A polynomial threshold function is a Boolean function obtained by thresholding a real polynomial 
on 
. The function is
when 
and 
when 
. It is said to have degree at most 
when such a representation exists with a real
polynomial of total degree at most 
(O'Donnell 2021, p. 115). For 
, for example, 
is represented by 
. Taking 
of total degree at most 1
gives linear threshold functions.
For enumeration, let 
count the distinct functions of degree at most 
on the Boolean cube, and put 
.
The hyperplane arrangement bound is 
, where 
.
Anthony (2026) proved
 |
for all sufficiently large 
,
uniformly over 
,
with an absolute constant 
.
This compares logarithms of the counts.
