OctoInformBeta

OpenAI preprint, September 2026 · Section 3. Sparse assignments from nonamenability

Proposition 3.2: A contracting average controls the row and column loads for every positive word length

Convolution bounds yield sparse endpoint assignments.

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

Let GG be a discrete group and let s:I→Gs:I\to G be a family indexed by a finite set II. Each pair (x,i)∈G×I(x,i)\in G\times I labels an edge from the row vertex xx to the column vertex xs(i)xs(i). Assigning each edge to one of its endpoints asks how many assigned edges must meet a single vertex. The operator associated with the family acts on the complex Hilbert space ℓ2(G)\ell^2(G) of square-summable complex functions on GG.

For a bijection e:G→Ge:G\to G, the coordinate permutation PeP_e on ℓ2(G)\ell^2(G) is the complex-linear map defined by (1). (Peξ)(x)=ξ(e(x)).(P_e\xi)(x)=\xi(e(x)).(1)✦ The right regular representation RR is the homomorphism from GG into the bounded complex-linear operators on ℓ2(G)\ell^2(G) given by (2); for t∈Gt\in G, the operator RtR_t is the coordinate permutation associated with right multiplication by tt. (Rtξ)(x)=ξ(xt).(R_t\xi)(x)=\xi(xt).(2) A convolution operator AA for the family ss is a bounded complex-linear operator on ℓ2(G)\ell^2(G) satisfying (3). (Aξ)(x)=∑i∈Iξ(xs(i))(ξ∈ℓ2(G),x∈G).(A\xi)(x)=\sum_{i\in I}\xi(xs(i)) \qquad (\xi\in\ell^2(G),\ x\in G).(3)

An endpoint mask aa for a family s:I→Gs:I\to G is a function a:G×I→{0,1}a:G\times I\to\{0,1\}, where 11 assigns an edge to its row and 00 assigns it to its column. For an endpoint mask a:G×I→{0,1}a:G\times I\to\{0,1\} for s:I→Gs:I\to G and vertices x,y∈Gx,y\in G, the row one set ℛa(x)\mathcal R_a(x) and column zero set 𝒞a,s(y)\mathcal C_{a,s}(y) are the subsets of II defined in (4). ℛa(x)={i∈I:a(x,i)=1},𝒞a,s(y)={i∈I:a(ys(i)−1,i)=0}.\mathcal R_a(x)=\{i\in I:a(x,i)=1\},\qquad \mathcal C_{a,s}(y)=\{i\in I:a(ys(i)^{-1},i)=0\}.(4)

For a nonnegative integer ℓ\ell, the set of words 𝒲ℓ(I)=Iℓ\mathcal W_\ell(I)=I^\ell on the finite alphabet II consists of ordered sequences of length ℓ\ell, with a single empty word at length zero.✦ For a word w=(i1,…,iℓ)w=(i_1,\ldots,i_\ell), its product ps(w)∈Gp_s(w)\in G is defined by (5). Distinct words retain their labels when their products coincide. ps(i1,…,iℓ)=s(i1)⋯s(iℓ),ps(⌀)=1.p_s(i_1,\ldots,i_\ell)=s(i_1)\cdots s(i_\ell),\qquad p_s(\varnothing)=1.(5)✦

For g∈Gg\in G, the left translation LgL_g on the space ℓ∞(G)\ell^\infty(G) of bounded complex functions on GG is the operator defined by (6). Lgf(x)=f(g−1x).L_gf(x)=f(g^{-1}x).(6) The group GG is amenable if there is a complex-linear functional m:ℓ∞(G)→ℂm:\ell^\infty(G)\to\mathbb C satisfying (7); the condition f≥0f\geq0 means that every value of ff is real and nonnegative. m(1)=1,m(f)≥0(f≥0),m(Lgf)=m(f)(g∈G,f∈ℓ∞(G)).m(1)=1,\qquad m(f)\geq0\ \ (f\geq0),\qquad m(L_gf)=m(f)\ \ (g\in G,\ f\in\ell^\infty(G)).(7)✦

For a set of edges EE with row map u:E→Vu:E\to V and column map v:E→Wv:E\to W, and for r∈ℕ0r\in\mathbb N_0, an endpoint slot is a pair consisting of a row or column vertex and one of rr places at that vertex. For r∈ℕ0r\in\mathbb N_0, put Jr={1,…,r}J_r=\{1,\ldots,r\}. The set Σr(e)\Sigma_r(e) of slots available to an edge ee is the finite subset in (8) of the disjoint union (V×Jr)⊔(W×Jr)(V\times J_r)\sqcup(W\times J_r). Σr(e)=({u(e)}×Jr)⊔({v(e)}×Jr).\Sigma_r(e)= \bigl(\{u(e)\}\times J_r\bigr)\sqcup \bigl(\{v(e)\}\times J_r\bigr).(8)✦

The Claim

Theorem 1. Let u:E→Vu:E\to V and v:E→Wv:E\to W be endpoint maps, and let r∈ℕ0r\in\mathbb N_0. Suppose every finite set F⊆EF\subseteq E satisfies |F|≤r(|u(F)|+|v(F)|)|F|\leq r\bigl(|u(F)|+|v(F)|\bigr). There is an injective endpoint assignment as in (9). f:E→(V×Jr)⊔(W×Jr),f injective,f(e)∈Σr(e)(e∈E).\begin{gathered} f:E\longrightarrow(V\times J_r)\sqcup(W\times J_r),\qquad f\text{ injective},\\ f(e)\in\Sigma_r(e)\qquad(e\in E). \end{gathered}(9)✦

Let s:I→Gs:I\to G be a finite labelled family, and let AA be its convolution operator from (3). If ∥A∥≤r\|A\|\leq r for r∈ℕ0r\in\mathbb N_0, there is an endpoint mask satisfying (10). a:G×I→{0,1},|ℛa(x)|≤r,|𝒞a,s(y)|≤r(x,y∈G).\begin{gathered} a:G\times I\longrightarrow\{0,1\},\\ |\mathcal R_a(x)|\leq r,\qquad |\mathcal C_{a,s}(y)|\leq r\qquad(x,y\in G). \end{gathered}(10)✦

Put d=|I|d=|I|. Suppose ρ≥0\rho\geq0 and ∥∑i∈IRs(i)∥≤dρ\bigl\|\sum_{i\in I}R_{s(i)}\bigr\|\leq d\rho. For every integer ℓ≥1\ell\geq1, there is a mask on the word labels satisfying (11). aℓ:G×𝒲ℓ(I)→{0,1},|ℛaℓ(x)|≤⌈dℓρℓ⌉,|𝒞aℓ,ps(y)|≤⌈dℓρℓ⌉(x,y∈G).\begin{gathered} a_\ell:G\times\mathcal W_\ell(I)\longrightarrow\{0,1\},\\ |\mathcal R_{a_\ell}(x)|\leq\lceil d^\ell\rho^\ell\rceil,\qquad |\mathcal C_{a_\ell,p_s}(y)|\leq\lceil d^\ell\rho^\ell\rceil \qquad(x,y\in G). \end{gathered}(11)✦

If GG is nonamenable, there are a finite subset S⊆GS\subseteq G containing 11, with d=|S|≥2d=|S|\geq2, and a real number 0<ρ<10<\rho<1 such that, for every integer ℓ≥1\ell\geq1, there is a mask satisfying (12); here pSp_S is the word product for the inclusion S↪GS\hookrightarrow G. aℓ:G×𝒲ℓ(S)→{0,1},|ℛaℓ(x)|≤⌈dℓρℓ⌉,|𝒞aℓ,pS(y)|≤⌈dℓρℓ⌉(x,y∈G).\begin{gathered} a_\ell:G\times\mathcal W_\ell(S)\longrightarrow\{0,1\},\\ |\mathcal R_{a_\ell}(x)|\leq\lceil d^\ell\rho^\ell\rceil,\qquad |\mathcal C_{a_\ell,p_S}(y)|\leq\lceil d^\ell\rho^\ell\rceil \qquad(x,y\in G). \end{gathered}(12)✦

In the paper, the result reads: for a countable nonamenable group GG and S,d,ρS,d,\rho as in Lemma 3.1, every ℓ≥1\ell\geq1 gives a list s1,…,sns_1,\ldots,s_n of all length-ℓ\ell products from SS, with multiplicity and n=dℓn=d^\ell, and, with r=⌈nρℓ⌉r=\lceil n\rho^\ell\rceil, there is a function a:G×{1,…,n}→{0,1}a:G\times\{1,\ldots,n\}\to\{0,1\} such that each row has at most rr indices with a(x,i)=1a(x,i)=1 and each column yy has at most rr indices with a(ysi−1,i)=0a(ys_i^{-1},i)=0.

What Is Checked

The endpoint assignment is stated over arbitrary sets of edges and vertices, and the group assignments over arbitrary discrete groups with finite label sets and the stated operator or nonamenability hypotheses.

Coordinate permutation on ℓ2(G)\ell^2(G) is isometric: for every bijection e:G→Ge:G\to G, the map PeP_e satisfies (13). ∥Peξ∥2=∥ξ∥2(ξ∈ℓ2(G)).\|P_e\xi\|_2=\|\xi\|_2\qquad(\xi\in\ell^2(G)).(13)✦