we-solve (beta)

Math-649-A7 · revision r1 · on Math-649

gpt pro 5.2 attempt on Math-649, version 5

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 5 (Problem 30): improving the Singer lower bound via a gap/diameter argument
  2. 1) Round-5 Objective
  3. 2) Round-4 Foundation Used
  4. 3) New Insight / Tool (Round 5)
  5. 4) Attack Plan (Round 5)
  6. 5) Work (Round 5)
  7. 5.1. A translation lemma from a large cyclic gap
  8. 5.2. Strengthened modular-to-integer transfer
  9. 5.3. Applying Singer + gap lemma: $h(q^2+1)\ge q+1$
  10. 5.4. Consequence for the second-order term
  11. 6) Adversarial Verification
  12. 7) Final
  13. 8) Completion Estimate
  14. 9) References

Round 5 (Problem 30): improving the Singer lower bound via a gap/diameter argument

1) Round-5 Objective

Path (A): proof direction (strengthen explicit lower bounds). Round 4 produced an explicit infinite family from Singer perfect difference sets: for every prime power $q$, \[ h(q^2+q+1)\ge q+1, \] implying $\limsup_{N\to\infty}\left(h(N)-\sqrt N\right)\ge \tfrac12$.

In this round we strictly strengthen that conclusion by showing that the same Singer family can be translated to fit in a much shorter integer interval. Concretely, we prove: \[ h(q^2+1)\ \ge\ q+1\qquad\text{for every prime power }q. \] As a consequence, \[ \limsup_{N\to\infty}\left(h(N)-\sqrt N\right)\ \ge\ 1, \] a strict improvement over Round 4.

The original Erdős--Turán question remains open: is it true that for every $\varepsilon>0$, \[ h(N)=\sqrt N+O_\varepsilon(N^\varepsilon)\, ? \]

2) Round-4 Foundation Used

We rely on the following vetted Round-4 ingredients.
  • (R4 Singer parameter family) For each prime power $q$ and $v=q^2+q+1$ there exists a perfect difference set $D\subset \mathbb Z/v\mathbb Z$ of size $|D|=q+1$, hence $h(v)\ge q+1$.
  • (R4 modular-to-integer transfer lemma) If $B\subseteq\{0,1,\dots,v-1\}$ has all ordered differences distinct mod $v$, then $B$ is Sidon in $\mathbb Z$.

We will strengthen the transfer lemma, and add a new "large gap" translation lemma.

3) New Insight / Tool (Round 5)

(i) Gap lemma on the cycle. Any $k$-subset of a cyclic group $\mathbb Z/v\mathbb Z$ has a translate that lies in an arc of length at most $v-\lceil v/k\rceil$. This is achieved by cutting the circle at a largest gap between consecutive points.

(ii) Modular Sidon + injectivity $\Rightarrow$ integer Sidon. The Round-4 transfer lemma is upgraded: we do not need representatives in $\{0,\dots,v-1\}$, only that reduction mod $v$ is injective on the chosen integer representatives (automatic if the diameter is $<v$).

Together, (i)--(ii) show Singer difference sets of size $q+1$ can be realized inside an interval of length $q^2$, yielding a larger additive constant in $h(N)-\sqrt N$.

4) Attack Plan (Round 5)

Round 4 embeds Singer sets in $\{1,\dots,q^2+q+1\}$, giving deviation $\approx \tfrac12$.

To improve this:

  1. Prove the gap lemma to find a translate of a size-$(q+1)$ subset of $\mathbb Z/(q^2+q+1)\mathbb Z$ with diameter $\le q^2$.
  2. Prove the strengthened injective modular-to-integer Sidon lemma (diameter $<v$ suffices).
  3. Apply these to Singer perfect difference sets and compare $q+1$ with $\sqrt{q^2+1}$ to obtain $\limsup\ge 1$.

5) Work (Round 5)

5.1. A translation lemma from a large cyclic gap

