A power saving for intersective polynomial differences with an exponent depending only on the degree

Proof. Put u'_p=v_p(b_{m_p,p}). These are nonnegative integers, and the factorization argument above shows that S_0=\{p:u'_p>0\} is finite. For p\in S_0, take u_p=u'_p+1, and set

Choose the representative -D_0<r\le0 satisfying r\equiv\mathfrak z_p\pmod{p^{u_p}} for every p\in S_0, by the Chinese remainder theorem. If S_0 is empty, these definitions give D_0=M=1 and r=0.

For p\in S_0, the congruence defining r shows that w_p=(\mathfrak z_p-r)/D_0 lies in \Z_p; for p\notin S_0, the same conclusion follows because D_0 is a p-adic unit. Define g initially as the displayed rational polynomial. Its centered expansion is

If p\in S_0, the coefficient at j=m_p has valuation u'_p+u_pm_p-(u_pm_p+u'_p)=0. For j>m_p, its valuation is at least

If p\notin S_0, both D_0 and M are p-adic units, so every coefficient is integral and the coefficient at j=m_p is again a unit. Thus the centered expansion belongs to \Z_p[X] for every prime p. Translation by -w_p\in\Z_p shows that g itself belongs to \Z_p[x]. Every rational coefficient of g is therefore integral at every prime and hence is an integer.

The elements w_p are roots of g; reducing them at the prime-power factors of any modulus and applying the Chinese remainder theorem proves intersectivity. The degree and sign of the leading coefficient are preserved because D_0,M>0. Finally, the defining identity for g gives Mg(n)=h(r+D_0n), and r>-D_0 gives r+D_0n\ge1 for n\ge1.□

Proof. Only primes dividing \lambda(l) can occur in denominators of the coefficients of h_l. Fix such a prime, put u=v_p(l)>0, and use the affine coordinate

Its slope is a unit, and expansion at \mathfrak z_p gives

The prefactor is a p-adic unit, and the displayed polynomial is integral over \Z_p. This proves h_l\in\Z[x].

For every prime p, the element (\mathfrak z_p-r_l)/l belongs to \Z_p: when p\mid l, this uses the defining congruence for r_l, and otherwise l is a unit. It is a root of h_l. Reducing these roots at the prime-power factors of an arbitrary modulus and applying the Chinese remainder theorem proves intersectivity.

Substitution of \mathfrak z_{p,l}+X into the definition of h_l gives the centered expansion in (2.1). Complete multiplicativity gives v_p(\lambda(l))=m_pv_p(l), so l^{m_p}/\lambda(l) is a unit in \Z_p. This proves the exact valuation there, including the preservation of the multiplicity and of the unit condition. The assertion is local at p; the displayed quotient need not be an integer.

The degree and leading coefficient follow from the definition. Expanding h(r_l+lx) and using |r_l|<l bounds every coefficient by O_h(l^k/\lambda(l))=O_h(a_l).

The same root choices give r_{lD}\equiv r_l\pmod l. The representatives of this class in (-lD,0] are exactly r_l,r_l-l,\ldots,r_l-(D-1)l, so r_{lD}=r_l-il for some 0\le i<D. Complete multiplicativity of \lambda now gives the polynomial identity in (2.2). The remaining bounds follow from 1\le m_p\le k, while \lambda(p)=p^{m_p} gives the equality of prime supports. Finally, Dx-i\ge D-(D-1)=1 for x\ge1.□

Proof. Choose an initial threshold so that the preceding nonconstancy holds and p>k. Under Condition (U), this initial threshold can be chosen using only k. The nonzero polynomial F'\bmod p has degree at most k-1, which gives the count of regular arguments; taking p\ge2(k-1) also makes at least half of the arguments regular.

First consider the sum modulo p, and let k' be the degree of F\bmod p. If k'=1, the sum is zero. If k'\ge2, repeated differencing gives

