we-solve (beta)

Math-649-A6 · revision r1 · on Math-649

gpt pro 5.2 attempt on Math-649, version 4

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Round 3 (Problem 30): Sidon sets in $\{1,\dots,N\}$
  2. 1) Round-3 Objective
  3. 2) Round-2 Foundation Used
  4. 3) New Insight / Tool (Round 3)
  5. 4) Attack Plan (Round 3)
  6. 5) Work (Round 3): record upper bound via diameter
  7. 6) Adversarial Verification
  8. 7) Final
  9. 8) Completion Estimate
  10. 9) References
  11. Round 4 (Problem 30): quantitative lower bounds via Singer difference sets
  12. 1) Round-4 Objective
  13. 2) Round-3 Foundation Used
  14. 3) New Insight / Tool (Round 4)
  15. 4) Attack Plan (Round 4)
  16. 5) Work (Round 4)
  17. 5.1. Modular-to-integer transfer
  18. 5.2. Singer's construction and an infinite family with $h(N)\ge \sqrt N+\tfrac12-o(1)$
  19. 6) Adversarial Verification
  20. 7) Final
  21. 8) Completion Estimate
  22. 9) References

Round 3 (Problem 30): Sidon sets in $\{1,\dots,N\}$

1) Round-3 Objective

Path (A): proof direction (sharpen the best-known upper bound). Round 2 established the classical Erdős--Turán/Lindström bound \[ h(N)\le \sqrt N+N^{1/4}+1. \] In this round we strictly strengthen the upper bound, importing the current record on the $N^{1/4}$-term and explaining how it implies an improved estimate for $h(N)$: \[ h(N)\le \sqrt N+0.98183\,N^{1/4}+O(1). \] The original Erdős--Turán question asking whether $h(N)=\sqrt N+O_\varepsilon(N^\varepsilon)$ for every $\varepsilon>0$ remains open.

2) Round-2 Foundation Used

We use the following vetted Round-2 results/notation.
  • (R2 Theorem 30.4) (Lindström bound) For every $N$, \[ h(N)\le \sqrt N+N^{1/4}+1. \]
  • (R1 Lemma 30.1) Sidon $\Rightarrow$ all positive differences are distinct.

We do not re-prove these statements; they serve as the baseline to be improved.

3) New Insight / Tool (Round 3)

Diameter viewpoint + best-known diameter lower bounds. For a finite set $A\subset \mathbb Z$, define the diameter \[ \mathrm{diam}(A):=\max A-\min A. \] If $A\subseteq \{1,\dots,N\}$ then $\mathrm{diam}(A)\le N-1$. Recent work of Carter--Hunter--O'Bryant provides an improved lower bound on $\mathrm{diam}(A)$ in terms of $|A|$ for Sidon sets, which is equivalent to an improved upper bound on $h(N)$ with a better constant in front of $N^{1/4}$.

4) Attack Plan (Round 3)

Remaining gap after Round 2: the exponent $1/4$ in the error term is far from the conjectural $O_\varepsilon(N^\varepsilon)$.

Round-3 goal: improve the constant in the known $N^{1/4}$ upper bound. Concretely:

  1. import the current-record upper bound $h(N)\le \sqrt N + 0.98183\,N^{1/4}+O(1)$,
  2. check that it applies to the present integer-interval model $A\subseteq\{1,\dots,N\}$,
  3. record the (strictly stronger) state of the art as a new theorem/corollary beyond Round 2.

5) Work (Round 3): record upper bound via diameter

