The Setting
A finite observation records a report at each point of a sign cube. Its fibers specify which distinctions between inputs remain available to a function of the report; the conditional coordinate sum measures the information about that sum retained by the observation.
The sign cube on a finite coordinate set is , whose coordinate signs are real numbers.✦ For a real-valued function on a finite set , its uniform mean is (1)✦ Every cube average uses the mean in (1).
For , the Fourier character is the product of the coordinate signs in .✦ The real Fourier-Walsh coefficient of and its ordinary real multilinear Fourier degree are defined by (2)
Cells and Conditional Scores
An observation on a finite set is a map assigning a report in to each input. For an observation and a report , the cell indicator is the indicator function of the fiber .✦ For an observation on a finite set and a report , the cell mass is the uniform mean of the cell indicator ✦, and the restricted moment of a function is the uniform mean of the product : (3) The fiber conditional mean is the ratio of the restricted moment to the cell mass in (3), with value zero on an empty fiber.✦ For an observation on a finite set and a function , the conditional average is the function whose value on the fiber is the fiber conditional mean : (4)
The coordinate sum and the score of an observation are (5) For a finite block set , write for the th block of . The grouped observation applies to each block: (6)✦ Its score uses (5) with coordinate set .
For an observation , a function , and a finite set , the observation tuple and block sum are defined by and . For an observation tuple and a map , the coarsened observation is the composite .
The Claim
Theorem 1. Let be finite. Let be a finite index set and a degree bound. For a family of real-valued functions indexed by and satisfying for every , (7)✦ For arbitrary real-valued functions , (8)✦ For any finite set and real-valued cube functions , (9)✦
Let be finite, and let have for every . For every , (10)✦ More generally, let be finite and let satisfy for every and . For every , (11)✦
Let be finite, , , and . Then (12)✦ For a finite set and any , (13)✦ For the observation tuple itself, (14)✦
Let satisfy for every . For every , the grouped observation in (6) satisfies (15)✦ For every observation , its grouped score satisfies (16)✦
In the paper, the result reads: every function of has degree at most its cell degree bound ; functions of observations on disjoint blocks with bounds have degree at most ; products have degree at most the sum of the degrees; for independent uniform blocks, conditioning the total sum on the observation tuple gives the sum of the block scores, and conditioning further on any function of that tuple preserves this score identity.
What Is Checked
The bounds (7), (8), (9), (10), (11), and (15) are stated for real-valued functions on finite sign cubes and, where observations occur, finite report sets; the identities (12), (13), (14), and (16) use conditional averages on finite uniform spaces and their products.