betaFeedback

WorksMathematics

Infinitely many decreases in the thresholds for sums of distinct powers

Abstract

Let TkT_k be the least integer such that every integer at least TkT_k is a sum of distinct positive kkth powers. We prove Tk>Tk+1T_k>T_{k+1} for infinitely many kk. 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 A⊆Z≥0A \subseteq\mathbb{Z}_{\geq0}, write

Σ(A)={∑a∈Ba:B⊆A, B finite}.\Sigma(A)=\left\{\sum_{a\in B}a:B\subseteq A,\ B\text{ finite}\right\}.

The empty sum is allowed. Let Pk={nk:n∈N, n≥1}P_k=\{n^k:n\in\mathbb{N},\ n\geq1\}, and put

Tk=min⁡{T∈Z≥0:[T,∞)∩Z⊆Σ(Pk)}.T_k=\min\{T\in\mathbb{Z}_{\geq0}:[T,\infty)\cap\mathbb{Z}\subseteq\Sigma(P_k)\}.

The finiteness of TkT_k for every positive kk is classical; see Kim [4]. We have T1=0T_1=0. If k≥2k\geq2, the integer two is not representable, so Tk≥3T_k\geq3. For k≥2k\geq2, 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 kk for which Tk>Tk+1T_k>T_{k+1}.

All logarithms are natural, and L(x)=log⁡x/log⁡log⁡x\mathcal{L}(x)=\log x/\log\log x for x>ex>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.

Proposition 1.2. There is a set G⊆NG\subseteq\mathbb{N} meeting every sufficiently large interval [2m,2m+1][2^m,2^{m+1}] such that

log⁡Tk≤(1+o(1))kexp⁡(25L(k))(k∈G).(1)\log T_k\leq(1+o(1))k\exp\left(\frac{2}{5}\mathcal{L}(k)\right)\qquad(k\in G). \tag*{(1)}

This is proved in § 2–§ 7. For comparison, define

ω∗(n)=#{p:p prime, p−1∣n},D(n)=∏p primep−1∣np.\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 [3 Theorem 1] prove unconditionally that

ω∗(n)>exp⁡((0.6736log⁡2)L(n))(2)\omega^*(n) > \exp((0.6736\log2)\mathcal{L}(n)) \tag*{(2)}

for infinitely many nn. Only this infinitely-often conclusion is used.

Lemma 1.3. There are arbitrarily large jj such that

log⁡Tj≥jexp⁡(920L(j)).(3)\log T_j \ge j\exp\left(\frac{9}{20}\mathcal{L}(j)\right). \tag*{(3)}

Proof. Choose nn satisfying (1.2), and put j=n+1j=n+1 and Q=D(n)Q=D(n). For every integer bb, bj≡b(modQ)b^j \equiv b \pmod Q. Modulo a prime factor pp of QQ, this follows from p−1∣np-1\mid n if p∤bp\nmid b; if p∣bp\mid b, both sides vanish. The factors of QQ are distinct.

Set H=⌊Q⌋H=\lfloor\sqrt{Q}\rfloor and S=H(H+1)/2<QS=H(H+1)/2<Q. Subset sums of powers with bases at most HH have residues in {0,…,S}\{0,\ldots,S\}. Choose M≡S+1(modQ)M\equiv S+1\pmod Q with

(H+1)j−Q≤M<(H+1)j.(H+1)^j-Q\le M<(H+1)^j.

For large QQ and j≥3j\ge3, this is positive. It cannot be represented: a base larger than HH contributes too much, while the smaller bases cannot produce its residue. Hence

log⁡Tj≥log⁡M≥j2log⁡Q−O(j).\log T_j\ge\log M\ge\frac{j}{2}\log Q-O(j).

Since log⁡Q≥(log⁡2)ω∗(n)\log Q\ge(\log2)\omega^*(n), 0.6736log⁡2>9/200.6736\log2>9/20, and L(n+1)−L(n)→0\mathcal{L}(n+1)-\mathcal{L}(n)\to0, the fixed factors and the error are absorbed by the strict difference of constants. This proves (1.3). □

Flat products and integral recurrences

For P(z)=∑hwhzhP(z)=\sum_h w_hz^h, put ∥P∥1=∑h∣wh∣\lVert P\rVert_1=\sum_h|w_h|. Let EE denote the shift operator on sequences: (Ex)n=xn+1(Ex)_n=x_{n+1}, and write Δ=E−1\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 [1 Corollary 0.2]. For every positive integer JJ, there are nonincreasing nonnegative integers a1,…,aJa_1,\ldots,a_J, of sum JJ, and a real a0a_0, such that

a0+∑h=1Jahcos⁡(hθ)≥0(θ∈R),a0≤232(1+log⁡J)5.(4)a_0+\sum_{h=1}^{J}a_h\cos(h\theta)\ge0\quad(\theta\in\mathbb{R}),\qquad a_0\le2^{32}(1+\log J)^5. \tag*{(4)}

Lemma 2.1. For every J≥1J\ge1, one can choose

PJ(z)=∏h=1J(1−zh)ah=(1−z)JQJ(z)∈Z[z]P_J(z)=\prod_{h=1}^{J}(1-z^h)^{a_h}=(1-z)^JQ_J(z)\in\mathbb{Z}[z]

so that

deg⁡PJ≤J2,log⁡∥PJ∥1≤C(1+log⁡J)6,(5)\deg P_J\le J^2,\qquad\log\lVert P_J\rVert_1\le C(1+\log J)^6, \tag*{(5)}
QJ∈Z≥0[z],MJ:=QJ(1)=∏hhah∣J!,(6)Q_J\in\mathbb{Z}_{\ge0}[z],\qquad M_J:=Q_J(1)=\prod_h h^{a_h}\mid J!, \tag*{(6)}
∑h<Jv∣hah≤J/v(v≥1).(7)\sum_{\substack{h<J\\v\mid h}}a_h\le J/v\qquad(v\ge1). \tag*{(7)}

The constant and leading coefficients of PJP_J have absolute value one.

Proof. Take the coefficients from (2.1). For 0<ρ<10<\rho<1,

log⁡∣PJ(ρeiθ)∣=−∑m≥1ρmm∑hahcos⁡(hmθ)≤a0log⁡11−ρ.\log\lvert P_J(\rho e^{i\theta})\rvert=-\sum_{m\ge1}\frac{\rho^m}{m}\sum_h a_h\cos(hm\theta)\le a_0\log\frac{1}{1-\rho}.

Also

∣1−eit∣≤21+ρ∣1−ρeit∣.\lvert1-e^{it}\rvert\le\frac{2}{1+\rho}\lvert1-\rho e^{it}\rvert.

Taking ρ=1−J−1\rho=1-J^{-1}, for J≥2J\ge2, gives log⁡∥PJ∥∞≤C(1+log⁡J)6\log\lVert P_J\rVert_\infty\le C(1+\log J)^6. By Parseval, ∥PJ∥1≤deg⁡PJ+1∥PJ∥∞\lVert P_J\rVert_1\le\sqrt{\deg P_J+1}\lVert P_J\rVert_\infty, proving (5); J=1J=1 is immediate.

The product

QJ(z)=∏h(1+z+⋯+zh−1)ahQ_J(z)=\prod_h(1+z+\cdots+z^{h-1})^{a_h}

