Sidon set density inside (4,5) sets
Description of constant
$C_{5b}$ is the largest constant such that every $(4,5)$-set of size $n$ (i.e., a set of reals such that every four-element subset determines at least five distinct differences) contains a Sidon set of cardinality $C_{5b}n$.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $1$ | Trivial | |
| $\frac{3}{5} = 0.6$ | [GL95] | |
| $\frac{4}{7} \approx 0.5714$ | [MT26] |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $\frac{1}{2}$ | [GL95] | A short 2-colorability argument |
| $\frac{1}{2} + \frac{1}{141 \times 76} \approx 0.500093$ | [GL95] | |
| $\frac{9}{17} \approx 0.5294$ | [MT26] |
Additional comments and links
- Determining $C_{5b}$ is Erdős problem #757.
- Write $f(n) := \min \{ h(A) : A \text{ a } (4,5)\text{-set with } \lvert A \rvert = n \}$, where $h(A)$ is the size of the largest Sidon subset of $A$, so that $C_{5b} = \inf_n f(n)/n$ [MT26]. The exact values $f(n) = 4, 5, 5, 6, 6, 7, 7, 8, 8, 9$ for $6 \le n \le 15$, and $f(17) = 10$, $f(19) = 11$, $f(21) = 12$, are known: for each such $n$ an explicit $(4,5)$-set of $n$ integers attains the lower bound $f(n) \ge n - \lfloor (8n-6)/17 \rfloor$, which follows from Lemma 2.4 and Theorem 5.3 (Henning–Yeo) of [MT26] when the $-6$ is kept. The sets and an exact checker are in [SK2026]. None of these improves the upper bound $4/7$, and a computer search at $n = 16, 18, 20, 22, 23, 25, 30$ (the sizes where that lower bound still allows $f(n) < 4n/7$) found no $(4,5)$-set with $h(A) < \lceil 4n/7 \rceil$.
References
- [GL95] A. Gyárfás and J. Lehel, Linear sets with five distinct differences among any four elements, J. Combin. Theory Ser. B 64 (1995), 108–118.
- [MT26] Jie Ma and Quanyu Tang, Largest Sidon subsets in weak Sidon sets. arXiv:2602.23282 (2026).
- [SK2026] Suresh Kannan, S. Exact small values for Erdős problem #757: Sidon subsets of (4,5)-sets. Data and checker, 2026. GitHub, commit afa2e10
Contribution notes
The small-$n$ data, checker and the comment on exact values were prepared with Claude Code (Anthropic) under the direction of the contributor.