The Setting
Let be uniform on the discrete cube , where . An observation is obtained by flipping each coordinate independently with probability . The question is how much information about a single Boolean function of can retain. A sign-valued function is a function taking only the values and .✦
The uniform cube expectation of a real function is the real number given by (1). (1)✦
The dictator and its complement on are the coordinate functions in (2), for . (2)
The bit-flip kernel for and is defined by (3). For , it is the conditional probability of observing given . (3)✦ The correlation parameter is . The noise transition kernel and the noise operator on real functions are defined by (4), for real . (4)
Put .✦ The logarithmic function is defined by (5). (5)✦ The binary entropy deficit and entropy function , in nats, are the real-valued functions on given by (6). (6) The binary entropy function , in bits, is given by (7). (7)✦ The mean binary entropy of a real field is the cube average of its pointwise entropies✦, and the information deficit of is the entropy Jensen gap in (8). (8)✦
The joint law of and , and its function and observation marginals and , are given by (9) and (10), for and . (9)✦ (10) The mutual information between and , measured in bits, is the sum in (11). (11)✦
The Claim
Theorem 1 (Boolean information bound). Let , let , and suppose , with . The entropy-gap bound is (12), and the mutual information bound is (13). (12)✦ (13)✦ For and , the coordinate and complemented coordinate have the mutual information values in (14) and (15), respectively. (14)✦ (15)✦ For every real , their entropy gaps satisfy (16) and (17). (16)✦ (17)✦ The Courtade-Kumar assertion in (18) is the universal positive-dimension version of (13) throughout .✦ (18)✦ The dictator attainment assertion in (19) requires (14) and (15) for every coordinate in every positive dimension throughout .✦ (19)✦ The sharp information assertion in (20) is together with .✦ (20)✦
In the paper, the result reads: for , , and , put and ; then the information in nats satisfies , with signed coordinates attaining the bound when and , and with when and .
What Is Checked
The claims are stated over uniform finite cubes, sign-valued functions and the product noise law (9), including dimension zero in (12) and (13), with for the general bounds and arbitrary real for the coordinate entropy-gap identities.