Représenter OR avec des polynômes

Je sais que trivialement la fonction OR sur $n$ variables $x_1,\ldots, x_n$ peut être représentée exactement par le polynôme $p(x_1,\ldots,x_n)$ comme tel: $p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)$ , qui est de degré $n$ .

Mais comment pourrais-je montrer, ce qui semble évident, que si $p$ est un polynôme qui représente exactement la fonction OR (donc $\forall x \in \{0,1\}^n : p(x) = \bigvee_{i = 1}^n x_i$ ), alors $\deg(p) \ge n$ ?

Soit $f\colon \{0,1\}^n \to \{0,1\}$ une fonction booléenne. S'il a une représentation polynomiale $P$ alors il a une représentation polynomiale multilinéaire $Q$ de degré $\deg Q \leq \deg P$ : il suffit de remplacer toute puissance $x_i^k$ , où $k \geq 2$ , par $x_i$ . Nous pouvons donc limiter notre attention aux polynômes multilinéaires.

Réclamation: Les polynômes , en tant que fonctions { 0 , 1 } n → R forment une base de l'espace de toutes les fonctions { 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}$

Preuve: Nous montrons d'abord que les polynômes sont linéairement indépendants. Supposons que pour tous ( x 1 , … , x n ) ∈ { 0 , 1 } n . Nous prouvons par (forte) induction sur | S | que c S = 0 . Supposons que c T = 0 pour tous | $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$ , et on nous donne un ensemble S de cardinalité k . Pour tous T ⊂ S on sait par induction que c T = 0 , et si 0 = f ( 1 S ) = c S , où 1 S est l'entrée qui est une des coordonnées 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 demande montre que la représentation multilinéaire d'une fonction est unique ( en effet, f n'a même pas être 0 / 1 -Évaluées). La représentation multilinéaire unique de OR est 1 - ∏ i ( 1 - x i ) , qui a le degré n .$f\colon \{0,1\}^n \to \{0,1\}$$f$$0/1$$1-\prod_i(1-x_i)$$n$

Soit un polynôme tel que pour tout x ∈ { 0 , 1 } n , p ( x ) = O R ( x ) . Considérons la symétrisation du polynôme p : q ( k ) = $p$$x\in \{0,1\}^n$$p(x) = \sf{OR}(x)$$p$Notez que, comme la fonction OU est une fonction booléenne symétrique, nous avons cela pourk=1,2,…,n,q(k)=1etq(0)=0. Puisqueq-1est un polynôme non nul, et qu'il a au moinsn0, il doit avoir un degré au moinsn. Par conséquent,

La symétrisation est souvent utilisée dans l'étude du degré approximatif des fonctions booléennes et de la complexité des requêtes quantiques. Voir, par exemple, http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf .

Yuval et Henry ont donné deux preuves différentes de ce fait. Voici une troisième preuve.

$n$$n$

Affirmation: Si deux polynômes multilinéaires p et q sont égaux sur l'hypercube, alors ils sont égaux partout.

$\{0,1\}^n$