OctoInformBeta

OpenAI preprint, September 2026 · §4. Folded Gaussian blocks

Lemma 4.2: Conditional sampling bounds and a controlled line maximum at sufficiently large block dimensions

Usable Gaussian anchors and compatible blocks.

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

A folded Gaussian assigns weights to the vertices of the unit cube after a point has been chosen in that cube. The question is whether a large collection of grid anchors retains a lower sampling bound on a finite abelian group, while taking a maximum along a line keeps the resulting density close to mean one.

The standard Gaussian density on ℝd\mathbb R^d and the folded density at height hh are the functions γd\gamma_d and qq in (1): γd(y)=(2π)−d/2exp⁡(−∥y∥2/2)=∏j=1dγ1(yj),q(h,t)=hγ1(ht)+hγ1(h(t−1)).\begin{aligned} \gamma_d(y)&=(2\pi)^{-d/2}\exp(-\|y\|^2/2) =\prod_{j=1}^d\gamma_1(y_j),\\ q(h,t)&=h\gamma_1(ht)+h\gamma_1(h(t-1)). \end{aligned}(1) The product folded density Q(h,t)Q(h,t) on ℝb\mathbb R^b is the product in (2); the notation FbF_b specifies its height: Q(h,t)=∏j=1bq(h,tj),hb=94log⁡b,Fb(t)=Q(hb,t).Q(h,t)=\prod_{j=1}^b q(h,t_j),\qquad h_b=\sqrt{\tfrac94\log b},\qquad F_b(t)=Q(h_b,t).(2) For positive bb, the height hbh_b uses the natural logarithm. The folded mass M(h)M(h) and the mean log density μ(h)\mu(h) are the integral and weighted average in (3): M(h)=∫01q(h,t)dt,μ(h)=∫01q(h,t)log⁡q(h,t)dtM(h).M(h)=\int_0^1q(h,t)\,dt,\qquad \mu(h)=\frac{\int_0^1q(h,t)\log q(h,t)\,dt}{M(h)}.(3)

For a prime pp, let G=𝔽pbG=\mathbb F_p^b, with all finite averages uniform. The grid anchor tz∈[0,1)bt_z\in[0,1)^b of z∈Gz\in G and its Gaussian anchor weight are (4), where [zj]p∈{0,…,p−1}[z_j]_p\in\{0,\ldots,p-1\} represents zjz_j: (tz)j=[zj]pp,anchor weight at z=Fb(tz).(t_z)_j=\frac{[z_j]_p}{p},\qquad \text{anchor weight at }z=F_b(t_z).(4) The eligible set E(h,μ,D,r;p)⊆GE(h,\mu,D,r;p)\subseteq G is the subset of grid residues selected with height hh, reference mean μ\mu, deviation parameter DD and threshold rr. The eligible block residues EbE_b and the prime window IbI_b are given by (5): Eb=E(hb,μ(hb),b0.56,b0.70;p),Ib=[bμ(hb)−4b0.56,bμ(hb)−3b0.56].\begin{aligned} E_b&=E(h_b,\mu(h_b),b^{0.56},b^{0.70};p),\\ I_b&=[b\mu(h_b)-4b^{0.56},\ b\mu(h_b)-3b^{0.56}]. \end{aligned}(5)

The conditional probability π(h,t,e)\pi(h,t,e) of a Boolean digit e∈{0,1}e\in\{0,1\} and the conditional probability P(h,t,ε)P(h,t,\varepsilon) of a Boolean word ε∈{0,1}b\varepsilon\in\{0,1\}^b are the probabilities defined by (6): π(h,t,e)=hγ1(h(t−e))q(h,t),P(h,t,ε)=∏j=1bπ(h,tj,εj).\pi(h,t,e)=\frac{h\gamma_1(h(t-e))}{q(h,t)},\qquad P(h,t,\varepsilon)=\prod_{j=1}^b\pi(h,t_j,\varepsilon_j).(6) For shifts w1,…,wbw_1,\ldots,w_b in an abelian group HH, the Boolean subset sum WεW_\varepsilon is (7); sums over words count these subset sums with multiplicity: Wε=∑j=1bεjwj.W_\varepsilon=\sum_{j=1}^b\varepsilon_jw_j.(7)✦

