PreprintarXiv licencearXiv
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(n2) 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.
Related
- Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
- Distance and resistance on random series-parallel graphs: logarithmic speeds and near-critical asymptotics
- Asymptotics for partition functions of random normal matrix models with singularities
- Bernstein and Stieltjes properties of some functions involving logarithmic functions
- Operator Michelson Contrast: Logarithmic Parametrisation, Subadditivity, and a Sharp Noncommutativity Threshold
BibTeX
@misc{anthony2026logarithmic,
title = {{Logarithmic asymptotics for polynomial threshold functions}},
author = {Martin Anthony},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34378},
eprint = {2610.34378},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34378},
}
RIS
TY - UNPB
TI - Logarithmic asymptotics for polynomial threshold functions
AU - Martin Anthony
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.34378
UR - https://arxiv.org/abs/2610.34378
AB - 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.
ER -