The Setting
A graph restriction fixes some edges and leaves a Boolean function on the remaining edges. Take a finite coordinate set ; for graphs on vertices, take . Let be the free coordinates and the fixed coordinates. The degree of a Fourier support among the free coordinates is .
For a real parameter , the scalar Bernoulli weight of a bit and the product weight of a configuration , on any finite coordinate set , are given in (1); for a real-valued function on this cube, denotes the corresponding finite weighted sum. (1) For , these are the Bernoulli product weights and expectation.
For any value set , the gluing of and is the configuration in (2).✦ For value sets and , a function , and a fixed configuration , the coordinate restriction is the function given by (2).✦ (2)
Fourier Coefficients and Influence
At bias , the biased coordinate character on , the product character for , and the biased Fourier coefficient of a real-valued function are defined by (3). (3)
For a Boolean function , the pivotal influence of coordinate is the weighted sum in (4), where is with bit toggled; the total influence is the sum of the coordinate influences.✦ (4)
The Claim
Theorem 1. Let be a finite coordinate set, let , and put . Let and . For any set of degrees, the selected-degree identity is (5): (5)✦ For every real cutoff , the low-degree identity is (6): (6)✦ For a Boolean function and every real , the influence identity is (7): (7)✦
In the paper, the result reads: for a Boolean function on , , , , and , with distributed according to the Bernoulli- product law on , every real satisfies (8) and (9): (8) (9)
What Is Checked
The Fourier identities concern real-valued functions on finite Boolean cubes at with an arbitrary set of free coordinates, and the influence identity concerns Boolean functions with the product weights of (1) for every real .