Erdős Problem #39

Erdős Problem #39 (Round 4)

1) ROUND-4 OBJECTIVE

Path (C) --- obstruction/correction.

While adversarially checking the Round 3 construction, I found a concrete flaw in the mixed-radix/discrete-log definition: for $p\in P_k$, the digit $x_j(p)$ was defined by \[ g_j^{x_j(p)}\equiv p \pmod{q_j}\qquad (1\le j\le k), \] but this congruence has no solution when $p=q_j$, because then the right-hand side is $0$ mod $q_j$ while the left-hand side lies in $\mathbb F_{q_j}^{\times}$. Thus the Round 2/3 construction was not literally well-defined on the full prime index set as stated.

The most promising Round 4 direction is therefore:

1. identify the exact exceptional indices where the definition fails;
2. prove that this obstruction is only finite;
3. give the minimal corrected statement and show that the Round 3 two-threshold theorem survives unchanged after this repair;
4. isolate the exact point where the current bad-prime counting mechanism becomes critical.

So the goal of this round is not to solve the original Erdős problem outright, but to repair a genuine logical gap and convert the Round 3 progress into a fully rigorous corrected theorem.

2) Round-3 FOUNDATION USED

I use the following specific Round 3 ingredients, but I do not re-prove them unless they need modification after the correction:

• The mixed-radix/discrete-log framework with bases $b_j=4q_j$, prime blocks \[ P_k=\{p\text{ prime}: 2^{c(k-1)^2-3}<p\le 2^{ck^2-3}\}, \] and integers $a_p$ built from digits $x_j(p)$.
• The exact repeated-sum window from Round 3: if a repeated sum occurs then \[ (1-c)k_1^2<k_2^2<\frac{c}{1-c}k_1^2. \]
• The Round 3 "no deletion" theorem for $0<c\le c_0:=\frac{3-\sqrt5}{2}$, conditional on the digit construction being well-defined.
• The Round 3 bad-prime exponent estimate \[ |B_{k}(c)|\le 2^{\gamma(c)k^2+o(k^2)}, \qquad \gamma(c):=\frac{3c-1}{1-c}, \] again conditional on the digit construction being well-defined.
• The Round 2 endpoint argument at $c=\sqrt2-1$, which sharpened the critical exponent comparison by a constant-level estimate.

3) NEW INSIGHT / TOOL (ROUND-4)

There are three genuinely new ingredients in this round.

• Finite-exception repair lemma. The obstruction $p=q_j$ can occur only in finitely many initial blocks. This gives a minimal corrected statement: remove a finite exceptional set $E(c)$ of problematic primes.
• Transfer principle. After removing $E(c)$, every Round 3 argument applies verbatim to the corrected construction, and the counting function remains $x^{c+o(1)}$ because only finitely many indices are lost.
• Sharp barrier theorem for the present counting method. The exponent \[ \gamma(c)=\frac{3c-1}{1-c} \] is the exact exponent produced by the Round 3 union-bound/divisor-counting argument. Hence that route is power-saving if and only if $c<\sqrt2-1$, critical at $c=\sqrt2-1$, and non-power-saving for $c>\sqrt2-1$.

4) ATTACK PLAN (ROUND-4)

The exact gaps left after Round 3 are:

• the construction was not literally defined for indices $p=q_j$ with $j\le k(p)$;
• therefore the Round 3 theorem, as written, needed a correction;
• the obstruction at $c=\sqrt2-1$ was described, but not isolated as a sharp theorem about the present counting method.

I will therefore prove the following claims:

1. The set of problematic primes \[ E(c):=\{p\text{ prime}: p\in P_k\text{ for some }k\text{ and }p=q_j\text{ for some }1\le j\le k\} \] is finite.
2. After replacing the index set $\mathbb P$ by $\mathbb P\setminus E(c)$, the whole Round 3 theory becomes rigorous with no loss in the exponent.
3. The present bad-prime counting route proves $|B_k(c)|=o(|P_k|)$ exactly for $c<\sqrt2-1$ and cannot yield that conclusion by exponent comparison alone when $c>\sqrt2-1$.