has nonnegative integral coefficients. Let λi=#{h:ah≥i}\lambda_i=\#\{h:a_h\ge i\}, 1≤i≤a11\le i\le a_1. Then ∑iλi=J\sum_i\lambda_i=J and MJ=∏iλi!M_J=\prod_i\lambda_i!, which divides J!J! by the multinomial formula. Finally, the block of vv indices ending at iviv has coefficient sum at least vaivva_{iv}. Adding the disjoint blocks proves (7). The remaining assertions follow from the product.

Lemma 2.2 (Rounding to an exact recurrence). Let k,Xk,X be positive integers and put K=1+log⁡kK=1+\log k. Suppose 1≤d≤k1\le d\le k, F∈R[x]F\in\mathbb{R}[x] has degree at most dd, and

∑0≤n<Xsin⁡2(πF(n))≤k2.\sum_{0\le n<X}\sin^2(\pi F(n))\le k^2.

If log⁡X\log X grows faster than every fixed power of KK, there is an integer sequence mnm_n, defined on all of Z\mathbb{Z}, with Pd+1(E)m=0P_{d+1}(E)m=0, and an interval II of LL consecutive integers such that

∑n∈I∣F(n)−mn∣2≤k2/4,L≥Xexp⁡(−CK6).(8)\sum_{n\in I}\lvert F(n)-m_n\rvert^2\le k^2/4,\qquad L\ge X\exp(-CK^6). \tag*{(8)}

Proof. On the prefix choose mnm_n nearest to F(n)F(n), and put ϵn=F(n)−mn\epsilon_n=F(n)-m_n. Since sin⁡(πt)≥2t\sin(\pi t)\ge2t on 0≤t≤1/20\le t\le1/2, ∑nϵn2≤k2/4\sum_n\epsilon_n^2\le k^2/4. The root of Pd+1P_{d+1} at one has order d+1d+1, so Pd+1(E)F=0P_{d+1}(E)F=0. The residuals Pd+1(E)mP_{d+1}(E)m are integers, and the finite convolution inequality gives

∑n∣Pd+1(E)mn∣2≤∥Pd+1∥12∑nϵn2≤∥Pd+1∥12k2/4.\sum_n\lvert P_{d+1}(E)m_n\rvert^2\le\lVert P_{d+1}\rVert_1^2\sum_n\epsilon_n^2\le\lVert P_{d+1}\rVert_1^2k^2/4.

Write D0=deg⁡Pd+1D_0=\deg P_{d+1}. The valid residual positions are 0,…,X−D0−10,\ldots,X-D_0-1. If B0B_0 is the number of nonzero residuals, then B0≤∥Pd+1∥12k2/4B_0\le\lVert P_{d+1}\rVert_1^2k^2/4. The zero residuals split into at most B0+1B_0+1 runs, so one run has length at least

X−D0−B0B0+1.\frac{X-D_0-B_0}{B_0+1}.

Here D0≤(d+1)2D_0\le(d+1)^2 and B0+1≤exp⁡(CK6)B_0+1\le\exp(CK^6). The hypothesis on XX therefore gives a run of rr zero residuals, beginning at an integer ss, with r≥Xexp⁡(−CK6)r\ge X\exp(-CK^6), after enlarging CC.

Use the D0D_0 rounded values at s,…,s+D0−1s,\ldots,s+D_0-1 to define an exact recurrence sequence. The leading coefficient of Pd+1P_{d+1} is a unit, so the rr zero residual equations force agreement with the rounded values throughout s,…,s+r+D0−1s,\ldots,s+r+D_0-1. Its constant coefficient is also a unit, so the extension to all of Z\mathbb{Z} 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

P(z)=∏i=1J(1−zhi),1≤hi≤H,D=deg⁡P.P(z)=\prod_{i=1}^{J}(1-z^{h_i}),\qquad1\le h_i\le H,\qquad D=\deg P.

Every sequence annihilated by P(E)P(E) is a sum ∑ζpζ(n)ζ−n\sum_\zeta p_\zeta(n)\zeta^{-n}, where the roots of unity have orders at most HH, and the degree of each polynomial is less than the multiplicity of its root.

Lemma 3.1 (Long-interval separation). For such a sum xnx_n, let aζa_\zeta be the leading coefficient of a nonzero component of degree bb. On an interval of LL consecutive integers,

∑n∈I∣xn∣2≥L2b+1∣aζ∣22(2b+1)(2bb)2.(9)\sum_{n\in I} |x_n|^2 \ge\frac{L^{2b+1}|a_\zeta|^2}{2(2b+1)\binom{2b}{b}^2}. \tag*{(9)}

provided L≥CD(J+1)3H2L \ge CD(J+1)^3H^2.

Proof. Translate the interval to start at zero. Let ℓj\ell_j be the shifted Legendre polynomials orthonormal on [0,1][0,1], with leading coefficient 2j+1(2jj)\sqrt{2j+1}\binom{2j}{j}. Writing ℓj(x)=2j+1Pj(2x−1)\ell_j(x)=\sqrt{2j+1}P_j(2x-1) in terms of the usual Legendre polynomial, one has

∥ℓj∥∞≤2j+1,∥ℓj′∥∞≤j(j+1)2j+1.\|\ell_j\|_\infty\le\sqrt{2j+1}, \qquad\|\ell'_j\|_\infty\le j(j+1)\sqrt{2j+1}.

For example, the derivative bound follows by summing Pj′=∑0≤r<j,j−r odd(2r+1)PrP'_j=\sum_{\substack{0\le r<j,\,j-r\ {\rm odd}}}(2r+1)P_r and using ∣Pr∣≤1|P_r|\le1 on [−1,1][-1,1]. Products of two basis polynomials of degrees less than JJ therefore have supremum and total variation O((J+1)3)O((J+1)^3).

Use the basis ℓj(n/L)ζn\ell_j(n/L)\zeta^n, with the appropriate degrees at each root. Its dimension is at most DD. At a common frequency, the normalized discrete inner product differs from the continuous one by O((J+1)3/L)O((J+1)^3/L). Distinct root frequencies are separated modulo one by at least H−2H^{-2}. Summation by parts and the geometric-series bound therefore give off-diagonal entries O((J+1)3H2/L)O((J+1)^3H^2/L). The row-sum estimate shows that the normalized Gram matrix has all eigenvalues at least 1/21/2 under the stated length condition. The coefficient of the top basis vector in the chosen component is

aζLb2b+1(2bb).\frac{a_\zeta L^b}{\sqrt{2b+1}\binom{2b}{b}}.

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 xx is annihilated by P(E)P(E), and bb is its largest component degree, then

(2b+1)log⁡L≤log⁡(∑n∈I∣xn∣2)+CJlog⁡(2H(J+1))(10)(2b+1)\log L \le\log\left(\sum_{n\in I}|x_n|^2\right)+CJ\log(2H(J+1)) \tag*{(10)}

whenever LL 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 PP. Since zDP(1/z)=(−1)JP(z)z^DP(1/z)=(-1)^JP(z), a change of sign in the numerator writes the generating function as A/PA/P, with A∈Z[z]A\in\mathbb{Z}[z] of degree less than DD. Cancel the monic common cyclotomic factors. Gauss’s lemma gives A0/CA_0/C with relatively prime integral polynomials. Choose a primitive root ζ\zeta at which CC has multiplicity b+1b+1. The absolute value of the top component coefficient is

∣A0(ζ)∣∣Creg(ζ)∣ b!,Creg(z)=C(z)/(z−ζ)b+1.\frac{|A_0(\zeta)|}{|C_{\mathrm{reg}}(\zeta)|\,b!}, \qquad C_{\mathrm{reg}}(z)=C(z)/(z-\zeta)^{b+1}.