For a weight F:G→ℝF:G\to\mathbb R and a subset U⊆GU\subseteq G, the usable mean mass mU(F)m_U(F) and restricted normalized weight sU,Fs_{U,F} are defined by (8): mU(F)=𝔼zF(z)𝟏U(z),sU,F(z)=F(z)p𝟏U(z).m_U(F)=\mathbb E_z F(z)\mathbf1_U(z),\qquad s_{U,F}(z)=\frac{F(z)}p\mathbf1_U(z).(8) A direction vv in GG is a nonzero vector; the line spanned by vv is 𝔽pv\mathbb F_pv. The line maximum LvfL_vf of a function f:G→ℝf:G\to\mathbb R and the Gaussian block function gb,U,vg_{b,U,v} are the functions in (9): Lvf(x)=maxa∈𝔽pf(x−av),gb,U,v=LvsU,Fb∘t.L_vf(x)=\max_{a\in\mathbb F_p}f(x-av),\qquad g_{b,U,v}=L_v s_{U,F_b\circ t}.(9) Here Fb∘tF_b\circ t denotes the anchor weight in (4).

Regular Blocks

A folded Gaussian block B=(bB,pB,hB,UB,vB)B=(b_B,p_B,h_B,U_B,v_B) consists of a natural dimension, a prime modulus, a positive height, a set UB⊆GB=𝔽pBbBU_B\subseteq G_B=\mathbb F_{p_B}^{b_B}, and a nonzero direction vB∈GBv_B\in G_B.✦ For a folded Gaussian block B=(bB,pB,hB,UB,vB)B=(b_B,p_B,h_B,U_B,v_B) and a real parameter AA, the block density gBg_B and loss δA(B)\delta_A(B) are the function and number defined by (10), with tzt_z taken at modulus pBp_B: gB=LvBsUB,Q(hB,t⋅),δA(B)=AbB−0.01.g_B=L_{v_B}s_{U_B,Q(h_B,t_{\cdot})},\qquad \delta_A(B)=A b_B^{-0.01}.(10) An AA-regular Gaussian block BB is a folded Gaussian block satisfying (11), where EbBE_{b_B} uses the modulus pBp_B: hB=hbB,log⁡pB∈IbB,UB⊆EbB,|𝔼xgB(x)−1|≤δA(B),gB(x)≤exp⁡(5bB0.56)(x∈GB).\begin{gathered} h_B=h_{b_B},\qquad \log p_B\in I_{b_B},\qquad U_B\subseteq E_{b_B},\\ |\mathbb E_xg_B(x)-1|\le\delta_A(B),\qquad g_B(x)\le\exp(5b_B^{0.56})\quad(x\in G_B). \end{gathered}(11) The block group of BB is the additive group GB=𝔽pBbBG_B=\mathbb F_{p_B}^{b_B} of vectors over the residue field modulo pBp_B.

The Claim

Theorem 1. There is an absolute constant A>0A>0 with the following property for all sufficiently large integers bb. Let pp be prime with log⁡p∈Ib\log p\in I_b, let HH be a finite abelian group with log⁡|H|≤b4\log|H|\le b^4, and let 1≤a≤b1/0.91\le a\le b^{1/0.9}. Suppose f:H→ℝf:H\to\mathbb R satisfies 0≤f≤exp⁡(5a0.56)0\le f\le\exp(5a^{0.56}) and 1/2≤f¯≤21/2\le\overline f\le2, where f¯=𝔼xf(x)\overline f=\mathbb E_xf(x). There are shifts w1,…,wb∈Hw_1,\ldots,w_b\in H, a subset U⊆EbU\subseteq E_b, and a nonzero v∈Gv\in G with the bounds (12): ∑ε∈{0,1}bP(hb,tz,ε)f(x−Wε)≥(1−Ab−0.01)f¯(z∈U,x∈H),|mU(Fb∘t)−1|≤Ab−0.05,|𝔼xgb,U,v(x)−1|≤Ab−0.01,0≤gb,U,v(x)≤exp⁡(5b0.56)(x∈G).\begin{gathered} \sum_{\varepsilon\in\{0,1\}^b}P(h_b,t_z,\varepsilon) f(x-W_\varepsilon) \ge(1-Ab^{-0.01})\overline f\quad(z\in U,\ x\in H),\\ |m_U(F_b\circ t)-1|\le Ab^{-0.05},\qquad |\mathbb E_xg_{b,U,v}(x)-1|\le Ab^{-0.01},\\ 0\le g_{b,U,v}(x)\le\exp(5b^{0.56})\quad(x\in G). \end{gathered}(12)✦

For any integer b≥1b\ge1 with hb>0h_b>0, prime pp with log⁡p∈Ib\log p\in I_b, and U⊆EbU\subseteq E_b with m=mU(Fb∘t)≤2m=m_U(F_b\circ t)\le2, there is a nonzero direction v∈Gv\in G satisfying (13): m−4mexp⁡(−2b0.56)≤𝔼xgb,U,v(x)≤m,0≤gb,U,v(x)≤exp⁡(5b0.56)(x∈G).\begin{gathered} m-4m\exp(-2b^{0.56})\le\mathbb E_xg_{b,U,v}(x)\le m,\\ 0\le g_{b,U,v}(x)\le\exp(5b^{0.56})\quad(x\in G). \end{gathered}(13)✦

There also exist A>0A>0 and an integer N≥2N\ge2 with the conclusions (14) for every integer b≥Nb\ge N; the compatibility assertion in its last line holds for every AA-regular block PP satisfying N≤bP≤b1/0.9N\le b_P\le b^{1/0.9}: Ab−0.01≤12,μ(hb)≤b,there is an A-regular block B0 with bB0=b,there are an A-regular block B with bB=b and shifts wj∈GP such that∑ε∈{0,1}bBP(hB,tz,ε)gP(x−Wε)≥(1−δA(B))𝔼ygP(y)(z∈UB,x∈GP).\begin{gathered} Ab^{-0.01}\le\tfrac12,\qquad \mu(h_b)\le b,\\ \text{there is an $A$-regular block $B_0$ with }b_{B_0}=b,\\ \begin{aligned} &\text{there are an $A$-regular block $B$ with }b_B=b \text{ and shifts }w_j\in G_P\text{ such that}\\[-2pt] &\sum_{\varepsilon\in\{0,1\}^{b_B}} P(h_B,t_z,\varepsilon)g_P(x-W_\varepsilon) \ge(1-\delta_A(B))\mathbb E_yg_P(y) \quad(z\in U_B,\ x\in G_P). \end{aligned} \end{gathered}(14)✦

In the paper, the result reads: there are absolute A,B>0A,B>0 such that, for every integer b≥Bb\ge B with the preceding block data, every finite abelian group HH with log⁡|H|≤b4\log|H|\le b^4, and every function g0:H→[0,∞)g_0:H\to[0,\infty) with 1/2≤g¯0≤21/2\le\overline g_0\le2 and g0≤exp⁡(5a0.56)g_0\le\exp(5a^{0.56}) for some 1≤a≤b1/0.91\le a\le b^{1/0.9}, one can choose shifts w1,…,wb∈Hw_1,\ldots,w_b\in H, Ub⊆EbU_b\subseteq E_b, and a one-dimensional linear subspace Cb⊆GC_b\subseteq G so that ∑εP(hb,tz,ε)g0(x−Wε)≥(1−Ab−0.01)g¯0\sum_\varepsilon P(h_b,t_z,\varepsilon)g_0(x-W_\varepsilon) \ge(1-Ab^{-0.01})\overline g_0 for every z∈Ubz\in U_b and x∈Hx\in H, and, with vb(z)=p−1Fb(tz)𝟏Ub(z)v_b(z)=p^{-1}F_b(t_z)\mathbf1_{U_b}(z) and gb(x)=max⁡c∈Cbvb(x−c)g_b(x)=\max_{c\in C_b}v_b(x-c), one has |g¯b−1|≤Ab−0.01|\overline g_b-1|\le Ab^{-0.01}, 0≤gb≤exp⁡(5b0.56)0\le g_b\le\exp(5b^{0.56}), and |𝔼zFb(tz)𝟏Ub(z)−1|≤Ab−0.05|\mathbb E_zF_b(t_z)\mathbf1_{U_b}(z)-1|\le Ab^{-0.05}, while in the base version, without HH, g0g_0 or WεW_\varepsilon, one may take Ub=EbU_b=E_b and choose CbC_b with these same conclusions for gbg_b.

What Is Checked

The usable-anchor assertion is stated over nonnegative functions on finite abelian groups with the specified size, mean and height bounds, the line-choice assertion over eligible subsets of prime-field grids with usable mass at most two, and block preparation over regular folded Gaussian blocks with the stated dimension relation.