\documentclass[11pt]{amsart} \usepackage[letterpaper,margin=1in,headheight=14pt]{geometry} \usepackage{amsmath,amssymb} \usepackage[hidelinks]{hyperref} \emergencystretch=2em \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} \newcommand{\Z}{\mathbb Z} \newcommand{\N}{\mathbb N} \newcommand{\R}{\mathbb R} \newcommand{\F}{\mathbb F} \newcommand{\one}{\mathbf 1} \newcommand{\res}[2]{\langle #1\rangle_{#2}} \newcommand{\floor}[1]{\lfloor #1\rfloor} \newcommand{\fracpart}[1]{\{#1\}} \title[Small maximal Sidon sets]{Small maximal integer Sidon sets by finite phase colorings} \author{Will Howe} \email{howew@purdue.edu} \author{Grant Huffman} \email{huffma97@purdue.edu} \author{Jensen Kohlmeyer} \email{jenwin@purdue.edu} \author{Liam Kruer} \email{kruerl@purdue.edu} \date{November 2, 2026} \subjclass[2020]{11B13, 11B75, 05D40} \keywords{Maximal Sidon set, additive combinatorics, finite phase coloring, formal verification} \begin{document} \begin{abstract} We prove that every sufficiently large integer interval \(\{1,\ldots,N\}\) contains an inclusion-maximal Sidon set of cardinality \(O(N^{1/3})\). The construction combines a quadratic Sidon seed with a periodically labeled family of anchors. Finite-dimensional bounds for affine sign patterns produce a fixed alphabet of integer translates and a periodic word that covers every relevant local window. A pair of separated alphabets supplies Sidon, sum-free tags for every prime, so the prime-selection step uses only Bertrand's postulate. The resulting seed blocks every point outside two intervals of length \(O(p^2)\) and one residue class, where \(p\asymp N^{1/3}\). A maximal completion adds only \(O(p)\) elements. A Lean proof verifies the upper bound, including the uniform pattern counts and the placement argument, against the formal statement of Erd\H{o}s problem 156. \end{abstract} \maketitle \section{Introduction} A set of integers \(A\) is a Sidon set if \(a+b=c+d\), with \(a,b,c,d\in A\), implies \(\{a,b\}=\{c,d\}\) as multisets. In particular, diagonal sums \(2a\) are included in the definition. A Sidon subset of \([1,N]\cap\Z\) is maximal if adjoining any further point of that interval destroys the Sidon property. Write \[ s(N)=\min\{|A|: A\subseteq[1,N]\cap\Z\text{ is a maximal Sidon set}\}. \] Maximality is with respect to inclusion. Erd\H{o}s, S\'ark\"ozy, and S\'os studied this problem in their work on sumsets of Sidon sets \cite{ess}. Ruzsa \cite{ruzsa} proved the existence of maximal Sidon sets of size \(O((N\log N)^{1/3})\). We establish the following upper bound by a construction whose uniformity statements are included in a Lean proof. \begin{theorem}\label{thm:main} There are absolute constants \(C>0\) and \(N_0\in\N\) such that, for every integer \(N\ge N_0\), there is a maximal Sidon set \(A\subseteq[1,N]\cap\Z\) satisfying \(|A|\le CN^{1/3}\). Equivalently, \(s(N)=O(N^{1/3})\). \end{theorem} The exponent is forced by a counting argument. \begin{proposition}\label{prop:lower} Every maximal Sidon set \(A\subseteq[1,N]\cap\Z\) satisfies \(|A|\ge(N/3)^{1/3}\). \end{proposition} \begin{proof} The case \(N=0\) is immediate. Otherwise put \(m=|A|\ge1\). For every \(x\in[1,N]\setminus A\), a nontrivial equality of pair sums in \(A\cup\{x\}\) must take one of the forms \[ x+a=b+c\quad\text{or}\quad 2x=a+b,\qquad a,b,c\in A. \] Indeed, equalities using \(x\) once on each side cancel to a trivial equality. Consequently the interval is contained in the union of \(A\), \(A+A-A\), and the set of integral midpoints of pairs from \(A\). Thus \(N\le m+m^3+m^2\le3m^3\). \end{proof} Together, Theorem~\ref{thm:main} and Proposition~\ref{prop:lower} give \(s(N)\asymp N^{1/3}\). The companion certificate proves the upper bound. \paragraph{Organization and notation.} For an integer \(z\) and a positive integer \(q\), let \(\res zq\in\{0,\ldots,q-1\}\) be its least nonnegative residue. For a real number \(u\), write \(\fracpart u=u-\floor u\). All intervals below are intersected with \(\Z\) when used as sets of marks. We first work in \([0,N)\) and translate by \(1\) at the end. A quadratic seed \(C_p\) supplies controlled differences. A finite alphabet of translates covers all nonmultiples of \(p\) 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 \(p\) remain available to a maximal completion. \section{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. \begin{lemma}[Affine sign patterns]\label{lem:signs} Let \(f_1,\ldots,f_q\) be affine real functions on \(\R^d\). The number of joint sign patterns, with each sign in \(\{-,0,+\}\), is at most \begin{equation} \big((d+2)(q+1)^{d+1}\big)^2. \end{equation} The same bound applies to any finite-valued label determined by these signs. \end{lemma} \begin{proof} Homogenize the affine functions on \(\R^{d+1}\). The family of their positive supports has VC dimension at most \(d+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 \cite{sauer,shelah} gives at most \[ \sum_{j=0}^{d+1}\binom qj\le(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. \end{proof} \begin{lemma}[Fractional-part tests]\label{lem:tests} Suppose a label is determined by \(t\) comparisons \[ \fracpart{f_i(v)}G \quad\text{whenever }\{i,j\}\ne\{k,l\}\text{ as multisets of labels}. \end{equation} \end{proposition} \begin{proof} Fix a positive integer \(\lambda\) with \(2\lambda-4>G\). For \(0\le i2M\), such a collision must have \(e\ne0\). Suppose both alphabets have a collision, with differences \((d_1,e_1)\) and \((d_2,e_2)\). Eliminating \(p\) gives \[ K\mid e_2d_1-e_1d_2,\qquad |e_2d_1-e_1d_2|\le4(M_1+M_2)(n+1)^3>N\), where \(n\ge2\) and \(K\ge1\). Finally \(p\ge n+1\) gives \(N