Paperlane

no. 4 · Wednesday 28 October 2026

Logarithmic asymptotics for polynomial threshold functions

Martin Anthony

math.IT · v2 · 39 pp

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
pdf ↗ page arXiv:2610.34378 ↗