The numerator is a nonzero algebraic integer, and its geometric mean over primitive conjugates is at least one.

If P=GCP=GC, then Preg=GregCregP_{\mathrm{reg}}=G_{\mathrm{reg}}C_{\mathrm{reg}}. Regularized values of integral polynomials are algebraic integers: successive division by the monic factor z−ζz-\zeta preserves algebraic integrality. Thus the geometric mean of ∣Greg(ζ)∣|G_{\mathrm{reg}}(\zeta)| is at least one. Each vanishing binomial in PP contributes a derivative of absolute value at most HH, and each nonvanishing one contributes at most two. The geometric mean of ∣Creg(ζ)∣|C_{\mathrm{reg}}(\zeta)| is consequently at most (2H)J(2H)^J. Some conjugate top coefficient has absolute value at least ((2H)JJ!)−1((2H)^J J!)^{-1}. Insert it into (9), use (2bb)≤4b\binom{2b}{b}\le4^b, and take logarithms. □

Lemma 3.3 (Refined cyclotomic height). Let K=1+log⁡kK=1+\log k, Z=log⁡XZ=\log X, with ZZ growing faster than every fixed power of KK. Suppose 2≤q∣k!(k+1)!2\le q\mid k!(k+1)!, gcd⁡(u,q)=1\gcd(u,q)=1, and F∈Q[x]F\in\mathbb{Q}[x] has degree at most dd, 1≤d≤k1\le d\le k, with

qF(n)∈Z,qF(n)≡unk(modq)(n∈Z).qF(n)\in\mathbb{Z},\qquad qF(n)\equiv un^k\pmod q\quad(n\in\mathbb{Z}).

If its sine energy on 0≤n<X0\le n<X is at most k2k^2, there is a nonzero rational sequence ϵ\epsilon, annihilated by Pd+1(E)P_{d+1}(E), such that qϵq\epsilon is integral and congruent to unk(modq)un^k\pmod q globally. If hth_t denotes its multiplicity at primitive ttth roots, then

ht≤CdKtZ(t≥2),(11)h_t\le\frac{CdK}{tZ}\qquad(t\ge2), \tag*{(11)}
h1≤C(log⁡q+dK)Z.(12)h_1\le\frac{C(\log q+dK)}{Z}. \tag*{(12)}

In particular a multiplicity vanishes if its upper bound is less than one.

Proof. Apply Lemma 2.2 and put ϵ=F−m\epsilon=F-m. This gives all the integrality, congruence, and energy assertions, with energy at most k2/4k^2/4 on an interval of length L≥Xexp⁡(−CK6)L\ge X\exp(-CK^6). The sequence is nonzero by its congruence at n=1n=1. Its least annihilator is an integral product of cyclotomic factors dividing Pd+1P_{d+1}, by cancellation in the generating function of qϵq\epsilon.

Put J=d+1J=d+1. At a nontrivial root the components of ϵ\epsilon are the negatives of those of the integer sequence mm, since FF contributes only at one. Fix primitive order t≥2t\ge2 with ht=b+1>0h_t=b+1>0. We refine the denominator estimate in the preceding proof. There are at most J/tJ/t vanishing factors, by (7), and their derivatives have absolute value at most JJ.

For a nonvanishing factor 1−ζh1-\zeta^h, put l=t/gcd⁡(t,h)>1l=t/\gcd(t,h)>1. Its geometric mean over primitive ttth roots is Φl(1)1/φ(l)\Phi_l(1)^{1/\varphi(l)}. This is one unless l=pal=p^a is a prime power, when its logarithm is log⁡p/φ(pa)\log p/\varphi(p^a). Such factors have t/pa∣ht/p^a\mid h; by (7) their number with multiplicity is at most Jpa/tJp^a/t. The total logarithmic contribution of nonvanishing factors is thus at most

∑pa∣tJpatlog⁡pφ(pa)≤2Jt∑pa∣tlog⁡p=2Jtlog⁡t.\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!≤JJ/tb!\le J^{J/t}. Some conjugate top coefficient therefore satisfies

∣aζ∣≥exp⁡(−C(J/t)log⁡(2J)).|a_{\zeta}|\ge\exp\left(-C(J/t)\log(2J)\right).

The interval-length condition in Lemma 3.1 is polynomial in kk, and hence holds here. It follows that

(2ht−1)log⁡L≤C(J/t)K+Clog⁡k.(2h_t-1)\log L\le C(J/t)K+C\log k.

If ht>0h_t>0, then t≤Jt\le J, so J/t≥1J/t\ge1. Now 2ht−1≥ht2h_t-1\ge h_t, J≤2dJ\le2d, and log⁡L∼Z\log L\sim Z. This proves (11) without an additive constant.

Apply Lemma 3.2 to qϵq\epsilon for the remaining bound. Its energy is at most q2k2/4q^2k^2/4, and its largest component degree is at least h1−1h_1-1. This gives (12); in particular the term involving log⁡q\log q is not discarded. □\square

Exact arithmetic of polynomial reductions

For 0≤d<k0\le d<k, define

Aj(k)=Δj(xk)∣x=0=j!S(k,j),Gd(k)=gcd⁡{Aj(k):d<j≤k},A_j(k)=\left.\Delta^j(x^k)\right|_{x=0}=j!S(k,j),\qquad G_d(k)=\gcd\{A_j(k):d<j\le k\},

where S(k,j)S(k,j) is a Stirling number of the second kind. In particular G0(k)=1G_0(k)=1, since A1(k)=1A_1(k)=1. The Newton expansion shows that

q∣Gd(k)⟺there exists an integer-valued P∈Q[x], deg⁡P≤d,nk≡P(n)(modq)for every n∈Z.(13)q\mid G_d(k)\qquad\Longleftrightarrow\qquad \begin{gathered} \text{there exists an integer-valued }P\in\mathbb{Q}[x],\ \deg P\le d,\\ n^k\equiv P(n)\pmod q\quad\text{for every }n\in\mathbb{Z}. \end{gathered} \tag*{(13)}

Indeed, the forward differences above degree dd must vanish modulo qq; conversely, the truncation ∑j=0dAj(k)(xj)\sum_{j=0}^{d} A_j(k) \binom{x}{j} supplies PP. This formulation applies on all integers, including negative ones.

Lemma 4.1 (A product bound for the reduction modulus). For 1≤d<k1 \le d < k, put

Fk,j=gcd⁡a∈Z≥0(ak−aj)(1≤j≤d).F_{k,j}=\gcd_{a\in\mathbb{Z}_{\ge0}}\left(a^k-a^j\right)\qquad(1\le j\le d).

Then

Gd(k)∣∏j=1dFk,j,Fk,j∣2(k−j)D(k−j).(14)G_d(k)\mid\prod_{j=1}^{d}F_{k,j},\qquad F_{k,j}\mid2(k-j)D(k-j). \tag*{(14)}

Proof. Start with qd=Gd(k)q_d=G_d(k), and recursively put qj−1=gcd⁡(qj,Aj(k))q_{j-1}=\gcd(q_j,A_j(k)). Then qj∣Gj(k)q_j\mid G_j(k), and the canonical truncation

Pj(x)=∑ℓ=0jAℓ(k)(xℓ)P_j(x)=\sum_{\ell=0}^{j}A_\ell(k)\binom{x}{\ell}

