Maximum conjugacy class size in $S_n$ with fixed number of cycles

Question

Context: It is well known that given a permutation in $S_n$ with $a_i$ $i$-cycles (when written as a product of disjoint cycles), the size of the conjugacy class is given by $$ \frac{n!}{\prod_{j=1}^n (j)^{a_j}(a_j !)}$$

It is also known that the conjugacy class containing permutations with exactly one fixed point and exactly one $n-1$ cycle (hence, $a_1 = 1$ and $a_{n-1} = 1$) has maximum conjugacy class size. (see this post)

Question: Now let's fix the number of cycles, $m$ (this count includes the trivial ones). Then how would one go about finding the cycle type with the maximum conjugacy class size, among the ones with $m$ cycles?

Note that the case for $m=2$ is true for $n \geq 3$ by the assertion above in the context.

My "conjecture" is that any such cycle type needs to have $a_1 \geq \frac{m-1}{2}$. (i.e. at least about half of the cycles are trivial). And that about a fourth are 2 cycles and so on.

EDIT:

The conjecture as it stands is not true, as per one of the answers posted below. To have roughly 1/2 of the parts as 1's, the number of parts also needs to be roughly a 1/2 of $n$ or so, it seems.

Answer 1

Fix $m.$ For each $n$ consider the the question: among all the conjugacy classes for permutations in $S_n$ with exactly $m+1$ cycles, which has the largest size?

I will write $\prod_{i \geq 1}i^{a_i}$ to describe a partition with $a_i$ cycles of length $i.$

Below is some data. It is the result of rather unsophisticated exhaustive calculation. It strongly suggests the following unsurprising result:

There is a $k=k(m)$ integers $a_1 \geq a_2 \geq \cdots \geq a_k=1$ and $t=t(m)=\sum_1^ka_kk$ such that, for $n$ large enough relative to $m,$ the unique maximum occurs for type $1^{a_1}2^{a_2}\cdots k^{a_k}(n-t)$

later

Based on the calculations one might speculate further that the $a_i$ decrease until they are $1$ (perhaps no later than $\sqrt{k}$ or some such $j \ll k$)

