OctoInformBeta

OpenAI preprint, September 2026 · Section 5. Uniform moment bounds for Fourier lifts

Lemma 5.2: Explicit support bounds and uniform subpower estimates for real lifts

Even moments of partial Fourier lifts.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The even moments of a partial Fourier lift measure its size when whole exact supports are retained. Let JJ be a finite coordinate set and let p=(pj)j∈Jp=(p_j)_{j\in J} be a family of nonzero natural moduli. The product residue space RpR_p is the product of the residue rings of these moduli, equipped with uniform probability averaging as in (1). Rp=∏j∈Jℤ/pjℤ,𝔼z∈Rpg(z)=1|Rp|∑z∈Rpg(z).R_p=\prod_{j\in J}\mathbb Z/p_j\mathbb Z, \qquad \mathbb E_{z\in R_p}g(z)=\frac{1}{|R_p|}\sum_{z\in R_p}g(z).(1)

For a nonzero natural modulus qq and a support U⊆JU\subseteq J, the centered residue delta dqd_q on ℤ/qℤ\mathbb Z/q\mathbb Z and the centered residue product ΓU\Gamma_U on RpR_p are the real functions defined by (2). dq(a)=q𝟏{a=0}−1,ΓU(z)=∏j∈Udpj(zj).d_q(a)=q\mathbf 1_{\{a=0\}}-1, \qquad \Gamma_U(z)=\prod_{j\in U}d_{p_j}(z_j).(2)

For a positive integer LL, a real function ff on the natural numbers and a support U⊆JU\subseteq J, the residue lift component ℒUf\mathcal L_Uf is the real function on RpR_p given by the normalized counting sum in (3); for a family ℱ\mathcal F of complete supports, the partial Fourier lift ℒℱf\mathcal L^{\mathcal F}f is the real function on RpR_p given by the sum of those components in (3). ℒUf(z)=1L∑n=0L−1f(n)ΓU(z−(nmod⁡pj)j∈J),ℒℱf(z)=∑U∈ℱℒUf(z).\mathcal L_Uf(z) =\frac{1}{L}\sum_{n=0}^{L-1}f(n) \Gamma_U\bigl(z-(n\bmod p_j)_{j\in J}\bigr), \qquad \mathcal L^{\mathcal F}f(z)=\sum_{U\in\mathcal F}\mathcal L_Uf(z).(3) The natural range {0,…,L−1}\{0,\ldots,L-1\} corresponds to the public integer interval {1,…,L}\{1,\ldots,L\} by sending the index nn to n+1n+1.

The conductor qUq_U of a support U⊆JU\subseteq J is the product of its moduli. For a natural cutoff QQ, the conductor-bounded support family 𝒮Q\mathcal S_Q consists of all supports whose conductor is at most QQ, as in (4). qU=∏j∈Upj,𝒮Q={U⊆J:qU≤Q}.q_U=\prod_{j\in U}p_j, \qquad \mathcal S_Q=\{U\subseteq J:q_U\le Q\}.(4)

The lift size conditions on natural lengths LL and cutoffs QQ are those in (5). L>0,Q>0,2Q≤L,Q5≤L.L>0,\qquad Q>0,\qquad 2Q\le L,\qquad Q^5\le L.(5)✦

A permutation word vv of height hh on a block set BB is a function assigning each block of BB a permutation of {0,…,h−1}\{0,\ldots,h-1\}.✦ The set 𝒱\mathcal V of permutation tuple vertices is the set of permutation words on the block set {0,…,b−1}\{0,\ldots,b-1\} for the block cutoff T=80T=80, height h=24h=24 and block count b=2T+1=161b=2T+1=161, specified in (6). T=80,h=24,b=2T+1=161,𝒱={v:{0,…,b−1}→Sym⁡({0,…,h−1})}.T=80,\qquad h=24,\qquad b=2T+1=161, \qquad \mathcal V=\{v:\{0,\ldots,b-1\}\longrightarrow \operatorname{Sym}(\{0,\ldots,h-1\})\}.(6)✦

The Claim

