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

<p>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 &gt; 0$,
$$
\begin{align*}
(P_1+P_2)(Q_1+Q_2) &amp;= \alpha \prod_{i=1}^{n-1} x_i + \cdots, \\
(P_1-P_2)(Q_1-Q_2) &amp;= -\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. $$</p>

CC BY-SA 3.0
2014-10-17T02:10:57.157Z
I vaguely recall having seen this proof somewhere, though I can't remember where.
Yuval Filmus
CC BY-SA 3.0
2014-10-17T03:43:17.897Z
Can your proof somehow help this http://cstheory.stackexchange.com/questions/27091/candidate-boolean-function-with-efficient-rational-representation-compared-to-po?
Turbo
CC BY-SA 3.0
2014-10-17T03:46:16.730Z
I don't know, you tell me.
Yuval Filmus
CC BY-SA 3.0
2014-10-17T03:58:23.813Z
multiplication just additively adds degrees.... i do not see a way for the problem there.
Turbo
CC BY-SA 3.0
2014-10-17T00:14:27.373Z
2014-10-17T00:14:27.373Z
Yuval Filmus
<p>Let $x_1,x_2,\dots x_n$ be literals.</p>

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

<p>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\}$)?</p>

<p>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\}$)?</p>

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

<boolean-functions>
Rational function for Parity function
Turbo
# Rational function for Parity function

(Asked by: username_0 on 2014-10-16)

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

**Tags:** boolean-functions


---

## 1 answers

### Answer by username_1 on 2014-10-17. Score: 4 | Accepted answer

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

> **Comments:**
> **username_1**: I vaguely recall having seen this proof somewhere, though I can't remember where.  
> **username_0**: Can your proof somehow help this http://cstheory.stackexchange.com/questions/27091/candidate-boolean-function-with-efficient-rational-representation-compared-to-po?  
> **username_1**: I don't know, you tell me.  
> **username_0**: multiplication just additively adds degrees.... i do not see a way for the problem there.  

---

