Erdős–Krückeberg conjecture

Research log for issue #61. The conjecture asks if there is a Sidon set A⊆ℕA\subseteq\mathbb N with

limsupN→∞|A∩[1,N]|N=1. \limsup_{N\to\infty} \frac{|A\cap[1,N]|}{\sqrt N}=1 .

In a Sidon set, equality of two pair sums forces the pairs to agree as multisets, allowing repeated summands.

Literature

  • Erdős's 1980 survey attributes the conjecture to Erdős and Krückeberg. The finite Erdős–Turán bound gives the universal upper limit 11. Krückeberg attains 1/21/\sqrt2.
  • Alexeev and Mixon, Conjecture 4 state the infinite problem separately from the finite perfect-difference-set extension conjecture. They disprove that finite extension conjecture and identify Hall's earlier counterexample.
  • O'Bryant and the November 2026 preprint of Wang and Yang distinguish the upper limit from lower-limit bounds and constructions with bounded multiplicities or higher-order sums. The Wang–Yang construction treats BhB_h sets for h≥3h\ge3.
  • Erdős Problem 329 and the Erdős Problems wiki record the exact infinite conjecture. The source search through November 2026 found no proof or disproof of it.
  • Eberhard and Manners identify the common finite-projective-plane structure of many dense modular Sidon sets. The Erdős Problem a Day report on #44 records explicit finite seeds that fail to embed in certain classical constructions and a deletion bound for Singer sets.

An obstruction to preserving prefixes in the classical constructions

Theorem. Let A⊆ℕA\subseteq\mathbb N. Suppose that there are cutoffs Ni→∞N_i\to\infty and cyclic Sidon sets Si⊆ℤ/MiℤS_i\subseteq\mathbb Z/M_i\mathbb Z with Mi→∞M_i\to\infty. Suppose membership in SiS_i is the vanishing of a linear recurrence of order at most dd, over a field KiK_i, with the same bound d≥2d\ge2 for all ii. More precisely, for all n≥0n\ge0, the recurrence term at nn vanishes exactly when nmodMi∈Sin\bmod M_i\in S_i. Assume that all but at most BB elements of A∩[1,Ni]A\cap[1,N_i] lie in SiS_i upon reduction modulo MiM_i, for a fixed BB.

Then |A∩[1,N]|=O(1+(logN)d−2)|A\cap[1,N]|=O(1+(\log N)^{d-2}). If the fields can be taken of characteristics tending to infinity, or of characteristic zero, then AA is finite.

To prove this, pad the recurrences to order dd if necessary. In the polynomial ring R=ℤ[c0,…,cd−1,u0,…,ud−1]R=\mathbb Z[c_0,\ldots,c_{d-1},u_0,\ldots,u_{d-1}], define the universal recurrence terms PnP_n by

Pj=uj(0≤j<d),Pn+d=∑j=0d−1cjPn+j. P_j=u_j\quad(0\le j<d),\qquad P_{n+d}=\sum_{j=0}^{d-1}c_jP_{n+j}.

Each individual sequence is an evaluation of these polynomials into KiK_i. The ring is countable. By successive subsequences and diagonal selection, arrange that each polynomial either vanishes eventually in the evaluations or is eventually nonzero. The eventually vanishing polynomials form a prime ideal 𝔭\mathfrak p. Indeed 11 never vanishes, and if neither factor vanishes eventually then their product is eventually nonzero in the fields. Take the universal recurrence in the fraction field KK of R/𝔭R/\mathfrak p, and let ZZ be its set of zero indices.

At most BB elements of AA can lie outside ZZ. Otherwise B+1B+1 fixed such elements would be excluded together for all large ii. The zero set ZZ is itself Sidon over the integers. Any nontrivial equality of two pair sums in ZZ would occur in the finite models eventually. For large ii, all the distinct indices appearing in the equality remain distinct modulo MiM_i, contradicting that SiS_i is Sidon. In particular, ZZ contains no infinite arithmetic progression.

In characteristic zero, the Skolem–Mahler–Lech theorem now makes ZZ finite. In characteristic pp, Derksen's Corollary 1.11 gives |Z∩[1,N]|=O(1+(logN)d−2)|Z\cap[1,N]|=O(1+(\log N)^{d-2}). If the input characteristics tend to infinity, each nonzero integer polynomial of degree zero is eventually nonzero, so KK has characteristic zero. This also holds if all input fields have characteristic zero.

