betaFeedback

WorksMathematics

Small maximal integer Sidon sets by finite phase colorings

Abstract

Every sufficiently large integer interval {1,…,N}\{1,\ldots,N\} contains an inclusion-maximal Sidon set of size O(N1/3)O(N^{1/3}). A quadratic seed supplies exact integer differences, and a periodically labeled family of anchors covers each relevant local window. Finite-dimensional bounds for affine sign patterns give a fixed alphabet of translates and a common periodic word. Two separated alphabets give Sidon, sum-free tags for all primes. The seed blocks every point outside two intervals of length O(p2)O(p^2) and the multiples of pp, with p≍N1/3p\asymp N^{1/3}. A maximal completion adds only O(p)O(p) elements. The linked Lean verification covers the original upper-bound target.

Introduction

A set of integers AA is a Sidon set if a+b=c+da+b=c+d, with a,b,c,d∈Aa,b,c,d\in A, implies {a,b}={c,d}\{a,b\}=\{c,d\} as multisets. In particular, diagonal sums 2a2a are included in the definition. A Sidon subset of [1,N]∩Z[1,N]\cap\mathbb{Z} is maximal if adjoining any further point of that interval destroys the Sidon property. Write

s(N)=min⁡{∣A∣:A⊆[1,N]∩Z is a maximal Sidon set}.s(N)=\min\{|A|:A\subseteq[1,N]\cap\mathbb{Z}\text{ is a maximal Sidon set}\}.

Maximality is with respect to inclusion.

Erdős, Sárközy, and Sós studied this problem in their work on sumsets of Sidon sets [1]. Ruzsa [2] proved the existence of maximal Sidon sets of size O((Nlog⁡N)1/3)O((N\log N)^{1/3}). We establish the following upper bound by a construction whose uniformity statements are included in a Lean proof.

Theorem 1.1. There are absolute constants C>0C>0 and N0∈NN_0\in\mathbb{N} such that, for every integer N≥N0N\geq N_0, there is a maximal Sidon set A⊆[1,N]∩ZA\subseteq[1,N]\cap\mathbb{Z} satisfying ∣A∣≤CN1/3|A|\leq CN^{1/3}. Equivalently, s(N)=O(N1/3)s(N)=O(N^{1/3}).

The exponent is forced by a counting argument.

Proposition 1.2. Every maximal Sidon set A⊆[1,N]∩ZA\subseteq[1,N]\cap\mathbb{Z} satisfies ∣A∣≥(N/3)1/3|A|\geq(N/3)^{1/3}.

Proof. The case N=0N=0 is immediate. Otherwise put m=∣A∣≥1m=|A|\geq1. For every x∈[1,N]∖Ax\in[1,N]\setminus A, a nontrivial equality of pair sums in A∪{x}A\cup\{x\} must take one of the forms

x+a=b+cor2x=a+b,a,b,c∈A.x+a=b+c\qquad\text{or}\qquad2x=a+b,\qquad a,b,c\in A.

Indeed, equalities using xx once on each side cancel to a trivial equality. Consequently the interval is contained in the union of AA, A+A−AA+A-A, and the set of integral midpoints of pairs from AA. Thus N≤m+m3+m2≤3m3N\leq m+m^3+m^2\leq3m^3. □

Together, Theorem 1.1 and Proposition 1.2 give s(N)≍N1/3s(N)\asymp N^{1/3}. The companion certificate proves the upper bound.

Organization and notation. For an integer zz and a positive integer qq, let ⟨z⟩q∈{0,…,q−1}\langle z\rangle_q \in\{0,\ldots,q-1\} be its least nonnegative residue. For a real number uu, write {u}=u−⌊u⌋\{u\}=u-\lfloor u\rfloor. All intervals below are intersected with Z\mathbb{Z} when used as sets of marks.

We first work in [0,N)[0,N) and translate by 1 at the end. A quadratic seed CpC_p supplies controlled differences. A finite alphabet of translates covers all nonmultiples of pp in a long interior interval. Two versions of this alphabet produce tags that preserve Sidonicity. A periodic choice of labels then makes a family of anchors cover the interior of the host interval. Only two short boundary intervals and the multiples of pp remain available to a maximal completion.

Finite pattern selection

The construction uses finite families of patterns even though the arithmetic parameters range over infinitely many primes and targets. The following deliberately nonoptimal estimate agrees with the bound used in the certificate.

Lemma 2.1 (Affine sign patterns). Let f1,…,fqf_1,\ldots,f_q be affine real functions on Rd\mathbb{R}^d. The number of joint sign patterns, with each sign in {−,0,+}\{-,0,+\}, is at most

((d+2)(q+1)d+1)2.(1)((d+2)(q+1)^{d+1})^2. \tag*{(1)}

The same bound applies to any finite-valued label determined by these signs.

Proof. Homogenize the affine functions on Rd+1\mathbb{R}^{d+1}. The family of their positive supports has VC dimension at most d+1d+1. To see the dimension bound, suppose a collection of the corresponding linear functionals is shattered. A nonzero linear dependence among them is impossible. Choose a realizing vector on which precisely the functionals with positive coefficients are positive, changing the sign of the dependence first if necessary. Evaluating the dependence then gives a strictly positive sum.

The Sauer–Shelah bound [3, 4] gives at most

