The Setting
The square-root degree question compares the linear Fourier coefficients of a Boolean function with the square root of its Fourier degree. The signed sum of those coefficients and the sum of their absolute values give two different comparisons.
For a finite index set , the sign cube is the set of sign vectors indexed by ; write when .✦ A Boolean function is a function taking only the values and .✦ A nonconstant function is one for which there are with .✦
For a real function on a finite set , the uniform mean is the real number given by (1), with mean zero when is empty: (1) For , the Fourier character is the coordinate product in (2): (2)✦ The real Fourier-Walsh coefficient of is its uniform mean against , as in (3): (3)✦
The Fourier degree of is the nonnegative integer defined in (4), measuring its ordinary real multilinear degree, with constants and the zero function having degree zero. This degree is distinct from polynomial threshold degree and degree over a finite field. (4)✦ The signed singleton sum and absolute singleton sum of are the two sums in (5): (5)
The set of absolute degree ratios consists of the ratios in (6), taken over Boolean functions of positive degree on positive-dimensional cubes: (6) The signed violation property is the assertion that for every real there are an integer and a nonconstant Boolean function satisfying (7): (7)✦
The Claim
Theorem 1. The signed violation property holds, and the absolute degree ratios are unbounded above, as in (8) and (9): (8)✦ (9)✦ If the signed violation property holds, then (10) holds: (10)✦ For every finite index set and every nonconstant real function , the degree satisfies (11): (11)✦
In the paper, the result reads: for every real there are an integer and a nonconstant Boolean function with , and consequently the supremum of over and positive-degree Boolean functions is infinite.
What Is Checked
The signed and joint assertions concern Boolean functions on positive-dimensional finite sign cubes, with nonconstancy in and positive degree in . The conditional assertion (10) uses precisely the signed violation property; the positivity assertion (11) applies to real functions on any finite sign cube, without a Boolean hypothesis.