is congruent to xk(modqj)x^k\pmod{q_j} on the integers. For every nonnegative integer aa, the polynomial Pj(ax)−akPj(x)P_j(ax)-a^kP_j(x) is integer-valued and divisible by qjq_j at every integer. Its jjth forward difference is Aj(k)(aj−ak)A_j(k)(a^j-a^k). Thus

qj/qj−1∣Fk,j.q_j/q_{j-1}\mid F_{k,j}.

Since q0=1q_0=1, multiplication gives the first assertion. Write h=k−j>0h=k-j>0. A prime pp divides Fk,jF_{k,j} exactly when p−1∣hp-1\mid h. Necessity follows by testing units modulo pp; sufficiency also includes nonunits, because j≥1j\ge1. Testing a=pa=p bounds vp(Fk,j)v_p(F_{k,j}) by jj. For odd pp, testing a=1+pa=1+p bounds it by 1+vp(h)1+v_p(h). For p=2p=2, testing a=3a=3 bounds it by 2+v2(h)2+v_2(h). These lifting identities show that Fk,j∣2hD(h)F_{k,j}\mid2hD(h). Taking logarithms gives

log⁡Gd(k)≤dlog⁡(2k)+∑j=1dlog⁡D(k−j).(15)\log G_d(k)\le d\log(2k)+\sum_{j=1}^{d}\log D(k-j). \tag*{(15)}

We next control a prime-power modulus from the cyclotomic multiplicities of an annihilator. Here vpv_p denotes the pp-adic valuation.

Lemma 4.2 (Dilation of an integral recurrence). Let pp be prime, e≥1e\ge1, and

B(z)=(z−1)m0∏a=1AΦpa(z)ma,0≤ma≤k(0≤a≤A).B(z)=(z-1)^{m_0}\prod_{a=1}^{A}\Phi_{p^a}(z)^{m_a},\qquad0\le m_a\le k\quad(0\le a\le A).

If B(E)nk≡0(modpe)B(E)n^k\equiv0\pmod{p^e} for all n∈Zn\in\mathbb{Z}, then

e≤C{m0p−1+∑a=1A(a+1)ma+(A+1)(1+log⁡p(k+1))}.(16)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\}. \tag*{(16)}

Proof. Put DB=deg⁡BD_B=\deg B. The rational BB-recurrence sequences on Z\mathbb{Z} have an integral lattice identified with ZDB\mathbb{Z}^{D_B} by their first DBD_B entries, since the leading and constant coefficients of BB are units. For a positive integer gg prime to pp, the dilation Sg(x)n=xgnS_g(x)_n=x_{gn} preserves this space and its integral lattice: on the complex basis njζnn^j\zeta^n, it permutes primitive roots of a fixed pp-power order and multiplies the degree-jj vector by gjg^j.

Extend 0k,1k,…,(DB−1)k0^k,1^k,\ldots,(D_B-1)^k by the recurrence to an integral sequence yy. The assumed congruence makes yn≡nk(modpe)y_n\equiv n^k\pmod{p^e} for all integers nn. The cases DB=0,1D_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

Sgy≡gky(modpe).S_g y\equiv g^k y\pmod{p^e}.

If χg\chi_g is the characteristic polynomial of this integral matrix, Cayley–Hamilton gives

pe∣χg(gk).(17)p^e \mid\chi_g(g^k). \tag*{(17)}

For odd pp, choose gg primitive modulo p2p^2, hence modulo every pap^a. The primitive pap^ath roots form one cycle of length φ(pa)\varphi(p^a). Their degree-jj characteristic factor is Tφ(pa)−gjφ(pa)T^{\varphi(p^a)}-g^{j\varphi(p^a)}, for 0≤j<ma0 \le j < m_a. At T=gkT=g^k, its valuation is

a+vp(k−j).a+v_p(k-j).

The root-one factor T−gjT-g^j has valuation zero unless p−1∣k−jp-1 \mid k-j; in that case its valuation is 1+vp(k−j)1+v_p(k-j). None of these factors vanishes, since j<ma≤kj<m_a\le k.

For any interval of m≤km\le k consecutive positive integers ending at kk, counting multiples of pνp^\nu gives

∑j=0m−1vp(k−j)≤mp−1+log⁡p(k+1).(18)\sum_{j=0}^{m-1}v_p(k-j)\le\frac{m}{p-1}+\log_p(k+1). \tag*{(18)}

For the root-one contribution, restrict to the single residue class k−j≡0(modp−1)k-j\equiv0\pmod{p-1}, and divide its terms by p−1p-1. The resulting consecutive integers number at most m0/(p−1)+1m_0/(p-1)+1. Applying (18) gives a contribution at most Cm0/(p−1)+C(1+log⁡p(k+1))Cm_0/(p-1)+C(1+\log_p(k+1)). The other cycles contribute at most ∑a(a+1)ma+Alog⁡p(k+1)\sum_a(a+1)m_a+A\log_p(k+1). Equation (17) proves the claim for odd pp.

For p=2p=2, take g=5g=5. There are at most two cycles at each primitive 2a2^ath order, of length 2a−22^{a-2} for a≥3a\ge3; the orders two and four are handled directly. The valuation of each factor is at most C(a+1+v2(k−j))C(a+1+v_2(k-j)). The root-one contribution is 2+v2(k−j)2+v_2(k-j). 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 k2k^2, there is an integer M≥1M\ge1 satisfying

M≤CK2(log⁡q+dK)Z+CK4(19)M\le\frac{CK^2(\log q+dK)}{Z}+CK^4 \tag*{(19)}

such that, whenever M<kM<k, one has q∣GM(k)q\mid G_M(k). All constants are uniform for 1≤d≤k1\le d\le k.

Proof. Choose

T=C0log⁡q+dKZT=C_0\frac{\log q+dK}{Z}

large enough that Lemma 3.3 gives h1≤Th_1\le T and hpa≤T/pah_{p^a}\le T/p^a. These multiplicities are less than kk for large kk, since log⁡q=O(kK)\log q=O(kK) and ZZ dominates powers of KK.

Fix pe∥qp^e\Vert q. Factor the integral annihilator of ϵ\epsilon as BCBC, where BB contains precisely its root-one and pp-power cyclotomic factors. Then C(1)C(1) is a unit modulo pp: Φt(1)\Phi_t(1) is one unless tt is a prime power, and the prime-power factors in CC correspond to primes other than pp. Put c0=C(1)c_0=C(1) and write C(1+Δ)=c0+ΔR(Δ)C(1+\Delta)=c_0+\Delta R(\Delta). On polynomial sequences of degree at most kk modulo pep^e, Δk+1=0\Delta^{k+1}=0. An explicit inverse is therefore

c0−1∑j=0k(−c0−1ΔR(Δ))j.c_0^{-1}\sum_{j=0}^{k}(-c_0^{-1}\Delta R(\Delta))^j.

Because B(E)C(E)(qϵ)=0B(E)C(E)(q\epsilon)=0 and qϵ≡unk(modpe)q\epsilon\equiv un^k\pmod{p^e}, the unit uu may be cancelled. Apply the displayed inverse, which commutes with B(E)B(E), to obtain

B(E)nk≡0(modpe).B(E)n^k\equiv0\pmod{p^e}.

Apply Lemma 4.2. The largest aa is at most log⁡p(d+1)\log_p(d+1), and ∑a≥1(a+1)p−a=O((p−1)−1)\sum_{a\ge1}(a+1)p^{-a}=O((p-1)^{-1}). Hence

