What can we possibly get out of the monoidal action of this function?

82 Views Asked by At

For an $n$-tuple $S$ of decreasing positive integers, we can define $f(S)$ as subtracting $1$ from every element of $S$, prepending $n$, and then removing $0$s and re-ordering in decreasing order if neccecary. For example, $f((4,2,1))=(3,3,1)$.

We're supposed to analyze this function using higher mathematics, and after consulting my friend he says that he's been able to recover some interesting properties using the monoidal action of $\{Id,f,f^2,f^3,\dots\}$.

But this makes no sense to me, because, unlike with groups, there is pretty much nothing to go on with monoids. No orbit-stabalizer theorem, no Burnside's Lemma, etc. I've tried analyzing the orbits of this monoid acting on the set of finite, decreasing tuples of positive integers but not gotten anywhere.

What can I learn about this function through it's monoidal action?

EDIT: I've gotten a very helpful answer putting the question in terms of monoidal theory and proving every tuple hits a cycle. Now I'm wondering how we can use it to prove that every tuple with the same sum reaches the same cycle, using his method or another. We've proven it has a cycle decomposition, now can we say anything of it's nature?

1

There are 1 best solutions below

17
On

Here's an idea. Let's be clear, as you've noted monoid actions are weak, so they don't tell you a whole lot, and what they do tell you could be gotten through other means.

Let $T$ be the set of all $n$-tuples of decreasing positive integers for all $n$. Then $f: T\to T$, and as your friend observed, $\newcommand{\NN}{\mathbb{N}}\NN$ acts on $T$ by $n\cdot S = f^n(S)$.

Now observe that $f$ preserves the sum of the elements of the tuple. Thus so does each power of $f$. Hence if $T_n = \{S\in T: n=\sum_{i}s_i\}$, then $T$ splits as $\bigsqcup_{n=0}^\infty T_n$ and the action of $\NN$ also splits along each of these. Thus if we want to understand the action of $\NN$ on $T$, it suffices to understand its action on each piece, $T_n$. Now $T_n$ can be identified with the partitions of $n$.

In particular, $T_n$ is finite. Now let $$S_n\subseteq T_n, S_n := \bigcap_{i\in\NN} f^i(T_n).$$ $f(S_n)\subseteq S_n$ by definition, and $S_n= T_n\cap f(S_n)\subset f(S_n)$ as well, so $f(S_n)=S_n$. Thus since $S_n$ is finite, $f|_{S_n}$ must be bijective. Hence the action of $\NN$ on $T_n$ restricts to an action on $S_n$ by bijections. Thus it induces a group action $\mathbb{Z}\to \operatorname{Sym}(S_n)$. In particular, $f$ acts on $S_n$ as a member of the symmetric group on $S_n$, hence it has a cycle decomposition. Thus for a fixed tuple, $S$, the action of $f$ on $S$ is eventually cyclic.

In summary, what we've learned is that $f$ sends partitions of $n$ to partitions of $n$, and on the set of partitions of $n$, iterating $f$ sends each element of $T_n$ into $S_n$, and then it acts bijectively on $S_n$. Iterating $f$ on a particular element $S$ gives an eventually cyclic sequence.

Honestly, I'm not sure you need the language of monoid actions to state all this, but one could use this language as I have above. Hopefully this is helpful and sort of what you were asking for.

Edit: not all tuples with the same sum come to the same cycle.

Here are two distinct cycles of partitions of 8: 422,3311,422 and 431,332,3221,4211,431

I'll note that so far it appears to me that the cycles of $f$ are obtained from taking the fixed points and adding 0,1 vectors. The cycle corresponds to rotations of the 0,1 vector added. For example the cycle 422 corresponds to the rotations of 1010: 1010, 0101, which when added to 3210 gives 4220 and 3311 respectively. The other cycle corresponds to the rotations of 1100.