where \Delta_bF(x)=F(x+b)-F(x). To obtain the inequality, square the mean, express it as the mean of multiplicative differences, and iterate the triangle inequality and Cauchy–Schwarz. The reduction modulo p of u\Delta_{b_1}\cdots\Delta_{b_{k'-1}}F has degree at most one, with coefficient of x equal to u k'! times the leading coefficient of F\bmod p times b_1\cdots b_{k'-1}. Its character mean vanishes unless one increment is zero. The right-hand side is therefore at most (k'-1)/p. Since 8\delta<2^{1-k}\le2^{1-k'} and 1\le k'\le k, increasing the threshold by an amount depending only on k gives the first bound in (2.4) for j=1. Removing at most k-1 arguments gives

The first bound and another increase depending only on k give the second bound in (2.4).

For j\ge2, put n=\lfloor j/2\rfloor. Write x=x_0+p^{j-n}y, where x_0 runs modulo p^{j-n} and y runs modulo p^n. Taylor expansion modulo p^j leaves only the linear variation, because 2(j-n)\ge j. The average over y vanishes unless F'(x_0)\equiv0\pmod{p^n}. We claim that these arguments occupy at most k-1 classes modulo p^v, where v=\lceil n/(k-1)\rceil.

Otherwise choose k integer representatives x_1,\ldots,x_k in distinct such classes with p^n\mid F'(x_i). Interpolation of the degree-at-most-k-1 polynomial F' gives

Each denominator has valuation at most (k-1)(v-1)<n, whereas the numerator polynomial has integral coefficients. Every coefficient of every summand is therefore divisible by p in \Z_p. This contradicts F'\not\equiv0\pmod p and proves the claim. Since v\le n\le j-n, the density of the surviving arguments is at most

Here n\ge j/3. Since 1/(3(k-1))>8\delta, one fixed increase of the prime threshold absorbs the factor k-1 for every j\ge2. All choices of threshold are uniform in l and u; fix P_1 large enough to satisfy them all. After the initial nonconstancy condition, every increase used only k. This proves the stated degree-only choice under Condition (U).□

Proof. For a nonconstant polynomial over \Z_p, consider the ideal generated by its nonconstant coefficients. An affine substitution with unit slope preserves this ideal: substitution gives one inclusion, since a constant cannot contribute to a nonconstant coefficient, and the inverse affine substitution gives the reverse inclusion. Thus it preserves the minimum valuation of the nonconstant coefficients.

Apply this observation to the translation by \mathfrak z_{p,l}. Equation (2.1) displays a nonconstant coefficient of valuation v_p(b_{m_p,p}), so the minimum for F=h_l is at most that number, uniformly in l. Differentiation multiplies the coefficient of degree j by j. Hence some coefficient of F' has valuation at most v_p(b_{m_p,p})+T_{k,p}.

The matrix V_k maps the coefficient vector of a polynomial of degree at most k-1 to its values at 0,1,\ldots,k-1. Its determinant is \prod_{0\le i<j\le k-1}(j-i)=\prod_{j=1}^{k-1}j!, and its adjugate has integer entries. If every value F'(x), 0\le x<k, had valuation greater than S_p, multiplication by V_k^{-1}=\operatorname{adj}(V_k)/ \det V_k would give valuation greater than S_p-v_p(\det V_k)=v_p(b_{m_p,p})+T_{k,p} for every coefficient of F'. This contradicts the preceding bound and proves the lemma.□

Proof. Taylor expansion over the integers gives

Indeed the linear coefficient is p^EF'(x_0)/p^s, and every term of degree at least two is divisible by p^{E+1}, since E-2s\ge1. The polynomial T(y)=c_1y+pC(y) induces a bijection modulo every power of p: its difference at two arguments is their difference times a p-adic unit, so the induced map on each finite residue ring is injective and hence bijective.

For a uniform argument in the stated class modulo p^j, the variable y is uniform modulo p^{j-E+s}. Its reduction modulo p^{j-E} is still uniform, with each residue occurring p^s times. The bijectivity of T at this latter modulus proves the asserted distribution of F.□

Proof. If p<P_1, repeat any admissible residue L times. The sum is zero because p^{E_p}\mid L.

If p\ge P_1, let R be h_l(x) for a uniform regular argument x\bmod p, and take independent copies R_1,\ldots,R_L. Fourier inversion gives

By (2.4), the sum following 1 has modulus at most (p-1)p^{-4\delta L}<1. The probability is therefore positive, and any realization with sum zero supplies the required residues.□

Proof. Reversing a directed edge replaces the one-edge operator by its adjoint, so its norm remains at most p^{-4\delta}. The case e_G=0 is immediate; assume e_G\ge1. For the first assertion, replace the edge weights by c_p one at a time. In a term containing the difference for an edge x\to y, fix all labels other than Y_x,Y_y. Because there is no other edge on this unordered pair, the remaining factors separate into a function of Y_x and a function of Y_y, each bounded by one and hence of uniform L^2 norm at most one. The one-edge operator estimate bounds this term by p^{-4\delta}. Summing over the e_G replacements gives the stated error e_Gp^{-4\delta}.

For the second assertion put B=K_G-c_p^{e_G}. If the two configuration spaces have cardinalities N_X,N_Y, the kernel operator (T_Bf)(X)=\E_Y B(X,Y)f(Y) has Euclidean matrix B(X,Y)/\sqrt{N_XN_Y} under the isometries from uniform L^2 to Euclidean space. Thus, with two independent copies of each list, matrix multiplication gives

where s_j(B) are the singular values for the normalized measures. Indeed, the trace of (T_BT_B^*)^2 is the uniform average of B(X_0,Y_0)\overline{B(X_1,Y_0)}B(X_1,Y_1)\overline{B(X_0,Y_1)}; here B is real, so the conjugates can be omitted. This explains why no factor depending on N_X,N_Y occurs. Expand the four copies of B. A product using any subset of the four corners again comes from a graph of the stated kind: an unordered pair of its formal endpoints determines both the original edge and its corner. A term using j corners has exactly je_G edges, so its graph error is at most je_Gp^{-4\delta}. Its constant multiplier has modulus c_p^{(4-j)e_G}\le1. All main terms are c_p^{4e_G} times the corresponding sign, so they cancel. Consequently

because \sum_{j=0}^4\binom4j j=4\cdot2^3=32. Taking fourth roots proves (3.1).□

Proof. The interaction between the two halves is governed by the symmetric matrix

Fix x\in V_+, and suppose that the cut symbols occur at positions i<j in its cut block, with gap g=j-i. Swapping the cut symbols gives the diagonal entry \mathsf A_{xx}=\Delta^g. Any other transposition carrying x across the cut must move the first cut symbol to a position beyond j, or the second to a position before i. Its gap is at least g+1. There are fewer than L^2 such transpositions; transpositions in other blocks do not cross the cut. Consequently the absolute off-diagonal row sum is at most L^2\Delta^{g+1}=\Delta^g/10. Symmetric diagonal dominance gives

For j\in[\ell_s]^{V_+} define u(j)=(\1_{\{j_x=i\}})_{x\in V_+,\,i\in[\ell_s]}. After identifying the minus side with the plus side by reflection, the cross-interaction matrix on half-index assignments is

Split \mathsf A=(\mathsf A-\kappa\operatorname{Id})+ \kappa\operatorname{Id}. The entrywise exponential associated with the first summand is positive semidefinite: its power-series expansion is a sum of Gram matrices of tensor powers. Its diagonal entries are at least one. The exponential associated with the second summand is a tensor product, over x\in V_+, of

on [\ell_s]. It therefore dominates a_*\operatorname{Id}, where a_*=(\exp(\kappa)-1)^{n_*}. The entrywise product of positive semidefinite matrices is positive semidefinite, as follows directly from their Gram representations. Multiply the lower bound for the second exponential entrywise by the first. The resulting diagonal lower bound is at least a_*\operatorname{Id} because the first exponential has diagonal entries at least one. Thus C\succeq a_*\operatorname{Id}.

The interactions within the two halves give the same diagonal factor on either side of C, with all entries at least one. The full index matrix retains the lower bound a_*\operatorname{Id}. For fixed lists Y, reflected vertices have the same address because b is marked. The half-label evaluations therefore form the same vector on both sides of this matrix, even when some field labels coincide. There are \ell_s^{n_*} half-index assignments. Averaging uniformly on both sides converts the matrix lower bound into

Multiplying by I_S(Y) and averaging Y proves (3.2) with c_*=a_*\ell_{t+1}^{-n_*}.□

Proof. Reflection identifies the minus lists and their internal edge factors with the plus lists and their internal factors. No index interaction crosses this cut: an interaction changes only a marked block, whereas the cut is determined by the unmarked block b. The two within-half index weights are likewise identified by reflection; write R_+ for the one on the plus half.

Let K(Y_+,Y_-) be the product of all cross-list edge weights. Then Q_S(J) is the quadratic form of this kernel on the half function

Cauchy–Schwarz, the uniform bound on R_+, and I_+^2\le I_+ give \|g\|_2^2\le C\mathcal D_S(J). By (3.1), the kernel K differs in operator norm by O(p^{-\delta}) from the constant c_p^{e_{\rm cross}}, where e_{\rm cross} is its number of edges. The constant contributes c_p^{e_{\rm cross}}(\E g)^2\ge0. This proves (3.3). In the terminal case I_S=1, so the cross kernel is exactly one and the entire form is nonnegative.□

Proof. Let \Pi_+ be the r_* words in block b satisfying the cut order. For each new address u\in U_{S'}, the old plus addresses above it are (u,q) with q\in\Pi_+; here q is inserted in block b. Concatenate their lists by identifying

This is a bijection of independent uniform list entries, so it changes neither their joint distribution nor the value of an average. Figure 1 separates this relabeling from the index restriction used below.

A new address edge requires t+1 shifted blocks outside S'. Those blocks also certify an old edge for every choice of the two words in block b. Hence every factor of I_{S'}(Y') occurs, with its direction unchanged, among the factors of I_+(Y_+). Since all factors belong to [0,1],

When S' is terminal this inequality follows from I_{S'}=1.

Apply (3.2) to S'. In its nonnegative right-hand side, restrict the new index at each v\in V_+ to the sublist \{v_b\}\times[\ell_s]. Each restriction has probability 1/r_*, independently across the n_* slots. On this event the labels and the remaining independent indices are exactly those in \mathcal D_S(J). Its probability is r_*^{-n_*}, and the pointwise weight comparison above now yields (3.4).□

Proof. At a cut in block b, pair each S with b\notin S, |S|\le t, with S\cup\{b\}. Each component containing b appears in exactly one pair. Equations (3.3) and (3.4) bound the quadratic form of the pair below by

This is nonnegative once p is sufficiently large. The only unpaired sets are terminal sets omitting b; their forms are nonnegative by Lemma 3.3. Thus M_{l,p} is reflection positive at every cut.

For S=\varnothing, each list has length one and R_S=1. Lemma 3.1 and c_p\ge1/(2k) show that \nu_{\varnothing}(1) is bounded below by a fixed positive constant for all sufficiently large p. All component masses are bounded above, and the number of components is fixed. It follows that

Our choice (t+1)\delta/2>5 gives the stated bound p^{-4} after increasing the prime threshold. Summing the nonleading coefficients also gives total probability O(p^{-\delta/2}) for S\ne\varnothing. Removing the terminal components retains the positive leading mass, so the same estimate holds after normalization to \mu_{l,p}^{\circ}.

Simultaneous translation of all list entries preserves their product law, all differences in I_S, and the index weight R_S. It therefore translates every output label and proves the asserted invariances and marginal uniformity.

Finally, a nonterminal S leaves at least t+1 blocks unmarked. Consecutive cycle vertices shift by c in all these blocks, including the edge from v_{L-1} to v_0. Their addresses are consequently joined by a directed edge. Since its weights include every pair of list entries, any positive-weight label tuple has admissible increment on this edge, regardless of the chosen indices. This holds around the entire cycle in every component retained by \mu_{l,p}^{\circ}.□

Proof. Equation (2.2) states that h_l(Dx-i)=\lambda(D)h_{lD}(x). Both D and \lambda(D) are units modulo p. The argument map x\mapsto Dx-i is therefore a bijection and, on differentiating this identity, preserves regularity. Counting regular arguments gives

Apply (3.5) to every list entry in a component measure. The independent uniform list law and all index weights are unchanged; each old edge weight becomes exactly the corresponding new edge weight. Thus the map pushes \nu_{l,p,S} to \nu_{lD,p,S} for each S. All component masses, and in particular the normalizing masses M_{l,p}(1) and M_{lD,p}(1), agree. The two claimed pushforwards follow with no additional factor.□

Proof. First normalize the leading component \nu_{\varnothing}, and write x=z_v, y=(z_{v'})_{v'\ne v}. Before normalization its density relative to uniform labels is K_1(x,y)K_2(y), where K_1 is the product of the m weights on edges incident to v, and K_2 contains the remaining weights. Put

The incident edges form a graph between the singleton list x and the list y. Equation (3.1), applied to this kernel, gives

This includes m=0, when A=1 and B_f=0.

Let Z_0=\nu_{\varnothing}(1), which is bounded below uniformly. The other-label marginal has density Z_0^{-1}K_2(y)A(y), and the conditional expectation equals B_f(y)/A(y) where A(y)>0. Its squared norm is therefore exactly

with the ratio taken as zero if A(y)=0. On A\ge c_p^m/2, the bound on B_f makes this O(p^{-2\delta})\|f\|_2^2. The complement has uniform probability O(p^{-2\delta}), by the bound on A-c_p^m and the fixed positive lower bound on c_p^m. Everywhere, weighted Cauchy–Schwarz gives

Since K_2\le1, the complement has the same required bound. Thus the squared conditional norm in the normalized leading component is O(p^{-2\delta})\|f\|_2^2.

For either mixture, condition additionally on its component index. The tower property and Jensen’s inequality can only increase the squared conditional norm under this extra conditioning. In each nonleading component the trivial bound is \|f\|_2^2, because its single-slot marginal is uniform. Proposition 3.5 bounds their total probability by O(p^{-\delta/2}). The squared norm for the mixture is consequently O(p^{-\delta/2})\|f\|_2^2, and the norm is O(p^{-\delta/4})\|f\|_2. Since \gamma=\delta/10, the fixed implicit constant is absorbed by taking p sufficiently large, proving (3.6).□

Proof. For every prime p\ge P_1, the quantitative local input to the estimates above is

Indeed, with the normalized Fourier convention, for u\ne0 the coefficient \widehat W_{l,p}(u) is c_p times the corresponding regular-argument average in (2.4); also c_p\le1. These statements hold uniformly in l. We extract constants from the preceding proofs using

They depend only on k,L,t, since d=(L!)^{2t+1}.

For a set of s marked blocks, the graph on list entries has K^{w-s}\ell_s=d/2^s\le d formal vertices. Its simplicity was checked above before field labels were assigned, so coincidences between their values do not affect the graph bound. Every graph for I_S, every cross-list graph in Lemma 3.3, and every incident graph in Lemma 3.7 consequently has at most e_* edges. Lemma 3.1 therefore bounds their graph errors by e_*p^{-4\delta}. For the cross-list and incident graphs, which join two lists, it bounds the operator errors by C_{\mathrm{gr}}p^{-\delta}.

Each index interaction H^S_{xy} is at most one, so R_S and every within-half weight R_+ are at most R_*. In particular, \nu_S(1)\le R_*. The proof of Lemma 3.2 gives the explicit constant

The exact half-index factor \ell_s^{-n_*} proved there and the exact index-restriction factor r_*^{-n_*} in Lemma 3.4 give the domination constant c_*r_*^{-n_*}. In the unmarked proof, Cauchy–Schwarz and I_+^2\le I_+ give \|g\|_2^2\le R_*^2\mathcal D_S(J). The list bound just obtained thus allows the constant in (3.3) to be

The pairing proof of Proposition 3.5 is therefore nonnegative at every cut whenever

Let e_0\le e_* be the number of edges in the leading component. The graph estimate and the lower bound on c_p give

Consequently \nu_{\varnothing}(1)\ge Z_* once e_*p^{-4\delta}\le Z_*. There are at most 2^w components, each of mass at most R_*. Set

The normalizing mass M_{l,p}(1) is at least the leading mass, so

It is at most p^{-4} if p^{\alpha_{\mathrm{exc}}-4}\ge C_{\mathrm{mass}}. In either \mu_{l,p} or \mu_{l,p}^{\circ} the probability of nonleading components is at most C_{\mathrm{mass}}p^{-\delta/2}. For the latter law, its unnormalized mass after removing the terminal terms still contains \nu_{\varnothing}(1)\ge Z_*; hence the same denominator bound applies without an additional normalization factor. Cycle support and translation invariance in Proposition 3.5 are exact properties of these components and impose no further threshold.

For the leading component in Lemma 3.7, the incident graph has m\le e_* edges. Its list operator error is at most C_{\mathrm{gr}}p^{-\delta}. The split into A\ge c_p^m/2 and its complement in that proof therefore bounds the squared conditional norm by

Using Z_0\ge Z_* and c_p^{-m}\le(2k)^{e_*} bounds this by

The case m=0 already has zero conditional norm. For either mixture, conditioning additionally on the component index and applying Jensen’s inequality bounds its squared conditional norm by

Here the bound in every other component is \|f\|_2^2 because its single-slot marginal is uniform. As \delta/2-2\gamma=3\delta/10>0, the desired squared bound p^{-2\gamma}\|f\|_2^2 follows once

Choose an integer P>P_1 large enough that the displayed requirements on p above hold for every p\ge P, and that P^{\gamma/2}\ge3. This is possible because \delta>0, \alpha_{\mathrm{exc}}-4>0, and \delta/2-2\gamma>0, and all the constants depend only on k,L,t. The product condition in (3.7) can be included in the same choice: for integer P\ge2,

whose last expression tends to one. The covariance proof uses only the exact progression identity and bijections when p\nmid D, so it imposes no further restriction on P. This proves the stated dependence of P. Under Condition (U), Section 2 allows P_1,L to be chosen from k and each E_p from k,p. Also, t is chosen from \delta, which depends only on k. The product defining M_0 then uses a degree-dependent set of primes and degree-dependent exponents. For a general fixed polynomial, M_0 retains any dependence of the local exponents E_p as well as that of P_1 and L.□

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 \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 (3.5) 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 \E_{\mathfrak m_p}T_pf=\E f. By (3.6), 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 u be the largest cardinality of a support whose prime product is at most Q. 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\1_{\{x\equiv z_p\pmod p\}}-1. Different supports B\supseteq J have disjoint sets of outside characters. Conditional Parseval therefore identifies the left side of (4.6) with the squared Euclidean norm of this coefficient vector on the union of those character 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

The associated Fourier analysis map has norm squared equal to this 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 \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, integration outside W' leaves exactly \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. 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 color independently and uniformly. 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 \E|G|^s is q_B^{-1}\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. The lift is real and has uniform mean |A|/N. The lower bound follows from Lemma 4.2. Ordinary Hölder and the uniform single-slot marginals give

The integer d is even. Also 6\beta<1, so for all sufficiently large N one has N\ge10Q^6. Apply (4.5) with moment order d, choosing its exponent small enough that its d-th power is at most C_\epsilon N^\epsilon. In the bounded remaining range of N, the lift has a bounded number of coefficients, each of modulus at most one. The probability normalization then supplies a uniform bound independent of l, and enlarging C_\epsilon finishes the proof.□

Proof. Put A_l=k!a_l, \theta'=A_l\alpha, and Q_0=\lfloor N^{1-\eta}\rfloor. Pigeonholing the Q_0+1 points 0,\theta',\ldots,Q_0\theta' into Q_0 equal intervals gives a reduced rational a'/q' such that

Lifting this approximation through multiplication by A_l places \alpha within 1/(A_lq'Q_0) of a rational with denominator at most A_lq'. If A_lq'\le N^\eta, this would place \alpha in a major arc, since Q_0^{-1}\le2N^{-1+\eta}. Therefore A_lq'>N^\eta, and in particular

using A_l\le N^{\eta/8}.

Choose M=\lceil2U\rceil. Since X<2U, this integer is larger than all the interval lengths under consideration. Also U\ge1, so the absolute comparison 2U\le M\le2U+1\le3U holds. Repeated differencing gives

Here the minimum equals M when the distance is zero. To verify the estimate, square the sum and group pairs by their difference. After taking absolute values, square again and use Cauchy–Schwarz on the increment indices. At each step the inner sum is over an intersection of interval translates, hence an interval. After s steps the prefactor is M^{2^s-s-1}: its exponent is zero for s=1, and the next step doubles that exponent and adds s. After k-1 steps the phase is linear with coefficient k!a_l\alpha b_1\cdots b_{k-1}, and a geometric sum proves (5.8). The added linear term contributes only a constant after the first differencing and does not change the estimate. This derivation uses only |I|\le M, so also covers short intervals.

The tuples with a zero increment contribute O_k(M^{k-1}) inside the sum in (5.8). For the others, group by the absolute product m\le M^{k-1}. For each \epsilon>0 their multiplicity is O_{\epsilon,k}(m^\epsilon). Indeed, at a prime power p^a the number of exponent choices is a binomial coefficient of fixed degree in a; it is at most p^{a\epsilon} for all sufficiently large p. The finitely many smaller primes contribute a bounded extra factor, since a fixed polynomial in a divided by p^{a\epsilon} is bounded.

Partition the positive product indices into blocks of \lfloor q'/2\rfloor consecutive integers. If 0<b<q'/2, then

Thus the points in a block have spacing at least 1/(2q') on the circle. Ordering their distances to zero and summing the reciprocal-distance bound gives O(M+q'\log(2q')) per block. There are O(M^{k-1}/q'+1) blocks. Dividing (5.8) by M^{2^{k-1}}, and absorbing the divisor bound and logarithms into N^\epsilon, gives

Here M^k\ll N and M^k\gg N^{1-\eta/8}. The three terms are bounded respectively by N^{-\eta/2}, O(N^{-(1-\eta/8)/k}), and O(N^{-7\eta/8}). For sufficiently small fixed \epsilon, the displayed expression is O(N^{-\eta/4}). Taking its 2^{k-1}-st root proves (5.7), because \eta/(4\cdot2^{k-1})=5\nu.□

Proof. In a periodic mean we may average at any common multiple of the periods and separate prime-power factors by the Chinese remainder theorem. First consider a prime p\mid D, and abbreviate E=E_p, s=s_p. On the chosen argument class, Section 2 gives

where C has integer coefficients. The polynomial in parentheses is a bijection modulo every power of p: its difference at two arguments is their difference times a unit. Thus for a local frequency of denominator p^j with j\le E, the phase is constant at its value on r. This remains true if j>E-s. For j>E, uniform arguments in the restricted class modulo p^j give uniform z modulo p^{j-E+s}, hence uniform reduction modulo p^{j-E}. The F-values are consequently uniform among the lifts of r modulo p^j, and a primitive character has mean zero. The joint factor from primes dividing D is therefore

Put q_1=q(\alpha_1). If u has a prime not dividing q_1, its factor B_p has mean zero independently of all the other factors, so A_u=0. Thus only divisors of \operatorname{rad}(q_1)=\prod_{p\mid q_1}p contribute. For p^j\Vert q_1, let \alpha_p be the primitive p^j-denominator part of \alpha_1 and set

The Chinese remainder theorem now expresses the truncated coefficient as

The mean against 1+B_p=\psi_p is

For j=1 this is the defining pushforward of \psi_p. For j\ge2, condition on a regular argument modulo p. Its lifts are mapped uniformly to the lifts of its value, so their primitive character mean vanishes. This holds on each argument class separately, regardless of the size of \psi_p there.

If q_1\le H, all divisors of \operatorname{rad}(q_1) occur. Thus (5.10) factors as

For squarefree q_1 this is \chi_D(\alpha_0)\Gamma(\alpha_1); if any exponent is at least two, it is zero. These are precisely the cases in (5.6). The empty product, when q_1=1, also gives the required coefficient.

Suppose instead that q_1>H. The model coefficient is then zero. By (2.4), |a_{p,j}|\le p^{-8\delta j}. For j=1 the preceding identity and (5.1) give |b_{p,1}|\le2p^{-\gamma}; for j\ge2 the identity gives b_{p,j}=-a_{p,j}, hence again |b_{p,j}|\le2p^{-\gamma j}. Taking absolute values in (5.10) and dropping the divisor cutoff yields

Here \omega(q_1) is the number of distinct prime divisors, and the last inequality before the strict one follows from (3.7), since every prime of q_1 is at least P. This bound also covers \operatorname{rad}(q_1)\le H<q_1: in that case the full divisor product is present and is actually zero, because some exponent is at least two. If q(\alpha_D)\nmid D, all coefficients vanish already through \chi_D(\alpha_0).□

Proof of Lemma 5.2. On the minor arcs the two bounds already proved give

On a major arc, the error terms in the two approximations are at most

respectively. Each of these four bounds is O(N^{-\beta\gamma/4})=O(H^{-\gamma/2}) by (4.8). Indeed \nu=100\beta, \eta=1/(100k) and \beta=\eta/(1000\cdot2^k), so the two major-arc exponents are less than -0.99 and -0.97/k, respectively; the minor-arc exponents have still larger margins than required. Lemma 5.4 and |V_N(y)|\le1 now complete the comparison on the major arcs as well. All thresholds used here are uniform under l\le N^\zeta and D\le N^\beta.□

Proof of Proposition 5.1. Extend J_1,J_2 by zero to \Z, and for either kernel define

Let \widetilde J_i(\alpha)=\sum_xJ_i(x)e(-x\alpha) denote the counting-measure Fourier transforms. Expanding the characters and integrating imposes n+x-y=0, so

Cauchy–Schwarz, Plancherel and Lemma 5.2 give

because the two counting-measure norms are at most \sqrt N.

Every term in \mathcal B_1 uses a positive shift F(m) with m\in\N_+, and hence vanishes by avoidance. Thus \mathcal B_1=0, regardless of the signed weights in (5.3). For a pair in the supports of J_1,J_2, ordering gives 1\le y-x\le N-1 and the residue conditions give y-x\equiv r\pmod D. Both indicators in k_0 are therefore automatic, and

This proves (5.2) with its stated normalization and signs.□

Proof. The frequencies contributing to \widehat g(\xi) have the form \xi+\omega, where \omega ranges over the characters on X_B that survive the cutoff. The denominators are coprime, so q(\xi+\omega)=q(\xi)q(\omega)\le q(\xi)q_B\le Q. Consequently every character on X_B occurs in the specialized coefficient, which equals

Character orthogonality makes the inner sum q_B when x\equiv b_p\pmod p for every p\in B, and zero otherwise. The Chinese remainder theorem now gives (6.2).□

Proof. We first record the scale inequalities. By (2.2), D\le L_D\le D^k, so L_D\ge M_0\ge2 and n_B<N for large N. The defining ceiling gives (6.4). Also

Here k\tau<1/2 and \tau<\beta/2 follow from (4.8).

By the signed Hölder inequality (4.1), it is enough to prove the asserted common bound for Z_{l,\mathcal S}(g), where g is any one of the specialized inputs. Let g_{\le H} retain exactly the remaining-coordinate frequencies of denominator at most H. We claim that

To see this, telescope the d slots and apply (4.4) to the high-frequency input in each term. The moment estimate (4.5) is applicable to all the other inputs as well as to that high-frequency piece. Indeed, before specialization, a cut on the remaining denominator retains entire supports C\subseteq\mathcal P_N according to the condition on q_{C\setminus B}; it never selects only part of the frequencies with a given full support C. Fixing B costs at most q_B^{1/2} in the distinguished L^2 norm and q_B^{1/[2(d-1)]} in each of the other d-1 norms. The total cost is therefore q_B. The original input is bounded by M_0, and N\ge10Q^6 for large N, so (4.5) supplies the remaining N^{o(1)} factor. Since

the claimed error is O(N^{-\sigma}). The denominator cuts are symmetric under negation, so the functions used here are real.

We next express g_{\le H} as an average of shorter lifts. Let a'\pmod D be the residue in Lemma 6.1. For each representative j\in[L_D] with j\equiv a'\pmod D, set

These progressions partition the integers of [N] in the class a'\pmod D: the first positive term is j, and n_B terms suffice for every such integer. Terms above N contribute no points to A'_j. Moreover, A'_j satisfies (6.1) with lD in place of l. For if a nonzero difference in A'_j-A'_j were h_{lD}(m) with m\ge1, the corresponding difference in A-A would be

by (2.2); its argument is positive and its value is nonzero.

Put \mathcal H_j=\mathcal L_{[n_B],\mathcal S,H}\1_{A'_j}. Every prime of L_D divides D, so L_D is invertible on X_{\mathcal S} and multiplication by L_D preserves denominators. Lemma 6.1, applied using q_BH\le Q, gives the exact identity

For completeness, the summand on the right has Fourier coefficient \widehat{\mathcal H_j}(L_D\xi)e(-c_j\xi) at \xi. Since \Lambda_B/(L_D/D)=Dn_B/N, summing these coefficients gives D/N times the sum over the required original integers, exactly as in (6.2); both sides have zero coefficients above H.

Under the map z\mapsto L_D^{-1}(z-c_j), the tuple law for l pushes forward to the tuple law for lD, by (3.5) at each remaining prime. There are exactly L_D/D representatives j. The seminorm triangle inequality applied to (6.5) therefore yields

This is where the exact change of tuple laws preserves the leading constant in the comparison.

It remains to replace the cutoff H on the shorter interval by its natural cutoff Q'. Equations (4.4) and (4.5), now on [n_B], bound the change of the diagonal by O(H^{-\gamma}N^{o(1)})=O(N^{-\sigma}). Their interval hypothesis holds because 6\beta<1, and hence n_B\ge10(Q')^6 for large N. The extended lift only uses primes in \mathcal P_{n_B}. It is obtained from \mathcal L_{[n_B],\mathcal P_{n_B},Q'}\1_{A'_j} by averaging the coordinates in B\cap\mathcal P_{n_B} and then viewing the result as independent of the additional coordinates in \mathcal S. The contraction under coordinate averaging from Lemma 4.2 gives

Combining these estimates with (6.4) proves the diagonal bound. Applying (4.1) to the mixed inputs proves (6.3): the product of dth roots of quantities bounded by the same nonnegative upper bound is at most that upper bound.□

Proof. At every prime-power factor of M_0, the construction in Section 2 supplies a length-L sequence of admissible residues whose sum is zero. The Chinese remainder theorem combines them into such a sequence modulo M_0. Fix one sequence. There are M_0 choices of the initial cycle residue; the other cycle residues are then determined, and the zero-sum condition closes the cycle. Its L vertices are distinct. The remaining d-L residues can be arbitrary, giving at least M_0^{d-L+1} good assignments out of M_0^d.□

Proof. We may replace each \mu_{l,p}-\eps_{l,p} by its normalized law \mu_{l,p}^{\circ}: passing back multiplies the integral by \prod_{p\in\mathcal P_N}(1-\eta_{l,p})\le1. We first locate an ordered pair of intervals along the cycle. We then truncate the other inputs and condition on their prime supports; the remaining pair integral will have exactly the multipliers appearing in Proposition 5.1.

Partition [N] into \lfloor N^\tau\rfloor consecutive intervals whose lengths differ by at most one. Each G_s is the average of the interval lifts \mathcal L_{I,\mathcal P_N,Q}f_s with weights |I|/N. Thus we may average independently over an interval assignment to every slot. These intervals have length \gg N^{1-\tau}, so the moment estimate (4.5) applies: indeed 6\beta+\tau<7\beta<1 by (4.8). For any interval assignment, ordinary Hölder, uniform single-slot marginals and (4.5) bound the integral in absolute value by N^{o(1)}. The probability that all L cycle slots choose the same interval is

Their contribution is O(N^{-\sigma}), since (L-1)\tau>\sigma=\gamma\tau/4.

In every other assignment, some directed cycle edge has its first interval I_1 strictly before its second interval I_2. Otherwise the interval indices would be nonincreasing all the way around the cycle, and therefore constant. Fix such an edge for the current assignment. The constants below are uniform in this choice.

Set T=N^\tau and truncate every interval lift except the two selected ones to denominators at most T. Telescoping the other slots, (4.4) and (4.5) give total error O(T^{-\gamma}N^{o(1)})=O(N^{-\sigma}), because \gamma\tau>\sigma. Expand the truncated inputs into characters. Each coefficient has modulus at most M_0, and there are at most T^2 rational frequencies of denominator at most T. Thus the sum of the absolute coefficients in the resulting expansion is O(T^{2(d-2)}).

Fix one term, let B be the union of the supports of its d-2 characters, and put

Condition on all tuple labels at every prime in B. The expanded characters become constants of modulus one. By independence between primes, the remaining tuple labels still have law \bigotimes_{p\in\mathcal S}\mu_{l,p}^{\circ}. Let g_1,g_2 denote the two selected interval lifts after specialization at this conditioning. They are functions on X_{\mathcal S}. For the chosen directed edge, let \Gamma be the increment multiplier defined in Section 5. The remaining pair integral is exactly

Indeed, simultaneous translation of the two labels kills all pairs of characters whose frequencies do not sum to zero. The surviving pair with frequencies -\xi,\xi has value e(\xi(z_2-z_1)), whose expectation is \Gamma(\xi).

For the terms with q(\xi)>H, (5.1) and Parseval give

The last inequality uses the interval moment bound and the cost R^{1/2} of each specialization in L^2.

We apply the kernel estimate to the remaining terms. Put D=M_0R. The parameter choice gives

for large N; the first inequality follows directly from \tau=\beta\gamma/[1000k(d+1)]. By Lemma 6.1, their Fourier coefficient formulas for q(\xi)\le H restrict the underlying integers to classes a'_1,a'_2\pmod D. The difference a'_2-a'_1 is admissible modulo M_0 by goodness. It is admissible at each prime in B because every conditioning of positive probability is in the cycle support of the nonexceptional law. It is therefore admissible modulo D.

The remaining frequencies of denominator at most H are precisely the set \Xi in Proposition 5.1. Indeed, their denominators are squarefree and coprime to D. Conversely, a squarefree denominator at most H and coprime to D has no prime below P, since all those primes divide M_0, and no prime in B; every prime divisor is at most H\le Q.

Define functions on [N] by

They are bounded by one and have ordered supports. Every difference from the first support to the second is positive, so a zero polynomial value cannot be such a difference; (6.1) excludes all nonzero values of h_l(\N_+). Thus all hypotheses of Proposition 5.1 hold at scale N. The Fourier normalizations in (6.2) are

Since (5.2) has a factor D outside its absolute value, the low-denominator part of (6.7) is at most

Both parts of (6.7) are consequently bounded, uniformly in the conditioning and in the term of the character expansion, by

Averaging the conditioning costs no factor, and summing the character expansion costs at most O(N^{2d\tau}). The final exponent satisfies

Thus the resulting error is O(N^{-\sigma}). The same-interval contribution and the truncation error already satisfy this bound. Finally, the interval assignments were averaged with probabilities summing to one, so the uniform estimate proves (6.6).□

Proof. Fix A\subseteq[N] satisfying (6.1). Use the functions f_s and their lifts G_s from Section 6, and, for a residue assignment \mathbf s=(s_v)_{v\in V}, write

Since \E_s f_s=\1_A, linearity of the lift and multilinearity of the integral give

where the residues s_v are independent and uniform modulo M_0.

For each B\subseteq\mathcal P_N, define the nonnegative measure

Its mass is \eta_{l,B}. Expanding the finite product gives the identity of signed measures

The complement of B therefore carries the full laws \mu_{l,p}, to which Proposition 6.2 applies. The functions \Phi_{\mathbf s} can have either sign; we will take the absolute value of each integral on the right of (7.3).

The exceptional masses have a uniform bound with an extra factor q_B:

Here we used \eta_{l,p}\le p^{-4} and the choice of P in (3.7). This bound first allows us to discard the terms with q_B>N^\tau.

To see this, suppose \eta_{l,B}>0. Simultaneous translation invariance of \eps_{l,p} implies that each single-label marginal of \eps_{l,p}/\eta_{l,p} is uniform on \F_p. The same holds for the full laws. Thus each single-slot marginal of \kappa_{l,B}/\eta_{l,B} is uniform on X_{\mathcal P_N}. Ordinary Hölder’s inequality and the moment estimate (4.5), at the fixed even exponent d, give

The constants are uniform in l,B,A and \mathbf s; the bound |f_s|\le M_0 only introduces a fixed factor. Terms of zero mass vanish. Combining (7.5) with (7.4) yields

where, for example, \epsilon=\tau/2 suffices because \sigma=\gamma\tau/4<\tau/2.

For q_B\le N^\tau and positive mass, condition instead on all the labels at primes in B. The laws at the remaining primes are unchanged, and the function in each slot is the corresponding specialization of G_{s_v}. Proposition 6.2, which allows arbitrary slotwise specializations, gives

The bound is uniform in every conditioned tuple, so integration over the prescribed labels preserves it. It also holds for zero-mass terms. By (6.4), \Lambda_B^d\le1+u_N; by (7.4), \sum_{B\ne\varnothing}\eta_{l,B}\le1/4. Therefore summing the errors in (7.6) still costs O(N^{-\sigma}).

For a good assignment \mathbf s, Proposition 6.4 bounds the integral against \bigotimes_p(\mu_{l,p}-\eps_{l,p}) by O(N^{-\sigma}) in absolute value. The expansion (7.3) and the two exceptional estimates consequently give

For every other assignment, apply Proposition 6.2 directly with B=\varnothing. The resulting bound is (1+u_N)\mathcal Y_{lM_0}(n_\varnothing)+O(N^{-\sigma}). Averaging these estimates in (7.2) gives the coefficients \rho_l and 1-\rho_l in (7.1). The bounds are uniform in A, so we may take the maximum defining \mathcal Y_l(N).

Finally, k\tau<1 by (4.8), so u_N\to0, and the bound 1\le n_B<N is part of Proposition 6.2.□

Proof. To select the exponents, suppose that at a scale where the recurrence applies the trial bound \mathcal Y_{lD_B}(n_B)\le C(lD_B)^b n_B^{-a} is available at every successor scale, with C\ge1 and a,b>0. Put s=ka+b. Since n_B\ge N/\lambda(D_B) and \lambda(D_B)\le D_B^k, each trial bound gives

If s\le1, then q_B^s\le q_B, so Equation (7.4) bounds the coefficient of C l^bN^{-a} inside the parentheses of (7.1) by

This upper bound tends to 1-3\rho_*/4<1 as s tends to zero. Two further restrictions handle the other parts of the argument. For any proposed a>0, Corollary 4.6 gives a bound \mathcal Y_l(N)\le C_aN^a for all positive l,N. Taking b=2a/\zeta makes l^bN^{-a}>N^a whenever l>N^\zeta, so this subpower bound covers the range outside the recurrence after increasing C. Finally, a<\sigma makes C_1N^{-\sigma}=o(N^{-a}), allowing the additive error to be absorbed at sufficiently large scales.

Choose explicitly

These numbers are positive because M_0\ge2 and 0<\rho_*\le1. They satisfy

Indeed, s_0=(k+2/\zeta)a_0\le1/2, and the third term in the minimum gives

This displays the asserted structural dependence. Under Condition (U), Sections 2 and 3 permit L,P,M_0,d to be fixed in terms of k only. Then \rho_*=M_0^{1-L} and all parameters in (4.8) depend only on k, so the displayed choices of a_0,b_0 do as well. The constants in the estimates below, and consequently C_0, may depend on the fixed data. All quantities in (7.8) are fixed from now on.

Corollary 4.6 supplies a constant C_*\ge1 such that

If l>N^\zeta, then

so (7.7) follows from (7.9) for any C_0\ge C_*. This establishes the estimate outside the range of the recurrence at every scale.

We choose the initial range before fixing C_0. Set \kappa=(1-\theta)/2>0, and take an integer N_*\ge N_1 so large that for every N\ge N_*,

This is possible because u_N\to0 and a_0<\sigma; the choice is independent of C_0. Now choose C_0\ge\max\{1,C_*N_*^{2a_0}\}. For all l\ge1 and N<N_*, (7.9) gives

Thus the initial range is covered simultaneously for every l.

Proceed by strong induction on N, simultaneously for all positive integers l. Suppose N\ge N_* and the estimate is known at every smaller scale. The case l>N^\zeta was established above, so assume l\le N^\zeta and apply Proposition 7.1. Its successor scales satisfy 1\le n_B<N, so the simultaneous induction hypothesis gives \mathcal Y_{lD_B}(n_B)\le C_0(lD_B)^{b_0}n_B^{-a_0} at every positive index lD_B, with no restriction on lD_B relative to n_B. The trial calculation above, with C=C_0, a=a_0, b=b_0, and s=s_0, therefore bounds the successor expression inside the parentheses of (7.1) by \theta C_0l^{b_0}N^{-a_0}. Substituting in (7.1), and then using (7.10), yields

The last step uses C_0l^{b_0}\ge1. This closes the induction.□

Proof of Theorem 1.1. Fix k\ge2. For this degree, fix the numerical choices furnished under Condition (U) by Sections 2, 3, and 4. In particular, L,P,M_0,d,\zeta,\sigma and \rho_*=M_0^{1-L} are now fixed using only k. Evaluate the explicit minimum above with these numbers to fix a_0, and put

The stated range for c_k follows from 0<a_0<\sigma<1 and d\ge1.

Now let h\in\Z[x] be an intersective polynomial of degree k with positive leading coefficient, and fix its chosen roots as in Section 2. Apply Lemma 2.1 to h. It supplies positive integers D_0,M, an integer r with -D_0<r\le0, and an intersective polynomial

of degree k with positive leading coefficient whose chosen roots satisfy Condition (U). Moreover,

Apply the preceding auxiliary family construction and estimates with g and its chosen roots as the fixed polynomial data, using the numerical choices already fixed for degree k. Proposition 7.2 then gives a constant C_0\ge1, which may depend on the fixed normalized polynomial, its chosen roots, and the fixed structural choices, for which (7.7) holds with the previously chosen a_0,b_0. At l=1 the auxiliary polynomial is g_1=g, since r_1=0 and \lambda(1)=1. Thus for every positive integer n and every B\subseteq[n] with (B-B)\cap g(\N_+)\subseteq\{0\}, Corollary 4.6 and Proposition 7.2, both applied to the framework for g, give

Now let N\ge M and let A\subseteq[N] satisfy the avoidance condition of the theorem. For each j\in[M], set

These sets give the progression coordinates of a partition of A. If a nonzero difference in A_j-A_j were g(m) for some m\in\N_+, the corresponding difference in A-A would be Mg(m)=h(r+D_0m), nonzero and with r+D_0m\ge1, contradicting avoidance. The bound just obtained therefore applies to each A_j. Since \lceil N/M\rceil\le2N/M for N\ge M and 1-c_k>0, it gives

Taking C_h=2^{1-c_k}M^{c_k}C_0^{1/d}\ge1 and N_h=M proves the theorem. The constants C_h,N_h may depend on every coefficient of h, while c_k depends only on k.□