Let $x_1,x_2,\dots x_n$ be literals.

Let $P(x_1,x_2,\dots,x_n)$ be the parity function.

What is the smallest degree of $f(x_1,x_2,\dots,x_n)\in \mathbb R[x_1,x_2,\dots,x_n]$ that represents $P(x_1,x_2,\dots,x_n)$ (where represents means $f(x_1,x_2,\dots,x_n)$ and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$)?

What is the smallest degree of $r(x_1,x_2,\dots,x_n)\in \mathbb R(x_1,x_2,\dots,x_n)$ (sum of degrees of numerator and denominator) that represents $P(x_1,x_2,\dots,x_n)$ (where represents means $R(x_1,x_2,\dots,x_n)$ and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$)?

Note that $f(x_1,x_2,\dots,x_n)$ and the numerator and denominator of $r(x_1,x_2,\dots,x_n)$ can be multilinear since $x_i^t=x_i$ on $\{0,1\}$.


It will be somewhat easier to replace $\{0,1\}$ with $\{\pm 1\}$, so that the parity function is just $x_1\cdots x_n$. Since this is an affine transformation, it doesn't affect degrees. I'm also assuming that the denominator of a rational function must be non-zero for all $\pm 1$ inputs. Since we only care about $\pm 1$ inputs, we work below over the ideal generated by $\{x_i^2 - 1\}$.

We prove by induction on $n$ that if $P/Q$ represents parity of length $n$ then $PQ = \alpha \prod_{i=1}^n x_i + \cdots$ for some positive $\alpha$, where the dots represent lower degree terms. This implies that $\deg P + \deg Q \geq n$. The claim is clearly true for $n = 0$. Now consider $$\frac{P}{Q} = \frac{x_nP_1+P_2}{x_nQ_1+Q_2}, $$ where $P_1,P_2,Q_1,Q_2$ are over $x_1,\ldots,x_{n-1}$. Substituting $x_n=\pm1$ and applying the induction hypothesis, we deduce that for some $\alpha,\beta > 0$, $$ \begin{align*} (P_1+P_2)(Q_1+Q_2) &= \alpha \prod_{i=1}^{n-1} x_i + \cdots, \\ (P_1-P_2)(Q_1-Q_2) &= -\beta \prod_{i=1}^{n-1} x_i + \cdots. \\ \end{align*} $$ Subtracting both equations, we get $$ P_1 Q_2 + P_2 Q_1 = \frac{\alpha+\beta}{2} \prod_{i=1}^{n-1} x_i + \cdots. $$ Therefore $$ PQ = (x_nP_1+P_2)(x_nQ_1+Q_2) = x_n(P_1Q_2+P_2Q_1) + \cdots = \frac{\alpha+\beta}{2} \prod_{i=1}^n x_i + \cdots. $$

  • $\begingroup$ I vaguely recall having seen this proof somewhere, though I can't remember where. $\endgroup$ – Yuval Filmus Oct 17 '14 at 2:10
  • $\begingroup$ Can your proof somehow help this cstheory.stackexchange.com/questions/27091/…? $\endgroup$ – Turbo Oct 17 '14 at 3:43
  • $\begingroup$ I don't know, you tell me. $\endgroup$ – Yuval Filmus Oct 17 '14 at 3:46
  • $\begingroup$ multiplication just additively adds degrees.... i do not see a way for the problem there. $\endgroup$ – Turbo Oct 17 '14 at 3:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.