# Sums of truth-table values mod 2 range over all truth tables

Let $A=\lbrace0,1\rbrace$. There are 16 distinct functions $f_i:A^2\to A$.

Choose a permutation $P=\left(a_1,\ldots,a_4\right)$ of the elements of $A^2$, and for each $i$ consider the ordered quadruple $\left(\sum_{j=1}^nf_i(a_j)\pmod2\right)_{n=1}^4\in A^4$. Clearly this quadruple is $f_k(P)$ for some $k$. I claim that as $i$ ranges over $\left(1,\ldots,16\right)$ we obtain all sixteen $f_k$ this way.

(My proof is by inspecting a single choice of $P$ — which I did manually — and handwavingly claiming that the choice of $P$ doesn't matter because everything's symmetric.)

Question: Why is this true? (Something (a proof not by inspection or an explanation) that generalizes would be most welcome.)

-

## 2 Answers

Suppose that $f_i$ and $f_k$ result in the same function. Then \begin{align*} f_i(a_1)&\equiv f_k(a_1)\pmod2,\\ f_i(a_1)+f_i(a_2)&\equiv f_k(a_1)+f_k(a_2)\pmod2,\\ f_i(a_1)+f_i(a_2)+f_i(a_3)&\equiv f_k(a_1)+f_k(a_2)+f_k(a_3)\pmod2,\text{ and}\\ f_i(a_1)+f_i(a_2)+f_i(a_3)+f_i(a_4)&\equiv f_k(a_1)+f_k(a_2)+f_k(a_3)+f_i(a_4)\pmod2,\\ \end{align*} and an easy reduction from the top down shows that $f_i(a_j)\equiv f_k(a_j)\pmod2$ for $j=1,2,3,4$, i.e., that $f_i=f_k$. The map is therefore injective, and since the set of functions is finite, it must be a bijection. Thus, you do get all $16$ functions.

-
Duh. I should have seen that. Thanks. – msh210 Oct 25 '11 at 15:05

The space of $f_i$'s is a 4-dimensional vector space over $\mathbb F_2$. Each permutation P gives rise to a linear transformation of this vector space whose matrix is $$\pmatrix{1&1&1&1\\0&1&1&1\\0&0&1&1\\0&0&0&1}$$ with respect to appropriate bases. The determinant of this matrix is clearly $1$, so it is invertible, and therefore the transformation is bijective.

-
"The determinant of this vector"? You mean matrix... and aren't permutations invertible to begin with? The question is why is every permutation is a linear permutation, this is the nontrivial part. – Asaf Karagila Oct 24 '11 at 23:24
Yes, I meant matrix. The permutation is invertible yes -- and to be completely precise, its permutation matrix should probably be multiplied into the one I show from the right -- but my point is that the strange sum over values of $f_i$ (which is not a priori a permutation) is also invertible. – Henning Makholm Oct 24 '11 at 23:27
Of course, however the question remains (as in my previous comment) why is that every permutation is actually a linear transformation? – Asaf Karagila Oct 24 '11 at 23:28
Because it acts by multiplication with its permutation matrix, and matrix multiplication is linear. – Henning Makholm Oct 24 '11 at 23:30
Right, but you're not answering my question. If the permutation is linear then of course it acts by multiplication with its matrix. However why is every permutation of this vector space is linear? This is the question left open in your answer. – Asaf Karagila Oct 24 '11 at 23:32