Anthony's conjecture on the number of polynomial threshold functions

About 8 years old · traced to

Let T(n,d)T(n,d) be the number of nn-variable polynomial threshold functions of degree dd, and let

m=(n≤d).m=\binom{n}{\le d}.

Here (n≤d)\binom{n}{\le d} denotes the number of monomials in at most dd variables’ degree contribution, including the constant term. Anthony's conjecture. For all degrees 1≤d≤n1\le d\le n, as n→∞n\to\infty,

T(n,d)=(2−o(1))(2n−1≤m−1).T(n,d)=\left(2-o(1)\right)\binom{2^n-1}{\le m-1}.

The conjecture would make the paper's upper bound asymptotically sharp when the degree grows rapidly, including degrees linear in nn; its resolution is not given in the supplied text.

References

Primary source

Pierre Baldi and Roman Vershynin, “Polynomial threshold functions, hyperplane arrangements, and random tensors”, arXiv:1803.10868 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.