Degree Lower Bounds for Symmetric Boolean Functions: Breaking the Prime-Gap Barrier
Xiaoming Sun, Chengu Wang
cs.CC
Nov 19, 2026 · v1
math.CO
TL;DR
Every numbered theorem, lemma, corollary, proposition and definition is formalized and checked in Lean 4 with Mathlib, with a public GitHub repository.
Abstract
We prove that every nonconstant symmetric Boolean function on $n$ variables has exact real polynomial degree at least $n-O(n^{1/3}(\log n)^{2/3})$. This makes progress toward the conjecture of von zur Gathen and Roche that the degree is always at least $n-3$. The original prime-gap argument of von zur Gathen and Roche yields a degree deficit of $O(n^{0.525})$ using the theorem of Baker, Harman, and Pintz, or $O(n^{0.52})$ using an estimate claimed in a recent preprint. Our $\widetilde{O}(n^{1/3})$ bound on the degree deficit improves upon the $\widetilde{O}(\sqrt{n})$ 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 $-1$. 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.
Problem
The question is how far the exact real polynomial degree of a nonconstant symmetric Boolean function on n variables can fall below n. Von zur Gathen and Roche conjectured a deficit of at most 3. Prime-gap arguments give a deficit of O(n^0.525), and no better than about sqrt(n) even under the Riemann hypothesis.
Approach
Vanishing binomial moments and a quantitative integer Hankel determinant method (Pólya–Carlson) force the sign word to satisfy a short rational recurrence on a central interval. A second determinant argument bounds the number of characteristic roots near -1, which are then cancelled via the binomial transform by a low-degree test polynomial. Contour estimates and an integer annihilator isolate the first failure of the recurrence. A separate argument handles the periodic, long-agreement case. All numbered results are formalized in Lean 4 with Mathlib.
Results
Every nonconstant symmetric Boolean function has degree at least n - O(n^{1/3}(log n)^{2/3}), and the proof avoids prime-gap estimates. All numbered results are machine-checked in Lean 4, although the formal proofs do not always follow the written ones.