\documentclass[11pt,leqno]{amsart} \usepackage[letterpaper,margin=1in]{geometry} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{microtype} \linespread{0.985} \usepackage{xurl} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} \title[Erd\H{o}s Problem 12]{The three parts of Erd\H{o}s Problem 12:\\ counting functions and reciprocal sums} \author[W. Howe]{Will Howe} \author[G. Huffman]{Grant Huffman} \author[J. Kohlmeyer]{Jensen Kohlmeyer} \author[L. Kruer]{Liam Kruer} \thanks{\textit{E-mail.} \href{mailto:howew@purdue.edu}{\texttt{howew@purdue.edu}} (W. Howe), \href{mailto:huffma97@purdue.edu}{\texttt{huffma97@purdue.edu}} (G. Huffman), \href{mailto:jenwin@purdue.edu}{\texttt{jenwin@purdue.edu}} (J. Kohlmeyer), \href{mailto:kruerl@purdue.edu}{\texttt{kruerl@purdue.edu}} (L. Kruer).} \date{November 5, 2026} \subjclass[2020]{11B05, 11N35, 11N36} \keywords{Erd\H{o}s problems, reciprocal sums, divisibility, sieve methods, primitive sets} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\T}{\mathbb R/\mathbb Z} \newcommand{\E}{\mathbb E} \newcommand{\Prob}{\mathbb P} \newcommand{\ind}{\mathbf 1} \newcommand{\hrec}{\mathcal H} \newcommand{\Pmax}{P^{+}} \newcommand{\norm}[1]{\left\lVert #1\right\rVert} \newcommand{\abs}[1]{\left\lvert #1\right\rvert} \newcommand{\e}{\mathrm e} \newcommand{\eps}{\varepsilon} \hypersetup{ pdftitle={The three parts of Erdos Problem 12: counting functions and reciprocal sums}, pdfauthor={Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer}, pdfsubject={Erdos Problem 12, parts i, ii and iii}, pdfkeywords={reciprocal sums, divisibility, Property P, sieve methods} } \begin{document} \begin{abstract} We give a unified account of the three numbered questions in Erd\H{o}s Problem~12 for sets in which no element divides the sum of two distinct larger elements. The positive answer to the square-root counting question and the negative answer to a universal power-saving bound are prior AlphaProof Nexus results of Google DeepMind. We include attributed proofs following its released Lean constructions. For the reciprocal-sum question, we retain the proof that one absolute constant bounds the sum for every such set, finite or infinite. The distinction between parameterwise dense examples and the uniform reciprocal bound is made explicit. A companion single-file Lean formalization combines the two adapted prior proofs with the reciprocal-sum proof and checks all three statements together. \end{abstract} \maketitle \section{The three questions and their attribution}\label{sec:introduction} A set \(A\subseteq\N=\{1,2,\ldots\}\) has \emph{Property P} if there are no pairwise distinct elements \(a,b,c\in A\) such that \[ a0. \] \end{theorem} \begin{theorem}[Part (ii), AlphaProof Nexus]\label{thm:part-ii} There is no absolute \(c>0\) such that every infinite set \(A\) with Property P satisfies \(A(N)1\), with \(\Pmax(1)=1\). A set is \emph{primitive} if no two distinct members divide one another. Property P is inherited by subsets and by division by a common divisor. The paper uses positive integers; the Lean statements use natural numbers, with \(1/0=0\). The constructions below consist of positive integers. \section{The counting constructions: parts (i) and (ii)}\label{sec:counting} This section is an attributed exposition of the released proofs \cite{NexusI,NexusII}. We isolate the common congruence argument and then make the two choices of scale. Omitting finitely many initial blocks in the exposition simplifies the estimates and does not affect the asserted asymptotic statements. The Lean implementations verify explicit initial bounds as well. \begin{lemma}[Congruence separation]\label{lem:congruence-separation} Let \(B_j\) be finite sets of positive integers, with every element of \(B_i\) smaller than every element of \(B_j\) when \(i2\) such that elements of \(B_j\) are \(0\pmod{q_j}\) and \(1\pmod{q_i}\) for every \(i2\). Otherwise both larger elements lie in \(B_i\), and \(2a0\), so \(A(M_j)=\sum_{i0\) existed, apply the construction with \(c=\min(d,1/2)\). For sufficiently large \(N\ge1\), \(A_c(N)\ge N^{1-c}\ge N^{1-d}\), contradicting the required infinitely many strict inequalities. This proves Theorem~\ref{thm:part-ii}. \section{A restriction estimate for sifted integers}\label{sec:restriction} Let \(\mathcal P\) be any set of primes. Define a multiplicative function supported on squarefree products of primes in \(\mathcal P\) by \[ h_{\mathcal P}(1)=1,\qquad h_{\mathcal P}(d)=\prod_{p\mid d}\frac1{p-1}, \] and put \(h_{\mathcal P}(d)=0\) for all other positive integers \(d\). For \(z\ge2\), set \[ G_{\mathcal P}(z)=\sum_{d2\) and every complex sequence \((a_n)\) supported on \(\mathcal S(N,\mathcal P,z)\), \begin{equation}\label{eq:restriction} \left(\sum_{\xi\in\mathcal B} \left|\sum_{n\le N}a_n\e(n\xi)\right|^q\right)^{1/q} \ll_q \left(\frac{N+\delta^{-1}}{G_{\mathcal P}(z)} \sum_{n\le N}|a_n|^2\right)^{1/2}. \end{equation} The constant is uniform in \(\mathcal P\). \end{lemma} \begin{proof} We give the enveloping-sieve argument in the form needed here. For a parameter \(z_0\ge2\), let \(\mathcal P'=\mathcal P\cap[z_0,z)\), write \(h'=h_{\mathcal P'}\), and put \(G'=\sum_{d0}}u_d(n)\right)^2 \end{equation} equals 1 on \(\mathcal S(N,\mathcal P,z)\). Orthogonality and the Chinese remainder theorem show that its constant Fourier coefficient is \(1/G'\). A nonconstant Fourier coefficient can occur only at a reduced fraction \(a/\ell\), where \(\ell\eta, \qquad \left|\sum_{n\in\Z}\psi(n)\e(n\theta)\right| \ll N+\eta^{-1}. \] Use \(\psi\beta\) to majorize the dual square sum. The constant coefficient of \(\beta\) contributes only when \(\xi=\xi'\). For a fixed ordered pair \((\xi,\xi')\), at most one reduced nonzero fraction \(a/\ell\), \(\ell0\) and \(D_0\) with the following properties. If \(D\ge D_0\), \(N\ge D\), and \(z=\tfrac12\min\{D,N^{1/4}\}\), then \begin{equation}\label{eq:full-density} G_{\{\text{all primes}\}}(z)\gg\log D. \end{equation} If \(16\le K\le D^{c_0}\), then \begin{equation}\label{eq:band-density} G_{\{p>4K\}}(z)\gg\frac{\log D}{\log(2K)}. \end{equation} \end{lemma} \begin{proof} Put \(z_1=z^c\), where \(c>0\) is a sufficiently small absolute constant. In the Euler product \(\prod_{4K8K\) for all sufficiently large \(D\). Since \(\log z_1\gg\log D\), this proves \eqref{eq:band-density}. The same argument with all primes at most \(z_1\) proves \eqref{eq:full-density}. \end{proof} \section{Interaction between separated rough blocks}\label{sec:blocks} \begin{lemma}\label{lem:blocks} Let \(D\ge D_0\), let \(XK^{1/2}\), divide \(J\) into consecutive chunks of length at most \(d\). Within a chunk the frequencies \(k\lambda\) are separated by at least \(1/(2d)\), since \(d\le4K\ll X\). Apply Lemma~\ref{lem:restriction} to each chunk and then average over \(J\). This gives \[ |B(\xi)|\ll\frac{\sqrt u}{K}d^{-1/q} \ll\frac{\sqrt u}{K}K^{-1/(2q)}. \] In both cases with \(d\ge2\), the interval average defining \(B_0\) is bounded by \[ |B_0(\xi)|\ll\frac{\alpha d}{Y} \ll\frac{\alpha K}{Y}. \] This term is smaller than the right side of \eqref{eq:fourier-comparison}, after decreasing \(c_0\) if needed. It remains to consider \(d=1\). Use the lift of \(\lambda\) with \(|\lambda|\le1/(100X)\), and put \(\rho=M|\lambda|\). If \(\rho\ge K^{1/4}\), geometric summation gives \[ |B(\xi)|+|B_0(\xi)|\ll\alpha/\rho \ll\alpha K^{-1/4}. \] If \(\rhoa\) and \(a,x,y\) in the underlying set. Distinct \(x,y\) contradict Property P. If \(x=y\), then \(x=ka\), which is impossible because \(k\ge2\) is \(D\)-smooth and \(x\) is \(D\)-rough. Therefore \( c\alpha v^2\le C\alpha v u^{-1/2}K^{-1/8} \), which proves \eqref{eq:blocks}. \end{proof} \section{Prime sets with inherited congruence restrictions}\label{sec:prime-tail} We use the analytic large sieve and the Brun--Titchmarsh inequality in their classical forms \cite{MV,MVbook}. In particular, if a set of primes occupies at most \(\vartheta\varphi(m)\) reduced residue classes modulo \(m\), then, for a fixed \(a>1\), \(x\ge m^a\), \(x\ge2\), and \(y\ge x\), partial summation gives \begin{equation}\label{eq:BT-mass} \sum_{\substack{p\in Q\\x\le p\delta U/J^2\). Choose \[ s=\lceil8\log_2J\rceil \] distinct primes from that bin. This is possible for all sufficiently large \(Y\), by \eqref{eq:delta-lower}. Let \(L\) be \(M\) times their product, and set \[ V_0=U J^8\delta^{-8}. \] Choose \(A_0\) sufficiently large that, uniformly for \(U\ge Y/2\), \begin{equation}\label{eq:near-range} 4V_0/U\le(U/2)^{c_0} \end{equation} for all sufficiently large \(Y\). This follows from \eqref{eq:delta-lower}. The same range gives \(L>V_0\). \subsection*{The near range} Take \(D=U/2\). In dyadic bins meeting \([U,V_0]\), every prime is \(D\)-rough. The normalized count \[ w_V=\frac{\log D}{V}|Q\cap[V,2V)| \] is \(O(\delta)\), by \eqref{eq:bin-density}. If two such counts are at least \(w>0\), then Lemma~\ref{lem:blocks} bounds their ratio of scales by \(O(w^{-12})\), unless the scales differ by a factor less than 16. The hypotheses of that lemma hold throughout the range by \eqref{eq:near-range}. It follows that \[ \#\{V:w_V\ge w\}\ll1+\log(C/w). \] Integrating this bound over \(02U\). For every prime \(p\in Q\cap[U,2U)\), the set \(T\) occupies at most \((p-1)/2\) classes modulo \(p\). Orthogonality and Cauchy--Schwarz give \[ \sum_{j=1}^{p-1} \left|\sum_{t\in T}\e(jt/p)\right|^2 \ge |T|^2. \] The reduced fractions \(j/p\) belonging to different such primes are distinct and have spacing at least \(1/(4U^2)\). The analytic large sieve therefore gives \[ n|T|^2\ll(V+U^2)|T|, \qquad \hrec(T)\ll\frac1n+\frac{U^2}{Vn}. \] Summing over bins meeting \([V_0,L]\), including the at most two boundary bins, yields \begin{equation}\label{eq:middle-mass} \hrec(Q\cap[V_0,L]) \ll\frac{sJ^3}{\delta U}+\frac{\delta^7}{J^6} \ll\frac{\delta}{J}. \end{equation} For the first inequality use \(\log L=O(sJ)\) and \(n>\delta U/J^2\). For the second, divide by \(\delta/J\) and use \[ \frac{sJ^4}{\delta^2U}+\frac{\delta^6}{J^5}=o(1), \] uniformly in the permitted range, by \eqref{eq:delta-lower}. \subsection*{The far range} On \((L,L^2]\), use the external \(q_i\) and the \(\lfloor s/2\rfloor\) smallest selected internal primes as moduli. Their product is at most \(\sqrt{ML}\), hence at most \(L^{2/3}\) for sufficiently large \(Y\). The occupied fraction of reduced classes is at most \(\delta2^{-\lfloor s/2\rfloor}\). Equation~\eqref{eq:BT-mass} therefore bounds the mass in this range by \(O(\delta2^{-\lfloor s/2\rfloor})\). Enumerate the primes of \(Q\) above \(L^2\) as \(p_11\), the probability that \(g\) is a prefix product is \begin{equation}\label{eq:prefix-probability} \mu_g=\frac1g\prod_{p<\Pmax(g)}(1-1/p) \asymp\frac1{g\log(2\Pmax(g))}. \end{equation} \end{lemma} \begin{proof} Put \(r=\Pmax(g)\). For primes \(p1\) the score \[ W_g=\log(2\Pmax(g))\,\hrec(Q_g). \] Tonelli's theorem and \eqref{eq:prefix-probability} show that it is enough to prove \begin{equation}\label{eq:expected-score} \E\sum_{\substack{g>1\\g\text{ a prefix}}}W_g\ll1. \end{equation} Lemma~\ref{lem:prime-tail} with \(k=0\) gives \(W_g\ll1\). More precisely, if \(Q_g\ne\varnothing\) and \(p_g=\min Q_g\), then \begin{equation}\label{eq:score-basic} W_g\ll\frac{\log(2\Pmax(g))}{\log(2p_g)}. \end{equation} We reserve \(p_g\) for this least terminal prime and use \(r=\Pmax(g)\) for the prime coordinate of the prefix. We may omit scores produced by the second or a later copy of a prime. Their total expectation is bounded by \[ C\sum_p\E(V_p-1)_+ =C\sum_p\frac1{p(p-1)}<\infty. \] The omitted copies remain in the list and in all later prefix products. Scores at primes below any fixed absolute threshold also have bounded total expectation. Thus only the first copy at each sufficiently large prime coordinate needs to be considered. \begin{lemma}\label{lem:inheritance} Suppose \(h\) and \(g\) are prefix products on one path, \(h\) occurs earlier, \(Q_h,Q_g\ne\varnothing\), and \(\Pmax(g)>p_h\). Then the residues of \(Q_g\) occupy at most one class from each opposite pair of nonzero classes modulo \(p_h\). The terminal primes \(p_h\) from distinct nonempty prefixes on a path are distinct. \end{lemma} \begin{proof} We have \(h\mid g\). If \(p_h\mid g/h\), then \(hp_h\in A\) divides every \(gp\in A\), \(p\in Q_g\). These are distinct elements because \(\Pmax(g)>p_h\), contrary to primitivity. Thus \((g/h,p_h)=1\). All primes in \(Q_g\) exceed \(p_h\). For distinct \(p,p'\in Q_g\), the congruence \(p+p'\equiv0\pmod{p_h}\) would now imply \[ hp_h\mid gp+gp', \] with both summands larger than \(hp_h\), contradicting Property P. This proves the first assertion. If two distinct nested prefixes \(h_1\mid h_2\) had the same terminal prime \(p\), then the distinct elements \(h_1p,h_2p\in A\) would contradict primitivity. \end{proof} \section{An adapted summation of prefix scores}\label{sec:scheduling} We process every prime coordinate \(r\) in increasing order, including coordinates for which \(V_r=0\). At coordinate \(r\), reveal \(V_r\), retain all its copies in the prefix product, and score the first copy if \(V_r\ge1\). Let \(A_0\) be the exponent in Lemma~\ref{lem:prime-tail}. The following scheduling rule uses selected terminal primes as congruence moduli, which we call \emph{guards}. After \(k\) guards have been activated, write \(M\) for their product and \(\delta=2^{-k}\). A \emph{ready stage} starts at the first unprocessed prime at least \(R\), where \(R\ge M^{A_0}\) is determined by the previously revealed coordinates. Initially \(k=0\) and \(R\) is a fixed sufficiently large absolute threshold. A stage starts with no pending guard. At a scored prefix \(g\) with \(Q_g\ne\varnothing\), schedule \(p_g\), retaining the smallest pending prime. If the newly scheduled minimum equals the current coordinate, activate it immediately after scoring. A guard already pending when its coordinate is reached is activated before revealing that coordinate, so that the coordinate belongs to the delay described below. The stage ends on activation. Every finite pending prime is eventually reached, since all prime coordinates are processed. A ready stage that never activates therefore has no nonempty scored prefix. The guard selected in a completed stage arose from a previously visited prefix. Lemma~\ref{lem:inheritance} shows that the old guards impose the required opposite-class restrictions on every nonempty fibre in that ready stage. They are distinct and smaller than its current coordinate. At a nonempty scored prefix \(g\) with \(r=\Pmax(g)\), Lemma~\ref{lem:prime-tail}, applied with \(Y=p_g\ge r\), gives \begin{equation}\label{eq:score-guarded} W_g\ll \delta(1+k)\frac{\log r}{\log p_g}. \end{equation} The harmless factors 2 in \eqref{eq:score-basic} are absorbed by the fixed lower threshold for \(r\). \begin{lemma}\label{lem:ready-cost} Conditional on the history at the start of a ready stage with \(k\) active guards, the expected total score in that stage is \(O(2^{-k}(1+k))\). \end{lemma} \begin{proof} Call a change of the pending minimum \emph{large} if its logarithm decreases by a factor of at least 2. The first finite pending value is counted as large. At consecutive large changes, the ratio \(\log r/\log p_g\) at least doubles, since \(r\) increases and the pending logarithm halves. Every such ratio is at most 1 before activation. Thus the sum of these ratios over all large changes is at most 2 on every path. Their total score is bounded by \(C\delta(1+k)\), by \eqref{eq:score-guarded}. For all other nonempty scored prefixes, let \(P_{\rm old}\) be the pending prime known before revealing \(V_r\). Then \[ \frac{\log r}{\log p_g} \le2\frac{\log r}{\log P_{\rm old}}. \] Interpret the right side as zero when no finite prime is pending. In that case the first nonempty prefix has already been assigned to the large-change class. Both readiness at \(r\) and \(P_{\rm old}\) are measurable before \(V_r\) is revealed. A first-copy score at \(r\) can occur only if \(V_r\ge1\), an event of conditional probability \(1/r\). If \(P_*\) is the prime eventually activated, every ready coordinate is at most \(P_*\), and every previous finite pending value is at least \(P_*\). Consequently, pathwise, \begin{equation}\label{eq:predictable-budget} \sum_{\substack{r\text{ ready}\\P_{\rm old}<\infty}} \frac1r\frac{\log r}{\log P_{\rm old}} \le\frac1{\log P_*} \sum_{\substack{r\le P_*\\r\text{ prime}}} \frac{\log r}{r} \ll1. \end{equation} For a stage without activation the sum is zero. Taking conditional expectation before each coordinate, and then applying Tonelli, proves the same \(O(\delta(1+k))\) bound for all remaining scores. \end{proof} After activating \(P_*\), put \(M_{\rm new}=MP_*\). Process the remaining coordinates below \(M_{\rm new}^{A_0}\) as a \emph{delay}, then start the next ready stage at the first unprocessed prime at least that threshold. The old guards remain valid throughout the delay. \begin{lemma}\label{lem:delay-cost} Conditional on the activation history, the expected total score in the delay is \(O(2^{-k}(1+k))\). \end{lemma} \begin{proof} Equation~\eqref{eq:score-guarded} bounds every scored prefix during the delay by \(C\delta(1+k)\), using \(\log r/\log p_g\le1\) and the old guards. Moreover \(M^{A_0}\le R\le P_*\), so \[ M_{\rm new}^{A_0} =(MP_*)^{A_0}\le P_*^{A_0+1}. \] Conditional on the activation history, all strictly later prime coordinates retain their independent geometric laws. Their expected number of first copies before the next ready stage is at most \[ \sum_{\substack{P_*1\\g\text{ a prefix}}}W_g \ll1+\sum_{k\ge0}2^{-k}(1+k)<\infty. \] Equation~\eqref{eq:expected-score}, Lemma~\ref{lem:prefix-probability}, and the decomposition \eqref{eq:fibre-decomposition} complete the proof. \end{proof} \section{Completion of the proof}\label{sec:completion} \begin{proof}[Proof of Theorem~\ref{thm:main}] It is enough to bound \(\hrec(B)\) uniformly for finite sets \(B\) with Property P. Let \(C\subseteq B\) consist of the elements minimal under divisibility. Every \(b\in B\setminus C\) has a proper divisor in \(C\). Assign \(b\) to one such divisor \(c\). No \(c\) receives two distinct elements, since it would divide their sum and both would exceed it. Every assigned \(b\) is at least \(2c\). Hence \begin{equation}\label{eq:primitive-reduction} \hrec(B)\le\frac32\hrec(C). \end{equation} The set \(C\) is primitive. For \(v\ge0\), define \[ C_v=\{c/2^v:c\in C,\ v_2(c)=v\}. \] Each \(C_v\) is an odd primitive set with Property P. Proposition~\ref{prop:odd-primitive} supplies one constant \(C_{\rm odd}\) bounding all their reciprocal sums, including the possible singleton \(\{1\}\). Therefore \[ \hrec(B)\le\frac32\sum_{v\ge0}2^{-v}\hrec(C_v) \le3C_{\rm odd}. \] This bound is independent of \(B\). Apply it to the finite truncations of an arbitrary \(A\), and use monotone convergence to obtain \eqref{eq:main}. \end{proof} \section{An explicit finite prefix bound}\label{sec:finite-prefix} We give a finite formulation of the argument in Section~\ref{sec:scheduling}, with explicit bounds for the total expected score. Fix an odd primitive set \(B\subseteq[2,N]\) with Property P. In this section, the fibres \(Q_g\) and scores \(W_g\) are defined using \(B\) in place of \(A\). Independently for each prime \(p\le N\), choose \(X_p\in\{0,1,\ldots,N+1\}\) with \[ \Prob(X_p=j)=(1-1/p)p^{-j}\quad(0\le j0\) such that \(\sum_{p\le x}(\log p)/p\le C_{\log}\log x\) for \(x\ge2\). The weighted prime sum and the monotonicity of the pending minimum imply \begin{equation}\label{eq:finite-prime-potential} \ind_{\{r\text{ prime}\}}\frac{U_r}{r} \le T_{r+1}-T_r+C_{\log}a_r. \end{equation} Indeed, without activation the increment of the numerator accounts for \((\log r)/r\), and a decrease of the denominator increases the potential. At an activation, the numerator through time \(r\) is at most \(C_{\log}\log P\), so the lost potential together with the current summand is at most \(C_{\log}w_{k_r}\). Every terminal prime of a nonempty fibre is at most \(N\). Hence no prime is pending after time \(N\), and both potentials begin and end at zero. Summing \eqref{eq:finite-prime-potential} and using \eqref{eq:finite-activation} gives \[ \sum_{r=1}^N\E\left[\ind_{\{X_r\ge1\}}U_r\right] \le4C_{\log}. \] Summation of \eqref{eq:finite-ready-charge} now bounds the expected ready contribution by \begin{equation}\label{eq:finite-ready-total} C_{\rm tail}(32+16C_{\log}). \end{equation} \subsection{The delayed coordinates} Suppose that the latest activation was at a prime \(P\), with \(j\) guards active before that activation and old product \(M\). Put \(H=(MP)^{A_0}\). The inequality \(M^{A_0}\le P\) gives \(H\le P^{A_0+1}\). Mertens' estimate supplies an absolute constant \(C_{\rm delay}>0\), depending only on the fixed \(A_0\), such that \[ \sum_{\substack{P\le p