e≤CTp−1+CK2.(20)e\le\frac{CT}{p-1}+CK^2. \tag*{(20)}

If p>Tp>T, all nontrivial pp-power roots are absent. Then B=(z−1)h1B=(z-1)^{h_1}; necessarily h1≥1h_1\ge1, and

pe∣Gh1−1(k).p^e\mid G_{h_1-1}(k).

Set M=⌈C1(T+K2)K2⌉M=\lceil C_1(T+K^2)K^2\rceil, with C1C_1 fixed and sufficiently large. For p≤Tp\le T, the elementary bound vp(M!)≥M/(2p)v_p(M!)\ge M/(2p), valid here since M≥2pM\ge2p, dominates (20). Thus the part of qq supported on primes at most TT divides M!M!. Now assume M<kM<k, as in the conclusion. The remaining prime powers divide GM(k)G_M(k), because M≥h1M\ge h_1 and Gh1−1(k)∣GM(k)G_{h_1-1}(k)\mid G_M(k). Each Aj(k)=j!S(k,j)A_j(k)=j!S(k,j), j>Mj>M, is divisible by M!M!. Thus the small-prime part also divides GM(k)G_M(k). The two parts are coprime, so q∣GM(k)q\mid G_M(k). The chosen value of MM satisfies (19). □\square

Good degrees and the exact-center estimate

Fix throughout

c=25,a=110,β=1100.(21)c=\frac{2}{5},\qquad a=\frac{1}{10},\qquad\beta=\frac{1}{100}. \tag*{(21)}

Lemma 5.1 (Simultaneous degree selection). For every sufficiently large dyadic YY, all but o(Y)o(Y) integers k∈[Y,2Y]k\in[Y,2Y] satisfy

log⁡D(k−j)≤exp⁡(aL(Y))for 1≤j≤⌈(2Y)β⌉.(22)\log D(k-j)\le\exp(a\mathcal{L}(Y))\qquad\text{for }1\le j\le\lceil(2Y)^\beta\rceil. \tag*{(22)}

Proof. Let τ\tau be the divisor function and dzd_z the ordered zz-fold divisor function. For every integer m≥1m\ge1,

τ(n)m≤d2m(n).\tau(n)^m\le d_{2m}(n).

For a prime power exponent bb, this follows by induction from

(b+2z−1b)(b+z−1b)=∏i=0b−12z+iz+i≥b+1(z≥1);\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 zz, and the product at z=1z=1 is b+1b+1. Multiplicativity completes the proof. Counting ordered factorizations and summing the first z−1z-1 factors harmonically gives, with no constant depending on zz,

∑n≤Udz(n)≤U(1+log⁡U)z−1.(23)\sum_{n\le U}d_z(n)\le U(1+\log U)^{z-1}. \tag*{(23)}

Since a prime predecessor divisor of nn is at most n+1n+1, log⁡D(n)≤τ(n)log⁡(n+1)\log D(n)\le\tau(n)\log(n+1). Take

m=⌊log⁡log⁡Y−3log⁡log⁡log⁡Ylog⁡2⌋,BY=exp⁡(aL(Y))log⁡(2Y+1).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 (23) and Markov’s inequality, the number of n≤2Yn\le2Y with log⁡D(n)>exp⁡(aL(Y))\log D(n)>\exp(a\mathcal{L}(Y)) is at most

2Y(1+log⁡(2Y))2m−1BY−m=Y1−a/log⁡2+o(1).2Y(1+\log(2Y))^{2m-1}B_Y^{-m} =Y^{1-a/\log2+o(1)}.

Indeed 2m≤log⁡Y/(log⁡log⁡Y)32^m\le\log Y/(\log\log Y)^3, so the positive logarithmic error is o(log⁡Y)o(\log Y), while mlog⁡BY=(a/log⁡2+o(1))log⁡Ym\log B_Y=(a/\log2+o(1))\log Y. The union over at most O(Yβ)O(Y^\beta) shifts has size Y1−a/log⁡2+β+o(1)=o(Y)Y^{1-a/\log2+\beta+o(1)}=o(Y), because β<a/log⁡2\beta<a/\log2. All shifted arguments are positive for large YY. □\square

Let G\mathcal{G} be the union of the sets selected in Lemma 5.1, and for k∈Gk\in\mathcal{G} put

K=1+log⁡k,N=⌊exp⁡(exp⁡(cL(k)))⌋,X=⌊Nexp⁡(−BK6)⌋,(24)K=1+\log k,\qquad N=\left\lfloor\exp(\exp(c\mathcal{L}(k)))\right\rfloor,\qquad X=\left\lfloor N\exp(-BK^6)\right\rfloor, \tag*{(24)}

where B>0B>0 is any fixed constant. Then

Z:=log⁡X∼log⁡N∼exp⁡(cL(k)),KA=o(Z) (A fixed),log⁡N=o(k).(25)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). \tag*{(25)}

In particular NN and XX exceed every fixed power of kk.

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]:

∑j=1dτ(k−j)≤Cβdlog⁡k(kβ≤d≤k/3).(26)\sum_{j=1}^{d}\tau(k-j)\le C_\beta d\log k\qquad(k^\beta\le d\le k/3). \tag*{(26)}

For clarity, its parameters are fixed: apply the theorem to the multiplicative function τ=τ2\tau=\tau_2, modulus one, and interval (k−d−1,k−1](k-d-1,k-1], with exponent β/2\beta/2. This interval has length dd and lies at height comparable to kk. The hypotheses τ(pν)=ν+1≤2ν\tau(p^\nu)=\nu+1\leq2^\nu and τ(n)≪εnε\tau(n)\ll_{\varepsilon}n^\varepsilon hold. The resulting bound is Oβ(d(log⁡k)−1exp⁡(∑p≤k2/p))=Oβ(dlog⁡k)O_\beta(d(\log k)^{-1}\exp(\sum_{p\leq k}2/p))=O_\beta(d\log k). Neither the function nor the interval exponent varies with kk.

Proposition 5.2 (Exact-center energy). For all sufficiently large k∈Gk\in\mathcal{G}, and every reduced fraction u/qu/q with 2≤q∣k!(k+1)!,2\leq q\mid k!(k+1)!,

∑0≤n<Xsin⁡2(πunk/q)>k2.(27)\sum_{0\leq n<X}\sin^2(\pi u n^k/q)>k^2. \tag*{(27)}

Here XX may be chosen as in (24) for any fixed B>0B>0.

Proof. Suppose the energy is at most k2k^2. Begin with F(x)=uxk/qF(x)=ux^k/q, of degree d=kd=k. Lemma 4.3 and log⁡q=O(kK)\log q=O(kK) give a new degree

M≤CkK3/Z+CK4=o(k).M\leq CkK^3/Z+CK^4=o(k).

In particular M<k/3M<k/3, and q∣GM(k)q\mid G_M(k). By (13), replace FF by

uq∑j=0MAj(k)(xj).\frac{u}{q}\sum_{j=0}^{M}A_j(k)\binom{x}{j}.

Its difference from unk/qun^k/q is integral at every integer, so the sine energy has not changed. The modulus qq and prefix XX 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 kβ≤d≤k/3k^\beta\leq d\leq k/3 and q∣Gd(k)q\mid G_d(k), (15), log⁡D(v)≤τ(v)log⁡(v+1)\log D(v)\leq\tau(v)\log(v+1), and (26) give