Three families of order at most three

In each formula below an affine change of the exponents n↦un+vn\mapsto un+v, with uu invertible modulo the cyclic group order, is allowed.

  • In the Singer construction the set is given by Tr𝔽q3/𝔽q(cgn)=0\operatorname{Tr}_{\mathbb F_{q^3}/\mathbb F_q}(c g^n)=0, where the class of gg generates 𝔽q3×/𝔽q×\mathbb F_{q^3}^\times/\mathbb F_q^\times. Multiplication by gg acts linearly on a three-dimensional space. Applying the trace functional to its orbit gives the recurrence by Cayley–Hamilton.
  • In the Bose–Chowla construction a power of a primitive element of 𝔽q2\mathbb F_{q^2} belongs to an affine line. This is a condition L(cgn)−1=0L(c g^n)-1=0 for a linear functional LL and a primitive gg. The homogeneous term has order at most two and the constant increases the order by at most one.
  • In the Ruzsa construction in ℤ/(p(p−1))ℤ\mathbb Z/(p(p-1))\mathbb Z, the membership condition after an affine change is gnc−u‾n−v‾=0g^n c-\bar u n-\bar v=0 over 𝔽p\mathbb F_p, with g∈𝔽p×g\in\mathbb F_p^\times. The exponential satisfies a first-order recurrence and the affine polynomial has second forward difference zero. In this family unbounded moduli force p→∞p\to\infty.

Thus any fixed infinite set whose successive prefixes are contained in a mixture of these three families, up to a fixed number of omissions, grows at most logarithmically. The conclusion also applies to incidence along a cyclic projective linear orbit in dimension three whenever the modular incidence set is Sidon: a linear equation of the projective line gives the same recurrence after choosing a matrix representative of the generator.

The logarithmic scale is attained

Let A={2j:j≥0}A=\{2^j:j\ge0\}. This is Sidon because the positive difference 2j−2i2^j-2^i for j>ij>i determines ii by its 2-adic valuation and then determines jj. For every sufficiently large qq of characteristic 22, a Singer difference set contains a generator of its cyclic group of order M=q2+q+1M=q^2+q+1. To see this, every nontrivial character sum over the difference set has magnitude q\sqrt q, by the equation for its difference multiplicities. Detecting multiples of divisors of MM by characters, and then applying Möbius inversion, counts

(q+1)φ(M)M+O(τ(M)q) (q+1)\frac{\varphi(M)}{M}+O(\tau(M)\sqrt q)

generators in the set. This is positive for large qq. Take a representative g∈𝔽q3×g\in\mathbb F_{q^3}^\times of such a generator with trace zero. Then each g2jg^{2^j} has trace zero by Frobenius. Using gg as the projective generator puts every fixed prefix of AA into Singer sets of arbitrarily large modulus.

The prefix theorem concerns exact modular embeddings with a uniform bound on the number of omitted points. A general integer Sidon set can have collisions after reduction modulo a number close to the length of its containing interval. That is an additional gap between this obstruction and the full infinite conjecture.

A deletion bound for all three cyclic constructions

Theorem. Let D⊆[0,M−1]D\subseteq[0,M-1] be the standard integer representatives of any affine Singer, Bose–Chowla or Ruzsa Sidon set. Let AA be an integer Sidon set that contains some a∈[0,M−1]\Da\in[0,M-1]\setminus D. Then

|D\A|≥(1/8−o(1))|D|,M→∞, |D\setminus A|\ge (1/8-o(1))|D|, \qquad M\longrightarrow\infty,

uniformly in DD and aa. The earlier deletion bound for Singer sets gives the constant 1/161/16 in that family. Here the count comes from equidistribution of the two summands in a representation of aa as a sum minus a third element.

First count modular solutions x+y−z≡a(modM)x+y-z\equiv a\pmod M in DD. We will show that at least (1/2−o(1))|D|(1/2-o(1))|D| of the ordered solutions satisfy the same equality over the integers. Since a∉Da\notin D, fixing a value as the first summand determines at most one ordered difference y−zy-z in the modular Sidon set. The same holds for the second summand. Fixing zz determines at most two ordered pairs x,yx,y. Thus removing any one element destroys at most four ordered solutions. Every genuine integer solution must lose at least one of its three elements if we adjoin aa. The claimed lower bound follows.

Character sums for Singer sets

