WorksMathematics
Small maximal integer Sidon sets by finite phase colorings
Abstract
Every sufficiently large integer interval contains an inclusion-maximal Sidon set of size . 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 and the multiples of , with . A maximal completion adds only elements. The linked Lean verification covers the original upper-bound target.
Introduction
A set of integers is a Sidon set if , with , implies as multisets. In particular, diagonal sums are included in the definition. A Sidon subset of is maximal if adjoining any further point of that interval destroys the Sidon property. Write
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 . 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 and such that, for every integer , there is a maximal Sidon set satisfying . Equivalently, .
The exponent is forced by a counting argument.
Proposition 1.2. Every maximal Sidon set satisfies .
Proof. The case is immediate. Otherwise put . For every , a nontrivial equality of pair sums in must take one of the forms
Indeed, equalities using once on each side cancel to a trivial equality. Consequently the interval is contained in the union of , , and the set of integral midpoints of pairs from . Thus . □
Together, Theorem 1.1 and Proposition 1.2 give . The companion certificate proves the upper bound.
Organization and notation. For an integer and a positive integer , let be its least nonnegative residue. For a real number , write . All intervals below are intersected with when used as sets of marks.
We first work in and translate by 1 at the end. A quadratic seed supplies controlled differences. A finite alphabet of translates covers all nonmultiples of 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 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 be affine real functions on . The number of joint sign patterns, with each sign in , is at most
The same bound applies to any finite-valued label determined by these signs.
Proof. Homogenize the affine functions on . The family of their positive supports has VC dimension at most . 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
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 comparisons
where are affine functions of , and on the parameter set under consideration, with a nonnegative integer. The number of labels is at most
No bound on the values of is required.
Proof. For each integer , record the signs of and . The first collection determines , including the case that is an integer. The second determines whether . There are affine functions. Apply Lemma 2.1. □
Lemma 2.3 (A common hitting word). Fix . For each , let be a family of matrices
If for fixed constants , then for all sufficiently large there is a word that meets every matrix: for each , some satisfies . 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 . The union bound is less than 1 once . To include all rotations, use the bound , which also tends to zero. □
The quadratic seed and exact differences
Let be an odd prime and put
Lemma 3.1. The set is Sidon, has elements, and is contained in .
Proof. If , reduction modulo gives , since both sums lie in . Subtracting this equality and dividing by gives equality of the sums of the quadratic residues. In we therefore have and . As is odd, these imply . The two pairs are roots of the same monic quadratic, so they agree as unordered pairs in , and hence as integer pairs in . Distinct parameters give distinct residues modulo , proving the cardinality statement. Finally, . □
Lemma 3.2 (Exact lift with two carries). Let and . Define
Then and
Proof. The definition of gives and . In , . The difference of the two least residues lies strictly between and . It is therefore or . The latter alternative occurs exactly when . Substitution in (3.1) proves the identity. □
In particular, if and , then
Thus the six pairs contain a suitable choice in every row. The identity is in .
A fixed covering alphabet
Definition 4.1. A covering alphabet consists of a finite label set of size , integers , and , such that
equality of two -pair sums determines the unordered pair of labels,
for every odd prime ,
The interval in (4.1) may be empty.
Proposition 4.2 (Separated covering alphabets). Covering alphabets exist. Moreover, for every prescribed , one can choose a covering alphabet for which
Proof. Fix a positive integer with . For , set and . The sequence is Sidon. A pair-sum equality modulo first determines the integer sum of the indices, and then the sum of their squares determines the unordered pair. Any selection of pairs gives
Here and . For distinct unordered index pairs, the -pair sums differ by at least 1, while the difference of the two -pair sums has absolute value at most 4. This proves (6) for every selection.
Write a target in uniquely as , where and . The interval bounds give . Hence lies in for every row. Let and . The successful pair in (4) is determined by the tests
The first test determines , and the second determines . Put .
Treat the eight normalized quantities in (8) as independent parameters in . This enlarges the pattern family. Since , the arguments inside the fractional parts are bounded in absolute value by . There are tests, so Lemma 2.2 gives matrices of successful choices, including both values of . Every row is a singleton. The formal bound is
By Lemma 2.3, for sufficiently large there is a fixed word of six choices that meets every matrix. Fix this word and use (7). For any and under consideration, a row at which the selected word agrees with its successful choice supplies (4). All choices and constants are fixed before and are given.
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 and an integer with the following property. For every integer , at least one alphabet admits a shift such that the residues
determine unordered label pairs from their pair sums and are sum-free:
Proof. Choose any covering alphabet with bound . By Proposition 4.2, choose with separation greater than and bound . Let be their sizes and put
For either alphabet, first consider the unshifted residues . A collision of distinct unordered label pairs gives
We have , , and . Since , such a collision must have . Suppose both alphabets have a collision, with differences and . Eliminating gives
Thus . As , we get , contrary to the separation of . At least one unshifted alphabet therefore has unique label pair sums modulo .
For any residues modulo , translation by can violate sum-freeness only if modulo for some triple of labels. There are at most forbidden shifts. Choose an allowed , and take to be the representative of modulo . Translation preserves pair-sum uniqueness and gives the desired tags.
This argument permits all primes . The construction uses only Bertrand’s postulate for prime selection.
A Sidon union with arbitrary anchor labels
For an odd prime , define the increasing ruler for . For it is Sidon, by the proof of Lemma 3.1 with the high and low components interchanged. The residue sums are less than , so an equality of ruler pair sums first determines those residue sums modulo , then the integer sum of the indices, and finally their unordered pair in . Also, for every ,
Choose an alphabet and shift from Proposition 5.1. For arbitrary labels , put
Thus .
Lemma 6.1. If are odd primes and , then is Sidon for every choice of the labels.
Proof. An equality first determines the unordered label pair modulo . The sums of the label offsets are consequently equal as integers. Subtract them and divide by to obtain an equality of ruler pair sums. The ruler is Sidon on , so . Moreover, is impossible by sum-freeness modulo .
Every seed mark is less than , while every anchor is a multiple of and at least . Hence a sum of two seed marks cannot equal a sum involving an anchor. If , reduction modulo gives and then . Finally, an equality forces modulo , so and , which is impossible. These cases exhaust the possible equalities.
A periodic word for all local windows
Fix a covering alphabet , its bounds , , and an integer . The baselines 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 is used for every positive integer .
Proposition 7.1 (Uniform periodic coverage). There are and a word such that the labels have the following property. For every odd prime , every , every , every , and every integer with , if
then for at least one .
The carry vector
For a window starting at , write
Direct subtraction gives the exact identity
Since , the three coefficients in (14) belong to . For , the expression being rounded is between 0 and . Its floor is determined by affine integer-level tests in three variables. Lemma 2.1 therefore gives possible carry vectors. The explicit bound used in Lean is
The exact good-label criterion
Set , , and . Then . Write , where . For each row and label put
These are integers. Under (13), . The lower bound on gives and its upper bound gives . Now use and .
Let . The label is good in row , meaning
if and only if
For sufficiency, apply Lemma 3.2 and (17). For necessity, a representation by two seed marks fixes their parameter difference modulo . Their actual parameter difference is with . The equality of differences then gives , where is the actual difference of the two quadratic residues. Thus parity gives , and . The quadratic equation fixes the leading seed parameter . Since , its two possible values are and . These give precisely the choices in (18).
Counting the matrices
For a fixed carry vector, the pattern depends only on the three parity bits of , , , because and the alphabet are fixed. There are at most eight parity patterns. Let and introduce the five integer features
In , the parameter is the linear combination of these features with coefficients
Normalize their least residues by . The least residue of , divided by , 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 . In addition, use five unrestricted real coefficients for , and one real parameter for . Thus all good-label matrices are included in a family of fractional-part tests in 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
The two forms inside the fractional parts have absolute values at most and . With row-label positions, Lemma 2.2 bounds the number of matrices, for fixed carries and parity bits, by
This is . Multiplying by (16) and the eight parity choices gives
For example, one may take
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 and a word meeting every retained matrix in every rotation, since
for sufficiently large . Fix this word. The labels on a window starting at form the rotation beginning at . 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 . For the moment suppose that are odd primes, , and , and that
By (11), the baselines are strictly increasing and
Write . The first condition in (22) gives , and therefore
Choose as the largest integer in for which
This choice exists and satisfies . Indeed, , so (23) gives . Together with , , and (22), this implies (25) at . The last index fails because .
All elements of lie in , by (25). Lemma 6.1 shows that is Sidon, and
Lemma 8.1 (Interior points are blocked). If , , and , then is not Sidon.
Proof. Let be the largest index in with . The bounds on give and . For and , monotonicity and (23) give . Proposition 7.1 gives with . Hence is an equality of pair sums in , and the unordered pairs differ because .
The unblocked points are thus contained in
The first interval has diameter at most . For the second, maximality of gives
Therefore .
Lemma 8.2 (Cost of completion). Under (22), some maximal Sidon subset of containing has at most elements.
Proof. Extend to an inclusion-maximal Sidon subset of the finite host. Any point blocked by remains blocked by every superset, so all new marks lie in (27).
If a Sidon set has elements in an interval of diameter , its ordered nonzero differences are distinct. In particular . For , this implies . For marks divisible by , divide all marks by . The resulting set remains Sidon and has diameter at most , so it has at most elements. Restricting to each exceptional set preserves Sidonicity. Using these three bounds, allowing overlap, and (26), gives
Translation by gives a maximal Sidon subset of 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 from Proposition 5.1. Apply Proposition 7.1 to each alphabet with this , obtaining periods . Put
These are absolute finite integers fixed independently of .
Proof of Theorem 1.1. Let and choose such that . Bertrand’s postulate supplies primes
Both primes are odd. Proposition 5.1 selects a compatible alphabet for this and a shift . Use its period and bound .
We verify (22). Since ,
Also . For we have . Therefore , where and . Finally gives , hence .
Lemma 8.2 provides a maximal Sidon set in of cardinality at most . Thus one may take and .
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
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.
| Mathlib | 065356127b1dc0016f66b7283ce0ce2c4055aa55 |
| Challenge | bf40872fe09f3c9c94e5b1480823a0622cc1698a |
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 component | Principal Lean declarations |
| Affine and fractional-part pattern bounds | SignPatterns.affine_sign_determined_card_le<br>SignPatterns.fractional_phase_card_le |
| Finite selection and rotations | Bounty.exists_hitting_word_permutations<br>Bounty.exists_hitting_word_of_polynomial_bound |
| Quadratic seed and carries | Bounty.quadraticSeed_isSidon<br>Bounty.quadratic_difference_canonical |
| Separated covering alphabets | Construction.exists_separatedAlphabet |
| Tags for every prime | Construction.one_of_two_tag_unique<br>Construction.exists_two_tagged_alphabets |
| Window counts and periodic word | Window.floorFamily_card_polynomial<br>Window.allWindowFamily_card_polynomial<br>Window.CoverAlphabet.exists_ruler_word |
| Sidon union and interior blocking | Construction.seed_anchor_union_isSidon<br>Construction.CoverScheme.blocks_interior |
| Truncation and maximal completion | Construction.CoverScheme.exists_truncation<br>Construction.maximal_completion_shifted |
| Prime selection and asymptotic bound | Construction.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]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]I. Z. Ruzsa, A small maximal Sidon set, Ramanujan J. 2 (1998), 55–58. DOI.
- [3]N. Sauer, On the density of families of sets, J. Combin. Theory Ser. A 13 (1972), no. 1, 145–147. DOI.DOI
- [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]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]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]Formal Conjectures project and Conjectures.io, Erdős problem 156, formalized task bundle at revision bf40872f.
- [8]Justin Sun Prize submission JSP-000154 and pinned manuscript and verification notes.