Erdős Problem #44

Erdős Problem #44 --- Round 4

1) ROUND-4 OBJECTIVE

Path (A): proof. Given the Round-3 status, the most promising direction is not to restart the global problem, but to close the cutoff-quantifier gap left by Round 2 and Round 3. Round 2 proved that every finite Sidon set extends to a Sidon superset of density $(1/\sqrt2-o(1))$ for some cutoff $M$, and Round 3 upgraded this to an infinite perfect-difference completion with the same limsup density. In this round I prove a strictly stronger finite theorem: \[ \textit{for every sufficiently large } M, \textit{ not merely for some } M, \] there is a Sidon extension of size at least $(1/\sqrt2-\varepsilon)\sqrt M$. This does not settle the original constant-$1$ target, but it eliminates the remaining "sporadic $M$" weakness in the Round-2 construction.

2) ROUND-3 FOUNDATION USED

I use the following previously established ingredient, which Round 3 explicitly preserved as valid progress from Round 2.

Round-2 block-extension construction. Fix a finite Sidon set $A\subset [N]$ and a prime power $q$. Put \[ L:=q^2+q+1. \] Whenever $L>N$, the Round-2 Singer-block + forbidden-difference pruning + sum-range separation argument produces a set \[ B\subset [N+L+1,\,N+2L] \] such that $A\cup B$ is Sidon and \[ |A\cup B|\ge q-N+2. \] I use this construction as a black box; I do not re-prove it here.

The unresolved issue after Round 3 was therefore not how to build one dense block, but how to choose the block order $q$ so that the resulting cutoff lands at a prescribed large $M$.

3) NEW INSIGHT / TOOL (ROUND-4)

The new ingredient is a prime-near-target selection lemma. By the prime number theorem, for every fixed $\delta>0$, every sufficiently large interval \[ [(1-\delta)x,\,x] \] contains a prime. Since a prime is a prime power, this lets us choose the Singer parameter $q$ very close to the target value \[ \sqrt{\frac{M-N}{2}}, \] so that the Round-2 block occupies almost exactly half of $[1,M]$. This upgrades "there exists some $M$" to "every sufficiently large $M$" without changing the constant $1/\sqrt2$.

4) ATTACK PLAN (ROUND-4)

Exact gap left after Round 3. Round 3 supplied infinitely many dense cutoffs, but not a theorem for a given large $M$.

Precise claim to prove now. For every finite Sidon set $A\subset [N]$ and every $\varepsilon>0$, there exists $M_0=M_0(A,\varepsilon)$ such that for every $M\ge M_0$ there exists \[ B\subset \{N+1,\dots,M\} \] with $A\cup B\subset [M]$ Sidon and \[ |A\cup B|\ge \left(\frac1{\sqrt2}-\varepsilon\right)\sqrt M. \]

Why this plan works. The Round-2 construction already gives the right density once $q$ is chosen. The only missing step is to ensure simultaneously that \[ q^2+q+1\le \frac{M-N}{2} \] and \[ q=(1-o(1))\sqrt{\frac M2}. \] A prime in a short relative interval does exactly this.

5) WORK (ROUND-4)

5.1\; Prime near a prescribed target

5.2\; Main theorem: every sufficiently large cutoff is admissible

5.3\; Reformulation of the advance

Theorem thm:cofinite-M strictly strengthens the Round-2 theorem. Round 2 gave, for fixed $(A,\varepsilon)$, existence of at least one suitable cutoff $M$. Round 4 gives every sufficiently large cutoff $M$. Thus the remaining gap to Erdős Problem #44 is no longer a quantifier problem about which $M$ are reachable; it is purely the density constant $1$ versus $1/\sqrt2$.

6) ADVERSARIAL VERIFICATION

• Did I accidentally use more than Round 2 proved? No. The only imported fact is the explicit Round-2 construction: for each prime power $q$ with $L=q^2+q+1>N$, it produces a block $B\subset [N+L+1,N+2L]$ and the lower bound $|A\cup B|\ge q-N+2$.

• Does the block really lie inside the prescribed ambient interval $[M]$? Yes. The estimate $L\le (M-N)/2$ gives $N+2L\le M$, so the entire Round-2 block sits inside $[N+1,M]$.

• Could $q$ be too small, invalidating the Round-2 separation argument? No. By construction $q\ge N$, hence $L=q^2+q+1>N$.

• Is the prime-selection lemma strong enough? Yes. We only need a prime in a fixed relative interval $[(1-\delta)x,x]$, and the prime number theorem implies this for all sufficiently large $x$.

