A Power Saving for Polynomial Differences at Prime Arguments

Proof. To check integrality at p\mid l, write u=v_p(l) and make the affine change of variable

Its coefficients lie in \Z_p, and its slope is a unit. Since v_p(\lambda(l))=um_p, (2.1) gives

Thus h_l is integral at p. If p\nmid l, its denominator \lambda(l) is a p-adic unit, so integrality is immediate. This proves h_l\in\Z[x]. Its leading coefficient is a_l, and expanding h(r_l+lx) with |r_l|<l bounds each coefficient by O_h(l^k/\lambda(l))=O_h(a_l).

The residues r_l and r_{lD} agree modulo l. Their specified ranges therefore give r_{lD}=r_l-il for some 0\le i<D. Substitution and complete multiplicativity prove (2.3); its last two assertions follow from 1\le m_p\le k.

For the final assertion, factor h=c\prod_i g_i^{d_i} over \Z[x], where c\ne0 is an integer and the g_i are distinct primitive irreducible nonconstant polynomials. Exclude primes dividing c or the nonzero integer right-hand sides of cleared Bézout identities for g_i,g_j with i\ne j, and for g_i,g_i'. At a root \mathfrak z_p for any remaining prime, exactly one factor g_i vanishes, its derivative is a unit, and all the other factors have unit values. Consequently m_p=d_i, and the coefficient of X^{m_p} in (2.1) is a unit.□

Proof. Take the threshold large enough for the preceding nonconstancy statements. The derivative excludes at most k-1 residues, so at most k arguments fail to be allowed regular. This gives the asserted cardinality after increasing the threshold.

We first work modulo p. If k' is the degree of F\bmod p, then the complete mean S=\mathbb E_{x\bmod p}e(vF(x)/p) vanishes when k'=1. For k'\ge2, repeated differencing gives

where \Delta_u F(x)=F(x+u)-F(x). The first inequality follows by squaring, grouping the two arguments by their difference, and iterating the triangle and Cauchy–Schwarz inequalities. For the second, the final phase is linear, with nonzero coefficient unless one of the u_i is zero: its coefficient is v k'! times the leading coefficient of F\bmod p times u_1\cdots u_{k'-1}. A union bound gives the displayed probability. Removing at most k arguments changes a normalized mean by O_k(p^{-1}). Since 8\delta<2^{-(k-1)}, this proves both assertions of (2.7) at conductor p, for sufficiently large p.

For j\ge2, set n=\lfloor j/2\rfloor and write x=x_0+p^{j-n}y, with x_0 modulo p^{j-n} and y modulo p^n. Taylor expansion over the integers gives

The condition p\nmid T_l(x) depends only on x_0. Averaging over y therefore annihilates every term for which p^n\nmid F'(x_0). We bound the proportion of the remaining x_0 by interpolation.

Put b=\lceil n/(k-1)\rceil. The solutions of F'(x_0)\equiv0\pmod{p^n} occupy at most k-1 residue classes modulo p^b. Otherwise, choose k integer solutions x_1,\ldots,x_k in distinct such classes. In the Lagrange interpolation formula for the degree-at-most-(k-1) polynomial F', every denominator \prod_{s\ne r}(x_r-x_s) has valuation at most

Since every F'(x_r) is divisible by p^n, each interpolating summand has all coefficients divisible by p. This contradicts F'\not\equiv0\pmod p.

Since b\le n\le j-n, the class count applies to the full range of x_0 modulo p^{j-n}. The unit condition retains at least a proportion 1/2 of all arguments. Consequently the conditional proportion that can survive y-averaging is at most

where \lfloor j/2\rfloor\ge j/3 for j\ge2. Because 8\delta<1/(3(k-1)), one further increase of P_1 makes this at most p^{-8\delta j} for every j\ge2. All thresholds were independent of l.□

Proof. Fix p<P_1. For a nonconstant polynomial over \Z_p, the minimum valuation of its nonconstant coefficients is preserved by an affine substitution of unit slope. One inequality follows by expanding the substitution, and the other by applying its inverse. If p\nmid l, this observation applied to (2.2) bounds that minimum for F=h_l by a constant depending only on h,p. If p\mid l, use (2.4): before the unit affine substitution, its degree-m_p coefficient is a unit multiple of b_{m_p,p}, whose valuation is fixed. The same uniform bound therefore holds in this case. Differentiation increases the minimum valuation by at most \max_{1\le j\le k}v_p(j), so the minimum coefficient valuation of F' has a uniform upper bound C_p\ge0, which we take to be an integer.

There are at least k distinct integers in [1,kp] satisfying p\nmid T_l(x). Interpolate F', of degree at most k-1, at any k of them. The interpolation denominators are products of differences of integers in this fixed interval. Let B_p\ge0 be a uniform integer upper bound for their p-adic valuations. If all k values of F' had valuation greater than C_p+B_p, Lagrange interpolation would force every coefficient of F' to have valuation greater than C_p, a contradiction. Thus (2.8) holds with S_p=C_p+B_p.

Now let p be arbitrary and x,s be as in the statement. In either case E_p\ge2s+1. Taylor expansion with integer coefficients gives

Indeed c_1=p^{-s}F'(x), and each term of degree at least two contains, after division by p^{E_p}, a factor p^{E_p-2s}. The polynomial G(y)=c_1y+pC(y) permutes the residues modulo every power of p: for integers y,z, the quotient (G(y)-G(z))/(y-z) is a unit when y\ne z, so

It follows that G is injective, hence bijective, on every finite residue ring. Formula (2.10) proves constancy modulo p^{E_p}. The argument class preserves the unit condition because E_p-s\ge1.

Finally, uniform arguments in this class modulo p^j correspond to uniform y modulo p^{j-E_p+s}. Each residue of y modulo p^{j-E_p} occurs exactly p^s times. Applying the permutation G modulo p^{j-E_p} therefore gives precisely the asserted uniform distribution of polynomial values.□

