The Setting
The initial stage of the Boolean function construction uses inputs close to block indicator strings. The distance allowed from a center is the parameter of each predicate.
Let be a finite coordinate set. A Boolean input on is a function from to . The Hamming distance between two inputs is the number of coordinates where they differ, as in (1). (1)
For a finite family of centers on a finite coordinate set and an integer , the union of Hamming balls of radius is the Boolean predicate on defined by (2). (2) For a nonempty finite family of centers on a finite coordinate set and a Boolean input on , the nearest distance from to the family is the minimum in (3). (3)✦
For a nonnegative integer , a family of Boolean predicates on a finite coordinate set is nested if it satisfies (4) at every Boolean input on . (4)✦ This condition concerns the predicate index rather than the order on input bits.
The Block Construction
Let be nonnegative integers. Use the coordinate set . For , the coordinate block of is the subset of coordinates with first coordinate , and its block indicator center is the Boolean input on defined in (5). (5) For a nonnegative integer , take . The initial Hamming family on is the family of Boolean predicates in (6), where uses the centers . (6)✦
The Claim
Theorem 1. Let , and take the blocks and centers of (5). For each , the block cardinality is (7). (7)✦ For distinct , the centers satisfy (8). (8)✦ For any finite nonempty family of centers on a finite coordinate set and any integer , the predicate in (2) satisfies (9) at every input . (9)✦ For , take and the initial family in (6). For , every input accepted by satisfies (10). (10)✦
In the paper, the result reads: with , and , set and for , partition the coordinates at level zero into disjoint blocks of size , let indicate , set and let be true exactly when for ; distinct centers have distance and the predicates are nested in , with radii .
What Is Checked
The statements concern finite Boolean cubes and the block construction on , with a nonempty finite center family for the nearest distance in (3).