Let with Discrete Fourier Transform on the Biased Cube By Discrete Fourier Transform inversion formula:

The degree of is

Note that the inversion formula lets us expand the domain of from to , as a multilinear (actually multiaffine) function. The degree of is then the same as the degree of this multilinear polynomial.

Lemma

For every there is a unique multilinear such that .

Proof

Existence is clear by the inversion formula. Now suppose is multilinear and vanishes on . Show this by induction on . If the result is clear. Now assume the result for and let vanish on . Then for all we can write

Also so is multilinear. Thus write

Let . Then clearly so by induction hypothesis . Now . Setting , we find that .