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

CREATORDavid B. Hulak, Arthur F. Ramos, Ruy J. G. B. de Queiroz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text