OctoInformBeta

OpenAI preprint, September 2026 ยท Section 7. Comparison along square-step progressions

Lemma 7.1: For modulus MM, frozen modulus product qBq_B and interval length LL, the lift gives normalization MqB/LMq_B/L

Low-denominator coefficients after freezing residues.

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

Fix residues on some coordinates of a product of residue rings. The question is how Fourier coefficients on the remaining coordinates record the original interval and its congruence conditions.

Let JJ be finite, with nonzero integer moduli pjp_j, and let BโІJB\subseteq J be the frozen coordinates. Write ๐’ฎ=J\B\mathcal S=J\setminus B and qB=โˆjโˆˆBpjq_B=\prod_{j\in B}p_j. For UโІJU\subseteq J, the product residue space XUX_U, its product additive characters indexed by ฮทโˆˆXU\eta\in X_U, and the residue vector ๐’U\mathbf n_U of an integer nn are given by (1), where em(t)=exp⁡(2ฯ€it/m)e_m(t)=\exp(2\pi i t/m); the unfrozen moduli are the restriction of the family p=(pj)jโˆˆJp=(p_j)_{j\in J} to ๐’ฎ\mathcal S. XU=โˆjโˆˆUโ„ค/pjโ„ค,ฯ‡ฮท(x)=โˆjโˆˆUepj(ฮทjxj),๐’U=(nmod⁡pj)jโˆˆU.X_U=\prod_{j\in U}\mathbb Z/p_j\mathbb Z, \qquad \chi_\eta(x)=\prod_{j\in U}e_{p_j}(\eta_jx_j), \qquad \mathbf n_U=(n\bmod p_j)_{j\in U}.(1) The support supp⁡(ฮท)\operatorname{supp}(\eta) of a character index ฮทโˆˆXU\eta\in X_U is the set of its nonzero coordinates. For a nonnegative conductor cutoff QQ, the support denominator dU(ฮท)d_U(\eta) of ฮทโˆˆXU\eta\in X_U and the family ๐’ฐQ\mathcal U_Q of coordinate sets are given by (2). supp⁡(ฮท)={jโˆˆU:ฮทjโ‰ 0},dU(ฮท)=โˆjโˆˆsupp⁡(ฮท)pj,๐’ฐQ={VโІJ:โˆjโˆˆVpjโ‰คQ}.\operatorname{supp}(\eta)=\{j\in U:\eta_j\ne0\}, \qquad d_U(\eta)=\prod_{j\in\operatorname{supp}(\eta)}p_j, \qquad \mathcal U_Q=\left\{V\subseteq J:\prod_{j\in V}p_j\le Q\right\}.(2) The conductor-bounded supports ๐’ฐQ\mathcal U_Q are the coordinate sets VโІJV\subseteq J for which the product of the moduli pjp_j over jโˆˆVj\in V is at most QQ.

For a nonnegative integer NN, the natural range [0,N)={0,โ€ฆ,Nโˆ’1}[0,N)=\{0,\ldots,N-1\} is carried to the public integer interval [N]={1,โ€ฆ,N}[N]=\{1,\ldots,N\} by nโ†ฆn+1n\mapsto n+1. The indicator 1A:โ„•โ†’โ„1_A:\mathbb N\to\mathbb R of a finite set AโІโ„•A\subseteq\mathbb N is one on AA and zero elsewhere.โœฆ Fix a nonnegative modulus MM, a residue sโˆˆโ„ค/Mโ„คs\in\mathbb Z/M\mathbb Z, and a natural interval I=[c,c+L)I=[c,c+L). The normalized residue slice fs:โ„•โ†’โ„f_s:\mathbb N\to\mathbb R and its interval restriction u:โ„•โ†’โ„u:\mathbb N\to\mathbb R are the real sequences given by (3). fs(n)=M1A(n)1{nโ‰กs(mod⁡M)},u(n)=1I(n)fs(n).f_s(n)=M1_A(n)1_{\{n\equiv s\pmod M\}}, \qquad u(n)=1_I(n)f_s(n).(3) For zโˆˆXJz\in X_J, the selected residue indicator h:โ„•โ†’โ„h:\mathbb N\to\mathbb R is the indicator of the set in (4). h(n)=1{nโˆˆAโˆฉI,nโ‰กs(mod⁡M),nโ‰กzj(mod⁡pj)for every jโˆˆB}.h(n)=1_{\{n\in A\cap I,\ n\equiv s\pmod M,\ n\equiv z_j\pmod{p_j}\ \text{for every }j\in B\}}.(4)โœฆ

Residue Kernels and Interval Lifts

For a residue modulus mm, the centered residue delta ฮบm\kappa_m on โ„ค/mโ„ค\mathbb Z/m\mathbb Z is the real function equal to mโˆ’1m-1 at zero and โˆ’1-1 elsewhere.โœฆ The centered residue product KVK_V, for VโІJV\subseteq J, is the real function on XJX_J given by the product of the centered residue deltas ฮบpj\kappa_{p_j} over jโˆˆVj\in V, as in (5).โœฆ ฮบm(y)=m1{y=0}โˆ’1,KV(y)=โˆjโˆˆVฮบpj(yj).\kappa_m(y)=m1_{\{y=0\}}-1, \qquad K_V(y)=\prod_{j\in V}\kappa_{p_j}(y_j).(5) For a real sequence ff and a coordinate set VโІJV\subseteq J, the interval lift component Pc,L,VfP_{c,L,V}f and interval lift โ„’c,L,Qf\mathcal L_{c,L,Q}f are the real functions on XJX_J given by (6). Pc,L,Vf(x)=1Lโˆ‘t=0Lโˆ’1f(c+t)KV(xโˆ’๐’„+๐’•J),โ„’c,L,Qf(x)=โˆ‘Vโˆˆ๐’ฐQPc,L,Vf(x).\begin{aligned} P_{c,L,V}f(x) &=\frac1L\sum_{t=0}^{L-1}f(c+t)K_V(x-\mathbf{c+t}_J),\\ \mathcal L_{c,L,Q}f(x) &=\sum_{V\in\mathcal U_Q}P_{c,L,V}f(x). \end{aligned}(6) Normalized sums with denominator zero are taken to be zero.

The outside coordinate assembly zโŠ•BxโˆˆXJz\oplus_Bx\in X_J fixes zz on BB and uses xโˆˆX๐’ฎx\in X_{\mathcal S} elsewhere.โœฆ The residue-gated sequence GB,zvG_{B,z}v retains terms of a real sequence vv with the prescribed residues on BB, with normalization qBq_B; both constructions are given in (7).โœฆ (zโŠ•Bx)j={zj,jโˆˆB,xj,jโˆˆ๐’ฎ,GB,zv(n)=qBv(n)1{nโ‰กzj(mod⁡pj)for every jโˆˆB}.(z\oplus_Bx)_j= \begin{cases}z_j,&j\in B,\\x_j,&j\in\mathcal S,\end{cases} \qquad G_{B,z}v(n)=q_Bv(n)1_{\{n\equiv z_j\pmod{p_j}\ \text{for every }j\in B\}}.(7) The frozen interval lift g:X๐’ฎโ†’โ„g:X_{\mathcal S}\to\mathbb R is defined in (8). g(x)=โ„’c,L,Qfs(zโŠ•Bx).g(x)=\mathcal L_{c,L,Q}f_s(z\oplus_Bx).(8)

For a complex function FF on XUX_U and a frequency ฮทโˆˆXU\eta\in X_U, the residue Fourier coefficient Fห†(ฮท)\widehat F(\eta) is the uniform probability average in (9). Fห†(ฮท)=๐”ผxโˆˆXUF(x)ฯ‡ฮท(x)ยฏ.\widehat F(\eta)=\mathbb E_{x\in X_U}F(x)\overline{\chi_\eta(x)}.(9)โœฆ Let ฮฉ\Omega be finite, let FF be a complex function on ฮฉ\Omega, and let ฮฝ:ฮฉโ†’โ„•\nu:\Omega\to\mathbb N. The sequence residue Fourier coefficient โ„›N,ฮฝF(ฮพ)\mathcal R_{N,\nu}F(\xi) at a frequency ฮพโˆˆX๐’ฎ\xi\in X_{\mathcal S} is the normalized counting sum in (10). For a positive integer qq, write rep⁡q\operatorname{rep}_q for the representative in [0,q)[0,q) of a residue modulo qq, and use the abbreviation in the same display. โ„›N,ฮฝF(ฮพ)=1Nโˆ‘yโˆˆฮฉF(y)ฯ‡ฮพ(๐‚(๐’š)๐’ฎ)ยฏ,RN,qh=โ„›N,rep⁡q(hโˆ˜rep⁡q).\mathcal R_{N,\nu}F(\xi) =\frac1N\sum_{y\in\Omega}F(y) \overline{\chi_\xi(\boldsymbol{\nu(y)}_{\mathcal S})}, \qquad R_{N,q}h=\mathcal R_{N,\operatorname{rep}_q} (h\circ\operatorname{rep}_q).(10)โœฆ The initial interval Fourier coefficient CN(v,ฮพ)C_N(v,\xi) of a real sequence vv is (11). CN(v,ฮพ)=1Nโˆ‘n=0Nโˆ’1v(n)ฯ‡ฮพ(๐’๐’ฎ)ยฏ.C_N(v,\xi)=\frac1N\sum_{n=0}^{N-1}v(n) \overline{\chi_\xi(\mathbf n_{\mathcal S})}.(11)โœฆ

The Claim

Theorem 1. Let M,c,L,N,Q,HM,c,L,N,Q,H be nonnegative integers, let AโІโ„•A\subseteq\mathbb N be finite, and let sโˆˆโ„ค/Mโ„คs\in\mathbb Z/M\mathbb Z, BโІJB\subseteq J, and zโˆˆXJz\in X_J. With uu and hh from (3) and (4), the gate identity (12) holds for every nโˆˆโ„•n\in\mathbb N: GB,zu(n)=MqBh(n).G_{B,z}u(n)=Mq_Bh(n).(12)โœฆ If AโІ[0,N)A\subseteq[0,N) and qโ‰ฅNq\ge N is positive, then for every ฮพโˆˆX๐’ฎ\xi\in X_{\mathcal S} the two sequence coefficients agree as in (13): CN(h,ฮพ)=RN,qh(ฮพ).C_N(h,\xi)=R_{N,q}h(\xi).(13)โœฆ If also N>0N>0, HqBโ‰คQHq_B\le Q, and d๐’ฎ(ฮพ)โ‰คHd_{\mathcal S}(\xi)\le H, then the Fourier coefficient of the frozen lift (8) is given by (14): gห†(ฮพ)=NLMqBRN,qh(ฮพ).\widehat g(\xi)=\frac NL\,Mq_B\,R_{N,q}h(\xi).(14)โœฆ

In the paper, the result reads: for Nโ‰ฅ1N\ge1, ApubโІ[N]A_{\mathrm{pub}}\subseteq[N], a residue modulus M0M_0, fs=M01Apub1{nโ‰กs(mod⁡M0)}f_s=M_0 1_{A_{\mathrm{pub}}}1_{\{n\equiv s\pmod{M_0}\}}, a nonempty interval IโІ[N]I\subseteq[N], a subset BโІ๐’ซNB\subseteq\mathcal P_N of the ambient prime family ๐’ซN\mathcal P_N, qB=โˆpโˆˆBpq_B=\prod_{p\in B}p, ๐’ฎ=๐’ซN\B\mathcal S=\mathcal P_N\setminus B, D=M0qBD=M_0q_B, and fixed residues s(mod⁡M0)s\pmod{M_0} and zBโˆˆXBz_B\in X_B with combined class a(mod⁡D)a\pmod D, the function gI=(โ„’I,๐’ซN,Qfs)(zB,โ‹…)g_I=(\mathcal L_{I,\mathcal P_N,Q}f_s)(z_B,\cdot) satisfies gห†I(ฮพ)=D|I|โˆ’1โˆ‘nโˆˆI,nโ‰กa(mod⁡D)1Apub(n)ฯ‡ฮพ(๐’๐’ฎ)ยฏ\widehat g_I(\xi)=D|I|^{-1}\sum_{n\in I,\ n\equiv a\pmod D} 1_{A_{\mathrm{pub}}}(n)\overline{\chi_\xi(\mathbf n_{\mathcal S})} for every character ฮพ\xi on X๐’ฎX_{\mathcal S} with d๐’ฎ(ฮพ)qBโ‰คQd_{\mathcal S}(\xi)q_B\le Q, including B=โŒ€B=\varnothing.

What Is Checked

The statement is over finite products of nonzero residue moduli, arbitrary frozen coordinate sets, and natural intervals, with the selected set contained in [0,N)[0,N) and an auxiliary positive cyclic modulus qโ‰ฅNq\ge N for the coefficient identities, and with N>0N>0 and the stated conductor bounds for the outside coefficient formula.