Write K=𝔽qK=\mathbb F_q, E=𝔽q3E=\mathbb F_{q^3}, and let UU be the trace-zero subspace of EE. Under the affine identification the indices of DD correspond to the classes of U\{0}U\setminus\{0\} in E×/K×E^\times/K^\times. Let δ\delta be a representative of the class for aa. It is outside UU, and a modular solution corresponds to classes X,Y,ZX,Y,Z with XY/Z=δXY/Z=\delta in the quotient. Equivalently, X,Y∈UX,Y\in U satisfy Tr(XY/δ)=0\operatorname{Tr}(XY/\delta)=0, with ZZ determined.

The bilinear form Tr(XY/δ)\operatorname{Tr}(XY/\delta) is nondegenerate on UU. Its radical would consist of the vectors in UU for which X/δX/\delta is in the trace annihilator of UU, namely KK. As δ∉U\delta\notin U, the radical is zero. Consequently each projective XX determines YY by an invertible projective linear map of ℙ1(K)\mathbb P^1(K). Choose representatives for the finite parameters of the projective line in the form

X(t)=a0+a1t,Y(t)=b0+b1t,t∈K, X(t)=a_0+a_1t,\qquad Y(t)=b_0+b_1t,\qquad t\in K,

where each pair of coefficients is linearly independent over KK. The parameter at infinity affects the counts by at most one.

Let χ\chi generate the characters of E×/K×E^\times/K^\times in the chosen exponent coordinate. For any fixed integer frequencies h,kh,k, the Fourier coefficient for the ordered summands is, up to a constant of modulus one, the sum of χh(X(t))χk(Y(t))\chi^{h}(X(t))\chi^{k}(Y(t)) over t∈Kt\in K. Here and below the affine changes of the indices only change the generator of the character group and the constant factor. Put ξ=−a0/a1\xi=-a_0/a_1 and υ=−b0/b1\upsilon=-b_0/b_1. Both have degree three over KK.

If their minimal polynomials are distinct, the character sum is a sum over monic degree-one polynomials for a Dirichlet character of K[T]K[T] modulo the product of those two cubics. This follows by identifying the quotient at each cubic with EE by evaluation at its root. For a nonzero fixed frequency pair and sufficiently large qq, at least one local character is nontrivial. Weil's bound gives O(q)O(\sqrt q) for this sum. In the function-field Dirichlet formulation, the sum is the coefficient of degree one in the LL-polynomial, and the degree of the modulus is bounded. A trivial local character can be removed from the modulus since none of the tested linear polynomials vanishes there.

If υ=ξqj\upsilon=\xi^{q^j} for j=1j=1 or 22, the two characters combine into a character at the same cubic with exponent h+qjkh+q^j k modulo M=q2+q+1M=q^2+q+1. This is nonzero modulo MM for a fixed nonzero pair and sufficiently large qq. For j=2j=2 use q2≡−q−1(modM)q^2\equiv-q-1\pmod M. The same square-root bound applies. In the remaining case υ=ξ\upsilon=\xi, the two field representatives are proportional by a fixed scalar. This scalar preserves UU, so it lies in K×K^\times by the trace annihilator property. The modular solutions then have x=yx=y. Their single coordinate is equidistributed, since the nontrivial character sums of a Singer difference set have magnitude q\sqrt q.

Character sums for Bose–Chowla sets

Now take E=𝔽q2E=\mathbb F_{q^2}, and identify DD with ϑ+K⊆E×\vartheta+K\subseteq E^\times for ϑ∉K\vartheta\notin K. Write L:E→KL:E\to K for the linear functional with L(1)=0L(1)=0 and L(ϑ)=1L(\vartheta)=1. Let δ∉ϑ+K\delta\notin\vartheta+K be the nonzero field element corresponding to aa. With X=ϑ+tX=\vartheta+t, the equations for Y=ϑ+sY=\vartheta+s become

L(Xϑ/δ)+sL(X/δ)=1. L(X\vartheta/\delta)+s L(X/\delta)=1.

For all but at most one tt, the coefficient of ss is nonzero, giving ss as a linear fractional function of tt. When the coefficient vanishes, X/δX/\delta lies in K×K^\times, so the equation would force X=δX=\delta, which is excluded. The same argument with X,YX,Y exchanged proves that the fractional function is nonconstant for large qq. In particular it has the form s=(A+Bt)/(C+Dt)s=(A+Bt)/(C+Dt) with BC−AD≠0BC-AD\ne0 in KK. Therefore

