Using your Head is Permitted

February 2016 solution

This month's riddle was a homage to Noga Alon, who celebrates his 60th birthday this month. The answer to the question was first given in 1993, in a joint paper by Noga Alon and Zoltan Fürdeli, entitled "Covering the Cube by Affine Hyperplanes".

The answer is that n hyperplanes are required.

Consider some set of hyperplanes that cover the 2n-1 desired points but not the origin. These can all be represented by equations of the type

bi1x1+...+binxn+1=0

The affine element can safely be taken to be "+1" as in the equation above, because we know the planes do not cross the origin.

Now, let us multiply all these equations together. If there are k equations, the result will be a polynomial of degree k. Because we know all points in the hypercube other than the origin are covered by the hyperplanes, the value of the polynomial will be zero at each of them. In the origin itself the polynomial has the value 1, as can be ascertained by substituting in the values xi=0 into every hyperplane equation.

Now comes the trick: in every monomial of the polynomial, replace every occurrence of xij by xi. Notably, the values of the polynomial in all hypercube points will not have changed because of this, because both 0j=0 and 1j=1. Note also that the degree of this new polynomial is necessarily at most k.

The new polynomial is easier to handle than the original one, in that we know that it is multilinear: in every monomial, every variable appears with degree at most 1. This makes the total number of monomials at most 2n. Furthermore, it is not difficult to see that the values of the polynomial at the hypercube points determine the values of the polynomial's coefficients uniquely: one can simply solve for them, starting with the value of the free coefficient (from the polynomial's value at the origin), continuing with the value of the linear coefficients (from the polynomial's values at the points whose coordinate sum is 1) and continuing in this way, each time incrementing the degree of the monomials solved for and the sum of the point coordinates.

In fact, the multilinear polynomial is the polynomial whose coefficients are (-1)d, where d is the degree of the monomial.

The important feature of this polynomial is that the coefficient of its degree n monomial is nonzero, meaning that the polynomial itself is of degree n. We have seen that this degree is necessarily at most k, so we have kn, a lower bound on the number of hyperplanes needed.

Actually finding a solution with k=n is easy. One can pick, for example, xi=1 for all i=1,...,n or, as another example, Σ xi=d for d=1,...,n.

The methodology used in this solution is known as the "arithmetical method". It has since been used to attack many fundamental problems in combinatorics.

 

Happy birthday, Noga!

Back to riddle

Back to main page