gpt pro 5.2 attempt on Math-841
mathematicsErdős problemscontributionManuscript
Contents
Let $\ell(N)$ be maximal such that in any finite set $A\subset \mathbb{R}$ of size $N$ there exists a Sidon subset $S$ of size $\ell(N)$ (i.e. the only solutions to $a+b=c+d$ in $S$ are the trivial ones). Determine the order of $\ell(N)$. In particular, is it true that $\ell(N)\sim N^{1/2}$? Originally asked by Riddell [Ri69]. Erdős noted the bounds\[N^{1/3} \ll \ell(N) \leq (1+o(1))N^{1/2}\](the upper bound following from the case $A=\{1,\ldots,N\}$). The lower bound was improved to $N^{1/2}\ll \ell(N)$ by Komlós, Sulyok, and Szemerédi [KSS75]. The correct constant is unknown, but it is likely that the upper bound is true, so that $\ell(N)\sim N^{1/2}$. In [AlEr85] Alon and Erdős make the stronger conjecture that perhaps $A$ can always be written as the union of at most $(1+o(1))N^{1/2}$ many Sidon sets. (This is easily verified for $A=\{1,\ldots,N\}$ using standard constructions of Sidon sets.) This is discussed in problem C9 of Guy's collection [Gu04]. See also [1088] for a higher-dimensional generalisation. References [AlEr85] Alon, Noga and Erdős, P., An application of graph theory to additive number theory . European J. Combin. $1985$, 201-203. [Gu04] Guy, Richard K., Unsolved problems in number theory . $2004$, xviii+437. [KSS75] Komlós, J. and Sulyok, M. and Szemeredi, E., Linear problems in combinatorial number theory . Acta Math. Acad. Sci. Hungar. $1975$, 113-121. [Ri69] Riddell, J., On sets of numbers containing no $l$ terms in arithmetic progression . Nieuw Arch. Wisk. $3$ $1969$, 204-209.
FORMAL RESTATEMENT
For an integer $N\ge 1$, define \[ \ell(N):=\min\Big\{\max\{|S|:S\subseteq A,\ S\ \text{is Sidon}\}: A\subset\mathbb R,\ |A|=N\Big\}. \] Here a finite set $S\subset\mathbb R$ is Sidon if every solution to $a+b=c+d$ with $a,b,c,d\in S$ is trivial in the sense that $\{a,b\}=\{c,d\}$ as multisets (equivalently: the sums $a+b$ with $a\le b$ are all distinct). The problem asks for the asymptotic order of growth of $\ell(N)$ as $N\to\infty$, and in particular whether $\ell(N)\sim N^{1/2}$.QUICK LITERATURE/CONTEXT CHECK
The statement records: Erdős' bounds $N^{1/3} \ll \ell(N) \le (1+o(1))N^{1/2}$ and an improvement of the lower bound to $\ell(N)\gg N^{1/2}$ by Komlós--Sulyok--Szemerédi [KSS75], plus conjectures in [AlEr85]. Per the integrity rule I do not claim or use any result beyond what is explicitly written in the problem text; instead I re-derive the $N^{1/3}$ lower bound and the $\sqrt N$ upper bound for $A=[N]$ from first principles.ATTACK PLAN
Proof-track ideas. (i) Upper bound: show for $A=\{1,\dots,N\}$ any Sidon subset has size $O(\sqrt N)$ by counting distinct sums. (ii) Lower bound: model all nontrivial additive collisions $a+b=c+d$ as edges of a small-uniformity hypergraph and find a large independent set by the probabilistic method; this yields a universal Sidon subset of size $\gg N^{1/3}$.Disproof-track ideas. To disprove $\ell(N)\sim \sqrt N$ one would need either (a) a family of sets $A$ where every Sidon subset is $o(\sqrt N)$, or (b) a proof that a universal $\gg\sqrt N$ lower bound fails. I do not find an explicit construction here.
WORK
A bad quadruple can involve either $4$ distinct elements or exactly $3$ distinct elements (the $2$-distinct case forces $\{a,b\}=\{c,d\}$). Indeed, if $a+b=c+d$ with $\{a,b\}\ne\{c,d\}$, and some element appears three times then the fourth appearance forces triviality; thus only $3$ or $4$ distinct elements can occur.
Step 1: encode bad configurations as hyperedges. Construct a $3$-uniform hypergraph $\mathcal H_3$ on vertex set $A$ whose hyperedges are triples $\{x,y,z\}$ of distinct vertices satisfying \[ x+y=2z, \] (which is exactly the form of a bad quadruple with three distinct elements, namely $x+y=z+z$). Construct a $4$-uniform hypergraph $\mathcal H_4$ on vertex set $A$ whose hyperedges are $4$-sets $\{a,b,c,d\}$ of distinct vertices for which $a+b=c+d$ in some ordering (which is exactly the form of a bad quadruple with four distinct elements).
If $S\subseteq A$ contains no hyperedge of $\mathcal H_3$ and no hyperedge of $\mathcal H_4$, then $S$ contains no bad quadruple, hence $S$ is Sidon.
Step 2: bound the number of hyperedges. For $\mathcal H_4$: choose an ordered triple $(a,b,c)\in A^3$; then $d$ is forced to be $d=a+b-c$. Hence the number of ordered solutions $(a,b,c,d)\in A^4$ to $a+b=c+d$ is at most $N^3$. Each unordered $4$-set hyperedge of $\mathcal H_4$ corresponds to at least one ordered solution, so \[ e(\mathcal H_4)\le N^3. \]
For $\mathcal H_3$: choose an ordered pair $(x,y)\in A^2$ with $x\ne y$; then $z$ is forced to be $z=(x+y)/2$. Hence the number of ordered solutions $(x,y,z)\in A^3$ to $x+y=2z$ with $x\ne y$ is at most $N^2$. Each unordered triple hyperedge corresponds to at least one ordered solution, so \[ e(\mathcal H_3)\le N^2. \]
Step 3: random sparsification and deletion. Choose a random subset $R\subseteq A$ by including each vertex independently with probability $p$. Let $X:=|R|$. Let $Y_3$ be the number of hyperedges of $\mathcal H_3$ fully contained in $R$, and $Y_4$ the number of hyperedges of $\mathcal H_4$ fully contained in $R$. Then \[ \mathbb E[X]=pN,\qquad \mathbb E[Y_3]=p^3 e(\mathcal H_3)\le p^3 N^2,\qquad \mathbb E[Y_4]=p^4 e(\mathcal H_4)\le p^4 N^3. \] Set $p:=\frac12 N^{-2/3}$. Then \[ \mathbb E[X]=\frac12 N^{1/3},\qquad \mathbb E[Y_3]\le \frac18 N^{1/3},\qquad \mathbb E[Y_4]\le \frac1{16} N^{1/3}. \] Hence $\mathbb E[X-Y_3-Y_4]\ge \left(\frac12-\frac18-\frac1{16}\right)N^{1/3}=\frac5{16}N^{1/3}$.
Now, from any specific $R$, delete one arbitrary vertex from each hyperedge contained in $R$ (first for the $3$-edges, then for the $4$-edges, or in any order). This produces a set $S\subseteq R$ containing no $\mathcal H_3$-edge and no $\mathcal H_4$-edge, and satisfying \[ |S|\ge |R|-Y_3-Y_4 = X-Y_3-Y_4. \] Therefore there exists a choice of $R$ for which $|S|\ge \frac5{16}N^{1/3}\ge \frac18 N^{1/3}$. By Step 1, this $S$ is Sidon. ∎
FAST REALITY CHECK (computation on the example $A=[N]$).
I computed by exhaustive backtracking the exact maximum size of a Sidon subset of $\{1,\dots,N\}$ for all $N\le 38$ (no timeouts in this range). The results support the $\Theta(\sqrt N)$ behavior in this model case.| $N$ | $\max\{|S|:S\subseteq [N]\ \text{Sidon}\}$ |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |
| 7 | 3 |
| 8 | 3 |
| 9 | 3 |
| 10 | 4 |
| 11 | 4 |
| 12 | 4 |
| 13 | 4 |
| 14 | 4 |
| 15 | 5 |
| 16 | 5 |
| 17 | 5 |
| 18 | 5 |
| 19 | 5 |
| 20 | 5 |
| 21 | 6 |
| 22 | 6 |
| 23 | 6 |
| 24 | 6 |
| 25 | 6 |
| 26 | 6 |
| 27 | 6 |
| 28 | 7 |
| 29 | 7 |
| 30 | 7 |
| 31 | 7 |
| 32 | 7 |
| 33 | 7 |
| 34 | 7 |
| 35 | 7 |
| 36 | 8 |
| 37 | 8 |
| 38 | 8 |
VERIFICATION
- Lemma lem:530-upper: verified that Sidon $\Rightarrow$ all unordered pair sums $a+b$ with $a\le b$ are distinct; counted them as $m(m+1)/2$; range of sums is exactly $\{2,\dots,2N\}$ of size $2N-1$.
- Lemma lem:530-lower: checked the classification of nontrivial equalities $a+b=c+d$ into either four distinct elements or the three-distinct form $x+y=2z$. Edge-count bounds $e(\mathcal H_3)\le N^2$ and $e(\mathcal H_4)\le N^3$ follow from direct forcing-counts.
- The deletion argument is deterministic and guarantees that after removing one vertex per surviving hyperedge, no hyperedge remains; thus the output set is Sidon.
FINAL
UNRESOLVED(i) Strongest proved partial result. For all $N$, $\ell(N)\gg N^{1/3}$ (Lemma lem:530-lower). Also the example $A=[N]$ forces $\ell(N)=O(\sqrt N)$ via Lemma lem:530-upper.
(ii) First gap (crisp statement). Prove (or disprove) that for every $A\subset\mathbb R$ with $|A|=N$ there exists a Sidon subset of size $\ge c\sqrt N$ for some absolute constant $c>0$ (and ideally determine the optimal constant).
(iii) Top 3 next moves. 1. Strengthen the $N^{1/3}$ argument by exploiting additive-structure dichotomies: either $A$ has low additive energy (so few collisions) or it has strong structure that can be handled separately. 2. Develop a container-style bound on the family of non-Sidon subsets of $A$ with improved independent set lower bounds. 3. Computationally: search for candidate worst-case sets $A$ (with many additive relations) and numerically estimate the largest Sidon subset size to guess extremal structure.
(iv) Minimal counterexample structure. A counterexample to $\ell(N)\asymp \sqrt N$ would be a family of sets $A_N$ of size $N$ with extremely many additive coincidences, arranged so that every subset of size $\gg \sqrt N$ still contains a nontrivial relation $a+b=c+d$ (including the three-distinct $x+y=2z$ type).