OctoInformBeta

OpenAI preprint, September 2026 · §2. The labelled tournament and nested predicates

§2.3 (setting): ordinary and joint profiles: Ordinary profiles separate the output sides; joint profiles count coordinates sensitive for two predicates at the same input

Sensitivity profiles track single-coordinate 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

Let II be a finite coordinate set and let 𝔹={false,true}\mathbb B=\{\mathrm{false},\mathrm{true}\}. For an input x∈𝔹Ix\in\mathbb B^I and a block B⊆IB\subseteq I, the block flip xBx^B is the input obtained by complementing the coordinates in BB: xiB={¬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)✦ Here ¬\neg interchanges false and true. The pointwise sensitivity s(f,x)s(f,x) of a Boolean function f:𝔹I→𝔹f\colon\mathbb B^I\to\mathbb B is the number of coordinates whose individual flip changes its value, using the block flip in (1): 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)✦

Write [h]={1,…,h}[h]=\{1,\ldots,h\}, with [0]=⌀[0]=\varnothing, and let F=(Fq)q∈[h]F=(F_q)_{q\in[h]} be a family of Boolean predicates on 𝔹I\mathbb B^I. A nested predicate family F=(Fq)q∈[h]F=(F_q)_{q\in[h]} on 𝔹I\mathbb B^I is a family in which truth of a predicate at an index forces truth at every smaller index; nesting therefore concerns the predicate index rather than monotonicity in the input bits.✦ The profiles below are defined for arbitrary families, including families without nesting.

For the iterated families, let kk and rr be the numbers of vertices and available edge labels, respectively, and let TT be a tournament on [k][k], a directed graph with no loops and exactly one directed edge between each pair of distinct vertices.✦ An edge labelling λ\lambda of the tournament TT is a function λ:[k]×[k]→[r]\lambda\colon[k]\times[k]\to[r]. The tower coordinate sets CℓC_\ell are the finite sets defined recursively by C0=I,Cℓ+1=([k]×[r])×Cℓ.C_0=I,\qquad C_{\ell+1}=([k]\times[r])\times C_\ell.(3)✦ Choose a base family AhA_h of hh predicates on 𝔹I\mathbb B^I for every nonnegative integer hh. The iterated predicate family P(ℓ,h)P^{(\ell,h)} is a family of hh predicates on 𝔹Cℓ\mathbb B^{C_\ell}: at level zero it is AhA_h, and at level ℓ+1\ell+1 it is the tournament recursion, with tournament TT and labelling λ\lambda, applied to P(ℓ,h+1)P^{(\ell,h+1)}, on the coordinate sets in (3).✦

For a nonnegative total height DD, write Hℓ=max⁡{D−ℓ,0}H_\ell=\max\{D-\ell,0\} and Pℓ,q=Pq(ℓ,Hℓ)P_{\ell,q}=P^{(\ell,H_\ell)}_q. Let dd denote the final level under consideration.

The Claim

Definition 1 (Nested families and sensitivity profiles). Fq′(x)=true⇒Fq(x)=true(q≤q′,x∈𝔹I).F_{q'}(x)=\mathrm{true}\ \Longrightarrow\ F_q(x)=\mathrm{true} \qquad(q\le q',\ x\in\mathbb B^I).(4)✦ For Boolean functions f,g:𝔹I→𝔹f,g\colon\mathbb B^I\to\mathbb B, their local joint sensitivity j(f,g;x)j(f,g;x) at xx is the number j(f,g;x)=|{i∈I:f(x{i})≠f(x),g(x{i})≠g(x)}|.j(f,g;x)=\bigl|\{i\in I: f(x^{\{i\}})\ne f(x),\quad g(x^{\{i\}})\ne g(x)\}\bigr|.(5)✦ For a family F=(Fq)q∈[h]F=(F_q)_{q\in[h]} of Boolean predicates on 𝔹I\mathbb B^I and a Boolean value bb, the side sensitivity 𝒮b(F)\mathcal S_b(F) is the maximum pointwise sensitivity in (2) over predicates and inputs with output bb, with maximum zero when there are no such inputs: 𝒮b(F)=max⁡({s(Fq,x):q∈[h],x∈𝔹I,Fq(x)=b}∪{0}).\mathcal S_b(F)= \max\bigl(\{s(F_q,x):q\in[h],\ x\in\mathbb B^I, \ F_q(x)=b\}\cup\{0\}\bigr).(6)✦ For a family F=(Fq)q∈[h]F=(F_q)_{q\in[h]} of Boolean predicates on 𝔹I\mathbb B^I and a Boolean value bb, the joint sensitivity 𝒥b(F)\mathcal J_b(F) is the maximum local joint sensitivity from (5) over pairs of distinct predicates that both have output bb at a common input, with maximum zero when there are no such pairs and inputs: 𝒥b(F)=max⁡({j(Fq,Fq′;x):q<q′,x∈𝔹I,Fq(x)=Fq′(x)=b}∪{0}).\mathcal J_b(F)= \max\bigl(\{j(F_q,F_{q'};x):q<q',\ x\in\mathbb B^I, \ F_q(x)=F_{q'}(x)=b\}\cup\{0\}\bigr).(7)✦ For a family FF containing exactly one predicate and either Boolean value bb, 𝒥b(F)=0.\mathcal J_b(F)=0.(8)✦ The ordinary tower profile Sℓ,bS_{\ell,b} is the side sensitivity (6) of the level ℓ\ell family: Sℓ,b=𝒮b(P(ℓ,Hℓ)).S_{\ell,b}=\mathcal S_b\bigl(P^{(\ell,H_\ell)}\bigr).(9)✦ The joint tower profile Jℓ,bJ_{\ell,b} of the predicate family P(ℓ,Hℓ)P^{(\ell,H_\ell)} at level ℓ\ell is its joint sensitivity for the Boolean value bb, as defined in (7): Jℓ,b=𝒥b(P(ℓ,Hℓ)).J_{\ell,b}=\mathcal J_b\bigl(P^{(\ell,H_\ell)}\bigr).(10)✦

In the paper, the result reads: for b∈𝔹b\in\mathbb B, Sℓ,bS_{\ell,b} is the maximum sensitivity of Pℓ,qP_{\ell,q} over indices qq and inputs xx with Pℓ,q(x)=bP_{\ell,q}(x)=b; Jℓ,bJ_{\ell,b} is the maximum number of raw coordinates whose single flip changes both Pℓ,qP_{\ell,q} and Pℓ,q′P_{\ell,q'} from bb to ¬b\neg b, over fixed pairs q<q′q<q' and common inputs where both equal bb; empty maxima are zero, and both final joint profiles vanish when Hd=1H_d=1.

What Is Checked

The definitions and the singleton identity (8) are stated over finite coordinate sets and arbitrary predicate families of the indicated size; the tower profiles (9) and (10) use a labelled tournament, arbitrary base families, and nonnegative heights and levels.