Formalizing Singer Sidon Constructions and Sidon Set Infrastructure in Lean 4
David B. Hulak, Arthur F. Ramos, Ruy J. G. B. de Queiroz · 2026
Read Formalizing Singer Sidon Constructions and Sidon Set Infrastructure in Lean 4 by David B. Hulak, Arthur F. Ramos, Ruy J. G. B. de Queiroz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03274.txt.
Introduction
David B. Hulak, Arthur F. Ramos, and Ruy J. G. B. de Queiroz formalize Singer's construction of Sidon sets in the Lean 4 proof assistant. Sidon sets have all pairwise sums distinct, and Singer's finite-field method gives the classic large examples behind Erdős Problem 30.
For every prime power, they prove a Sidon set of the stated size exists modulo the matching number, through a chain running from field extensions and trace kernels to subspace geometry. Around that core they build a reusable library with bounds on the extremal function and representation identities. Thousands of lines check with no gaps left open.
Catalog record
| CREATOR | David B. Hulak, Arthur F. Ramos, Ruy J. G. B. de Queiroz |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.03274
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Formalizing Singer Sidon Constructions and Sidon Set Infrastructure in Lean 4 David B. Hulak, Arthur F. Ramos, Ruy J. G. B. de Queiroz Abstract Erdős Problem 30 asks for sharp asymptotics of the Sidon extremal function h ( N ) h(N) , and Singer’s construction is the classical source of lower-bound examples matching the main term. We present a Lean 4 formalization of Singer’s Sidon set construction, together with reusable Sidon-set infrastructure for additive combinatorics. For every prime power q = p k q=p^{k} , we prove the existence of a Sidon set modulo q 2 + q + 1 q^{2}+q+1 of cardinality q + 1 q+1 ; the prime-field case q = p q=p is the base presentation. The proof proceeds through a non-trivial algebraic chain: construction of the base field and its degree-three extension, analysis of the trace kernel as a 2-dimensional subspace over the base field, a geometric argument via subspace intersections establishing the multiplicative Sidon property in the quotient group, and a transfer from quotient multiplication to modular integer addition. Around this central result, we develop a reusable Sidon set library for additive combinatorics. It comprises interval Sidon sets, modular Sidon sets, the extremal function h ( N ) h(N) , Lindström’s cross-difference inequality, a Johnson-route shift-incidence upper bound of the form h ( N ) ≤ N + N 1 / 4 + O ( 1 ) h(N)\leq\sqrt{N}+N^{1/4}+O(1) , exact representation-function identities, and unconditional two-sided h ( N ) = Θ ( N ) h(N)=\Theta(\sqrt{N}) bounds with exact floor-rounded finite statements for N ≥ 5 N\geq 5 . We further formalize a conditional reduction: subpolynomial prime gaps together with a full subpolynomial upper-error hypothesis for h ( N ) h(N) imply the Erdős Problem 30 estimate h ( N ) = N + O ε ( N ε ) h(N)=\sqrt{N}+O_{\varepsilon}(N^{\varepsilon}) for every ε > 0 \varepsilon>0 . The Singer/Sidon modules and transfer lemmas comprise 7 541 lines of Lean 4 with zero active uses of sorry . We describe the mathematical lessons learned, focusing on how formalization clarifies the precise scope of classical arguments and forces explicit treatment of the passage from the field-theoretic construction to integer Sidon predicates. 2020 Mathematics Subject Classification: 05B10, 11B75, 68V20. Keywords: Singer theorem, Sidon sets, Lean 4, formalization, additive combinatorics, difference sets. 1 Introduction 1.1 Erdős Problem 30 Let h(N)=\max\{|A|:A\subseteq\{1,\dots,N\}\text{ is Sidon}\} , where a set A of integers is Sidon (or a B_{2} set) if all pairwise sums a+b with a\leq b (including a=b ) and a,b\in A are distinct. Lindström [ 15 ] established the upper bound h(N)\leq\sqrt{N}+N^{1/4}+1, sharpening the earlier Erdős–Turán [ 10 ] bound. Later work [ 2 , 8 ] improves the constant in the N^{1/4} term but not the exponent. On the lower side, Singer’s construction and prime-finding results give h(N)\geq\sqrt{N}-O(N^{\theta_{\mathrm{gap}}}) . Thus an upper error O(N^{\theta_{\mathrm{up}}}) and this Singer–prime lower error combine to give h(N)=\sqrt{N}+O(N^{\max(\theta_{\mathrm{up}},\theta_{\mathrm{gap}})}) . Here \theta_{\mathrm{gap}} denotes the prime-gap error exponent and \theta_{\mathrm{up}} the upper-bound error exponent for h(N) . Erdős Problem 30 [ 9 , 12 ] asks whether this can be improved to h(N)=\sqrt{N}+O_{\varepsilon}(N^{\varepsilon}) for every \varepsilon>0 . This remains open. 1.2 Why formalize? Formalization of classical combinatorial number theory serves three purposes beyond mere verification: 1. Scope discipline : the type system forces the formalizer to confront exactly which hypotheses each theorem requires. For Singer’s construction, the development separates the prime-field presentation from the prime-power theorem, where the base field is GaloisField p k and the degree-three extension is supplied by Mathlib’s finite-field extension API. 2. Field-to-integer transfer : the passage from algebraic structures (quotient groups, field extensions) to combinatorial predicates (modular Sidon, interval containment) requires explicit definitions and transfer lemmas that informal proofs often elide. 3. Conditional dependencies : formal verification makes the logical dependencies between open conjectures (prime gaps, upper bounds) and the target statement (Erdős 30) machine-checkable. 1.3 Contributions Our main contributions are: 1. A Singer formalization presented through explicit Sidon-set predicates ( \lx@sectionsign 3 ), with the algebraic chain (trace-kernel proof, no-invariant-subspace argument, Grassmann intersection, projective-line representatives) and the transfer through the modular Sidon predicate fully unfolded; this yields the prime-field theorem and the prime-power theorem giving Sidon sets of size q+1 modulo q^{2}+q+1 for every prime power q=p^{k} . 2. A reusable Sidon set library ( \lx@sectionsign 4 ) with interval and modular variants, the extremal function h(N) , and modular-to-interval transfer machinery. 3. Unconditional bounds on h(N) ( \lx@sectionsign 5 ), including h(N)=\Theta(\sqrt{N}) and a formalized Johnson-route upper bound h(N)\leq\lfloor\sqrt{N}\rfloor+\lfloor\sqrt{\lfloor\sqrt{N}\rfloor}\rfloor+2 for N\geq 16 , matching Lindström’s \sqrt{N}+N^{1/4}+O(1) leading order. This yields two separate consequences: the one-sided upper-bound half of Erdős 30 for \varepsilon\geq 1/4 , and, from the coarser two-sided bounds, the full two-sided estimate for the coarse range \varepsilon\geq 1/2 . 4. A conditional reduction ( \lx@sectionsign 6 ) whose mathematical content is the prime-gap-driven lower-bound transfer sidonLowerBound_of_singer_and_gap , including the threshold arithmetic that turns subpolynomial gaps into a Sidon lower error of the same exponent; the final assembly erdos30_of_gap_and_upper packages this with the upper-bound hypothesis as a clean corollary. 5. Mathematical lessons ( \lx@sectionsign 7 ) on how formalization reshapes the classical Singer argument and exposes hidden dependencies in the field-to-integer transfer. 1.4 Scope and limitations We separate deliberate modeling choices from practical limitations. Modeling choices (deliberate scope decisions that do not weaken stated results): • Singer’s original theorem [ 19 ] applies to all prime powers q . We now formalize both the prime case q=p , using Lean’s GaloisField p 3 type, and the prime-power case q=p^{k} , using GaloisField p k as the base field and a degree-three finite-field extension over it. • The conditional Erdős 30 reduction relies on a subpolynomial prime gap hypothesis (implied by Cramér’s conjecture [ 7 ] but weaker) which remains open. This is inherent: no unconditional proof of Erdős 30 is known. Practical limitations (results not provided by this paper): • The prime-power Singer theorem does not close Erdős 30. It discharges the algebraic Singer-family input at prime powers, but the subpolynomial prime-gap and upper-bound hypotheses in the full conditional reduction remain open. 1.5 Development overview The files listed in Table 1 comprise 7 541 lines of Lean 4. The build uses toolchain leanprover/lean4:v4.29.0 and the Mathlib commit 8a178386ffc0f5fef0b77738bb5449d50efeea95 . This Mathlib commit bumps the Mathlib toolchain to Lean v4.29.0 and, together with the toolchain pin, fully determines the build environment. Those files sit inside a larger Erdős Problem 30 repository, which also contains boundary-analysis modules, computational verification modules (using native_decide ), and experimental proof paths. The listed Singer/Sidon files reported in this paper use no sorry and no native_decide . For the declarations listed in AxiomCheck.lean , the axiom audit reports only Lean’s standard foundations ( propext , Quot.sound , Classical.choice ). The use of classical logic is inherent: the extremal function h(N) is defined via a non-constructive maximum, and the Galois field construction requires classical existence of irreducible polynomials. Table 1: Modules listed for the Singer/Sidon formalization. Module Content Lines Sidon.lean Sidon predicate, basic properties 85 Interval.lean Interval/modular Sidon, transfer 526 CyclicWindow.lean Cyclic-window relabeling 177 Averaging.lean Window averaging lemma 183 GapBound.lean Distinct-gap lower bound 192 SidonGap.lean Sidon gap distinctness