Let h be an integer polynomial of degree k >= 2 with positive leading
coefficient. For N >= 1 and a set A contained in {1, ..., N}, say that
A avoids h at prime arguments when no difference a - a' of two distinct
elements of A equals h(p) for a prime p. Zero differences are always
present, so a prime root of h imposes no condition. The problem is to
bound |A| in terms of N.
A structural hypothesis is necessary. Take h(x) = x^2 + 1 and let A be
the multiples of 3 up to N. Differences of elements of A are multiples
of 3, while h(r) is congruent to 1 or 2 modulo 3 for every integer r,
so A avoids h at prime arguments with |A| asymptotic to N/3.
Definition. The polynomial h is prime-intersective if for every q >= 1
there is an integer r, coprime to q, with h(r) congruent to 0 modulo q.
Equivalently, h has a root in the p-adic units at every prime p:
solutions modulo prime powers form a finitely branching tree, and
compatible solutions define a unit z_p in Z_p with h(z_p) = 0.
Primality of the argument is precisely the unit condition: a prime
argument is not divisible by p unless it equals p, so a prime-supported
value congruent to 0 modulo a power of p has to come from a unit root.
The condition is strictly stronger than intersectivity, the existence
of a root modulo every q. The polynomial x(x - 1) is intersective,
since 0 and 1 are roots modulo every q, but modulo a prime p its only
roots are 0 and 1, neither coprime to p, so it is not
prime-intersective. The unit-root criterion for patterns at prime
arguments goes back to Kamae and Mendes France; Rice records Wierdl's
earlier qualitative form together with its history.
kamae-mendes-france-van-der-corput-difference-theorem.pdf
arxiv-1111.6559.pdf
https://arxiv.org/pdf/1111.6559
Theorem (power saving at prime arguments). Let h be prime-intersective
of degree k >= 2 with positive leading coefficient. There are
constants c_h > 0 and C_h >= 1, depending only on h, with
|A| <= C_h N^{1-c_h} for every N >= 1 and every A contained in
{1, ..., N} that avoids h at prime arguments.
Examples. For h(x) = (x - 1)^2 the choice r = 1 works for every q, so
h is prime-intersective. Its prime values are the squares (p - 1)^2,
so a set containing no nonzero square difference avoids h at prime
arguments, and the theorem supplies a power saving for such sets. The
prime-argument hypothesis forbids fewer differences than the
integer-argument one, so a bound of the same shape is a stronger
statement; the local unit-root condition is what makes it accessible.
For integer arguments the history is classical. Furstenberg's
correspondence principle recasts density questions as recurrence
statements, and Sarkozy proved that sets without square differences
have zero density. The first power saving for squares is due to
Pintz, Steiger and Szemeredi, whose double iteration was improved by
Bloom and Maynard; Rice gave the maximal extension of the best-known
bounds to general intersective polynomials, and Arala sharpened the
square case further. Green and Sawhney reached
N exp(-c sqrt(log N)) through an arithmetic level-d inequality, and
Adajar and coauthors obtained N exp(-c_{h,mu} (log N)^mu) for every
0 < mu < 1/2. All of these concern unrestricted integer arguments.
furstenberg-1977-ergodic-diagonal-measures.pdf
sarkozy-1978-difference-sets-i.pdf
pintz-steiger-szemeredi-1988.pdf
https://doi.org/10.1112/jlms/s2-37.2.219
arxiv-2011.13266.pdf
https://arxiv.org/pdf/2011.13266
arxiv-1612.01760.pdf
https://arxiv.org/pdf/1612.01760
arxiv-2303.03345.pdf
https://arxiv.org/pdf/2303.03345
green-sawhney-2025-arithmetic-level-d.pdf
adajar-et-al-2026-polynomial-differences.pdf
For prime arguments, Sarkozy treated the shifts p - 1 and p + 1.
After successive improvements by Lucier, Ruzsa and Sanders, and Wang,
Green proved a power saving for p - 1, noting that his argument also
applies to p + 1. His abstract reads, in ASCII:
"Suppose that A in {1, ..., N} has no two elements differing by
p - 1, p prime. Then |A| << N^{1-c}."
Thorner and Zaman made an admissible exponent explicit. For nonlinear
polynomials, Li and Pan proved a quantitative result when h(1) = 0,
and Rice's theorem covers every prime-intersective polynomial of
degree k >= 2, with |A| << N (log N)^{-c} for every c < 1/(2k - 2)
and a stronger bound for quadratics. The present result replaces
these subpolylogarithmic savings by a fixed power, for every
prime-intersective polynomial simultaneously.
sarkozy-1978-difference-sets-iii.pdf
lucier-2008.pdf
https://doi.org/10.1007/s10474-007-7107-1
ruzsa-sanders-2008.pdf
https://doi.org/10.4064/aa131-3-5
wang-2020.pdf
https://doi.org/10.1016/j.jnt.2019.10.009
arxiv-2206.08001.pdf
https://arxiv.org/pdf/2206.08001
thorner-zaman-2024.pdf
https://doi.org/10.1515/forum-2023-0091
li-pan-2009.pdf
https://doi.org/10.4064/aa138-1-2
arxiv-1111.6559.pdf
https://arxiv.org/pdf/1111.6559
For intersective polynomials in integer arguments, a fixed power
saving with an exponent depending only on the degree was obtained in
power-saving-intersective-polynomial-differences.pdf
and the descent recurrence and the reflection-positive tuple laws
developed below adapt that method. What the prime problem adds is a
local theory: a rescaled family of polynomials carrying the prime
argument through every change of progression, a cycle of admissible
local values at each prime power, and a signed kernel supported on
polynomial values at prime arguments.
The unit-root hypothesis enters at exactly three points. First, the
p-adic root supplies the rescaling shift that keeps the argument
prime under restriction to progressions. Second, admissible residues
and their zero-sum cycles must exist at every prime power, uniformly
in the auxiliary index. Third, the local weights that realize the
Fourier multipliers must have unit means, which requires the regular
argument classes and their uniform lifting to higher prime powers.
Without a unit root at some modulus, each of these fails and the
argument gives no control.
Conventions. Write e(x) = exp(2 pi i x). For a rational xi, q(xi) is
its denominator in lowest terms, with q(0) = 1. A quantity is
N^{o(1)} if it is O_eps(N^eps) for every eps > 0. Constants and
thresholds depend only on h and on structural parameters derived from
it; they are uniform in the auxiliary index l introduced below.
The argument proceeds in five stages. Local structure is settled by
the p-adic root, a rescaled polynomial family, admissible residues,
and a zero-sum cycle of fixed length. Reflection-positive probability
laws on residue labels then carry those cycles, together with a small
exceptional part and a conditional mixing estimate. Fourier lifts of
interval indicators turn mixing into decay for large denominators,
and reflection positivity into a signed Holder inequality and a
seminorm. Two analytic inputs over primes, an asymptotic formula in
progressions and cancellation in polynomial exponential sums,
produce a signed kernel matched to the model kernel of admissible
differences. A descent recurrence on shorter intervals contracts
and yields the saving.
frohlich-israel-lieb-simon-1978.pdf
https://doi.org/10.1007/BF01940327
arxiv-1611.05784.pdf
https://arxiv.org/pdf/1611.05784
arxiv-0806.0047.pdf
https://arxiv.org/pdf/0806.0047
quasi-riemann-hypothesis-zero-free-half-plane.pdf
weyl-1916-gleichverteilung.pdf
https://doi.org/10.1007/BF01475864
vaughan-1980-elementary-method.pdf
https://doi.org/10.4064/aa-37-1-111-115
The first obstruction is that restricting a set to a residue class
changes the polynomial that expresses the forbidden differences. The
cure is to use progression steps that are powers of a fixed
completely multiplicative function, chosen so that the transformed
polynomials remain in one auxiliary family. Admissible local values
at prime powers then supply the increments carried by the tuple laws
below. The unit-root hypothesis is what makes both steps possible.
The p-adic root and the rescaled polynomial family. By
prime-intersectivity, for each prime p and each j >= 1 the
congruence h(x) congruent to 0 modulo p^j has a solution coprime to
p. Compatible choices under reduction form a finitely branching
tree, so there is a unit z_p in Z_p with h(z_p) = 0. Expanding at
that root,
h(z_p + X) = sum_{j = m_p}^{k} b_{j,p} X^j,
with b_{j,p} in Z_p, b_{m_p,p} != 0, and 1 <= m_p <= k. Let lambda
be the completely multiplicative function with lambda(p) = p^{m_p}.
For l >= 1 let r_l be the unique integer in (-l, 0] congruent to z_p
modulo p^{v_p(l)} for every prime p dividing l, where v_p is the
p-adic valuation; the Chinese remainder theorem provides r_l, and
(r_l, l) = 1. Put r_1 = 0, and define
T_l(x) = r_l + l x, h_l(x) = h(T_l(x)) / lambda(l),
a_l = a l^k / lambda(l).
Auxiliary-family lemma.
(a) h_l lies in Z[x], has degree k, leading coefficient a_l > 0, and
coefficients O_h(a_l).
(b) h_1 = h and T_1(x) = x.
(c) For every D >= 1 there is an integer i with 0 <= i < D and
T_l(D x - i) = T_{lD}(x), h_l(D x - i) = lambda(D) h_{lD}(x),
and moreover D divides lambda(D) and lambda(D) <= D^k.
(d) b_{m_p,p} is a unit of Z_p for every p >= P_unit, a threshold
depending only on h.
Proof. (a) Fix a prime p. If p divides l, put u = v_p(l) and change
variables by Y = (r_l - z_p)/p^u + (l/p^u) x, whose coefficients lie
in Z_p and whose slope is a unit. Substituting into the expansion at
z_p gives
h_l(x) = [lambda(l) / p^{u m_p}]^{-1}
sum_j b_{j,p} p^{u(j - m_p)} Y^j,
and every term lies in Z_p because b_{j,p} does. If p does not
divide l then lambda(l) is a p-adic unit and integrality is
automatic. So h_l is integral at every prime and therefore lies in
Z[x]. Its leading coefficient is a_l > 0. Each coefficient of
h(r_l + l x) is at most C_h a l^k in absolute value because
|r_l| < l, and division by lambda(l) produces a bound
C_h a l^k / lambda(l) = C_h a_l.
(b) Immediate from r_1 = 0.
(c) For every prime p dividing l the integers r_{lD} and r_l are
both congruent to z_p modulo p^{v_p(l)}, hence modulo l. Both lie in
(-lD, 0], so r_{lD} = r_l - i l for an integer i in (-1, D), that
is, 0 <= i < D. Then
T_{lD}(x) = r_{lD} + lD x = r_l + l(D x - i) = T_l(D x - i),
and dividing h(T_{lD}(x)) by lambda(lD) = lambda(l) lambda(D) gives
the second identity. The divisibility D | lambda(D) and the bound
lambda(D) <= D^k follow from 1 <= m_p <= k.
(d) Factor h = c prod_i g_i^{d_i} over Z[x], with c a nonzero integer
and the g_i distinct primitive irreducible nonconstant polynomials.
Discard the finitely many primes dividing c or dividing one of the
nonzero integer right sides of cleared Bezout identities for the
pairs (g_i, g_j) with i != j and for the pairs (g_i, g_i'). At any
remaining prime p the root z_p is a zero of exactly one factor g_i,
the derivative g_i'(z_p) is a unit, and every other g_j(z_p) is a
unit. Hence m_p = d_i and the coefficient of X^{m_p} is, up to a
p-adic unit, c g_i'(z_p)^{d_i} prod_{j != i} g_j(z_p)^{d_j}, itself
a unit. QED
Forbidden values and avoidance. The forbidden set at parameter l is
D_l = { h_l(m) : m in Z, m >= 1, T_l(m) prime }.
A set A contained in [N] avoids at l if (A - A) intersect D_l is
contained in {0}. Since h_1 = h and T_1(m) = m, avoidance at l = 1
is exactly the hypothesis of the main theorem.
Transport lemma. For l, D, n >= 1 and any integer c, the set
A' = { x in [n] : lambda(D) x + c is in A } avoids at lD whenever A
avoids at l.
Proof. Suppose x_1 - x_2 = h_{lD}(m') with x_i in A', m' >= 1, and
T_{lD}(m') prime; the difference is nonzero. Put a_i = lambda(D) x_i
+ c, so that a_i are in A. By the auxiliary-family lemma there is an
integer i with 0 <= i < D and
a_1 - a_2 = lambda(D) h_{lD}(m') = h_l(D m' - i).
Also D m' - i >= D - (D - 1) = 1 and T_l(D m' - i) = T_{lD}(m') is
prime, so h_l(D m' - i) belongs to D_l. Since lambda(D) > 0 and
h_{lD}(m') != 0, this is a nonzero difference of two elements of A,
contradicting avoidance at l. QED
Local sums. Fix
delta = 1/(100 k 2^k), gamma = delta/10.
A class x modulo p is allowed regular if p does not divide T_l(x) and
F'(x) is not congruent to 0 modulo p, where F is h_l reduced modulo
p.
Local-sums lemma. There is P_1 > max(k, 2), depending only on h,
such that for every l >= 1 and every prime p >= P_1 at least p/2
classes modulo p are allowed regular, and for every integer v
coprime to p,
|E_{x mod p^j, p not dividing T_l(x)} e(v h_l(x)/p^j)|
<= p^{-8 delta j} (j >= 1),
|E_{x mod p, x allowed regular} e(v h_l(x)/p)|
<= p^{-4 delta}.
Proof. Take the threshold large enough that h_l modulo p is
nonconstant of positive degree and its derivative is not identically
zero. Nonconstancy is uniform in l: if p does not divide l it follows
from p not dividing the leading coefficient a, and if p divides l it
reduces to a unit multiple of Y^{m_p}. The derivative vanishes on at
most k - 1 classes, so at most k classes fail to be allowed regular,
which gives the count p/2.
Modulo p, let k' be the degree of F. The complete mean
S = E_{x mod p} e(v F(x)/p) vanishes when k' = 1. When k' >= 2, Weyl
differencing squares k' - 1 times and groups by the increments; the
final inner sum over x equals 1 unless
v k'! (leading coefficient of F) u_1 ... u_{k'-1}
is divisible by p, that is, unless some increment u_i vanishes. That
event has probability at most (k' - 1)/p, so |S|^{2^{k'-1}} <=
(k' - 1)/p. Restricting to allowed-regular classes changes the mean
by at most k/p, so for p >= P_1,
|E_{allowed} e(v F(x)/p)|
<= (k' - 1)^{2^{-(k'-1)}} p^{-2^{-(k'-1)}} + O_k(p^{-1})
<= p^{-4 delta},
the last step because 8 delta < 2^{-(k-1)} for the chosen delta.
For j >= 2 put n = floor(j/2) 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 F(x) congruent to F(x_0) + p^{j-n} y F'(x_0) modulo p^j, and
the unit condition depends only on x_0. Averaging over y kills every
term with p^n not dividing F'(x_0), so only classes x_0 with
p^n | F'(x_0) survive.
Count surviving x_0 by interpolation. Put b = ceil(n/(k-1)). The
solutions of F'(x_0) congruent to 0 modulo p^n occupy at most k - 1
classes modulo p^b: given k distinct classes carrying solutions
x_1, ..., x_k, Lagrange interpolation of the polynomial F' of degree
at most k - 1 gives
F'(x) = sum_i F'(x_i) prod_{s != i} (x - x_s)/(x_i - x_s).
Each denominator has p-adic valuation at most (k-1)(b-1) < n, each
numerator is divisible by p^n, so every coefficient of F' would be
divisible by p, contradicting F' not identically zero modulo p.
Since b <= n <= j - n, the count applies to the full range of x_0
modulo p^{j-n}, and the unit condition retains at least half of the
classes. The surviving proportion is therefore at most
2(k-1) p^{-b} <= 2(k-1) p^{-j/(3(k-1))}. One more increase of P_1,
using 8 delta < 1/(3(k-1)), gives the bound p^{-8 delta j}. QED
Lifting lemma. For every prime p < P_1 there is an integer
S_p >= 0, depending only on h and p, such that for every l >= 1
some integer x satisfies p not dividing T_l(x) and
v_p(h_l'(x)) <= S_p. Set E_p = 2S_p + 1 for p < P_1 and E_p = 1
otherwise. Let p be a prime and let x satisfy the condition just
described when p < P_1, or be allowed regular when p >= P_1, and put
s = v_p(h_l'(x)). Then:
(i) every integer y congruent to x modulo p^{E_p - s} satisfies
p not dividing T_l(y), and h_l(y) is congruent to h_l(x) modulo
p^{E_p};
(ii) for every j > E_p, the uniform distribution on the class of x
modulo p^j pushes forward under h_l to the uniform distribution on
the classes congruent to h_l(x) modulo p^{E_p}.
Proof. Small primes. 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, since the
substitution and its inverse have the same form. The p-adic form of
h_l is obtained from h by a substitution of that type when p divides
l, and is plainly integral when p does not divide l, so the minimum
is bounded uniformly in l by a constant depending only on h and p.
Differentiation raises it by at most max_{1 <= j <= k} v_p(j), so the
minimum valuation of the nonconstant coefficients of F' is at most
C_p, independently of l.
Choose k distinct integers x_1, ..., x_k with p not dividing T_l and
interpolate F', a polynomial of degree at most k - 1. The p-adic
valuations of the denominators in the interpolation formula are
bounded by some B_p independent of l. If every F'(x_r) had valuation
larger than C_p + B_p, every coefficient of F' would have valuation
larger than C_p, contradicting the definition of C_p. Hence
S_p = C_p + B_p serves for every l.
Both ranges. Taylor expansion gives
F(x + p^{E_p - s} y) = F(x) + p^{E_p} (c_1 y + p C(y))
with c_1 = p^{-s} F'(x) coprime to p and C(y) in Z[y], because each
term of degree d >= 2 gains a factor p^{E_p - 2s} >= 1. For the
polynomial G(y) = c_1 y + p C(y) and distinct integers y, z,
(G(y) - G(z))/(y - z) = c_1 + p (C(y) - C(z))/(y - z)
is coprime to p, so v_p(G(y) - G(z)) = v_p(y - z), and G is a
bijection of every finite ring Z/p^m.
(i) Write y = x + p^{E_p - s} z. The expansion gives h_l(y)
congruent to h_l(x) modulo p^{E_p}, and T_l(y) is congruent to
T_l(x) modulo p because E_p - s >= 1, so p does not divide T_l(y).
(ii) A uniform y modulo p^{j - E_p + s} corresponds to a uniform z
modulo p^{j - E_p}, each z occurring p^s times. The map G is a
permutation modulo p^{j - E_p}, and pushing forward gives uniformity
on the stated residue class modulo p^j. QED
Admissible residues. A class y modulo p^{E_p} is admissible at l if
y is congruent to h_l(x) modulo p^{E_p} for some integer x as in the
lifting lemma. For a modulus that is a product of distinct factors
p^{E_p}, a class is admissible when it is admissible at every
factor.
Cycle lemma. Choose an integer L > 2 with
4 delta L > 2 and p^{E_p} divides L for every p < P_1.
Then for every l >= 1 and every prime p there are L admissible
classes y_0, ..., y_{L-1} modulo p^{E_p}, repetitions allowed, whose
sum is congruent to 0 modulo p^{E_p}.
Proof. For p < P_1 take one admissible class, which exists by the
lifting lemma, and repeat it L times; the sum is L y_0 = 0 because
p^{E_p} divides L. For p >= P_1 take L independent uniform
allowed-regular arguments x_0, ..., x_{L-1} in F_p. Character
orthogonality and the local-sums lemma with the single frequency v
give
|p P(F(x_0) + ... + F(x_{L-1}) = 0 mod p) - 1|
<= (p - 1) p^{-4 delta L} < 1,
because 4 delta L > 2 and p >= P_1 is large. The probability is
positive, so some choice of the x_j sums to 0. QED
The cycle is fixed once and for all. Given y_0, ..., y_{L-1} as in
the cycle lemma, set z_0 = 0 and z_j = y_0 + ... + y_{j-1} for
1 <= j <= L. Then z_L = z_0 and every increment z_{j+1} - z_j = y_j
is admissible. For a cutoff P > P_1 the same sequence propagates by
the Chinese remainder theorem: cycles are combined prime by prime
over the primes below P, and the sum remains 0 modulo the product of
the p^{E_p}. The designated cycle of the tuple laws below uses
exactly these increments.
Reflection-positive tuple laws. Fix a prime p and an auxiliary index
l. The goal is a probability law on labels z_v in F_p, one for each
slot v of a large finite set V, with four properties: reflection
positivity at every reflection cut; an exceptional submeasure of
small mass, off which the increments along a designated cycle are
admissible; translation invariance together with covariance under
the affine maps of the auxiliary family; and a conditional mixing
bound. Reflection positivity yields the signed Holder inequality and
the seminorm used for the lifts. Mixing makes large Fourier
denominators decay. The construction adapts the reflection-positive
tuple laws of
power-saving-intersective-polynomial-differences.pdf
with the additional requirement that the designated cycle carry
admissible values at prime arguments. The positivity argument is the
chessboard method of Frohlich, Israel, Lieb and Simon. Reflection
arguments for graph norms appear in Conlon and Lee, and the passage
from a multilinear Holder inequality to a seminorm is part of
Hatami's criterion for graph norms.
frohlich-israel-lieb-simon-1978.pdf
https://doi.org/10.1007/BF01940327
arxiv-1611.05784.pdf
https://arxiv.org/pdf/1611.05784
arxiv-0806.0047.pdf
https://arxiv.org/pdf/0806.0047
Slots and cuts. Choose an integer t >= 1 with (t+1) delta/2 > 5 and
set
w = 2 t + 1, K = L!, r_* = K/2.
A word is a bijection from the positions [L] onto the symbols [L],
and Pi denotes the set of words. The slots are
V = Pi^w, d = |V| = K^w,
and the entries of a slot are its blocks. Fix an L-cycle c on [L];
composing a word on the right by c permutes its positions. Writing
c^j for the corresponding word, fix the designated cycle slots
v_j = (c^j, ..., c^j), 0 <= j < L, v_L = v_0.
A cut is a block b in [w] together with an ordered pair of distinct
symbols alpha, beta in [L]. Its plus side is the set of slots in
whose b-th word alpha precedes beta, and theta is the involution
that exchanges alpha and beta in block b and fixes every other
block. Thus theta pairs the plus side with its complement, and each
of the two halves has d/2 slots.
A measure nu on F_p^V is reflection positive when, for every cut and
every real function J on F_p^{V_+},
int J((z_v)_{v in V_+}) J((z_{theta v})_{v in V_+}) dnu(z) >= 0.
Tuple-laws proposition. There is a threshold P > P_1, depending
only on h, with the following property. For every l >= 1 and every
prime p >= P there are a probability measure mu_{l,p} on F_p^V and
a submeasure 0 <= eps_{l,p} <= mu_{l,p} such that:
(1) mu_{l,p} is reflection positive, and mu_{l,p} and eps_{l,p} are
both invariant under simultaneous translations z_v -> z_v + a. Any
nonzero one of mu_{l,p}, eps_{l,p}, mu_{l,p} - eps_{l,p} has uniform
one-slot marginals after normalization.
(2) With eta_{l,p} = eps_{l,p}(1) and
mu_{l,p}^circ = (mu_{l,p} - eps_{l,p}) / (1 - eta_{l,p}),
the exceptional mass satisfies eta_{l,p} <= p^{-4}, and under
mu_{l,p}^circ every cycle increment z_{v_{j+1}} - z_{v_j} with
0 <= j < L is admissible at l.
(3) For every D >= 1 coprime to p and every a' in F_p the map
A_{D,a'}(z)_v = lambda(D)^{-1} (z_v - a')
sends mu_{l,p} to mu_{lD} and eps_{l,p} to eps_{lD}.
(4) For rho_p equal to mu_{l,p} or mu_{l,p}^circ, for every v in V,
and every f : F_p -> C of uniform mean zero,
|| E_{rho_p}[f(z_v) | (z_u)_{u != v}] ||_{L^2(rho_p)}
<= p^{-gamma} ||f||_{L^2(F_p)}.
Every threshold and constant is independent of l.
Strategy of proof. The simplest candidate is independent uniform
labels weighted by the cycle increments alone. It has the cycle
property, and conditional mixing follows from the local Fourier
bounds, but it is not reflection positive: a cut sees weights whose
signs can be negative.
Marked, or forgotten, blocks repair this. Marking a block forgets
its word, so slots agreeing in every other block share a list of
labels, and the cut matrix at a marked block is diagonal. A positive
interaction between selection indices makes a marked cut control the
mean square of its test function from below by an amount that
dominates the possible negative contribution of the matching cut at
an unmarked block. The components in which all t+1 blocks are marked
carry no cycle constraint; they form the exceptional submeasure.
Edge weights. Fix l and a prime p >= P_1, and write F = h_l. For y
in F_p put
W(y) = (1/k) #{ x in F_p : F(x) = y, x allowed regular }.
Then 0 <= W <= 1, and c_p = E_y W(y) is at least 1/(2k), since at
least p/2 classes are allowed regular. For nonzero a the Fourier
coefficient
W_hat(a) = (1/(k p)) sum_{x allowed regular} e(-a F(x)/p)
has modulus at most p^{-4 delta} by the local-sums lemma.
Graph lemma. Let G be a finite directed graph with no loops and at
most one edge on each unordered pair of vertices. Give its vertices
independent uniform labels Y_x in F_p and put
I_G(Y) = prod_{x -> y in E(G)} W(Y_y - Y_x),
with e_G edges.
(i) E I_G = c_p^{e_G} + O_G(p^{-4 delta}).
(ii) If the vertices split into two classes A and B and every edge
joins A to B, then the kernel D = I_G - c_p^{e_G}, regarded as an
operator between the uniform L^2 spaces on the two label families,
has norm O_G(p^{-delta}).
Both bounds are uniform in l.
Proof. (i) The convolution kernel (y, x) -> W(y - x) - c_p has L^2
operator norm at most p^{-4 delta}, since its Fourier coefficients at
nonzero frequencies are bounded by p^{-4 delta}. Replace the factors
of I_G by c_p one edge at a time. In a correction term, hold every
label fixed except those at the endpoints x, y of the replaced edge;
the graph has no loops and at most one edge on each unordered pair,
so the remaining weight factors as a(Y_x) b(Y_y) with |a|, |b| <= 1.
The operator bound controls the conditional expectation, and summing
over the e_G edges gives (i).
(ii) In uniform L^2 spaces the fourth Schatten moment of the kernel
for the partition A, B is
E D(a, b) D(a', b) D(a', b') D(a, b'),
the expectation over independent a, a' in A and b, b' in B, with
D applied to the corresponding label differences. Expanding
D = I_G - c_p^{e_G} produces products of selected copies of I_G over
an extended vertex set carrying two copies of A and two of B. The
counting graph of each summand is loop-free and has at most one edge
on each unordered pair, so (i) expresses its expectation as
c_p^{number of edges} plus O_G(p^{-4 delta}). Replacing every edge
weight by c_p annihilates the full expanded sum, by the binomial
identity for the fourth power of I_G - c_p^{e_G} summed over the
selectors. The fourth moment is therefore O_G(p^{-4 delta}), and the
operator norm is at most its fourth root, namely O_G(p^{-delta}).
QED
Components. For S contained in [w] with |S| = s <= t + 1, the blocks
in S are marked. The address of a slot v is the tuple u_S(v) of its
words in the unmarked blocks, and the address set is
U_S = Pi^{[w] \ S}. At each address u place a list
(Y_{u,1}, ..., Y_{u,ell_s}), ell_s = r_*^s,
of independent uniform labels in F_p, independently across addresses.
A slot of address u will select one label from its list.
For s <= t declare a directed edge u -> u' between addresses when
u'_b = u_b c in at least t + 1 unmarked blocks b.
Every entry of the first list is joined to every entry of the second,
with the weight
I_S(Y) = prod_{u -> u'} prod_{i, i' in [ell_s]}
W(Y_{u',i'} - Y_{u,i}).
For s = t + 1 set I_S = 1; those components carry no cycle
constraint.
There are no loops, since c is not the identity. There are no
opposite edges either: c^2 is not the identity, so the witnessing
blocks for u -> u' and for u' -> u would be disjoint and there would
be at least 2t + 2 > w of them. Hence the graph on individual list
entries satisfies the graph lemma.
Index weights and components. Select indices j_v uniformly in
[ell_s], independently over slots, and put Delta = 1/(10 L^2). For
distinct slots x, y in V set H^S_{xy} = Delta^g when x and y agree
in every block except one marked block, and in that block their
words differ by exchanging two symbols at positions of distance g.
Set H^S_{xy} = 0 in every other case, and H^S_{xx} = 0. Define
R_S(j) = exp( sum_{x < y} H^S_{xy} 1_{j_x = j_y} ),
nu_S(Phi) = E_{Y,j} I_S(Y) R_S(j)
Phi((Y_{u_S(v), j_v})_{v in V}),
the sum running over unordered pairs of distinct slots.
Each nu_S is a finite nonnegative measure. Its mass lies between
fixed positive constants depending only on the slot system: the
graph lemma bounds E I_S from below by c_p^{e_S} - O_S(p^{-4 delta}),
which is positive for large p since c_p >= 1/(2k), while R_S lies
between 1 and a constant depending only on the slot system.
Reflection invariance. Every component is invariant under every
reflection theta. Exchanging two symbols in one block preserves all
transposition distances appearing in H^S. In an unmarked block the
exchange permutes addresses and preserves the edge rule, because
symbol permutations commute with the right action of c on positions;
in a marked block the addresses do not change at all. The uniform
lists and indices are preserved in either case. Hence every cut
matrix of nu_S is symmetric. Positivity is the substantive point.
The three quadratic-form comparisons. Fix a cut in block b and, for
a real function J of the plus labels, write
Q_S(J) = int J((z_v)_{v in V_+}) J((z_{theta v})_{v in V_+})
dnu_S(z).
Marked cut. Suppose b is in S, so the cut sits at a marked block.
Let A_{xy} = H^S_{x, theta y} for x, y in V_+, the matrix of
interactions across the cut. It is symmetric. If the two cut symbols
of a slot x occupy positions at distance g in block b, then
A_{xx} = Delta^g. Every other transposition taking x across the cut
must move one cut symbol past the other while fixing it, hence
exchanges positions at distance at least g+1, and only a
transposition in block b can do this. Fewer than L^2 such
transpositions exist, so
sum_{y != x} |A_{xy}| <= L^2 Delta^{g+1} = Delta^g / 10.
With Delta = 1/(10 L^2) this makes A diagonally dominant:
A >= kappa Id in the positive semidefinite order,
kappa = (9/10) Delta^{L-1} > 0,
the worst case being g = L - 1.
Positivity of the interaction matrix yields strict positivity of the
whole index kernel as follows. Identify minus indices with plus
indices through theta, let j, j' be two half-index assignments, and
put u(j) = (1_{j_x = i}), a matrix indexed by x in V_+ and i in
[ell_s]. The cross factor of R_S is the matrix
C(j, j') = exp( u(j)^T (A (x) Id) u(j') ).
Split A = kappa Id plus a positive semidefinite matrix. The entrywise
exponential of a positive semidefinite Gram matrix is positive
semidefinite: expand the power series and apply the Schur product
theorem to each power. The factor coming from A - kappa Id is
therefore positive semidefinite with diagonal entries at least one.
The factor coming from kappa Id is the tensor product over x in V_+
of 11^T + (e^kappa - 1) Id, which dominates (e^kappa - 1)^{d/2} Id.
Schur multiplication with the other factor preserves this lower
bound, because Schur multiplication by the identity returns the
diagonal. The internal interactions in the two halves multiply the
matrix on the left and on the right by the same diagonal matrix with
entries at least one, so the bound survives.
When b is in S, reflected slots have the same address, and for fixed
lists Y the two factors involving J evaluate the same vector over
half-index assignments, of which there are n_s = ell_s^{d/2}. The
uniform average over the two halves is n_s^{-2} times the associated
quadratic form, whose diagonal lower bound is therefore
(e^kappa - 1)^{d/2} n_s^{-1} times the uniform average of squares.
There are finitely many possible s, so there is a fixed c_* > 0 with
Q_S(J) >= c_* E_{Y, j_+} I_S(Y)
J((Y_{u_S(v), j_v})_{v in V_+})^2
whenever b is in S.
Unmarked cut. Suppose b is not in S. The lists split into plus and
minus addresses according to the order of the cut symbols in block
b. Write Y_+ for the plus lists and I_+ for the product of those
factors of I_S whose edges have both ends on the plus side, and put
A_S(J) = E_{Y_+, j_+} I_+(Y_+)
J((Y_{u_S(v), j_v})_{v in V_+})^2.
No index interaction crosses this cut, since changing a marked block
does not change the word in block b. After averaging the indices,
Q_S(J) is the quadratic form of the cross-list edge kernel applied to
the half-function
B(Y_+) = I_+(Y_+) E_{j_+} R_+(j_+)
J((Y_{u_S(v), j_v})_{v in V_+}),
where R_+ is the internal index weight on the plus side. Since
R_+ <= C and I_+^2 <= I_+, Cauchy-Schwarz gives
||B||_2^2 <= C A_S(J). The graph lemma replaces the cross kernel by
its nonnegative constant value c_p^{cross edges}, with operator
error O(p^{-delta}), and the constant kernel contributes a
nonnegative multiple of (E B)^2. Hence
Q_S(J) >= -C p^{-delta} A_S(J)
whenever b is not in S. When s = t + 1 no index interaction crosses
the cut at all, the cross kernel equals 1 exactly, and Q_S(J) >= 0.
Concatenation. Let b be outside S with s <= t and put
S' = S union {b}. Then
Q_{S'}(J) >= c_* r_*^{-d/2} A_S(J).
Indeed the new address forgets block b, and exactly r_* = K/2 old
plus addresses become each new address, one for every word in which
alpha precedes beta. Enumerate those words as sigma_1, ...,
sigma_{r_*} and write the old addresses above a new address u as
(u, sigma_a). Concatenate the old lists by
Ytilde_{u, (a-1) ell_s + i} = Y_{(u, sigma_a), i},
for a in [r_*] and i in [ell_s]. These are independent uniform lists
of length r_* ell_s = ell_{s+1}, exactly as the component nu_{S'}
requires.
Under this identification I_{S'} >= I_+ pointwise. Any edge between
new addresses is witnessed in at least t+1 blocks other than b, so
every pair of their constituent old plus addresses already carried
that directed edge; every factor of I_{S'} thus occurs in I_+, which
carries additional factors in [0,1]. When |S'| = t+1 the inequality
follows from I_{S'} = 1.
In the nonnegative right side of the marked-cut bound applied to S',
let j'_v be the new indices. For a plus slot of old address
(u, sigma_a), restricting j'_v to {(a-1) ell_s + 1, ..., a ell_s}
has probability 1/r_*, independently over the d/2 plus slots, and
conditionally the selected labels have exactly their old law. With
I_{S'} >= I_+ this proves the concatenation bound.
The mixture. Define
M = sum_{|S| <= t+1} p^{-|S| delta/2} nu_S,
mu_{l,p} = M / M(1).
Reflection positivity: fix a cut in block b and pair each S that
misses b and has |S| <= t with S' = S union {b}. By the unmarked-cut
and concatenation bounds the combined quadratic form is at least
p^{-s delta/2}
( c_* r_*^{-d/2} p^{-delta/2} - C p^{-delta} ) A_S(J) >= 0
for large p, since r_* and c_* are fixed. Every component containing
b is used in exactly one pair, and the remaining components have
|S| = t+1, b not in S, and nonnegative quadratic forms by the last
remark of the unmarked-cut discussion. Hence M is reflection
positive, and so is mu_{l,p}.
Mass bounds. For S empty every list has length one, every index
weight is one, and the component mass is a graph average; the graph
lemma and c_p >= 1/(2k) give nu_empty(1) >= c_0 > 0 for large p,
uniformly in l. The masses of all components being bounded above and
below, the total satisfies
0 < c_0 <= M(1) <= C_0.
The exceptional submeasure is
eps_{l,p} = ( p^{-(t+1) delta/2} / M(1) ) sum_{|S| = t+1} nu_S,
whose mass is at most C p^{-(t+1) delta/2} <= p^{-4} after one more
increase of the prime threshold, by the choice of t.
Cycle property. Suppose |S| <= t. At least t+1 blocks are then
unmarked, and the addresses of v_j and v_{j+1} satisfy the edge rule
in every one of them. The product I_S therefore contains the factor
W( Y_{u_S(v_{j+1}), j_{v_{j+1}}} - Y_{u_S(v_j), j_{v_j}} ).
Wherever the density of nu_S is positive this factor is nonzero, so
the difference of the two selected labels equals F(x) = h_l(x) for
an allowed-regular class x, which is admissible modulo p by
definition. Hence under mu_{l,p}^circ every cycle increment
z_{v_{j+1}} - z_{v_j} is admissible at l, which is property (2).
Translation invariance. Translating every list entry by the same
element of F_p leaves all differences Y_{u',i'} - Y_{u,i} unchanged,
so every component is translation invariant, and so are mu_{l,p}
and eps_{l,p}. Since translation acts transitively on F_p, every
nonzero one of the three measures has uniform one-slot marginals
after normalization, which is property (1).
Covariance. If p does not divide D, the auxiliary-family lemma gives
W_{lD,p}(y) = W_{l,p}(lambda(D) y).
The substitution x -> D x - i is a bijection modulo p, it carries
T_l(D x - i) = T_{lD}(x), and it preserves nonvanishing of the
derivative because D and lambda(D) are units modulo p. Changing every
list entry to lambda(D)^{-1}(Y_{u,i} - a') therefore transforms each
component for l into the corresponding component for lD, preserving
its mass and all index weights. The mixtures and their exceptional
parts inherit the transformation, which is property (3).
Conditional mixing. Consider first the normalized leading component
nu_empty / nu_empty(1). At a fixed slot v write x = z_v and
y = (z_u)_{u != v}. Its density relative to independent uniform
labels factors as J_1(x, y) J_2(y), where J_1 is the product of the m
edge weights incident with v and J_2 collects all remaining edges.
Put
A(y) = E_x J_1(x, y), B(y) = E_x f(x) J_1(x, y).
The graph lemma applied to the graph of incident edges with
partition {{v}, V \ {v}} gives, since f has mean zero,
||A - c_p^m||_2 <= C p^{-delta},
||B||_2 <= C p^{-delta} ||f||_2.
The conditional expectation at y equals B(y)/A(y) when A(y) > 0,
and the marginal density of y is J_2(y) A(y)/nu_empty(1). The
squared conditional norm is therefore
(1/nu_empty(1)) E_y J_2(y) |B(y)|^2 / A(y),
with the ratio read as zero when A = 0. On the set where
A >= c_p^m / 2 the bound follows from ||B||_2^2 together with the
lower bound on A. The complementary set has probability
O(p^{-2 delta}) by the estimate on A, since c_p^m is bounded below,
and on it weighted Cauchy-Schwarz together with J_1 <= 1 gives
|B(y)|^2 / A(y) <= E_x |f(x)|^2 J_1(x, y) <= ||f||_2^2.
With J_2 <= 1 and the lower bound on nu_empty(1), the squared
conditional norm is O(p^{-2 delta}) ||f||_2^2.
Both mu_{l,p} and mu_{l,p}^circ are mixtures of the normalized
components, and in either mixture the total probability of S
nonempty is O(p^{-delta/2}). Transfer is justified by retaining the
component label as an extra random variable: conditional Jensen shows
that conditioning on the label as well as on the other slots can only
increase the squared conditional norm, and in each normalized
component the trivial bound is ||f||_2^2, because that component has
uniform one-slot marginals. Averaging the leading estimate with these
trivial bounds gives
|| E_{rho_p}[ f(z_v) | (z_u)_{u != v} ] ||_2^2
<= C p^{-delta/2} ||f||_2^2.
Since 2 gamma = delta/5 < delta/2, one more increase of the threshold
gives the bound p^{-2 gamma} ||f||_2^2, which is property (4) and
completes the proof of the tuple-laws proposition.
Fixed constants. From now on P > P_1 is a threshold for which the
tuple-laws proposition holds, chosen large enough that
p^{gamma/2} >= 3 for p >= P,
prod_{p >= P} (1 + p^{-3}) - 1 <= 1/4,
(t+1) delta/2 > 5,
the product running over primes and converging to 1 because
sum_p p^{-3} converges. Put
M_0 = prod_{p < P} p^{E_p} >= 2.
A class modulo D = M_0 q_B, with q_B a product of distinct primes at
least P, is admissible at l if it is admissible at every factor
p^{E_p}. The integers P, P_1, L, E_p, delta, gamma, M_0, t, w, K,
r_*, c_*, c_0, C_0 are fixed from this point on, and all thresholds
below depend only on them.
Fourier lifts. The tuple laws give two complementary controls of
multilinear averages. Reflection positivity compares arbitrary
inputs with a single diagonal quantity, which yields a signed Holder
inequality and a seminorm. Conditional mixing suppresses large
Fourier denominators. Both are applied to bounded functions on
integer intervals through a lift that retains denominators up to a
bound. The reflection step is the chessboard argument of Frohlich,
Israel, Lieb and Simon; the lift and the multilinear estimates
adapt
frohlich-israel-lieb-simon-1978.pdf
https://doi.org/10.1007/BF01940327
power-saving-intersective-polynomial-differences.pdf
Fix l >= 1 and a finite set P of primes at least P. Put
X_P = product_{p in P} F_p, let mu_{l,P} be the product of the laws
mu_{l,p} over p in P, a probability measure on X_P^V, and collect
the prime labels of a slot into a single variable z_v in X_P. Every
one-slot marginal of mu_{l,P} is uniform. For real functions g_v on
X_P write
Z_{l,P}((g_v)) = int prod_{v in V} g_v(z_v) dmu_{l,P},
Z_{l,P}(g) = Z_{l,P}((g)),
where the second is the diagonal case in which every entry equals g.
The empty prime set is allowed; then X_P is a single point and
Z_{l,P}(g) = g^d.
Fourier notation on X_P. Every frequency has a unique additive
decomposition
xi = sum_{p in P} a_p/p mod 1, 0 <= a_p < p,
with character e(z xi) = prod_{p in P} e(a_p z_p/p). The exact
support of xi is the set of primes with a_p != 0, and the reduced
denominator q(xi) is the product of the support. For a set B of
primes write q_B = prod_{p in B} p, so q_empty = 1.
Signed Holder inequality. For every l >= 1, every finite set P of
primes at least P, and all real functions g, g_v on X_P,
Z_{l,P}(g) >= 0,
|Z_{l,P}((g_v))| <= prod_{v in V} Z_{l,P}(g_v)^{1/d}.
Proof. Across any reflection cut of V the matrix of the product law
mu_{l,P} is a tensor product of the cut matrices of the prime laws,
each of which is positive semidefinite by reflection positivity, so
the product cut matrix is positive semidefinite. Taking as test
function J((z_v)_{v in V_+}) = prod_{v in V_+} g(z_v) gives
Z_{l,P}(g) >= 0, the first display.
For the mixed estimate fix a cut V_+ union V_- with reflection
theta, and let Phi_+ and Phi_- be the two fold maps V -> V_+ that
fix the chosen half and reflect the other half. Given an assignment
a of functions from a fixed finite list to the slots V, write
Lambda(a) for its mixed integral. The two functions of the plus-side
labels entering the cut bilinear form are
F(x) = prod_{v in V_+} a(v)(x_v),
G(x) = prod_{v in V_+} a(theta v)(x_v).
The cut bilinear form evaluates at F, G as Lambda(a),
Lambda(a o Phi_+), and Lambda(a o Phi_-); Cauchy-Schwarz for the
positive semidefinite matrix gives
|Lambda(a)|^2 <= Lambda(a o Phi_+) Lambda(a o Phi_-),
and both factors on the right are nonnegative.
A finite chain of fold maps now sends every slot to a single one.
In one block let p_i be the position of symbol i in a permutation
word. For i = 1, ..., L - 1 fold onto the side where i precedes
i + 1; this sorts the pair (p_i, p_{i+1}) and leaves the other
entries of the word fixed. Perform the sweep i = 1, ..., L - 1 a
total of L - 1 times. Each sweep moves the largest remaining entry
to the end, and once the largest entries occupy their final
positions the next sweep fixes them and places the largest remaining
entry before them. Every position array therefore becomes
(1, 2, ..., L). Doing this in each block gives fold maps
Phi_1, ..., Phi_m, in chronological order, with
Phi_m o ... o Phi_1 (v) = v_*
for every v in V, where v_* carries the identity word in every
block.
Now fix a finite nonempty list of real functions and let M be the
maximum of |Lambda| over all assignments from the list, repetitions
allowed. If M = 0 there is nothing to prove. Otherwise take a
maximizing assignment. Each folded integral is nonnegative and at
most M, while their product is at least M^2 by the Cauchy-Schwarz
display, so both equal M and either fold preserves maximality.
Iterating the pullbacks backwards gives a constant assignment with
integral M. Hence the maximum absolute mixed integral equals the
largest diagonal value in the list.
For eps > 0 apply this to the list g_v/(Z_{l,P}(g_v) + eps)^{1/d}.
Every diagonal value of the new list is at most one, so
multilinearity gives
|Z_{l,P}((g_v))| <= prod_v (Z_{l,P}(g_v) + eps)^{1/d},
and eps tends to 0. QED
Seminorm. Put ||g||_{l,P} = Z_{l,P}(g)^{1/d} for real g on X_P, and
for B contained in P let E_B g denote the average of g over the
B-coordinates with the other coordinates fixed; it may be read as a
function on X_P or on X_{P \ B}.
Seminorm lemma. The map g -> ||g||_{l,P} is a seminorm on real
functions on X_P. Moreover:
(i) |E g| <= ||g||_{l,P};
(ii) ||E_B g||_{l,P \ B} = ||E_B g||_{l,P} <= ||g||_{l,P};
(iii) simultaneous translations of the input are isometries;
(iv) if D >= 1 is coprime to every prime in P, then for every a' in
X_P,
|| g(lambda(D)^{-1}(. - a')) ||_{l,P} = ||g||_{lD,P}.
Proof. Positive homogeneity is clear. For the triangle inequality
note that d is even; expanding Z(g + h) slot by slot and bounding
each term with the mixed estimate gives
Z(g + h) <= sum_{S subset V} ||g||^{|S|} ||h||^{d-|S|}
= (||g|| + ||h||)^d,
and taking d-th roots proves subadditivity.
(ii) The set G_B of vectors supported on the primes of B is a
subgroup of X_P, and averaging over B-coordinates is averaging over
g(z + a) with a in G_B. The triangle inequality gives the
contraction. The averaged function does not depend on the
B-coordinates, so integrating the prime laws of B out of Z leaves
the seminorm unchanged.
(i) Constant functions have |E g| equal to their diagonal value,
which is bounded by the mixed estimate with g repeated d times.
(iii) Simultaneous translation of the labels leaves every tuple law
unchanged, so Z is unchanged.
(iv) The covariance property of the tuple laws carries the product
law at l exactly to the product law at lD, and lambda(D) is a unit
at every prime of P. QED
Large-denominator lemma. Fix l >= 1 and a finite set P of primes at
least P. At every prime choose rho_p equal to mu_{l,p} or to
mu_{l,p}^circ, and let g_v : X_P -> C be arbitrary. If in one
distinguished slot v every Fourier coefficient of g_v at every
denominator at most R vanishes, with R >= 1, then
| int prod_{u in V} g_u(z_u) d(tensor_p rho_p) |
<= R^{-gamma} ||g_v||_2 prod_{u != v} ||g_u||_{2(d-1)}.
Proof. At one prime let m_p be the marginal law of the labels of all
slots other than v, and put
T_p f = E_{rho_p}[ f(z_v) | (z_u)_{u != v} ].
This is a linear map from uniform L^2(F_p) to L^2(m_p). It fixes
constants and sends mean-zero functions to functions of m_p-mean
zero, and the mixing property of the tuple laws gives norm at most
p^{-gamma} on the mean-zero Hilbert space.
Tensor the maps over the primes of P. The tensor equals the
conditional operator of the product law: this holds for products of
one-prime functions by independence and for all functions by
linearity. On the exact-support-B Fourier space the tensor acts by
at most q_B^{-gamma}. The images of two distinct exact-support
spaces are orthogonal in L^2(tensor_p m_p): at a prime in the
symmetric difference of the supports one image factor is constant
and the other has mean zero, and tensoring preserves orthogonality.
Decompose g_v = sum over exact supports B with q_B > R. Domain
summands and images are mutually orthogonal, so
||T g_v||_2^2 = sum_{q_B > R} ||T g_{v,B}||_2^2
<= sum_{q_B > R} q_B^{-2 gamma} ||g_{v,B}||_2^2
<= R^{-2 gamma} ||g_v||_2^2.
Condition the integral on all slots except v and apply
Cauchy-Schwarz. The remaining factor is
|| prod_{u != v} g_u(z_u) ||_2
<= prod_{u != v} (E |g_u(z_u)|^{2(d-1)})^{1/(2(d-1))}
= prod_{u != v} ||g_u||_{2(d-1)},
by Holder and the uniform one-slot marginals. When P is empty the
frequency hypothesis forces g_v = 0 and the claim is immediate. QED
Lifts of interval indicators. Let I be a nonempty consecutive
interval of integers and f : I -> C. Put
hat f_I(xi) = (1/|I|) sum_{x in I} f(x) e(-x xi).
For B contained in P the exact-support piece is
f_B(z) = sum_{q(xi) = q_B} hat f_I(xi) e(z xi),
which depends only on the B-coordinates and has mean zero in each of
them. For Q >= 1 the Fourier lift is
L_{I,P,Q} f(z) = sum_{B : q_B <= Q} f_B(z)
= sum_{q(xi) <= Q} hat f_I(xi) e(z xi).
Retaining a support always means retaining all of its frequencies.
When f is real every piece and every lift is real.
Lift-moments proposition. Let P be a finite set of primes, Q >= 1,
and I a consecutive integer interval with |I| >= 10 Q^6. For every
integer r >= 1, every eps > 0, every f : I -> C, and every subfamily
F of the supports with q_B <= Q,
|| sum_{B in F} f_B ||_{2r} <= C_{r,eps} ||f||_infty Q^eps,
with a constant independent of the prime set, of the interval and
its location, of the function, and of the subfamily.
Proof. The zero function is trivial, so rescale to ||f||_infty <= 1.
Write N_I = |I| and let u = max{|B| : q_B <= Q}, finite because the
empty support is allowed.
Step 1, conditional energy. For J contained in P with q_J <= Q and
any fixed z_J,
sum_{B in F, B contains J} E( |f_B|^2 | z_J ) <= 4^{|J|}.
The conditional expectation averages uniformly over the coordinates
outside J. If B contains J, the coefficient of an outside character
eta with exact support B \ J after fixing z_J equals
c_J(eta; z_J) = (1/N_I) sum_{x in I} f(x) e(-x eta)
prod_{p in J} ( p 1_{x = z_p mod p} - 1 ),
the last factor arising from summing the nonzero frequencies at p.
The character sets attached to different B containing J are
disjoint, so conditional Parseval writes the left side as the
squared Euclidean norm of this coefficient vector.
Expand the product over J' contained in J. Up to sign, the term J'
contributes a vector with coordinates
(q_{J'}/N_I) sum_{x in I, x = z_{J'} mod q_{J'}} f(x) e(-x eta).
Write the progression as x = a + q_{J'} n with n in a consecutive
interval of length N'. Then N' >= 0.9 N_I/q_{J'} and
N' q_{J'}/N_I <= 1.1. After the substitution the frequencies
q_{J'} eta are still distinct, since their denominators are coprime
to q_J, so they number at most Q^2 and are at least Q^{-2} apart on
the circle. The Gram matrix of these characters in normalized L^2 on
the progression has diagonal 1 and off-diagonal entries of modulus
at most Q^2/(2N') = Q^5/(1.8 N_I) <= 1/(18 Q). Its operator norm is
therefore at most its maximum row sum, which is at most
1 + 1/(18 Q).
The synthesis map sending coefficients (b_eta) to
sum_eta b_eta e(n q_{J'} eta) on the progression, with normalized
counting measure, has Gram matrix equal to the estimate just
derived, and its adjoint is the normalized Fourier analysis map.
Since ||f||_infty <= 1 and N' q_{J'}/N_I <= 1.1, the coefficient
vector has Euclidean norm bounded by an absolute constant. The
triangle inequality over the 2^{|J|} subsets J', followed by
squaring, proves the conditional-energy bound.
Step 2, square-function moments. Put
S(z) = ( sum_{B in F} |f_B(z)|^2 )^{1/2}.
Expand E S^{2r} and fix the supports of the first r - 1 factors;
their union W' has at most (r-1)u elements and their product depends
only on z_{W'}. For the last support B, the function f_B ignores
coordinates outside B, so integration outside W' leaves exactly
E(|f_B|^2 | z_J) with J = B intersect W'. Every intersection that
occurs has q_J <= q_B <= Q, and for each fixed J the sum over the
supports with B intersect W' = J is bounded by the larger sum over
B containing J in the conditional-energy bound. There are at most
2^{(r-1)u} intersections, so
E S^{2r} <= C 2^{(r-1)u} 4^u E S^{2r-2},
and the case r = 1 uses J = W' empty. Iteration gives
||S||_{2r} <= C_r^{1+u}.
Step 3, recovering the sum. First treat transversal supports. Fix a
support size j >= 1 and color every prime coordinate with one of j
colors. A support is transversal when it has j elements, one of each
color; let T be the set of transversal supports belonging to F.
Take independent uniform pairs (X_p^0, X_p^1) at every prime, let
swap_p interchange the two copies at prime p, and put
D_B = prod_{p in B} (1 - swap_p) f_B(X^0).
Averaging over the second copies leaves f_B(X^0), because every
other term of the expansion has mean zero in some copied coordinate,
and Jensen gives
|| sum_{B in T} f_B ||_{2r}
<= || sum_{B in T} D_B ||_{L^{2r}(X^0, X^1)}.
Independent swaps preserve the joint law of the copies and multiply
D_B by a product of signs, so for independent uniform signs eps_p,
|| sum_{B in T} D_B ||_{L^{2r}(X^0,X^1)}
= || sum_{B in T} D_B prod_{p in B} eps_p ||
_{L^{2r}(X^0,X^1,eps)}.
Scalar sign estimate. For any coefficients (a_i) and any r >= 1,
|| sum_i a_i eps_i ||_{2r} <= C_r ( sum_i |a_i|^2 )^{1/2}.
This is Khintchine's inequality for Rademacher sums. Expanding the
even moment, every |a_i|^2 survives with an even multiplicity; for
nonnegative coefficients the moment is at most
(2r)!/(2^r r!) (sum_i a_i^2)^r, because (2m)! >= 2^m m!, and the
complex case follows by applying the inequality to the product of
the two conjugate sums and using the triangle inequality.
khintchine-1923-dyadische-brueche.pdf
Iterating over the j color classes, with Minkowski in the
intermediate L^{2r} spaces, gives, for fixed copies X^0, X^1,
|| sum_{B in T} D_B prod_{p in B} eps_p ||_{2r}
<= C_r^j ( sum_{B in T} |D_B|^2 )^{1/2}.
Expanding the swaps in D_B gives 2^j terms indexed by a choice of
copy at each color. For any fixed choice, consistent across the
supports, the selected coordinates retain their original uniform
product law, and the triangle inequality in L^{2r}(l^2(T)) gives
|| ( sum_{B in T} |D_B|^2 )^{1/2} ||_{2r}
<= 2^j || ( sum_{B in T} |f_B|^2 )^{1/2} ||_{2r}
<= 2^j ||S||_{2r}.
So the transversal sum has norm at most (2 C_r)^j ||S||_{2r}.
Average over independent uniform colorings. A fixed support of size
j is transversal with probability j!/j^j >= e^{-j}, since
log j! >= integral_1^j log x dx. The full size-j sum is the coloring
average of the transversal sum divided by this probability, so
Minkowski yields
|| sum_{B in F, |B| = j} f_B ||_{2r} <= (2 e C_r)^j ||S||_{2r}.
Include the empty support and sum over j <= u. After trimming
constants,
|| sum_{B in F} f_B ||_{2r} <= (C'_r)^{1+u}.
The product of u distinct primes is at least (u+1)!, so (u+1)! <= Q
and therefore u = o(log Q) as Q tends to infinity, uniformly in the
prime set. For every fixed r and eps one has
(C'_r)^{1+u} <= C_{r,eps} Q^eps, and restoring ||f||_infty proves
the proposition. QED
Specialization lemma. Let B be contained in P, fix z_B in X_B, and
let G : X_P -> C. For 1 <= s < infinity,
|| G(z_B, .) ||_{L^s(X_{P \ B})} <= q_B^{1/s} ||G||_{L^s(X_P)}.
In particular a lift, or a subfamily of its complete supports,
satisfies the lift-moments bound after specialization with an extra
factor q_B^{1/(2r)}, and the same holds after retaining either the
denominators at most H or those greater than H.
Proof. The fiber z = z_B has probability 1/q_B in X_P, and its
contribution to E|G|^s is q_B^{-1} E|G(z_B, .)|^s; dropping the
other q_B - 1 nonnegative contributions gives the display. For the
subfamily cut, a character with support C keeps exact support C \ B
after specialization, so the two cuts in the remaining denominators
come from the families with q_{C \ B} <= H and q_{C \ B} > H. Apply
the lift-moments bound to these families and then the display.
Combining coefficients can cancel frequencies but cannot create any
outside the indicated ranges. QED
Cost of specialization. Specializing the same set B of coordinates
in every slot, with possibly different values, and applying the
large-denominator lemma to the product law on the remaining primes
incurs the total factor
q_B^{1/2} ( q_B^{1/(2(d-1))} )^{d-1} = q_B.
Two specialized L^2 norms incur the same factor. All moment orders
needed later are fixed once h is fixed, finite products of their
subpower bounds remain subpower, and none depends on l, on the
specialized values, or on the retained supports.
Prime estimates. Two uniform estimates feed the kernel comparison.
The first is an asymptotic formula for primes in residue classes. The
second is cancellation in polynomial exponential sums over primes.
Both rest on a zero-free half-plane for Dirichlet L-functions.
Write Lambda'(n) = log n when n is prime and Lambda'(n) = 0
otherwise, and let Lambda be the von Mangoldt function, equal to
log p when n = p^j with j >= 1 and zero otherwise. Sums run over
integers, and sums with real endpoints are read by summation by
parts. Constants in this part do not depend on the lower
coefficients of polynomial phases.
Zero-free input. For every integer b >= 1 and every Dirichlet
character chi modulo b, the function L(s, chi) has no zero in the
half-plane Re s > 7/8. Imprimitive characters and the trivial
character of modulus 1 are included; a pole at s = 1 for a principal
character is allowed.
quasi-riemann-hypothesis-zero-free-half-plane.pdf
Only the assertion about L-functions is used; its proof is not
repeated here. The standard toolbox for contour estimates with
L-functions, in particular the use of Borel-Caratheodory for
logarithmic derivatives, is presented in Davenport's book.
davenport-multiplicative-number-theory.pdf
Primes in residue classes. Uniformly for Y >= 2, 0 <= x <= Y,
integers b >= 1, and reduced classes c modulo b,
sum_{n <= x, n = c mod b} Lambda'(n)
= x/phi(b) + O(Y^{31/32} log^2(2 b Y)).
For a nonreduced class modulo b > 1 the sum is O(log b) and the main
term vanishes.
Proof. Put sigma_0 = 15/16. First comes the logarithmic derivative
estimate
|(L'/L)(s, chi)| << log(2 b (2 + |Im s|)),
valid on Re s = sigma_0 and throughout sigma_0 <= Re s <= 2 when
|Im s| >= 1, with absolute constants including imprimitive
characters.
Write delta_chi = 1 for a principal character and 0 otherwise, and
put G_chi(s) = (s - 1)^{delta_chi} L(s, chi). Fix radii
2 - sigma_0 < r < R < 2 - 7/8 and use disks of radius R centered at
s_t = 2 + i t. The zero-free input makes G_chi holomorphic and
nonvanishing on every disk, the principal pole having been removed.
To bound its modulus above, use periodicity to write
sum_{n <= u} chi(n) = bar chi u + E_chi(u),
|E_chi(u)| <= 2 b,
with bar chi = phi(b)/b for a principal character and bar chi = 0
otherwise. Partial summation continues the Dirichlet series to
Re s > 0:
L(s, chi) = bar chi s/(s - 1)
+ s int_1^infty E_chi(u) u^{-s-1} du.
On the disk, |G_chi(s)| <= C [2 b (2 + |t|)]^C. At the center the
Euler product gives |L(2 + i t, chi)| >= zeta(4)/zeta(2), so
|G_chi(s_t)| is bounded below by a positive constant. Choose a
holomorphic logarithm and subtract its value at s_t; its real part is
at most C log(2 b (2 + |t|)). Borel-Caratheodory on an intermediate
disk, followed by Cauchy's estimate on the disk of radius r, gives
|(G_chi'/G_chi)(s)| << log(2 b (2 + |t|))
for |s - s_t| <= r. Subtracting delta_chi/(s - 1) proves the
logarithmic derivative bound.
Smooth sum. Absolute convergence of the contour integral requires
smoothing, and the choice (1 - u)_+ suffices. Mellin inversion
gives, for x >= 1,
sum_{n <= x} (x - n) Lambda(n) chi(n)
= (1/(2 pi i)) int_{(2)} -(L'/L)(s, chi)
x^{s+1}/(s(s+1)) ds.
The interchange with the Dirichlet series is absolute. Move the line
to Re s = sigma_0. The horizontal integrals are bounded by
C x^3 log(2 b (2 + T))/T^2, which tends to zero as T grows. The only
crossed pole is at s = 1 for a principal character, with residue
x^2/2. On the new vertical line, integrating
log(2 b (2 + |t|))/(1 + t^2) gives
sum_{n <= x} (x - n) Lambda(n) chi(n)
= delta_chi x^2/2 + O(x^{1 + sigma_0} log(2 b)).
Orthogonality. For (c, b) = 1, character orthogonality yields
A_c(x) = sum_{n <= x, n = c mod b} (x - n) Lambda(n)
= x^2/(2 phi(b)) + O(x^{1 + sigma_0} log(2 b)),
the phi(b) character errors summing and dividing by phi(b), which
keeps the bound uniform in b.
Sharp differencing on a nonnegative sum. Positivity of Lambda avoids
the delicate complex character problem. For 0 < H < x,
(A_c(x) - A_c(x - H))/H
<= sum_{n <= x, n = c mod b} Lambda(n)
<= (A_c(x + H) - A_c(x))/H.
Take H = x^{31/32}. The main terms differ from x/phi(b) by O(H), and
the errors are O(x^{1 + sigma_0}/H log(2 b)) = O(x^{31/32} log(2 b)).
Bounded x is harmless.
Higher prime powers. Since
sum_{p^j <= Y, j >= 2} log p << Y^{1/2} log^2(2 Y),
removing these from the summable contributions proves the displayed
formula. A prime in a nonreduced class modulo b divides b, and the
sum of logarithms of distinct such primes is at most log b, which is
the last assertion. QED
Cancellation over primes. Fix k >= 2 and 0 < rho < 1. There is a
constant c_m = c_m(k, rho) in (0, 1/4) with the following property.
If Y is large, I is an interval contained in [1, Y], and f is a real
polynomial of degree at most k with coefficient b_k of x^k, then
| sum_{n in I} Lambda'(n) e(f(n)) | <<_{k,rho} Y^{1 - c_m},
provided theta = (k!)^2 b_k admits an approximation a/q with
(a, q) = 1, |theta - a/q| <= q^{-2}, Y^rho <= q <= Y^{k-rho}.
The proof splits the prime sum with Vaughan's identity and converts
every resulting sum into averages of linear phases by differencing,
the method of Weyl. The two elementary tools are classical and come
first.
weyl-1916-gleichverteilung.pdf
https://doi.org/10.1007/BF01475864
Rational spacing. Suppose (a, q) = 1, q >= 2, and
|theta - a/q| <= q^{-2}. For R >= 1 and M >= 1,
sum_{1 <= r <= R} min(M, ||theta r||^{-1})
<< (R/q + 1)(M + q log(2 q)).
Proof. Inside a block of floor(q/2) consecutive integers two distinct
indices differ by a nonzero d with |d| < q/2, and
||theta d|| >= ||a d/q|| - |d|/q^2 >= 1/(2 q),
so the associated points are 1/(2 q) apart on the circle. The point
nearest zero contributes at most M, and summing the others in bands
of width 1/(2 q) costs O(q log(2 q)). Partitioning the indices into
such blocks proves the bound. QED
Divisor counting. When a fixed number of nonzero integer factors is
grouped by its product, and that product has absolute value at most
Y^{C_k}, the number of such factorizations is Y^{o(1)}, uniformly in
the product: the prime factorization bounds the count by a
fixed-order divisor function, up to a bounded number of sign choices.
Differencing lemma. Let k >= 2 and let f be a real polynomial of
degree at most k with coefficient b_k of x^k.
(i) If J is an interval of integers of length at most an integer
M >= 1 and m is a positive integer, then
| (1/M) sum_{n in J} e(f(m n)) |^{2^{k-1}}
<<_k (1/M^k) sum_{|u_1|, ..., |u_{k-1}| < M}
min(M, ||k! b_k m^k u_1 ... u_{k-1}||^{-1}).
(ii) Let A and B be positive integers, I an interval contained in
[1, Y], and |a_m|, |d_n| <= 1. Set
S = sum_{A <= m < 2A, B <= n < 2B}
a_m d_n 1_{m n in I} e(f(m n)),
and theta = (k!)^2 b_k. Then
|S/(A B)|^{2^{2k-1}}
<<_k (1/(A^k B^k))
sum_{|u_1|, ..., |u_k| < B; |v_1|, ..., |v_{k-1}| < A}
min(A, ||theta u_1 ... u_k v_1 ... v_{k-1}||^{-1}).
Zero shifts occur on both sides.
Proof. Part (ii) is proved; part (i) is the same argument with a
single variable. For a two-variable function g put
Delta^n_u g(m, n) = g(m, n + u) - g(m, n),
Delta^m_v g(m, n) = g(m + v, n) - g(m, n).
Let D_0 be the set of pairs (m, n) of the box with m n in I, and
extend all coefficients by zero outside their boxes.
Cauchy-Schwarz in m gives
|S/(A B)|^2 <= (1/A) sum_{A <= m < 2A}
| (1/B) sum_n d_n 1_{D_0}(m, n) e(f(m n)) |^2.
Expand the square and group by u = n' - n:
<= (1/B) sum_{|u| < B} | (1/(A B)) sum_{m, n}
d_{n+u} bar d_n 1_{D_0}(m, n + u) 1_{D_0}(m, n)
e(Delta^n_u f(m n)) |.
For fixed u the new weight depends only on n and is bounded by one,
so a further n-difference is available. The product cutoff m n in I
is preserved throughout; it is never replaced by a rectangular
domain.
Induction over n-shifts. For shifts u = (u_1, ..., u_j) put
D_u = { (m, n) : (m, n + eps*u) in D_0 for every eps in {0,1}^j },
F_u(m, n) = Delta^n_{u_j} ... Delta^n_{u_1} f(m n),
and define the accompanying coefficient recursively by
d_empty(n) = d_n and d_{(u, u')}(n) = d_u(n + u') bar d_u(n); it is
bounded by one. Cauchy-Schwarz in the existing shifts, which acts
unitarily after normalizing, together with Cauchy-Schwarz in m and
another square expansion in n, adds one more n-shift. Iteration
gives
|S/(A B)|^{2^k} <<_k (1/B^k) sum_{|u_1|, ..., |u_k| < B}
| (1/(A B)) sum_{m, n} d_u(n) 1_{D_u}(m, n) e(F_u(m, n)) |.
Every summand still has m and n in their original intervals, because
the zero vertex of each translated cube lies in D_0.
After k differences in n every lower-degree term vanishes, and
F_u(m, n) = k! b_k u_1 ... u_k m^k.
For 0 <= j <= k-1 and m-shifts v = (v_1, ..., v_j) put
D_{u,v} = { (m, n) : (m + eta*v, n + eps*u) in D_0
for every eta in {0,1}^j and eps in {0,1}^k },
T_{u,v} = (1/(A B)) sum_{m, n} 1_{D_{u,v}}(m, n)
e(Delta^m_{v_j} ... Delta^m_{v_1} F_u(m, n)),
with D_{u,empty} = D_u. To remove d_u, apply Cauchy-Schwarz in n:
| (1/(A B)) sum_{m, n} d_u(n) 1_{D_u}(m, n) e(F_u(m, n)) |^2
<= (1/B) sum_{B <= n < 2B}
| (1/A) sum_m 1_{D_u}(m, n) e(F_u(m, n)) |^2.
Expanding the square bounds this by
(1/A) sum_{|v_1| < A} |T_{u,(v_1)}|,
which is the first m-differencing step: removing d_u costs no extra
squaring. For 1 <= j <= k-2, Cauchy-Schwarz in n and the same square
expansion give
|T_{u,v}|^2 <= (1/A) sum_{|v| < A} |T_{u,(v,v)}|.
Applying Cauchy-Schwarz also over the existing shifts, whose total
normalized mass is bounded by a constant depending on k, yields
|S/(A B)|^{2^{k+j}}
<<_k (1/(B^k A^j)) sum_{|u| < B, |v| < A} |T_{u,v}|
for 1 <= j <= k-1.
Take j = k-1. For fixed n the section of D_{u,v} in m is an
interval: each condition places m + eta*v in [A, 2A) and its product
with the positive number n + eps*u in I, and the intersection has
length at most A. The final phase
Delta^m_{v_{k-1}} ... Delta^m_{v_1} F_u is linear in m with
coefficient
(k!)^2 b_k u_1 ... u_k v_1 ... v_{k-1}.
Geometric summation bounds each m-sum by the stated minimum divided
by A; summing over at most B values of n leaves that minimum divided
by A B. The shift weights factor as B^{-k} A^{-(k-1)}, which proves
part (ii). Part (i) repeats the argument in one variable: k-1 square
expansions remove the auxiliary variable, the final phase is linear
with coefficient k! b_k m^k u_1 ... u_{k-1}, and the normalizer is
M^{-k}. QED
Proof of the minor-arc proposition. It is enough to prove the bound
with Lambda in place of Lambda'; the passage back is described at the
end. Put e_0 = rho/(100 k) and Z = Y^{e_0}. For an arithmetic
function g write g_{<= Z}(n) = g(n) 1_{n <= Z} and
g_{> Z} = g - g_{<= Z}. Let mu be the Mobius function, 1 the
constant function, and * Dirichlet convolution. Vaughan's identity,
in the form used here, reads
Lambda = Lambda_{<= Z} + mu_{<= Z} * log
- mu_{<= Z} * Lambda_{<= Z} * 1
+ (mu_{> Z} * 1) * Lambda_{> Z},
which follows from log = 1 * Lambda and mu * 1 = 1_{n=1}.
vaughan-1980-elementary-method.pdf
https://doi.org/10.4064/aa-37-1-111-115
vaughan-1997-hardy-littlewood-method.pdf
https://doi.org/10.1017/CBO9780511470929
https://doi.org/10.1017/CBO9780511470929
Sums with one short variable. The middle two terms of the identity
are sums whose outer variable satisfies m <= Z^2 and whose inner
variable satisfies n <= Y/m. The outer coefficient is either mu(m) or
a divisor-type sum over a b = m with a, b <= Z, hence of size
Y^{o(1)}, and the inner weight is log n or 1. Fix m, put
M = ceil(Y/m), and consider an arbitrary interval subsum
S_m = sum_{n in J} e(f(m n)).
The one-variable half of the differencing lemma, the inequality
min(M, ||k! b_k r||^{-1}) <= k! min(M, ||theta r||^{-1}) with
theta = (k!)^2 b_k, and the rational-spacing bound, applied after
grouping nonzero shift tuples by their product
r = m^k u_1 ... u_{k-1} <= m^k M^{k-1}, give, uniformly in the
interval,
|S_m/M|^{2^{k-1}} << Y^{o(1)}
( 1/M + m^k/q + m^k/M + 1/M^{k-1} + q/M^k ).
Since m <= Y^{2 e_0} and M >= Y^{1 - 2 e_0},
m^k/q, q/M^k <= Y^{-rho + 2 k e_0},
m^k/M <= Y^{-1 + 2(k+1) e_0},
and the remaining terms save a positive power as well. Taking the
2^{k-1}-st root gives S_m << M Y^{-c} for some c = c(k, rho) > 0,
uniform in the subinterval. Partial summation handles the weight
log n at the cost of an extra O(log Y). Summing over m <= Z^2 uses
sum_{m <= Z^2} ceil(Y/m) << Y log(2 Y),
so both short-variable terms lose only a fixed power of Y after the
outer coefficients are included.
Bilinear sums. If A B < Y^{1 - e_0} the trivial estimate suffices,
so assume A B >= Y^{1 - e_0}. The last term of the identity is a
bilinear form in (mu_{> Z} * 1)(m) and Lambda_{> Z}(n). Each
coefficient is Y^{o(1)} when m n <= Y, and a nonzero coefficient
forces m > Z and n > Z. Partition into dyadic boxes
A <= m < 2A, B <= n < 2B, A, B >= Z/2, A B <= Y.
There are O(log^2(2 Y)) relevant boxes. Dividing out the coefficient
bounds reduces each box to |a_m|, |d_n| <= 1, to which the mixed half
of the differencing lemma applies.
Group nonzero shift tuples by their absolute product, at most
R = A^{k-1} B^k. The rational-spacing bound and the divisor-counting
remark give
|S/(A B)|^{2^{2k-1}} << Y^{o(1)}
( 1/A + 1/B + 1/q + 1/R + q/(A R) ).
Each nonzero shift bound before expansion is
Y^{o(1)}/(A R) times (R/q + 1)(A + q log(2 q)), and the term
O(log(2 q)/A) is absorbed. Now A, B >= Y^{e_0}/2, and
A R = (A B)^k >= Y^{k(1 - e_0)},
q/(A R) <= Y^{-rho + k e_0},
so the display saves a fixed power of Y, uniformly over the boxes.
Conclusion. The remaining term Lambda_{<= Z} costs
O(Z log(2 Z)). This proves the bound for Lambda with a positive
exponent depending only on k and rho. Removing higher prime powers
costs O(Y^{1/2} log^2(2 Y)), and decreasing the exponent if necessary
gives c_m in (0, 1/4). QED
Kernel comparison. The tuple laws prescribe, along each cycle edge,
a distribution of admissible increments. The next step realizes the
low-denominator Fourier multipliers of that distribution by a signed
kernel supported on prime arguments of the auxiliary polynomial, so
that avoidance of prime-supported values gives cancellation for
pairs of Fourier lifts. The comparison follows the integer-argument
method of
power-saving-intersective-polynomial-differences.pdf
with the additional ingredient of the unit conditions at prime
arguments, handled through the unit means and allowed regular
arguments of the local sections.
Parameters. Fix, depending only on h,
eta = 1/(10000 k),
c_m = c_m(k, eta/4),
nu = min(eta, c_m/k) / 10,
beta = nu/100, zeta = nu/100,
tau = beta gamma / (1000 k (d + 1)),
sigma = gamma tau / 4,
where c_m is the exponent from the cancellation-over-primes bound.
The symbol eta is distinct from the exceptional masses eta_{l,p}. For
scale N set
Q = N^beta, H = N^{beta/2}, P_N = { p prime : P <= p <= Q }.
The edge multiplier. Fix l >= 1, write F = h_l, and choose a
directed cycle edge v_j -> v_{j+1}. For each p >= P let pi_p be the
F_p-distribution of z_{v_{j+1}} - z_{v_j} under mu_{l,p}^circ; the
tuple laws put its mass on admissible residues. For integer v define
Gamma_p(v/p) = sum_{y in F_p} pi_p(y) e(v y / p).
For v coprime to p, the conditional mixing estimate at the second
endpoint, paired with the conjugate character at the first, gives
|Gamma_p(v/p)| <= p^{-gamma}.
For rational xi with squarefree denominator supported on primes at
least P, there is a unique decomposition xi = sum_{p | q(xi)} xi_p
modulo 1, and the multiplier is defined as the product
Gamma(xi) = prod_{p | q(xi)} Gamma_p(xi_p).
It satisfies
Gamma(0) = 1, |Gamma(xi)| <= q(xi)^{-gamma}.
The multiplier may depend on l and on the chosen edge; every estimate
below is uniform in both.
Pair-cancellation proposition. Let N be sufficiently large, let
l <= N^zeta, and let D = M_0 q_B <= N^beta with q_B the product of a
finite set B of primes at least P. Let J_1, J_2 : [N] -> C satisfy
|J_i| <= 1 and vanish off residue classes a'_1, a'_2 modulo D. Assume
that r = a'_2 - a'_1 modulo D is admissible at l, and that
J_1(x) J_2(y) != 0 implies x < y and y - x not in D_l.
Set Xi to be the set of frequencies xi with q(xi) <= H, q(xi)
squarefree, and (q(xi), D) = 1. Then, for the multiplier of any
directed cycle edge,
D | sum_{xi in Xi} Gamma(xi) hat J_1(-xi) hat J_2(xi) |
<< H^{-gamma/2}.
Because M_0 contains every prime below P, the multiplier is defined
on Xi. Denote by hat f the normalized Fourier transform of f on [N].
The auxiliary family reaches N at a point of size about N^{1/k}
times a factor coming from lambda(l), which is where the unit
conditions of the prime arguments are used.
Unit means. For a periodic function of an integer m, its unit mean
modulo b averages over the classes m modulo b with (T_l(m), b) = 1.
There are exactly
n_b = b prod_{p | b, p not dividing l} (1 - 1/p) = phi(l b)/phi(l)
such classes: a prime p dividing l excludes no class, because
(r_l, l) = 1, while a prime p not dividing l excludes one. These
means factor over prime powers and are consistent under replacing b
by a multiple.
At a prime p dividing D, choose an argument witnessing admissibility
of r modulo p^{E_p} and put s_p = v_p(F'). The lifting lemma
supplies a class modulo p^{E_p - s_p} on which the unit condition
holds and F is congruent to r modulo p^{E_p}, and uniform argument
lifts in that class give uniform higher lifts of the value. The
Chinese remainder theorem produces a single class modulo
d_r = prod_{p | D} p^{E_p - s_p}, d_r | D.
Let rho_D be n_{d_r} times the indicator of that class. Then rho_D
has unit mean one and |rho_D| <= D.
At a prime p not dividing D, necessarily p >= P, choose for each y
with pi_p(y) > 0 one allowed regular argument x_y modulo p with
F(x_y) = y, and set
psi_p(x_y) = n_p pi_p(y), psi_p(x) = 0 at every other class.
Then psi_p has unit mean one, and its F-value distribution is
exactly pi_p. Put
B_p = psi_p - 1, B_u = prod_{p | u} B_p, B_1 = 1,
for squarefree u coprime to D. Each B_p has unit mean zero, B_u has
period u, and |B_u| <= u.
Expanding psi_p = 1 + B_p produces a product sum over squarefree u.
In a unit mean against a rational phase e(alpha F(m)), a prime factor
of u absent from q(alpha) makes the corresponding term vanish. So
retaining u <= H keeps every term that could contribute when the
D-free part of q(alpha) is at most H; denominators greater than H
are bounded separately.
The model kernel. For the data of the pair-cancellation proposition
set
k_0(n) = (D/N) 1_{1 <= n <= N} 1_{n = r mod D}
sum_{xi in Xi} Gamma(xi) e(-xi n).
The congruence restriction is imposed on polynomial arguments by a
local weight, and the factors Gamma_p by weights of unit mean one.
The prime-supported kernel. Put U = (N/a_l)^{1/k}. Since a_l is a
positive integer with a_l <= a l^k,
U <= N^{1/k}, U >> N^{1/k - zeta}.
By the auxiliary-family lemma there is an absolute x_* such that for
x >= x_*,
F(x) ~ a_l x^k, F'(x) ~ k a_l x^{k-1}, F''(x) = O(a_l x^{k-2}),
so there is a unique X >= x_* with F(X) = N, and X ~ U. Put Y = C l U
with a fixed C large enough that T_l(X) <= Y. The relation
a_l = a l^k/lambda(l) gives
Y >> N^{1/k}, Y << N^{1/k + zeta}, Y^k ~ N lambda(l),
and in particular Y <= N for large N. Define
k_1(n) = sum_{x_* < m <= X} 1_{n = F(m)}
(F'(m)/N) (phi(l)/l) Lambda'(T_l(m)) rho_D(m)
sum_{u <= H, squarefree, (u, D) = 1} B_u(m).
Every nonzero term has 0 < F(m) <= N and T_l(m) prime, so k_1 is
supported on D_l intersect [N]. No positivity is required.
Kernel-comparison lemma. For the data of the pair-cancellation
proposition,
sup_{alpha in R/Z} |S_0(alpha) - S_1(alpha)| << H^{-gamma/2},
where S_i(alpha) = sum_{n in Z} k_i(n) e(alpha n).
Proof. Use major arcs of radius 3 N^{-1 + eta} around reduced
rationals of denominator at most N^eta; they are disjoint for large
N because 3 eta < 1. Bound both transforms off them, then compare
coefficients on them.
Minor arc for S_0. Expanding the congruence indicator in the model
kernel gives the exact identity
S_0(alpha) = sum_{xi in Xi} sum_{j' mod D} Gamma(xi)
e(-j' r/D) V_N(alpha - xi + j'/D),
with V_N(y) = N^{-1} sum_{1 <= n <= N} e(y n). There are O(D H^2)
terms, and their centers are distinct: an equality between two of
them would exhibit a rational whose denominator is at once coprime
to D, as a divisor of q(xi), and a divisor of D, as a center j'/D.
Every center has denominator at most D H <= N^{3 beta/2} <= N^eta.
On minor arcs the geometric-summation bound for V_N gives
|S_0(alpha)| << D H^2 N^{-eta}.
Minor arc for S_1. Fix a linear twist y' and consider sums over
subintervals I of (x_*, X] of Lambda'(T_l(m)) e(alpha F(m) + y' m).
Substitute n = T_l(m) and expand the restriction n = r_l mod l as
the average of its l additive characters. Each resulting prime sum
has polynomial phase in n with coefficient of n^k equal to
b_k = alpha a/lambda(l); the twist changes only the linear
coefficient, because k >= 2.
Fix a representative of alpha and apply Dirichlet approximation to
theta = (k!)^2 b_k with Q_0 = floor(Y^k N^{-eta/2}). The reduced
a'/q satisfies q <= Q_0 and |theta - a'/q| <= q^{-2}. Since
Y^k ~ N lambda(l), this places alpha within O(N^{-1 + eta/2}) of a
rational of denominator at most (k!)^2 a q. A minor-arc point must
have that denominator exceeding N^eta, so with Y <= N,
Y^{eta/4} <= q <= Y^{k - eta/4}.
The cancellation-over-primes bound then gives O(Y^{1 - c_m}),
uniformly in the linear twist and the interval.
Since Y = C l U and U is bounded below,
Y^{1 - c_m} << U l N^{-c_m/k} <= U N^{zeta - c_m/k}
<< U N^{-nu}.
Partial summation against the F'/N weight, whose supremum and total
variation are O(U^{-1}), and against rho_D and B_u, retains
O(U^{-nu}). The Fourier l^1 norms are small: rho_D is a constant
times one residue-class indicator, so at most n_{d_r} <= D, and
B_u, bounded by its period times its supremum, contributes at most
u^2. Hence
|S_1(alpha)| << D sum_{u <= H} u^2 N^{-nu} << D H^3 N^{-nu}.
The two powers are 2 beta - eta and 5 beta/2 - nu. Both are below
-beta gamma/4 because beta, zeta <= eta/1000, eta = 1/(10000 k) and
gamma < 1, so both bounds are O(H^{-gamma/2}).
Major arcs. Write alpha = alpha_0 + y on a major arc, with
q = q(alpha_0) <= N^eta and |y| <= 3 N^{-1 + eta}. Split
alpha_0 = alpha_D + alpha_1 into the prime-power denominator parts
supported on primes dividing D and on primes not dividing D. The
coefficient attached in the model-kernel identity to the center
alpha_0, or zero if that center is absent, is
c_0(alpha_0) = e(alpha_D r) Gamma(alpha_1)
if q(alpha_D) divides D and alpha_1 lies in Xi, and 0 otherwise.
Every other center is at circle distance at least 1/(q D H) from
alpha_0, and |y| q D H = o(1), so geometric summation in each of the
O(D H^2) terms gives
S_0(alpha) = c_0(alpha_0) V_N(y) + O(q D^2 H^3/N).
Coefficients for S_1. For squarefree u <= H coprime to D let A_u be
the unit mean of b_u(m) = rho_D(m) B_u(m) e(alpha_0 F(m)). Its period
divides b = q D u, and |b_u| <= D u. For x_* <= x' < x'' <= X the
primes-in-progressions proposition gives
sum_{x' < m <= x''} b_u(m) (phi(l)/l) Lambda'(T_l(m))
= A_u (x'' - x')
+ O(q D^2 u^2 Y^{31/32} log^2(2 l b Y)).
Indeed one class m = c modulo b maps to r_l + l c modulo l b in the
prime interval of length l (x'' - x'), and it is reduced exactly when
(T_l(c), b) = 1, since (r_l, l) = 1. On reduced classes the factor
phi(l)/l changes the main term to (x'' - x')/n_b, matching A_u. A
nonreduced class supports only finitely many primes dividing l b,
whose total logarithmic weight is O(log(l b)) with no main term.
The smooth factor F'(m) e(y F(m))/N has supremum plus total
variation O((1 + N|y|)/U). Partial summation gives main term
(A_u/N) int_{x_*}^X F'(x) e(y F(x)) dx
= (A_u/N) int_{F(x_*)}^N e(y t) dt.
The normalized integral differs from V_N(y) by
O(a_l/N + (1 + N|y|)/N): the missing initial interval has length
F(x_*) << a_l, and comparing integral and integer sum on [0, N]
costs O(1 + N|y|). Hence
S_1(alpha) = c(alpha_0) V_N(y) + O(H^{-gamma/2}),
c(alpha_0) = sum_{u <= H, squarefree, (u, D) = 1} A_u.
Error bounds. Since Y^{31/32}/U << l N^{-1/(32 k)}, the summed
progression error, over at most b = q D u classes with weights at
most D u and u <= H, is
((1 + N|y|)/U) q D^2 sum_{u <= H} u^2 Y^{31/32} N^{o(1)}
<< N^{2 eta + 4 beta + zeta - 1/(32 k) + o(1)}.
The replacement of the integrals is
O(D H^2 (U^{-k} + N^{eta - 1}))
<< N^{2 beta + k zeta - 1} + N^{2 beta + eta - 1},
and the error in the model-kernel major-arc identity is at most
N^{eta + 7 beta/2 - 1}. All three are O(N^{-beta gamma/4}), because
beta, zeta <= eta/1000, eta = 1/(10000 k) and gamma < 1; the first
exponent has enough margin to absorb the o(1) loss.
Comparing c and c_0. At primes dividing D the common factor in every
A_u is
chi_D(alpha_0) = e(alpha_D r) if q(alpha_D) divides D, else 0.
The p-adic unit-mean base class has prescribed F-value r modulo
p^{E_p} and unit mean one, so a character of conductor at most
p^{E_p} returns r. A primitive character of higher conductor
averages to zero, because the lifting lemma gives uniform higher
lifts of F on the class, all satisfying the unit condition.
At primes not dividing D put q_1 = q(alpha_1). If u has a prime
factor outside q_1, then B_p has unit mean zero and A_u = 0. For
p^j exactly dividing q_1 define
a_{p,j} = E_{m mod p^j, p not dividing T_l(m)} e(alpha_p F(m)),
b_{p,j} = E_{m mod p^j, p not dividing T_l(m)}
B_p(m) e(alpha_p F(m)),
the averages in the unit mean. The surviving A_u, over squarefree u
dividing q_1, are chi_D(alpha_0) times products that choose b_{p,j}
for p dividing u and a_{p,j} otherwise. Moreover
a_{p,j} + b_{p,j} = Gamma_p(alpha_p) if j = 1, and 0 if j >= 2.
For j = 1 the relation psi_p = 1 + B_p pushes the unit mean forward
to pi_p. For j >= 2 the factor psi_p is supported on allowed regular
arguments modulo p, and a primitive character of conductor p^j
averages to zero over the lifts of a fixed value modulo p, so the
sum of the two averages vanishes.
If q_1 <= H, every squarefree divisor needed in the product
expansion of c already occurs in the sum defining c, so c = c_0;
a nonsquarefree q_1 makes both sides vanish. If q_1 > H, the model
coefficient c_0 is zero. Bound c as follows. The local-sums lemma
gives |a_{p,j}| <= p^{-8 delta j}, while the multiplier bound and
the identity just proved give |b_{p,j}| <= 2 p^{-gamma j}, because
b_{p,j} = -a_{p,j} for j >= 2. Bounding the truncated product
expansion by its full absolute sum,
|c(alpha_0)| <= prod_{p^j || q_1} (|a_{p,j}| + |b_{p,j}|)
<= prod_{p^j || q_1} 3 p^{-gamma j}
<= q_1^{-gamma/2} < H^{-gamma/2},
using p^{gamma/2} >= 3 for p >= P. Together with the two major-arc
identities this gives the major-arc comparison, and the minor-arc
bounds complete the lemma. QED
Proof of pair cancellation. Extend J_1 and J_2 by zero to Z and
put
B_i = (1/N) sum_{x, n in Z} k_i(n) J_1(x) J_2(x + n), i = 0, 1.
With the counting-measure transforms
tilde J_i(alpha) = sum_x J_i(x) e(-alpha x), character
orthogonality gives
B_i = (1/N) int_{R/Z} S_i(alpha) tilde J_1(-alpha) tilde J_2(alpha)
d alpha.
Both counting-measure l^2 norms are at most sqrt N, so
Cauchy-Schwarz, Plancherel and the kernel-comparison lemma give
|B_1 - B_0| << H^{-gamma/2}.
The forbidden-support hypothesis gives B_1 = 0. For every
contributing pair in B_0 the ordering and the two residue classes
force 1 <= n <= N and n congruent to r modulo D. Substituting the
model kernel and setting y = x + n gives
B_0 = (D/N^2) sum_{xi in Xi} Gamma(xi)
sum_{x, y} J_1(x) J_2(y) e(-xi (y - x))
= D sum_{xi in Xi} Gamma(xi) hat J_1(-xi) hat J_2(xi),
which is the display of the proposition. QED
Descent. Pair cancellation and the seminorm combine in a recurrence.
The quantity that decreases is a diagonal tuple integral of a Fourier
lift. Restriction to progressions compares it with the same quantity
at a shorter interval, and avoidance forces a fixed proportion of
residue assignments to cancel, the remaining proportion being paid
for by the exceptional submeasure. The scheme is the recurrence
method of
power-saving-intersective-polynomial-differences.pdf
adapted so that the prime argument survives throughout the auxiliary
family, which is what the transport lemma provides.
The descent quantity. Keep the structural parameters fixed:
M_0, d, t, w, L, delta, gamma, and eta, c_m, nu, beta, zeta, tau,
sigma. At every integer scale N >= 1 use P_N, Q = N^beta and
H = N^{beta/2} as before. For l >= 1 and A contained in [N] put
Upsilon_l(N, A) = Z_{l, P_N}( L_{[N], P_N, Q} 1_A ),
Upsilon_l(N) = max over A contained in [N] avoiding at l
of Upsilon_l(N, A).
The constant Fourier coefficient of the lift, together with the
seminorm lemma, gives
(|A|/N)^d <= Upsilon_l(N, A).
For the upper bound, Holder and the lift-moments proposition give
0 <= Upsilon_l(N) <= N^{o(1)} for every l >= 1,
and no restriction of the form l <= N^zeta enters here.
Averaging over residues modulo M_0. For each s modulo M_0 put
f_s(x) = M_0 1_A(x) 1_{x = s mod M_0},
G_s = L_{[N], P_N, Q} f_s.
Averaging f_s over uniform s gives 1_A, so for independent uniform
residues s_v modulo M_0 indexed by v in V, multilinearity gives
Upsilon_l(N, A) = E_{(s_v)} Z_{l, P_N}((G_{s_v})_{v in V}).
The integrals are bounded in two ways below. The comparison with
shorter intervals holds for every l, while the cancellation step
requires l <= N^zeta.
Residue-specialization lemma. Let N >= 1, let A be contained in [N],
let s be a residue modulo M_0, and let I be a nonempty consecutive
integer interval contained in [N]. Let B be a subset of P_N, write
q_B = prod_{p in B} p, D = M_0 q_B and S = P_N \ B. Fix the
B-coordinates of L_{I, P_N, Q} f_s at b = (b_p)_{p in B}, obtaining
g_I : X_S -> R. Let a' modulo D be the unique residue with a' = s
modulo M_0 and a' = b_p modulo p for p in B. Then every frequency xi
on X_S with q(xi) q_B <= Q satisfies
hat g_I(xi) = (D/|I|) sum_{x in I, x = a' mod D} 1_A(x) e(-x xi).
Proof. The coefficient on the left is the sum of
hat f_s(xi + omega) e(b omega) over the frequencies omega on X_B
that the lift retains. The condition q(xi) q_B <= Q retains every
omega, since q(xi + omega) = q(xi) q(omega) <= Q. Orthogonality of
the q_B characters imposes x = b_p modulo p for every p in B and
contributes the factor q_B. Together with the factor M_0 in f_s this
is the display. QED
Short-interval comparison proposition. For all sufficiently large
N, every l >= 1 and every A contained in [N] avoiding at l, the
following holds. Let B be a subset of P_N with q_B <= N^tau and put
D = M_0 q_B, L_D = lambda(D), n_B = ceil(N/L_D),
Lambda_B = L_D n_B / N, S = P_N \ B.
For each v in V choose s_v modulo M_0 and fix the B-coordinates of
G_{s_v} arbitrarily, obtaining g_v : X_S -> R. Then
| Z_{l, S}((g_v)_{v in V}) |
<= Lambda_B^d Upsilon_{lD}(n_B) + O(N^{-sigma}),
uniformly in these choices, and the new scale and normalization
satisfy
N^{1/2} <= M_0^{-k} N^{1 - k tau} <= n_B < N,
1 <= Lambda_B <= 1 + M_0^k N^{k tau - 1}.
Proof. The scale bounds follow from D <= L_D <= D^k and M_0 >= 2,
and the first inequality holds for large N because k tau < 1/2.
Hence, with Q' = n_B^beta,
H <= Q' <= Q.
By the signed Holder inequality it is enough to prove the displayed
bound for Z_{l,S}(g) with g any one of the specialized inputs.
Step 1, large-denominator truncation. Keep only the frequencies of g
of denominator at most H and call the result g_{<= H}. Telescoping
the diagonal integral one slot at a time, the large-denominator
lemma together with the lift-moments proposition and the
specialization lemma bounds the change by
|Z_{l,S}(g) - Z_{l,S}(g_{<=H})| << H^{-gamma} q_B N^{o(1)}
= O(N^{-sigma}).
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, the product
being q_B. Every frequency selection retains whole exact supports
before specialization, and the saving follows from
beta gamma/2 - tau > sigma.
Step 2, progressions and avoidance. The auxiliary-family identity
transports avoidance along progressions of step L_D = lambda(D).
Since D divides L_D, the prescribed class modulo D splits into its
L_D/D classes modulo L_D. Let a' modulo D be the class determined by
the specialization. For j in [L_D] with j = a' modulo D put
c_j = j - L_D, A'_j = { x' in [n_B] : L_D x' + c_j in A },
H_j = L_{[n_B], S, H} 1_{A'_j}.
Every integer of A in the class a' modulo D has a unique
representation L_D x' + c_j, and the definition excludes surplus
points beyond N.
Each A'_j avoids at lD. A nonzero difference h_{lD}(m') in A' would
give the difference lambda(D) h_{lD}(m') = h_l(D m' - i) in A, with
0 <= i < D supplied by the auxiliary-family lemma. Here D m' - i >= 1
and T_l(D m' - i) = T_{lD}(m'), and the difference is nonzero since
lambda(D) > 0. That would violate avoidance of A at l.
Step 3, exact fiber decomposition. Since q_B H <= Q, the
residue-specialization lemma gives the exact identity
g_{<=H}(z) = (Lambda_B / (L_D/D))
sum_{j in [L_D], j = a' mod D} H_j(L_D^{-1}(z - c_j)).
Every prime divisor of L_D divides D, so multiplication by L_D is
invertible on X_S and preserves Fourier denominators. For
q(xi) <= H the coefficient of the jth summand at xi is
hat H_j(L_D xi) e(-c_j xi); summing over j and multiplying by
Lambda_B/(L_D/D) = D n_B/N gives the residue-specialization identity
with I = [N]. Both sides have zero coefficients at denominators
greater than H.
Step 4, seminorm contraction. There are L_D/D summands, so the
triangle inequality for the seminorm and its identity under scalar
rescaling give
Z_{l,S}(g_{<=H}) <= Lambda_B^d max_j Z_{lD,S}(H_j).
Raise the cutoff in H_j from H to Q'. The same large-denominator
argument, now without specialization, changes the diagonal integral
by O(H^{-gamma} N^{o(1)}) = O(N^{-sigma}). The moment hypothesis
holds at the new scale because n_B >= 10 (Q')^6 for large N, by
6 beta < 1 and the scale bounds.
Step 5, extend and identify. The extended lift is obtained from
L_{[n_B], P_{n_B}, Q'} 1_{A'_j} by averaging out its coordinates in
B intersect P_{n_B} and adding unused coordinates in S \ P_{n_B}.
Averaging contracts the seminorm and adding unused coordinates does
not change it, by the seminorm lemma. Its diagonal integral is
therefore at most Upsilon_{lD}(n_B, A'_j) <= Upsilon_{lD}(n_B).
Combining with Steps 1 and 4 proves the diagonal bound and hence the
proposition. None of these steps restricts the size of l. QED
Cancellation for good residue assignments. The comparison
proposition controls every assignment. A stronger bound holds for
those assignments whose cycle increments can occur as local
polynomial values.
Call (s_v)_{v in V} good at l if every cycle increment
s_{v_{j+1}} - s_{v_j}, for 0 <= j < L, is admissible modulo M_0 at l.
Let rho_l be the proportion of good assignments. The zero-sum
admissible sequences of the cycle lemma give
rho_l >= rho_* := M_0^{1 - L} > 0.
Indeed combine such a sequence at each prime power dividing M_0 by
the Chinese remainder theorem: after prescribing the L increments,
the initial cycle residue and every residue off the cycle are free.
Cancellation proposition. For all sufficiently large N, all
1 <= l <= N^zeta, every A contained in [N] avoiding at l, and every
good assignment (s_v),
| int prod_{v in V} G_{s_v}(z_v)
d(tensor_p (mu_{l,p} - eps_{l,p})) |
<< N^{-sigma},
with an implied constant uniform in l, in A and in the assignment.
Proof. The aim is to leave just the two endpoint lifts on an ordered
cycle edge. First average over short intervals, then truncate and
expand the remaining inputs. Each expansion term uses prime
coordinates of small product, and conditioning on those coordinates
leaves the pair to which pair cancellation applies.
Step 1, short intervals. It suffices to use the probability measures
mu_{l,p}^circ = (mu_{l,p} - eps_{l,p})/(1 - eta_{l,p}),
since restoring the omitted masses multiplies the integral by
prod_p (1 - eta_{l,p}) <= 1. Partition [N] into m = floor(N^tau)
consecutive intervals of lengths as equal as possible. Each G_s is
the weighted average of L_{I, P_N, Q} f_s over these intervals, with
weights |I|/N, so the integral is an average over independently
chosen intervals for all slots. The lengths are comparable to
N^{1 - tau}, so the lift-moments bound applies, because
6 beta + tau < 1. Holder and the uniform marginals bound every
interval assignment by N^{o(1)}.
The probability that all L cycle slots use the same interval is
sum_I (|I|/N)^L = O(N^{-(L-1) tau}), and these assignments
contribute O(N^{-sigma}). For any other assignment the cyclic
sequence of interval indices is nonconstant, hence has a strict
increase along some directed cycle edge. Choose such an edge, with
first endpoint in I_1 and second endpoint in a later interval I_2.
Step 2, truncation and expansion. Keep the two endpoint lifts
unchanged and truncate every other lift to denominators at most
T = N^tau. Telescoping with the large-denominator lemma and the
lift-moments bound costs O(T^{-gamma} N^{o(1)}) = O(N^{-sigma}).
Expand the truncated d - 2 inputs into characters: the coefficients
have modulus at most M_0, each input has O(T^2) frequencies, and the
sum of absolute coefficients in the product expansion is therefore
O(T^{2(d-2)}).
Step 3, fixing one expansion term. Let B be the union of the prime
supports of the chosen characters and put
R = q_B <= T^{d-2}, D = M_0 R, S = P_N \ B.
Condition on the entire tuple of labels at every prime in B, with
any conditioning of 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_S,
and the laws at primes in S are unchanged. By translation
invariance the pair integral equals
sum_{xi on X_S} hat g_1(-xi) hat g_2(xi) Gamma(xi),
where Gamma is the multiplier of this directed cycle edge: only
opposite characters survive common translation, and their product is
the character of the second label minus the first.
By the multiplier bound, Parseval and the specialized moment bound,
the part with q(xi) > H is at most
H^{-gamma} ||g_1||_2 ||g_2||_2 << H^{-gamma} R N^{o(1)}.
For the remaining frequencies q(xi) <= H, one has H R <= Q, and
also D <= N^beta for large N because (d - 2) tau < beta/2. Apply the
residue-specialization lemma to the endpoint lifts, obtaining
classes a'_1, a'_2 modulo 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 in B.
Set
J_i = 1_A 1_{I_i} 1_{x = a'_i mod D}, i = 1, 2,
as functions on [N]. Every contributing pair has x < y, because I_1
precedes I_2, and avoidance gives y - x not in D_l. All hypotheses of
pair cancellation hold.
Its frequency set Xi is exactly the remaining frequencies on X_S of
denominator at most H: coprimality with D excludes the primes below P
and the primes in B, and every prime in a denominator at most H is
at most Q. The coefficient identity becomes
hat g_i(xi) = (D N/|I_i|) hat (J_i)_{[N]}(xi) for q(xi) <= H.
Consequently pair cancellation bounds the low-denominator part of
the pair integral by
O(H^{-gamma/2} D N^2/(|I_1| |I_2|))
= O(H^{-gamma/2} D N^{2 tau}).
Since D = M_0 q_B <= T^{d-2+o(1)}, multiplication by the expansion
bound O(T^{2(d-2)}) makes both the high-denominator and the
low-denominator parts at most
N^{-beta gamma/4 + (3d+2) tau + o(1)} = O(N^{-sigma}),
because beta gamma/4 > (3d + 2) tau + sigma. The estimates are
uniform in the conditioning, in the selected edge and in the
interval assignment. Averaging, and including the truncation and
coincident-interval errors, proves the display. QED
The contracting recurrence. Cancellation holds after removing the
exceptional part of every local law. Returning to the full laws
requires expanding that removal, and the total mass of the resulting
exceptional terms is small enough to pay for their possibly shorter
progression scales. For B contained in P_N put
eta_{l,B} = prod_{p in B} eta_{l,p},
D_B = M_0 q_B, n_B = ceil(N/lambda(D_B)),
so D_empty = M_0. The mass estimate of the tuple laws and the choice
of P give, uniformly in l,
sum_{nonempty B contained in P_N} q_B eta_{l,B}
<= prod_{p >= P} (1 + p^{-3}) - 1 <= 1/4.
Recurrence proposition. There is a constant C_1 such that for every
sufficiently large N and every 1 <= l <= N^zeta,
Upsilon_l(N) <= C_1 N^{-sigma}
+ (1 + u_N) [ (1 - rho_l) Upsilon_{l M_0}(n_empty)
+ rho_l sum_{nonempty B, q_B <= N^tau} eta_{l,B}
Upsilon_{l D_B}(n_B) ],
with
u_N = (1 + M_0^k N^{k tau - 1})^d - 1 = o(1).
Both the constant and the threshold are independent of l.
Proof. Fix an avoiding set A. For assignments in the averaging
display that are not good, apply the short-interval comparison with
B empty; their proportion is 1 - rho_l. For a good assignment the
cancellation proposition handles the product of the measures
mu_{l,p} - eps_{l,p}. The difference from the full product is
tensor_p mu_{l,p} - tensor_p (mu_{l,p} - eps_{l,p})
= sum_{nonempty B} (-1)^{|B|+1}
(tensor_{p in B} eps_{l,p})
tensor (tensor_{p not in B} mu_{l,p}).
The Bth summand has positive mass eta_{l,B} and vanishes when that
mass is zero. Otherwise, after normalization, every one-slot
marginal is uniform by simultaneous translation invariance, so
Holder and the lift-moments proposition bound the integral by
N^{o(1)} in absolute value. The terms with q_B > N^tau have total
mass at most N^{-tau}/4 by the budget estimate, and hence contribute
O(N^{-sigma}).
For q_B <= 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 the
short-interval comparison applies to the specialized inputs. Its
factor Lambda_B^d is at most 1 + u_N by the scale bounds, and its
errors sum to O(N^{-sigma}) by the budget estimate. Taking absolute
upper bounds in the signed expansion and averaging over the good
assignments gives the recurrence. Maximizing over A completes the
proof. QED
Uniform power decay. The recurrence is useful only when l <= N^zeta,
while its successors l D_B need not lie in the analytic range at
the scale n_B. The bound is therefore proved simultaneously for
every auxiliary parameter l, the factor l^{b_0} below covering the
complementary range through the trivial upper bound.
Uniform-decay proposition. There are constants a_0, b_0 > 0 and
C_0 >= 1, depending only on h, such that for all integers l and all
N >= 1,
Upsilon_l(N) <= C_0 l^{b_0} N^{-a_0}.
Proof. After the parameters are fixed, choose a_0 > 0 small enough
and put b_0 = 2 a_0/zeta so that
a_0 < sigma, s_0 := k a_0 + b_0 <= 1,
theta_0 := M_0^{s_0} (1 - 3 rho_*/4) < 1.
This is possible because s_0 tends to 0 as a_0 does, while rho_* > 0
is fixed.
If l > N^zeta, then l^{b_0} N^{-a_0} >= N^{a_0}, and the trivial
upper bound, used with exponent a_0, proves the display in that
range after a fixed enlargement of C_0. This treats every l > N^zeta
before the induction.
Induct on the integer N simultaneously for all l >= 1. At a
sufficiently large N with l <= N^zeta, every successor in the
recurrence satisfies n_B < N by the scale bounds, so the induction
hypothesis is available at l D_B whether or not l D_B <= n_B^zeta.
Since n_B >= N/D_B^k, it gives
Upsilon_{l D_B}(n_B) <= C_0 (l D_B)^{b_0} n_B^{-a_0}
<= C_0 l^{b_0} N^{-a_0} D_B^{s_0}.
With q_B^{s_0} <= q_B and the budget estimate, the bracket in the
recurrence is at most
C_0 l^{b_0} N^{-a_0} M_0^{s_0} (1 - rho_l + rho_l/4)
<= C_0 l^{b_0} N^{-a_0} theta_0,
using rho_l >= rho_*. Choose a fixed threshold N_*, large enough for
the recurrence and such that
C_1 N^{a_0 - sigma} + (1 + u_N) theta_0 <= 1 for N >= N_*;
this exists because theta_0 < 1 and u_N = o(1), and it is
independent of C_0 >= 1. Dividing the recurrence by
C_0 l^{b_0} N^{-a_0} proves the induction step, since
C_0 l^{b_0} >= 1.
Finally enlarge C_0 to cover the range l > N^zeta and every N < N_*,
uniformly in l, using the trivial upper bound. This completes the
induction. QED
Proof of the main theorem. At l = 1, T_1(m) = m and h_1 = h, so the
hypothesis of the theorem is exactly avoidance at l = 1. Combining
the lower bound for Upsilon with the uniform decay,
(|A|/N)^d <= Upsilon_1(N) <= C_0 N^{-a_0},
|A| <= C_0^{1/d} N^{1 - a_0/d}.
Thus c_h = a_0/d and C_h = C_0^{1/d} serve for every N >= 1. Only
strictly ordered pairs, hence positive differences, were used in
cancellation. Restriction to progressions preserved nonzero
forbidden values together with their prime arguments, by the
transport lemma, so a value h(p) = 0 makes no additional demand at
any stage. QED
Closing remarks. On constants. Every constant c_h and C_h depends
only on h: on its degree k, on its coefficients through the p-adic
roots z_p, and on the thresholds P_1, x_* and N_*. The exponents
satisfy
c_h = a_0/d, 1/d = K^{-w}, K = L!, w = 2 t + 1,
a_0 in (0, sigma),
with sigma = gamma tau/4, tau = beta gamma/(1000 k (d+1)),
beta = nu/100, nu = min(eta, c_m/k)/10, eta = 1/(10000 k), and
c_m = c_m(k, eta/4) from the cancellation-over-primes bound. The
saving is extremely small, and only its existence is asserted.
On the prime-argument condition. The unit-root condition at every
prime power enters at three points. First, the p-adic root z_p and
the auxiliary family h_l. Second, the admissible local values and
the zero-sum cycle of length L. Third, the signed kernel supported
on prime arguments of h_l and its local realization through unit
means. If the unit-root condition is dropped at some modulus, all
three break down, since no admissible cycle exists at that modulus,
and the argument gives no control.
On further improvements. The saving is fixed but tiny, and more
careful choices of t, w, L and of the parameter hierarchy can
plausibly produce larger exponents. The skeleton - reflection-
positive tuple laws, Fourier lifts, and a prime-supported kernel -
seems flexible, while optimizing the constants would be a project
in itself. Only the existence of a positive c_h is established here.