OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

§1 (setting): literal flips, sensitivity, and block sensitivity: Pointwise and maximum values on a finite set of coordinates

Sensitivity from coordinate and block flips.

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

Sensitivity and block sensitivity describe how a total Boolean function reacts to changes in its input coordinates. The distinction is between changing one coordinate at a time and allowing disjoint sets of coordinates.

The Definition

Definition 1. Let II be a coordinate set, let X={false,true}IX=\{\mathrm{false},\mathrm{true}\}^{I}, and let f:X→{false,true}f:X\to\{\mathrm{false},\mathrm{true}\} be a total Boolean function. For an input x∈Xx\in X and a finite set B⊆IB\subseteq I, the block flip xB∈Xx^B\in X is defined by (1), where ¬\neg denotes Boolean negation: (xB)i={¬xi,i∈B,xi,i∉B.(x^B)_i= \begin{cases} \neg x_i,& i\in B,\\ x_i,& i\notin B. \end{cases}(1)✦

Suppose that II is finite. The pointwise sensitivity s(f,x)s(f,x) of ff at xx is the number of coordinates whose singleton flips change its value, as in (2): s(f,x)=|{i∈I:f(x{i})≠f(x)}|.s(f,x)=\bigl|\{i\in I:f(x^{\{i\}})\ne f(x)\}\bigr|.(2)✦ The sensitivity s(f)s(f) of ff is its maximum pointwise sensitivity, as in (3): s(f)=maxx∈Xs(f,x).s(f)=\max_{x\in X}s(f,x).(3)✦

The pointwise block sensitivity bs(f,x)\mathrm{bs}(f,x) of ff at xx is the largest number of pairwise disjoint nonempty blocks whose flips change its value, as in (4): bs(f,x)=maxℬ a family of subsets of IA∩B=⌀(A,B∈ℬ,A≠B)B≠⌀,f(xB)≠f(x)(B∈ℬ)|ℬ|.\mathrm{bs}(f,x)= \max_{\substack{ \mathcal B\text{ a family of subsets of }I\\ A\cap B=\varnothing\ (A,B\in\mathcal B,\ A\ne B)\\ B\ne\varnothing,\ f(x^B)\ne f(x)\ (B\in\mathcal B) }}|\mathcal B|.(4)✦ The block sensitivity bs(f)\mathrm{bs}(f) of ff is its maximum pointwise block sensitivity, as in (5): bs(f)=maxx∈Xbs(f,x).\mathrm{bs}(f)=\max_{x\in X}\mathrm{bs}(f,x).(5)✦

In the paper, the result reads: for a positive integer nn and a total Boolean function ff on {false,true}n\{\mathrm{false},\mathrm{true}\}^{n}, xBx^B flips precisely the coordinates of BB, s(f,x)s(f,x) counts coordinates aa with f(x{a})≠f(x)f(x^{\{a\}})\ne f(x) and s(f)s(f) is its maximum over xx, while bs(f,x)\mathrm{bs}(f,x) is the largest size of a family of pairwise disjoint nonempty coordinate sets whose flips change ff at xx and bs(f)\mathrm{bs}(f) is its maximum over xx.

What Is Checked

Block flips are defined for finite subsets of any coordinate set; sensitivity and block sensitivity are defined for total Boolean functions on a finite coordinate set.