## Partition Transform Cycles

```Consider the two sequences A_k and B_k,  k=1,2,3,... with the values
shown below

A:  1,2,3,4,6,9,11,15,19,25,31,41,49,61,75,91,110,134,157,189,...

B:  1,2,3,5,6,10,12,17,22,29,36,48,58,73,91,111,134,165,197,236,...

These two sequences are "duals" of each other in the sense that A_n
is the number of partitions of n into elements of B, and B_n is the
number of partitions of n into elements of A.

In general, given two sequences X and Y, we write X = P{Y} to indicate
that X_n is the number of partitions of n into elements of Y.  Thus,
the above sequences satisfy the equations A=P{B} and B=P{A}.

This raises the question of whether there exist higher order cycles
of partition sequences, such as a sequences X,Y,Z such that
X=P{Y}, Y=P{Z}, and Z=P{X}.  I posed this question on the internet
(it was Question #22 on a list of 23 questions), and received an
email from Dan Ford in January 1996 proving that there are only four
cycles of partition sequences, none of which have period greater
than 2.  Here's a lightly edited version of Dan's proof along with

==================================================================
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
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

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?
```