# Permutations of $(Z/pZ)^*$

Let $p$ be a prime integer, and let $(\mathbb Z/p\mathbb Z)^*$ be the set of non-zero elements of $\mathbb Z/p \mathbb Z$. Denote by $S((\mathbb Z/p \mathbb Z)^*)$ the group of permutations of $(\mathbb Z/p \mathbb Z)^*$.

Say that a map $a:(\mathbb Z/p \mathbb Z)^*\to S((\mathbb Z/p \mathbb Z)^*)$ satisfies condition (A) if, for any two distinct elements $i,j\in (\mathbb Z/p \mathbb Z)^*$, $a(i)-a(j)\in S((\mathbb Z/p \mathbb Z)^*)$.

For example, let $a(i)(k) = ik.$ This satisfies condition (A). The same is true if we permute the functions $a'(i) = a(c(i))$, or relabel the objects $a''(i)(k) = i \cdot b(k)$, or both. Are these modifications of $a(i)(k) = ik$ the only ways to get a map satisfying condition (A)?

If $a$ satisfies (A), are there $b,c\in S((\mathbb Z/p \mathbb Z)^*)$ such that, for all $i\in (\mathbb Z/p \mathbb Z)^*$ and all $k\in (\mathbb Z/p \mathbb Z)^*$, $a(i)(k)=c(i)\cdot b(k)$, where the dot is multiplication in $\mathbb Z/p \mathbb Z$?

Note: it would probably be sufficient to prove that, if $a$ satisfies (A), then, for all $i,j,l\in (\mathbb Z/p \mathbb Z)^*$, $a(i)a(l)^{-1}a(j)=a(j)a(l)^{-1}a(i)$. Or in simpler terms, if $a(1)$ is the identity (one can reduces to this case) then the $a(i)$ commute.

edit I've corrected the question -- and the paragraph before it -- thanks to comments by François Brunault and Victor Protsak, who noted that the original formulation was incorrect due to an irrelevant $b^{-1}$.

• What is the meaning of $a(i)-a(j)$ in the second paragraph of your question? Does it mean the function whose value at $k$ is $a(i)(k)-a(j)(k)$, using the subtraction in the ring $\mathbf{Z}/p\mathbf{Z}$. In that case,your condition (A) forces this to be a permutation. Then $a(i)$ and $a(j)$ are permutations agreeing nowhere. Is the map $a$ a group homomorphism? Then $a$ specifies a free action of $\mathbf{Z}/p\mathbf{Z}^*$ on itself. – P Vanchinathan May 20 '13 at 15:29
• Bonjour Jean-Marc. Nice question. Perhaps you should give more information about the motivation. How did this problem arose? Is it in your research, or is it "recreational"? – Joël May 20 '13 at 18:25
• Joël: the question comes up rather naturally in a "recreational" but still serious project we're working on with Teo Banica and Ion Nechita, on complex Hadamard matrices. It looks like it might involves some ideas from basic number theory, things that I don't really know but that should be obvious to someone like you, so perhaps MO can help here... BTW, thanks for the editing. – Jean-Marc Schlenker May 20 '13 at 19:10
• I let Magma compute the maps satisfying (A) in the case p=5. It turns out that some of them do not have the identity permutation in the image, which seems to indicate that the property you ask is not true in general. As an example, take the four permutations of (Z/5Z)^* whose tables of values are [4,2,3,1], [1,3,2,4], [2,1,4,3] and [3,4,1,2] respectively. Note also that any map satisfying (A) defines a Latin square indexed by (Z/pZ)^* (but the converse is not true). – François Brunault May 21 '13 at 20:21
• What you call "relabeling" does not preserve condition (A)! Keep in mind that a permutation $b$ is not, in general, compatible with the additive structure on $\mathbb{Z}/p\mathbb{Z}$ involved in checking the condition. For a specific example, consider $p=5$ and $b=(12).$ Then $a''(i)=b^{-1}(i\cdot b(k))$ are the following permutations: $$i=1: 1\to 1, 2\to 2, 3\to 3, 4\to 4\qquad i=2: 1\to 4, 2\to 1, 3\to 2, 4\to 3$$ Clearly, $a''(1)-a''(2)$ is not a permutation, since it maps $2,3,$ and $4$ to $1.$ – Victor Protsak May 21 '13 at 22:11

A similar concept is an orthomorphism of a group $G$. This is an automorphism $\theta: G \rightarrow G$ with the property that $g^{-1}\theta(g)$ is a bijection (equivalently an automorphism). Two orthomorphisms $\theta$, $\eta$ are orthogonal if $\theta^{-1} \eta$ is an orthomorphism.
A set of $k$ orthogonal orthomorphisms correspond to a set of $k$ mutually orthogonal latin squares with specified symmetries. In particular, the examples you give above are the prototypical examples of orthogonal orthomorphisms, and they give a set of $p-1$ MOLS of order $p$. From these one can easily construct the (desarguesian) projective plane of order $p$.
It seems to me that your question relaxes the condition that the orthomorphisms be automorphisms of $G$: you simply want functions. The relation to mutually orthogonal latin squares should still hold however. So you are essentially looking for a non-desarguesian projective plane of order $p$. As far as I know this problem is open, though none are known to exist. (And people have looked.)