Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers 2

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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.