5) WORK (ROUND-4)

5.1. The concrete flaw

For each prime $p$, let $k(p)$ be the unique block index with $p\in P_{k(p)}$. In Rounds 2--3, for every $p\in P_k$ and every $1\le j\le k$, the $j$-th digit of $a_p$ was defined by \[ g_j^{x_j(p)}\equiv p \pmod{q_j}, \qquad q_j< x_j(p)<2q_j, \] where $g_j$ is a primitive root mod $q_j$.

This requires $p\not\equiv 0\pmod{q_j}$, i.e. $p\neq q_j$. So the original definition is illegal whenever $p=q_j$ for some $1\le j\le k(p)$. This is not a cosmetic issue: in that case $p$ has no discrete logarithm in $\mathbb F_{q_j}^{\times}$.

Thus the construction from Round 2/3 was not fully well-defined as written.

5.2. The obstruction is finite

Lemma 5.1 (finite-exception lemma).

Fix $0<c<1/2$. If a prime $p$ lies in $P_k$ and also equals $q_j$ for some $1\le j\le k$, then \[ c(k-1)^2<2k+4. \] Consequently the exceptional set \[ E(c):=\{p\text{ prime}: p\in P_k,\ p=q_j\text{ for some }1\le j\le k\} \] is finite.

Proof.

Assume $p\in P_k$ and $p=q_j$ with $1\le j\le k$. Since $p\in P_k$, \[ 2^{c(k-1)^2-3}<p. \] Since $p=q_j$ and $j\le k$, the defining choice of the $q_j$ gives \[ p=q_j\le 2^{2j+1}\le 2^{2k+1}. \] Therefore \[ 2^{c(k-1)^2-3}<2^{2k+1}, \] which is equivalent to \[ c(k-1)^2<2k+4. \] The left-hand side is quadratic in $k$ and the right-hand side is linear, so this can hold only for finitely many $k$. Hence $E(c)$ is finite. $\square$

A convenient explicit threshold is any integer $K(c)$ satisfying \[ c(K(c)-1)^2>2K(c)+4. \] Then Lemma 5.1 implies that for every $k\ge K(c)$ and every $p\in P_k$, one has $p\neq q_j$ for all $1\le j\le k$.

5.3. Minimal corrected statement

Definition 5.2 (corrected prime blocks).

For each $k\ge 2$, define \[ P_k^{\circ}:=P_k\setminus \{q_j:1\le j\le k\}. \] Equivalently, \[ \bigcup_{k\ge2}P_k^{\circ}=\mathbb P\setminus E(c). \] For $p\in P_k^{\circ}$, define the digits $x_j(p)$ for $1\le j\le k$ exactly as in Rounds 2--3: \[ g_j^{x_j(p)}\equiv p\pmod{q_j}, \qquad q_j< x_j(p)<2q_j, \] and set $x_j(p)=0$ for $j>k$. Then define $a_p$ and the corrected sequence \[ A_{q,c}^{\circ}:=\{a_p: p\in \bigcup_{k\ge2}P_k^{\circ}\}. \]

Lemma 5.3 (eventual agreement with the original blocks).

For all $k\ge K(c)$, one has $P_k^{\circ}=P_k$. In particular, \[ |P_k^{\circ}|=|P_k| \qquad (k\ge K(c)). \]

Proof.

By the defining property of $K(c)$, Lemma 5.1 rules out every equality $p=q_j$ with $p\in P_k$ and $1\le j\le k$ once $k\ge K(c)$. Thus no prime is removed from $P_k$ for $k\ge K(c)$. $\square$

This is the minimal correction: only the finitely many illegal indices are removed. A simpler but equivalent variant is to discard all blocks $P_k$ with $k<K(c)$; this differs from the minimal correction by only finitely many indices and leaves all asymptotic statements unchanged.

5.4. Counting function after the repair

Proposition 5.4.

For every fixed $0<c<1/2$, the corrected sequence satisfies \[ A_{q,c}^{\circ}(x)=x^{c+o(1)}. \]

Proof.

