Enumerating the Partition Transform Cycles

The following is extracted from an email sent by Dan Ford 
(Daniel.Ford@cww.octec.org.au) in Jan 96, answering the 
"Most Wanted" question #22.

SUMMARY

There are only four cycles of partition sequences, none of which 
have period greater than 2.  Also, it is shown that all sequences 
of positive integers will approach one of these cycles.


DEFINITIONS AND NOTATION

P is a function from sequences of positive integers to infinite 
sequences of positive integers.  If X is the sequence 
{x_1,x_2,...x_t} and if Y = P(X) then y_n for n = 1,2,3,... is 
the number of ways of partitioning the integer n into elements 
of X.  

We will use the following notation:  If X is a sequence of 
positive integers then (1)X = X  and  (n)X = P((n-1)X).    
In this notation (a)x_b refers to the bth element of (a)X.
Also, we will use [abc...z] to denote a partition of a 
number, eg [2221] is a partition of 7.


CYCLE OF PARTITION SEQUENCES

We'll start by proving a few things about cyclical partition 
sequences.  First, we obviously have  (a)X = (b)X  if  a = b 
modulo the (finite) cycle length.

Now let k be the smallest positive number in (1)X.  It follows 
that (2)x_k = 1, and so  (3)x_1 = 1, and (4)x_1 = 1, ... and so
on to (1)x_1 = 1.  Therefore k = 1.  Thus, the first element of 
all the sequences in any finite cycle is necessarily 1.  If no 
member of (1)X is greater than 1, then then we have  (1)X = 
{1,1,1,1,1...} and the cycle has length 1.  

On the other hand, if (1)X does contain a number greater than 
1, then let k denote the smallest such number.  It follows that 
(2)x_n = 1  for all n less than k, and (2)x_k = 2.  (The two 
partitions being [11...11] and [k].)  Therefore (3)x_2 = 2,  
so  (4)x_2=2, and so on to (1)x_2 = 2.   Therefore k = 2.  Thus, 
unless a cycle consists entirely of sequences of the form 
{1,1,1,1..} (which has period 1), it must consist of sequences 
each of which starts with {1,2,...}.

We wish to prove a Lemma that will enable us to generate a 
small number terms in a suggested cycle and then know that these 
generate the rest of each of the sequences in the cycle without 
contradictions - ie that they define a cycle which exists.  For 
example, we wish to prove that {1,2,2,4,5,7,9,12,..} is the 
start of one and only one sequence X, such that X=P(X).

Suppose we have generated the first n terms of each sequence 
in our suggested/hypothesied cycle H (hcycle with n terms).
For example, the first 6 terms of the sequences in a 
hypothesized two-step cycle might be 

              {1,2,3,4,6, 9}
              {1,2,3,5,6,10}

In general we define an "hcycle" as an ordered set of finite 
sequences such that (k+1)h_j (the jth term of the the (k+1)th 
sequence in the set) is the number of partitions of j into 
elements of (k)H (the kth sequence in the set) where k is 
modulo the cycle length.

We say a hcycle has the property K if each sequence in the set 
is the same length, n, and contains the numbers 1, 2 and an odd 
number less than n and greater than 1, and for each sequence the 
last (nth) term is greater than n.  Our example above has the 
property K as both sequences are length 6, contain 1 and 2, 
contain 3 (an odd number less than 6) and have final terms (9 
and 10) which are greater than 6.

LEMMA:  A h-cycle with property K defines an ordered set of 
infinite sequences which form a cycle under P.  (i.e., they 
define a set of cyclical partition sequences, which means that 
when we are trying to generate c.p.seqs we only need to find 
a hcycle with property K.)

PROOF:  As all the sequences contain 1 and 2 they are all 
non-decreasing (because we may simply add another 1 to each of 
the partitions of n to find at least as many partitions of n+1).

Considering one of the sequences, say (2)H, let us call L_n the 
set of the partitions of the number n into elements of (1)H.  
Thus |L_n| = (2)h_n.  Similarly we have  (2)h_n+1  as the number 
of partitions of n+1 into elements of (1)H.  As noted above, the 
sequences are non-decreasing, so (2)h_n+1 >= (2)h_n.

Moreover, we know that  (2)h_n+1  is strictly greater than 
(2)h_n.  This follows because (1)H contains an odd number less 
than n, called a, so we have either:

  n even:  [2...21] and [a2...211] are members of L_n+1 
           but [a2...22] (an extra 2 instead of two 1s) 
           is also a member of L_n+1 which is not derived 
           from L_n by adding another 1 to a member of L_n.

  n odd:   [2...211] and [a2...21] are members of L_n+1 but 
           [2...22] (an extra 2 instead of two 1s) is also a 
           member of L_n+1 which is not derived from L_n by 
           adding another 1 to a member of L_n.

It follows that
                  (2)h_n+1   >=   (2)h_n  +  1

and so
            (2)h_n+1    >=    n + 1 + 1    >    n + 1

Similarly we add (3)h_n+1 to (3)H, (4)h_n+1 to (4)H, etc.  As 
(1)h_n+1 is greater than n+1 we have that the number of partitions 
of n+1 into elements of (1)H is still (2)h_n+1.  Thus we have 
produced a new hcycle which has property K and is �longer�, each 
sequence having n+1 terms instead of n.  (It should be noted that 
there was only one possible hcycle which could have been generated 
from the one given, such that each sequence in the given hcycle 
constituted the first n terms of the corresponding sequence of 
the new hcycle.)

We can therefore generate, in only one way, a sequence of further 
hcycles, each larger than the last.  Thus we can generate an 
hcycle as large as we want.  This essentially defines the set
of infinite sequences forming a cycle, since we can use a series 
of hcycles to generate as many terms of them as needed.  (The 
sequence of hcycles �converges to� the set of infinite sequences 
which form a cycle which we were after.) 
END OF LEMMA


With this lemma in mind it's quite trivial to prove (by simply 
examining about 10 cases on a tree - checking each branch to see
whether the first sequence in the cycle contains a particular 
number - and eliminating those that lead to contradictions until 
we are left with an hcycle with property K at the end of each 
branch) that the only cycles of partition sequences are the 
following four:

  period 1:   {1,1,1,1,1,1,...}

  period 1:   {1,2,2,4,5,7,...}

  period 2:   {1,2,3,4,6,...} --> {1,2,3,5,6,...}

  period 2:   {1,2,2,4,4,6,7,10,...} --> {1,2,2,4,4,7,7,12,...}


[KSB Note:  To illustrate the process that leads to these results, 
recall that every sequence in a partition cycle must begin with 
{1,2,...}.  Since the sequence is non-decreasing, the possible
third members of the initial sequence (1)X are 2, 3, or some number 
greater than 3.  The sequence of sequences in these cases would 
then be
            Case 1            Case 2         Case 3

 (1)X     {1,2,2,...}       {1,2,3,...}     {1,2,[k>3],...}
 (2)X     {1,2,2,...}       {1,2,3,...}     {1,2,2,...}
 (3)X     {1,2,2,...}       {1,2,3,...}     {1,2,2,...}
 etc.        etc.              etc.            etc.

Obviously Case 3 is ruled out, because every subsequent sequence
is of the form {1,2,2,...} so it can't return to it's starting
sequence.  However, Cases 1 and 2 are both possible, so we
proceed to examine the possibilities for the fourth numbers in
(1)X, and then for the fifth numbers, and so on.  Eventually 
each of the branches of possibilities leads to cases where the 
nth term is greater than n, and from that point onward the results 
are uniquely defined, i.e., we no longer have any choice about 
what the next terms will be, and they depend only on the members 
prior to the nth term.  Thus the periodicity is fully determined 
by these leading terms.]



FURTHER DISCUSSION

I�m guessing that �most�, if not all, infinite sequences of 
positive integers approach one of these four cycles (under the 
operation P).  (Here the term �approach� means that taking the 
sequence of sequences which starts with the sequence given, 
q_1=X, and is such that q_n = P(q_n-1), called Q, for any given 
positive integer N there exists a number M such that, for all 
m > M, q_m agrees with one of the cyclic sequences in the first 
N elements.)

Taking a given sequence X:
[If X contains all 0�s then (2)X=(n)X={0,0,0,...} for all n >=2.]
Otherwise, let k be the smallest non-zero number in the sequence.
Therefore (2)x_k = 1.  If (2)x_k only contains 1s then it is 
{1,1,1,...}  Otherwise, let m be the smallest number in (2)X 
greater than 1.  Therefore (3)x_m = 2.  Therefore (4)x_1=1, 
(4)x_2=2.

Similarly consider the case that (3)X does or does not contain 3,
and so on.  Following this kind of argument, exactly the same as 
the method used to find the cycles in the first place, we find 
that all (as usual, ignoring those which become {0,0,0,...} or 
{1,1,1,...}) sequences eventually (quite quickly, usually around
4 iterations) have property J_n - That their first n elements 
correspond to the elements of a sequence in a hcycle, H, with 
property K and length n.

Once we have a sequence, X, with property J_n  we know (by exactly 
the same reasoning as in Lemma 1) that (2)X has property J_n+1, 
implying (3)X has property J_n+2, etc.  I.e. that X will approach 
the cycle determined by the hcycle H.  The result of which is that 
all sequences of positive integers approach one of the four cycles.

NOTE:  Just to rigourize "approaches" or "converges to" as I've used 
them: Define a set whose elements are all the sequences of positive 
integers and a distance function on this set is such that: For 
A != B the distance between two points/elements A and B is 1/(1+h) 
where h is the number of consecutive elements, starting with the 
first, on which A and B agree; For A = B the distance between A 
and B is 0.  For example, {1,2,3,4,5,..} and {1,2,3,7,16,...} are 
1/(1+3) apart.  This is trivially a metric space and is complete.  
Thus we can speak of sequences of sequences "converging to" or 
"approaching" a limit as we usually do.


GENERALIZATION

Next we might consider the function P2 from sequences of positive 
integers to infinite sequences of positive integers.  Where if 
Y = P2(X) then y_m is the number of ways of partitioning m+1 into 
elements of X.   And then the functions P3,P4,...,Pn,... defined in 
a similar manner:  if Y=Pn(X) then y_m is the number of ways of 
partitioning m+n-1 into elements of X.  (Thus P and P1 are the 
same.)  

Notice that the number �0� is needed for these higher n�s as you 
run into problems otherwise - you can�t always partition a number
using the elements given.  So just say that you can�t use 0 when
partitioning, meaning 1+2+0+0 is the same as 1+2.

We might form conjectures about the number and periods of cycles of
�Pn partition sequences�.  As another question: Do all sequences 
approach a cycle of �Pn partition sequences� for all n?