11
$\begingroup$

Let $S$ be a finite group with operator + and $\pi$ be a permutation on $S$. Then what is the probability that $\pi(x) + x$ is injective over choices of $\pi$?

The concrete instantiation I'm interested in is $S=$GF$(2^n)$ for fixed $n > 0$. (Computer Scientists call this "xor on $n$-bit strings.")

For $n=1$ we have two permutations, neither of which produce an injection. For $n=2$ we have 24 permutations, 8 of which induce an injection so the probability is 1/3.

Here is an example $\pi$ for $n=2$:

$\pi(0)=0,\ \pi(1) = z,\ \pi(z)=z+1,\ \pi(z+1)=1.$

Here notice that $\pi(x) + x$ produces $0$, $z+1$, $1$, and $z$, respectively, which is an injection.

2 Answers 2

5

There is a name for what you describe: it's called an orthomorphism. If $S$ is the cyclic group of order $n$, then the number of orthomorphisms for $n=1,3,5,...$ is $1, 3, 15, 133, 2025, 37851,...$ (sequence A006717 in OEIS). (If $n$ is even, $S$ has no orthomorphisms.)

You can find lots of links for the case when $S$ is GF$(2^n)$ by googling "orthomorphism of galois field". For instance, here is a short paper which confirms my $244744192$ and goes on to discuss the construction of permutation polynomials.

6

My laptop has extended your results to $n=3$ and $n=4$ (but $n=5$ is completely out of reach).

For $n=3$ we have $8!=40320$ permutations, of which $384$ induce an injection. $384/40320 = 1/105$.

For $n=4$ we have $16!=20922789888000$ permutations, of which $244744192$ induce an injection. $244744192/20922789888000 = 97/8292375$ in lowest terms, so I don't see a nice pattern here.

  • 0
    There's one pattern that might help to estimate the probability: The highest power of $2$ that divides the number of permutations which induce an injection seems to be $2^{2^n - 1}$ for $n \ge 2$. I don't have a proof, however.2011-03-01