Proof. For p<P_1, an admissible residue exists by Lemma 2.3. Repeat it L times and use p^{E_p}\mid L. For p\ge P_1, take independent uniform allowed regular arguments x_0,\ldots,x_{L-1} modulo p. Character orthogonality and (2.7) give

The probability is therefore positive, yielding the required sequence of admissible values.□

Proof. The convolution kernel W(y-x)-c_p has L^2 operator norm at most p^{-4\delta} by (3.4). Telescope the product I_G by replacing one edge weight at a time by c_p. In a resulting term, hold fixed all labels except those at the endpoints x,y of the edge being replaced. As there is no second edge on this pair, the other factors depending on these two labels separate as a(Y_x)b(Y_y), with |a|,|b|\le1. The convolution bound controls the conditional average by p^{-4\delta}. Summing over the edges proves (3.5).

For the second assertion write A,B for the label spaces of these two classes and D(a,b)=I_G(a,b)-c_p^{e_G}. In uniform L^2 spaces, the fourth Schatten moment of its operator T_D is

All kernels here are real. Expand the four differences. Each term is the graph average of the selected copies of I_G, times the corresponding power of -c_p^{e_G}. Its formal vertices consist of two separate copies of each of the two vertex classes. No pair of formal vertices receives two edges: it determines one corner of the rectangle and one edge of G. Thus (3.5) applies to every term. Replacing all its edge weights by c_p makes the expanded sum zero, so the fourth moment is O_G(p^{-4\delta}). The fourth power of the largest singular value is at most this moment, proving (3.6).□

Proof. Across any reflection cut of V, the matrix of the product law is the tensor product of the corresponding prime-law matrices. It is therefore positive semidefinite. To explain its consequence for signed inputs, fix a cut V=V_+\sqcup V_- and its reflection \theta. Define maps \phi_\pm:V\to V_\pm that fix the selected half and reflect the other half into it. An assignment of functions is a map a:v\mapsto g_v; write its integral as \Lambda(a). The two real functions on the plus-half labels that enter the cut bilinear form are

Its mixed value is \Lambda(a), and its two quadratic values are \Lambda(a\circ\phi_+) and \Lambda(a\circ\phi_-). Cauchy–Schwarz for the positive semidefinite matrix gives

In particular a constant assignment has nonnegative integral, proving the first assertion of (4.1).

We next give a finite sequence of fold maps that sends every vertex to one vertex. In one block write p_i for the position of symbol i in its permutation word. Folding onto the half where i precedes i+1 sorts the pair (p_i,p_{i+1}), leaving all other entries unchanged. Apply the comparisons i=1,\ldots,L-1 in that order, and repeat this sweep L-1 times. A sweep moves the largest entry to the end. Once the largest entries occupy their final positions, the next sweep leaves them there and places the largest remaining entry immediately before them. Thus every position array becomes (1,\ldots,L). Perform these sweeps in each block. If their fold maps in chronological order are \phi_1,\ldots,\phi_m, then

where v_* has the identity word in every block.

Now fix a finite nonempty list of real functions and let M be the maximum absolute integral over all assignments from that list, allowing repetition. If M>0, take a maximizing assignment. Each of its folded integrals is nonnegative and at most M, while their product is at least M^2 by (4.2). Both therefore equal M. Hence either fold preserves maximality. Apply the pullbacks in reverse order, first \phi_m, then \phi_{m-1}, and so on. The final assignment is a\circ\phi_m\circ\cdots\circ\phi_1, which is constant. It follows that M is a diagonal value. Conversely, constant assignments are included in the maximum. We have proved that the maximum absolute mixed integral equals the largest diagonal value in the list; this is also true when M=0.

For \epsilon>0, apply this conclusion to the list

Each diagonal value in this list is at most one. Multilinearity gives |\mathcal Z_{l,\mathcal P}((g_v)_v)| \le\prod_v(Z_{l,\mathcal P}(g_v)+\epsilon)^{1/d}. Let \epsilon\downarrow0. This proves the second assertion, including cases where some diagonal values vanish.□

Proof. Nonnegativity follows from Proposition 4.1. Since d is even, homogeneity of Z gives absolute homogeneity of its d-th root. Expanding Z(g+h) by its slots and applying (4.1) termwise gives

Taking roots proves the triangle inequality. Putting g in one slot and 1 in all others in (4.1) proves mean domination, since the single-slot marginal is uniform and Z(1)=1.

The simultaneous translation invariance of the tuple laws proves that translations are isometries. Let G_B\subseteq X_{\mathcal P} be the additive subgroup of vectors supported on B. Then

The triangle inequality gives the asserted contraction. Since \mathbb E_Bg is independent of B, the probability laws at those primes integrate out, proving the equality of the two seminorms. Finally, \lambda(D) is a unit at each remaining prime, and the covariance identity (3.1) pushes the product law at l exactly to that at lD. This proves (4.3).□

Proof. At one prime, let \mathfrak m_p denote the marginal law of the labels in all slots other than v, and let

This is an operator from uniform L^2(\F_p) to L^2(\mathfrak m_p). It preserves constants. It sends uniform-mean-zero inputs to \mathfrak m_p-mean-zero outputs, since \mathbb E_{\mathfrak m_p}T_pf=\mathbb E f. By the conditional mixing estimate (3.2), its norm on the mean-zero subspace is at most p^{-\gamma}.

The product law makes the conditional operator for all primes equal to T=\bigotimes_pT_p: this identity holds first for products of one-prime functions, by independence across primes, and then for every function by linearity. The exact-support B Fourier space has a mean-zero factor at primes in B and a constant factor elsewhere. On this space the operator norm is at most q_B^{-\gamma}. Furthermore, the images of two distinct exact-support spaces are orthogonal in L^2(\bigotimes_p\mathfrak m_p). At a prime in the symmetric difference of the supports, one image factor is constant and the other has mean zero. Their inner product is zero, and tensoring preserves this orthogonality.

Decompose g_v=\sum_{q_B>R}g_{v,B} by exact supports. Both the domain summands and their images are orthogonal, so

Condition the original integral on the other slots and apply Cauchy–Schwarz. The remaining factor is bounded by

using ordinary Hölder and the uniform single-slot marginals. This proves (4.4). If \mathcal P is empty, the frequency hypothesis forces g_v=0, and the conclusion is immediate.□

Proof. The zero function is immediate; otherwise scale so that \|f\|_\infty\le1. Write N_I=|I|, and let

The empty support is included, so this maximum is defined even when \mathcal P is empty. We first control conditional sums of squares of the f_B, then their square-function moments. Symmetrization will recover the moment of their sum.

Conditional energy. For J\subseteq\mathcal P with q_J\le Q, and any fixed coordinate vector z_J, we claim that

The conditional expectation here averages uniformly over all coordinates outside J. If B\supseteq J, the coefficient of an outside character \eta of exact support B\setminus J, after fixing z_J, is

Indeed, the sum over the nonzero frequencies at p is \sum_{a=1}^{p-1}e(a(z_p-x)/p) =p\mathbf 1_{\{x\equiv z_p\pmod p\}}-1. The outside characters associated with B have exact support B\setminus J. These supports distinguish the sets B\supseteq J, so their character sets are disjoint. Conditional Parseval therefore identifies the left side of (4.6) with the squared Euclidean norm of this coefficient vector on the union of those sets.

Expand the product in c_J over subsets J'\subseteq J. Apart from a sign, the corresponding vector has coordinates

The congruence denotes the class determined by the fixed coordinates in J'; for the empty subset it imposes no restriction. Write its progression as x=a+q_{J'}n, with n in a consecutive interval of length N'. Then

