New Upper Bounds on the Average PTF Density of Boolean Functions

A Boolean function f : {1, - 1}(n) -> {1, - 1} is said to be sign-represented by a real polynomial p : R-n -> R if sgn(p(x)) = f (x) for all x is an element of {1, - 1}(n). The PTF density of f is the minimum number of monomials in a polynomial that sign-represents f. It is well known that every n-variable Boolean function has PTF density at most 2(n). However, in general, less monomials are enough. In this paper, we present a method that reduces the problem of upper bounding the average PTF density of n-variable Boolean functions to the computation of (some modified version of) average PTF density of k-variable Boolean functions for small k. By using this method, we show that almost all n-variable Boolean functions have PTF density at most (0.617)2(n), which is the best upper bound so far.