Rational function for Parity function

Question

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\}$.

score 4 · Accepted Answer · answered Oct 17 '14 at 00:14

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. $$

I vaguely recall having seen this proof somewhere, though I can't remember where. — Yuval Filmus, Oct 17 '14 at 02:10
Can your proof somehow help this http://cstheory.stackexchange.com/questions/27091/candidate-boolean-function-with-efficient-rational-representation-compared-to-po? — Turbo, Oct 17 '14 at 03:43
multiplication just additively adds degrees.... i do not see a way for the problem there. — Turbo, Oct 17 '14 at 03:58

Rational function for Parity function

1 Answers1