Logarithmic asymptotics for polynomial threshold functions
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.34378
curl -X POST /api/v1/records/arxiv/2610.34378/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.34378/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'