OctoInformBeta

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

Lemma 3.1: Finite subsets containing the identity give bounds for right regular sums on the complex Hilbert space ℓ2(G)\ell^2(G)

Nonamenability supplies contracting regular averages.

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, with identity ee. The question is how nonamenability constrains the operator norm of a finite sum of right translations.

The complex Hilbert space ℓ2(G)\ell^2(G) consists of square-summable functions ξ:G→ℂ\xi:G\to\mathbb C, with norm (1). ∥ξ∥22=∑x∈G|ξ(x)|2<∞.\|\xi\|_2^2=\sum_{x\in G}|\xi(x)|^2<\infty.(1)✦

Write ℓ∞(G)\ell^\infty(G) for the bounded complex-valued functions on GG. For g∈Gg\in G and f∈ℓ∞(G)f\in\ell^\infty(G), the left translate LgfL_gf is the bounded function defined by (2). Lgf(x)=f(g−1x)(x∈G).L_gf(x)=f(g^{-1}x)\qquad(x\in G).(2)✦

A discrete group GG is amenable if there is a complex-linear functional m:ℓ∞(G)→ℂm:\ell^\infty(G)\to\mathbb C satisfying (3), where 𝟏\mathbf 1 is the constant function with value 11. m(𝟏)=1,m(f)∈[0,∞)whenever f(x)∈[0,∞) for every x∈G,m(Lgf)=m(f)(g∈G,f∈ℓ∞(G)).\begin{aligned} m(\mathbf 1)&=1,\\ m(f)&\in[0,\infty) &&\text{whenever }f(x)\in[0,\infty)\text{ for every }x\in G,\\ m(L_gf)&=m(f) &&(g\in G,\ f\in\ell^\infty(G)). \end{aligned}(3)✦

For a bijection σ:G→G\sigma:G\to G, the coordinate permutation Pσ:ℓ2(G)→ℓ2(G)P_\sigma:\ell^2(G)\to\ell^2(G) is the map defined by (4). (Pσξ)(x)=ξ(σ(x))(ξ∈ℓ2(G),x∈G).(P_\sigma\xi)(x)=\xi(\sigma(x)) \qquad(\xi\in\ell^2(G),\ x\in G).(4)✦

The right regular representation RR of GG is the monoid homomorphism into the bounded complex-linear operators on ℓ2(G)\ell^2(G) defined by (5).✦ For operators, ∥⋅∥\|\cdot\| denotes the operator norm. Rtξ(x)=ξ(xt)(t,x∈G,ξ∈ℓ2(G)).R_t\xi(x)=\xi(xt) \qquad(t,x\in G,\ \xi\in\ell^2(G)).(5)

The Claim

Theorem 1. Let GG be a nonamenable discrete group. There are a finite set S⊆GS\subseteq G, with e∈Se\in S and d=|S|≥2d=|S|\ge2, and a real number 0<ρ<10<\rho<1 such that ∥1d∑t∈SRt∥≤ρ.\left\|\frac1d\sum_{t\in S}R_t\right\|\le\rho.(6)✦ There are also a finite set T⊆GT\subseteq G, with e∈Te\in T and q=|T|≥2q=|T|\ge2, and a real number 0<η<10<\eta<1 such that ∥∑t∈TRt∥≤qη.\left\|\sum_{t\in T}R_t\right\|\le q\eta.(7)✦

In the paper, the result reads: if GG is a nonamenable discrete group, there are a finite set S⊆GS\subseteq G containing ee, with d=|S|≥2d=|S|\ge2, and a real number 0<ρ<10<\rho<1 such that ∥1d∑t∈SRt∥≤ρ\|\frac1d\sum_{t\in S}R_t\|\le\rho.

What Is Checked

The assertions (6) and (7) are stated for arbitrary discrete groups, with amenability defined by (3) and the right regular operators on ℓ2(G)\ell^2(G) defined by (5).

Every coordinate permutation PσP_\sigma in (4) is a norm-preserving complex-linear map on ℓ2(G)\ell^2(G).✦