∑j=0d+1(qj)≤(d+2)(q+1)d+1\sum_{j=0}^{d+1}\binom{q}{j}\leq(d+2)(q+1)^{d+1}

positive supports. Apply the same estimate to negative supports. The pair consisting of the positive and negative supports also determines all zero signs. □

Lemma 2.2 (Fractional-part tests). Suppose a label is determined by tt comparisons

{fi(v)}<gi(v),1≤i≤t,\{f_i(v)\}<g_i(v),\qquad1\leq i\leq t,

where fi,gif_i,g_i are affine functions of v∈Rdv\in\mathbb{R}^d, and ∣fi(v)∣≤B|f_i(v)|\leq B on the parameter set under consideration, with BB a nonnegative integer. The number of labels is at most

((d+2)(2t(2B+1)+1)d+1)2.((d+2)(2t(2B+1)+1)^{d+1})^2.

No bound on the values of gig_i is required.

Proof. For each integer k∈[−B,B]k\in[-B,B], record the signs of fi−kf_i-k and fi−gi−kf_i-g_i-k. The first collection determines ⌊fi⌋\lfloor f_i\rfloor, including the case that fif_i is an integer. The second determines whether fi−⌊fi⌋<gif_i-\lfloor f_i\rfloor<g_i. There are 2t(2B+1)2t(2B+1) affine functions. Apply Lemma 2.1. □

Lemma 2.3 (A common hitting word). Fix b≥2b\geq2. For each mm, let Gm\mathcal{G}_m be a family of matrices

(G0,…,Gm−1),∅≠Gi⊆{1,…,b}.(G_0,\ldots,G_{m-1}),\qquad\varnothing\ne G_i\subseteq\{1,\ldots,b\}.

If ∣Gm∣≤AmB|\mathcal{G}_m|\leq A m^B for fixed constants A,BA,B, then for all sufficiently large mm there is a word w∈{1,…,b}mw\in\{1,\ldots,b\}^m that meets every matrix: for each G∈GmG\in\mathcal{G}_m, some ii satisfies wi∈Gw_i\in G. One may also require this property simultaneously for every cyclic rotation of $w.

Proof. Choose the letters independently and uniformly. A fixed matrix is missed with probability at most (1−1/b)m(1-1/b)^m. The union bound is less than 1 once AmB(1−1/b)m<1Am^B(1-1/b)^m<1. To include all rotations, use the bound AmB+1(1−1/b)mAm^{B+1}(1-1/b)^m, which also tends to zero. □

The quadratic seed and exact differences

Let pp be an odd prime and put

Qp=2p2,cp(t)=t+2p⟨t2⟩p,Cp={cp(t):0≤t<p},Dp=Cp−Cp.(2)Q_p=2p^2,\qquad c_p(t)=t+2p\langle t^2\rangle_p,\qquad C_p=\{c_p(t):0\le t<p\},\qquad D_p=C_p-C_p. \tag*{(2)}

Lemma 3.1. The set CpC_p is Sidon, has pp elements, and is contained in [0,Qp)[0,Q_p).

Proof. If cp(i)+cp(j)=cp(k)+cp(l)c_p(i)+c_p(j)=c_p(k)+c_p(l), reduction modulo 2p2p gives i+j=k+li+j=k+l, since both sums lie in [0,2p)[0,2p). Subtracting this equality and dividing by 2p2p gives equality of the sums of the quadratic residues. In Fp\mathbb{F}_p we therefore have i+j=k+li+j=k+l and i2+j2=k2+l2i^2+j^2=k^2+l^2. As pp is odd, these imply ij=klij=kl. The two pairs are roots of the same monic quadratic, so they agree as unordered pairs in Fp\mathbb{F}_p, and hence as integer pairs in [0,p)[0,p). Distinct parameters give distinct residues modulo pp, proving the cardinality statement. Finally, 0≤cp(t)≤(p−1)+2p(p−1)<2p20\le c_p(t)\le(p-1)+2p(p-1)<2p^2. □

Lemma 3.2 (Exact lift with two carries). Let 1≤d<p1\le d<p and 1≤H<p1\le H<p. Define

t=⟨(H+d2)(2d)−1⟩p,σ=1t<d,u=t−d+pσ,ε=1⟨t2⟩p<H.t=\langle(H+d^2)(2d)^{-1}\rangle_p,\qquad\sigma=1_{t<d},\qquad u=t-d+p\sigma,\qquad\varepsilon=1_{\langle t^2\rangle_p<H}.

Then 0≤u<p0\le u<p and

cp(t)−cp(u)=d−pσ+2pH−εQp.(3)c_p(t)-c_p(u)=d-p\sigma+2pH-\varepsilon Q_p. \tag*{(3)}

Proof. The definition of σ\sigma gives t−u=d−pσt-u=d-p\sigma and 0≤u<p0\le u<p. In Fp\mathbb{F}_p, t2−u2=2dt−d2=Ht^2-u^2=2dt-d^2=H. The difference of the two least residues lies strictly between −p-p and pp. It is therefore HH or H−pH-p. The latter alternative occurs exactly when ⟨t2⟩p<H\langle t^2\rangle_p<H. Substitution in (3.1) proves the identity. □

In particular, if τ∈{0,1}\tau\in\{0,1\} and k≥0k\ge0, then