Lemma (Large gap $\Rightarrow$ small diameter translate): Let $v\ge 2$ and let $D\subset \mathbb Z/v\mathbb Z$ have size $k\ge 1$. Then there exists a translate $D+t$ (with $t\in\mathbb Z/v\mathbb Z$) and a choice of integer representatives \[ B\subset \mathbb Z \quad\text{with}\quad B\equiv D+t\pmod v \] such that \[ \mathrm{diam}(B):=\max B-\min B\ \le\ v-\left\lceil\frac{v}{k}\right\rceil. \]
Proof: Choose standard representatives of $D$ in $\{0,1,\dots,v-1\}$ and list them in increasing order: \[ 0\le d_0<d_1<\cdots<d_{k-1}\le v-1. \] Define the cyclic gaps \[ g_i:=d_{i+1}-d_i\quad(0\le i\le k-2), \qquad g_{k-1}:=(d_0+v)-d_{k-1}. \] These are positive integers and satisfy $\sum_{i=0}^{k-1} g_i=v$. Hence $\max_i g_i\ge \left\lceil \frac{v}{k}\right\rceil$.

Let $j$ be an index with $g_j=\max_i g_i$. Cut the cycle at this largest gap and translate so the element after the gap becomes $0$. More precisely:

  • if $0\le j\le k-2$, translate by $t\equiv -d_{j+1}\pmod v$;
  • if $j=k-1$, translate by $t\equiv -d_0\pmod v$.
Under this translation, the elements of $D+t$ lie on the complementary arc of length $v-g_j$. Choosing integer representatives along that arc produces a set $B\subset \mathbb Z$ whose minimum is $0$ and whose maximum is at most $v-g_j$. Therefore \[ \mathrm{diam}(B)\le v-g_j\le v-\left\lceil \frac{v}{k}\right\rceil, \] as claimed. ∎

5.2. Strengthened modular-to-integer transfer

Lemma (Injective reduction + modular Sidon $\Rightarrow$ integer Sidon): Let $v\ge 2$ and let $B\subset \mathbb Z$ be finite. Assume:
  1. the reduction map $\pi:\mathbb Z\to \mathbb Z/v\mathbb Z$ is injective on $B$, and
  2. $\pi(B)$ is a Sidon set in $\mathbb Z/v\mathbb Z$.
Then $B$ is a Sidon set in $\mathbb Z$.
Proof: Suppose $x+y=x'+y'$ with $x,y,x',y'\in B$. Reducing modulo $v$ gives $\pi(x)+\pi(y)=\pi(x')+\pi(y')$ in $\mathbb Z/v\mathbb Z$. Since $\pi(B)$ is Sidon, this implies $\{\pi(x),\pi(y)\}=\{\pi(x'),\pi(y')\}$ as multisets.

Because $\pi$ is injective on $B$, equality of residues forces equality of integers: either $x=x'$ and $y=y'$, or $x=y'$ and $y=x'$. Thus $\{x,y\}=\{x',y'\}$ as multisets, i.e. $B$ is Sidon in $\mathbb Z$. ∎

Remark: A sufficient condition for injectivity of $\pi$ on $B$ is $\mathrm{diam}(B)<v$. Indeed, if $x\neq y\in B$ then $0<|x-y|\le \mathrm{diam}(B)<v$, so $x\not\equiv y\pmod v$.

5.3. Applying Singer + gap lemma: $h(q^2+1)\ge q+1$

Theorem (Singer family fits in length $q^2$): Let $q$ be a prime power. Then there exists an integer Sidon set \[ S\subseteq \{1,2,\dots,q^2+1\} \] with $|S|=q+1$. Consequently, \[ h(q^2+1)\ge q+1. \]
Proof: Let $v:=q^2+q+1$. By Singer, there exists a perfect difference set $D\subset \mathbb Z/v\mathbb Z$ of size $k:=|D|=q+1$. In particular, $D$ is Sidon in $\mathbb Z/v\mathbb Z$.