log⁡q≤CβdK2.\log q\leq C_\beta dK^2.

A further contraction therefore gives

M≤CβdK4/Z+CK4<d/2M\leq C_\beta dK^4/Z+CK^4<d/2

for large kk, uniformly in this range. After finitely many steps the degree is at most kβk^\beta. Choose the dyadic YY for which (22) holds for kk. Put EY=exp⁡(aL(Y))E_Y=\exp(a\mathcal{L}(Y)). For every 1≤d≤kβ1\leq d\leq k^\beta, the same bound (22) gives

log⁡q≤dlog⁡(2k)+dEY.\log q\leq d\log(2k)+dE_Y.

The contraction estimate now reads

M≤ρkd+C0K4,ρk=C2K2(K+EY)Z⟶0.(28)M\leq\rho_kd+C_0K^4,\qquad\rho_k=\frac{C_2K^2(K+E_Y)}{Z}\longrightarrow0. \tag*{(28)}

The constants are fixed. Since Y≤k≤2YY\leq k\leq2Y, L(Y)=L(k)+O(1/log⁡log⁡k)\mathcal{L}(Y)=\mathcal{L}(k)+O(1/\log\log k). Thus EY=exp⁡(aL(k)+o(1))E_Y=\exp(a\mathcal{L}(k)+o(1)), whereas Z≍exp⁡(cL(k))Z\asymp\exp(c\mathcal{L}(k)); the inequality a<ca<c gives ρk→0\rho_k\to0, uniformly over the selected degrees. Take kk large enough that ρk<1/4\rho_k<1/4. While d>2C0K4d>2C_0K^4, this gives M<3d/4<kM<3d/4<k, so the same exact replacement remains valid. Eventually q∣Gd(k)q\mid G_d(k) with 1≤d≤2C0K41\leq d\leq2C_0K^4. A reduction to degree zero would already give q∣G0(k)=1q\mid G_0(k)=1, which is impossible. At the terminal positive degree,

log⁡q≤CK4(K+EY)=o(Z).(29)\log q\leq CK^4(K+E_Y)=o(Z). \tag*{(29)}

Thus q=Xo(1)q=X^{o(1)}.

Return to the original phase, not to an individual cyclotomic component. Each full block of qq consecutive inputs contains an n≡1(modq)n\equiv1\pmod q. Since gcd⁡(u,q)=1\gcd(u,q)=1,

sin⁡2(πu/q)≥4∥u/q∥R/Z2≥4/q2.\sin^2(\pi u/q)\geq4\lVert u/q\rVert_{\mathbb{R}/\mathbb{Z}}^2\geq4/q^2.

Consequently the original energy is at least

4⌊X/q⌋q2≥2Xq3=X1−o(1)>k2,\frac{4\left\lfloor X/q\right\rfloor}{q^2} \ge\frac{2X}{q^3} = X^{1-o(1)} > k^2,

by (25) and (29). This is the desired contradiction. □

From rational centers to collision estimates

Retain k∈Gk \in\mathcal{G} and NN from (24). Put

S=512⌊⌊N/k⌋512⌋,V={N−S+1,…,N},R={1,…,N−S}∖{2,…,257}.S = 512\left\lfloor\frac{\left\lfloor N/k\right\rfloor}{512}\right\rfloor,\qquad\mathcal{V} = \{N-S+1,\ldots,N\},\qquad R = \{1,\ldots,N-S\}\setminus\{2,\ldots,257\}.

Thus V\mathcal{V} is the reserved set of bases and RR is the available initial population. Write

MR=∣R∣,t=⌊N/8192⌋,ℓ=128.M_R = |R|,\qquad t = \left\lfloor N/8192\right\rfloor,\qquad\ell= 128.

For b∈Vb \in\mathcal{V}, let qb=bkq_b=b^k, and define

Db(α)=∑n∈Rsin⁡2(παnk),D_b(\alpha)=\sum_{n\in R}\sin^2(\pi\alpha n^k),
Fb(h)=1MR∑n∈Rcos⁡2(πhnk/qb)=1−Db(h/qb)MR.F_b(h)=\frac{1}{M_R}\sum_{n\in R}\cos^2(\pi h n^k/q_b)=1-\frac{D_b(h/q_b)}{M_R}.

We will prove

sup⁡b∈V∑h=1qb−1Fb(h)t=o(1).(30)\sup_{b\in\mathcal{V}}\sum_{h=1}^{q_b-1}F_b(h)^t=o(1). \tag*{(30)}

Notice that MR∼NM_R\sim N and t/MR≥1/16384t/M_R\ge1/16384 for large kk. Also S≤N/kS\le N/k, so b/N≥1−1/kb/N\ge1-1/k for b∈Vb\in\mathcal{V}. Since (1−1/k)k→e−1>1/4(1-1/k)^k\to e^{-1}>1/4, we have bk≥Nk/4b^k\ge N^k/4 uniformly over the reserved bases.

Lemma 6.1 (A common rational approximation). Let A>0A>0 be fixed. There are a constant CC and an integer Bk∣k!(k+1)!B_k\mid k!(k+1)!, independent of α\alpha, such that

Db(α)≤Aklog⁡N⟹∣α−uBk∣≤N−kexp⁡(CkK6)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 uu. The assertion is uniform in b∈Vb\in\mathcal{V}.

Proof. The population is independent of bb. Add back the at most 256 excluded terms and use the prefix 0≤n<N−S0\le n<N-S; the term at zero vanishes. Its energy E0E_0 is at most Aklog⁡N+256Ak\log N+256.

Take P=Pk+1=(1−z)k+1QP=P_{k+1}=(1-z)^{k+1}Q from Lemma 2.1, and M=Q(1)∣(k+1)!M=Q(1)\mid(k+1)!. Round f(n)=αnkf(n)=\alpha n^k to integers mnm_n. As in Lemma 2.2, the number of nonzero integer residuals P(E)mnP(E)m_n is at most ∥P∥12E0/4\|P\|_1^2E_0/4. We have log⁡(1+E0)=O(K)\log(1+E_0)=O(K), including when E0=0E_0=0. The zero-run count in Lemma 2.2 therefore provides L≥Nexp⁡(−C1K6)L\ge N\exp(-C_1K^6) consecutive valid residual positions, say s,…,s+L−1s,\ldots,s+L-1.

Put D0=deg⁡PD_0=\deg P. As deg⁡Q=D0−k−1\deg Q=D_0-k-1, the integers bn=Q(E)mnb_n=Q(E)m_n are defined for every s≤n≤s+L+ks\le n\le s+L+k. On the LL residual positions, Δk+1bn=0\Delta^{k+1}b_n=0. Successive finite differences consequently show that all these values agree with one rational polynomial of degree at most kk. Its Newton coefficients about the integer ss are integral, so its coefficient of nkn^k is u/k!u/k! for some u∈Zu\in\mathbb{Z}.

The polynomial Q(E)fQ(E)f has coefficient MαM\alpha at nkn^k. Since QQ has nonnegative coefficients of sum MM, the finite convolution inequality bounds the squared error of their difference, on the first LL positions of this interval, by M2E0/4M^2E_0/4.

Take H=⌊L/(2k)⌋≥L/(4k)H=\lfloor L/(2k)\rfloor\ge L/(4k). The kkth difference with step HH of this error polynomial is the constant

k!HkM(α−uk!M).k!H^kM\left(\alpha-\frac{u}{k!M}\right).