d+pτ+2p(H+k)=cp(t)−cp(u)+p(2k+τ+σ)+εQp.(4)d+p\tau+2p(H+k)=c_p(t)-c_p(u)+p(2k+\tau+\sigma)+\varepsilon Q_p. \tag*{(4)}

Thus the six pairs (s,ε)∈{0,1,2}×{0,1}(s,\varepsilon)\in\{0,1,2\}\times\{0,1\} contain a suitable choice in every row. The identity is in Z\mathbb{Z}.

A fixed covering alphabet

Definition 4.1. A covering alphabet consists of a finite label set LL of size b≥2b\ge2, integers δℓ∈[0,M]\delta_\ell\in[0,M], and εℓ∈{0,1}\varepsilon_\ell\in\{0,1\}, such that

  1. equality of two δ\delta-pair sums determines the unordered pair of labels,

  2. for every odd prime pp,

Ip(M)∖pZ⊆Dp+{pδℓ+εℓQp:ℓ∈L},Ip(M)=[2p(M+2),2p(p−1)).(5)I_p(M)\setminus p\mathbb{Z}\subseteq D_p+\{p\delta_\ell+\varepsilon_\ell Q_p:\ell\in L\},\qquad I_p(M)=[2p(M+2),2p(p-1)). \tag*{(5)}

The interval in (4.1) may be empty.

Proposition 4.2 (Separated covering alphabets). Covering alphabets exist. Moreover, for every prescribed G≥0G\ge0, one can choose a covering alphabet for which

∣δi+δj−δk−δl∣>Gwhenever {i,j}≠{k,l} as multisets of labels.(6)|\delta_i+\delta_j-\delta_k-\delta_l|>G\qquad\text{whenever }\{i,j\}\ne\{k,l\}\text{ as multisets of labels}. \tag*{(6)}

Proof. Fix a positive integer λ\lambda with 2λ−4>G2\lambda-4>G. For 0≤i<m0\le i<m, set ai=i+2mi2a_i=i+2mi^2 and ki=λaik_i=\lambda a_i. The sequence (ai)(a_i) is Sidon. A pair-sum equality modulo 2m2m first determines the integer sum of the indices, and then the sum of their squares determines the unordered pair. Any selection of pairs (si,εi)∈{0,1,2}×{0,1}(s_i,\varepsilon_i)\in\{0,1,2\}\times\{0,1\} gives

δi=2ki+si,εi∈{0,1},M=6λm3+2.(7)\delta_i=2k_i+s_i,\qquad\varepsilon_i\in\{0,1\},\qquad M=6\lambda m^3+2. \tag*{(7)}

Here δi≤M\delta_i \le M and ki≤Mk_i \le M. For distinct unordered index pairs, the aa-pair sums differ by at least 1, while the difference of the two ss-pair sums has absolute value at most 4. This proves (6) for every selection.

Write a target in Ip(M)∖pZI_p(M) \setminus p\mathbb{Z} uniquely as y=d+pτ+2pYy=d+p\tau+2pY, where 1≤d<p1 \le d < p and τ∈{0,1}\tau\in\{0,1\}. The interval bounds give M+2≤Y<pM+2 \le Y < p. Hence Hi=Y−kiH_i=Y-k_i lies in [1,p)[1,p) for every row. Let r=(2d)−1∈Fpr=(2d)^{-1}\in\mathbb{F}_p and u=r(Y+d2)∈Fpu=r(Y+d^2)\in\mathbb{F}_p. The successful pair in (4) is determined by the tests

{⟨u⟩p/p−ki⟨r⟩p/p}<d/p,{⟨u2⟩p/p+ki⟨−2ur⟩p/p+ki2⟨r2⟩p/p}<Y/p−ki/p.(8)\begin{aligned} \{\langle u\rangle_p/p-k_i\langle r\rangle_p/p\} &< d/p,\\ \{\langle u^2\rangle_p/p+k_i\langle-2ur\rangle_p/p+k_i^2\langle r^2\rangle_p/p\} &< Y/p-k_i/p. \tag*{(8)} \end{aligned}

The first test determines σi\sigma_i, and the second determines εi\varepsilon_i. Put si=τ+σis_i=\tau+\sigma_i.

Treat the eight normalized quantities in (8) as independent parameters in [0,1]8[0,1]^8. This enlarges the pattern family. Since ki=Oλ(m3)k_i=O_\lambda(m^3), the arguments inside the fractional parts are bounded in absolute value by Oλ(m6)O_\lambda(m^6). There are 2m2m tests, so Lemma 2.2 gives Oλ(m126)O_\lambda(m^{126}) matrices of successful choices, including both values of τ\tau. Every row is a singleton. The formal bound is

200(16(3λ+1)2)18m126.200(16(3\lambda+1)^2)^{18}m^{126}.

By Lemma 2.3, for sufficiently large mm there is a fixed word of six choices that meets every matrix. Fix this word and use (7). For any pp and yy under consideration, a row at which the selected word agrees with its successful choice supplies (4). All choices and constants are fixed before pp and yy are given. □\square

Tags for every prime

We next arrange that arbitrary labels can be attached to a Sidon ruler without creating new equalities of pair sums. The modulus below need not be prime.

