A problem on cyclic permutations

[Julien Cassaigne]

Fix a positive integer n. Let X be a subset of the group of permutations
on n elements with the following property : if s and t are any two
elements of X, then their product st is a cycle of order n. Let M(n) be
the maximum possible size of such a set X. What is M(n)?

Note that X is not a subgroup of S_n : the product st may not be in X.
Taking s=t, one gets immediately that X is empty when n is even (the
square of a permutation cannot be a cycle of even order), and that
elements of X are themselves cycles of order n.

My conjecture (checked by hand for n=3 and n=5, with a computer for n=7)
is that, when n is odd, M(n) = (n-1)! / (2^((n-1)/2) ((n-1)/2)!),
i.e., M(n) is the product of odd integers from 1 to n-2.

Here is a maximal X for n=5 : X = {(12345), (12453), (12534)}
(it is actually unique up to conjugation).

I need this to construct a counterexample on multidimensional sofic
shifts. I would be happy with a reasonable upper bound on M(n), but a
proof or disproof of the conjectured exact formula would be even
better.

--
Julien Cassaigne
Institut de mathématiques de Marseille

[David Cullen]

Hi Julien.  I believe I have proved the result you require.  Do please
let me know what you think!

Notation:
n is a positive odd number.
C_n denotes the set of all n-cycles in the symmetric group S_n.
Let A -t-> B mean that t(A) = B for A, B in {1, 2, ..., n}, and t in
S_n.
Products ab of elements a, b in S_n act on A in {1, 2, ..., n} like:
(ab)(A) := a(b(A)).
P_n denotes the product of all positive odd numbers less than n.

Objective:
Find the number M(n) which is the maximum size of a set N contained in
C_n with the propery that xy is in C_n for all x, y in N.

Theorem:
M(n) = P_n.

Lemma 1:
Let a, b, t be elements of C_n with the property that ab = t.  
Further suppose that the cycle notation for a and b are respectively
(a_1 a_2 ... a_n) and (b_1 b_2 ... b_n).
Then t' := (a_1 a_2 ... a_n n+1 n+2)(b_1 b_2 ... b_n n+1 n+2) is in
C_(n+2).

Proof of Lemma 1:
Case 1: (b_1 = a_n)
b_n -t'-> n+2 -t'-> n+1 -t'-> a_1.
However, b_n -t-> a_1.
All other elements of {1, 2, ..., n} have the same image under both t
and t'.
i.e to obtain t' from t, you just insert "n+1 n+2" into the cycle
structure of t between b_n and a_1, so t' is an n+2-cycle.
Case 2: (b_k = a_n, k != 1)
b_n -t'-> n+2 -t'-> t(b_n) and b_(k-1) -t'-> n+1 -t'-> a_1 = t(b_(k-1)).
However, b_n -t-> t(b_n) and b_(k-1) -t-> t(b_(k-1)).
All other elements of {1, 2, ..., n} have the same image under both t
and t'.
i.e. to obtain t' from t you just insert "n+2" after b_n, and "n+1"
before a_1 into the cycle structure of t, so t' is an n+2-cycle.

Lemma 2:
M(n) is at least P_n.

Proof of Lemma 2:
By induction on n.
If n=3, then any two 3-cycles have non-3-cycle product, so M(3) = 1.
Let B be a subset of S_n of size P_n with the property that xy is in
C_n for all x,y in B.
Form a new set B' contained in C_(n+2) by generating n new elements
from each element b of B by inserting "n+1 n+2" into any of the n
possible places in the cycle structure of b.
Then B' has P_(n+2) distinct elements, and the product of any two of
them is in C_(n+2) by Lemma 1.

Lemma 3:
Let a = (a_1 a_2 ... a_n), b = (b_1 b_2 ... b_n), a' = (1 2 a_1 a_2 ...
a_n), b' = (1 2 b_1 b_2 ... b_n), ab = t, a'b' = t'.
If t' is in C_(n+2), then t is in C_n.

Proof of Lemma 3:
Case 1: (b_1 = a_n)
b_n -t'-> 2 -t'-> 1 -t'-> a_1.
However, b_n -t-> a_1.
All other elements of {1, 2, ..., n} have the same image under both t
and t'.
i.e. to obtain t from t', you just remove "2 1" from the cycle
structure of t', thus t is an n-cycle.
Case 2: (b_k = a_n, b_1 = a_j, k !=1, j != n)
b_(k-1) -t'-> 1 -t'-> a_1 and b_n -t'-> 2 -t'-> a_(j+1).
However, b_(k-1) -t-> a_1 and b_n -t-> a_(j+1).
i.e. to obtain t from t' you just remove "1" and "2" from the cycle
structure of t', thus t is an n-cycle.

Lemma 4:
M(n) is at most P_n.

Proof of Lemma 4:
Suppose for contradiction, that m is the smallest number such that
C_(m+2) has a subset B with more than P_(m+2) elements, which also has
the property that xy is in C_(m+2) for all x, y in B.
Let b be any element of B and suppose I -b-> 1.
Consider the sets Q_J := {c in B | 1 -c-> J}.  In particular, Q_I is
empty because if it contained any element c, then bc would fail to be
an n+2-cycle, because it fixes 1.
It follows that the Q_J for J in {2, 3, ..., n+2}\{I} form a partition
of B into n sets.
By the pigeonhole principle, one of these sets contains more than the
average number of elements, say Q_K has more than P_m elements.
Conjugate all of the elements of Q_K by (2 K) to obtain a new set Q'
with the property that 1 -q-> 2 for each q in Q', and also still xy is
in C_(m+2) for x, y in Q'.
Remove "1 2" from the cycle structure of each element of Q' to obtain
the set Q.  By Lemma 3, Q has the property that xy is in C_m for x, y
in Q.
But Q has more than P_m elements, so this contradicts the minimality of
m.

Proof of Theorem:
Lemma 2 and Lemma 4.

Best regards,
David

On Thursday, October 27, 2016 at 6:32:17 AM UTC-6, Julien Cassaigne
wrote: