1 · The essentials
A rule can take a list of minus-one and plus-one inputs and return either minus one or plus one. For each input, we can measure how much the output tends to agree with it, and then add these signed measurements. The proposed bound compared that sum with the square root of the degree of a polynomial that exactly describes the rule. The main manuscript gives rules whose sums exceed this proposed bound by arbitrarily large factors. In particular, no fixed positive multiplier can make the proposed bound hold for every such rule. Each example uses a finite list of inputs and has an output that is not constant. The main result has a Lean formalization.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine a rule that combines several yes-or-no votes into one yes-or-no decision. You measure its tendency to agree with each voter and add those signed scores; the proposed bound would limit that total using a measure of the rule's algebraic complexity. The result says that no fixed multiplier makes this particular limit work for every rule.
Why it matters
This rules out not only the stated square-root bound but also every version obtained by multiplying its right-hand side by a fixed positive constant. It establishes a limitation on how polynomial degree can control the total signed correlation of a Boolean function with its individual inputs.
2 · Going further
The precise statement concerns nonconstant functions with finite . Write for the linear Fourier coefficient associated with input , and let be the degree of the real multilinear polynomial representing . For every real , the main manuscript states that there is such a function satisfying .
The manuscript identifies the proposed bound as the Gopalan–Servedio square-root conjecture. The quantifier “for every ” is crucial: the violation cannot be repaired by choosing a larger universal constant. The quantity on the left is a signed sum of linear Fourier coefficients, not a sum of their absolute values.
The supplied abstract states the result but does not describe the construction or the argument establishing it, so no mechanism can be extracted from this source. The main result has a Lean formalization, although the supplied material does not give its detailed scope. Only the main manuscript is supplied; there are no companion-manuscript descriptions to relate to it.
Useful notions
- Functions with minus-one and plus-one inputs and outputs
- Signed correlation with an individual input
- Polynomial degree
- Multilinear polynomial representations
- A bound with a universal constant
What was known before / what is new
Before
The manuscript identifies a proposed square-root bound as the Gopalan–Servedio conjecture. That proposal relates the sum of a Boolean function's linear Fourier coefficients to the square root of its polynomial degree. The supplied source gives no further history or earlier partial results.
New
The main result establishes violations by arbitrarily large constant factors: for every , a finite, nonconstant sign-valued Boolean function exceeds in the stated signed sum. Thus no fixed positive constant rescues the square-root bound. The main result has a Lean formalization.
Limits and assumptions
The statement is existential and concerns nonconstant sign-valued Boolean functions on finite sign cubes. The function and its number of inputs may depend on the chosen constant; it does not assert arbitrarily large violations at a fixed number of inputs. The sum is signed, and the degree is that of the real multilinear polynomial representing the function. The main result has a Lean formalization, but the supplied material does not specify its detailed coverage, provide the construction, or describe the argument. No remaining open questions or alternative bounds are identified in the source.
Mini glossary
- Boolean function —
- Here, a function that takes a finite list of minus-one or plus-one inputs and returns minus one or plus one.
- Sign cube —
- The set of all possible lists of sign inputs.
- Linear Fourier coefficient —
- The coefficient associated with an individual input, expressing the function's signed correlation with that input.
- Multilinear polynomial —
- A polynomial in which each variable appears with exponent at most one in each term.
- Polynomial degree —
- The largest total degree of a term with a nonzero coefficient in the real multilinear polynomial representing the function.
- Universal constant —
- A fixed number intended to make a bound hold for every function under consideration.
Keywords : Boolean functions · Fourier coefficients · Polynomial degree
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Disproves the proposed square-root bound relating a Boolean function's linear Fourier coefficients to its polynomial degree. For every C > 0, there is a sign-valued Boolean function f with . Thus its total signed correlation with individual input bits can exceed the proposed bound by an arbitrary factor.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Unbounded Violations of the Square-Root Degree Bound
26/09/2026We disprove the Gopalan–Servedio square-root conjecture, even up to an arbitrary constant factor. For every real C > 0, there is a nonconstant Boolean function on a finite sign cube such that Here is the linear Fourier coefficient associated with the ith input, and is the degree of the real multilinear polynomial representing f.