Proposition 5.1 (Two alphabets suffice). There exist two covering alphabets L1,L2L_1,L_2 and an integer K≥1K\ge1 with the following property. For every integer p≥0p\ge0, at least one alphabet admits a shift T∈{0,…,K−1}T\in\{0,\ldots,K-1\} such that the residues

vℓ=4p+T+δℓ+2pεℓ(modK)(9)v_\ell=4p+T+\delta_\ell+2p\varepsilon_\ell\pmod K \tag*{(9)}

determine unordered label pairs from their pair sums and are sum-free:

vi+vj=vk+vl⟹{i,j}={k,l},vi+vj≠vk.v_i+v_j=v_k+v_l\Longrightarrow\{i,j\}=\{k,l\},\qquad v_i+v_j\ne v_k.

Proof. Choose any covering alphabet L1L_1 with bound M1M_1. By Proposition 4.2, choose L2L_2 with separation greater than 4M14M_1 and bound M2M_2. Let b1,b2b_1,b_2 be their sizes and put

K=4(M1+M2)+b13+b23+1.(10)K=4(M_1+M_2)+b_1^3+b_2^3+1. \tag*{(10)}

For either alphabet, first consider the unshifted residues δℓ+2pεℓ\delta_\ell+2p\varepsilon_\ell. A collision of distinct unordered label pairs gives

K∣d+2pe,d=δi+δj−δk−δl,e=εi+εj−εk−εl.K\mid d+2pe,\qquad d=\delta_i+\delta_j-\delta_k-\delta_l,\qquad e=\varepsilon_i+\varepsilon_j-\varepsilon_k-\varepsilon_l.

We have d≠0d\ne0, ∣d∣≤2M|d|\le2M, and ∣e∣≤2|e|\le2. Since K>2MK>2M, such a collision must have e≠0e\ne0. Suppose both alphabets have a collision, with differences (d1,e1)(d_1,e_1) and (d2,e2)(d_2,e_2). Eliminating pp gives

K∣e2d1−e1d2,∣e2d1−e1d2∣≤4(M1+M2)<K.K\mid e_2d_1-e_1d_2,\qquad|e_2d_1-e_1d_2|\le4(M_1+M_2)<K.

Thus e2d1=e1d2e_2d_1=e_1d_2. As 1≤∣e1∣≤21\le|e_1|\le2, we get ∣d2∣≤∣e1d2∣=∣e2d1∣<4M1|d_2|\le|e_1d_2|=|e_2d_1|<4M_1, contrary to the separation of L2L_2. At least one unshifted alphabet therefore has unique label pair sums modulo KK.

For any bb residues uℓu_\ell modulo KK, translation by cc can violate sum-freeness only if c=uk−ui−ujc=u_k-u_i-u_j modulo KK for some triple of labels. There are at most b3<Kb^3<K forbidden shifts. Choose an allowed cc, and take TT to be the representative of c−4pc-4p modulo KK. Translation preserves pair-sum uniqueness and gives the desired tags. □\square

This argument permits all primes pp. The construction uses only Bertrand’s postulate for prime selection.

A Sidon union with arbitrary anchor labels

For an odd prime rr, define the increasing ruler ar(h)=2rh+⟨h2⟩ra_r(h)=2rh+\langle h^2\rangle_r for h≥0h\ge0. For 0≤h<r0\le h<r it is Sidon, by the proof of Lemma 3.1 with the high and low components interchanged. The residue sums are less than 2r2r, so an equality of ruler pair sums first determines those residue sums modulo 2r2r, then the integer sum of the indices, and finally their unordered pair in Fr\mathbb{F}_r. Also, for every h≥0h\ge0,

r<ar(h+1)−ar(h)<3r.(11)r<a_r(h+1)-a_r(h)<3r. \tag*{(11)}

Choose an alphabet and shift TT from Proposition 5.1. For arbitrary labels ℓh\ell_h, put

zh=Kar(h)+4p+T+δℓh+2pεℓh,Ah=pzh,z_h=Ka_r(h)+4p+T+\delta_{\ell_h}+2p\varepsilon_{\ell_h},\qquad A_h=pz_h,
Bh=p(Kar(h)+4p+T).(12)B_h=p(Ka_r(h)+4p+T). \tag*{(12)}

Thus Ah=Bh+pδℓh+εℓhQpA_h=B_h+p\delta_{\ell_h}+\varepsilon_{\ell_h}Q_p.

Lemma 6.1. If p,rp,r are odd primes and 0≤H<r0\le H<r, then S=Cp∪{Ah:0≤h≤H}S=C_p\cup\{A_h:0\le h\le H\} is Sidon for every choice of the labels.

Proof. An equality zi+zj=zk+zlz_i+z_j=z_k+z_l first determines the unordered label pair modulo KK. The sums of the label offsets are consequently equal as integers. Subtract them and divide by KK to obtain an equality of ruler pair sums. The ruler is Sidon on [0,r)[0,r), so {i,j}={k,l}\{i,j\}=\{k,l\}. Moreover, zi+zj=zkz_i+z_j=z_k is impossible by sum-freeness modulo KK.

