\documentclass[11pt,reqno]{amsart} \usepackage{amssymb,mathtools} \usepackage{newtxtext,newtxmath} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pdfencoding=auto]{hyperref} \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{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\Prb}{\mathbb P} \newcommand{\E}{\mathbb E} \newcommand{\NS}{\mathrm{NS}_{\omega_1}} \newcommand{\ZFC}{\mathrm{ZFC}} \newcommand{\Con}{\operatorname{Con}} \newcommand{\dd}{\,\mathrm d} \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 17, 2026} \thanks{AI tools assisted with developing and checking arguments and with drafting this manuscript.} \emergencystretch=2em \setlength{\textwidth}{446.4bp} \setlength{\oddsidemargin}{\dimexpr82.8bp-1in\relax} \setlength{\evensidemargin}{\oddsidemargin} \addtolength{\topmargin}{-33.3bp} \addtolength{\textheight}{44.6bp} \hypersetup{pdfauthor={Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer},pdftitle={Sharp Growth and Gap Exponents for Admissible Sequences}} \title[Growth of admissible sequences]{Sharp growth and gap exponents for admissible sequences} \subjclass[2020]{Primary 11B13. Secondary 11B25, 11P70.} \keywords{Erd\H{o}s problem, admissible sets, subset sums, generalized arithmetic progressions} \begin{document} \begin{abstract} An increasing sequence of positive integers is admissible if any two finite subsets with the same sum have the same cardinality. We solve the growth and consecutive-gap questions of Deshouillers and Erd\H{o}s. The least possible exponent in an eventual polynomial bound on the \(n\)-th term is \(2+2\sqrt 2\). The least possible consecutive-gap exponent is \((5+\sqrt{17})/2\). Both endpoints are attained with little-\(o\) bounds, and the endpoint gap bound holds with coefficient one at every index. We also determine the tradeoff when both bounds are imposed on the same sequence. The lower bounds use subset-sum counts, a restricted-sum progression theorem, and an elementary large-gap lemma. The upper bounds use an induction on congruences of signed subset sums. \end{abstract} \maketitle \section{Introduction} Following Deshouillers and Erd\H{o}s \cite{Erdos,Bloom}, call \(A=\{a_1\frac14\sum_{i\le j-3}a_i \] at infinitely many indices \(j\). In addition, \(a_{n+1}/a_n\) cannot tend to \(1\). \end{lemma} \begin{proof} First consider two unbounded sets \(X,Y\) of nonnegative integers containing zero, with gaps bounded by \(P_0,Q_0\), respectively. Suppose functions \(f,g\) on these sets vanish at zero and \(f(x)+g(y)\) depends only on \(x+y\). Then \(k(y-x)=g(y)-f(x)\) is well defined on \(Y-X\). For adjacent \(x\sum_{i\sum_{i\le j-2}b_i\ \ge\ \frac12\sum_{i\le\ell-4}a_i . \] For the second inequality, pair each term of the other parity with the next term of the chosen parity up to \(\ell-4\). One of the two adjacent gaps is at least half of this two-step increment. Its left index is \(\ell-2\) or \(\ell-1\), which proves the claimed strict bound. If \(a_{n+1}/a_n\to1\), both parity ratios tend to one, so the two preceding terms of each parity eventually have sum greater than its next term. This would give bounded deficits for both parities. \end{proof} \section{Counts in the early part of the sequence} Suppose \(a_n\ll n^p\), \(\Delta_n\ll n^c\), where \begin{equation}\label{eq:parameter-range} 4.55\le c\le p_*,\qquad c\le p\le c+1,\qquad p\le5.562 . \end{equation} Set \(B=p+1\), \(S_n=\sum_{i\le n}a_i\), \(S_0=0\), and let \(T(x)\) be the largest \(n\) with \(S_n\le x\). Write \(Z(n)\) for the number of all subset-sum values on the first \(n\) terms, \(F(n)\) for the largest size of a single cardinality layer there, and \(W(n)\) for the size of the layer with cardinality \(\lfloor n/2\rfloor\). We have \(Z(n)\le S_n+1\) and \(F(n)\ge Z(n)/(n+1)\). The caps imply \(S_n\ll n^B\). They also imply \begin{equation}\label{eq:slope} a_n^2\ll S_n n^c,\qquad S_{n+1}\ll S_n+(n+1)^c . \end{equation} For the first inequality, \(\gg\max\{1,a_n/n^c\}\) of the last terms up to \(n\) are at least \(a_n/2\), by summing the gap bound backwards and using \(a_n\ll n^{c+1}\). The second follows from \(a_{n+1}\le a_n+O(n^c)\). \begin{lemma}\label{lem:cutoff} If \(W(n)\gg(n+1)^u\) for \(2\le u\le c-1\), then \(Z(n)\gg(n+1)^{u+1}\). For every fixed \(v0\), we have \(F(T(x))\gg x^v\) for \(x\ge1\). \end{lemma} \begin{proof} Append one subset of each available cardinality from the second half of the first \(n\) terms to the middle layer of the first half. These families are disjoint by admissibility, proving the assertion about \(Z\). Put \(U=u+1\). The estimate for \(S_n\) gives \(Z(T(x))\gg x^{U/B}\). Suppose \(Z(T(x))\gg x^w\), where \(w<1\). For \(8\le H\le a_n\), let \(k(H)\) count the terms at least \(H\) among the first \(n\). The sum set through \(T(H/8)\) lies in \([0,H/8]\) and uses none of these \(k(H)\) terms. Shift it by their \(k(H)+1\) cumulative sums. The shifts are spaced by at least \(H\), so \(Z(n)\gg (k(H)+1)H^w\). Integration yields \(S_n\ll Z(n)a_n^{1-w}\). The integral below \(H=8\) is \(O(n)\), absorbed by \(Z(n)\ge n+1\). By \eqref{eq:slope} it follows that \[ S_n\ll Z(n)^{2/(1+w)}n^{c(1-w)/(1+w)}. \] At \(n=T(x)\) we have \(x0\). An ordinary subprogression of \(\mathcal P\) of step \(g\) and length \(L\ge2\) protects the preceding prefix through \(m\asymp(gL)^{1/B}\), where a fixed small multiplier ensures \(m\le n/4\) and \(S_m\le g(L-1)\). If two subset sums from this prefix agree modulo \(g\), their difference is realized by subtracting two values of the ordinary progression. The signed relation on the disjoint supports forces equal cardinalities. Take \[ t=\min\{T(g/4),\lfloor m/4\rfloor\}. \] An early layer through \(t\) has values distinct modulo \(g\). Padding it with one subset of each size from the next \(m-t\) terms gives disjoint residue families. In the uncapped case Lemma~\ref{lem:cutoff} gives \(g\gg m g^v\). In the capped case \(W(t)\gg m^u\) gives \(g\gg m^{u+1}\). In particular \begin{equation}\label{eq:capacity} L\ll g^\mu,\qquad \mu\ge B/(u+1)-1 . \end{equation} The last comparison follows from \(p-Bu/c-[B/(u+1)-1]=Bu(c-u-1)/(c(u+1))\ge0\). Bounded spans are covered by increasing the constant. If the rank is one, use a progression of length \(L\asymp n^2\); a rank-two box with a side of length one also provides it. Its step obeys \(g\ll n^{p-1}\), so \(m\gg g^{1/(p-1)}\). Because \(p-1\le c\), the capped case still supplies an early layer of size \(\gg g^v\). Equation~\eqref{eq:capacity} now gives \(g\gg n^{2/\mu}\). Adding that early layer to the progression gives disjoint translates. Padding to the middle layer uses available indices outside both supports. This proves \begin{equation}\label{eq:rankone} W(n)\gg n^{F_1(v)},\qquad F_1(v)=2+\frac{2v}{\mu}. \end{equation} Rank at least three gives \(W(n)\gg n^4\) directly. Rank two gives \(W(n)\gg n^3\), which suffices for \(u<2.99\). \subsection{Separation of rank-two chains} Suppose \(u\ge2.99\) and \(\mathcal P\) has two nontrivial sides of sizes \(L_1,L_2\). Write \(f(x)=g_1x_1+g_2x_2\) for the progression map on the coordinate box, up to translation. Put \(M=L_1L_2\gg n^3\), \(V=\operatorname{diam}\mathcal P\), and \(R=V/M\). Choose \(m\asymp V^{1/B}\) with \(m\le n/4\) and \(S_m\le V/2\). The \(m+1\) translates supplied by different cardinalities in this prefix are disjoint by admissibility. Hence \(R\gg m\). At least one \(|g_i|/L_{3-i}\) is at least \(R/2\). All nonzero coordinate differences with numerical image of absolute value at most \(R/10\) are collinear. Two linearly independent differences would have nonzero integral determinant. Solving for \(g_i\) would give both \(|g_i|\le 2(R/10)L_{3-i}\), a contradiction. If such a direction exists, choose its primitive integer vector \(z=(a,b)\) and put \(d=|f(z)|\). Properness implies \(1\le d\le R/10\). All nonzero numerical spacings are at least \(d\). Let \[ \lambda=\min_{z_i\ne0}\frac{L_i-1}{|z_i|},\qquad L=\lfloor\lambda\rfloor+1 . \] Here \(\lambda\ge1\), and \(L\) is the largest length of a chain in direction \(z\), achieved from a suitable corner. By \eqref{eq:capacity}, \(L\ll d^\mu\). Relabel so that \(\lambda=(L_1-1)/|a|\). The integer \(k=a x_2-bx_1\) indexes the chains because \(z\) is primitive. We have \[ f(x)=\frac{g_2}{a}k+\frac{f(z)}a x_1,\qquad V\le2|g_2|(L_2-1)+d\lambda. \] The second estimate follows from \(|a g_1|\le |b g_2|+d\). Since \(d\lambda\le V/10\) and \(|a|(L_2-1)\le M/\lambda\), we get \(|g_2/a|\ge0.45 R\lambda\). Points on distinct chains are separated numerically by at least \(0.35R\lambda\ge0.175RL\). Take \(\delta=3/25\) and \(H=\min(RL,R^{1+\delta})/10\). A length-\(H\) interval meets at most one chain. Adding a layer through \(T(H)\) therefore has multiplicity at most \(L\). A layer through \(T(d/4)\) gives disjoint translates. The larger of these two fixed-cardinality families has size at least a constant times \[ M\max\!\left\{d^v,\ R^v\frac{\min(L,R^\delta)^v}{L}\right\}. \] Because the quotient is decreasing in \(L\), use \(L\ll d^\mu\) in the second term. If \(d^\mu\ge R^\delta\), balancing the terms gives a factor \(R^\sigma\), where \(\sigma=(1+\delta)v^2/(\mu+v)\). If \(d^\mu0\). \section{Excluding all smaller exponents} Under \eqref{eq:parameter-range}, assume \(pu\) is equivalent to \[ B u^2-(cp+2B-2)u+2cp>0 . \] The discriminant is \(p[p(c-2)^2-8c]<0\). For the refined rank-two argument, \(F_2(u/c)>3\). When \(u\ge3\), writing \(s=u-3\) gives the equivalent inequality \[ 1.12(s+3)^2(3+(p+1)s)-c p^2(c-3-s)s>0. \] Here \(0\le s\le c-4\). For \(s>0\) the expression decreases in \(p\) throughout the range, since \(c-3-s\ge1\) and \(1.12(s+3)^2<2cp(c-3-s)\). Increase \(p\) to \(\min(5.562,P(c))\). On each rational interval \([l,h]\) below put \(B_-=1+P(h)\) and \(K=h\min(5.562,P(l))^2\). Bounding the positive term with \(B_-\), using \(K\) and \(h\) in the negative term, and discarding the positive cubic yield a quadratic with coefficients \[ 27(1.12),\qquad 1.12(18+9B_-)-K(h-3),\qquad 1.12(3+6B_-)+K . \] The leading coefficient is positive, and direct substitution of the rational endpoints gives the strict upper bounds on its discriminant displayed below. In each interval \(P(h)<5.562\), so the lower bound for the positive term applies. \[ \begin{array}{c|r@{\qquad}c|r} [l,h]&\text{discriminant}&[l,h]&\text{discriminant}\\ \hline {[4.55,4.562]}&<-4811 &[4.562,4.59]&<-3175\\ {[4.59,4.62]}&<-2810 &[4.62,4.66]&<-1987\\ {[4.66,4.70]}&<-1712 &[4.70,4.75]&<-920\\ {[4.75,4.80]}&<-667 &[4.80,4.829]&<-1469 \end{array} \] Thus the rank-two gain is also strict. For \(u\le2.99\) the direct exponent \(3\) is already larger than \(u\). The exponent \(4\) for higher ranks is larger than \(c-1\). For fixed \(c,p\), compactness on the two subintervals of \(2\le u\le c-1\) lets us take \(v=u/c-\varepsilon\), with one sufficiently small \(\varepsilon>0\), and gives a uniform positive gain in \(u\). Initially \(W(n)\gg n^2\), since moving the chosen middle-layer indices one place at a time from their least to their greatest possible positions gives a strictly increasing path of \(1+\lfloor n/2\rfloor\lceil n/2\rceil\) sums. Finitely many applications of Lemma~\ref{lem:cutoff} and the progression estimates give \(W(n)\gg n^{c-1+\eta}\) for some \(\eta>0\). The cardinality padding gives \(S_n\ge Z(n)-1\gg n^{c+\eta}\). Lemma~\ref{lem:spike} contradicts the gap cap. To see that this excludes every claimed range, first suppose a gap bound holds for an exponent less than \(c_0\). Increase it if needed to \(c\in[4.55,c_0)\), and sum the gaps to obtain the term exponent \(p=c+1\). Then \(p2\), \(13\), \(c\le p\le c+1\), and \begin{equation}\label{eq:scale} \rho+s=c,\qquad t(\rho-2)=\rho,\qquad sp=\rho+2t. \end{equation} At one stage let \(A\subset[1,B)\) have size \(N\ge2\). Let \(h\) be a positive integer, \(d=h/\gcd(B,h)\), \(r=\lceil N^s\rceil\), and \(D=\sum_{a\in A}(B-a)\). Maintain \begin{equation}\label{eq:deficits} d\le r,\qquad D+10hN^2(r/N)^3\). The last step uses \(r\le N^2\) and \(R/2\ge(32/17)C^2N^{2t-2}>N^3\). Put \(H=R-k-(r/N)^3>0\). Define the row indices by \[ j_i=\left\lfloor (i/N)^3+H(i/r)^7\right\rfloor \qquad(0\le i\le r). \] For \(0\le i3\) and \(7>p\), its normalized value \(a_n/n^p\) is \(O(g/N^p+B'/r^p)=O(B/N^\rho)\), by \eqref{eq:scale}. The dense group begins beyond \(N+r\) and satisfies the same bound using \(B'/r^p\). For an adjacent pair within one row the gap is \(h\le g\). At a row change, including the first dense term at \(i=r\), the next within-row index is zero. Thus a gap with left index \(n=N+i+1\) in the filler part is at most \[ g\left(1+3(i+1)^2/N^3+7H(i+1)^6/r^7\right). \] Dividing by \(n^c\) yields \(O(g/N^c+B'/r^{c+1})=O(B/N^\rho)\), since \(20\) were represented by signed sums arbitrarily far out. Disjoint representations of \(d\) have a common signed cardinality \(h\). Take \(d\) distinct terms larger than \(d^2\). Two of their \(d+1\) cumulative sums agree modulo \(d\), so between them is a nonempty subset of size \(r\le d\) with sum \(kd\) and \(k>d\). Choose \(k\) pairwise disjoint later signed representations of \(d\). Admissibility would give \(r=kh\), which is impossible. Hence for every fixed \(H\) all distinct subset-sum values on a sufficiently late tail are spaced by more than \(H\). This proves gap divergence. On \(m\) tail terms the layer of size \(j\) has at least \(1+j(m-j)\) values by a monotone path, and the layers are disjoint. Summing and comparing with the total span \(m a_n\) gives \(a_n\ge Hm^2/6\). Take \(m=n-O_H(1)\), then let \(H\) increase. Given an admissible prefix \(A\), set \(M=1+\sum A\) and append \(M\{k^2,k^2+1,\ldots,k^2+k-1\}\). In a signed zero relation the old sum is divisible by \(M\), hence vanishes and has signed cardinality zero. The normalized new sum is \(k^2j+I\) with \(|I|\le k(k-1)/2\), so \(j=0\) as well. At stage \(j\) choose \(k\ge\max\{N^2,(2M)^j\}\), where \(N\) is the old length. This gives \(a_{N+k}\le2Mk^2\) and \(\Delta_{N+k-1}=M\) on the resulting subsequences. In conjunction with the universal divergence, the lower logarithmic orders are \(2\) and \(0\). \newpage \begin{thebibliography}{10} \bibitem{Bloom} T. F. Bloom, \emph{Erd\H{o}s Problem \#875}, \url{https://www.erdosproblems.com/875}. \bibitem{DF} J.-M. Deshouillers and G. A. Freiman, \emph{On an additive problem of Erd\H{o}s and Straus, 2}, Ast\'erisque \textbf{258} (1999), 141--148. \href{https://doi.org/10.24033/ast.442}{doi:10.24033/ast.442}. \bibitem{Erdos62} P. Erd\H{o}s, \emph{Sz\'amelm\'eleti megjegyz\'esek, III. N\'eh\'any addit\'iv sz\'amelm\'eleti probl\'em\'ar\'ol}, Matematikai Lapok \textbf{13} (1962), 28--38. \href{https://www.renyi.hu/~p_erdos/1962-22.pdf}{Digitized copy}. \bibitem{Erdos} P. Erd\H{o}s, \emph{Some of my new and almost new problems and results in combinatorial number theory}, Number Theory (Eger, 1996), de Gruyter, Berlin, 1998, 169--180. \bibitem{ENS} P. Erd\H{o}s, J.-L. Nicolas, and A. S\'ark\"ozy, \emph{Sommes de sous-ensembles}, S\'eminaire de th\'eorie des nombres de Bordeaux, S\'erie 2, \textbf{3} (1991), 55--72. \href{https://www.numdam.org/item/JTNB_1991__3_1_55_0/}{Digitized copy}. \bibitem{Carry} \textsc{erdosSweep} (maintainer D. R. Colkitt), \emph{Sharp local carry lemmas and a quadratic radix barrier for admissible-set block constructions}, \href{https://github.com/Mister-Meeseeks/erdos-875-carry-lemmas/blob/main/note/note.pdf}{research note}, July 2026. \bibitem{Mazur} GPT-5.5 Pro and L. Mazur, \emph{On an absolute-gap variant of Erd\H{o}s Problem \#875: An infinite admissible set with \(a_{n+1}-a_n\le n^{3+2\sqrt2}\) and little-\(o\) gaps}, \href{https://github.com/lechmazur/erdos_875/blob/main/docs/reference/admissible_carry_note_erdos875.pdf}{research note}, May 2026. \bibitem{Nicolas} J.-L. Nicolas, \emph{Stratified sets}, Ast\'erisque \textbf{258} (1999), 205--215. \href{https://www.numdam.org/item/AST_1999__258__205_0/}{Digitized copy}. \bibitem{SV} E. Szemer\'edi and V. H. Vu, \emph{Long arithmetic progressions in sumsets: Thresholds and bounds}, J. Amer. Math. Soc. \textbf{19} (2006), 119--169. \href{https://doi.org/10.1090/S0894-0347-05-00502-3}{doi:10.1090/S0894-0347-05-00502-3}. \bibitem{WY} G. Wang and W. Yang, \emph{Sharp enumeration and growth of admissible sets of integers}, \href{https://arxiv.org/abs/2610.34372v2}{arXiv:2610.34372v2}, November 2026. \end{thebibliography} \end{document}