There are at least L/2L/2 valid starting points. The difference operator has coefficient norm 2k2^k, so

L2(k!HkM)2∣α−uk!M∣2≤4kM2E0/4.\frac{L}{2}(k!H^kM)^2\left|\alpha-\frac{u}{k!M}\right|^2\leq4^kM^2E_0/4.

Using k!≥(k/e)kk!\geq(k/e)^k, we obtain

∣α−uk!M∣≤(8e)kL−kE02L≤N−kexp⁡(CkK6).\left|\alpha-\frac{u}{k!M}\right|\leq(8e)^kL^{-k}\sqrt{\frac{E_0}{2L}}\leq N^{-k}\exp(CkK^6).

Take Bk=k!MB_k=k!M. All filters and this denominator depend only on kk. □

Lemma 6.2 (Small symmetric numerators). Put K∗=1010(1+log⁡N/log⁡k)K_* = 10^{10}(1+\log N/\log k). Uniformly for b∈Vb\in\mathcal{V},

∑1≤h<qbmin⁡(h,qb−h)≤(b/(K∗k2))kFb(h)t=o(1).\sum_{\substack{1\leq h<q_b\\ \min(h,q_b-h)\leq(b/(K_*k^2))^k}}F_b(h)^t=o(1).

Proof. By symmetry take a=min⁡(h,qb−h)a=\min(h,q_b-h) and put r=ba−1/kr=ba^{-1/k}. Then K∗k2≤r≤b≤NK_*k^2\leq r\leq b\leq N, and the sine phase is (n/r)k(n/r)^k.

If r>N/2r>N/2, use the interval

[r(1/8)1/k,r(1/4)1/k].[r(1/8)^{1/k},r(1/4)^{1/k}].

It has ≫N/k\gg N/k integer points, all in RR for large kk: its upper endpoint is at most N4−1/k<N−SN4^{-1/k}<N-S, and its lower endpoint exceeds 257257. On it the sine square is at least 1/81/8. Thus Db(h/qb)≫N/kD_b(h/q_b)\gg N/k.

If r≤N/2r\leq N/2, set Yr=⌊r/(1000k)⌋Y_r=\lfloor r/(1000k)\rfloor. For 1≤j≤Yr1\leq j\leq Y_r, use the disjoint intervals

Ij=[r(j+1/8)1/k,r(j+1/4)1/k].I_j=[r(j+1/8)^{1/k},r(j+1/4)^{1/k}].

The mean value theorem gives

∣Ij∣≥r16k(j+1)>2.|I_j|\geq\frac{r}{16k(j+1)}>2.

Their integer points lie in RR. Indeed their lower endpoints exceed 257257, while their upper endpoints are at most r(Yr+1)1/k≤3N/4r(Y_r+1)^{1/k}\leq3N/4 eventually, because log⁡N=o(k)\log N=o(k). Each interval contains at least half its length in integers, with sine square at least 1/81/8. Therefore

Db(h/qb)≥r256k∑j=1Yr1j+1≥rlog⁡(Yr+1)512k≥K∗klog⁡k1024.D_b(h/q_b)\geq\frac{r}{256k}\sum_{j=1}^{Y_r}\frac{1}{j+1}\geq\frac{r\log(Y_r+1)}{512k}\geq\frac{K_*k\log k}{1024}.

The first case satisfies the same final bound, since N/k≫K∗klog⁡kN/k\gg K_*k\log k.

Now Fb(h)t≤exp⁡(−Db(h/qb)/16384)F_b(h)^t\leq\exp(-D_b(h/q_b)/16384). There are fewer than NkN^k frequencies, and K∗>224log⁡N/log⁡kK_*>2^{24}\log N/\log k by a fixed factor. Hence their total contribution is bounded by

Nkexp⁡(−K∗klog⁡k224)=o(1).N^k\exp\left(-\frac{K_*k\log k}{2^{24}}\right)=o(1).

□

Proposition 6.3. The uniform collision estimate (30) holds.

Proof. Choose a fixed AA sufficiently large. Frequencies with Db(h/qb)>Aklog⁡ND_b(h/q_b)>Ak\log N have total contribution at most

Nkexp⁡(−Aklog⁡N/16384)=o(1).N^k\exp(-Ak\log N/16384)=o(1).

Every remaining frequency is in an arc

∣hqb−uBk∣≤δ,δ=N−kexp⁡(CkK6),\left|\frac{h}{q_b}-\frac{u}{B_k}\right|\leq\delta,\qquad\delta=N^{-k}\exp(CkK^6),

by Lemma 6.1. We have log⁡Bk=O(kK)\log B_k=O(kK), and δBk=o(1)\delta B_k=o(1). Thus at most Bk+2B_k+2 centers are relevant in or adjacent to [0,1][0,1]. Each arc contains at most 2qbδ+22q_b\delta+2 points of the actual grid. The total

number of grid points in these arcs is therefore at most exp⁡(C3kK6)\exp(C_3 k K^6). Consequently those among them with Db≥A3kK6D_b \ge A_3 k K^6 also contribute o(1)o(1), for a fixed A3>2⋅16384C3A_3 > 2 \cdot16384 C_3.

It remains to consider Db<A3kK6D_b < A_3 k K^6. Choose the constant BB in (24) larger than C+2C+2. On the prefix n<Xn<X, replacing the frequency by its center changes the square root of the sine energy by at most

πδXkX≤πexp⁡(−(B−C)kK6+12log⁡X)=o(1).\pi\delta X^k \sqrt{X} \le\pi\exp\left(-(B-C)kK^6+\frac{1}{2}\log X\right)=o(1).

If the center is not an integer, its reduced denominator is a divisor of BkB_k, and Proposition 5.2 gives center energy greater than k2k^2. Removing the at most 256 auxiliary terms leaves

Db(h/qb)≥k2/2−256D_b(h/q_b)\ge k^2/2-256

for large kk, contradicting Db<A3kK6D_b<A_3kK^6.

If the center is an integer, then min⁡(h,qb−h)≤qbδ\min(h,q_b-h)\le q_b\delta. Since log⁡N\log N dominates K6K^6 and log⁡(K∗k2)=O(K)\log(K_*k^2)=O(K), we have δ≤(K∗k2)−k\delta\le(K_*k^2)^{-k} eventually. These frequencies lie in the range of Lemma 6.2, whose total contribution is o(1)o(1). 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 k∈Gk\in\mathcal{G}, there are ℓ=128\ell=128 pairwise disjoint sets of bases, all at most NN, whose power subset-sum sets A1,…,AℓA_1,\ldots,A_\ell satisfy

∣Ai∣≥sNk/16,Ai⊆[0,2sNk],s=S/512.(31)|A_i|\ge sN^k/16,\qquad A_i\subseteq[0,2sN^k],\qquad s=S/512. \tag*{(31)}

No AiA_i is contained in an arithmetic progression of integer difference greater than one.

Proof. Choose ℓ\ell disjoint random tt-subsets CiC_i of RR, uniformly. This is possible since ℓt<MR\ell t<M_R, and each marginal is a uniform tt-subset. Independence between the CiC_i is not required.

For a fixed C=CiC=C_i, choose each subset U⊆CU\subseteq C with probability 2−t2^{-t}; equivalently, include its bases independently with probability 1/21/2. Let

μb(x)=2−t#{U⊆C:∑n∈Unk≡x(modqb)}.\mu_b(x)=2^{-t}\#\left\{U\subseteq C:\sum_{n\in U}n^k\equiv x\pmod{q_b}\right\}.

