OctoInformBeta

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

Random subset sums on a finite abelian group: Normalized counting probability for independent uniform shifts in a finite abelian group

Random subset sums with Boolean multiplicity.

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, and let kk be a nonnegative integer. A tuple w=(w1,…,wk)∈Gkw=(w_1,\ldots,w_k)\in G^k gives kk shifts, and a Boolean word e=(e1,…,ek)∈{0,1}ke=(e_1,\ldots,e_k)\in\{0,1\}^k records a choice of them. The subset sums are indexed by all 2k2^k Boolean words, retaining multiplicity when different words give the same translation.

Independent uniform shifts are sampled on GkG^k with normalized counting probability. For a finite nonempty sample space Ω\Omega, an event A⊆ΩA\subseteq\Omega is a set of outcomes, and #A\#A denotes its cardinality.

The Definition

Definition 1. For w∈Gkw\in G^k and e∈{0,1}ke\in\{0,1\}^k, the Boolean subset shift sw(e)∈Gs_w(e)\in G is the group element sw(e)=∑1≤i≤kei=1wi.s_w(e)=\sum_{\substack{1\le i\le k\\ e_i=1}}w_i.(1)✦ For a finite nonempty sample space Ω\Omega and an event A⊆ΩA\subseteq\Omega, the event probability ℙΩ(A)\mathbb P_{\Omega}(A) is its normalized counting measure, ℙΩ(A)=#A#Ω.\mathbb P_{\Omega}(A)=\frac{\#A}{\#\Omega}.(2)✦

What Is Checked

The definitions in (1) and (2) are stated over Boolean words and shifts in a finite abelian group, and events in a finite sample space.