WorksMathematics
Infinitely many decreases in the thresholds for sums of distinct powers
Abstract
Let be the least integer such that every integer at least is a sum of distinct positive th powers. We prove for infinitely many . An upper estimate on degrees in every sufficiently large dyadic interval follows from cyclotomic recurrences, exact reduction of rational Fourier phases, and collision estimates for subset sums modulo reserved powers. A lower estimate on infinitely many other degrees follows from the shifted-prime divisor bound of Fan and Pollack. Comparing the two estimates rules out eventual monotonicity.
The problem and the two estimates
For , write
The empty sum is allowed. Let , and put
The finiteness of for every positive is classical; see Kim [4]. We have . If , the integer two is not representable, so . For , using the largest exceptional integer instead subtracts one from each threshold, and therefore preserves adjacent comparisons. The question considered here is Erdős problem 345; see Erdős and Graham [2 p. 55].
Theorem 1.1. There are infinitely many positive integers for which .
All logarithms are natural, and for . 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.
Proposition 1.2. There is a set meeting every sufficiently large interval such that
This is proved in § 2–§ 7. For comparison, define
Fan and Pollack [3 Theorem 1] prove unconditionally that
for infinitely many . Only this infinitely-often conclusion is used.
Lemma 1.3. There are arbitrarily large such that
Proof. Choose satisfying (1.2), and put and . For every integer , . Modulo a prime factor of , this follows from if ; if , both sides vanish. The factors of are distinct.
Set and . Subset sums of powers with bases at most have residues in . Choose with
For large and , this is positive. It cannot be represented: a base larger than contributes too much, while the smaller bases cannot produce its residue. Hence
Since , , and , the fixed factors and the error are absorbed by the strict difference of constants. This proves (1.3). □
Flat products and integral recurrences
For , put . Let denote the shift operator on sequences: , and write . A rational polynomial is called integer-valued if its values at all integers are integers.
We use the following consequence of Belov and Konyagin [1 Corollary 0.2]. For every positive integer , there are nonincreasing nonnegative integers , of sum , and a real , such that
Lemma 2.1. For every , one can choose
so that
The constant and leading coefficients of have absolute value one.
Proof. Take the coefficients from (2.1). For ,
Also
Taking , for , gives . By Parseval, , proving (5); is immediate.
The product
has nonnegative integral coefficients. Let , . Then and , which divides by the multinomial formula. Finally, the block of indices ending at has coefficient sum at least . Adding the disjoint blocks proves (7). The remaining assertions follow from the product.
Lemma 2.2 (Rounding to an exact recurrence). Let be positive integers and put . Suppose , has degree at most , and
If grows faster than every fixed power of , there is an integer sequence , defined on all of , with , and an interval of consecutive integers such that
Proof. On the prefix choose nearest to , and put . Since on , . The root of at one has order , so . The residuals are integers, and the finite convolution inequality gives
Write . The valid residual positions are . If is the number of nonzero residuals, then . The zero residuals split into at most runs, so one run has length at least
Here and . The hypothesis on therefore gives a run of zero residuals, beginning at an integer , with , after enlarging .
Use the rounded values at to define an exact recurrence sequence. The leading coefficient of is a unit, so the zero residual equations force agreement with the rounded values throughout . Its constant coefficient is also a unit, so the extension to all of is integral in both directions. This whole interval lies in the original prefix. Restricting the error estimate to it proves the assertion.
Cyclotomic heights on a long interval
Write
Every sequence annihilated by is a sum , where the roots of unity have orders at most , and the degree of each polynomial is less than the multiplicity of its root.
Lemma 3.1 (Long-interval separation). For such a sum , let be the leading coefficient of a nonzero component of degree . On an interval of consecutive integers,
provided .
Proof. Translate the interval to start at zero. Let be the shifted Legendre polynomials orthonormal on , with leading coefficient . Writing in terms of the usual Legendre polynomial, one has
For example, the derivative bound follows by summing and using on . Products of two basis polynomials of degrees less than therefore have supremum and total variation .
Use the basis , with the appropriate degrees at each root. Its dimension is at most . At a common frequency, the normalized discrete inner product differs from the continuous one by . Distinct root frequencies are separated modulo one by at least . Summation by parts and the geometric-series bound therefore give off-diagonal entries . The row-sum estimate shows that the normalized Gram matrix has all eigenvalues at least under the stated length condition. The coefficient of the top basis vector in the chosen component is
Its contribution to the Gram lower bound gives (9). Translation multiplies the top coefficient by a number of absolute value one and does not change this estimate. □
Lemma 3.2 (Integer recurrence height). If a nonzero integral sequence is annihilated by , and is its largest component degree, then
whenever satisfies Lemma 3.1.
Proof. Translate the interval to start at zero. The recurrence first gives a generating-function denominator equal to the reciprocal of . Since , a change of sign in the numerator writes the generating function as , with of degree less than . Cancel the monic common cyclotomic factors. Gauss’s lemma gives with relatively prime integral polynomials. Choose a primitive root at which has multiplicity . The absolute value of the top component coefficient is
The numerator is a nonzero algebraic integer, and its geometric mean over primitive conjugates is at least one.
If , then . Regularized values of integral polynomials are algebraic integers: successive division by the monic factor preserves algebraic integrality. Thus the geometric mean of is at least one. Each vanishing binomial in contributes a derivative of absolute value at most , and each nonvanishing one contributes at most two. The geometric mean of is consequently at most . Some conjugate top coefficient has absolute value at least . Insert it into (9), use , and take logarithms. □
Lemma 3.3 (Refined cyclotomic height). Let , , with growing faster than every fixed power of . Suppose , , and has degree at most , , with
If its sine energy on is at most , there is a nonzero rational sequence , annihilated by , such that is integral and congruent to globally. If denotes its multiplicity at primitive th roots, then
In particular a multiplicity vanishes if its upper bound is less than one.
Proof. Apply Lemma 2.2 and put . This gives all the integrality, congruence, and energy assertions, with energy at most on an interval of length . The sequence is nonzero by its congruence at . Its least annihilator is an integral product of cyclotomic factors dividing , by cancellation in the generating function of .
Put . At a nontrivial root the components of are the negatives of those of the integer sequence , since contributes only at one. Fix primitive order with . We refine the denominator estimate in the preceding proof. There are at most vanishing factors, by (7), and their derivatives have absolute value at most .
For a nonvanishing factor , put . Its geometric mean over primitive th roots is . This is one unless is a prime power, when its logarithm is . Such factors have ; by (7) their number with multiplicity is at most . The total logarithmic contribution of nonvanishing factors is thus at most
Cancellation decreases the geometric-mean denominator bound, as above, and . Some conjugate top coefficient therefore satisfies
The interval-length condition in Lemma 3.1 is polynomial in , and hence holds here. It follows that
If , then , so . Now , , and . This proves (11) without an additive constant.
Apply Lemma 3.2 to for the remaining bound. Its energy is at most , and its largest component degree is at least . This gives (12); in particular the term involving is not discarded.
Exact arithmetic of polynomial reductions
For , define
where is a Stirling number of the second kind. In particular , since . The Newton expansion shows that
Indeed, the forward differences above degree must vanish modulo ; conversely, the truncation supplies . This formulation applies on all integers, including negative ones.
Lemma 4.1 (A product bound for the reduction modulus). For , put
Then
Proof. Start with , and recursively put . Then , and the canonical truncation
is congruent to on the integers. For every nonnegative integer , the polynomial is integer-valued and divisible by at every integer. Its th forward difference is . Thus
Since , multiplication gives the first assertion. Write . A prime divides exactly when . Necessity follows by testing units modulo ; sufficiency also includes nonunits, because . Testing bounds by . For odd , testing bounds it by . For , testing bounds it by . These lifting identities show that . Taking logarithms gives
We next control a prime-power modulus from the cyclotomic multiplicities of an annihilator. Here denotes the -adic valuation.
Lemma 4.2 (Dilation of an integral recurrence). Let be prime, , and
If for all , then
Proof. Put . The rational -recurrence sequences on have an integral lattice identified with by their first entries, since the leading and constant coefficients of are units. For a positive integer prime to , the dilation preserves this space and its integral lattice: on the complex basis , it permutes primitive roots of a fixed -power order and multiplies the degree- vector by .
Extend by the recurrence to an integral sequence . The assumed congruence makes for all integers . The cases are impossible, because the values at zero and one are respectively zero and one. Thus the initial vector contains a unit, and
If is the characteristic polynomial of this integral matrix, Cayley–Hamilton gives
For odd , choose primitive modulo , hence modulo every . The primitive th roots form one cycle of length . Their degree- characteristic factor is , for . At , its valuation is
The root-one factor has valuation zero unless ; in that case its valuation is . None of these factors vanishes, since .
For any interval of consecutive positive integers ending at , counting multiples of gives
For the root-one contribution, restrict to the single residue class , and divide its terms by . The resulting consecutive integers number at most . Applying (18) gives a contribution at most . The other cycles contribute at most . Equation (17) proves the claim for odd .
For , take . There are at most two cycles at each primitive th order, of length for ; the orders two and four are handled directly. The valuation of each factor is at most . The root-one contribution is . Summing with (18) proves the same bound. □
Lemma 4.3 (One contraction step). Under the hypotheses of Lemma 3.3, if the sine energy is at most , there is an integer satisfying
such that, whenever , one has . All constants are uniform for .
Proof. Choose
large enough that Lemma 3.3 gives and . These multiplicities are less than for large , since and dominates powers of .
Fix . Factor the integral annihilator of as , where contains precisely its root-one and -power cyclotomic factors. Then is a unit modulo : is one unless is a prime power, and the prime-power factors in correspond to primes other than . Put and write . On polynomial sequences of degree at most modulo , . An explicit inverse is therefore
Because and , the unit may be cancelled. Apply the displayed inverse, which commutes with , to obtain
Apply Lemma 4.2. The largest is at most , and . Hence
If , all nontrivial -power roots are absent. Then ; necessarily , and
Set , with fixed and sufficiently large. For , the elementary bound , valid here since , dominates (20). Thus the part of supported on primes at most divides . Now assume , as in the conclusion. The remaining prime powers divide , because and . Each , , is divisible by . Thus the small-prime part also divides . The two parts are coprime, so . The chosen value of satisfies (19).
Good degrees and the exact-center estimate
Fix throughout
Lemma 5.1 (Simultaneous degree selection). For every sufficiently large dyadic , all but integers satisfy
Proof. Let be the divisor function and the ordered -fold divisor function. For every integer ,
For a prime power exponent , this follows by induction from
each factor increases with , and the product at is . Multiplicativity completes the proof. Counting ordered factorizations and summing the first factors harmonically gives, with no constant depending on ,
Since a prime predecessor divisor of is at most , . Take
By (23) and Markov’s inequality, the number of with is at most
Indeed , so the positive logarithmic error is , while . The union over at most shifts has size , because . All shifted arguments are positive for large .
Let be the union of the sets selected in Lemma 5.1, and for put
where is any fixed constant. Then
In particular and exceed every fixed power of .
We will also use the following fixed-parameter consequence of Shiu’s short-interval estimate [7], in the form stated by Nair and Tenenbaum [6 Introduction]:
For clarity, its parameters are fixed: apply the theorem to the multiplicative function , modulus one, and interval , with exponent . This interval has length and lies at height comparable to . The hypotheses and hold. The resulting bound is . Neither the function nor the interval exponent varies with .
Proposition 5.2 (Exact-center energy). For all sufficiently large , and every reduced fraction with
Here may be chosen as in (24) for any fixed .
Proof. Suppose the energy is at most . Begin with , of degree . Lemma 4.3 and give a new degree
In particular , and . By (13), replace by
Its difference from is integral at every integer, so the sine energy has not changed. The modulus and prefix also remain unchanged. Every subsequent invocation of the rounding lemma starts again on this same prefix, so its interval-length loss is not accumulated across steps.
Whenever and , (15), , and (26) give
A further contraction therefore gives
for large , uniformly in this range. After finitely many steps the degree is at most . Choose the dyadic for which (22) holds for . Put . For every , the same bound (22) gives
The contraction estimate now reads
The constants are fixed. Since , . Thus , whereas ; the inequality gives , uniformly over the selected degrees. Take large enough that . While , this gives , so the same exact replacement remains valid. Eventually with . A reduction to degree zero would already give , which is impossible. At the terminal positive degree,
Thus .
Return to the original phase, not to an individual cyclotomic component. Each full block of consecutive inputs contains an . Since ,
Consequently the original energy is at least
by (25) and (29). This is the desired contradiction. □
From rational centers to collision estimates
Retain and from (24). Put
Thus is the reserved set of bases and is the available initial population. Write
For , let , and define
We will prove
Notice that and for large . Also , so for . Since , we have uniformly over the reserved bases.
Lemma 6.1 (A common rational approximation). Let be fixed. There are a constant and an integer , independent of , such that
for some integer . The assertion is uniform in .
Proof. The population is independent of . Add back the at most 256 excluded terms and use the prefix ; the term at zero vanishes. Its energy is at most .
Take from Lemma 2.1, and . Round to integers . As in Lemma 2.2, the number of nonzero integer residuals is at most . We have , including when . The zero-run count in Lemma 2.2 therefore provides consecutive valid residual positions, say .
Put . As , the integers are defined for every . On the residual positions, . Successive finite differences consequently show that all these values agree with one rational polynomial of degree at most . Its Newton coefficients about the integer are integral, so its coefficient of is for some .
The polynomial has coefficient at . Since has nonnegative coefficients of sum , the finite convolution inequality bounds the squared error of their difference, on the first positions of this interval, by .
Take . The th difference with step of this error polynomial is the constant
There are at least valid starting points. The difference operator has coefficient norm , so
Using , we obtain
Take . All filters and this denominator depend only on . □
Lemma 6.2 (Small symmetric numerators). Put . Uniformly for ,
Proof. By symmetry take and put . Then , and the sine phase is .
If , use the interval
It has integer points, all in for large : its upper endpoint is at most , and its lower endpoint exceeds . On it the sine square is at least . Thus .
If , set . For , use the disjoint intervals
The mean value theorem gives
Their integer points lie in . Indeed their lower endpoints exceed , while their upper endpoints are at most eventually, because . Each interval contains at least half its length in integers, with sine square at least . Therefore
The first case satisfies the same final bound, since .
Now . There are fewer than frequencies, and by a fixed factor. Hence their total contribution is bounded by
□
Proposition 6.3. The uniform collision estimate (30) holds.
Proof. Choose a fixed sufficiently large. Frequencies with have total contribution at most
Every remaining frequency is in an arc
by Lemma 6.1. We have , and . Thus at most centers are relevant in or adjacent to . Each arc contains at most points of the actual grid. The total
number of grid points in these arcs is therefore at most . Consequently those among them with also contribute , for a fixed .
It remains to consider . Choose the constant in (24) larger than . On the prefix , replacing the frequency by its center changes the square root of the sine energy by at most
If the center is not an integer, its reduced denominator is a divisor of , and Proposition 5.2 gives center energy greater than . Removing the at most 256 auxiliary terms leaves
for large , contradicting .
If the center is an integer, then . Since dominates and , we have eventually. These frequencies lie in the range of Lemma 6.2, whose total contribution is . All cases have now been covered. □
A represented interval and the infinite tail
The last step converts (30) into ordinary subset sums, with no repetition of bases.
Lemma 7.1. For all sufficiently large , there are pairwise disjoint sets of bases, all at most , whose power subset-sum sets satisfy
No is contained in an arithmetic progression of integer difference greater than one.
Proof. Choose disjoint random -subsets of , uniformly. This is possible since , and each marginal is a uniform -subset. Independence between the is not required.
For a fixed , choose each subset with probability ; equivalently, include its bases independently with probability . Let
This is a distribution on residues, not the uniform distribution on distinct represented values. Its Fourier transform is
Finite Fourier orthogonality therefore gives the collision excess
For , the expectation of the product over a uniform -subset equals , where is the elementary symmetric polynomial of degree . Maclaurin’s inequality bounds this by .
Write . If the support has fewer than elements, Cauchy–Schwarz gives , so the collision excess is greater than three. For each fixed group, the expected number of such bad reserved bases is at most . Markov’s inequality bounds the probability of more than bad bases by . A union bound over the fixed groups proves that, with probability , every group has at least good bases.
We may simultaneously require
Indeed the expectation is at most , because and . Sampling without replacement has variance at most . Chebyshev’s inequality makes the failure probability at most , uniformly in the fixed number of groups. Fix a realization with both properties.
Allocate good reserved bases to each group, with no base used twice. Before any individual choice, fewer than bases have been used, whereas the group in question has at least good choices. The greedy allocation is therefore possible; the completed allocation uses exactly bases. If a finite integer set occupies residue classes modulo a positive integer , then
For each occupied residue, its largest element supplies a new element after addition of . Applying this with shows that each allocated base increases the subset-sum cardinality by at least . The original support is retained after earlier additions, so the support condition continues to hold. After additions the cardinality is at least .
Finally add the distinct auxiliary pairs
to the 128 groups, one pair per group. They are disjoint from and from the reserved bases. Each resulting subset-sum set contains zero and two coprime th powers, so it cannot lie in a proper integer arithmetic progression. The initial span in (32) is at most eventually, because . The reserved bases add at most , and the two auxiliary powers add at most . This proves (31). □
We use Lev’s consecutive-interval theorem in the following sufficient form [5 Corollary 1]. If are subsets of , each of size at least , none contained in an integer arithmetic progression of difference greater than one, and
then their sumset contains consecutive integers. Here the length of a block means its largest element minus its smallest, as in Lev’s statement.
Proof of Proposition 1.2. Apply this result to Lemma 7.1, with
The ratio tends to 32, so the strict inequality has a fixed margin. The sumset contains an interval with
Also . Every integer in this interval is a sum of distinct th powers with bases at most , because the groups of bases are disjoint.
Adjoin the unused powers with bases . If the currently represented interval is and a new power satisfies , its translate joins it without a gap, producing . Initially . If , then the new length is at least , since and . 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 consequently belongs to one finite-stage interval, and is represented by finitely many distinct positive th powers. We have proved
Taking logarithms and using (25) gives (1). □
Proof of Theorem 1.1. If there were only finitely many strict adjacent decreases, then for all sufficiently large . Choose arbitrarily large from Lemma 1.3. Let be a dyadic integer with , and choose . Then , and . Proposition 1.2 gives
whereas
The latter is larger for all sufficiently large , contradicting . Thus strict adjacent decreases occur infinitely often. □
Acknowledgment
The authors acknowledge extensive assistance from OpenAI’s artificial-intelligence tools in developing and checking the mathematical argument and in preparing the exposition.
References
References
- [1]A. S. Belov and S. V. Konyagin, An estimate of the free term of a non-negative trigonometric polynomial with integer coefficients, Izvestiya: Mathematics 60 (1996), no. 6, 1123–1182. doi:10.1070/IM1996v060n06ABEH000095.DOI
- [2]P. Erdős and R. L. Graham, Old and New Problems in Combinatorial Number Theory, Monographies de L’Enseignement Mathématique, vol. 28, Université de Genève, Geneva, 1980. Author’s archived copy.
- [3]Kai (Steve) Fan and Paul Pollack, The maximal order of the shifted-prime divisor function, Integers 26A (2026), Article A9. doi:10.5281/zenodo.23017984.
- [4]D. Kim, On the largest integer that is not a sum of distinct positive nth powers, Journal of Integer Sequences 20 (2017), Article 17.7.5. Journal version.
- [5]V. F. Lev, Consecutive integers in high-multiplicity sumsets, Acta Mathematica Hungarica 129 (2010), 245–253. doi:10.1007/s10474-010-0026-6. arXiv:0806.4580v1.DOI
- [6]M. Nair and G. Tenenbaum, Short sums of certain arithmetic functions, Acta Mathematica 180 (1998), 119–144. Author’s version.DOI
- [7]P. Shiu, A Brun–Titchmarsh theorem for multiplicative functions, Journal für die reine und angewandte Mathematik 313 (1980), 161–170. doi:10.1515/crll.1980.313.161.DOI