Let \[ B_k:=(4q_1)\cdots (4q_k). \] Round 2 already showed that \[ 2^{k^2+2k}<B_k\le 2^{k^2+4k}, \] so if $B_k<x\le B_{k+1}$, then $k^2=\log_2 x+o(\log x)$.

For the lower bound, every prime $p\le 2^{ck^2-3}$ belongs to some block $P_{\ell}$ with $\ell\le k$. After the correction we lose only the finite exceptional set $E(c)$, so \[ A_{q,c}^{\circ}(x)\ge \pi(2^{ck^2-3})-|E(c)|. \] By the prime number theorem, \[ \pi(2^{ck^2-3})=2^{ck^2+o(k^2)}=x^{c+o(1)}, \] and subtracting the constant $|E(c)|$ does not change the asymptotic exponent.

For the upper bound, exactly the same block argument as in Round 2 gives \[ A_{q,c}^{\circ}(x)\le \pi(2^{c(k+2)^2-3})=x^{c+o(1)}. \] Hence \[ A_{q,c}^{\circ}(x)=x^{c+o(1)}. \] $\square$

5.5. Transfer of the Round-3 structure theorem

Lemma 5.5 (transfer principle).

After replacing each block $P_k$ by $P_k^{\circ}$, every Round 3 proof from the digit-definition stage onward applies verbatim to the corrected family. In particular:

1. the injectivity proof survives unchanged;
2. the exact repeated-sum window \[ (1-c)k_1^2<k_2^2<\frac{c}{1-c}k_1^2 \] survives unchanged;
3. the Round 3 bad-prime estimate \[ |B_k^{\circ}(c)|\le 2^{\gamma(c)k^2+o(k^2)}, \qquad \gamma(c)=\frac{3c-1}{1-c}, \] survives unchanged;
4. the Round 2 endpoint estimate at $c=\sqrt2-1$ survives unchanged.

Proof.

The only place where the original proof could fail was the attempted use of a discrete logarithm when $p=q_j$. By Definition 5.2 that case has been removed. All subsequent arguments in Rounds 2--3 are purely algebraic manipulations involving:

• carry-free addition in the mixed-radix digits;
• the congruences $g_j^{x_j(p)}\equiv p\pmod{q_j}$ for indexed primes;
• size comparisons using the block bounds $p\in P_k$ and the growth conditions on the $q_j$.

Those ingredients are now valid for every indexed prime in the corrected construction. Nothing else in the proofs depends on the discarded set $E(c)$. Therefore all those arguments transfer without change. $\square$

5.6. The corrected two-threshold theorem

Let \[ c_0:=\frac{3-\sqrt5}{2}, \qquad c_1:=\sqrt2-1. \]

Theorem 5.6 (corrected explicit family for the full Round-3 range).

For the corrected construction, the following hold.

1. If $0<c\le c_0$, then $A_{q,c}^{\circ}$ is a Sidon sequence and \[ A_{q,c}^{\circ}(x)=x^{c+o(1)}. \]
2. If $c_0<c<c_1$, then after the same largest-element deletion as in Round 2 one obtains a corrected Sidon sequence $A_{q,c}^{\circ,*}$ with \[ A_{q,c}^{\circ,*}(x)=x^{c+o(1)}. \]
3. If $c=c_1=\sqrt2-1$, then the corrected deleted sequence $A_{q,c_1}^{\circ,*}$ satisfies \[ A_{q,c_1}^{\circ,*}(x)=x^{\sqrt2-1+o(1)}. \]

Proof.

For part $1$, combine Lemma 5.5 with the Round 3 exact collision window. If a repeated sum existed, it would force \[ (1-c)k_1^2<k_2^2<\frac{c}{1-c}k_1^2. \] When $c\le c_0$, the interval on the right is empty because \[ \frac{c}{1-c}\le 1-c \quad\Longleftrightarrow\quad c\le \frac{3-\sqrt5}{2}. \] So no repeated sum exists, and $A_{q,c}^{\circ}$ is Sidon. The counting function is Proposition 5.4.

