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
    "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.2011-10-24
  • 0
    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.2011-10-24
  • 0
    Of course, however the question remains (as in my previous comment) why is that every permutation is actually a linear transformation?2011-10-24
  • 0
    Because it acts by multiplication with its permutation matrix, and matrix multiplication is linear.2011-10-24
  • 0
    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.2011-10-24
  • 0
    Every permutation of basis vectors for _any_ vector space is a linear operation. This is a general fact, not particular to this specific space.2011-10-24
  • 0
    We're running in a circle, aren't we... :-)2011-10-24
  • 0
    Possibly yes. I cannot understand what your objection is. It is not even important in this question that a permutation is linear. We're simply given the ordered set $(a_1,a_2,a_3,a_4)$, and with this set as a basis for $A^2\to A$, the matrix of the mapping defined in the question is as in my answer.2011-10-24
  • 0
    There are $2^\frak c$ many permutations of $\mathbb R$ as a set, but only $\frak c$ are linear as a $1$-dim. vector space, my question is how do you deduce that *all* the permutations of $A^2$ are linear.2011-10-24
  • 0
    I don't _care_, 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