Is there a subset of $\Sigma_n$ s.t. each pair of elements is once in each pair of positions?

Question

Is there a subset $A \subset \Sigma_n$ such that for each pair $(x, y)$ and each pair $(i, j)$, there is exactly one permutation $\sigma \in A$ such that $\sigma(i) = x$ and $\sigma(j) = y$? Remark that it implies that the cardinality of $A$ is $n * (n-1)$.

Is there a simple condition on $n$ such that it is possible?

If n is prime, it is easy, for example with the following method. For each pair $(x, k)$, consider the permutation $\sigma$ such that $\sigma(i) = x + (i - 1) * k$ (modulo $n$). For example, for $n = 5$, you get:

• 1 2 3 4 5 and its 5 circular permutations,
• 1 3 5 2 4 and its 5 circular permutations,
• 1 4 2 5 3 and its 5 circular permutations,

• 1 5 4 3 2 and its 5 circular permutations.

  If n = 4, it is also possible. For example :

• 1 2 3 4
• 1 3 4 2
• 1 4 2 3
• 2 1 4 3
• 2 3 1 4
• 2 4 3 1
• 3 1 2 4
• 3 2 4 1
• 3 4 1 2
• 4 1 3 2
• 4 2 1 3

• 4 3 2 1

  For $n = 6$, I suspect that it is not possible, but I am not sure...

Answer 1

You are asking for a sharply $2$-transitive set of degree $n$. These objects are closely linked to projective planes of order $n$. In particular, they exist if $n$ is a prime power, and no example is known with $n$ not a prime power. It also follows from the Bruck–Ryser Theorem that there is no example of degree $6$.

See for example

http://tinyurl.com/go5el94

and

http://www.mathematik.uni-wuerzburg.de/~mueller/Papers/sharplyTGPM.pdf

Answer 2

Edit: as pointed out in comment, my answer implicitly assumes $A$ to be a subgroup of $\Sigma_n$. The question whether every $A$ with the given property is a subgroup (up to translation) is intriguing.

---

The comment by abx triggered in me the right keyword: you are asking in which finite cardinal there is a sharply $2$-transitive group action.

Camille Jordan proved among other things in 1872 ("Recherche sur les substitutions", Journal de Mathématiques pures et appliquées) that such an action must be conjugated to an affine action on a vector space over a finite field.

In conclusion, the finite cardinals carrying a sharply $2$-transitive group action are precisely the powers of primes.

For the story, I had some ideas related to this when I discovered Jordan had scooped me by more than 130 years (yeah, I was being naïve assuming this kind of question was anything close to new). My (gorgeous and regretted) library of that time had the volume of Liouville's journal where Jordan's paper was published, and I discovered that the article in this volume had not been read: its pages where not cut (at that time, pages where printed on large sheets, which were then folded and binded together, but to open the book one had to first cut the folds). So I cut the pages of a 130-years old volume in order to read a reference.

---

Pushed down in edit

Even better, the classification of sharply $2$-transitive group actions is known, though far from trivial. It turns out that they are all close to the affine group of a field, except one has to consider near-fields, which differ from skew fields only in that they are asked only one-sided distributivity (see Dixon-Mortimer Corollary 7.6A p238)

Also, finite near-fields are either finite fields, or Dixon near-fields which are skew fields with a modified multiplication, or one of 7 exceptional examples of cardinal $5,7,11,23,19$ or $59$.