OctoInformBeta

OpenAI preprint, September 2026 · §6. Conditional averaging in the shared environment · §6

Lemma 6.1 [A uniform affine spectral gap]: Twenty permutations of (ℤ/n)4\{0}(\mathbb{Z}/n)^4\setminus\{0\} times (ℤ/l)4(\mathbb{Z}/l)^4 satisfy a Poincaré inequality whose constant depends on neither the prime nn nor ll

The sampler’s generators have a uniform spectral gap.

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 sampler is a random walk whose steps are permutations drawn from a fixed family of twenty, each acting at once on a nonzero vector of (ℤ/n)4(\mathbb{Z}/n)^4, for a prime nn, and on a vertex of the box (ℤ/l)4(\mathbb{Z}/l)^4, for a positive integer ll: linearly on the first and affinely on the second, with unit translations besides. For the walk that applies a random member of such a family, or its inverse, a spectral gap is a Poincaré inequality, a bound on the variance of every function by a constant times its energy along the generators.

Theorem 1 gives this inequality for the twenty generators on the product of (ℤ/n)4\{0}(\mathbb{Z}/n)^4\setminus\{0\} and (ℤ/l)4(\mathbb{Z}/l)^4 and on the box (ℤ/l)4(\mathbb{Z}/l)^4 alone, with constants that depend on neither nn nor ll, together with an inequality of the same shape on the square (ℤ/n)2(\mathbb{Z}/n)^2 for families of functions moved by shears of amount ±3\pm 3 and by unit translations.

Variance and Energy

The average of a real function over a finite set ss is the sum of its values on ss divided by |s||s|✦; for a function ff on a finite set XX, 𝔼x∈Xf(x)\mathbb{E}_{x\in X} f(x) is its average over all of XX.✦ The variance of a real function ff on a finite set XX is the average of its squared deviation from its average, Var⁡f=𝔼x∈X(f(x)−𝔼Xf)2.\operatorname{Var} f = \mathbb{E}_{x\in X}\bigl(f(x)-\mathbb{E}_{X} f\bigr)^2 .(1)✦

The energy of order kk of a real function ff on XX along a map p:X→Xp\colon X\to X is ℰk(f,p)=𝔼x∈X(f(p(x))−f(x))k\mathcal{E}_k(f,p)=\mathbb{E}_{x\in X}\bigl(f(p(x))-f(x)\bigr)^k.✦ A family of permutations of XX indexed by a finite set JJ is a map π:J→Sym(X)\pi\colon J\to\mathrm{Sym}(X), written j↦πjj\mapsto\pi_j✦, and the total energy of ff along π\pi is ℰπ(f)=∑j∈Jℰ2(f,πj).\mathcal{E}_\pi(f)=\sum_{j\in J}\mathcal{E}_2(f,\pi_j).(2)✦

A family π\pi of permutations of XX expands with constant CC, a real number, if every real function ff on XX satisfies the Poincaré inequality Var⁡f≤Cℰπ(f).\operatorname{Var} f\le C\,\mathcal{E}_\pi(f).(3)✦

Shears of the Square

For a positive integer nn, write Tn=(ℤ/n)2T_n=(\mathbb{Z}/n)^2 for the pairs of residues modulo nn.✦ For d∈ℤ/nd\in\mathbb{Z}/n, the upper shear UdU_d and the lower shear LdL_d are the maps of TnT_n given by Ud(y1,y2)=(y1+dy2,y2),Ld(y1,y2)=(y1,y2+dy1).U_d(y_1,y_2)=(y_1+d\,y_2,\;y_2),\qquad L_d(y_1,y_2)=(y_1,\;y_2+d\,y_1).(4)✦ The lemma uses the four shears of amount ±3\pm 3, S={U3,U−3,L3,L−3}S=\{U_3,U_{-3},L_3,L_{-3}\}, and the axial unit vectors e1=(1,0)e_1=(1,0) and e2=(0,1)e_2=(0,1).✦ The threshold τ\tau and the gap constant C0C_0 of the lemma are the real numbers τ=2(1−cos⁡π8),C0=6+4τ.\tau=2\Bigl(1-\cos\frac{\pi}{8}\Bigr),\qquad C_0=6+\frac{4}{\tau}.(5)

Let II be a finite nonempty set. The mean square of a family G=(Gi)i∈IG=(G_i)_{i\in I} of real functions on TnT_n is M(G)=𝔼i∈I𝔼x∈TnGi(x)2\mathrm{M}(G)=\mathbb{E}_{i\in I}\,\mathbb{E}_{x\in T_n}G_i(x)^2.✦ The change of a family F=(Fi)i∈IF=(F_i)_{i\in I} under a shear s∈Ss\in S along a permutation uu of II is the family Δs,uF\Delta_{s,u}F, and its shifted difference along an axial vector ee is the family ∂eF\partial_e F, where (Δs,uF)i(x)=Fu(i)(sx)−Fi(x),(∂eF)i(x)=Fi(x+e)−Fi(x).(\Delta_{s,u}F)_i(x)=F_{u(i)}(s\,x)-F_i(x),\qquad (\partial_e F)_i(x)=F_i(x+e)-F_i(x).(6)

The Twenty Generators

Write Vn=Tn×Tn=(ℤ/n)4V_n=T_n\times T_n=(\mathbb{Z}/n)^4, a point being a pair (y,z)(y,z) of blocks in TnT_n.✦ A command is one of ten symbols: a shear s∈Ss\in S, an axial vector e∈{e1,e2}e\in\{e_1,e_2\}, or a cross pair (i,j)∈{1,2}2(i,j)\in\{1,2\}^2.✦ A generator is a pair g=(b,k)g=(b,k) of a face bit b∈{0,1}b\in\{0,1\} and a command kk, twenty in all.✦

The affine lead action of a command kk at a block z=(z1,z2)∈Tnz=(z_1,z_2)\in T_n is the permutation λk(z)\lambda_k(z) of TnT_n given by λs(z)y=sy,λe(z)y=y+e,λ(i,j)(z)y=y+zjei,\lambda_s(z)\,y=s\,y,\qquad \lambda_e(z)\,y=y+e,\qquad \lambda_{(i,j)}(z)\,y=y+z_j\,e_i,(7)✦ The linear lead action of a command kk at a block z∈Tnz\in T_n is the permutation of TnT_n that agrees with λk(z)\lambda_k(z), except that each axial command ee acts as the identity.

The lead permutation of a command kk is the permutation Λk(y,z)=(λk(z)y,z)\Lambda_k(y,z)=(\lambda_k(z)\,y,\;z) of VnV_n.✦ The face swap ϕ1(y,z)=(z,y)\phi_1(y,z)=(z,y) exchanges the blocks, and ϕ0\phi_0 is the identity.✦ A generator g=(b,k)g=(b,k) acts on VnV_n by ρg=ϕb∘Λk∘ϕb,\rho_g=\phi_b\circ\Lambda_k\circ\phi_b,(8)✦ The linear action ρglin\rho^{\mathrm{lin}}_g of a generator gg is ρg\rho_g with Λk\Lambda_k built from the linear lead action, and the affine action ρgaff\rho^{\mathrm{aff}}_g of gg is ρg\rho_g with Λk\Lambda_k built from the affine lead action.

For a set with a zero element, the punctured set is the subset of its elements different from zero.✦ For a prime nn, the punctured frame Vn×V_n^{\times} is the punctured set of VnV_n✦, and the frame permutation of a generator gg is the restriction of ρglin\rho^{\mathrm{lin}}_g to Vn×V_n^{\times}.✦ For a prime nn and a positive integer ll, the slice is Ωn,l=Vn××Vl\Omega_{n,l}=V_n^{\times}\times V_l, with Vl=(ℤ/l)4V_l=(\mathbb{Z}/l)^4 the box, and the slice generators are the family γ=(γg)\gamma=(\gamma_g) of twenty permutations of Ωn,l\Omega_{n,l} that move a frame vector by the frame permutation and a vertex of the box by the affine action of the same generator: γg(x,v)=(ρglinx,ρgaffv).\gamma_g(x,v)=\bigl(\rho^{\mathrm{lin}}_g\,x,\;\rho^{\mathrm{aff}}_g\,v\bigr).(9)✦

The Claim

Theorem 1 (A uniform affine spectral gap). Let C0C_0 be the gap constant (5).

(i) For a positive integer nn, a finite nonempty set II, a family F=(Fi)i∈IF=(F_i)_{i\in I} of real functions on (ℤ/n)2(\mathbb{Z}/n)^2, and a permutation usu_s of II for each shear s∈Ss\in S, 𝔼i∈IVar⁡Fi≤C0(∑s∈SM(Δs,usF)+∑e∈{e1,e2}M(∂eF)).\mathbb{E}_{i\in I}\operatorname{Var}F_i\le C_0\Bigl(\sum_{s\in S}\mathrm{M}(\Delta_{s,u_s}F) +\sum_{e\in\{e_1,e_2\}}\mathrm{M}(\partial_e F)\Bigr).(10)✦

(ii) For a prime nn and a positive integer ll, the twenty slice generators expand with constant 10C010\,C_0: every real function ff on Ωn,l\Omega_{n,l} satisfies Var⁡f≤10C0ℰγ(f).\operatorname{Var}f\le 10\,C_0\,\mathcal{E}_\gamma(f).(11)✦

(iii) For a positive integer ll, the twenty generators in the affine action on the box VlV_l expand with constant C0C_0: every real function ff on VlV_l satisfies Var⁡f≤C0ℰρaff(f).\operatorname{Var}f\le C_0\,\mathcal{E}_{\rho^{\mathrm{aff}}}(f).(12)✦

In the paper, the result reads: for the group GH=SLH(ℤ)⋉ℤHG_H=\mathrm{SL}_H(\mathbb{Z})\ltimes\mathbb{Z}^H with a fixed H≥3H\ge 3, there are a fixed finite symmetric generating multiset and a lazy rational random walk on it whose action on every finite transitive GHG_H-set has spectral gap bounded below by a positive constant depending only on HH.

What Is Checked

The claim is stated over the average, the variance and the total energy of real functions on finite sets, the Poincaré inequality with a constant, the gap constant C0C_0 built from the threshold τ\tau, the shears of amount ±3\pm 3 and the axial unit vectors of (ℤ/n)2(\mathbb{Z}/n)^2 with the mean squares of the changes and shifted differences they define, and the twenty generators, acting linearly on the punctured frame Vn×V_n^{\times} and affinely on the box VlV_l.

About these constructions the library proves that the shear by −d-d undoes the shear by dd, U−d∘Ud=L−d∘Ld=idU_{-d}\circ U_d=L_{-d}\circ L_d=\mathrm{id}✦, so that each shear is a permutation of (ℤ/n)2(\mathbb{Z}/n)^2.✦