The Setting
The question is how sensitivity and block sensitivity behave when one Boolean function is substituted into every coordinate of another. Let and be finite coordinate sets, and let . Take total Boolean functions and .
The block composition is the Boolean function on that applies to each row and to the resulting input.✦ For , write for its row indexed by and for the input to , as in (1). (1)✦
For a finite coordinate set , an input , and a block , the block flip is the input given by (2), where interchanges and . Write , or when the coordinates are understood, for the input that is false at every coordinate of . (2)✦
Let be a Boolean function. The pointwise sensitivity of at is the number of coordinates whose singleton flip changes the value of ✦; the sensitivity is its maximum over all inputs, as in (3).✦ (3)
A sensitive block for at is a nonempty subset of such that . The pointwise block sensitivity of at is the maximum cardinality of a family of pairwise disjoint sensitive blocks, as in (4); the empty family is allowed.✦ (4)✦
The Claim
Theorem 1. Let and be total Boolean functions on finite coordinate sets, and put . For every input , (5) holds, and the maximum satisfies (6). (5)✦ (6)✦ Suppose that . Then (7) and (8) hold. (7)✦ (8)✦ For any index sets and , let and be families of pairwise disjoint sensitive blocks for at and for at , respectively. The Cartesian blocks satisfy (9) for all indices in the indicated families. (9)✦ For finite and , (10) holds. (10)✦
In the paper, the result reads: for total Boolean functions on bits and on bits, , and if , then and , with any families of and pairwise disjoint nonempty sensitive blocks at zero for and yielding such blocks for .
What Is Checked
The statements concern total Boolean functions on finite coordinate sets; the zero-input claims assume , and the Cartesian block claims concern indexed families of pairwise disjoint sensitive blocks, with finite index sets for (10).