Bounds for the average degree-k monomial density of Boolean functions

For a Boolean function f represented in algebraic normal form (i.e. as a multivariate polynomial function over F2) we consider the density of monomials of degree k in f, for each degree k, i.e. the number of monomials of degree k that appear in f, normalized by the total number of possible monomials of degree k. We then average this number over all functions which are affine equivalent to f; we call the resulting quantity, denoted by addk(f), the average degree-k monomial density of f. We defined this quantity in our previous work, and showed it is closely related to a probabilistic test we introduced for deciding whether deg(f) < k. In this paper we give lower and upper bounds for addk(f) for polynomials of any degree d (only the particular case d = k having been dealt with in our previous work). There are several consequences of these bounds. Firstly, the deg(f) < k probabilistic test is guaranteed to have high accuracy when the actual degree of f is not much higher than k. Secondly, it answers negatively the question: does there exist a function f which has no monomials of a particular degree k (with k < deg(f)) and, moreover, it still has no monomials of degree k after applying any affine invertible change of coordinates to f. Thirdly, while the average of addk(f) over all n-variable functions f of a fixed degree d > k is equal to 0.5, the distribution of the values is somewhat surprising; when k ≤ n − 10 and n ≥ 20, low values of addk(f) exist (reaching approximately 1/2d−k ), but there are no values higher than around 0.5005.