For part $2$, define the bad-prime sets $B_k^{\circ}(c)$ exactly as in Round 2 but inside the corrected family. By Lemma 5.5, the same largest-element deletion destroys all repeated sums, so the deleted corrected family is Sidon. Round 3 already identified the bad-prime exponent \[ |B_k^{\circ}(c)|\le 2^{\gamma(c)k^2+o(k^2)}, \qquad \gamma(c)=\frac{3c-1}{1-c}. \] If $c<c_1=\sqrt2-1$, then \[ \gamma(c)-c=\frac{c^2+2c-1}{1-c}<0. \] Hence $|B_k^{\circ}(c)|=o(2^{ck^2})$. Since Proposition 5.4 gives $|P_k^{\circ}|=2^{ck^2+o(k^2)}$, deleting the bad primes does not change the exponent, and \[ A_{q,c}^{\circ,*}(x)=x^{c+o(1)}. \]

For part $3$, when $c=c_1$, the exponent comparison becomes critical because $\gamma(c_1)=c_1$. Here one uses the sharper Round 2 constant-level estimate (transferred by Lemma 5.5), which shows that only a strict proportion of each block is removed. Therefore the deleted corrected family still has counting function \[ x^{\sqrt2-1+o(1)}. \] $\square$

5.7. The exact barrier inside the present method

Proposition 5.7 (sharp obstruction for the current deletion-counting route).

Inside the corrected mixed-radix/discrete-log framework, the Round 3 union-bound/divisor-counting method yields \[ |B_k^{\circ}(c)|\le 2^{\gamma(c)k^2+o(k^2)}, \qquad \gamma(c):=\frac{3c-1}{1-c}. \] Since \[ |P_k^{\circ}|=2^{ck^2+o(k^2)}, \] this method proves \[ |B_k^{\circ}(c)|=o(|P_k^{\circ}|) \] if and only if $c<\sqrt2-1$. At $c=\sqrt2-1$ the exponent comparison is critical, and for $c>\sqrt2-1$ the exponent comparison alone cannot yield $o(|P_k^{\circ}|)$.

Proof.

The upper bound \[ |B_k^{\circ}(c)|\le 2^{\gamma(c)k^2+o(k^2)} \] is exactly the Round 3 exponent calculation transferred by Lemma 5.5. Now \[ \gamma(c)-c = \frac{3c-1}{1-c}-c = \frac{c^2+2c-1}{1-c}. \] Because $1-c>0$, the sign of $\gamma(c)-c$ is the sign of $c^2+2c-1$. Its positive root is $c=\sqrt2-1$. Therefore:

• if $c<\sqrt2-1$, then $\gamma(c)<c$, so the bad-prime bound is power-saving and gives \[ |B_k^{\circ}(c)|=o(|P_k^{\circ}|); \]
• if $c=\sqrt2-1$, then $\gamma(c)=c$, so exponent comparison alone is inconclusive;
• if $c>\sqrt2-1$, then $\gamma(c)>c$, so this exponent comparison route by itself cannot prove that the bad set is negligible.

This is the exact obstruction claimed. $\square$

Interpretation.

To improve the explicit exponent beyond $\sqrt2-1$ inside this framework, one must introduce a new ingredient beyond the present union-bound/divisor-counting step. In other words, the barrier is not in the digit construction itself, but in the present way of estimating how many primes must be deleted.

6) ADVERSARIAL VERIFICATION

I tried to break the new work in the following ways.

• Could the exceptional set be infinite? No. Lemma 5.1 reduces the bad event $p=q_j$ with $j\le k(p)$ to the inequality \[ c(k-1)^2<2k+4, \] which can hold for only finitely many $k$.

• Did the correction change the exponent? No. The repair removes only the finite set $E(c)$, so Proposition 5.4 differs from the Round 2 growth proof only by subtracting a constant in the lower bound.

• Did I overstate the transfer principle? No. I checked where the old proof could fail: only at the discrete-log step. Once the illegal indices are removed, every later algebraic step in Round 2/3 is legitimate.

• Could the finite repair itself create a new Sidon obstruction? Deleting indices cannot create repeated sums, so all positive Sidon results remain valid after the correction.

