We present methods for computing the distance from a Boolean polynomial on$m$variables of degree$m-3$(i.e., a member of the Reed–Muller code$RM(m-3, m)$) to the space of lower-degree polynomials ($RM(m-4, m)$). The methods give verifiable certificates for both the lower and upper bounds on this distance. By applying these methods to representative lists of polynomials, we show that the covering radius of$RM(4,8)$in$RM(5,8)$is 26 and the covering radius of$RM(5,9)$in$RM(6,9)$is between 28 and 32 inclusive, and we get improved lower bounds for higher$m$. We also apply our methods to various polynomials in the literature, thereby improving the known bounds on the distance from 2-resilient polynomials to$RM(m-4, m)$.

Abstract Let X and Y be uncountable Polish spaces. We show in ZF that there is a coanalytic subset P of X × Y with countable sections which cannot be expressed as the union of countably many partial coanalytic, or even PCA = , graphs. If X = Y = ωω, P may be taken to be . Assuming stronger set theoretic axioms, we identify the least pointclass such that any such coanalytic P can be expressed as the union of countably many graphs in this pointclass. This last result is extended (under suitable hypotheses) to all levels of the projective hierarchy.