# Proof that the ring-sum expansion of a binary function is unique

I am trying to understand a proof that the ring-sum expansion of a binary function is unique. The proof is as follows.

Proof. By induction on the number of inputs $n$. For $n=1$, $f(x)=0$ or $f(x)=1$ or $f(x)=x$ or $f(x)=\bar{x}=1\bigoplus x$. For all it can be seen that the ring sum expansion is unique. Assume that for any arbitrary function of $n-1$ arguments, the RSE is unique.

Consider: $f(x_1, ..., x_{n})=g(x_2,...,x_n)\bigoplus x_1h(x_2,...,x_n)$. By induction both g and h have unique RSE's and therefore the RSE $g(x_2,...,x_n)\bigoplus xh(x2,...x_n)$ is also unique.

The only thing about this proof that I do not understand is where $f(x_1,...,x_n)=g(x_2,...,x_n)\bigoplus xh(x_2,...,x_n)$ came from. Could anyone shed some light on that for me? It could just be that its late and my brain is not working but I've been staring at it for a while now.

-
The ring sum expansion is a normal form that is the sum (exclusive or) of products (ands) of the inputs of the function. No other operation is allowed. It can be seen that every binary function has one by taking the disjunctive normal form, replacing the or's with xor's, and replacing all occurances of not x_i with x_i xor 1, then simplifying. en.wikipedia.org/wiki/Disjunctive_normal_form – Deddryk Sep 16 '11 at 6:04
A clarification: So, this question is only about proving that there is at most 1 RSE? – Srivatsan Sep 16 '11 at 6:06
I've actually just figured it out but I am not allowed to post an answer to my own question. Basically, the terms that involve x_1 are grouped together, and x_1 is factored out to form x_1h(x2...xn), and the rest of the terms form g(x2...xn) – Deddryk Sep 16 '11 at 6:06
Yes, it is proving that every function has a unique RSE – Deddryk Sep 16 '11 at 6:06
@John: If by "I am not allowed to post an answer to my own question" you mean a restriction due to lack of reputation points: No, one point is enough to answer questions. If you mean that you're not supposed to answer your own question: No, this is explicitly encouraged. – joriki Sep 16 '11 at 6:26

Write out $f(x_1,\dots,x_n)$ in disjunctive normal form and collect separately the terms in $x_1$ and the terms in $\overline{x_1}$: you get an expression of the form $x_1f_+(x_2,\dots,x_n)\lor \overline{x_1}f_{-}(x_2,\dots,x_n)$. Now do your replacement to get \begin{align*} &x_1f_+(x_2,\dots,x_n)\bigoplus (1\bigoplus x_1)f_{-}(x_2,\dots,x_n) =\\ &x_1f_+(x_2,\dots,x_n)\bigoplus f_{-}(x_2,\dots,x_n) \bigoplus x_1f_{-}(x_2,\dots,x_n) =\\ &x_1\left(f_+(x_2,\dots,x_n)\bigoplus f_{-}(x_2,\dots,x_n)\right)\bigoplus f_{-}(x_2,\dots,x_n), \end{align*} and let $g = f_{-}$ and $h = f_+ \bigoplus f_{-}$.
The place in the proof that John Stephanos was having difficulty with is missing the subscript $1$ on $x$ where it says $g(x_2, \ldots, x_n) \oplus xh(x_2), \ldots, x_n)$, and when the subscript is inserted (as in his later remarks), the difficulty disappears as he discovered for himself. But if the proof by induction is felt to be "sneaky", here is a different one which sets up a one-one correspondence between functions and RSEs.
There are $2^{2^n}$ different functions from $\{0,1\}^n$ to $\{0,1\}^n$. Given the disjunctive normal form of such a function, there is a mechanical procedure for obtaining the RSE for the function. Now, an RSE is a polynomial in $n$ variables $x_1, \ldots, x_n$, and any such polynomial can be expressed as $$f(x_1, \ldots, x_n) = a_0 \oplus \sum_i a_ix_i \oplus \sum_{i_1 \neq i_2}a_{i_1,i_2}x_{i_1}x_{i_2} \oplus \ldots \oplus a_{1,\ldots, n}x_1\cdots x_n$$ where the $a$'s have value $0$ or $1$. Since $x_i^2 = x_i$, each variable need have degree $1$ at most. Now, since there is $1 = \binom{n}{0}$ term of degree $0$, $n$ terms of degree $1$, $\binom{n}{2}$ terms of degree $2$, $\ldots$, $\binom{n}{n} = 1$ terms of degree $n$, we see that there are $\sum_{i=0}^n \binom{n}{i} = 2^n$ terms in the polynomial. Since each term has a coefficient that has value $0$ or $1$, there are $2^{2^n}$ different polynomials. Thus, there are exactly as many polynomials as there are functions. Each polynomial is the RSE of some function whose disjunctive normal form can be obtained by a reverse mechanical procedure: multiply each term of degree less than $n$ by terms of the form $(x_i \oplus \bar{x_i}) = 1$ where $x_i$ is a variable missing in that term (e.g., if $n=4$, then the term $x_2x_4$ becomes $(x_1\oplus \bar{x_1})x_2(x_3\oplus \bar{x_3})x_4$), multiply out to get terms of degree $n$ in which each $x_i$ occurs once (with or without complementation), and replace all $\oplus$ by $\vee$. So we have a one-one correspondence between functions and RSEs, and each function has a unique RSE.