Every seed mark is less than 2p22p^2, while every anchor is a multiple of pp and at least 4p24p^2. Hence a sum of two seed marks cannot equal a sum involving an anchor. If cp(t)+Ai=cp(u)+Ajc_p(t)+A_i=c_p(u)+A_j, reduction modulo pp gives t=ut=u and then Ai=AjA_i=A_j. Finally, an equality Ai+Aj=cp(t)+AkA_i+A_j=c_p(t)+A_k forces t=0t=0 modulo pp, so cp(t)=0c_p(t)=0 and zi+zj=zkz_i+z_j=z_k, which is impossible. These cases exhaust the possible equalities.

A periodic word for all local windows

Fix a covering alphabet LL, its bounds bb, MM, and an integer K≥1K\ge1. The baselines BhB_h in (12) do not depend on the labels. We show that a single periodic word works for all arithmetic data. In the following proposition the formula for ar(h)a_r(h) is used for every positive integer rr.

Proposition 7.1 (Uniform periodic coverage). There are R≥2R\ge2 and a word w∈LRw\in L^R such that the labels ℓh=wh mod R\ell_h=w_{h\bmod R} have the following property. For every odd prime pp, every r≥1r\ge1, every 0≤h<r0\le h<r, every T≥0T\ge0, and every integer xx with p∤xp\nmid x, if

x−Bh+j∈Ip(M)(0≤j<R),(13)x-B_{h+j}\in I_p(M)\qquad(0\le j<R), \tag*{(13)}

then x∈Ah+j+Dpx\in A_{h+j}+D_p for at least one j∈{0,…,R−1}j\in\{0,\ldots,R-1\}.

The carry vector

For a window starting at hh, write

ej=⌊⟨h2⟩rr+2hrj+j2r⌋.(14)e_j=\left\lfloor\frac{\langle h^2\rangle_r}{r}+\frac{2h}{r}j+\frac{j^2}{r}\right\rfloor. \tag*{(14)}

Direct subtraction gives the exact identity

ar(h+j)−ar(h)=2(r+h)j+j2−rej.(15)a_r(h+j)-a_r(h)=2(r+h)j+j^2-re_j. \tag*{(15)}

Since h<rh<r, the three coefficients in (14) belong to [0,1]×[0,2]×[0,1][0,1]\times[0,2]\times[0,1]. For j<Rj<R, the expression being rounded is between 0 and (R+1)2(R+1)^2. Its floor is determined by O(R3)O(R^3) affine integer-level tests in three variables. Lemma 2.1 therefore gives O(R24)O(R^{24}) possible carry vectors. The explicit bound used in Lean is

#{(ej)j<R}≤25⋅108R24.(16)\#\{(e_j)_{j<R}\}\le25\cdot10^8R^{24}. \tag*{(16)}

The exact good-label criterion

Set A=2K(r+h)A=2K(r+h), B=KrB=Kr, and tj=Aj+Kj2−Bejt_j=Aj+Kj^2-Be_j. Then Bh+j=Bh+ptjB_{h+j}=B_h+pt_j. Write x−Bh=d+pm0x-B_h=d+pm_0, where d=⟨x⟩p∈{1,…,p−1}d=\langle x\rangle_p\in\{1,\ldots,p-1\}. For each row and label put

njℓ=m0−tj−δℓ,σjℓ=⟨njℓ⟩2,Hjℓ=njℓ+σjℓ2.(17)n_{j\ell}=m_0-t_j-\delta_\ell,\qquad\sigma_{j\ell}=\langle n_{j\ell}\rangle_2,\qquad H_{j\ell}=\frac{n_{j\ell}+\sigma_{j\ell}}{2}. \tag*{(17)}

These are integers. Under (13), 0<Hjℓ<p0<H_{j\ell}<p. The lower bound on x−Bh+jx-B_{h+j} gives m0−tj≥2(M+2)m_0-t_j\ge2(M+2) and its upper bound gives m0−tj≤2p−3m_0-t_j\le2p-3. Now use 0≤δℓ≤M0\le\delta_\ell\le M and 0≤σjℓ≤10\le\sigma_{j\ell}\le1.

Let Tjℓ=⟨(Hjℓ+d2)(2d)−1⟩pT_{j\ell}=\langle(H_{j\ell}+d^2)(2d)^{-1}\rangle_p. The label ℓ\ell is good in row jj, meaning

x∈Bh+j+pδℓ+εℓQp+Dp,x\in B_{h+j}+p\delta_\ell+\varepsilon_\ell Q_p+D_p,

if and only if

(Tjℓ<d)⟺σjℓ=1,(⟨Tjℓ2⟩p<Hjℓ)⟺εℓ=1.(18)(T_{j\ell}<d)\Longleftrightarrow\sigma_{j\ell}=1,\qquad(\langle T_{j\ell}^2\rangle_p<H_{j\ell})\Longleftrightarrow\varepsilon_\ell=1. \tag*{(18)}

For sufficiency, apply Lemma 3.2 and (17). For necessity, a representation by two seed marks fixes their parameter difference modulo pp. Their actual parameter difference is d−pσ′d-p\sigma' with σ′∈{0,1}\sigma'\in\{0,1\}. The equality of differences then gives njℓ+σ′=2(H′+pεℓ)n_{j\ell}+\sigma'=2(H'+p\varepsilon_\ell), where H′H' is the actual difference of the two quadratic residues. Thus parity gives σ′=σjℓ\sigma'=\sigma_{j\ell}, and H′≡Hjℓ(modp)H'\equiv H_{j\ell}\pmod p. The quadratic equation fixes the leading seed parameter TjℓT_{j\ell}. Since H′∈(−p,p)H'\in(-p,p), its two possible values are HjℓH_{j\ell} and Hjℓ−pH_{j\ell}-p. These give precisely the choices in (18).