• Could the repaired undeleted family actually stay Sidon for some $c>c_0$? Possibly; I did not settle that here. The correction removes only finitely many primes, so the most likely answer is "no", but I have not proved a persistence-of-collisions theorem after the repair. I therefore make no claim beyond the explicit range already justified by Theorem 5.6.

• Does Proposition 5.7 say the construction fails for $c>\sqrt2-1$? No. It says only that the current counting method is not strong enough there. A different argument could still conceivably control the bad primes beyond the critical exponent.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 4 found and repaired a genuine flaw in the Round 2/3 mixed-radix construction: the digits were not defined when $p=q_j$ with $j\le k(p)$. I proved that this obstruction is only finite, gave the minimal corrected statement, and showed that after the correction the full Round 3 explicit range survives: \[ 0<c\le \sqrt2-1 \quad\Longrightarrow\quad \text{there is an explicit corrected Sidon construction with }A(x)=x^{c+o(1)}. \] I also isolated a sharp obstruction: the present bad-prime counting route is power-saving exactly for $c<\sqrt2-1$, critical at $c=\sqrt2-1$, and therefore cannot by exponent comparison alone push the explicit construction past the Ruzsa--Cilleruelo exponent.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 83%

9) REFERENCES

References

• [Ruzsa1998] I. Z. Ruzsa, An infinite Sidon sequence, J. Number Theory 68 $1998$, no. 1, 63--71.
• [Cilleruelo2014] J. Cilleruelo, Infinite Sidon sequences, Adv. Math. 255 $2014$, 474--486.
• [ErdosProblems39] T. F. Bloom, Erdős Problem #39, problem page checked on 2026-03-07.

Erdős Problem #39: independent continuation

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

1) OBJECTIVE AND SOURCE AUDIT

The target is one infinite Sidon set with $A(x)\gg_\varepsilon x^{1/2-\varepsilon}$ for every $\varepsilon>0$. The source treats dense infinite Sidon sequences through a mixed-radix construction. Removing illegal discrete logarithms repairs a definition, but does not itself re-prove the unavailable earlier-round collision estimates. Also an upper exponent $\gamma(c)>c$ shows only that this estimate is insufficient, not that the construction actually fails.

2) FINITE PREFIXES DO NOT OBSTRUCT A GROWTH EXPONENT

Here is an independent extension statement. Let $F\subseteq[1,K]$ be any finite Sidon set, and let $A\subseteq\mathbb N$ be any infinite Sidon set. Put \[ C=2K+1,\qquad M=6K+3,\qquad B=F\cup\{Ma+C:a\in A\}. \] Then $B$ is Sidon. Modulo $M$, sums from two elements of $F$ lie in $[2,2K]$; mixed sums lie in $[2K+2,3K+1]$; sums from two elements of the new tail have residue $4K+2$. These residue ranges are disjoint and all lie below $M$, so collisions cannot mix the three types. Within $F$ use its Sidon property. Within the tail, divide an equality by $M$ and use the Sidon property of $A$. Two mixed sums satisfy \[ f_1-f_2=M(a_2-a_1), \] and $|f_1-f_2|<M$ forces both differences to vanish. This also handles repeated summands in the usual Sidon convention. If $A(x)=x^{c+o(1)}$, then \[ B(x)=|F|+A((x-C)/M)=x^{c+o(1)}. \] Thus every available exponent can be realized while preserving any prescribed finite Sidon prefix.

3) CONSEQUENCE FOR THE SUPPLIED APPROACH

The extension theorem separates finite repairs from the real asymptotic difficulty: finitely many exceptional indices, or a prescribed initial segment, cannot prevent an exponent already achieved by some infinite Sidon sequence. What remains difficult is controlling infinitely many potential collisions while increasing that exponent. This lemma does not supply such control and does not approach exponent $1/2$ by itself.

7) FINAL

UNRESOLVED. A fully proved finite-prefix extension principle is obtained, without claiming a new best density or independent validation of the source's endpoint estimates. Problem record: https://www.erdosproblems.com/39.

8) COMPLETION ESTIMATE

COMPLETION: 10% 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 #39 (Round 2)

1) ROUND-2 OBJECTIVE

