no. 4 · Wednesday 28 October 2026
Logarithmic asymptotics for polynomial threshold functions
Abstract
We count Boolean functions represented as the sign of a real polynomial of bounded degree on the $n$-dimensional cube. We prove that the logarithm of their number is asymptotic to that of the classical hyperplane-arrangement upper bound, uniformly over all degrees, with relative error $O((\log n)^2/n)$. We also obtain sharper additive and relative error estimates in particular degree ranges, including an additive error $O(n^2)$ between the logarithms throughout a small linear degree range and improved bounds just below the central degree. The proof combines probabilistic estimates for Reed–Muller codes with a deletion argument for sets of evaluation vectors, an entropy count, and a sharp-threshold estimate for expected rank deficiency.
- comments
- 39 pages. Revised exposition and organisation, with expanded explanations. Main results and theorem statements unchanged
- fields
- Information Theory, Combinatorics