The conjecture from the question is that $a_1$ is about $\frac{m}2$, $a_2$ is about $\frac{m}4$ and so on. That is a bit vague. Does it mean that $a_j$ is about $\frac{m}{2^j}$ (perhaps for $1 \leq j \ll k?.$ An now deleted answer speculated that $a_1=2a_2=3a_3=\cdots=ja_j$ again perhaps for $1 \leq j \ll k.$

The present calculations are not sufficient to test if either of these is likely.

• For $m=1$ the maximum occurs for $1\ (n-1)$
• For $m=2$ and $n \gt 5$ the maximum occurs for $1\ 2\ (n-3)$
• For $m=3$ and $n \gt 10$ the maximum occurs for $1^2\ 2\ (n-4)$
• For $m=4$ and $n \gt 10$ the maximum occurs for $1^2\ 2\ \ 3 (n-7)$
• For $m=5$ and $n \gt 20$ the maximum occurs for $1^3\ 2\ 3\ (n-8)$
• For $m=6$ and $n \gt 17$ the maximum occurs for $1^3\ 2\ 3\ 4\ (n-12)$ except that
  • for $n=22$ there is a tie between $1^3\ 2\ 3\ 4\ (10)$ and $1^2\ 2\ 3\ 4\ 5\ 6$
• For $m=7$ and $n \gt 29$ the maximum occurs for $1^3\ 2^2\ 3\ 4\ (n-14)$

This might allow a more refined conjecture. Certainly data for larger $m$ would be suggestive. That would justify taking the time to do design a more intelligent search.

Here are more detailed results on $m=7$ to show exactly what I know for sure:

For $30 \leq n \leq 60$ the maximum occurs only for $1^3\ 2^2\ 3\ 4\ (n-14).$ Presumably the same is true for all $30 \leq n.$ It is also true for $n=19,20,21,22. $

the other cases are:

• $1^8$
• $1^72$
• $1^62^2$
• $1^62\,3$
• $1^52^23$
• $1^42^33$
• $1^5\,2\,3\,4$
• $1^42^23\,4$
• $1^42^23\,5$
• For $n=17$ a tie between $1^42^23\,6$ and $1^32^23^24$
• $1^4\,2\,3\,4\,5$ for $n=18.$
• $1^32\,3\,4\,5\,(n-17)$ for $23 \leq n \leq 28$
• for $n=29$ a tie between $1^3\,2\,3\,4\,5\,12$ and $1^32^23\,4\,15$

Answer 2

Here is a different viewpoint: the question is equivalent to asking for a permutation $\sigma$ whose disjoint cycle structure contains exactly $m$ cycles, and with $|C_{S_{n}}(\sigma)|$ as small as possible subject to that.

Note that if $\sigma$ has $a_{j}$ cycles of length $j$ for each $j$ in that decomposition, then $|C_{S_{n}}(\sigma)| = \prod_{j} j^{a_{j}} a_{j}!,$ (which is just the denominator in the expression given in the question for the size of the conjugacy class). Note that this is clearly at least as large as $ \prod_{ \{j : a_{j} >0\}} j$, and note on the other hand that equality holds if all cycle sizes are distinct.

From now on I consider the case where there is a partition of $n$ into $m$ parts of distinct sizes (which is equivalent to requiring that $n \geq \frac{m(m+1)}{2}).$ I want to show first that there is a unique (up to conjugacy) choice of $\sigma$ which minimizes $|C_{S_{n}}(\sigma)|$ subject to the condition that $\sigma$ has $m$ cycles of pairwise distinct sizes.

Given such a permutation $\sigma,$ choose $j = j(\sigma)$ maximal subject to the fact that the $r$-th shortest cycle of $\sigma$ has size $r$ whenever $r \leq j$ - the possibility that $j =0$ is allowed, and occurs precisely when the shortest cycle of $\sigma$ has size greater than one. Note that the $j+1$-st shortest cycle of $\sigma$ (if there is one) has size at least $j+2$ by the maximality of $j$.

If $\sigma$ has more than $j+1$ disjoint cycles, then we may produce a permutation $\tau$ with $m$ disjoint cycles of pairwise distinct lengths and with $|C_{S_{n}}(\tau)| < |C_{S_{n}}(\sigma)|.$ We simply shorten the $j+1$-st shortest cycle of $\sigma$ by one, and lengthen the longest cycle of $\sigma$ by one. The resulting permutation $\tau$ still has all its $m$ disjoint cycles of pairwise distinct lengths, but we see easily that if $a$ is the length of the $j+1$-st shortest cycle of $\sigma$ and $b > a $ is the length of the longest cycle of $\sigma,$ then $ab|C_{S_{n}}(\tau)|= (b+1)(a-1)|C_{S_{n}}(\sigma)|$, so the claim follows as $(b+1)(a-1) < ab.$

Hence we can "improve" our choice of $\sigma$ if $\sigma$ has more than one cycle of length greater than $j+1,$ so the unique minimizing choice of $\sigma$ has its $r$-th cycle of length $r$ for $r \leq j$ and only one cycle of length greater than $j+1$. This forces $j = m-1$ or $j =m.$

Hence if $n \geq \frac{m(m+1)}{2},$ the unique choice of $\sigma$ with $m$ disjoint cycles of pairwise distinct lengths which minimizes $|C_{S_{n}}(\sigma)|$ has its $r$-th cycle of length $r$ for $1 \leq r \leq m-1$ and one cycle of length $n - \frac{m(m-1)}{2}.$ Note that the size of the corresponding conjugacy class is $\frac{n!}{(n-\frac{m(m-1)}{2})(m-1)!}$.

While this does not directly answer the question, it does perhaps give some insight and provides large conjugacy classes of elements with $m$ disjoint cycles.

Later edit: As indicated in the last sentence, and suggested also by comments of Gerhard Paseman, this is not at all the end of the story if we allow repeated cycle lengths.

For example, if $\sigma$ has cycle type $12 \ldots (m-2)(m-1)d$ where d > m, we can shorten (m-2) cycles of $\sigma$ by one each, and lengthen the longest cycle by m-2 to obtain $\tau$ of cycle type $112 \ldots (m-2)(d+m-2)$.

Then $(m-1)d|C_{S_{n}}(\tau)| = 2(d+m-2)|C_{S_{n}}(\sigma)|$ which yields $|C_{S_{n}}(\tau)| < |C_{S_{n}}(\sigma)|$ as long as $m>3.$ Then $\tau$ is the product of $m$ disjoint cycles, but $\tau$ has a larger conjugacy class than $\sigma$. This suggests other continuations, and seems to point towards some of the empirically found maxima found by Aaron in his answer, at least when $n$ is large enough compared to $m.$

Answer 3

Let's consider having c cycles of size k, d > c cycles of size k+1, and some number of largest cycles of size p >k+1. Let's shift an element out of d-c of the k+1 cycles, and put them on one p cycle. Just considering cycle lengths, in the product this represents a differential of 1 + (d-c)/p against (1+1/k)^(d-c). If we started with b many p cycles, we now have b-1, and so the product is reduced by an additional factor of b. So "shifting the excess" to a large enough cycle results in a reduction in denominator. Thus almost any cycle that optimizes the product will have more smaller cycles than larger cycles, with all lengths between 1 and l represented, followed by a solitary cycle of length p or more possibly larger than l+1.

(In case we have p=k+1, a similar argument with d-c>1 also works, as does the case when there is more than one cycle of maximal length. So, with the exception of a gap between l and p, we have cycles represented in decreasing number as length grows.)

So with care, the above can be turned into a proof of Aaron's unsurprising result. Now let us see if we can predict how big is l, the length of the largest (but one) cycle .

Suppose the two largest cycle lengths are l and p, with l less than p, and assume they occur uniquely. We split the l cycle into a 1 cycle and increment the p cycle by l-1. If we started with d many 1 cycles, we win (by shrinking the denominator) if (d+1)(p+l-1) is less than or equal to pl. If we have c many cycles of length l, replace pl by cpl in the previous inequality. So we win for sure if (d+1) is less than or equal to cl/2.

If we are giving too much attention to one cycles, we can consider having c many k cycles and increasing their count by 1. The inequality now becomes a win if (c+1)k(p+l-k) is at most lp. In particular, if kc is at most l/2, consider shortening the l cycle to k and adding the excess up. If you lose, it won't be by much.

By considering a number of moves of this type, the search space for a cycle that optimizes the associated product should be readily obtained, even by hand, for large enough n.

Update 2019.06.11:

Here is an attempt at justifying an approximation to the conjecture made in the post. While not strictly following the conjecture, we show that a good attempt at an optimum starts with n large enough, about m/2 fixed points, about m/4 cycles of length 2, and so on. I do not claim the result is an absolute optimum. I do suggest that the optimum is not far from this choice for n about 2m. For larger n there is more room to play.

I follow the original post, assume n is at least 2m, and look at the permutation of m cycles with one cycle of length n-m+1. The denominator of (n-m+1)((m-1!)) is easily calculated; what changes in cycle structure can make it smaller?

To start, we borrow from the large cycle to make at least (m-1)/2 cycles of length 2, giving possibly more cycles of length 2 than of length 1. (Don't worry, we will recycle some of these 2-cycles. Hah, I'm so funny.) Indeed, when we borrow about (m-1)/2 elements from the large cycle and convert that many 1-cycles to 2-cycles, we replace some terms in the denominator ((m-1)(m-2)(m-3)...) by terms that resemble (m-1)(m-3)(m-5)... (Or possibly (m)(m-2)(m-4)...), and n-m+1 gets replaced by something like n-3(m-1)/2. I am not bothering to use integer arithmetic, as the messy justification that the denominator is made smaller I leave to you. In any case, I assert we can reduce the denominator by replacing half or more of the 1-cycles by 2-cycles, especially when m is at least 6.

Now we can repeat this: replace slightly more than half the 2-cycles with 3-cycles, borrowing about m/4 from the large cycle. We get another reduction, but with a factor of about (3/2)^(m/4) involved as opposed to (2/1)^(m/2). We can iterate this up to log m times about, taking half or more k cycles and making (k+1) cycles from them. With care we borrow about m elements from the large cycle, and make cycle lengths up to log m.

Do we stop there? Not if n is big enough. We can now use a 1-cycle (we have about m/2 of them) and borrow from the large cycle to create a single cycle of length slightly larger than log m. We can repeat this as long as the cycle created has length less than the number of remaining 1-cycles. Similarly, we can reuse a few of the m/4 2-cycles this way.

We do not get quite up to cycles of length sqrt(m) this way because of the repetitions of small cycles, but for large n we have made a series of reductions in the denominator. Using this as a threshold, one can try perturbing this structure slightly to improve the denominator, without having to search the whole space.

End Update 2019.06.11.

Gerhard "Now Show Me Your Moves" Paseman, 2019.06.10.

Answer 4

Really guys, local optimization is the way to go, or at least to start. By analyzing those cycle patterns which are resistant to being optimized, you can get a lot of information, and reduce the search space dramatically. I said this in comments and another post; this post shows it in action using the move c d goes to c-1,d+1, and occasional variations on this move. Here c and d are integers representing cycle lengths with c at most d. Often, but not always, it will be useful to choose d to be the maximal length present in a given cycle structure.

Let's start with r many cycles of length d, where r is greater than one. If d is 1, we can't do the move. If d is greater than one, the denominator is affected by a) replacing d^2 by (d^2-1), b) reducing a factorial term by r(r-1), and c) increasing two other factorial terms representing cycle counts for lengths d+1 and d-1, which we will call an increase by a factor of st.

