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 some of his additional comments. ================================================================== 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?

Return to MathPages Main Menu