WorksComputer Science
Degree Lower Bounds for Symmetric Boolean Functions: Breaking the Prime-Gap Barrier
Abstract
We prove that every nonconstant symmetric Boolean function on variables has exact real polynomial degree at least . This makes progress toward the conjecture of von zur Gathen and Roche that the degree is always at least . The original prime-gap argument of von zur Gathen and Roche yields a degree deficit of using the theorem of Baker, Harman, and Pintz, or using an estimate claimed in a recent preprint. Our bound on the degree deficit improves upon the bound obtainable from the prime-gap approach, even assuming the Riemann hypothesis or Legendre's conjecture. Notably, our proof avoids prime-gap estimates entirely. The proof combines vanishing binomial moments with the arithmetic of linear recurrences. A quantitative form of the integer Hankel determinant method in the Pólya–Carlson theorem forces the function's values on a central interval of Hamming weights to satisfy a short rational recurrence. A second determinant argument bounds the number of characteristic roots near . Through the binomial transform, these roots can then be cancelled by a polynomial test of degree below the deficit. An integer annihilator and contour estimates make the test isolate the first failure of the recurrence, yielding a contradiction with the vanishing-moment conditions. If the recurrence agrees with the function on a sufficiently long interval, arithmetic height bounds instead force a bounded period, which is ruled out by a separate polynomial test. Every numbered result in the paper has been formally verified in Lean~4.