Before we break it down to cases, we see that this move says something about a cycle structure: if this move doesn't optimize it, then either it has not many cycles of length greater than 1, or it does, but for every cycle length d greater than 1 which has two or more cycles, there is a relationship almost harmonic in nature, represented by the exponents (a_j) given by the relationship $st\geq r(r-1)$. In particular, for cycle lengths j-1,j, and j+1, if the counts for j-1 and j+1 are both at least two less than the count for j, this move optimizes (replaces this configuration with another with smaller denominator). More particularly, any configuration with $ r\gt 1$ cycles of length $j \gt 1$ and at most one cycle having a length from { j+1,j -1} is nonoptimal (0,2,1 and 1,2,0 and similar can't appear as consecutive subsequences can't appear in an optimal cycle structure).

For the case of replacing c d by c-1, d+1, where there are $r \gt 0$ many cycles of maximal length $d \gt c \gt 1$, $s$ many cycles of length c, and $t-1$ many cycles of length c-1 before replacement, we get a) cd replaced by cd + c-d-1, b) a reduction by r of one factorial term, and c) a change of t/s in the terms induced by moving the cycle of length $c$. This is a reduction whenever $t \leq rs$.

From these two kinds of moves we see that if there are fewer cycles of length $j$ than of length $j+1$, then either $j+1$ is d , the maximal cycle length, and there is one such cycle of that length, or else we have a move to optimize this configuration. We also have the counts for any three successive lengths present in the structure s-1,r, and t-1 the relation $r(r-1) \leq st$, otherwise we have an optimizing move to make. In particular, s-r cannot be smaller than r-t-1. Also, if there is a gap (a single cycle of maximal length d and none of length d-1), then the move c d to c+1,.d-1 optimizes if the exponents on c and c+1 differ enough (if s/t+1 is greater than (cd +d-c-1)/cd), so one gets a tighter relationship on the exponents with a gap present. If the gap is large enough, and s is the smallest cycle not present, then 1^s d can be replaced by 1^(s-1)s(d-s+1), which gives more bounds on the exponents.

