I'm looking at the proof of this lemma:

Lemma For every integer $t>0$, there exists a (proper) polynomial of total degree $(2t)^d$ that differs with $C$ on at most $size(C) 2^{n-t}$ inputs

Where C is a d-depth circuit with OR and NOT gates, and the polynomial is on the field $\mathbb{F}_3=\{-1,0-1\}$. The construction of the polynomial is inductive:

  1. for all inputs $x_i$ we associate to it the variable $x_i$
  2. suppose a gate has input the polynomials $p_1,...,p_k$, let choose random subsets $S_1,...,S_t\subseteq [k]$, and define $q_i=(\sum_{j\in S_i}p_j)^2$, then the output polynomial is defined as $p=1-\prod_{i=1}^t (1-q_i)$

A polynomial is said to be proper if given inputs in $\{0,1\}$ the output is in $\{0,1\}$. What I don't understand is the observation that if all the $p_i$'s are proper that so is $p$.

  • 4
    $\begingroup$ It does not matter whether the $p_i$’s are proper. The output of $q_i$ can only be $0$ or $1$, as these are the only squares modulo $3$ by Fermat’s little theorem (or just by direct verification; however, FLT tells you how to generalize the argument to other finite fields in place of $\mathbb F_3$ if desired). $\endgroup$ – Emil Jeřábek Jun 19 '16 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.