Anthony's conjecture on the number of polynomial threshold functions

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

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

Here (nd)\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 1dn1\le d\le n, as nn\to\infty,

T(n,d)=(2o(1))(2n1m1).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.

Sources & referencesView supporting material

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.