arXiv:2610.34378 · v2

Logarithmic asymptotics for polynomial threshold functions

首次提交 2026-10-25 23:34

版本更新 2026-10-27 17:49

雷达观测 2026-10-29 00:35

摘要

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.

作者备注：39 pages. Revised exposition and organisation, with expanded explanations. Main results and theorem statements unchanged