Let $F = \operatorname{GF}(2^n)$ be a finite field. Define a permutation $\phi:F \rightarrow F$ by the formula $$ \phi(x) = x^{-1}, \ x\neq 0; \ \phi(0) =0. $$ We say that a permutations $\psi$ of $F$ is linear if $\psi(x+y) = \psi(x)+\psi(y)$.

It is not hard to see that all automorphisms $\sigma_k: x\rightarrow x^{2^k}$ are commuting with $\phi$. That is in the group $S(F)$ of permutations of $F$ we have the following equality: $$ \phi\cdot \sigma_k = \sigma_k\cdot\phi. $$

My question. Are there other linear permutations of $F$, commuting with $\phi$?


The answer is no: a linear transformation of $F$ which commutes with $\phi$ is an automorphism of $F$.

This is a seemingly inelegant but simple argument.

Any map $\psi: F \rightarrow F$ can be represented uniquely as a polynomial $P_\psi (x) = \sum a_i x^i$ of degree less than $2^n$, with each $a_i \in F$. If the map $\psi$ is linear, then in fact $a_i =0$ for all $i\neq 2^j$, so that the degree of $P_\psi$ is in fact at most $2^{n-1}$. Indeed, there are $2^{n^2}$ linear transformations of $F$ and the same number of polynomials of the form $\sum_{0 \le j \le n - 1}b_jx^{2^j}$, all of which induce linear transformations.

Let $Q_\psi(x) = x^{2^{n-1}} P_\psi(\frac{1}{x})$ as polynomials; in other words, $Q_\psi$ is the "reverse" of $P_{\psi}$. Note that the degree of $Q_{\psi}$ is also at most $2^{n-1}-1$, because the coefficient of $1$ in $P_\psi$ is $0$.

Your condition is equivalent to the equation $(P_\psi(x))^{-1} = P_\psi(x^{-1})$ in value for any $x \neq 0$. Multiplying it out so everything is a polynomial, it's equivalent to $P_\psi(x)Q_\psi(x) = x^{2^{n-1}}$ in value for all $x$ including $0$. But two polynomials are equal in value iff they are equivalent modulo $x^{2^n}-x$. Both of these polynomials are of smaller degree than $2^n$, so they must in fact be equal. Unique factorization therefore says that $P_{\psi}$ must be a monomial, with coefficient $a$ such that $a^2=1$. As we are in characteristic $2$, this is unique: $a=1$.

I wouldn't be surprised if there were a more elegant answer based on automorphisms, but I don't see it immediately.

I figured out an answer based on multiplication-preserving endomorphisms that works generally in any characteristic other than $2$, and for any finite field (or any field in which every element is a square) in characteristic $2$.

The commutation equation says that for any $x$, we have $\psi(x^{-1}) = \psi(x)^{-1}$. Assume $x, y, x + y \neq 0$. Let's apply it to $x^{-1} + y^{-1}$:

$\psi((x^{-1} + y^{-1})^{-1}) = (\psi(x^{-1} + y^{-1}))^{-1}$

$\psi(\frac{xy}{x + y}) = (\psi(x^{-1}) + \psi(y^{-1}))^{-1}$ (using linearity)

$\psi(\frac{xy}{x + y}) = (\psi(x)^{-1} + \psi(y)^{-1})^{-1} = \frac{\psi(x) \psi(y)}{\psi(x) + \psi(y)}$

Multiplying it out, we get:

$\psi(\frac{xy}{x + y}) (\psi(x + y)) = \psi(x) \psi(y)$

Choose $y = y' - x$. Our conditions become $x, y', y'-x \neq 0$. Then

$\psi(\frac{x (y' - x)}{y'}) \psi(y') = \psi(x) \psi(y' - x)$

Using linearity and canceling terms, we get:

$\psi(\frac{x^2}{y'})\psi(y') = \psi(x)^2$

From here, this separates into two proofs: one for characteristic $2$ fields, and one for any field not of characteristic $2$.

For characteristic $2$ fields:

$\psi(z z')^2 \psi(1)^2 = \psi(z^2) \psi(1) \psi(z'^2) \psi(1) = \psi(z)^2 \psi(z')^2$ for any $z, z'$.

In fields of characteristic $2$, square roots are unique, if they exist. Therefore:

$\psi(z z') \psi(1) = \psi(z) \psi(z')$

For characteristic not $2$:

$\psi(x^2)\psi(1) = \psi(x)^2$ for any $x \neq 0, 1$. However, for both of those cases, this is obvious, so this is true for any $x$.

Let $x = z + z'$. Then: $\psi((z + z')^2) \psi(1) = \psi(z + z') \psi(z + z')$. We can again cancel terms and divide by $2$ (except in characteristic $2$) to get:

$\psi(z z') \psi(1) = \psi(z) \psi(z')$.

Here, the proofs reunite.

In other words, $\psi$ must be a multiplication-preserving morphism up to scaling by $\psi(1)$. But $\psi(1) = \psi(1^{-1}) = \psi(1)^{-1}$, so $\psi(1) = \pm 1$. In characteristic $2$, these are the same, and the only answers are multiplication-preserving morphisms; more generally, negation (and composing negation with a multiplication-preserving morphism) is also possible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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