Counting the matrices

For a fixed carry vector, the pattern σjℓ\sigma_{j\ell} depends only on the three parity bits of m0m_0, AA, BB, because KK and the alphabet are fixed. There are at most eight parity patterns. Let ρ=(4d)−1∈Fp\rho=(4d)^{-1}\in\mathbb{F}_p and introduce the five integer features

Fjℓ=(1,j,j2,ej,δℓ−σjℓ).(19)F_{j\ell}=(1,j,j^2,e_j,\delta_\ell-\sigma_{j\ell}). \tag*{(19)}

In Fp\mathbb{F}_p, the parameter TjℓT_{j\ell} is the linear combination of these features with coefficients

ρ(m0+2d2),−ρA,−ρK,ρB,−ρ.\rho(m_0+2d^2),\qquad-\rho A,\qquad-\rho K,\qquad\rho B,\qquad-\rho.

Normalize their least residues by pp. The least residue of TjℓT_{j\ell}, divided by pp, is the fractional part of the resulting real linear form. Its square residue is obtained from the twenty-five ordered products of the five features, using the normalized residues of the products of the corresponding field coefficients.

Permit these five linear coefficients and twenty-five quadratic coefficients to vary independently in [0,1][0,1]. In addition, use five unrestricted real coefficients for Hjℓ/pH_{j\ell}/p, and one real parameter for d/pd/p. Thus all good-label matrices are included in a family of fractional-part tests in 5+25+5+1=365+25+5+1=36 real variables. Allowing independent coefficients enlarges the family. The five height coefficients need no bound in Lemma 2.2.

Each feature has absolute value at most

L=(R+1)2+M+2≤(M+6)R2(R≥1).L=(R+1)^2+M+2\le(M+6)R^2\qquad(R\ge1).

The two forms inside the fractional parts have absolute values at most 5L5L and 25L225L^2. With bRbR row-label positions, Lemma 2.2 bounds the number of matrices, for fixed carries and parity bits, by

[38(4bR(25L2+5L)+1)+1]372.(20)\left[38\left(4bR\left(25L^2+5L\right)+1\right)+1\right]^{37^2}. \tag*{(20)}

This is Ob,M(R370)O_{b,M}(R^{370}). Multiplying by (16) and the eight parity choices gives

#{good-label matrices on an R-window}≤Cb,MR394.(21)\#\{\text{good-label matrices on an }R\text{-window}\}\le C_{b,M}R^{394}. \tag*{(21)}

For example, one may take

Cb,M=25⋅108⋅8⋅1444[4b(2(25(M+6)2+5(M+6))+1)+1]74.C_{b,M}=25\cdot10^8\cdot8\cdot1444\left[4b\left(2\left(25(M+6)^2+5(M+6)\right)+1\right)+1\right]^{74}.

These estimates retain every equality case in the comparisons.

Proof. of Proposition 7.1. Keep only those matrices in the counted family whose rows are all nonempty. Every actual window satisfying (13) gives such a matrix, by the covering property (5). Lemma 2.3, with all cyclic rotations included, supplies an R≥2R \ge2 and a word meeting every retained matrix in every rotation, since

Cb,MR395(1−1/b)R<1C_{b,M}R^{395}(1-1/b)^R < 1

for sufficiently large RR. Fix this word. The labels on a window starting at hh form the rotation beginning at h mod Rh \bmod R. A good entry at which this rotation meets the matrix gives the asserted exact integer representation.

Placement and maximal completion

Fix an alphabet and its periodic word, with period RR. For the moment suppose that p,rp,r are odd primes, r≤pr \le p, and 0≤T<K0 \le T < K, and that

4(M+K+4)≤p,6KRr≤p,R≤r,10p2≤N,N<Br−1,⌊N/p⌋≤p2.(22)\begin{gathered} 4(M+K+4) \le p,\qquad6KRr \le p,\qquad R \le r,\\ 10p^2 \le N,\qquad N < B_{r-1},\qquad\lfloor N/p \rfloor\le p^2. \tag*{(22)} \end{gathered}

By (11), the baselines are strictly increasing and

0<Bh+1−Bh≤Δ,Δ=3Kpr,RΔ≤p2/2.(23)0 < B_{h+1}-B_h \le\Delta,\qquad\Delta=3Kpr,\qquad R\Delta\le p^2/2. \tag*{(23)}

Write J=2p(M+2)J=2p(M+2). The first condition in (22) gives J≤p2/2J \le p^2/2, and therefore

J+RΔ≤p2≤2p(p−1).(24)J+R\Delta\le p^2 \le2p(p-1). \tag*{(24)}

Choose HH as the largest integer in [0,r−1][0,r-1] for which

BH+Qp+pM+1≤N.(25)B_H+Q_p+pM+1 \le N. \tag*{(25)}

This choice exists and satisfies R−1≤H<r−1R-1 \le H < r-1. Indeed, B0=4p2+pTB_0=4p^2+pT, so (23) gives BR−1≤4p2+pT+RΔB_{R-1} \le4p^2+pT+R\Delta. Together with T<K≤pT<K \le p, M≤pM \le p, and (22), this implies (25) at R−1R-1. The last index r−1r-1 fails because N<Br−1N < B_{r-1}.

