The Setting
For an OR of disjoint copies of a Boolean function, sensitivity counts individual coordinates that change the output, whereas block sensitivity counts disjoint sets of coordinates that change it. The final construction concerns the ratio of block sensitivity to squared sensitivity as the depth increases.
Write and let denote the all-false input. For a finite coordinate set , an input and a block , the block flip complements precisely the coordinates in .✦ The local sensitivity of a Boolean function is the number of coordinates for which .✦ For a Boolean function on a finite coordinate set and an input , the local block sensitivity is the maximum size of a family of pairwise disjoint nonempty blocks satisfying , with the empty family allowed.✦ For a Boolean function on a finite coordinate set , the maximum sensitivity and maximum block sensitivity are the maxima of the corresponding local quantities over all inputs, as in (1). (1)
For a finite set , the OR gate is true exactly when at least one of its inputs is true.✦ The block composition of and is the Boolean function on given by (2), where . (2)✦ The OR of disjoint copies of is the function on defined in (3). (3)✦
The Tower Predicate
For a natural number , write . Let be natural numbers, and put , and . A tournament on is a directed graph without loops in which exactly one of and holds for distinct vertices.✦ A regular tournament on with parameter is a tournament in which every vertex has outdegree .✦
A good labelling of with labels is a map satisfying (4): for every set of vertices and every map , there are such that (4)✦
For a finite base coordinate set and a natural number , the tower coordinate sets and the construction coordinate sets are the finite sets defined recursively in (5). (5)
For a finite coordinate set , a finite family of centers in and a radius , the union of Hamming balls of radius is the Boolean predicate on that is true exactly when the input has Hamming distance at most from one of the centers.✦ For , the block indicator center on is the Boolean input that is true exactly on coordinates whose first component equals .✦ With denoting Hamming distance, the initial Hamming ball family is the family of Boolean predicates on defined by (6). (6)✦ For every index count , the construction base family is the family of Boolean predicates on equal to when and to the constant false family otherwise.✦ For a family of Boolean predicates on a coordinate set and a natural index count , the extended initial family is the family of Boolean predicates on that equals when and consists of constant false predicates otherwise.✦
For a tournament on vertices, a labelling with labels and a base family of Boolean predicates on a coordinate set for every natural index count , the tower predicate family consists of Boolean predicates on at depth . For a tournament on vertices, a labelling with labels and a base family on for every natural index count, the tower predicate family at index count is the base family at index count at depth zero, and is the recursive predicate family formed from the preceding tower family at index count at a successor depth.✦ For a regular tournament with parameter and a good labelling with labels, the terminal predicate is the sole predicate in the tower predicate family with the construction base family at depth and index count one.✦
The construction dimension is the natural number in (7). (7)✦
Coordinate relabelling along a bijection sends a Boolean function on to the function on .✦
The Claim
Theorem 1. Let be finite sets and . Suppose the nonnegative integers satisfy for every and every input with . Then the OR sensitivity bound is (8). (8)✦ If , the bound at the all-false input is (9). (9)✦
For natural numbers , let be a regular tournament with parameter and a good labelling with labels. The final OR function on is defined by (10). (10)✦ Its coordinate count is (11). (11)✦ For the fixed coordinate bijection , the indexed final witness is the relabelling in (12). (12)✦ Assume , and ; then the sensitivity estimate (13) holds. (13)✦ When , the block sensitivity estimate is (14). (14)✦
For and , set . There is a Boolean function with the properties in (15). (15)✦
Let be natural numbers with , and let be a nonconstant Boolean function on any finite coordinate set. Suppose and . Then (16) holds. (16)✦ The numerical lower bound has the natural depth limit (17). (17)✦
In the paper, the result reads: for every integer , choose and good labels, set , and let be the OR of disjoint copies of ; then , , is nonconstant, and , with tending to infinity with .
What Is Checked
The OR estimates (8) and (9) concern arbitrary finite coordinate and copy sets; the construction statements concern natural parameters and regular tournaments with good labellings, and the ratio estimate (16) concerns any nonconstant finite Boolean function satisfying its two quantitative bounds.