Path (A) --- proof/construction track.

Round 1 ended UNRESOLVED with only the elementary greedy lower bound $|A\cap[1,N]|\gg N^{1/3}$ (Round 1, Lemma 39.3) and the crude interval upper bound $|A\cap[1,N]|<\sqrt{2N}+1$ (Round 1, Lemma 39.2).

In Round 2 I push the constructive lower bound substantially past exponent $1/3$ by giving a fully explicit infinite Sidon sequence with counting function \[ A(x)=x^{\sqrt2-1+o(1)}, \] following and re-verifying the discrete-logarithm + deletion construction of Cilleruelo. This improves the Round 1 lower bound exponent from $1/3\approx0.333$ to $\sqrt2-1\approx0.414$.

This does not settle Erdős's conjecture (which asks for $A(x)\gg_\varepsilon x^{1/2-\varepsilon}$ for every $\varepsilon>0$). The conjecture remains open in the current literature listings(For instance, the Erdős Problems project lists the conjectural density question among the open "Sidon sets" problems (last edited December 28, 2025).). [ErdosProblemsPrize,Cilleruelo2013]

2) ROUND-1 FOUNDATION USED

I rely on the following Round 1 items as already established:

• The formal restatement/definition of an infinite Sidon set and counting function $A(x)=|A\cap[1,x]|$.
• Round 1, Lemma 39.3: the greedy algorithm gives an explicit infinite Sidon sequence with $A(x)\gg x^{1/3}$.
• Round 1, Lemma 39.2: $|A\cap[1,N]|\ll \sqrt N$ for any Sidon $A\subseteq[1,N]$ (upper bound context).

No Round 1 proof is repeated.

3) NEW INSIGHT / TOOL (ROUND-2)

• Mixed-radix encoding with carry-free addition: represent integers in a base $b_1,b_2,\dots$ where each digit is $<b_j/2$, so that addition of two encoded numbers is digitwise (no carries).
• Discrete logarithm digit selection: choose digits $x_j(p)$ so that $g_j^{x_j(p)}\equiv p\pmod{q_j}$ for a primitive root $g_j$ mod a prime $q_j$.
• Deletion-by-largest-element: characterize all possible repeated sums, then remove from the sequence the largest term in each potential collision. If the removed set is thin enough, the counting function is essentially unchanged.

4) ATTACK PLAN (ROUND-2)

Gap after Round 1: no explicit construction beating exponent $1/3$.

Claims to prove now:

1. Construct an explicit infinite sequence $A_{q,c}$ (indexed by primes) with $A_{q,c}(x)=x^{c+o(1)}$ for any fixed $0<c<1/2$.
2. Analyze all repeated sums in $A_{q,c}$ via digitwise equality (carry-free) and deduce strong congruence constraints on the corresponding primes.
3. Show:
   • for $c_0:=\frac{3-\sqrt5}{2}$, the constraints are impossible, so $A_{q,c_0}$ is already Sidon;
   • for $c:=\sqrt2-1$, remove an explicit thin subsequence of primes to destroy all repeated sums, and prove the surviving sequence is Sidon with counting function $x^{c+o(1)}$.

5) WORK (ROUND-2)

5.1. Mixed radix and carry-free addition

Fix integers $b_j\ge 2$. Every $n\in\mathbb N$ has a unique expansion \[ n = x_1 + x_2 b_1 + x_3 b_1 b_2 + \cdots + x_k b_1\cdots b_{k-1} \] with digits $0\le x_j<b_j$ and $x_k\ne 0$. (Proof: repeated Euclidean division; uniqueness by induction.) We write this as the digit string $n=x_k\cdots x_1$.

5.2. Choice of primes and the discrete-log digit map

Choose a sequence of primes $(q_j)_{j\ge1}$ such that \begin{equation} \label{wsref-0-65-71-3a-71-6a-2d-67-72-6f-77-74-68} 2^{2j-1}<q_j\le 2^{2j+1}\qquad(j\ge1). \end{equation} Existence is easy, e.g. by Bertrand's postulate applied to $2^{2j-1}$. Set \[ b_j := 4q_j. \] For each $j$, fix a primitive root $g_j$ modulo $q_j$ (exists since $\mathbb F_{q_j}^\times$ is cyclic).