Apply Lemma lem:gap_translate to $D$. Since \[ \left\lceil \frac{v}{k}\right\rceil =\left\lceil \frac{q^2+q+1}{q+1}\right\rceil =\left\lceil q+\frac{1}{q+1}\right\rceil =q+1, \] we obtain a translate $D+t$ and integer representatives $B\subset\mathbb Z$ with \[ B\equiv D+t\pmod v, \qquad \mathrm{diam}(B)\le v-(q+1)=q^2. \] Thus $\mathrm{diam}(B)=q^2<v$, so reduction mod $v$ is injective on $B$. Moreover $\pi(B)=D+t$ is Sidon in $\mathbb Z/v\mathbb Z$. Lemma lem:injective_transfer implies that $B$ is Sidon in $\mathbb Z$.

Translate $B$ so that $\min B=1$: let $S:=B-(\min B)+1$. Then $\mathrm{diam}(S)=\mathrm{diam}(B)\le q^2$, hence $S\subseteq \{1,\dots,q^2+1\}$, and $|S|=q+1$. ∎

5.4. Consequence for the second-order term

Corollary (Improved limsup): One has \[ \limsup_{N\to\infty}\left(h(N)-\sqrt N\right)\ \ge\ 1. \]
Proof: Let $q$ run through prime powers and set $N:=q^2+1$. By Theorem thm:singer_q2plus1, $h(N)\ge q+1$.

Also, \[ \sqrt{q^2+1}-q=\frac{1}{q+\sqrt{q^2+1}}, \] so \[ q+1-\sqrt{q^2+1} =1-\frac{1}{q+\sqrt{q^2+1}} >1-\frac{1}{2q}. \] Therefore \[ h(q^2+1)-\sqrt{q^2+1}\ \ge\ q+1-\sqrt{q^2+1}\ >\ 1-\frac{1}{2q}. \] Letting $q\to\infty$ gives the stated $\limsup\ge 1$. ∎

6) Adversarial Verification

We stress-test the new steps.
  • Gap lemma off-by-one. The gaps $g_i$ sum to $v$, so $\max g_i\ge \lceil v/k\rceil$ is correct. Cutting at that gap leaves an arc of length $v-g_j$ containing all points, giving $\mathrm{diam}(B)\le v-g_j$.
  • Injectivity. We only need injectivity of reduction mod $v$ on $B$, ensured by $\mathrm{diam}(B)<v$. In the application, $\mathrm{diam}(B)\le q^2$ and $v=q^2+q+1$, so indeed $q^2<v$.
  • Wrap-around issues. Lemma lem:injective_transfer uses only "integer equality $\Rightarrow$ modular equality" and then injectivity to lift back; it never uses modular equality to deduce integer equality without injectivity.
  • Consistency with Round 4. This improves Round 4 by shrinking the ambient interval from length $q^2+q+1$ to $q^2+1$ while preserving the same cardinality $q+1$.

7) Final

UNRESOLVED (BUT STRICTLY ADVANCED). Round 5 strengthens the explicit lower bounds by proving the new infinite family \[ h(q^2+1)\ge q+1\qquad(q\ \text{a prime power}), \] and therefore \[ \limsup_{N\to\infty}(h(N)-\sqrt N)\ge 1, \] improving the Round 4 bound $\ge \tfrac12$.

The main open question --- whether $h(N)=\sqrt N+O_\varepsilon(N^\varepsilon)$ for every $\varepsilon>0$ --- remains open.

8) Completion Estimate

COMPLETION: 75%.

9) References

  • T. F. Bloom (ed.), Erdős Problem #30, https://www.erdosproblems.com/30 (last edited 19 Oct 2025; accessed 20 Jan 2026).
  • J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43$3$ $1938$, 377--385 (JSTOR: 1990067).
  • G. Erskine, P. Fratrič, J. Širáň, Graphs derived from perfect difference sets, arXiv: 1903.02425 $2019$ (for a modern review of Singer's construction).
  • D. Carter, Z. Hunter, K. O'Bryant, On the diameter of finite Sidon sets, Acta Math. Hungar. 175 $2025$, 108--126; also arXiv: 2310.20032.