Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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. – J. J. Mar 1 '11 at 6:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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