Representando OR con polinomios

Sé que trivialmente la función OR en $n$ variables $x_1,\ldots, x_n$ puede representarse exactamente por el polinomio $p(x_1,\ldots,x_n)$ como tal: $p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)$ , que es de grado $n$ .

Pero, ¿cómo podría mostrar, lo que parece obvio, que si $p$ es un polinomio que representa la función OR exactamente (entonces $\forall x \in \{0,1\}^n : p(x) = \bigvee_{i = 1}^n x_i$ ), entonces $\deg(p) \ge n$ ?

Sea una función booleana. Si tiene una representación polinomial P, entonces tiene una representación polinomial multilineal Q de grado deg Q ≤ deg P : simplemente reemplace cualquier potencia x k i , donde k ≥ 2 , por x i . Entonces podemos restringir nuestra atención a polinomios multilineales.$f\colon \{0,1\}^n \to \{0,1\}$$P$$Q$$\deg Q \leq \deg P$$x_i^k$$k \geq 2$$x_i$

Reclamación: Los polinomios , como las funciones de { 0 , 1 } n → R formar una base de por el espacio de todas las funciones de { 0 , 1 } n → R .$\{ \prod_{i \in S} x_i : S \subseteq [n] \}$$\{0,1\}^n \to \mathbb{R}$$\{0,1\}^n \to \mathbb{R}$

Prueba: Primero mostramos que los polinomios son linealmente independientes. Suponga que para todos ( x 1 , … , x n ) ∈ { 0 , 1 } n . Probamos por (fuerte) inducción en | S | que c S = 0 . Supongamos que c T = 0 para todos | $f = \sum_S c_S \prod_{i \in S} x_i = 0$$(x_1,\ldots,x_n) \in \{0,1\}^n$$|S|$$c_S = 0$$c_T = 0$ , y se nos dará un conjunto S de cardinalidad k . Para todos T ⊂ S sabemos por inducción que c T = 0 , y así 0 = f ( 1 S ) = c S , donde 1 S es la entrada que es 1 de las coordenadas de S .$|T| < k$$S$$k$$T \subset S$$c_T = 0$$0 = f(1_S) = c_S$$1_S$$1$$S$$~\qquad\square$

La reclamación muestra que la representación multilineal de una función es único (de hecho, f no siquiera tiene que ser 0 / 1 -valued). La representación multilineal única de OR es 1 - ∏ i ( 1 - x i ) , que tiene un grado n .$f\colon \{0,1\}^n \to \{0,1\}$$f$$0/1$$1-\prod_i(1-x_i)$$n$

Sea un polinomio tal que para todo x ∈ { 0 , 1 } n , p ( x ) = O R ( x ) . Considere la simetrización del polinomio p : q ( k ) = $p$$x\in \{0,1\}^n$$p(x) = \sf{OR}(x)$$p$Tenga en cuenta que, dado que la función OR es una función booleana simétrica, tenemos que parak=1,2,...,n,q(k)=1yq(0)=0. Comoq-1es un polinomio distinto de cero y tiene al menosn0, debe tener un grado de al menosn. Por lo tanto,

La simetrización se usa a menudo en el estudio del grado aproximado de funciones booleanas y la complejidad de la consulta cuántica. Ver, por ejemplo, http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf .

Yuval y Henry han dado dos pruebas diferentes de este hecho. Aquí hay una tercera prueba.

$n$$n$

Reclamación: Si dos polinomios multilineales p y q son iguales en el hipercubo, entonces son iguales en todas partes.

$\{0,1\}^n$