The notion of a threshold function as a Boolean function for which there is a hyperplane in Rn which separates the true vectors from the false vectors of the function is generalized to the case in which more general surfaces may be needed for the separation. A Boolean function is said to be a threshold function of order m if the surface required to separate the true from the false vectors is a polynomial of degree m. The authors have used such functions in the problem of extrapolating partially defined Boolean functions. For each dimension n, there are exactly two threshold functions of order 0 (the constant functions), and it is shown that there are exactly two threshold functions of order n (the parity functions). It is also shown that a Boolean function is a threshold function of order at least m if some sequence of ‘contractions’ and ‘projections’ of it to a (generally) lower dimensional space is a threshold function of order m. This leads to a generalization of a result of threshold function theory that complete monotonicity is a necessary condition for a Boolean function to be a threshold function (or order 0 or 1). A more recent result of threshold function theory, namely that the threshold recognition problem for a general Boolean function is NP-complete is shown to hold true for the order-m recognition problem as well. Also, the characterization of threshold functions in terms of summability is generalized to a characterization of threshold functions of any order. Finally, the authors present the result of a calculation in which the numbers of threshold functions of all orders for dimension n•4 are determined exactly, and statistical estimates are given for n=5, 6, and 7. This leads to the supposition that the vast majority of threshold functions have order near n/2 for n even and (n±1)/2 for n odd, as well as to some more precise conjectures.