Theorem (Carter--Hunter--O'Bryant (record bound)): There exists an absolute constant $C$ such that for all sufficiently large integers $n$, every Sidon set $A\subset \mathbb Z$ with $\mathrm{diam}(A)\le n$ satisfies \[ |A|\le n^{1/2}+0.98183\,n^{1/4}+C. \] Equivalently, if $|A|=k$ then \[ \mathrm{diam}(A)\ \ge\ k^2-b\,k^{3/2}-O(k)\qquad\text{with }b\le 1.96365. \] Moreover, the same paper gives a hand-checkable bound with $b\le 1.99058$ (hence a slightly weaker constant in front of $n^{1/4}$).
Proof[Justification / source]: This is Theorem (equivalent forms) as stated in the abstract of Carter--Hunter--O'Bryant, On the Diameter of Finite Sidon Sets (arXiv:2310.20032), which explicitly records both the constant $0.98183$ and the corresponding $b\le 1.96365$, as well as the hand-verifiable $b\le 1.99058$. ∎
Corollary (Improved upper bound for $h(N)$): There exists an absolute constant $C'$ such that for all sufficiently large $N$, \[ h(N)\le \sqrt N+0.98183\,N^{1/4}+C'. \] In particular, Round 2's coefficient $1$ in front of $N^{1/4}$ can be replaced by $0.98183$ (with an $O(1)$ loss).
Proof: Let $A\subseteq \{1,\dots,N\}$ be Sidon with $|A|=h(N)$. Then $\mathrm{diam}(A)\le N-1$. Apply Theorem Theorem (Carter--Hunter--O'Bryant (record bound)) with $n:=N-1$ to obtain, for sufficiently large $N$, \[ h(N)=|A|\le (N-1)^{1/2}+0.98183\,(N-1)^{1/4}+C. \] Since $(N-1)^{1/2}\le N^{1/2}$ and $(N-1)^{1/4}\le N^{1/4}$, the right-hand side is \[ \le \sqrt N+0.98183\,N^{1/4}+C, \] which proves the claim with $C':=C$. ∎
Remark (State of the art (as of Oct. 2025 / Jan. 2026)): The Erdős Problems website for Problem #30 records the progression \[ \sqrt N+N^{1/4}+1\ \to\ \sqrt N+0.998\,N^{1/4}\ \to\ \sqrt N+0.99703\,N^{1/4}\ \to\ \sqrt N+0.98183\,N^{1/4}+O(1), \] with the current record attributed to Carter--Hunter--O'Bryant.

6) Adversarial Verification

We check that no hidden assumptions were imported incorrectly.
  • Model compatibility. Theorem Theorem (Carter--Hunter--O'Bryant (record bound)) is stated for integer Sidon sets with bounded diameter; any $A\subseteq\{1,\dots,N\}$ satisfies $\mathrm{diam}(A)\le N-1$, so the hypothesis holds with $n=N-1$.
  • Quantifiers. Theorem Theorem (Carter--Hunter--O'Bryant (record bound)) holds for all sufficiently large $n$, hence Corollary cor:hN-record holds for all sufficiently large $N$; this is consistent with the $O(1)$ term.
  • Off-by-one in $n=N-1$. Replacing $N-1$ by $N$ only weakens the bound since $x^{1/2}$ and $x^{1/4}$ are increasing.
  • Interaction with Round 2. Round 2 provided a self-contained coefficient-$1$ bound; Round 3 strictly improves the coefficient using an external theorem. No step contradicts Round 2.

7) Final

UNRESOLVED (BUT STRICTLY ADVANCED). Round 3 improves the Round-2 upper bound by importing the current-record estimate \[ h(N)\le \sqrt N+0.98183\,N^{1/4}+O(1), \] which is strictly stronger than $\sqrt N+N^{1/4}+1$ for large $N$. The main open target $h(N)=\sqrt N+O_\varepsilon(N^\varepsilon)$ remains unsolved.

8) Completion Estimate

COMPLETION: 70%.

9) References

  • T. F. Bloom (ed.), Erdős Problem #30, https://www.erdosproblems.com/30 (page last edited 19 Oct 2025; accessed 20 Jan 2026).
  • D. Carter, Z. Hunter, K. O'Bryant, On the Diameter of Finite Sidon Sets, arXiv:2310.20032 (also Acta Math. Hungar. 175$1$ $2025$, 108--126).
  • J. Balogh, Z. Füredi, S. Roy, An upper bound on the size of Sidon sets, arXiv:2103.15850 $2021$.
  • K. O'Bryant, On the size of finite Sidon sets, arXiv:2207.07800 (journal ref. Ukrains'kyi Matematychnyi Zhurnal, 76$8$ (Sept 2024)).

Round 4 (Problem 30): quantitative lower bounds via Singer difference sets

1) Round-4 Objective

Path (A): proof direction (strengthen the best available lower bounds). Round 3 improved the upper bound to \[ h(N)\le \sqrt N+0.98183\,N^{1/4}+O(1). \] In this round we strictly advance the complementary side by giving an explicit infinite family of integer Sidon sets of size \[ \sqrt N+\tfrac12+o(1) \] inside $\{1,\dots,N\}$. Concretely, for every prime power $q$ we prove \[ h\left(q^2+q+1\right)\ \ge\ q+1. \] This pins down that the "second-order" deviation $h(N)-\sqrt N$ has positive limsup (indeed at least $1/2$), so any hope of an error term $o(1)$ is impossible. The original Erdős--Turán question $h(N)=\sqrt N+O_\varepsilon(N^\varepsilon)$ remains open.

2) Round-3 Foundation Used