In these coordinates the frequencies are q_{J'}\eta, up to constant phases. They remain distinct because their denominators are coprime to q_J. Their denominators are at most Q, so they number at most Q^2 and have pairwise circle distance at least Q^{-2}.

The Gram matrix of these characters in normalized L^2 on the progression has diagonal 1. By geometric summation, every off-diagonal entry has modulus at most Q^2/(2N'). Its operator norm is therefore at most its maximum absolute row sum, which is bounded by

To see how this bounds the coefficients, let the synthesis map send (b_\eta)_\eta to \sum_\eta b_\eta e(nq_{J'}\eta) on the progression interval with normalized counting measure. Its adjoint is the normalized Fourier analysis map, and its Gram matrix is the matrix just estimated. The two maps therefore have norm squared equal to that Gram-matrix norm. Since \|f\|_\infty\le1 and N'q_{J'}/N_I\le1.1, the displayed coefficient vector has Euclidean norm bounded by an absolute constant. The triangle inequality over the 2^{|J|} subsets J', followed by squaring, proves (4.6).

Square-function moments. Set

Expand \mathbb E S^{2r} and fix the supports of its first r-1 factors. Their union W' has size at most (r-1)u, and their product depends only on z_{W'}. For the final support B, the function f_B ignores every coordinate outside B. Thus integration outside W' leaves exactly \mathbb E(|f_B|^2\mid z_J), where J=B\cap W'. Every intersection that occurs satisfies q_J\le q_B\le Q. For each fixed intersection J, the sum over supports with B\cap W'=J is bounded by the larger sum over all B\supseteq J in (4.6). There are at most 2^{(r-1)u} possible intersections and each has at most u elements. Thus

The same argument with r=1 uses J=W'=\varnothing. Iteration gives

The overlaps among supports have now been controlled. It remains to bound their sum by this square function with a loss exponential only in u.

Recovering the sum. We color the prime coordinates and first retain only terms that use one coordinate of each color. This will let us apply a scalar random-sign estimate one color at a time and use consistent coordinate copies across the retained terms. Fix a support size j\ge1 and color every prime coordinate with one of j colors. Call a support transversal when it has exactly one prime of each color, and let \mathcal T be the transversal supports in \mathcal F for this coloring. Take independent uniform pairs X_p^0,X_p^1 at every prime. The operator \operatorname{swap}_p interchanges these two copies. Define

Averaging over all second copies leaves f_B(X^0), since every other term in this expansion has mean zero in at least one copied coordinate. Jensen’s inequality gives

Independent swaps preserve the joint law of the copies and multiply D_B by the product of the corresponding signs. Thus for independent uniform signs \epsilon_p, indexed by primes,

For completeness, the scalar sign estimate

follows by expanding the even moment. Surviving terms have even multiplicity at every index. For nonnegative coefficients their sum is at most

because (2m)!\ge2^m m!. For complex coefficients, take absolute values of the surviving terms in (\sum_i a_i\epsilon_i)^r(\sum_i\overline{a_i}\epsilon_i)^r and use the nonnegative case. Iterating this estimate over the color classes gives, for fixed copies,

At each step Minkowski is used in the form \| (\sum_i|B_i|^2)^{1/2}\|_{2r} \le(\sum_i\|B_i\|_{2r}^2)^{1/2}. The signs are indexed by individual primes; transversality ensures that each monomial uses exactly one sign from each color class.

In expanding the swaps in D_B, index its 2^j terms by a choice of copy for each color. For any fixed such choice, made consistently across all supports, the selected prime coordinates have the original product law. The triangle inequality in L^{2r}(\ell^2(\mathcal T)) therefore gives

Consequently the transversal sum has norm at most (2C_r)^j\|S\|_{2r}.

Now average over independent uniform colorings. A fixed size-j support is transversal with probability j!/j^j\ge e^{-j}, where here e is Euler’s number; the inequality follows from \log(j!)\ge\int_1^j\log x\,dx. Thus the full size-j sum is exactly the coloring average of its transversal sum divided by this probability. Minkowski yields

Include the constant term of size zero and sum over j\le u. Together with (4.7), this bounds the norm of the full sum by (C'_r)^{1+u}. Finally, the product of u distinct primes is at least (u+1)!, so (u+1)!\le Q. Hence u=o(\log Q) as Q\to\infty, uniformly in the prime set. For every fixed r and \epsilon>0, (C'_r)^{1+u}\le C_{r,\epsilon}Q^\epsilon. Restoring \|f\|_\infty proves (4.5) with all the stated uniformities.□

Proof. The specified fiber has uniform probability 1/q_B. Its contribution to \mathbb E|G|^s is q_B^{-1}\mathbb E|G(z_B,\cdot)|^s. Dropping the other nonnegative contributions proves the first assertion. For the last assertion, a character with original exact support C retains exact support C\setminus B after specialization. The two cuts therefore arise, before specialization, from the complete-support subfamilies

Apply Proposition 4.4 to these subfamilies and then use the fiber bound. Combining coefficients can cancel frequencies but cannot create any outside the indicated ranges.□

Proof. Set \sigma_0=15/16. We first prove the logarithmic derivative estimate

on \Re s=\sigma_0, and throughout \sigma_0\le\Re s\le2 when |\Im s|\ge1. The constants are absolute, including for imprimitive characters.

Write \delta_\chi=1 for a principal character and 0 otherwise, and let

Fix radii 2-\sigma_0<r<R<2-7/8 and use disks of radius R centered at s_t=2+it. Theorem 5.1 makes G_\chi holomorphic and nonvanishing on each disk, with the principal pole removed. To bound its size there, use periodicity to write

Partial summation continues the Dirichlet series to \Re s>0 as

Consequently, on the disk, |G_\chi(s)|\le C[2b(2+|t|)]^C. At its center the absolutely convergent Euler product gives |L(2+it,\chi)|\ge\zeta(4)/\zeta(2); hence |G_\chi(s_t)| is bounded below by the same positive constant. Choose a holomorphic logarithm and subtract its value at s_t. Its real part is bounded above by C\log(2b(2+|t|)). Borel–Carathéodory on an intermediate disk, followed by Cauchy’s estimate on the disk of radius r, now gives

Subtracting \delta_\chi/(s-1) proves (5.2) in the asserted ranges.

We next pass through a smoothed sum so that the contour integral is absolutely convergent. Mellin inversion for (1-u)_+ gives, for x\ge1,

Here the interchange with the Dirichlet series is absolute. Move the line to \Re s=\sigma_0. Estimate (5.2) bounds the horizontal integrals by a constant times x^3\log(2b(2+T))/T^2, which tends to zero with the height T. The sole crossed pole is at s=1 for the principal character; its residue is x^2/2. On the new vertical line, integration of \log(2b(2+|t|))/(1+t^2) gives

For (c,b)=1, character orthogonality yields

There are \varphi(b) character errors and a factor 1/\varphi(b), so the error is uniform in b. Crucially, sharp differencing is now performed on this nonnegative progression sum, rather than on a complex character sum. For 0<H<x, positivity of \Lambda gives

Take H=x^{31/32} for sufficiently large x. The main terms differ from x/\varphi(b) by O(H), and the errors are

Bounded x is harmless. Finally,

so removing higher prime powers proves (5.1). If a prime lies in a nonreduced residue class modulo b, it divides b; the sum of the logarithms of distinct such primes is at most \log b. This proves the last assertion.□

Proof. Within a block of \lfloor q/2\rfloor consecutive integers, two distinct indices differ by a nonzero d with |d|<q/2. Thus

The associated points are 1/(2q) separated on the circle. The nearest point to zero contributes at most M, and summing the others in bands of width 1/(2q) gives O(q\log(2q)), with another O(M) for the bounded number of points in the first band. Partitioning the indices into such blocks proves the result, also when q=2 or 3.□

Proof. We give the mixed argument explicitly. For a function g of two integer variables, define

Let D_0 be the set of pairs in the displayed box with mn\in I. Extend a_m and d_n by zero outside their respective intervals, and extend every summand by zero outside D_0. Cauchy–Schwarz first removes a_m:

Expanding the square and grouping by u=n'-n bounds its right side by

For fixed u the new weight depends only on n and has modulus at most one. This is exactly the form needed for another n-difference. In particular, the product cutoff remains inside the sum; it has not been replaced by a rectangular domain.

For j fixed shifts \mathbf u=(u_1,\ldots,u_j), let

The accompanying coefficient d_{\mathbf u}(n) is defined recursively by d_\varnothing(n)=d_n and

It depends only on n and is bounded by one. At each subsequent step, Cauchy–Schwarz in the existing shifts costs only a constant depending on j, because their total normalized mass is at most 2^j. Cauchy–Schwarz in m, followed by the same square expansion, adds one n-shift. Induction therefore gives

All summands still have m and n in their original intervals, as the zero vertex of every translated cube belongs to D_0.

After k differences in n, every lower-degree term vanishes, and

For 0\le j\le k-1 and m-shifts \mathbf v=(v_1,\ldots,v_j), define the domains

Thus D_{\mathbf u,\varnothing}=D_{\mathbf u}. For 1\le j\le k-1, let

To enter this unweighted family, remove d_{\mathbf u} by Cauchy–Schwarz in n:

Expanding the square bounds this by A^{-1}\sum_{|v_1|<A}|T_{\mathbf u,(v_1)}|. This is the first m-differencing step, so removing the coefficients requires no additional squaring. For 1\le j\le k-2, Cauchy–Schwarz in n and the same square expansion give

Applying Cauchy–Schwarz also to all existing shift variables, whose total normalized mass is bounded in terms of k, now yields

This accounts for all k+(k-1) squarings.

Take j=k-1. For fixed n, the section of D_{\mathbf u,\mathbf v} is an interval of m’s, possibly empty. In fact each condition puts m+\eta\cdot\mathbf v in [A,2A) and its product with the positive number n+\varepsilon\cdot\mathbf u in I; it therefore specifies an interval in m. Their intersection is an interval of length at most A. The final phase \Delta^m_{v_{k-1}}\cdots\Delta^m_{v_1}F_{\mathbf u} is linear in m with coefficient

A geometric-sum estimate bounds each m-sum by the corresponding minimum in (5.9). Summing over at most B values of n, the remaining normalized sum is bounded by that minimum divided by A. The shifts have normalizing factor B^{-k}A^{-(k-1)}, which proves (5.9).

For (5.8), perform the same square expansion k-1 times in a single variable. The translated intersections of J are intervals of length at most M, and the final linear coefficient is k!b_km^ku_1\cdots u_{k-1}. The normalizing factor is M^{-(k-1)}, followed by M^{-1} for the final geometric sum. This proves the first bound as well.□

Proof of Proposition 5.3. We now apply the differencing bounds to Vaughan’s decomposition. We first prove the estimate with \Lambda in place of \Lambda'. Put e_0=\rho/(100k) and Z=Y^{e_0}. For an arithmetic function g, write g_{\le Z}(n)=g(n)\mathbf 1_{\{n\le Z\}} and g_{>Z}=g-g_{\le Z}. Let \mu denote the Möbius function, let 1 denote the constant arithmetic function, and use * for Dirichlet convolution. Vaughan’s identity, in the form used here, is

This decomposition is classical; see [25, Chapter 3]. It follows directly from \log=1*\Lambda and \mu*1=\mathbf 1_{\{1\}}: split \mu at Z in \mu*\log, and then split \Lambda at Z in the term \mu_{>Z}*1*\Lambda.

The two sums with a short variable. The middle two terms of (5.12) reduce to sums with an outer variable m\le Z^2 and an inner variable n\le Y/m. The outer coefficient is either \mu(m) or \sum_{ab=m,\,a,b\le Z}\mu(a)\Lambda(b), and therefore has size Y^{o(1)}. The inner weight is respectively \log n or 1. Fix m, let M=\lceil Y/m\rceil, and consider any interval subsum S_m=\sum_{n\in J}e(f(mn)) of the inner sum.

Apply (5.8). For every integer r,

since \|k!u\|\le k!\|u\|. Tuples with a zero shift contribute O_k(M^{-1}) after normalization. For the others group by r=m^k|u_1\cdots u_{k-1}|\le m^kM^{k-1} and apply Lemma 5.4. The divisor bound gives

Here and below logarithmic factors are included in Y^{o(1)}. For completeness, the four terms after 1/M result from expanding

As m\le Y^{2e_0} and M\ge Y^{1-2e_0},

The remaining terms also save a positive power of Y. Taking the 2^{k-1}-st root in (5.13) therefore gives S_m\ll M Y^{-c} for some c=c(k,\rho)>0, uniformly in the subinterval. Partial summation permits the weight \log n with a further O(\log Y) factor. Since

both short-variable terms save a fixed power of Y after including the outer coefficients.

The bilinear sum. For the final term of (5.12), group the factors as (\mu_{>Z}*1)(m)\Lambda_{>Z}(n). Each coefficient is Y^{o(1)} when mn\le Y, and a nonzero coefficient requires both m>Z and n>Z. Partition into dyadic boxes

There are O(\log^2(2Y)) relevant boxes. Divide out the coefficient bounds to reduce to |a_m|,|d_n|\le1. If AB<Y^{1-e_0}, the trivial estimate is already sufficient. Otherwise put R=A^{k-1}B^k and apply (5.9).

There are k shifts of range B and k-1 of range A. Tuples containing a zero shift contribute O_k(A^{-1}+B^{-1}). Group the others by their nonzero absolute product, at most R. Lemma 5.4 and the divisor bound imply

Indeed the nonzero-shift bound before expansion is

the additional term O(\log(2q)/A) is included in Y^{o(1)}/A. Now A,B\ge Y^{e_0}/2, while

Thus (5.14) saves a fixed power. Restoring the coefficients and summing the boxes preserves a positive saving.

The remaining term \Lambda_{\le Z} costs only O(Z\log(2Z)). This proves the required estimate for \Lambda, with some positive exponent depending only on k,\rho. Removing higher prime powers costs O(Y^{1/2}\log^2(2Y)), as in Proposition 5.2. Decreasing the exponent if necessary gives c_m\in(0,1/4) and proves (5.5).□

Proof. Use major arcs of radius 3N^{-1+\eta} around the reduced rationals with denominator at most N^\eta. They are disjoint for large N, since 3\eta<1. The remaining points form the minor arcs. We first bound both transforms on the minor arcs; on a major arc we will compare their local coefficients.

Write V_N(y)=N^{-1}\sum_{n\in[N]}e(yn). Expanding the congruence indicator in (6.5) gives

There are O(DH^2) terms. Their centers \xi-j'/D are distinct: an equality would give a rational with denominator both coprime to D and dividing D, and hence an integer. Each center has denominator at most DH\le N^{3\beta/2}\le N^\eta. On minor arcs, geometric summation therefore gives

To estimate S_1, first consider, with any linear twist y', the sums

over subintervals I of (x_*,X]. On setting n=T_l(m), expand the restriction n\equiv r_l\pmod l as the average of its l additive characters. Each resulting prime sum has a polynomial phase in n whose coefficient of n^k is b_k=\alpha a/\lambda(l); the new twists change only the linear coefficient because k\ge2.

Fix a representative of \alpha and apply Dirichlet approximation to \vartheta=(k!)^2b_k with

The resulting reduced fraction a'/q satisfies q\le Q_0 and |\vartheta-a'/q|\le1/(qQ_0)\le q^{-2}. By (6.9), this places \alpha within O(N^{-1+\eta/2}) of a rational of denominator at most (k!)^2aq. For a minor-arc point that denominator must exceed N^\eta for large N. Hence, using Y\le N and absorbing the fixed factor (k!)^2a,

Proposition 5.3 applies uniformly in the linear twists and in the interval, and gives a bound O(Y^{1-c_m}). The relation Y=ClU and the lower bound in (6.9) imply

This accounts for the dependence on l before any periodic weight is expanded.

By (6.7), the supremum and total variation of F'/N on [x_*,X] are O(U^{-1}). Partial summation therefore retains an O(N^{-\nu}) bound after including this weight. Use normalized Fourier coefficients on each finite period for the other weights. Since \rho_D is a constant times one residue-class indicator, its Fourier \ell^1 norm is n_{d_r}\le D. For B_u the bound by its period times its supremum gives Fourier \ell^1 norm at most u^2. Expanding the weights in (6.8), and using \varphi(l)/l\le1, yields

The powers in (6.12) and (6.13) are 2\beta-\eta and 5\beta/2-\nu, respectively. Both are smaller than -\beta\gamma/4, so these bounds are O(H^{-\gamma/2}).

Now let \alpha=\alpha_0+y be on a major arc, with q=q(\alpha_0)\le N^\eta and |y|\le3N^{-1+\eta}. Decompose \alpha_0=\alpha_D+\alpha_1 into the prime-power denominator parts supported, respectively, on primes dividing D and on primes not dividing D. The coefficient in (6.11) belonging to the center \alpha_0, or zero if that center is absent, is

Here the sign follows from \alpha_D=-j'/D at that center. Every other center is at circle distance at least 1/(qDH) from \alpha_0. Since |y|qDH=o(1), geometric summation in each of the O(DH^2) terms gives

We next derive the corresponding coefficient for S_1, including the normalization of the prime weights. For squarefree u\le H coprime to D, let A_u be the unit mean of

Its period divides b=qDu, and \|b_u\|_\infty\le Du. For x_*\le x'<x''\le X, Proposition 5.2 gives

Indeed, one class m\equiv c\pmod b corresponds to the class r_l+lc\pmod {lb} in a prime interval of length l(x''-x'). It is reduced exactly when (T_l(c),b)=1, since (r_l,l)=1. For such a class the factor \varphi(l)/l changes the prime main term to (x''-x')/n_b, by (6.6). On a nonreduced class the only possible primes divide lb, and their total logarithmic weight is O(\log(lb)), with zero main term. Apply the progression bound at both endpoints, then sum its errors over at most b=qDu classes with weights of modulus at most Du. This proves (6.16), including the nonreduced classes.

The smooth factor F'(x)e(yF(x))/N has supremum plus total variation

For example, its derivative is bounded in integral by the contributions of F''/N and 2\pi |y|(F')^2/N, which are O(U^{-1}) and O(N|y|/U) by (6.7). Partial summation in (6.16) therefore produces main term

The normalized integral N^{-1}\int_{F(x_*)}^{N}e(yt')\,dt' differs from V_N(y) by O(a_l/N+(1+N|y|)/N): the missing initial interval has length F(x_*)\ll a_l, and comparison of the integral on [0,N] with its integer sum costs O(1+N|y|). It follows that

Here are the error bounds underlying this assertion. Since Y^{31/32}/U\ll lN^{-1/(32k)}, the summed progression error is at most

The replacement of the integrals costs, using |A_u|\le Du,

The error in (6.15) is at most N^{\eta+7\beta/2-1}. All three estimates are O(N^{-\beta\gamma/4}): indeed \beta,\zeta\le\eta/1000, \eta=1/(10000k), and \gamma<1. The first exponent has a strict margin, so its o(1) loss is harmless.

It remains to compare c and c_0. This is precisely the reason for the unit means and the regular argument classes used above. At primes dividing D, the common factor in each A_u is

To see both cases, factor \rho_D and the unit mean prime by prime. At p\mid D the chosen class has weight of unit mean one and prescribed F-value modulo p^{E_p}. A character of conductor at most p^{E_p} therefore gives its value at r. A primitive character of higher conductor averages to zero, since Lemma 2.3 gives uniform higher lifts of F on that class, all still satisfying the unit condition.

Put q_1=q(\alpha_1). If u has a prime factor outside q_1, its local B_p factor has unit mean zero and A_u=0. For p^j\Vert q_1, write \alpha_p for the p^j-part of \alpha_1 and let

The surviving A_u, for squarefree divisors u of q_1, are \chi_D(\alpha_0) times products that choose b_{p,j} when p\mid u and a_{p,j} otherwise. Moreover,

For j=1, the weight 1+B_p=\psi_p pushes the unit mean forward to \pi_p. For j\ge2, it is supported on allowed regular classes modulo p, and their uniform argument lifts give uniform lifts of the F-value. The primitive character therefore has mean zero.

If q_1\le H, every squarefree divisor needed in the product expansion occurs in the sum for c. Thus (6.19) and (6.18) show that c=c_0, including the case of a nonsquarefree q_1, when both vanish. If q_1>H, the model coefficient is zero. Lemma 2.2 gives |a_{p,j}|\le p^{-8\delta j}, while (6.3) and (6.19) give |b_{p,j}|\le2p^{-\gamma j} (for j\ge2 one has b_{p,j}=-a_{p,j}). Bounding the truncated product expansion by the full sum of absolute values, and using (3.16), we obtain

Indeed p^{\gamma/2}\ge3, so each factor is at most p^{-\gamma j/2}. Together with (6.15) and (6.17), this proves the comparison on major arcs. The minor-arc bounds already proved complete the lemma.□

Proof of Proposition 6.1. Extend J_1,J_2 by zero to \Z and put

To keep track of signs and normalizations, let \widetilde J_i(\alpha)=\sum_xJ_i(x)e(-\alpha x), with counting measure in this transform. Character orthogonality gives

Both counting-measure \ell^2 norms are at most \sqrt N. Cauchy–Schwarz, Plancherel, and Lemma 6.2 therefore imply |\mathcal B_1-\mathcal B_0|\ll H^{-\gamma/2}. The forbidden-support hypothesis gives \mathcal B_1=0. For every contributing pair in \mathcal B_0, the ordering and the residue classes imply 1\le n\le N and n\equiv r\pmod D. Substituting (6.5) and setting y=x+n thus yields

This is exactly (6.4).□

Proof. The coefficient on the left is the sum of \widehat{f_s}_I(\xi+\omega)e(b\omega) over the frequencies \omega on X_B retained by the lift. The denominator condition retains every \omega, because q(\xi+\omega)=q(\xi)q(\omega)\le Q. Orthogonality of these q_B characters imposes x\equiv b_p\pmod p for every p\in B and contributes the factor q_B. Together with the factor M_0 in f_s, this gives (7.4).□

Proof. The scale bounds follow from D\le L_D\le D^k and M_0\ge2; their first inequality holds for sufficiently large N because k\tau<1/2. In particular, with Q'=n_B^\beta,

By Proposition 4.1, it is enough to prove (7.5) for Z_{l,\mathcal S}(g), where g is any one of the specialized inputs.

First keep only the frequencies of g with denominator at most H, and call the resulting real function g_{\le H}. Telescope the diagonal integral one slot at a time. Lemma 4.3, followed by Proposition 4.4 and Lemma 4.5, bounds the change by

Indeed specialization costs q_B^{1/2} in the L^2 norm of the removed part, and q_B^{1/(2(d-1))} in each of the other d-1 norms. Their product is q_B. All frequency selections retain whole exact supports before specialization, as required by the moment bound. Here N\ge10Q^6 for large N, and the saving follows from \beta\gamma/2-\tau>\sigma.

The auxiliary-family identity transports avoidance along progressions of step L_D=\lambda(D). Since D\mid L_D, we split the prescribed class modulo D into its L_D/D classes modulo L_D. Let a'\bmod D be the class determined by this specialization. For j\in[L_D] with j\equiv a'\pmod D, set

Every integer of A in the class a'\bmod D has a unique representation L_Dx'+c_j of this form: take j to be its representative in [L_D]. The definition by membership in A excludes any surplus points beyond N in these progressions.

Each A'_j avoids at lD. More explicitly, a nonzero difference h_{lD}(m) with m\ge1 and T_{lD}(m) prime would give the difference \lambda(D)h_{lD}(m)=h_l(Dm-i) in A, where 0\le i<D is supplied by (2.3). We have Dm-i\ge1 and T_l(Dm-i)=T_{lD}(m), so this would violate avoidance at l. The nonzero condition is preserved because \lambda(D)>0.

Since q_BH\le Q, Lemma 7.1 now gives the exact identity

To check it, every prime divisor of L_D divides D, so multiplication by L_D is invertible on X_{\mathcal S} and preserves Fourier denominators. For q(\xi)\le H, the coefficient of the jth summand at \xi is \widehat{\mathcal H_j}(L_D\xi)e(-c_j\xi). Multiplication by the prefactor \Lambda_B/(L_D/D)=Dn_B/N and summation over j therefore gives (D/N)\sum_{x\in A,\ x\equiv a'\ (D)}e(-x\xi), which is exactly the coefficient in (7.4) for I=[N]. Both sides of (7.9) have zero coefficients at denominators greater than H.

There are L_D/D summands. The triangle inequality from Lemma 4.2 and its transport identity (4.3) imply

Increase the cutoff in \mathcal H_j from H to Q'. The same large-denominator argument, now without specialization, changes its diagonal integral by O(H^{-\gamma}N^{o(1)})=O(N^{-\sigma}). The moment hypothesis is valid at the new scale: n_B\ge10(Q')^6 for large N, by 6\beta<1 and (7.6).

The extended lift is obtained from \mathcal L_{[n_B],\mathcal P_{n_B},Q'}\mathbf1_{A'_j} by averaging out its coordinates in B\cap\mathcal P_{n_B} and adding unused coordinates in \mathcal S\setminus\mathcal P_{n_B}. Averaging contracts the seminorm, and adding unused coordinates does not change it, by Lemma 4.2. Consequently its diagonal integral is at most Y_{lD}(n_B,A'_j)\le\mathcal Y_{lD}(n_B). Combining this observation with (7.8) and (7.10) proves the diagonal bound, hence the stated multilinear bound. None of these steps restricts the size of l.□

Proof. The aim is to leave just the two endpoint lifts on an ordered cycle edge. We first average over short intervals, then truncate and expand the other inputs. Each expansion term uses prime coordinates with small product; conditioning on those coordinates leaves the pair to which Proposition 6.1 applies.

It suffices to use the probability laws \mu_{l,p}^\circ, since restoring the omitted masses multiplies the integral by \prod_p(1-\eta_{l,p})\le1. Partition [N] into m=\lfloor N^\tau\rfloor consecutive intervals of lengths as equal as possible. Each G_s is the weighted average of \mathcal L_{I,\mathcal P_N,Q}f_s over these intervals, with weights |I|/N. Thus the integral is an average over independently chosen intervals for all slots. Their lengths are comparable to N^{1-\tau}, so the lift moment bound applies because 6\beta+\tau<1. Ordinary Hölder and uniform marginals bound every interval assignment by N^{o(1)} in absolute value.

The probability that all L cycle slots use the same interval is \sum_I(|I|/N)^L=O(N^{-(L-1)\tau}). These assignments contribute O(N^{-\sigma}). For any remaining assignment, the cyclic sequence of interval indices is nonconstant, and hence has a strict increase along some directed cycle edge. Choose such an edge, with first endpoint in I_1 and second endpoint in the later interval I_2.

Keep the two endpoint lifts unchanged and truncate every other lift to denominators at most T=N^\tau. Telescoping with Lemma 4.3 and the lift moment bound costs O(T^{-\gamma}N^{o(1)})=O(N^{-\sigma}). Expand the truncated d-2 inputs into characters. Their coefficients have absolute value at most M_0, and each input has O(T^2) frequencies, so the sum of absolute coefficients in this product expansion is O(T^{2(d-2)}).

Fix one term. Let B be the union of the prime supports of its characters and write

Condition on the entire tuple of labels at every prime in B, taking any conditioning with positive probability under the product of the \mu_{l,p}^\circ. The expanded characters become constants of modulus one. The specialized endpoint lifts give functions g_1,g_2 on X_{\mathcal S}, and the laws at primes in \mathcal S remain unchanged. Translation invariance shows that their pair integral is

where \Gamma is the multiplier for this directed cycle edge. Indeed only opposite characters survive common translation, and their product is the character of the second label minus the first. By (6.3), Parseval, and the specialized moment bound, the part with q(\xi)>H is at most

For the remaining frequencies, HR\le Q and D\le N^\beta for large N, since (d-2)\tau<\beta/2. Apply Lemma 7.1 to the endpoint lifts, obtaining classes a'_1,a'_2\bmod D. Their directed difference is admissible at l: goodness supplies admissibility modulo M_0, and the cycle property of \mu_{l,p}^\circ supplies it at the conditioned primes p\in B. Set

as functions on [N]. Every contributing pair x,y has x<y because I_1 precedes I_2. Avoidance therefore gives y-x\notin\mathcal D_l. All hypotheses of Proposition 6.1 hold. Its frequency set \Xi is exactly the remaining frequencies on X_{\mathcal S} with denominator at most H: coprimality with D excludes the primes below P and the primes in B, while every prime in a denominator at most H is at most Q. The coefficient identity becomes

Consequently (6.4) bounds the low-denominator part of (7.13) by

After multiplication by the expansion bound O(T^{2(d-2)}), both (7.14) and (7.15) are bounded by

since (6.1) gives \beta\gamma/4>(3d+2)\tau+\sigma. These estimates are uniform in the conditioning, in the selected edge, and in the interval assignment. Averaging, and including the earlier truncation and coincident-interval errors, proves the proposition.□

Proof. Fix an avoiding set A. For assignments in (7.3) that are not good, apply Proposition 7.2 with B=\varnothing. Their proportion is 1-\rho_l. For a good assignment, Proposition 7.3 handles the product of the measures \mu_{l,p}-\varepsilon_{l,p}. The difference from the full product is

The positive product measure in the Bth summand has mass \eta_{l,B}. If this mass is zero the term vanishes. Otherwise, after normalization, every single-slot marginal is uniform by simultaneous translation invariance. Hölder and Proposition 4.4 thus bound its integral by N^{o(1)} in absolute value. The terms with q_B>N^\tau have total mass at most N^{-\tau}/4 by (7.16), and hence contribute O(N^{-\sigma}).

For q_B\le N^\tau, condition on all labels at the primes in B. The remaining law is the product of the full measures \mu_{l,p}, so Proposition 7.2 applies to the specialized inputs. Its factor \Lambda_B^d is at most 1+u_N by (7.6), and its errors sum to O(N^{-\sigma}) by (7.16). Taking absolute upper bounds in the signed expansion and averaging over the good assignments gives their contribution in (7.17). Finally maximize over A in (7.3).□

Proof. After all parameters in (6.1) have been fixed, choose a_0>0 sufficiently small and put b_0=2a_0/\zeta, so that

This is possible because s_0\to0 with a_0 while \rho_*>0 is fixed. If l>N^\zeta, then

The estimate (7.2), used with exponent a_0, proves (7.18) in this range after a fixed enlargement of C_0. This treats all such l,N before the induction.

For the remaining pairs, induct on the integer N, simultaneously for all l\ge1. At a sufficiently large scale with l\le N^\zeta, every successor in (7.17) satisfies n_B<N by (7.6). The induction hypothesis is available at lD_B whether or not that parameter satisfies lD_B\le n_B^\zeta. Since n_B\ge N/D_B^k, it gives

Use q_B^{s_0}\le q_B and (7.16) to bound the bracket in (7.17) by

where (7.11) was used in the last step. Choose a fixed threshold N_*, large enough for the recurrence and for

Such a threshold exists by (7.19) and u_N=o(1); it is independent of C_0\ge1. Dividing the recurrence by C_0l^{b_0}N^{-a_0} now proves the induction step, since C_0l^{b_0}\ge1. Finally choose C_0 large enough to cover both the previously treated range l>N^\zeta and every N<N_*, uniformly in l, by (7.2). This completes the induction.□

Proof of Theorem 1.1. At l=1 we have T_1(m)=m and h_1=h, so the hypothesis of the theorem is exactly avoidance at l=1. Combining (7.2) with (7.18) gives

Thus one may take c_h=a_0/d and C_h=C_0^{1/d}, for every N\ge1. Only strictly ordered pairs, and hence positive differences, were used in cancellation. Restriction to progressions preserved nonzero forbidden values and their prime arguments. A value h(p)=0 therefore imposes no additional condition at any stage.□