Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

106 views

Skip to first unread message

Oct 27, 2016, 8:32:17 AM10/27/16

to

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

Nov 17, 2016, 3:07:14 PM11/17/16

to

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:

0 new messages

Search

Clear search

Close search

Google apps

Main menu