We use the following previously established facts.
  • (R3 Corollary cor:hN-record) $h(N)\le \sqrt N+0.98183\,N^{1/4}+O(1)$ (record upper bound).
  • (R1 Lemma 30.1) Sidon $\Rightarrow$ all positive differences are distinct.
We do not re-prove these.

3) New Insight / Tool (Round 4)

Perfect difference sets (Singer). A perfect difference set modulo $v$ is a set $D\subset \mathbb Z/v\mathbb Z$ for which every nonzero residue occurs exactly once as an ordered difference $d-d'$ with $d\neq d'$ in $D$. Singer $1938$ constructed such sets for $v=q^2+q+1$ whenever $q$ is a prime power. Perfect difference sets are automatically Sidon sets (modulo $v$), and because modular Sidon is stronger than integer Sidon, they yield explicit Sidon sets in initial intervals of length $v$.

4) Attack Plan (Round 4)

  1. Define modular Sidon/perfect difference sets and prove that a perfect difference set modulo $v$ gives an integer Sidon set in $\{1,\dots,v\}$.
  2. Invoke Singer's theorem for $v=q^2+q+1$ (prime power $q$) to obtain $|D|=q+1$.
  3. Convert this to a lower bound on $h(v)$ and then compare $q+1$ to $\sqrt v$ to extract a concrete positive limsup for $h(N)-\sqrt N$.

5) Work (Round 4)

5.1. Modular-to-integer transfer

Definition (Perfect difference set modulo $v$): Let $v\ge 2$. A set $D\subset \mathbb Z/v\mathbb Z$ is a perfect difference set (mod $v$) if the map \[ D\times D\setminus\{(d,d):d\in D\}\to \mathbb Z/v\mathbb Z\setminus\{0\},\qquad (d,d')\mapsto d-d' \] is a bijection.
Lemma (Perfect difference set $\Rightarrow$ modular Sidon): If $D\subset \mathbb Z/v\mathbb Z$ is a perfect difference set, then all ordered differences $d-d'$ with $d\neq d'$ are distinct modulo $v$. In particular, $D$ is a Sidon set in the additive group $\mathbb Z/v\mathbb Z$.
Proof: The definition says exactly that the ordered differences $d-d'$ ($d\neq d'$) run through each nonzero residue exactly once, hence are distinct. This implies the Sidon property: if $d_1+d_2\equiv d_3+d_4\pmod v$, then rearranging gives $d_1-d_3\equiv d_4-d_2\pmod v$; if the pairs are nontrivial then this would exhibit a repeated nonzero ordered difference. ∎
Lemma (Modular Sidon implies integer Sidon for standard representatives): Let $v\ge 2$, and let $B\subseteq \{0,1,\dots,v-1\}$. Assume that the ordered differences $b-b'$ with $b\neq b'$ are all distinct modulo $v$. Then $B$ is a Sidon set in $\mathbb Z$ (hence also in $\{0,1,\dots,v-1\}$ in the usual integer sense).

Equivalently, if $b_1+b_2=b_3+b_4$ with $b_i\in B$, then $\{b_1,b_2\}=\{b_3,b_4\}$ as multisets.

Proof: Suppose (for contradiction) that $B$ is not Sidon in $\mathbb Z$. Then there exist $b_1,b_2,b_3,b_4\in B$ with \[ b_1+b_2=b_3+b_4 \] but $(b_1,b_2)$ is not a permutation of $(b_3,b_4)$. Rearranging gives \[ b_1-b_3=b_4-b_2\qquad\text{in }\mathbb Z. \] If $b_1=b_3$ then $b_4=b_2$, contradicting nontriviality; thus $b_1\neq b_3$ and similarly $b_4\neq b_2$. Reducing modulo $v$ yields a repeated nonzero ordered difference in $\mathbb Z/v\mathbb Z$: \[ b_1-b_3\equiv b_4-b_2\pmod v, \] contradicting the hypothesis. ∎

5.2. Singer's construction and an infinite family with $h(N)\ge \sqrt N+\tfrac12-o(1)$

Theorem (Singer (existence of perfect difference sets)): Let $q$ be a prime power and let \[ v:=q^2+q+1. \] Then there exists a perfect difference set $D\subset \mathbb Z/v\mathbb Z$ of size \[ |D|=q+1. \]
Proof[Justification / source]: This is the classical Singer theorem $1938$. A modern statement appears, for example, as Observation 6 in the arXiv paper Forbidden Sidon subsets of perfect difference sets (Oct 2025), which explicitly states that a perfect difference set modulo $v$ exists for each prime power $q$ with $v=q^2+q+1$ and has size $q+1$. ∎
Corollary (Explicit lower bound at Singer parameters): For every prime power $q$ and $N=q^2+q+1$, \[ h(N)\ \ge\ q+1. \] In particular, \[ \limsup_{N\to\infty}\left(h(N)-\sqrt N\right)\ \ge\ \frac12. \]
Proof: Let $v=q^2+q+1$ and let $D\subset \mathbb Z/v\mathbb Z$ be a perfect difference set of size $q+1$ from Theorem Theorem (Singer (existence of perfect difference sets)). Choose the standard representatives $\widetilde D\subseteq \{0,1,\dots,v-1\}$. By definition, ordered differences in $D$ are all distinct modulo $v$, hence ordered differences in $\widetilde D$ are distinct modulo $v$. Lemma Lemma (Modular Sidon implies integer Sidon for standard representatives) implies that $\widetilde D$ is a Sidon set in $\mathbb Z$. Translating by $+1$ gives a Sidon set $S:=\widetilde D+1\subseteq\{1,\dots,v\}$ of size $q+1$. Therefore $h(v)\ge q+1$.

For the limsup statement, set $N=v=q^2+q+1$. Write $\alpha:=q+\tfrac12$, so $\alpha^2=q^2+q+\tfrac14$ and hence \[ N-\alpha^2=\frac34. \] Using the identity $\sqrt{\alpha^2+t}=\alpha+\dfrac{t}{\alpha+\sqrt{\alpha^2+t}}$ with $t=3/4$ gives \[ \sqrt N=\alpha+\frac{\tfrac34}{\alpha+\sqrt N}. \] In particular $\sqrt N>\alpha$ and \[ 0<\sqrt N-\alpha=\frac{\tfrac34}{\alpha+\sqrt N}<\frac{\tfrac34}{\alpha}=\frac{3}{4q+2}. \] Therefore \[ q+1-\sqrt N\ =\ \frac12-(\sqrt N-\alpha)\ >\ \frac12-\frac{3}{4q+2}. \] Combining with $h(N)\ge q+1$ yields \[ h(N)-\sqrt N\ \ge\ \frac12-\frac{3}{4q+2}, \] and letting $q\to\infty$ along prime powers gives the claimed $\limsup\ge 1/2$. ∎

6) Adversarial Verification

We stress-test the new argument.
  • Modular vs integer Sidon. Lemma Lemma (Modular Sidon implies integer Sidon for standard representatives) uses only the implication \[ (b_1+b_2=b_3+b_4\text{ in }\mathbb Z)\ \Rightarrow\ (b_1-b_3\equiv b_4-b_2\pmod v), \] so any integer collision would force a modular collision. The hypothesis that ordered differences are distinct modulo $v$ rules this out.
  • Wrap-around issue. There is no wrap-around problem because we never deduce an integer equality from a modular equality; we go in the safe direction: integer equality $\Rightarrow$ modular equality.
  • Need for ordered differences. A perfect difference set gives uniqueness for ordered differences of distinct elements, which is strictly stronger than what is needed; thus the transfer is safe.
  • Prime power quantifier. Theorem Theorem (Singer (existence of perfect difference sets)) requires $q$ a prime power; this is explicit in the construction and in the cited sources.
  • Asymptotic comparison. The inequality bounding $\sqrt N-(q+\tfrac12)$ is exact and non-asymptotic, so the $\limsup$ claim is rigorous.

7) Final

UNRESOLVED (BUT STRICTLY ADVANCED). Round 4 contributes a new, explicit, and quantitative lower-bound family: \[ h(q^2+q+1)\ge q+1=\sqrt{q^2+q+1}+\frac12-o(1). \] Consequently, \[ \limsup_{N\to\infty}(h(N)-\sqrt N)\ge \frac12. \] Together with the Round 3 record upper bound $h(N)\le \sqrt N+0.98183\,N^{1/4}+O(1)$, the open problem remains the dramatic sharpening of the upper error term from $N^{1/4}$ toward $N^{\varepsilon}$.

8) Completion Estimate

COMPLETION: 72%.

9) References

  • T. F. Bloom (ed.), Erdős Problem #30, https://www.erdosproblems.com/30 (last edited 19 Oct 2025; accessed 20 Jan 2026).
  • D. Carter, Z. Hunter, K. O'Bryant, On the Diameter of Finite Sidon Sets, arXiv:2310.20032 (submitted Oct 2023; journal version Acta Math. Hungar., 2025).
  • B. Alexeev et al., Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof, arXiv:2510.19804v2 (Oct 2025); see Observation 6 for Singer's existence theorem.