Y(t)=(ϑC+A)+(ϑD+B)tC+Dt. Y(t)=\frac{(\vartheta C+A)+(\vartheta D+B)t}{C+Dt}.

The numerator coefficients are independent over KK. The numerator and X(t)X(t) give irreducible quadratics in the function-field Dirichlet character argument, and a nonconstant denominator gives a linear factor. The multiplicative character now has order q2−1q^2-1 on E×E^\times and order q−1q-1 on K×K^\times.

If the two quadratic factors are distinct, a nonzero frequency gives a nontrivial character at at least one factor. If the roots are distinct conjugates, the exponent at their common quadratic is h+qkh+qk, which gives a nontrivial character for any fixed nonzero pair and large qq. If the roots are equal and C+DtC+Dt is nonconstant, the denominator factor is nontrivial when k≠0k\ne0 for large qq. When k=0k=0 the first frequency gives a nontrivial character. All three cases give a square-root bound. Removing the possible pole changes the bound by O(1)O(1).

Finally, if the quadratic roots are equal and the denominator constant, then Y(t)Y(t) is a fixed scalar multiple of X(t)X(t). Preservation of the affine line forces the scalar to be in K×K^\times by taking differences and then to be 11 by applying LL. These are diagonal solutions. The single summand coordinate is equidistributed by the same character bound for one irreducible quadratic.

Character sums for Ruzsa sets

Use the cyclic group model 𝔽p×𝔽p×\mathbb F_p\times\mathbb F_p^\times, with addition in the first coordinate and multiplication in the second. The set is the diagonal (x,x)(x,x) with x∈𝔽p×x\in\mathbb F_p^\times. If the image of aa is (b,c)(b,c), then b≠cb\ne c and c≠0c\ne0. The modular equation determines the second summand by

y(x)=c(x−b)x−c. y(x)=\frac{c(x-b)}{x-c}.

There are only O(1)O(1) excluded values where a denominator or one of the required nonzero coordinates vanishes. A generating character in the exponent coordinate splits into a nontrivial additive character ψ\psi and a generating multiplicative character χ\chi. The sum for each fixed nonzero frequency pair (h,k)(h,k), apart from a constant of modulus one, is

∑xψ(hx+ky(x))χ(xhy(x)k). \sum_x \psi(hx+k y(x))\chi(x^h y(x)^k).

For sufficiently large pp, the additive argument has a simple pole at x=cx=c if k≠0k\ne0, and a simple pole at infinity if k=0k=0 and h≠0h\ne0. This excludes the Artin–Schreier exceptional form, since the poles of Hp−HH^p-H have orders divisible by pp. Thus the mixed Weil character bound gives Oh,k(p)O_{h,k}(\sqrt p).

From modular to integer solutions

In the cases with the two-dimensional character bounds, the pairs (x/M,y/M)(x/M,y/M) are equidistributed in the unit square by the Fourier criterion. The number of modular solutions is |D|+O(1)|D|+O(1) by the parameterizations. A modular solution becomes an integer solution precisely when 0≤x/M+y/M−a/M<10\le x/M+y/M-a/M<1. For α=a/M∈[0,1)\alpha=a/M\in[0,1) the strip has area 1/2+α−α2≥1/21/2+\alpha-\alpha^2\ge1/2. In the diagonal cases, the corresponding interval for x/Mx/M has length 1/21/2. These estimates are uniform in the choice of α\alpha. Indeed any subsequence of choices has a further subsequence with α\alpha convergent, where the strip or interval boundaries have limiting measure zero. In every case at least (1/2−o(1))|D|(1/2-o(1))|D| ordered solutions are integer solutions, as claimed.

Consequence for an infinite Sidon set

For every infinite integer Sidon set A⊆ℕA\subseteq\mathbb N, the fraction of agreement with these classical sets satisfies

limsupM→∞supD|A∩D||D|≤78, \limsup_{M\to\infty}\ \sup_D\frac{|A\cap D|}{|D|} \le \frac78,

where the supremum is over these affine constructions at the available moduli. Indeed, agreement above 7/8+ϵ7/8+\epsilon along an unbounded sequence of moduli would force every element of A∩[1,M−1]A\cap[1,M-1] to be in DD for all sufficiently large members of the sequence. The recurrence theorem would then bound these prefixes by O(logM)O(\log M), contradicting the supposed agreement. This rules out obtaining the conjectured infinite density by modifications of size o(M)o(\sqrt M) of these three classical cyclic families. The infinite conjecture is open.

