1
$\begingroup$

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 2

1

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.

  • 0
    Duh. I should have seen that. Thanks.2011-10-25
0

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.

  • 0
    I don't _c$a$re_, for this purpose, whether permutations are linear. The property to be proven depends on some arbitrary permutation P, but it does not treat that permutation as a linear map, and I don't depend on its being linear in my argument.2011-10-24