Theorem 1. Let the moduli pjp_j be pairwise coprime, let L,QL,Q satisfy (5), and let ℱ⊆𝒮Q\mathcal F\subseteq\mathcal S_Q. Suppose that M≥0M\ge0, that |f(n)|≤M|f(n)|\le M for 0≤n<L0\le n<L, and that every support in ℱ\mathcal F has size at most a natural number kk. For every integer r≥1r\ge1, the partial Fourier lift satisfies (7). 𝔼z∈Rp(ℒℱf(z))2r≤((4⋅22r)k)r(4M25rk)r.\mathbb E_{z\in R_p}\bigl(\mathcal L^{\mathcal F}f(z)\bigr)^{2r} \le \bigl((4\cdot2^{2r})^k\bigr)^r \bigl(4M^2 5^{rk}\bigr)^r.(7)✦ If the modulus family is injective, then for each integer r≥1r\ge1 and each ε>0\varepsilon>0 there is a constant C>0C>0, independent of ℱ,Q,L,f,M\mathcal F,Q,L,f,M, such that the subpower moment estimate (8) holds for all the preceding choices: 𝔼z∈Rp(ℒℱf(z))2r≤(CMQε)2r.\mathbb E_{z\in R_p}\bigl(\mathcal L^{\mathcal F}f(z)\bigr)^{2r} \le \bigl(CM Q^{\varepsilon}\bigr)^{2r}.(8)✦ For pairwise coprime moduli pjp_j, L,QL,Q satisfying (5), ℱ⊆𝒮Q\mathcal F\subseteq\mathcal S_Q, M≥0M\ge0, |f(n)|≤M|f(n)|\le M for 0≤n<L0\le n<L, and every support in ℱ\mathcal F of size at most a natural number kk, the partial Fourier lift satisfies (9) for every integer r≥1r\ge1. 𝔼z∈Rp(ℒℱf(z))2r≤((4⋅22r)k)r(4M25rk)r.\mathbb E_{z\in R_p}\bigl(\mathcal L^{\mathcal F}f(z)\bigr)^{2r} \le \bigl((4\cdot2^{2r})^k\bigr)^r \bigl(4M^2 5^{rk}\bigr)^r.(9)✦ Let pp be an injective prime family on a finite coordinate set JJ, let L,QL,Q satisfy (5), and let NN be a natural number with Q≤NQ\le N. Suppose that M≥0M\ge0, that |f(n)|≤M|f(n)|\le M for 0≤n<L0\le n<L, and that ℱ⊆𝒮Q\mathcal F\subseteq\mathcal S_Q, and take either r=1r=1 or r+1=|𝒱|r+1=|\mathcal V|. For each ε>0\varepsilon>0, the partial Fourier lift satisfies (10) with a constant C>0C>0 uniform over all these choices. 𝔼z∈Rp(ℒℱf(z))2r≤(CMNε)2r.\mathbb E_{z\in R_p}\bigl(\mathcal L^{\mathcal F}f(z)\bigr)^{2r} \le \bigl(CM N^{\varepsilon}\bigr)^{2r}.(10)✦

In the paper, the result reads: for a finite prime family pp, Q≥1Q\ge1, an interval II of length L≥10Q6L\ge10Q^6 and ∥f∥∞≤M\|f\|_\infty\le M, every ℱ⊆𝒮Q\mathcal F\subseteq\mathcal S_Q and every integer r≥1r\ge1 satisfy (11), where the norm uses uniform probability on RpR_p, kQ=maxU∈𝒮Q|U|,K2r=((2r)!2rr!)1/(2r),Ar=2eK2r2(r+3)/4,∥ℒℱf∥2r≤2M(kQ+1)ArkQ,\begin{gathered} k_Q=\max_{U\in\mathcal S_Q}|U|, \qquad K_{2r}=\left(\frac{(2r)!}{2^r r!}\right)^{1/(2r)}, \qquad A_r=2eK_{2r}2^{(r+3)/4},\\ \|\mathcal L^{\mathcal F}f\|_{2r} \le2M(k_Q+1)A_r^{k_Q}, \end{gathered}(11) and consequently, for fixed rr, this is at most MQor(1)MQ^{o_r(1)} as Q→∞Q\to\infty, uniformly in all the data.

What Is Checked

The component estimates (7) concern real residue lift components on pairwise coprime modulus families under (5), with injectivity added for (8), while (10) ranges over all finite injective prime families and the two moment orders specified by the permutation tuple vertices.