All elements of S=Cp∪{Ah:0≤h≤H}S=C_p\cup\{A_h:0\le h\le H\} lie in [0,N)[0,N), by (25). Lemma 6.1 shows that SS is Sidon, and

∣S∣≤p+H+1≤p+r≤2p.(26)|S| \le p+H+1 \le p+r \le2p. \tag*{(26)}

Lemma 8.1 (Interior points are blocked). If x∉Sx\notin S, p∤xp\nmid x, and BR−1+J≤x<BH+JB_{R-1}+J \le x < B_H+J, then S∪{x}S\cup\{x\} is not Sidon.

Proof. Let tt be the largest index in [0,H][0,H] with Bt+J≤xB_t+J \le x. The bounds on xx give R−1≤t<HR-1 \le t < H and x<Bt+1+Jx < B_{t+1}+J. For h=t−R+1h=t-R+1 and 0≤j<R0\le j<R, monotonicity and (23) give J≤x−Bh+j<J+RΔ≤2p(p−1)J \le x-B_{h+j}<J+R\Delta\le2p(p-1). Proposition 7.1 gives x=Ah+j+c−dx=A_{h+j}+c-d with c,d∈Cpc,d\in C_p. Hence x+d=Ah+j+cx+d=A_{h+j}+c is an equality of pair sums in S∪{x}S\cup\{x\}, and the unordered pairs differ because x∉Sx\notin S.

The unblocked points are thus contained in

[0,BR−1+J]∪[BH+J,N]∪pZ.(27)[0,B_{R-1}+J]\cup[B_H+J,N]\cup p\mathbb{Z}. \tag*{(27)}

The first interval has diameter at most 10p210p^2. For the second, maximality of HH gives

N<BH+1+Qp+pM+1≤BH+Δ+Qp+pM+1.N < B_{H+1}+Q_p+pM+1 \le B_H+\Delta+Q_p+pM+1.

Therefore max⁡(0,N−BH−J)≤10p2\max(0,N-B_H-J)\le10p^2.

Lemma 8.2 (Cost of completion). Under (22), some maximal Sidon subset of [0,N)[0,N) containing SS has at most 14p14p elements.

Proof. Extend SS to an inclusion-maximal Sidon subset AA of the finite host. Any point blocked by SS remains blocked by every superset, so all new marks lie in (27).

If a Sidon set has mm elements in an interval of diameter LL, its m(m−1)m(m-1) ordered nonzero differences are distinct. In particular m(m−1)≤2L+1m(m-1) \le2L+1. For L≤10p2L \le10p^{2}, this implies m≤5pm \le5p. For marks divisible by pp, divide all marks by pp. The resulting set remains Sidon and has diameter at most ⌊N/p⌋≤p2\lfloor N/p\rfloor\le p^{2}, so it has at most 2p2p elements. Restricting AA to each exceptional set preserves Sidonicity. Using these three bounds, allowing overlap, and (26), gives

∣A∣≤∣S∣+5p+5p+2p≤14p.|A| \le|S| + 5p + 5p + 2p \le14p.

Translation by 11 gives a maximal Sidon subset of [1,N][1,N] with the same cardinality. In the certificate this step uses the corresponding translation of the exceptional residue class.

Prime selection and proof of the main theorem

Fix the two alphabets and the modulus KK from Proposition 5.1. Apply Proposition 7.1 to each alphabet with this KK, obtaining periods R1,R2R_1,R_2. Put

R∗=R1+R2,M∗=M1+M2,L∗=12KR∗+16,n0=40L∗2+4(M∗+K+4)+R∗+2.(28)\begin{aligned} R_* &= R_1 + R_2, \qquad M_* = M_1 + M_2, \qquad L_* = 12KR_* + 16,\\ n_0 &= 40L_*^2 + 4(M_* + K + 4) + R_* + 2. \tag*{(28)} \end{aligned}

These are absolute finite integers fixed independently of NN.

Proof of Theorem 1.1. Let N≥n03N \ge n_0^3 and choose n≥n0n \ge n_0 such that n3≤N<(n+1)3n^3 \le N < (n+1)^3. Bertrand’s postulate supplies primes

L∗n<p≤2L∗n,n<r≤2n.(29)L_*n < p \le2L_*n, \qquad n < r \le2n. \tag*{(29)}

Both primes are odd. Proposition 5.1 selects a compatible alphabet for this pp and a shift T<KT < K. Use its period R≤R∗R \le R_* and bound M≤M∗M \le M_*.

We verify (22). Since n≥n0n \ge n_0,

4(M+K+4)≤n<p,R≤n<r≤p,6KRr≤12KR∗n≤L∗n<p.4(M + K + 4) \le n < p, \qquad R \le n < r \le p, \qquad6KRr \le12KR_*n \le L_*n < p.

Also 10p2≤40L∗2n2≤n3≤N10p^2 \le40L_*^2n^2 \le n^3 \le N. For r≥2r \ge2 we have ar(r−1)≥r2a_r(r-1) \ge r^2. Therefore Br−1≥pKr2≥16n3>(n+1)3>NB_{r-1} \ge pKr^2 \ge16n^3 > (n+1)^3 > N, where n≥2n \ge2 and K≥1K \ge1. Finally p≥n+1p \ge n+1 gives N<p3N < p^3, hence ⌊N/p⌋≤p2\lfloor N/p\rfloor\le p^2.

