betaFeedback

WorksComputer Science

Degree Lower Bounds for Symmetric Boolean Functions: Breaking the Prime-Gap Barrier

Abstract

We prove that every nonconstant symmetric Boolean function on nn variables has exact real polynomial degree at least n−O(n1/3(log⁡n)2/3)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−3n-3. The original prime-gap argument of von zur Gathen and Roche yields a degree deficit of O(n0.525)O(n^{0.525}) using the theorem of Baker, Harman, and Pintz, or O(n0.52)O(n^{0.52}) using an estimate claimed in a recent preprint. Our O~(n1/3)\widetilde{O}(n^{1/3}) bound on the degree deficit improves upon the O~(n)\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-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.

Paper details

vlnc:W_f3mf5fm2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…