Fix a parameter $c$ with $0<c<\tfrac12$. Partition the prime numbers into blocks \begin{equation} \label{wsref-0-65-71-3a-50-6b-64-65-66} \mathcal P = \bigcup_{k\ge2} P_k,\qquad P_k := \left\{p\text{ prime}: 2^{c(k-1)^2-3}<p\le 2^{ck^2-3}\right\}. \end{equation}

5.3. Injectivity and the counting function of $A_{q,c}$

5.4. Structure of repeated sums in $A_{q,c}$

The key point is that digitwise addition is carry-free: by Lemma Lemma (Well-defined digits), each digit satisfies $x_j(p)\in\{0\}\cup[q_j+1,2q_j-1]$. So for any two primes $p,p'$, \[ 0\le x_j(p)+x_j(p')\le (2q_j-1)+(2q_j-1)=4q_j-2<b_j. \] Thus Lemma Lemma (Carry-free digitwise sums) applies.

5.5. An explicit Sidon sequence with exponent $\tfrac{3-\sqrt5}{2}$

Proposition Proposition (Congruence constraints from a repeated sum)(iv) is already enough to get a purely explicit Sidon sequence beating $1/3$ without deletions.

5.6. Deletion to reach exponent $c=\sqrt2-1$

Now take \[ c:=\sqrt2-1\approx0.414213. \] The set $A_{q,c}$ may have repeated sums, but Proposition Proposition (Congruence constraints from a repeated sum) shows they are highly structured. We now delete the "largest" element from every potential collision.

It remains to show that the deletion does not destroy the density exponent.

5.7. Bounding the number of bad primes

Fix $k_1\ge2$. Let $p_1\in B_{k_1}$ and choose a witness collision as in (eq:bad). By Proposition Proposition (Congruence constraints from a repeated sum) there is some $k_2<k_1$ with \begin{equation} \label{wsref-0-65-71-3a-6b-32-72-61-6e-67-65} k_2^2<\frac{c}{1-c}k_1^2, \end{equation} and writing $Q_1=q_1\cdots q_{k_2}$, $Q_2=q_{k_2+1}\cdots q_{k_1}$ we have \begin{equation} \label{wsref-0-65-71-3a-63-6f-6e-67-2d-51-31-51-32} p_1p_2\equiv p_1'p_2'\pmod{Q_1},\qquad p_1\equiv p_1'\pmod{Q_2}. \end{equation} Thus there exist nonzero integers $s_1,s_2$ such that \begin{equation} \label{wsref-0-65-71-3a-73-31-73-32} p_1p_2-p_1'p_2'=s_1Q_1,\qquad p_1'-p_1=s_2Q_2. \end{equation} From $p\in P_k\Rightarrow p\le 2^{ck^2-3}$ we get \begin{equation} \label{wsref-0-65-71-3a-73-31-62-6f-75-6e-64} |s_1|\le \frac{|p_1p_2-p_1'p_2'|}{Q_1}\le \frac{p_1p_2+p_1'p_2'}{Q_1}\le \frac{2\cdot 2^{c(k_1^2+k_2^2)-6}}{Q_1}=\frac{2^{c(k_1^2+k_2^2)-5}}{Q_1}, \end{equation} and similarly \begin{equation} \label{wsref-0-65-71-3a-73-32-62-6f-75-6e-64} |s_2|\le \frac{|p_1'-p_1|}{Q_2}\le \frac{2^{ck_1^2-3}}{Q_2}. \end{equation} Now rewrite \begin{equation} \label{wsref-0-65-71-3a-64-69-76-69-64-65-73} p_1(p_2-p_2')=(p_1p_2-p_1'p_2')+(p_1'-p_1)p_2'=s_1Q_1+s_2p_2'Q_2. \end{equation} So $p_1$ divides the integer \begin{equation} \label{wsref-0-65-71-3a-73-64-65-66} s:=s_1Q_1+s_2p_2'Q_2. \end{equation} Then every $p_1\in B_{k_1}$ divides some nonzero $s\in S_{k_2,k_1}$ for some $k_2$ satisfying (eq:k2range).

Lemma lem:oneprime implies the combinatorial bound \begin{equation} \label{wsref-0-65-71-3a-42-6b-2d-73-75-6d-53-6b} |B_{k_1}|\le \sum_{k_2<\sqrt{\frac{c}{1-c}}\,k_1} |S_{k_2,k_1}|. \end{equation} We now estimate $|S_{k_2,k_1}|$.

To convert this into a bound on $|B_{k_1}|$, we use the crude estimates \begin{equation} \label{wsref-0-65-71-3a-51-31-32-2d-6c-6f-77-65-72} Q_1Q_2=q_1\cdots q_{k_1}>2^{k_1^2} \end{equation} (from (eq:qj-growth)) and the prime number theorem in the weak form $|P_{k}|\le \pi(2^{ck^2})=2^{ck^2+o(k^2)}$. For the boundary exponent $c=\sqrt2-1$ we keep one more term (a $k^{-2}$ factor) to compare against $|P_{k_1}|$.

5.8. Final explicit lower bound exponent $\sqrt2-1$

5.9. What this achieves toward Erdős's conjecture

The original conjecture asks for $A(x)\gg_\varepsilon x^{1/2-\varepsilon}$ for all $\varepsilon>0$. Theorem thm:main gives exponent $\sqrt2-1$. Thus it implies the conjectured bound only for those $\varepsilon$ satisfying \[ \frac12-\varepsilon \le \sqrt2-1\quad\Longleftrightarrow\quad \varepsilon\ge \frac32-\sqrt2\approx 0.085786. \] The remaining gap is to improve the exponent from $\sqrt2-1$ up to $1/2-o(1)$.

6) ADVERSARIAL VERIFICATION

