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

Question

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.

Answer 1

If I understand your description of the RSE correctly, they seem to have done something like this:

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_{-}$.

Answer 2

The place in the proof that Deddryk 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.