Translated blocks and the constant 1/21/\sqrt2

Let AA be an infinite Sidon set, and suppose it retains a fraction tending to one of each of a sequence of blocks Ti+DiT_i+D_i, where Ti≥0T_i\ge0, Di⊆[0,Mi−1]D_i\subseteq[0,M_i-1] is one of the three classical sets above, and Mi→∞M_i\to\infty. Then

liminfi→∞Ti/Mi≥1. \liminf_{i\to\infty} T_i/M_i\ge1.

Suppose instead that Ti/Mi≤1−εT_i/M_i\le1-\varepsilon along a subsequence for some fixed ε>0\varepsilon>0. For any fixed a∈Aa\in A set b=a−Tib=a-T_i. If bmodMi∉Dib\bmod M_i\notin D_i, we can apply the modular triple argument with that residue. To obtain true integer collisions with aa in the translated block, take the strip 0≤x/Mi+y/Mi−b/Mi<10\le x/M_i+y/M_i-b/M_i<1. For −1≤α=b/Mi≤0-1\le\alpha=b/M_i\le0, its area in the square is (1+α)2/2(1+\alpha)^2/2, and its length on the diagonal, in the summand coordinate, is (1+α)/2(1+\alpha)/2. Since aa is fixed, α≥−1+ε\alpha\ge-1+\varepsilon and α≤o(1)\alpha\le o(1). These areas or lengths are bounded below by a positive constant depending on ε\varepsilon. At least that fraction, up to o(1)o(1), of the modular triples turn into true collisions. The deletion bound contradicts retention of all but o(|Di|)o(|D_i|) elements of the block.

Consequently each fixed a∈Aa\in A is eventually present in the modular translate Ti+Di(modMi)T_i+D_i\pmod{M_i}. By passing to a subsequence, there are cutoffs tending to infinity for which all points of the corresponding prefixes are present. The recurrence theorem gives |A∩[1,N]|=O(logN)|A\cap[1,N]|=O(\log N). But the retained block gives (1−o(1))Mi(1-o(1))\sqrt{M_i} points below Ti+Mi≤2MiT_i+M_i\le2M_i on this subsequence, a contradiction.

In particular, if the prefixes up to Ti+Mi−1T_i+M_i-1 differ from those translated blocks in o(Mi)o(\sqrt{M_i}) points, their normalized sizes have upper limit at most 1/21/\sqrt2. This is sharp within the sparse modification scheme. The usual lower-bound construction of Krückeberg can be implemented by translating each new block by Ti=Mi+2LT_i=M_i+2L, with LL the previous largest element. Remove at most LL elements of the new modular set to destroy all its positive differences at most LL. Each such difference occurs at most once. Internal new differences are then above the internal old differences, and mixed differences exceed MiM_i. Two distinct mixed differences cannot agree because this would give an internal new difference at most LL. Taking MiM_i very large compared with L2L^2 gives a prefix with (1−o(1))Mi(1-o(1))\sqrt{M_i} points at Ti+Mi∼2MiT_i+M_i\sim2M_i. See also O'Bryant, Lemma 9 for the block construction.

The same argument gives a tradeoff with a fixed fraction of deletions. Along any sequence of blocks with Ti/Mi→θ∈[0,1)T_i/M_i\to \theta\in[0,1), an infinite Sidon set must satisfy

liminfi→∞|(Ti+Di)\A||Di|≥(1−θ)28. \liminf_{i\to\infty}\frac{|(T_i+D_i)\setminus A|}{|D_i|} \ge\frac{(1-\theta)^2}{8}.

If a subsequence had deletion fractions smaller by a fixed margin, the bounded-frequency calculation would force every fixed element of AA into the modular translates as before. The logarithmic growth bound again contradicts the retained block. Thus even if the number of deletions is unrestricted, prefixes built from a single such block with o(Mi)o(\sqrt{M_i}) additional points have normalized upper limit at most 7/87/8. For 0≤θ≤10\le\theta\le1 this follows by maximizing (1−(1−θ)2/8)/1+θ(1-(1-\theta)^2/8)/\sqrt{1+\theta}, which decreases on that interval. For θ≥1\theta\ge1 the whole block contributes at most 1/21/\sqrt2 after normalization.