← All papers
First page of Formalizing Singer Sidon Constructions and Sidon Set Infrastructure in Lean 4

Formalizing Singer Sidon Constructions and Sidon Set Infrastructure in Lean 4

David B. Hulak, Arthur F. Ramos, Ruy J. G. B. de Queiroz

math.CO May 5, 2026 · v1
Formalizes Singer's Sidon set construction and reusable Sidon-set infrastructure in 7541 lines of Lean 4.
Erdős Problem 30 asks for sharp asymptotics of the Sidon extremal function $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$, we prove the existence of a Sidon set modulo $q^2+q+1$ of cardinality $q+1$; the prime-field case $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. It comprises interval and modular Sidon sets, the extremal function $h(N)$, Lindström's cross-difference inequality, a Johnson-route shift-incidence upper bound of the form $h(N)\leq\sqrt{N}+N^{1/4}+O(1)$, representation-function identities, and unconditional two-sided $h(N)=Θ(\sqrt{N})$ bounds with exact floor-rounded finite statements for $N\geq 5$. We further formalize a conditional reduction: subpolynomial prime gaps together with a full subpolynomial upper-error hypothesis for $h(N)$ imply the Erdős Problem 30 estimate $h(N)=\sqrt{N}+O_ε(N^ε)$ for every $ε>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.

Erdos Problem 30 asks for sharp asymptotics of the Sidon extremal function h(N), and Singer's construction is the classical source of lower-bound examples. No prior Lean formalization existed for Singer's construction or for reusable Sidon set infrastructure in additive combinatorics.

The authors formalize Singer's Sidon set construction in Lean 4, proving that for every prime power q there exists a Sidon set modulo q^2+q+1 of cardinality q+1. The proof proceeds through construction of the base field and its degree-three extension, analysis of the trace kernel as a 2-dimensional subspace, a geometric argument via subspace intersections establishing the multiplicative Sidon property, and transfer from quotient multiplication to modular integer addition. Around this, the authors develop a reusable Sidon set library including interval and modular Sidon sets, the extremal function h(N), Lindstrom's cross-difference inequality, a Johnson-route shift-incidence upper bound, representation-function identities, and unconditional two-sided bounds.

The formalization comprises 7,541 lines of Lean 4 with zero active uses of sorry. It establishes unconditional two-sided h(N) = Theta(sqrt(N)) bounds with exact floor-rounded finite statements for N >= 5, and formalizes a conditional reduction showing that subpolynomial prime gaps together with a subpolynomial upper-error hypothesis imply h(N) = sqrt(N) + O_epsilon(N^epsilon).

ModuleContentLines
Sidon.leanSidon predicate, basic properties85
Interval.leanInterval/modular Sidon, transfer526
SidonGap.leanSidon gap distinctness and quantitative transfer1395
SingerSidon.leanQuotient-group Sidon property129
SingerTheorem.leanQuotient-to-modular transfer316
FormalStatement.leanh(N), Erdos 30 statement171
Module breakdown of the formalization