This is a distribution on residues, not the uniform distribution on distinct represented values. Its Fourier transform is

μ^b(h)=∏n∈C1+exp⁡(2πihnk/qb)2.\widehat{\mu}_b(h)=\prod_{n\in C}\frac{1+\exp(2\pi i h n^k/q_b)}{2}.

Finite Fourier orthogonality therefore gives the collision excess

qb∑xμb(x)2−1=∑h=1qb−1∏n∈Ccos⁡2(πhnk/qb).q_b\sum_x\mu_b(x)^2-1=\sum_{h=1}^{q_b-1}\prod_{n\in C}\cos^2(\pi h n^k/q_b).

For xn=cos⁡2(πhnk/qb)x_n=\cos^2(\pi h n^k/q_b), the expectation of the product over a uniform tt-subset equals et((xn)n∈R)/(MRt)e_t((x_n)_{n\in R})/\binom{M_R}{t}, where ete_t is the elementary symmetric polynomial of degree tt. Maclaurin’s inequality bounds this by (MR−1∑n∈Rxn)t=Fb(h)t(M_R^{-1}\sum_{n\in R}x_n)^t=F_b(h)^t.

Write ηk=sup⁡b∈V∑h=1qb−1Fb(h)t=o(1)\eta_k=\sup_{b\in\mathcal{V}}\sum_{h=1}^{q_b-1}F_b(h)^t=o(1). If the support has fewer than qb/4q_b/4 elements, Cauchy–Schwarz gives qb∑xμb(x)2>4q_b\sum_x\mu_b(x)^2>4, so the collision excess is greater than three. For each fixed group, the expected number of such bad reserved bases is at most Sηk/3S\eta_k/3. Markov’s inequality bounds the probability of more than S/2S/2 bad bases by 2ηk/32\eta_k/3. A union bound over the fixed ℓ\ell groups proves that, with probability 1−o(1)1-o(1), every group has at least S/2S/2 good bases.

We may simultaneously require

∑n∈Cink≤4tNk/k(1≤i≤ℓ).(32)\sum_{n\in C_i}n^k\le4tN^k/k\qquad(1\le i\le\ell). \tag*{(32)}

Indeed the expectation is at most 2tNk/k2tN^k/k, because ∑n≤Nnk≤Nk+1/(k+1)+Nk\sum_{n\le N} n^k \le N^{k+1}/(k+1)+N^k and MR∼NM_R\sim N. Sampling without replacement has variance at most tN2ktN^{2k}. Chebyshev’s inequality makes the failure probability at most k2/(4t)=o(1)k^2/(4t)=o(1), uniformly in the fixed number of groups. Fix a realization with both properties.

Allocate ss good reserved bases to each group, with no base used twice. Before any individual choice, fewer than ℓs=S/4\ell s=S/4 bases have been used, whereas the group in question has at least S/2S/2 good choices. The greedy allocation is therefore possible; the completed allocation uses exactly S/4S/4 bases. If a finite integer set AA occupies rr residue classes modulo a positive integer qq, then

∣A+{0,q}∣≥∣A∣+r.|A+\{0,q\}|\ge|A|+r.

For each occupied residue, its largest element supplies a new element after addition of qq. Applying this with q=bkq=b^k shows that each allocated base increases the subset-sum cardinality by at least qb/4≥Nk/16q_b/4\ge N^k/16. The original support is retained after earlier additions, so the support condition continues to hold. After ss additions the cardinality is at least sNk/16sN^k/16.

Finally add the distinct auxiliary pairs

(2,3),(4,5),…,(256,257)(2,3),(4,5),\ldots,(256,257)

to the 128 groups, one pair per group. They are disjoint from RR and from the reserved bases. Each resulting subset-sum set contains zero and two coprime kkth powers, so it cannot lie in a proper integer arithmetic progression. The initial span in (32) is at most sNk/3sN^k/3 eventually, because 4t/(ks)→1/4<1/34t/(ks)\to1/4<1/3. The reserved bases add at most sNksN^k, and the two auxiliary powers add at most 2⋅257k=o(sNk)2\cdot257^k=o(sN^k). This proves (31). □

We use Lev’s consecutive-interval theorem in the following sufficient form [5 Corollary 1]. If A1,…,AℓA_1,\ldots,A_\ell are subsets of [0,l]∩Z[0,l]\cap\mathbb{Z}, each of size at least n≥3n\ge3, none contained in an integer arithmetic progression of difference greater than one, and

ℓ≥2⌈l−1n−2⌉,\ell\ge2\left\lceil\frac{l-1}{n-2}\right\rceil,

then their sumset contains ℓ(n−1)+1\ell(n-1)+1 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

l=⌈2sNk⌉,n=⌊sNk/16⌋,ℓ=128.l=\lceil2sN^k\rceil,\qquad n=\lfloor sN^k/16\rfloor,\qquad\ell=128.

The ratio (l−1)/(n−2)(l-1)/(n-2) tends to 32, so the strict inequality has a fixed margin. The sumset contains an interval [a,a+L]∩Z[a,a+L]\cap\mathbb{Z} with

L≥128(n−1)∼8sNk>(N+1)k.L\ge128(n-1)\sim8sN^k>(N+1)^k.

Also 0≤a≤256sNk≤256Nk+10\le a\le256sN^k\le256N^{k+1}. Every integer in this interval is a sum of distinct kkth powers with bases at most NN, because the groups of bases are disjoint.

Adjoin the unused powers with bases N+1,N+2,…N+1,N+2,\ldots. If the currently represented interval is [a,a+L][a,a+L] and a new power bkb^k satisfies bk≤L+1b^k\le L+1, its translate joins it without a gap, producing [a,a+L+bk][a,a+L+b^k]. Initially L≥(N+1)kL\ge(N+1)^k. If L≥bkL\ge b^k, then the new length is at least 2bk>(b+1)k2b^k>(b+1)^k, since b≥Nb\ge N and N/k→∞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 aa consequently belongs to one finite-stage interval, and is represented by finitely many distinct positive kkth powers. We have proved

Tk≤256Nk+1.T_k\le256N^{k+1}.

Taking logarithms and using (25) gives (1). □

Proof of Theorem 1.1. If there were only finitely many strict adjacent decreases, then Tk+1≥TkT_{k+1} \ge T_k for all sufficiently large kk. Choose arbitrarily large jj from Lemma 1.3. Let YY be a dyadic integer with j≤Y<2jj \le Y < 2j, and choose k∈G∩[Y,2Y]k \in G \cap[Y,2Y]. Then j≤k<4jj \le k < 4j, and L(k)=L(j)+o(1)\mathcal{L}(k) = \mathcal{L}(j) + o(1). Proposition 1.2 gives

log⁡Tk≤(4+o(1))jexp⁡(25L(j)),\log T_k \le(4+o(1))j\exp\left(\frac{2}{5}\mathcal{L}(j)\right),

whereas

log⁡Tj≥jexp⁡(920L(j)).\log T_j \ge j\exp\left(\frac{9}{20}\mathcal{L}(j)\right).

The latter is larger for all sufficiently large jj, contradicting Tj≤TkT_j \le T_k. 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. [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. [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. [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. [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. [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. [6]M. Nair and G. Tenenbaum, Short sums of certain arithmetic functions, Acta Mathematica 180 (1998), 119–144. Author’s version.DOI
  7. [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

Paper details

vlnc:W_vvvndr3x
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents