An Operation on Multisets

Question

Define a 2 x n array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities.
Repeat the process. For example, starting with the 2 x 1 array [1; 1], the sequence is: [1; 1] -> [1; 2] -> [1, 2; 1, 1] -> [1, 2; 3, 1] -> [1, 2, 3; 2, 1, 1] -> [1, 2, 3; 3, 2, 1] -> [1, 2, 3; 2, 2, 2] -> [1, 2, 3; 1, 4, 1] -> [1, 2, 3, 4; 3, 1, 1, 1] -> [1, 2, 3, 4; 4, 1, 2, 1] -> [1, 2, 3, 4; 3, 2, 1, 2] -> [1, 2, 3, 4; 2, 3, 2, 1], and we now have a fixed point (loop of one array).

Does the process always result in a loop of 1, 2, or 3 arrays?

Answer 1

But I don't have a clear proof that the sequence always terminates in a loop. – Martin Erickson

Here is a proof that the sequence always terminates in a loop.

Let $A, B$ be consecutive arrays in the sequence, and c(X) denote the number of columns in array X.

Claim 1. $c(A) \leq c(B)$.

Proof. Trivial.

Claim 2. $$\sum_{i=1}^{c(B)} B[2,i] = 2 c(A).$$

Proof. By the sequence definition, the second row of each subsequent array contains the multiplicities of elements of the preceding array, and thus the sum of multiplicities equals the total number of elements in the preceding array. QED

Now, let $A', A, B$ be three consecutive arrays in the sequence.

Claim 3. Let $m\geq 5$ be an odd integer such that no element $B$ exceeds $m$. Then no element larger than $m$ can appear in subsequent arrays (while their size may eventually grow up to $2\times m$).

Proof. Assume that a larger element $m'\geq m+1$ appears. Without loss of generality suppose that this happens in (the bottom row of) array $C$ that immediately follows $B$. By Claim 1, we have $c(A)\leq c(B)\leq c(C)\leq m$.

By Claim 2 and since $C$ contains $m'\geq m+1$ (while the other elements are at least 1), $$m + c(C) \leq m' + (c(C)-1) \leq \sum_{i=1}^{c(C)} C[2,i] = 2c(B) \leq 2c(C)\leq 2m$$ implying that $c(B)=c(C)=m$ and $m'=m+1$.

Therefore, the top row of both $B$ and $C$ contains all integers from 1 to $m$.

The bottom row of $C$ consists of one number $m'=m+1$ and $m-1$ ones. If $m'$ appear under the number $k$, then bottom row of $B$ contains at least $m$ numbers $k$, whose sum must not exceed $2c(A)\leq 2m$, implying that $k\leq 2$. Consider two cases:

If $k=1$ then the bottom row of $B$ consists of all ones, implying that the elements of $A$ are the integers from $1$ to $m$ without repetitions, and hence $m$ is even, a contradiction proving that no element larger than $m$ may appear.

If $k=2$ then the bottom row of $B$ consists of all twos, implying that $c(A)=m$ and $A$ contains in each row all integers from 1 to $m$ so that the sum of its bottom row equal $1+2+\dots+m = m(m+1)/2.$ The inequality $m(m+1)/2 \leq 2c(A') \leq 2c(A) = 2m$ then implies that $m\leq 3$, that is not the case.

QED

Claim 4. The sequence always terminates in a loop.

Proof. By Claim 3, there exists an integer $m$ such that elements of the arrays in the sequence do not exceed $m$. By Claim 1 and since $c(X)\leq m$ for all $X$ in the sequence, the size (and hence the top row) of arrays stabilizes to a certain $c(X)=n$. Then by Claim 2, the sum of the bottom row stabilizes to $2n$. Since, there are only a finite number of compositions of $2n$ into the sum of $n$ positive integers (namely, $\binom{2n-1}{n}$), there exists only a finite number of distinct arrays that may appear after the size stabilization, implying that the sequence loops. QED

Claim 5. The length of the terminal loop is bounded by $\binom{2m-1}{m}$, where $m$ is defined as in Claim 3.

Proof. See proof of Claim 4.

Answer 2

This is a very interesting question. I would like to add that the order property is not necessary for the convergence, since the transformation from one array to another does not depend on it. (We could define an equivalence relation on the set of arrays: a ~ b iff a is a permutation on the columns of b). Also, of course, 2 x m arrays work just as well as m x 2 arrays.

Answer 3

This reminds me a little of Conway's "Look-and-say" sequence, although I'm not sure if any of his results will carry over to your setting.

http://en.wikipedia.org/wiki/Look-and-say_sequence

The asymptotic behavior of the Look-and-say sequence makes me guess that you probably won't have divergent trajectories, but bounding the period might be tricky. The way you phrase the question makes it sound like you already have examples with period 1, 2, and 3, and if so that already suggests that the answer might be complicated...