I know that trivially the OR function on variables can be represented exactly by the polynomial as such: , which is of degree .
Mas como eu poderia mostrar, o que parece óbvio, que se é um polinômio que representa exatamente a função OR (então ∀ x ∈ { 0 , 1 } n : p ( x ) = ⋁ n i = 1 x i ), então deg ( p ) ≥ n ?
Respostas:
Claim: The polynomials{∏i∈Sxi:S⊆[n]} , as functions {0,1}n→R form a basis of for the space of all functions {0,1}n→R .
Proof: We first show that the polynomials are linearly independent. Suppose thatf=∑ScS∏i∈Sxi=0 for all (x1,…,xn)∈{0,1}n . We prove by (strong) induction on |S| that cS=0 . Suppose that cT=0 for all |T|<k , and let us be given a set S of cardinality k . For all T⊂S we know by induction that cT=0 , and so 0=f(1S)=cS , where 1S is the input which is 1 on the coordinates of S . □
The claim shows that the multilinear representation of a functionf:{0,1}n→{0,1} is unique (indeed, f doesn't even have to be 0/1 -valued). The unique multilinear representation of OR is 1−∏i(1−xi) , which has degree n .
fonte
Letp be a polynomial such that for all x∈{0,1}n , p(x)=OR(x) . Consider the symmetrization of the polynomial p :
Symmetrization is often used in the study of the approximate degree of boolean functions and quantum query complexity. See, for example, http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf.
fonte
Yuval and Henry have given two different proofs of this fact. Here's a third proof.
First, as in Yuval's answer we restrict our attention to multilinear polynomials. Now you have already exhibited a degreen multilinear polynomial that equals the OR function. Now all we need to show is that this polynomial is unique, and hence you have found the one and only representation of the OR function as a polynomial. Consequently, its degree is n .
Claim: If two multilinear polynomials p and q are equal on the hypercube, then they are equal everywhere.
Proof: Let r(x) = p(x) - q(x), and we know that r(x)=0 for all x in{0,1}n . We want to show that r(x) is identically zero. Toward a contradiction, assume it is not, and pick any monomial in r with a nonzero coefficient that has minimal degree. Set all the variables outside this monomial to be 0 and all the variables in this monomial to be 1. r(x) is nonzero on this input, but this input is Boolean, which is a contradiction.
fonte