Lemma 8.2 provides a maximal Sidon set in [1,N][1,N] of cardinality at most 14p≤28L∗n≤28L∗N1/314p \le28L_*n \le28L_*N^{1/3}. Thus one may take C=28L∗C = 28L_* and N0=n03N_0 = n_0^3.

Remark 9.1. The proof is existential. The finite pattern arguments determine absolute alphabets and words. The resulting constants have not been optimized. No numerical search for these objects is used in establishing the theorem.

Appendix A. The Lean certificate

The original companion file Erdos156.lean contains the construction-specific auxiliary results and the theorem Bounty.target. The original challenge wrapper imports Mathlib, FormalConjectures.ErdosProblems.156, and TaskSupport. Its final declaration is

namespace Bounty
theorem target : fcTypeOfName% "Erdos156.erdos_156" :=
  target_iff_small_maximal_sets.mpr
    Construction.eventual_small_maximal_sets
end Bounty

The target type is checked against the explicit proposition

True  ⟺  (N↦(minMaximalSidonSet⁡(N):R))=ON→∞(N↦(N:R)1/3).\mathrm{True} \iff(N \mapsto(\operatorname{minMaximalSidonSet}(N) : \mathbb{R})) = O_{N \to\infty}(N \mapsto(N : \mathbb{R})^{1/3}).

The reduction target_iff_small_maximal_sets identifies this statement with the existence of eventually bounded maximal sets. The proof uses the construction above to supply these sets.

Verification record. The original source report gives Lean 4.35.0-rc2 and the following revisions.

Mathlib065356127b1dc0016f66b7283ce0ce2c4055aa55
Challengebf40872fe09f3c9c94e5b1480823a0622cc1698a

The reported single-file source has 3,725 lines and SHA-256 digest

e266058ad3e0e487ea88440470c6d8dbc0 f51999b08daa68c0fce5bd3bdc664b.

The pinned portable project audit reports a successful statement bridge, source build, and kernel replay. It audited all 178 public theorems, including the eleven declarations with an inline @[simp] attribute omitted from the original count [8]. The final theorem depends exactly on propext, Classical.choice, and Quot.sound. The bibliography includes the standard references for Lean and Mathlib [5, 6].

Correspondence between the paper and certificate. In the table, the SignPatterns, Window, and Construction namespaces are nested in Bounty.

Mathematical componentPrincipal Lean declarations
Affine and fractional-part pattern boundsSignPatterns.affine_sign_determined_card_le<br>SignPatterns.fractional_phase_card_le
Finite selection and rotationsBounty.exists_hitting_word_permutations<br>Bounty.exists_hitting_word_of_polynomial_bound
Quadratic seed and carriesBounty.quadraticSeed_isSidon<br>Bounty.quadratic_difference_canonical
Separated covering alphabetsConstruction.exists_separatedAlphabet
Tags for every primeConstruction.one_of_two_tag_unique<br>Construction.exists_two_tagged_alphabets
Window counts and periodic wordWindow.floorFamily_card_polynomial<br>Window.allWindowFamily_card_polynomial<br>Window.CoverAlphabet.exists_ruler_word
Sidon union and interior blockingConstruction.seed_anchor_union_isSidon<br>Construction.CoverScheme.blocks_interior
Truncation and maximal completionConstruction.CoverScheme.exists_truncation<br>Construction.maximal_completion_shifted
Prime selection and asymptotic boundConstruction.choose_primes_at_scale<br>Construction.eventual_small_maximal_sets<br>Bounty.target

Table 1.

Acknowledgments

OpenAI Codex provided substantial assistance with mathematical development, the Lean formalization, proof checking, and preparation of the exposition and \LaTeX{} source. The formalization uses Lean and Mathlib, and the target statement is supplied by the Formal Conjectures project and the Conjectures.io task bundle [7]. Email address: [email protected]

Email address: [email protected]

Email address: [email protected]

Email address: [email protected]

References

  1. [1]P. Erdős, A. Sárközy, and V. T. Sós, On sum sets of Sidon sets, I, J. Number Theory 47 (1994), no. 3, 329–347. DOI.
  2. [2]I. Z. Ruzsa, A small maximal Sidon set, Ramanujan J. 2 (1998), 55–58. DOI.
  3. [3]N. Sauer, On the density of families of sets, J. Combin. Theory Ser. A 13 (1972), no. 1, 145–147. DOI.DOI
  4. [4]S. Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math. 41 (1972), no. 1, 247–261. DOI.DOI
  5. [5]L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in Automated Deduction—CADE 28, LNCS 12699, Springer, 2021, 625–635. DOI.DOI
  6. [6]The mathlib Community, The Lean mathematical library, in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP ’20), ACM, 2020, 367–381. DOI.DOI
  7. [7]Formal Conjectures project and Conjectures.io, Erdős problem 156, formalized task bundle at revision bf40872f.
  8. [8]Justin Sun Prize submission JSP-000154 and pinned manuscript and verification notes.

Paper details

vlnc:W_z9kdvzer
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex

View statement
Looking for related papers…
Contents