Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 –  John Stephanos 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) –  John Stephanos Sep 16 '11 at 6:06
    
Yes, it is proving that every function has a unique RSE –  John Stephanos 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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
Yeah, that;s basically it, although you could skip the DNF because it is proven that an RSE exists for f already and just factor x_1 out from the terms that involve it. It's a sneaky little proof. –  John Stephanos Sep 16 '11 at 6:33

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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