OpenAI preprint, September 2026 · §3. A uniform Boolean sampler
Lemma3.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 be a finite abelian group, written additively. A Boolean sampler uses the subset sums of a random family in to average a function at every translate.
The uniform mean of a function is the real number in (1): (1)
For a nonnegative integer , choose a family uniformly from .The uniform probability of an event is the real number defined in (2): (2)✦
The Boolean subset sum associated with and a Boolean word is the element of defined in (3): (3)✦ The Boolean sampling average is the function (4)
The sampling constant is the real number in (5): (5)✦
The Claim
Theorem 1. There is a real constant with the following property. Let and let be a finite abelian group with . Let have uniform mean as in (1), and suppose that for every and that . Let be a nonnegative integer satisfying .With uniform probability as in (2), the sampling average in (4) satisfies (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.