\documentclass[11pt]{amsart} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[letterpaper,margin=1in]{geometry} \usepackage{microtype} \usepackage{mathtools,amssymb} \usepackage{xcolor} \definecolor{linkblue}{rgb}{0,0,0.6} \usepackage[colorlinks=true,linkcolor=linkblue,citecolor=linkblue,urlcolor=linkblue]{hyperref} \hypersetup{pdftitle={Infinitely Many Decreases in Distinct-Power Thresholds}, pdfauthor={Will Howe; Grant Huffman; Jensen Kohlmeyer; Liam Kruer}} \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\e}{\mathrm e} \newcommand{\ii}{\mathrm i} \newcommand{\E}{\mathbb E} \newcommand{\Prob}{\mathbb P} \newcommand{\normone}[1]{\lVert #1\rVert_1} \newcommand{\dist}[1]{\lVert #1\rVert_{\R/\Z}} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\Var}{Var} \setlength{\emergencystretch}{2em} \allowdisplaybreaks[1] \title[Distinct-power thresholds]{Infinitely many decreases in the thresholds\\ for sums of distinct powers} \author[W. Howe]{Will Howe} \author[G. Huffman]{Grant Huffman} \author[J. Kohlmeyer]{Jensen Kohlmeyer} \author[L. Kruer]{Liam Kruer} \date{November 8, 2026} \subjclass[2020]{11P05, 05A17} \keywords{distinct powers, subset sums, complete sequences, cyclotomic recurrences} \thanks{Email addresses: \href{mailto:howew@purdue.edu}{\texttt{howew@purdue.edu}} (Will Howe); \href{mailto:huffma97@purdue.edu}{\texttt{huffma97@purdue.edu}} (Grant Huffman); \href{mailto:jenwin@purdue.edu}{\texttt{jenwin@purdue.edu}} (Jensen Kohlmeyer); \href{mailto:kruerl@purdue.edu}{\texttt{kruerl@purdue.edu}} (Liam Kruer).} \begin{document} \begin{abstract} Let \(T_k\) be the least integer such that every integer at least \(T_k\) is a sum of distinct positive \(k\)th powers. We prove that \(T_k>T_{k+1}\) for infinitely many positive integers \(k\). The principal upper estimate holds on a set of degrees meeting every sufficiently large dyadic interval: \[ \log T_k\le(1+o(1))\,k \exp\!\left(\frac25\frac{\log k}{\log\log k}\right). \] We obtain it from flat integral recurrences, cyclotomic coefficient estimates, an exact reduction of polynomial degree, and a subset-sum construction. A shifted-prime divisor theorem of Fan and Pollack supplies larger lower bounds along an unbounded sequence of degrees. The two estimates contradict eventual monotonicity of the thresholds. \end{abstract} \maketitle \section{The problem and the two estimates} For \(A\subseteq\Z_{\ge0}\), write \[ \Sigma(A)=\left\{\sum_{a\in B}a:B\subseteq A,\ B\text{ finite}\right\}. \] The empty sum is allowed. Let \(\mathcal P_k=\{n^k:n\in\N,\ n\ge1\}\), and put \[ T_k=\min\{T\in\Z_{\ge0}:[T,\infty)\cap\Z\subseteq\Sigma(\mathcal P_k)\}. \] The finiteness of \(T_k\) for every positive \(k\) is classical; see Kim~\cite{Kim}. We have \(T_1=0\). If \(k\ge2\), the integer two is not representable, so \(T_k\ge3\). For \(k\ge2\), using the largest exceptional integer instead subtracts one from each threshold, and therefore preserves adjacent comparisons. The question considered here is Erd\H{o}s problem~345; see Erd\H{o}s and Graham~\cite[p.~55]{EG}. \begin{theorem}\label{thm:main} There are infinitely many positive integers \(k\) for which \(T_k>T_{k+1}\). \end{theorem} All logarithms are natural, and \(\mathcal L(x)=\log x/\log\log x\) for \(x>\e\). An unspecified positive absolute constant may be enlarged when it reappears; dependence on a fixed parameter is indicated by a subscript. All asymptotic estimates below are uniform in the degrees and frequencies to which they are applied. \begin{proposition}\label{prop:upper} There is a set \(\mathcal G\subseteq\N\) meeting every sufficiently large interval \([2^m,2^{m+1}]\) such that \begin{equation}\label{eq:upper} \log T_k\le(1+o(1))\,k\exp\!\left(\frac25\mathcal L(k)\right) \qquad(k\in\mathcal G). \end{equation} \end{proposition} This is proved in Sections~\ref{sec:flat}--\ref{sec:completion}. For comparison, define \[ \omega^*(n)=\#\{p:p\text{ prime},\ p-1\mid n\},\qquad D(n)=\prod_{\substack{p\text{ prime}\\p-1\mid n}}p. \] Fan and Pollack~\cite[Theorem~1]{FP} prove unconditionally that \begin{equation}\label{eq:FP} \omega^*(n)> \exp\!\left((0.6736\log2)\mathcal L(n)\right) \end{equation} for infinitely many \(n\). Only this infinitely-often conclusion is used. \begin{lemma}\label{lem:lower} There are arbitrarily large \(j\) such that \begin{equation}\label{eq:lower} \log T_j\ge j\exp\!\left(\frac9{20}\mathcal L(j)\right). \end{equation} \end{lemma} \begin{proof} Choose \(n\) satisfying \eqref{eq:FP}, and put \(j=n+1\) and \(Q=D(n)\). For every integer \(b\), \(b^j\equiv b\pmod Q\). Modulo a prime factor \(p\) of \(Q\), this follows from \(p-1\mid n\) if \(p\nmid b\); if \(p\mid b\), both sides vanish. The factors of \(Q\) are distinct. Set \(H=\lfloor\sqrt Q\rfloor\) and \(S=H(H+1)/29/20\), and \(\mathcal L(n+1)-\mathcal L(n)\to0\), the fixed factors and the error are absorbed by the strict difference of constants. This proves \eqref{eq:lower}. \end{proof} \section{Flat products and integral recurrences}\label{sec:flat} For \(P(z)=\sum_h w_hz^h\), put \(\normone P=\sum_h|w_h|\). Let \(E\) denote the shift operator on sequences: \((Ex)_n=x_{n+1}\), and write \(\Delta=E-1\). A rational polynomial is called integer-valued if its values at all integers are integers. We use the following consequence of Belov and Konyagin~\cite[Corollary~0.2]{BK}. For every positive integer \(J\), there are nonincreasing nonnegative integers \(a_1,\ldots,a_J\), of sum \(J\), and a real \(a_0\), such that \begin{equation}\label{eq:cosine} a_0+\sum_{h=1}^J a_h\cos(h\theta)\ge0\quad(\theta\in\R), \qquad a_0\le2^{32}(1+\log J)^5. \end{equation} \begin{lemma}\label{lem:flat} For every \(J\ge1\), one can choose \[ P_J(z)=\prod_{h=1}^J(1-z^h)^{a_h}=(1-z)^JQ_J(z)\in\Z[z] \] so that \begin{align} \deg P_J&\le J^2,& \log\normone{P_J}&\le C(1+\log J)^6,\label{eq:flatnorm}\\ Q_J&\in\Z_{\ge0}[z],& M_J:=Q_J(1)&=\prod_h h^{a_h}\mid J!,\label{eq:moment}\\ \sum_{\substack{h\le J\\v\mid h}}a_h&\le J/v&& (v\ge1). \label{eq:slots} \end{align} The constant and leading coefficients of \(P_J\) have absolute value one. \end{lemma} \begin{proof} Take the coefficients from \eqref{eq:cosine}. For \(0<\rho<1\), \[ \log|P_J(\rho\e^{\ii\theta})| =-\sum_{m\ge1}\frac{\rho^m}{m}\sum_h a_h\cos(hm\theta) \le a_0\log\frac1{1-\rho}. \] Also \[ |1-\e^{\ii t}|\le\frac2{1+\rho}|1-\rho\e^{\ii t}|. \] Taking \(\rho=1-J^{-1}\), for \(J\ge2\), gives \(\log\|P_J\|_\infty\le C(1+\log J)^6\). By Parseval, \(\normone{P_J}\le\sqrt{\deg P_J+1}\|P_J\|_\infty\), proving \eqref{eq:flatnorm}; \(J=1\) is immediate. The product \[ Q_J(z)=\prod_h(1+z+\cdots+z^{h-1})^{a_h} \] has nonnegative integral coefficients. Let \(\lambda_i=\#\{h:a_h\ge i\}\), \(1\le i\le a_1\). Then \(\sum_i\lambda_i=J\) and \(M_J=\prod_i\lambda_i!\), which divides \(J!\) by the multinomial formula. Finally, the block of \(v\) indices ending at \(iv\) has coefficient sum at least \(va_{iv}\). Adding the disjoint blocks proves \eqref{eq:slots}. The remaining assertions follow from the product. \end{proof} \begin{lemma}[Rounding to an exact recurrence]\label{lem:rounding} Let \(k,X\) be positive integers and put \(K=1+\log k\). Suppose \(1\le d\le k\), \(F\in\R[x]\) has degree at most \(d\), and \[ \sum_{0\le n0\). We refine the denominator estimate in the preceding proof. There are at most \(J/t\) vanishing factors, by \eqref{eq:slots}, and their derivatives have absolute value at most \(J\). For a nonvanishing factor \(1-\zeta^h\), put \(l=t/\gcd(t,h)>1\). Its geometric mean over primitive \(t\)th roots is \(\Phi_l(1)^{1/\varphi(l)}\). This is one unless \(l=p^a\) is a prime power, when its logarithm is \(\log p/\varphi(p^a)\). Such factors have \(t/p^a\mid h\); by \eqref{eq:slots} their number with multiplicity is at most \(Jp^a/t\). The total logarithmic contribution of nonvanishing factors is thus at most \[ \sum_{p^a\mid t}\frac{Jp^a}t \frac{\log p}{\varphi(p^a)} \le\frac{2J}t\sum_{p^a\mid t}\log p =\frac{2J}t\log t. \] Cancellation decreases the geometric-mean denominator bound, as above, and \(b!\le J^{J/t}\). Some conjugate top coefficient therefore satisfies \[ |a_\zeta|\ge\exp\!\left(-C(J/t)\log(2J)\right). \] The interval-length condition in Lemma~\ref{lem:gram} is polynomial in \(k\), and hence holds here. It follows that \[ (2h_t-1)\log L\le C(J/t)K+C\log k. \] If \(h_t>0\), then \(t\le J\), so \(J/t\ge1\). Now \(2h_t-1\ge h_t\), \(J\le2d\), and \(\log L\sim Z\). This proves \eqref{eq:nontrivialheight} without an additive constant. Apply Lemma~\ref{lem:integerheight} to \(q\epsilon\) for the remaining bound. Its energy is at most \(q^2k^2/4\), and its largest component degree is at least \(h_1-1\). This gives \eqref{eq:oneheight}; in particular the term involving \(\log q\) is not discarded. \end{proof} \section{Exact arithmetic of polynomial reductions}\label{sec:arithmetic} For \(0\le d0\). A prime \(p\) divides \(F_{k,j}\) exactly when \(p-1\mid h\). Necessity follows by testing units modulo \(p\); sufficiency also includes nonunits, because \(j\ge1\). Testing \(a=p\) bounds \(v_p(F_{k,j})\) by \(j\). For odd \(p\), testing \(a=1+p\) bounds it by \(1+v_p(h)\). For \(p=2\), testing \(a=3\) bounds it by \(2+v_2(h)\). These lifting identities show that \(F_{k,j}\mid2hD(h)\). Taking logarithms gives \begin{equation}\label{eq:logG} \log G_d(k)\le d\log(2k)+\sum_{j=1}^d\log D(k-j). \end{equation} \end{proof} We next control a prime-power modulus from the cyclotomic multiplicities of an annihilator. Here \(v_p\) denotes the \(p\)-adic valuation. \begin{lemma}[Dilation of an integral recurrence]\label{lem:dilation} Let \(p\) be prime, \(e\ge1\), and \[ B(z)=(z-1)^{m_0}\prod_{a=1}^A\Phi_{p^a}(z)^{m_a}, \qquad 0\le m_a\le k\quad(0\le a\le A). \] If \(B(E)n^k\equiv0\pmod {p^e}\) for all \(n\in\Z\), then \begin{equation}\label{eq:dilation} e\le C\left\{\frac{m_0}{p-1} +\sum_{a=1}^A(a+1)m_a +(A+1)(1+\log_p(k+1))\right\}. \end{equation} \end{lemma} \begin{proof} Put \(D_B=\deg B\). The rational \(B\)-recurrence sequences on \(\Z\) have an integral lattice identified with \(\Z^{D_B}\) by their first \(D_B\) entries, since the leading and constant coefficients of \(B\) are units. For a positive integer \(g\) prime to \(p\), the dilation \(S_g(x)_n=x_{gn}\) preserves this space and its integral lattice: on the complex basis \(n^j\zeta^n\), it permutes primitive roots of a fixed \(p\)-power order and multiplies the degree-\(j\) vector by \(g^j\). Extend \(0^k,1^k,\ldots,(D_B-1)^k\) by the recurrence to an integral sequence \(y\). The assumed congruence makes \(y_n\equiv n^k\pmod {p^e}\) for all integers \(n\). The cases \(D_B=0,1\) are impossible, because the values at zero and one are respectively zero and one. Thus the initial vector contains a unit, and \[ S_g y\equiv g^k y\pmod {p^e}. \] If \(\chi_g\) is the characteristic polynomial of this integral matrix, Cayley--Hamilton gives \begin{equation}\label{eq:characteristic} p^e\mid\chi_g(g^k). \end{equation} For odd \(p\), choose \(g\) primitive modulo \(p^2\), hence modulo every \(p^a\). The primitive \(p^a\)th roots form one cycle of length \(\varphi(p^a)\). Their degree-\(j\) characteristic factor is \(T^{\varphi(p^a)}-g^{j\varphi(p^a)}\), for \(0\le jT\), all nontrivial \(p\)-power roots are absent. Then \(B=(z-1)^{h_1}\); necessarily \(h_1\ge1\), and \[ p^e\mid G_{h_1-1}(k). \] Set \(M=\lceil C_1(T+K^2)K^2\rceil\), with \(C_1\) fixed and sufficiently large. For \(p\le T\), the elementary bound \(v_p(M!)\ge M/(2p)\), valid here since \(M\ge2p\), dominates \eqref{eq:primeexponent}. Thus the part of \(q\) supported on primes at most \(T\) divides \(M!\). Now assume \(MM\), is divisible by \(M!\). Thus the small-prime part also divides \(G_M(k)\). The two parts are coprime, so \(q\mid G_M(k)\). The chosen value of \(M\) satisfies \eqref{eq:contraction}. \end{proof} \section{Good degrees and the exact-center estimate}\label{sec:centers} Fix throughout \begin{equation}\label{eq:parameters} c=\frac25,\qquad a=\frac1{10},\qquad \beta=\frac1{100}. \end{equation} \begin{lemma}[Simultaneous degree selection]\label{lem:selection} For every sufficiently large dyadic \(Y\), all but \(o(Y)\) integers \(k\in[Y,2Y]\) satisfy \begin{equation}\label{eq:good} \log D(k-j)\le \exp(a\mathcal L(Y)) \quad\text{for }1\le j\le\lceil(2Y)^\beta\rceil. \end{equation} \end{lemma} \begin{proof} Let \(\tau\) be the divisor function and \(d_z\) the ordered \(z\)-fold divisor function. For every integer \(m\ge1\), \[ \tau(n)^m\le d_{2^m}(n). \] For a prime power exponent \(b\), this follows by induction from \[ \frac{\binom{b+2z-1}{b}}{\binom{b+z-1}{b}} =\prod_{i=0}^{b-1}\frac{2z+i}{z+i}\ge b+1\qquad(z\ge1); \] each factor increases with \(z\), and the product at \(z=1\) is \(b+1\). Multiplicativity completes the proof. Counting ordered factorizations and summing the first \(z-1\) factors harmonically gives, with no constant depending on \(z\), \begin{equation}\label{eq:momentbound} \sum_{n\le U}d_z(n)\le U(1+\log U)^{z-1}. \end{equation} Since a prime predecessor divisor of \(n\) is at most \(n+1\), \(\log D(n)\le\tau(n)\log(n+1)\). Take \[ m=\left\lfloor\frac{\log\log Y-3\log\log\log Y}{\log2}\right\rfloor, \qquad B_Y=\frac{\exp(a\mathcal L(Y))}{\log(2Y+1)}. \] By \eqref{eq:momentbound} and Markov's inequality, the number of \(n\le2Y\) with \(\log D(n)>\exp(a\mathcal L(Y))\) is at most \[ 2Y(1+\log(2Y))^{2^m-1}B_Y^{-m} =Y^{1-a/\log2+o(1)}. \] Indeed \(2^m\le\log Y/(\log\log Y)^3\), so the positive logarithmic error is \(o(\log Y)\), while \(m\log B_Y=(a/\log2+o(1))\log Y\). The union over at most \(O(Y^\beta)\) shifts has size \(Y^{1-a/\log2+\beta+o(1)}=o(Y)\), because \(\beta0\) is any fixed constant. Then \begin{equation}\label{eq:scales} Z:=\log X\sim\log N\sim\exp(c\mathcal L(k)),\qquad K^A=o(Z)\ (A\text{ fixed}),\qquad \log N=o(k). \end{equation} In particular \(N\) and \(X\) exceed every fixed power of \(k\). We will also use the following fixed-parameter consequence of Shiu's short-interval estimate~\cite{Shiu}, in the form stated by Nair and Tenenbaum~\cite[Introduction]{NT}: \begin{equation}\label{eq:shiu} \sum_{j=1}^d\tau(k-j)\le C_\beta d\log k \quad(k^\beta\le d\le k/3). \end{equation} For clarity, its parameters are fixed: apply the theorem to the multiplicative function \(\tau=\tau_2\), modulus one, and interval \((k-d-1,k-1]\), with exponent \(\beta/2\). This interval has length \(d\) and lies at height comparable to \(k\). The hypotheses \(\tau(p^\nu)=\nu+1\le2^\nu\) and \(\tau(n)\ll_\varepsilon n^\varepsilon\) hold. The resulting bound is \(O_\beta(d(\log k)^{-1}\exp(\sum_{p\le k}2/p)) =O_\beta(d\log k)\). Neither the function nor the interval exponent varies with \(k\). \begin{proposition}[Exact-center energy]\label{prop:center} For all sufficiently large \(k\in\mathcal G\), and every reduced fraction \(u/q\) with \(2\le q\mid k!(k+1)!\), \begin{equation}\label{eq:center} \sum_{0\le nk^2. \end{equation} Here \(X\) may be chosen as in \eqref{eq:NX} for any fixed \(B>0\). \end{proposition} \begin{proof} Suppose the energy is at most \(k^2\). Begin with \(F(x)=ux^k/q\), of degree \(d=k\). Lemma~\ref{lem:contraction} and \(\log q=O(kK)\) give a new degree \[ M\le CkK^3/Z+CK^4=o(k). \] In particular \(M2C_0K^4\), this gives \(M<3d/4k^2, \] by \eqref{eq:scales} and \eqref{eq:smallq}. This is the desired contradiction. \end{proof} \section{From rational centers to collision estimates}\label{sec:collision} Retain \(k\in\mathcal G\) and \(N\) from \eqref{eq:NX}. Put \[ S=512\left\lfloor\frac{\lfloor N/k\rfloor}{512}\right\rfloor,\quad \mathcal V=\{N-S+1,\ldots,N\},\quad R=\{1,\ldots,N-S\}\setminus\{2,\ldots,257\}. \] Thus \(\mathcal V\) is the reserved set of bases and \(R\) is the available initial population. Write \[ M_R=|R|,\qquad t=\lfloor N/8192\rfloor,\qquad \ell=128. \] For \(b\in\mathcal V\), let \(q_b=b^k\), and define \begin{align*} D_b(\alpha)&=\sum_{n\in R}\sin^2(\pi\alpha n^k),\\ F_b(h)&=\frac1{M_R}\sum_{n\in R} \cos^2(\pi hn^k/q_b) =1-\frac{D_b(h/q_b)}{M_R}. \end{align*} We will prove \begin{equation}\label{eq:collision} \sup_{b\in\mathcal V}\sum_{h=1}^{q_b-1}F_b(h)^t=o(1). \end{equation} Notice that \(M_R\sim N\) and \(t/M_R\ge1/16384\) for large \(k\). Also \(S\le N/k\), so \(b/N\ge1-1/k\) for \(b\in\mathcal V\). Since \((1-1/k)^k\to\e^{-1}>1/4\), we have \(b^k\ge N^k/4\) uniformly over the reserved bases. \begin{lemma}[A common rational approximation]\label{lem:inverse} Let \(A>0\) be fixed. There are a constant \(C\) and an integer \(B_k\mid k!(k+1)!\), independent of \(\alpha\), such that \[ D_b(\alpha)\le Ak\log N \quad\Longrightarrow\quad \left|\alpha-\frac u{B_k}\right| \le N^{-k}\exp(CkK^6) \] for some integer \(u\). The assertion is uniform in \(b\in\mathcal V\). \end{lemma} \begin{proof} The population is independent of \(b\). Add back the at most 256 excluded terms and use the prefix \(0\le nN/2\), use the interval \[ [r(1/8)^{1/k},\,r(1/4)^{1/k}]. \] It has \(\gg N/k\) integer points, all in \(R\) for large \(k\): its upper endpoint is at most \(N4^{-1/k}2. \] Their integer points lie in \(R\). Indeed their lower endpoints exceed 257, while their upper endpoints are at most \(r(Y_r+1)^{1/k}\le3N/4\) eventually, because \(\log N=o(k)\). Each interval contains at least half its length in integers, with sine square at least \(1/8\). Therefore \[ D_b(h/q_b) \ge\frac r{256k}\sum_{j=1}^{Y_r}\frac1{j+1} \ge\frac{r\log(Y_r+1)}{512k} \ge\frac{K_*k\log k}{1024}. \] The first case satisfies the same final bound, since \(N/k\gg K_*k\log k\). Now \(F_b(h)^t\le\exp(-D_b(h/q_b)/16384)\). There are fewer than \(N^k\) frequencies, and \(K_*>2^{24}\log N/\log k\) by a fixed factor. Hence their total contribution is bounded by \[ N^k\exp\!\left(-\frac{K_*k\log k}{2^{24}}\right)=o(1). \] \end{proof} \begin{proposition}\label{prop:collision} The uniform collision estimate \eqref{eq:collision} holds. \end{proposition} \begin{proof} Choose a fixed \(A\) sufficiently large. Frequencies with \(D_b(h/q_b)>Ak\log N\) have total contribution at most \[ N^k\exp(-Ak\log N/16384)=o(1). \] Every remaining frequency is in an arc \[ \left|\frac h{q_b}-\frac u{B_k}\right|\le\delta,\qquad \delta=N^{-k}\exp(CkK^6), \] by Lemma~\ref{lem:inverse}. We have \(\log B_k=O(kK)\), and \(\delta B_k=o(1)\). Thus at most \(B_k+2\) centers are relevant in or adjacent to \([0,1]\). Each arc contains at most \(2q_b\delta+2\) points of the actual grid. The total number of grid points in these arcs is therefore at most \(\exp(C_3kK^6)\). Consequently those among them with \(D_b\ge A_3kK^6\) also contribute \(o(1)\), for a fixed \(A_3>2\cdot16384C_3\). It remains to consider \(D_b4\), so the collision excess is greater than three. For each fixed group, the expected number of such bad reserved bases is at most \(S\eta_k/3\). Markov's inequality bounds the probability of more than \(S/2\) bad bases by \(2\eta_k/3\). A union bound over the fixed \(\ell\) groups proves that, with probability \(1-o(1)\), every group has at least \(S/2\) good bases. We may simultaneously require \begin{equation}\label{eq:initialspan} \sum_{n\in C_i}n^k\le4tN^k/k\qquad(1\le i\le\ell). \end{equation} Indeed the expectation is at most \(2tN^k/k\), because \(\sum_{n\le N}n^k\le N^{k+1}/(k+1)+N^k\) and \(M_R\sim N\). Sampling without replacement has variance at most \(tN^{2k}\). Chebyshev's inequality makes the failure probability at most \(k^2/(4t)=o(1)\), uniformly in the fixed number of groups. Fix a realization with both properties. Allocate \(s\) good reserved bases to each group, with no base used twice. Before any individual choice, fewer than \(\ell s=S/4\) bases have been used, whereas the group in question has at least \(S/2\) good choices. The greedy allocation is therefore possible; the completed allocation uses exactly \(S/4\) bases. If a finite integer set \(A\) occupies \(r\) residue classes modulo a positive integer \(q\), then \[ |A+\{0,q\}|\ge|A|+r. \] For each occupied residue, its largest element supplies a new element after addition of \(q\). Applying this with \(q=b^k\) shows that each allocated base increases the subset-sum cardinality by at least \(q_b/4\ge N^k/16\). The original support is retained after earlier additions, so the support condition continues to hold. After \(s\) additions the cardinality is at least \(sN^k/16\). Finally add the distinct auxiliary pairs \[ (2,3),(4,5),\ldots,(256,257) \] to the 128 groups, one pair per group. They are disjoint from \(R\) and from the reserved bases. Each resulting subset-sum set contains zero and two coprime \(k\)th powers, so it cannot lie in a proper integer arithmetic progression. The initial span in \eqref{eq:initialspan} is at most \(sN^k/3\) eventually, because \(4t/(ks)\to1/4<1/3\). The reserved bases add at most \(sN^k\), and the two auxiliary powers add at most \(2\cdot257^k=o(sN^k)\). This proves \eqref{eq:groups}. \end{proof} We use Lev's consecutive-interval theorem in the following sufficient form~\cite[Corollary~1]{Lev}. If \(A_1,\ldots,A_\ell\) are subsets of \([0,l]\cap\Z\), each of size at least \(n\ge3\), none contained in an integer arithmetic progression of difference greater than one, and \[ \ell\ge2\left\lceil\frac{l-1}{n-2}\right\rceil, \] then their sumset contains \(\ell(n-1)+1\) consecutive integers. Here the length of a block means its largest element minus its smallest, as in Lev's statement. \begin{proof}[Proof of Proposition~\ref{prop:upper}] Apply this result to Lemma~\ref{lem:groups}, with \[ l=\lceil2sN^k\rceil,\qquad n=\lfloor sN^k/16\rfloor,\qquad \ell=128. \] The ratio \((l-1)/(n-2)\) tends to 32, so the strict inequality has a fixed margin. The sumset contains an interval \([a,a+L]\cap\Z\) with \[ L\ge128(n-1)\sim8sN^k>(N+1)^k. \] Also \(0\le a\le256sN^k\le256N^{k+1}\). Every integer in this interval is a sum of distinct \(k\)th powers with bases at most \(N\), because the groups of bases are disjoint. Adjoin the unused powers with bases \(N+1,N+2,\ldots\). If the currently represented interval is \([a,a+L]\) and a new power \(b^k\) satisfies \(b^k\le L+1\), its translate joins it without a gap, producing \([a,a+L+b^k]\). Initially \(L\ge(N+1)^k\). If \(L\ge b^k\), then the new length is at least \(2b^k>(b+1)^k\), since \(b\ge N\) and \(N/k\to\infty\). This preserves the induction invariant. At each stage the interval consists of subset sums of the finitely many bases used up to that stage, all distinct. Its length tends to infinity. Every fixed integer at least \(a\) consequently belongs to one finite-stage interval, and is represented by finitely many distinct positive \(k\)th powers. We have proved \[ T_k\le256N^{k+1}. \] Taking logarithms and using \eqref{eq:scales} gives \eqref{eq:upper}. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:main}] If there were only finitely many strict adjacent decreases, then \(T_{k+1}\ge T_k\) for all sufficiently large \(k\). Choose arbitrarily large \(j\) from Lemma~\ref{lem:lower}. Let \(Y\) be a dyadic integer with \(j\le Y<2j\), and choose \(k\in\mathcal G\cap[Y,2Y]\). Then \(j\le k<4j\), and \(\mathcal L(k)=\mathcal L(j)+o(1)\). Proposition~\ref{prop:upper} gives \[ \log T_k\le(4+o(1))j\exp\!\left(\frac25\mathcal L(j)\right), \] whereas \[ \log T_j\ge j\exp\!\left(\frac9{20}\mathcal L(j)\right). \] The latter is larger for all sufficiently large \(j\), contradicting \(T_j\le T_k\). Thus strict adjacent decreases occur infinitely often. \end{proof} \section*{Acknowledgment} The authors acknowledge extensive assistance from OpenAI's artificial-intelligence tools in developing and checking the mathematical argument and in preparing the exposition. \begin{thebibliography}{9} \bibitem{BK} A.~S.~Belov and S.~V.~Konyagin, \emph{An estimate of the free term of a non-negative trigonometric polynomial with integer coefficients}, Izvestiya: Mathematics \textbf{60} (1996), no.~6, 1123--1182. \href{https://doi.org/10.1070/IM1996v060n06ABEH000095} {doi:10.1070/IM1996v060n06ABEH000095}. \bibitem{EG} P.~Erd\H{o}s and R.~L.~Graham, \emph{Old and New Problems and Results in Combinatorial Number Theory}, Monographies de L'Enseignement Math\'ematique, vol.~28, Universit\'e de Gen\`eve, Geneva, 1980. \href{https://fanchung.ucsd.edu/ron/papers/80_11_number_theory.pdf}{Author's archived copy}. \bibitem{FP} Kai (Steve) Fan and Paul Pollack, \emph{The maximal order of the shifted-prime divisor function}, Integers \textbf{26A} (2026), \href{https://math.colgate.edu/~integers/aap9/aap9.pdf}{Article A9}. \href{https://doi.org/10.5281/zenodo.23017984}{doi:10.5281/zenodo.23017984}. \bibitem{Kim} D.~Kim, \emph{On the largest integer that is not a sum of distinct positive \(n\)th powers}, Journal of Integer Sequences \textbf{20} (2017), Article 17.7.5. \href{https://cs.uwaterloo.ca/journals/JIS/VOL20/Kim/kim6.pdf}{Journal version}. \bibitem{Lev} V.~F.~Lev, \emph{Consecutive integers in high-multiplicity sumsets}, Acta Mathematica Hungarica \textbf{129} (2010), 245--253. \href{https://doi.org/10.1007/s10474-010-0026-6}{doi:10.1007/s10474-010-0026-6}. \href{https://arxiv.org/abs/0806.4580v1}{arXiv:0806.4580v1}. \bibitem{NT} M.~Nair and G.~Tenenbaum, \emph{Short sums of certain arithmetic functions}, Acta Mathematica \textbf{180} (1998), 119--144. \href{https://tenenb.perso.math.cnrs.fr/PPP/ShortSums.pdf}{Author's version}. \bibitem{Shiu} P.~Shiu, \emph{A Brun--Titchmarsh theorem for multiplicative functions}, Journal f\"ur die reine und angewandte Mathematik \textbf{313} (1980), 161--170. \href{https://doi.org/10.1515/crll.1980.313.161}{doi:10.1515/crll.1980.313.161}. \end{thebibliography} \end{document}