I'm reading this paper on cycles of partitions, and was wondering if anyone could motivate the last condition in the definition of the sets $M_n$ in terms of the partitions being examined.

In particular, for each positive integer $n$, $M_n$ consists of all bi-infinite sequences of positive integers whose terms never exceed $n$, and moreover, the $i$th term $\sigma_i$ is the number of previous terms $\sigma_j$ that are at least $i-j$. I can see that a partition of $n$ cannot have a length greater than $n$, but I'm confused about this second condition. I tried to rephrase the definition of $M_n$ as $$ M_n = \{f:\mathbb{Z} \to \mathbb{N} \,\, \vert \,\, \max_i f(i) = n \text{ and } f(i) = \#\{f(j) : f(j) \ge i-j\}\} $$ and think about it on an $ij$ plane, but I'm still not grasping the intuitive reason for this condition.

Help would be appreciated!


Recall the operation of $T$: if $\lambda$ is the partition with parts $p_1,p_2,\ldots,p_\ell$, then $T(\lambda)$ is the partition with parts $p_1-1,p_2-1,\ldots,p_\ell-1,\ell$, ignoring any $0$ parts generated in the process. I’ll call $\ell$ the new part of $T(\lambda)$.

Now consider a cycle of partitions of some positive integer. Once the cycle gets going, every part of every partition in the cycle begins as a new part. Suppose that $\ell$ is the length of $\lambda_0$, where $\lambda_0$ is some partition in the cycle. Then $\ell$ is the new part of $\lambda_1=T(\lambda_0)$, and for $k=1,\ldots,\ell$ the partition $\lambda_k=T^k(\lambda_0)$ has $\ell+1-k$ as a part. In other words, the part corresponding to the length $\ell$ of $\lambda_0$ is present precisely in the $\ell$ consecutive partitions $\lambda_1,\ldots,\lambda_\ell$. Another way to say this is that $\lambda_0$ contributes a part to $\lambda_k$ iff $1\le k\le\ell$.

More generally, if $j<i$, and $|\lambda_j|$ is the length of $\lambda_j$, then $\lambda_j$ contributes a part to $\lambda_i$ iff $i-j\le|\lambda_j|$, and it follows that $\lambda_i$ must have one part for each $j<i$ such that $i-j\le|\lambda_j|$. In other words,

$$|\lambda_i|=|\{j<i:|\lambda_j|\ge i-j\}|\;.\tag{1}$$

Since the $\sigma_i$ of the paper is precisely my $|\lambda_i|$, $(1)$ says that

$$\sigma_i=|\{j<i:\sigma_j\ge i-j\}|\;,$$

which is the condition about which you were asking. As we’ve just seen, it’s a necessary condition on the sequence of partition lengths in a cycle of partitions.

When combined with a bound on the lengths, it’s also a sufficient condition, though that does not seem to me quite so obvious as the author of the paper implies.

  • $\begingroup$ Thank you for such a clear explanation! I'll think more about how I'd prove the sufficiency part. $\endgroup$ – sourisse Mar 17 '15 at 10:55
  • $\begingroup$ @sourisse: You’re welcome! $\endgroup$ – Brian M. Scott Mar 17 '15 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.