Now suppose we have a cycle structure with k many distinct cycle lengths. We assume the structure has more than 1 cycle.

If k is 1, then the cycle lengths must all be 1, otherwise the structure is non optimal. This is the case m=n in the notation of the problem with cycle structure 1^n.

If k is two, then one of the lengths must be 1, otherwise we have a nontrivial configuration. If the other length is greater than 2, there can be only one cycle of that length, and by reversing the move c-1,d+1 to c,d, we have a nonoptimal structure if there are at least three 1-cycles. So one potentially optimal structure with only two lengths is 11(n-2): this works when n is 4 or 5. For larger n this is beaten by the structure with three lengths 12(n-3).

If k is two and the longest cycle present is length 2, this is optimal unless there are r 2-cycles and s-1 1-cycles and r(r-1) is at least 3s/4, in which case turning two of the 2-cycles into a 1-cycle and a three cycle gives a possibly more optimal structure. So for two cycle lengths, we either have 1(n-1), 113, or 1^(s-1)2^r with 4r(r-1) at most 3s. Indeed, trying to improve upon this configuration for n=2r+s-1 by replacing 2-cycles by a j cycle and j 1-cycles gives a less optimal configuration since s+i is greater than 2(r-i).

For k = 3, we must have the lengths be 1,2, and d, otherwise we have a nonoptimal structure. Suppose d is greater than 4. We can replace 2,d by 3,d-1 and if there are two or more 2-cycles, this is an optimizing move.if there is only one 2-cycle, then we can do 1,d to 2,d-1 , and this is an optimizing move if there are 4 or more 1-cycles. So for d 5 or greater, the only possible optimal cycle structure with three cycle lengths are 1112d and 112d and 12d. For large d, 1112d is less optimal than 1123(d-2).

If d is 4 and there are 3 or more 2-cycles or 5 or more 1-cycles, we can do a c 4 to c+1 3 optimizing move. Otherwise 1^s2^r4 is a potential optimum for s at most 4 and r at most 2.

Finally assume d is 3, and the structure to study is 1^s2^r3^t. Assume r and t large enough when needed. The moves to investigate are 3 3 to 2 4, 2 3 to 1 4, and 2 2 to 1 3 and the reverse move. These involve comparing 9t(t-1) to 8(r+1), 6rt to 4(s+1), and 4r(r-1) to 3(s+1)(t+1). One needs to run the calculations for a specific triple s,r,t, but if t is roughly bigger than square root of r, then the structure is nonoptimal, and if r is bigger than a fractional power ( compute it, but use 3/5 for an initial guess) of s, the structure is non optimal.

As pointed out before, one expects a decrease in exponents of a harmonic type (to counter moves like j j to j-1 j+1) as cycle length increases and with a largest cycle there can be only one gap in the list of cycle lengths, and if there is a gap then there is one largest cycle. When k gets larger, if there is a gap of length two or greater between second largest and largest cycle lengths, sometimes a move from c d to c+1 to d-1 can optimize, so usually the second largest cycle length has exponent one in an optimal structure, and one can say more about the sequence of exponents for smaller cycle lengths.

Gerhard "One Move At A Time" Paseman, 2019.06.23.