The Setting
The question is how large block sensitivity at the all-false input can be compared with maximum sensitivity. Let be a finite coordinate set and let be a total Boolean function. Write for the all-false input and for the numbered coordinate set of size . A Boolean function is nonconstant if takes different values at two inputs.
The block flip of an input along a coordinate block is the input that complements precisely the coordinates in , as in (1). (1)โฆ
The local sensitivity counts the coordinates whose individual flips change at โฆ; the sensitivity is its maximum over inputs, as in (2).โฆ (2)
The local block sensitivity is the largest size of a family of pairwise disjoint nonempty coordinate blocks, each changing at ; the empty family is allowed.โฆ The block sensitivity of a Boolean function is the maximum of its local block sensitivity over inputs , as in (3).โฆ (3)
Iterated Block Composition
For each nonnegative integer , the coordinate set of the th iterate is the set defined recursively by (4), where is a single coordinate. (4)โฆ
The iterated block composition is the Boolean function on defined by (5): each outer coordinate receives the value of the previous iterate on its own block. (5)โฆ
For a bijection , the coordinate relabelling of a Boolean function on is the function on given by .โฆ Choose bijections . The indexed iterate of is the relabelled function .โฆ
Seed Bounds and Amplification
For a positive integer , the depth-nine parameters are , and . The seed gap (6) holds for every positive integer . (6)โฆ For every positive real , the ratio bound is (7). (7)โฆ
Suppose is finite, , and natural numbers satisfy , , and . Set . Power amplification gives (8) for the indexed iterates . (8)โฆ
The Claim
Theorem 1. There exist a real number , integers , and total Boolean functions such that, for every integer , , and is nonconstant, with the separation and growth in (9). (9)โฆ There is also a choice of these data for which the same conditions hold for every integer , together with the geometric bound (10). (10)โฆ
In the paper, the result reads: there exist a real and nonconstant total Boolean functions , for integers , such that for every and tends to infinity.
What Is Checked
The amplification statement ranges over total Boolean functions on arbitrary finite coordinate sets, with and natural numbers satisfying , , and ; the resulting families have numbered coordinate sets .
The iterated coordinate sets in (4) satisfy the counting identity (11). (11)โฆ