Representando OR com polinômios

23

I know that trivially the OR function on n variables x1,,xn can be represented exactly by the polynomial p(x1,,xn) as such: p(x1,,xn)=1i=1n(1xi), which is of degree n.

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 ?px{0,1}n:p(x)=i=1nxideg(p)n

matthon
fonte
1
Are you talking about real polynomials? Or polynomials modulo 2? If you want to talk about modulo 6 (or other composite numbers), then the question becomes more interesting.
Igor Shinkar

Respostas:

30

f:{0,1}n{0,1}PQdegQdegPxikk2xi. So we can restrict our attention to multilinear polynomials.

Claim: The polynomials {iSxi:S[n]}, as functions {0,1}nR form a basis of for the space of all functions {0,1}nR.

Proof: We first show that the polynomials are linearly independent. Suppose that f=ScSiSxi=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 TS 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 function f:{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 1i(1xi), which has degree n.

Yuval Filmus
fonte
26

Let p be a polynomial such that for all x{0,1}n, p(x)=OR(x). Consider the symmetrization of the polynomial p:

q(k)=1(nk)x:|x|=kp(x).
Note that, since the OR function is a symmetric boolean function, we have that for k=1,2,,n, q(k)=1, and q(0)=0. Since q1 is a non-zero polynomial, and it has at least n 0's, it must have degree at least n. Therefore, p must also have degree n.

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.

Henry Yuen
fonte
It seems to me that in order for your proof to work, you need to show that the degree of q is at most the degree of p. This is not clear to me. How do you show this?
matthon
Let d = deg(p). Then q is a sum of degree d polynomials, hence the degree of q is at most d.
Henry Yuen
3

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 degree n 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.

Robin Kothari
fonte