• Boundary cases. If $\varepsilon\ge 1/\sqrt2$, the theorem is trivial. If $A=\varnothing$, the same proof works verbatim with any $N\ge 1$ such that $A\subset [N]$.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED). This round does not settle the original constant-$1$ conjecture. However, it proves a genuinely stronger theorem than any previous round: \[ \textit{for every finite Sidon set }A\subset [N]\textit{ and every }\varepsilon>0,\textit{ every sufficiently large }M \] admits a Sidon extension inside $[M]$ of size at least \[ \left(\frac1{\sqrt2}-\varepsilon\right)\sqrt M. \] So the Round-2 / Round-3 constant $1/\sqrt2$ is now available with the correct cofinite quantifier in $M$; the only unresolved issue is whether the constant can be pushed all the way from $1/\sqrt2$ to $1$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 78%

9) REFERENCES

• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008. (Prime number theorem.)
• J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 $1938$, 377--385. (Underlying finite-geometric Sidon block used in Round 2.)

Erdős Problem #44: independent continuation

Date: 23 September 2026. Source versions read in full: 44.tex in gpt_pro_5.4.

1) OBJECTIVE AND SOURCE AUDIT

Given a finite Sidon set $A\subset[1,N]$, the original problem asks for an extension of size $(1-\varepsilon)\sqrt M$ for some $M$. The supplied argument upgrades a previously asserted block construction to every sufficiently large cutoff, at constant $1/\sqrt2$. I audit that construction instead of assuming the missing earlier round. The following lemma also replaces a loss depending on $N$ by one depending on $|A|$.

2) WORK: EXPLICIT COMPATIBILITY PRUNING

Write $k=|A|$, assume $L\ge N$, and let $S\subset[1,L]$ be any Sidon set of size $s$. There is a subset $S'\subset S$ of size at least $s-\binom{k}{2}$ such that \[ A\cup(N+L+S')\quad\hbox{is Sidon}. \] For each positive difference in $A-A$, delete one endpoint of the pair in $S$ realizing that difference, if such a pair exists. Each difference has at most one such pair because $S$ is Sidon. The set of forbidden positive differences has size $\binom{k}{2}$, so at most that many points are deleted. Now $(S'-S')\cap(A-A)\subseteq\{0\}$.

Put $B=N+L+S'$. The three types of sums lie in disjoint intervals: \[ A+A\subset[2,2N],\quad A+B\subset[N+L+2,2N+2L],\quad B+B\subset[2N+2L+2,2N+4L], \] provided $L\ge N$. Sums of the first and third type are unique as unordered pairs by the individual Sidon hypotheses. An equality $a+b=a'+b'$ in the middle type would give $a-a'=b'-b$, hence $a=a'$ and $b=b'$. This proves the lemma, including sums with repeated summands.

In particular, whenever a Singer-type block of length $L=q^2+q+1$ and size $q+1$ is supplied with $L\ge N$, this gives \[ |A\cup B|\ge q+1+k-\binom{k}{2},\qquad A\cup B\subset[1,N+2L]. \] The bound is uniform over the locations of the old points. Using the standard prime-near-target selection from the supplied attempt yields $(1/\sqrt2-o(1))\sqrt M$ at every sufficiently large $M$, now with a completely explicit compatibility proof. This corollary is conditional only on the stated classical block input; the pruning lemma needs no finite-field theorem.

3) VERIFICATION AND REMAINING GAP

The factor $2L$ is essential to this particular proof: moving the new block down can make mixed sums overlap new--new sums. Avoiding old differences alone does not exclude these new collisions. Thus improved deletion costs do not turn $1/\sqrt2$ into $1$; the principal asymptotic gap is untouched. The all-large-$M$ conclusion is already in the source, not a new result here.

7) FINAL AND REFERENCE

UNRESOLVED. A self-contained block-compatibility lemma and a better finite loss are established; no constant-$1$ extension has been found. Official target checked through the indexed primary page: https://www.erdosproblems.com/44.

8) COMPLETION ESTIMATE

COMPLETION: 15% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Erdős Problem #44 --- Round 2

1) ROUND-2 OBJECTIVE