I tried to break the new argument in the following ways:

• Carry issues: digits satisfy $x_j(p)\le 2q_j-1$ and bases are $b_j=4q_j$, so $x_j(p)+x_j(p')<4q_j=b_j$. Hence Lemma Lemma (Carry-free digitwise sums) applies globally.
• Uniqueness of digit choice: the interval $[q_j+1,2q_j-1]$ has length exactly $q_j-1$, matching the period of discrete logs in $\mathbb F_{q_j}^\times$.
• Injectivity: requires $Q=q_1\cdots q_k$ to exceed possible differences $|p-p'|$ inside a block. This holds because $\log_2 Q\ge k^2$ whereas $\log_2|p-p'|\le ck^2+O(1)$ and $c<1$.
• Repeated-sum classification: the key step is that the thresholds $q_j+1$ and $2q_j+2$ distinguish whether 0, 1, or 2 summands have nonzero $j$th digit. This uses the digit range $\{0\}\cup[q_j+1,2q_j-1]$.
• Deletion correctness: any repeated sum has a largest element; removing all primes that can be the largest element of a collision eliminates all collisions.
• Density after deletion: the borderline case $c=\sqrt2-1$ is exactly where the exponent of the bad-set bound matches the block exponent. I checked that Proposition prop:badminority keeps a constant fraction of each block (in fact, the crude constants already make the ratio far below $1/2$).

No hidden quantifier issue was found: all "for large $k$" statements can be made uniform because the inequalities have polynomial/exponential separations in $k$.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 1 established only an explicit lower bound exponent $1/3$. Round 2 constructs an explicit infinite Sidon set $A$ with \[ |A\cap[1,x]|=x^{\sqrt2-1+o(1)}. \] This is a strict and substantial improvement, but still falls short of the conjectured $x^{1/2-o(1)}$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 65%

9) REFERENCES

References

• [Cilleruelo2013] J. Cilleruelo, Infinite Sidon sequences, arXiv:1209.0326v2 $2013$.
• [ErdosProblemsPrize] Erdős Problems Project, Sidon set density conjecture (Erdős prize page / Sidon tags), last edited December 28, 2025.
• [Ruzsa1998] I. Z. Ruzsa, An infinite Sidon sequence, J. Number Theory 68 $1998$, 63--71.