OctoInformBeta

OpenAI preprint, September 2026 · §3. A uniform Boolean sampler

Lemma 3.1: Exponential success estimates and a polynomial failure bound for bounded functions on finite abelian groups

Uniform lower bounds from Boolean sampling.

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 finite abelian group, written additively. A Boolean sampler uses the subset sums of a random family in GG to average a function at every translate.

The uniform mean μ\mu of a function f:G→ℝf\colon G\to\mathbb R is the real number in (1): μ=1|G|∑y∈Gf(y).\mu=\frac{1}{|G|}\sum_{y\in G}f(y).(1)

For a nonnegative integer ss, choose a family w=(w1,…,ws)w=(w_1,\ldots,w_s) uniformly from GsG^s. The uniform probability ℙ(E)\mathbb P(E) of an event E⊆GsE\subseteq G^s is the real number defined in (2): ℙ(E)=|E||G|s.\mathbb P(E)=\frac{|E|}{|G|^s}.(2)✦

The Boolean subset sum Sw(e)S_w(e) associated with w∈Gsw\in G^s and a Boolean word e∈{0,1}se\in\{0,1\}^s is the element of GG defined in (3): Sw(e)=∑1≤i≤sei=1wi.S_w(e)=\sum_{\substack{1\le i\le s\\ e_i=1}}w_i.(3)✦ The Boolean sampling average Awf:G→ℝA_wf\colon G\to\mathbb R is the function Awf(x)=12s∑e∈{0,1}sf(x−Sw(e)).A_wf(x)=\frac{1}{2^s}\sum_{e\in\{0,1\}^s}f\bigl(x-S_w(e)\bigr).(4)

The sampling constant c*c_* is the real number in (5): c*=log⁡28.c_*=\frac{\log 2}{8}.(5)✦

The Claim

Theorem 1. There is a real constant b0>1b_0>1 with the following property. Let b≥b0b\ge b_0 and let GG be a finite abelian group with log⁡|G|≤b4\log|G|\le b^4. Let f:G→ℝf\colon G\to\mathbb R have uniform mean μ\mu as in (1), and suppose that 0≤f(x)≤exp⁡(b65/100)0\le f(x)\le \exp(b^{65/100}) for every x∈Gx\in G and that 1/2≤μ≤21/2\le\mu\le2. Let ss be a nonnegative integer satisfying b69/100≤s≤bb^{69/100}\le s\le b. With uniform probability as in (2), the sampling average in (4) satisfies ℙ(∀x∈G,Awf(x)≥(1−3b−1/10)μ)≥1−exp⁡(−c*b69/100)−bexp⁡(−c*2b59/100),ℙ(∃x∈G,Awf(x)<(1−3b−1/10)μ)≤b−1/2.\begin{aligned} \mathbb P\!\left(\forall x\in G,\quad A_wf(x)\ge (1-3b^{-1/10})\mu\right) &\ge 1-\exp\!\left(-c_*b^{69/100}\right) -b\exp\!\left(-\frac{c_*}{2}b^{59/100}\right),\\ \mathbb P\!\left(\exists x\in G,\quad A_wf(x)<(1-3b^{-1/10})\mu\right) &\le b^{-1/2}. \end{aligned}(6)✦

What Is Checked

The claim (6) is stated over finite abelian groups with uniform probability, using the Boolean subset sums (3) and the constant (5), under the stated bounds on group size, the function and its mean, and the sample count.