Path (A): proof. Round 1 isolated the key gap: Lemma 1 and Lemma 2 only add $O(\log M)$ new elements, whereas the target size is $\asymp \sqrt{M}$. In this round I push the block extension idea (Round-1 "next move" $2$) to obtain an unconditional constant-density extension. Specifically, I prove a gap-free theorem showing that every Sidon $A\subset [N]$ can be extended to a Sidon subset of some $[M]$ of size at least $(1/\sqrt2-\varepsilon)\sqrt M$. This does not settle the original $(1-\varepsilon)\sqrt M$ target, but it is a strict quantitative advance.

2) ROUND-1 FOUNDATION USED

I use the Round-1 formal restatement of the problem and the Round-1 identification of the main gap ("need $\Theta(\sqrt M)$ new elements without $M$ exponential"). I do not reuse Lemma 1 or Lemma 2 directly; instead I replace the exponential-growth tail with a dense block.

3) NEW INSIGHT / TOOL (ROUND-2)

New ingredients beyond Round 1:

• Sum-range separation. Place the new set $B$ inside a top interval of $[M]$ so that \[A+A \;<\; A+B \;<\; B+B\] (as sets of integers). This deletes the hardest mixed collisions (e.g. $a+b=b_1+b_2$) by sheer range separation.
• Forbidden-difference pruning lemma. Starting from any Sidon set $T$, delete at most $|F|$ elements to ensure that the remaining subset has no pairwise differences lying in a prescribed finite forbidden set $F$.
• Dense Sidon blocks from finite geometry. Use Singer's construction of a perfect difference set (hence Sidon set) of size $q+1$ inside $[q^2+q+1]$ for every prime power $q$.

4) ATTACK PLAN (ROUND-2)

Gap from Round 1. We need a mechanism to add many elements in $\{N+1,\dots,M\}$ while preserving Sidon-ness.

Plan. Fix $A\subset [N]$ Sidon and choose a large length $L$ and an interval \[I:=[N+L+1,\,N+2L]\subset [M],\qquad M:=N+2L. \] We will place $B\subset I$ so that:

1. $B$ itself is Sidon;
2. no nonzero difference of two elements of $B$ equals a difference of two elements of $A$;
3. because $I$ sits far above $[N]$, the sum-ranges $A+A$, $A+B$, $B+B$ are disjoint.

Then $A\cup B$ is Sidon by a direct case analysis. Choosing $L\approx q^2$ with $q$ large yields $|B|\approx \sqrt L$ and hence $|A\cup B|\approx \sqrt{M/2}=(1/\sqrt2)\sqrt M$.

5) WORK (ROUND-2)

5.1\; A Sidon set has unique differences

5.2\; Deleting a small set to avoid forbidden differences

5.3\; A dense Sidon block (Singer)

5.4\; Main theorem: a universal $1/\sqrt2$-density extension

6) ADVERSARIAL VERIFICATION

• Repeated summands. The Sidon definition allows $x_1=x_2$. In the range separation check, $2b\in B+B$ is still $\ge 2(N+L+1)=2N+2L+2$, strictly larger than any $a+b\le 2N+2L$, so no hidden overlap.
• Cross-sums among themselves. The only way $a_1+b_1=a_2+b_2$ could fail to force $a_1=a_2$ is if $b_1-b_2$ equals a nonzero difference of $A$. This is exactly what Lemma Lemma (Forbidden-difference pruning) eliminates.
• Cardinality of $F_A$. We used only $F_A\subset\{1,\dots,N-1\}$, hence $|F_A|\le N-1$ (no bound on $|A|$ is needed).
• Quantifiers/dependence. The construction chooses $M$ and $B$ depending on $(N,A,\varepsilon)$, as allowed.
• Extremal small-$N$ cases. When $N=1$, $F_A=\varnothing$ and the construction works verbatim. If $A=\varnothing$, then $F_A=\varnothing$ and we simply place a dense Sidon block $B$ in the top interval.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED). The original problem asks for extension to size $(1-\varepsilon)\sqrt M$. In Round 2 we proved the following unconditional quantitative extension theorem: for every Sidon $A\subset [N]$ and every $\varepsilon>0$ there exist $M$ and $B\subset\{N+1,\dots,M\}$ such that $A\cup B$ is Sidon and \[|A\cup B|\ge \left(\tfrac1{\sqrt2}-\varepsilon\right)\sqrt M.\] The structural reason for the $1/\sqrt2$ loss is that we enforced $A+B$ and $B+B$ to lie in disjoint ranges; improving the constant beyond $1/\sqrt2$ requires handling those mixed collisions rather than separating them.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 55%

9) REFERENCES

• J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 $1938$, 377--385.