The Setting
The blocks relevant to block sensitivity at the all-false input are sets of coordinates whose simultaneous flip changes the function’s value. For a family of Boolean predicates, the question is whether the same collection of blocks works for every predicate.
Write , with , and let denote the all-false input on the coordinate set in question. For a Boolean input on and a finite coordinate block , the block flip is the input specified by (1). (1)✦
For nonnegative integers and , the base block is the subset of consisting of the coordinates with first component .✦ The block indicator center of is the Boolean input on defined in (2). (2)
For a finite family of Boolean centers on a finite coordinate set and a nonnegative integer , the union of Hamming balls is the predicate in (3), where counts the coordinates at which two inputs differ. (3)✦
Let be nonnegative integers and put . The initial Hamming family is the family of predicates on defined by (4); the predicate index starts at one. (4)✦
For nonnegative integers , a tournament on is a directed graph with no loops and exactly one orientation of each pair of distinct vertices.✦ An edge labelling assigns one of labels to each ordered pair.
For a coordinate set , a finite block index set and each nonnegative depth , the tower coordinate sets and tower block index sets are the Cartesian products in (5). (5)
Given finite base blocks indexed by , the tower block is the finite set defined recursively in (6). The row lift in row of a tower block is the successor block defined by (6). (6)✦
Let , for each nonnegative integer and , be Boolean base predicates on . The tower family consists of predicates on defined by (7), where denotes the recursive predicate construction associated with the labelled tournament. (7)✦
The Claim
Theorem 1. For nonnegative integers , the initial family satisfies (8) and (9), for every and . (8)✦ (9)✦ For arbitrary base block length , (10) holds for each ; (11) holds for every nonnegative length . (10)✦ (11)✦
Let be nonnegative integers, let be finite, and let be finite blocks on an arbitrary coordinate set . At every nonnegative depth , the index count is (12). (12)✦ If every base block has size , then (13) holds for every . (13)✦ If and every base block is nonempty, then (14) holds for every . (14)✦ For pairwise disjoint base blocks, (15) holds. (15)✦
Let be a tournament on , let take values in , and assume . Fix nonnegative integers . If every base predicate is false at , then (16) holds for every . (16)✦ If, in addition, every base predicate is true at for every , then (17) holds for every and . (17)✦ For and nonempty, pairwise disjoint base blocks, the number of distinct blocks is (18). (18)✦
In the paper, the result reads: for and , with , and , the specified construction has, at every level , all predicates false at zero and pairwise disjoint nonempty coordinate blocks of size , flipping any one of which at zero makes every predicate at that level true.
What Is Checked
The initial assertions concern the Hamming family (4) on with and the base blocks (2); the tower assertions concern the recursively defined families (6) and (7) on (5), for arbitrary Boolean base predicates and a finite index set , with the stated hypotheses on the blocks and the label count.