\documentclass[11pt]{amsart} \usepackage[letterpaper,margin=1in,headheight=14pt]{geometry} \usepackage{amsmath,amssymb} \usepackage[hidelinks]{hyperref} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} \newcommand{\N}{\mathbb N_0} \newcommand{\E}{\mathcal E} \newcommand{\triples}{\mathcal T} \title[Non-unique sums and Erd\H{o}s problem 14]{A uniform square-root lower bound for non-unique sums and a resolution of Erd\H{o}s problem 14} \author{Liam Kruer} \email{kruerl@purdue.edu} \author{Jensen Kohlmeyer} \email{jenwin@purdue.edu} \date{September 13, 2026} \subjclass[2020]{Primary 11B34; Secondary 11B13, 68V20} \keywords{Unique sums, additive representation functions, exceptional sets, Erd\H{o}s problem 14, formal proof, Lean} \begin{document} \begin{abstract} For a set \(A\subseteq\N\), let \(E_A(N)\) count the positive integers at most \(N\) that do not have exactly one unordered representation as a sum of two elements of \(A\), with equal summands allowed. We prove the uniform estimate \(E_A(N)>\sqrt{N}/12000\) for every integer \(N\ge 2\cdot10^{24}\). This answers both questions in Erd\H{o}s problem 14: part I holds with exponent \(1/2\), and the existence assertion in part II is false. The common finite estimate is \(E_A(2T^4)>T^2/1000-1\) for every integer \(T\ge10^6\). Its proof combines a triple-sum moment identity, pair counting in an arithmetic progression, and two incompatible estimates for a finite generating polynomial. We give the shared argument once and describe the two accompanying Lean proof files and the scope of their reported local verification. \end{abstract} \maketitle \section{Introduction and main results} For \(A\subseteq\N=\{0,1,2,\ldots\}\) and integers \(n,N\ge0\), define \begin{equation} \begin{aligned} r_A(n)&=|\{(a,b)\in A^2:a\le b,\ a+b=n\}|,\\ E_A(N)&=|\{1\le n\le N:r_A(n)\ne 1\}|. \end{aligned} \end{equation} The first function counts unordered pairs, including diagonal pairs \((a,a)\). An exceptional integer has either no representation or more than one unordered representation. These conventions agree with the exceptional counting function in the Formal Conjectures formulation \cite{fc}. The set \(A\) may be finite or infinite. Erd\H{o}s discussed this counting function in connection with a problem of Erd\H{o}s and Nathanson \cite[pp.~43--44]{erdos}. The two questions recorded as Erd\H{o}s problem 14 ask whether \begin{align} N^{1/2-\varepsilon}&= O(E_A(N))\quad(N\to\infty) &&\text{for every \(A\) and every \(\varepsilon>0\)},\\ E_A(N)&=o(\sqrt N)\quad(N\to\infty) &&\text{for some \(A\subseteq\N\)}. \end{align} All asymptotic statements here are taken along positive integers. We answer the first question affirmatively and the second negatively by proving one uniform lower bound. \begin{theorem}\label{thm:uniform} For every \(A\subseteq\N\) and every integer \(N\ge2\cdot10^{24}\), \begin{equation}\label{eq:uniform} \sqrt N<12000\,E_A(N). \end{equation} \end{theorem} \begin{corollary}[Part I]\label{cor:i} For every \(A\subseteq\N\) and every real \(\varepsilon>0\), one has \(N^{1/2-\varepsilon}=O(E_A(N))\) as \(N\to\infty\). The constant \(12000\) and threshold \(2\cdot10^{24}\) work simultaneously for all \(A\) and \(\varepsilon\). \end{corollary} \begin{corollary}[Part II]\label{cor:ii} There is no set \(A\subseteq\N\) for which \(E_A(N)=o(\sqrt N)\). More precisely, every \(A\subseteq\N\) satisfies \begin{equation}\label{eq:liminf} \liminf_{N\to\infty}\frac{E_A(N)}{\sqrt N}\ge \frac{1}{12000}. \end{equation} \end{corollary} The numerical constants are chosen to simplify the estimates; no optimality is asserted. The main finite result is the following. \begin{theorem}\label{thm:finite} For every \(A\subseteq\N\) and every integer \(T\ge10^6\), \begin{equation} E_A(2T^4)>\frac{T^2}{1000}-1. \end{equation} \end{theorem} Sections 2--5 prove Theorem~\ref{thm:finite}. The structural step is a first-moment identity for triple sums: for targets whose relevant pair sums are uniquely represented, a unique weighted representation \(n=a+2b\) constrains \(3b\) to a single congruence class while the prefix \(A\cap[0,n]\) stays fixed. Pair counting then shows that almost every target has at least two weighted representations. This contradicts an upper bound for \(F(z)F(z^2)\), where \(F\) is a finite generating polynomial. Section 6 passes to every sufficiently large scale and derives both answers. \section{Pair counting and the finite scale} All intervals in counting expressions are intersected with \(\N\). For finite sets \(U,V\subseteq\N\), write \(U+V=\{u+v:u\in U,\ v\in V\}\). For a positive integer \(d\), the notation \(dU=\{du:u\in U\}\) denotes dilation. For finite \(B\subseteq\N\), put \[ R_B(n)=|\{(a,b)\in B^2:a+b=n\}|. \] Unlike \(r_A\), the function \(R_B\) counts ordered pairs. \begin{lemma}\label{lem:pairs} Let \(B,V,\mathcal F\) be finite sets of nonnegative integers, and let \(m\ge0\). Suppose that \(B+B\subseteq V\), \(|\mathcal F|\le m\), and \(R_B(n)\le2\) whenever \(n\notin\mathcal F\). If \(t=|B|\), then \begin{equation}\label{eq:pairs} t^2\le 2|V|+mt. \end{equation} If \(L\ge0\) and, in addition, \(B\subseteq[0,L]\) lies in a single residue class modulo an integer \(q>0\), then \begin{equation}\label{eq:progression} t^2\le 4\lfloor L/q\rfloor+2+mt. \end{equation} \end{lemma} \begin{proof} For every \(n\), the first coordinate of an ordered pair determines the second, so \(R_B(n)\le t\). Summing over \(V\setminus\mathcal F\) and \(V\cap\mathcal F\) gives \[ t^2=\sum_{n\in V}R_B(n)\le2|V\setminus\mathcal F|+t|V\cap\mathcal F|\le2|V|+mt. \] For the second assertion, choose the residue representative \(0\le rm+L\) would give \(t(t-m)\ge(t-m)^2>L^2\), a contradiction. Fix \(A\subseteq\N\) and an integer \(T\ge10^6\), and set \begin{equation} \begin{gathered} X=T^4,\qquad S=A\cap[0,X],\qquad k=|S|,\\ \E=\{0\le n\le2X:r_A(n)\ne1\},\qquad m=|\E|. \end{gathered} \end{equation} We shall prove \(1000m>T^2\). Until the contradiction in Section 5, assume \begin{equation}\label{eq:assume} 1000m\le T^2. \end{equation} For every \(n\in\N\setminus\E\), one has \(R_S(n)\le2\). For \(n\le2X\) this follows from uniqueness of the unordered representation in \(A\); for \(n>2X\) there are no representations from \(S\). Lemma~\ref{lem:pairs} therefore gives \[ k^2\le4X+2+mk\le(2T^2+1)^2+mk. \] By \eqref{eq:quadratic} and \eqref{eq:assume}, \begin{equation}\label{eq:k} k\le m+2T^2+1\le3T^2. \end{equation} For integers \(0\le n\le X\), define the prefix and its statistics by \begin{equation} S_n=A\cap[0,n],\qquad K_n=|S_n|,\qquad H_n=\sum_{a\in S_n}a. \end{equation} Every integer in \([0,n]\setminus\E\) is a sum of two members of \(S_n\). Since there are \(K_n^2\) possible ordered pairs and at most \(m\) exceptions, \begin{equation}\label{eq:prefix} n+1\le K_n^2+m. \end{equation} \begin{lemma}\label{lem:prefix} Under assumption \eqref{eq:assume}, every integer \(n\) with \(X/10000,\qquad K_n+1\ge T^2/32. \end{equation} \end{lemma} \begin{proof} If \(K_n+11\), which also gives \(K_n>0\). \end{proof} \section{A triple-sum moment identity} Introduce the weighted representation function \begin{equation} g(n)=|\{(a,b)\in S^2:a+2b=n\}|. \end{equation} Call a nonnegative integer \(n\) \emph{clean} if \(n\notin S+\E\). There are at most \(km\) integers which are not clean. If \(n\le X\) is clean and \(a\in S_n\), then \(0\le n-a\le X\) and \(n-a\notin\E\). Otherwise \(n=a+(n-a)\) would belong to \(S+\E\). Consequently \(n-a\) has a unique unordered representation as a sum of two elements of \(A\), and both summands lie in \(S_n\). For \(0\le n\le X\), put \[ \triples_n=\{(a,b,c)\in S_n^3:a+b+c=n\},\qquad B_n=\sum_{\substack{a,b\in S\\a+2b=n}}b. \] The symbol \(B_n\) denotes a sum of integers, not a set. All pairs counted by \(g(n)\) belong to \(S_n^2\), by nonnegativity. \begin{lemma}[Triple-sum identity]\label{lem:moment} For every clean target \(0\le n\le X\), \begin{equation}\label{eq:moment} 3H_n+3B_n=n(K_n+g(n)). \end{equation} \end{lemma} \begin{proof} Fix the first coordinate \(a\in S_n\). The unique unordered pair representing \(n-a\) contributes two ordered triples unless its entries coincide, in which case it contributes one. A diagonal pair is exactly a solution of \(a+2b=n\). Thus \begin{equation}\label{eq:ordered-triples} |\triples_n|=2K_n-g(n),\qquad \sum_{(a,b,c)\in\triples_n}a=2H_n-\sum_{\substack{a,b\in S\\a+2b=n}}a. \end{equation} The set \(\triples_n\) is invariant under permutations of its three coordinates. The three coordinate sums are therefore equal, and their sum is \(n|\triples_n|\). Hence \begin{equation}\label{eq:sum-coordinates} 3\sum_{(a,b,c)\in\triples_n}a=n|\triples_n|. \end{equation} Also, \[ \sum_{\substack{a,b\in S\\a+2b=n}}a=ng(n)-2B_n. \] Substitution in \eqref{eq:ordered-triples}--\eqref{eq:sum-coordinates} gives \[ 6H_n-3ng(n)+6B_n=2nK_n-ng(n). \] Rearranging and dividing by \(2\) proves \eqref{eq:moment}. \end{proof} The diagonal correction in \eqref{eq:ordered-triples} is essential. The argument includes triples with all three coordinates equal and uses no distinctness assumption. \section{Few targets have at most one weighted representation} As \(n\) runs from \(0\) to \(X\), the sets \(S_n\) are nested and take at most \(k+1\) distinct values. Fix one such prefix, and consider clean targets \(X/10000\) and \(q\ge T^2/32\). If \(g(n)=0\), then \(B_n=0\) and \eqref{eq:moment} becomes \(3H=nK\). Since \(K>0\), at most one target with this prefix has \(g(n)=0\). If \(g(n)=1\), let \((a,b)\) be its unique weighted pair. Then \(B_n=b\), so \begin{equation} 3H+3b=nq. \end{equation} As \(q>0\), distinct targets yield distinct values of \(b\). Moreover, all corresponding integers \(3b\) are congruent to \(-3H\) modulo \(q\). \begin{lemma}\label{lem:single} Under assumption \eqref{eq:assume}, for each fixed prefix there are at most \(m+20T\) clean targets \(X/10004\), one has \(z^{-1}=(1-4/X)^{-1}\ge1+4/X\). Bernoulli's inequality gives \[ z^{-X}\ge(1+4/X)^X\ge1+X(4/X)=5, \] so \(z^X\le1/5\). Consequently, \[ 2\sum_{n=0}^{X-1}z^n=\frac{2(1-z^X)}{1-z}=\frac X2(1-z^X)\ge\frac{2X}{5}. \] Insert this and \(D\le X/100\) in \eqref{eq:lower-partial} to obtain \[ F(z)F(z^2)\ge\frac{2X}{5}-\frac{2X}{100}=\frac{19X}{50}. \] \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:finite}] If \(1000m\le T^2\), Lemmas~\ref{lem:upper} and \ref{lem:lower} would imply \[ \frac{38X}{100}\le F(z)F(z^2)<\frac{37X}{100}, \] which is impossible. Hence \(m>T^2/1000\). The count \(m\) includes the possible exception at \(0\), whereas \(E_A(2T^4)\) counts only positive integers. Thus \(m\le E_A(2T^4)+1\), and \[ E_A(2T^4)\ge m-1>\frac{T^2}{1000}-1. \] \end{proof} \section{All large scales and the two answers} \begin{proof}[Proof of Theorem~\ref{thm:uniform}] Let \(N\ge2\cdot10^{24}\) and choose \[ T=\left\lfloor (N/2)^{1/4}\right\rfloor. \] Then \(T\ge10^6\) and \[ 2T^4\le N<2(T+1)^4\le32T^4. \] In particular, \(\sqrt N<6T^2\). The function \(E_A\) is nondecreasing because its defining sets are nested. By Theorem~\ref{thm:finite}, \[ E_A(N)\ge E_A(2T^4)>\frac{T^2}{1000}-1\ge\frac{T^2}{2000}>\frac{\sqrt N}{12000}. \] The middle inequality uses \(T^2\ge2000\). \end{proof} \begin{proof}[Proof of Corollary~\ref{cor:i}] For \(N\ge1\) and \(\varepsilon>0\), one has \(N^{1/2-\varepsilon}\le\sqrt N\). Theorem~\ref{thm:uniform} gives \(N^{1/2-\varepsilon}\le12000E_A(N)\) for every \(N\ge2\cdot10^{24}\), which is the asserted big-\(O\) estimate. \end{proof} \begin{proof}[Proof of Corollary~\ref{cor:ii}] Dividing \eqref{eq:uniform} by \(12000\sqrt N\) and taking the lower limit proves \eqref{eq:liminf}. Since \(E_A(N)\ge0\), the assertion \(E_A(N)=o(\sqrt N)\) would mean that for every \(c>0\) there is an integer \(N_0\) such that \(E_A(N)\le c\sqrt N\) for all \(N\ge N_0\). Taking \(c=1/24000\) contradicts \eqref{eq:uniform} as soon as \(N\ge\max\{N_0,2\cdot10^{24}\}\). \end{proof} \begin{remark}[Direct finite-scale proof of the negative answer] The nonexistence assertion also follows directly from Theorem~\ref{thm:finite}, as in the accompanying Lean proof for part II. If \(E_A(N)=o(\sqrt N)\), choose \(N_0\) with \(E_A(N)\le\sqrt N/4000\) for \(N\ge N_0\). Choose an integer \(T\ge10^6\) such that \(2T^4\ge N_0\). Then \[ E_A(2T^4)\le\frac{\sqrt{2T^4}}{4000}\le\frac{T^2}{2000},\qquad E_A(2T^4)>\frac{T^2}{1000}-1\ge\frac{T^2}{2000}, \] a contradiction. Thus both answers rest on the same finite obstruction, and the uniform theorem strengthens both asymptotic conclusions. \end{remark} \section{Lean formalization and verification scope} The two source manuscripts \cite{source-i,source-ii} identify separate proof files: \texttt{Erdos14\_PartI.lean} for part I and \texttt{Erdos14\_PartII\_Counterexample.lean} for the negative answer to part II. Copies with these names were available when preparing the unified manuscript. Their shared core proof bodies are identical. Each includes its helper lemmas in the namespace \texttt{Erdos14Verification}. The task wrapper supplies the imports of the Erd\H{o}s 14 source and \texttt{TaskSupport}, together with the enclosing namespace \texttt{Bounty}. The final declarations in the two files have the respective target types \begin{verbatim} theorem target : fcTypeOfName% "Erdos14.erdos_14.parts.i" \end{verbatim} and \begin{verbatim} theorem target : Not (fcTypeOfName% "Erdos14.erdos_14.parts.ii") \end{verbatim} The second file writes \texttt{Not} with Lean's usual negation symbol. For the affirmative-answer target described in the original verification reports, the first source type expresses True if and only if the assertion in part I holds. The second expresses True if and only if the existence assertion in part II holds. Accordingly, the part I submission proves its target, and the part II submission proves the negation of its target. The part II result is the nonexistence statement of Corollary~\ref{cor:ii}. Table~\ref{tab:correspondence} records the correspondence between the mathematical argument and the principal declarations present in the files. The part I scale selection uses two integer square roots in place of an analytic fourth root. The part II file follows the direct finite-scale argument. \begin{table}[ht] \small \centering \caption{Proof components and Lean declarations. The common helper namespace is omitted.} \label{tab:correspondence} \begin{tabular}{@{}ll@{}} \hline Mathematical component&Lean declaration\\ \hline Lemma~\ref{lem:pairs}: pair and progression bounds& \texttt{pair\_count\_bound}, \texttt{progression\_pair\_count}\\ Lemma~\ref{lem:moment}: triple-sum identity&\texttt{clean\_triple\_moment}\\ Proposition~\ref{prop:low}: low-target count&\texttt{low\_targets\_density}\\ Polynomial contradiction&\texttt{finite\_obstruction}\\ Theorem~\ref{thm:finite}: finite estimate for \(A\)&\texttt{set\_scale\_obstruction}\\ Theorem~\ref{thm:uniform}: uniform bound&\texttt{uniform\_sqrt\_bound}\\ Corollary~\ref{cor:i}: affirmative answer&\texttt{part\_i\_positive}\\ Corollary~\ref{cor:ii}: nonexistence assertion&\texttt{part\_ii\_negative}\\ \hline \end{tabular} \end{table} \paragraph{Reported verification.} The source manuscripts report successful compilation with Lean 4.33.1 and mathlib \cite{mathlib} at revision \begin{center} \texttt{0df444a360eaa60ab8c11dca51a86af692955474}. \end{center} They identify the audited Formal Conjectures revision as \begin{center} \texttt{8432eac998110a563e03df65a28c117e97c8c142}, \end{center} and the validator \cite{validator} revision as \begin{center} \texttt{076ead3c71c8b0bfc0641975076d95015d075ce3}. \end{center} The reported local checks compiled the trusted wrapper, compared the target types and referenced statement constants against the pinned challenge, checked axiom dependencies, and replayed the exported proof declarations into an empty Lean environment. According to those reports, each final theorem depends only on \texttt{propext}, \texttt{Classical.choice}, and \texttt{Quot.sound}, with no dependency on \texttt{sorryAx}, an unproved source conjecture, or a \texttt{native\_decide} certificate. \paragraph{Public verification records.} The unified manuscript describes these checks as reported local verification. The prize submission \cite{prize} also links separate production verification records for part I \cite{public-i} and part II \cite{public-ii}, certified on September 16, 2026, and the pinned original-source edition and local verification reports \cite{pinned}. The mathematical proof in Sections 2--6 is self-contained and independent of the submission infrastructure. \section*{Acknowledgments} OpenAI's Codex assisted substantially in developing the argument, constructing and checking the Lean formalization described in the source manuscripts, and preparing the unified manuscript. The authors are responsible for the final mathematical content. We acknowledge the Lean and mathlib communities and the maintainers of Formal Conjectures and Conjectures.io for the libraries and verification infrastructure used in this work. \begin{thebibliography}{10} \bibitem{erdos} P.~Erd\H{o}s, Some of my forgotten problems in number theory, \emph{Hardy--Ramanujan J.} 15 (1992), 34--50. \href{https://hrj.episciences.org/125/pdf}{Journal PDF}. \bibitem{fc} The Formal Conjectures contributors, Formal Conjectures: Erd\H{o}s problem 14, Lean source file \texttt{FormalConjectures/ErdosProblems/14.lean}. \href{https://github.com/google-deepmind/formal-conjectures}{Repository}. The reported revision is given in Section 7. \bibitem{mathlib} The mathlib Community, The Lean mathematical library, \emph{Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020)}, ACM, 2020, 367--381. \href{https://doi.org/10.1145/3372885.3373824}{DOI}. \bibitem{validator} Conjectures.io, Conjectures validator, \href{https://github.com/conjectures-io/conjectures-validator}{source repository}. The reported revision is given in Section 7. \bibitem{source-i} L.~Kruer and J.~Kohlmeyer, A uniform square-root lower bound for non-unique sums, source manuscript, September 13, 2026, 7 pp., accompanying file \texttt{Erdos14\_PartI.lean}. \bibitem{source-ii} L.~Kruer and J.~Kohlmeyer, A negative answer to Erd\H{o}s problem 14, part II, source manuscript, September 13, 2026, 7 pp., accompanying file \texttt{Erdos14\_PartII\_Counterexample.lean}. \bibitem{prize} \href{https://github.com/TheJustinSunPrize/awards/pull/4902}{Justin Sun Prize submission JSP-000052}, with \href{https://github.com/lkruer/conjectures/blob/e88dec4c88e42824b4acd3f9559febe67115471b/problems/erdos-14/paper/proof.pdf}{unified manuscript PDF}. \bibitem{public-i} Conjectures.io, \href{https://conjectures.io/results/dce3d778-6f52-4c27-8da0-c82d2f391b64}{Erd\H{o}s problem 14, part i, production verification record}. \bibitem{public-ii} Conjectures.io, \href{https://conjectures.io/results/adb53fba-0b01-4398-abab-cb9b2176eebc}{Erd\H{o}s problem 14, part ii, production verification record}. \bibitem{pinned} \href{https://github.com/JENW1N/complete-math-solutions/tree/a624e9de77e0bd8868e7103f8b379f9dbd86b607}{Pinned original-source edition}. Local verification reports for \href{https://github.com/JENW1N/complete-math-solutions/blob/a624e9de77e0bd8868e7103f8b379f9dbd86b607/verification/erdos14i.json}{part i} and \href{https://github.com/JENW1N/complete-math-solutions/blob/a624e9de77e0bd8868e7103f8b379f9dbd86b607/verification/erdos14ii.json}{part ii}. \end{thebibliography} \end{document}