Cranks Andt Cores
Cranks Andt Cores
Cranks Andt Cores
Summary. New statistics on partitions (called cranks) are defined which com-
binatorially prove Ramanujan's congruences for the partition function modulo 5,
7, 11, and 25. Explicit bijections are given for the equinumerous crank classes. The
cranks are closely related to the t-core of a partition. Using q-series, some explicit
formulas are given for the number of partitions which are t-cores. Some related
questions for self-conjugate and distinct partitions are discussed.
1. Introduction
Let p(n) be the number of partitions of n [1]. Dyson [7] proposed a combinatorial
proof of Ramanujan's congruence
p(5n+4)-O mod5.
He defined an integral statistic on partitions, called the rank, whose value rood 5
split the set of partitions of 5n + 4 into 5 equal classes. He further conjectured that
the rank also proved
p(7n + 5) - O m o d 7 ,
and hypothesized a statistic, called the crank, which would similarly prove
p(lln+6)-0 modll.
Atkin and Swinnerton-Dyer [5] proved Dyson's conjecture for 5 and 7. In [9], a
crank for 11 as well as new cranks for 5 and 7 were found relative to vector
partitions. Later, Andrews and Garvan [3] were able to define a crank, in terms of
ordinary partitions, for 5, 7 and 11, thus completing the solution of Dyson's crank
conjecture. New relations for the crank of partitions mod 8, 9 and 10 have been
found in [10].
Explicit bijections between these equinumerous classes have not been found in
any of these three cases. This should be related to another possible approach to
these problems: split the set of partitions of 5n + 4 into p ( 5 n . + 4)/5 classes, each of
size 5. Hopefully, the bijections among the five classes should be realized by a 5-
cycle which acts on all partitions of 5n + 4 with no fixed points. The orbits of the 5-
cycle are the p ( 5 n + 4)/5 classes. A crank statistic should be defined which is
{0, 1, 2, 3, 4} on an orbit. A 5-cycle, but no crank, was found by computer in [11].
In this paper, we complete this program by finding dihedral groups of size 10, 14,
and 22 which act on the partitions of 5n + 4, 7n + 5, and 1 In + 6, respectively. The
5 (7 or 11) cycles in these groups have no fixed points, thus proving the con-
gruences. We also define new statistics on partitions, i.e. new cranks, which split the
set of partitions into equinumerous classes. A cycle in the dihedral groups increases
the crank by 1, thus supplying an explicit bijection between the crank classes. Our
definitions of the cycles and the cranks are completely combinatorial.
The key ingredients to our proof are two bijections for partitions and t-cores,
which are given in w They allow us to find dihedral groups as symmetry groups of
quadratic forms. There are interesting q-series attached to these forms, and these q-
series imply some remarkable explicit formulas (Theorems 4 and 5 in w for the
number of partitions which are t-cores, t = 5 or 7. The explicit cranks are given in
Theorems 2 and 3, and in Proposition 1 of w and w A crank for 25n + 24 is given
in w Similar bijections and generating functions for self-conjugate partitions and
partitions with distinct parts are given in w and w
We shall use the notation for generating functions from q-series, e.g.
k-1
(a;q)k = I~ (1 - a q l ) ,
i=O
SO
p(n)q" = 1
.:o (q;q)~
2. Two bijections
1 ~ q89 z + ~,.7~
~oP(n)q "
d
(qt;qt)~ ;~.i =0
(2.3)
n=
~eZ'
We now give Bijection 2, and sketch Bijection 1.
Let 2 be a t-core. Define the vector n 42(~) in the following way. Label a cell
=
in the ith row and jth column of ~, by j - i m o d t. (This is called the t-residue
diagram in [13, p. 84].) We also label the cells in column 0 in the same way, and call
the resulting diagram the extended t-residue diagram. A cell is called exposed if it is
at the end of a row. Region r of the extended t-residue diagram of~ is the set of cells
(j,j) satisfying t(r - 1) < j - i < tr. We now define ni to be the m a x i m u m region of
2 which contains an exposed cell labeled i. Since column 0 contains infinitely m a n y
exposed cells, ni is well-defined.
If an exposed cell labeled i lies in region r, then there is an exposed cell labeled i
in each region < r . F o r example, in region r - 1, if i is not exposed, then the rim
h o o k whose northeast head is i in region r, and whose tail is i + ! in region r - 1
has length t. (Note: If i = t - 1, the rim hook will lie entirely in region r.) This
contradicts the assumption that 2 is a t-core.
N o t e that the size of the Durfee square of 2 is the sum of the positive ni's, since
this is the number of exposed cells in positive regions.
We next verify that n o + n 1 + . . . + n,-1 = 0. Let ~' be the conjugate
of ~. First we show that if 4 2 ( ~ ) = ( n o , nl . . . . , n t - 1 ) , then ~ 2 ( 2 ' ) =
( - n t - i, - n t - 2, " ' ", - n o ) . Let a cell labeled i be exposed in region r of 2, so that
i + 1 lies above i. In 2', the cell corresponding to i + 1 will be labeled t - i - 1, lie
in region 1 - r, and not be the last cell in its row. Thus t - i - ! is not exposed
in region 1 - r of z'. This shows that if i is exposed in region r of ~, r < ni; then
t - 1 - i is not exposed in region r of ~,', r > 1 - n~. A similar argument shows that
if a b o u n d a r y cell labeled t - i - 1 is not exposed in region 1 - r, then i is exposed
in region r. This verifies the claim about 42(2'). Since the size of the Durfee square is
unchanged by conjugation, the sum of the positive n~'s must be equal to minus the
sum of the negative n~'s; that is, n o + n t + . . . + n t_ 1 = O.
4 F. Garvan et al.
The inverse m a p to ~bz is easy to find: if (no, n~ . . . . . n,_ 1) is given, then the
exposed cells in each region are known. This in turn gives the lengths of each row of
the Ferrers diagram of ~, and thus ~..
Finally we show that if ~b2(~) = n, then ~ is a partition of the exponent in
Bijection 2. The n u m b e r of cells to the right of the main diagonal of the Ferrers
diagram of 2 is
ini + t(21 ) 9
nz>O
For the cells below the main diagonal, we take ~', to find
- ~ (t- l-j)nj+t
n~<O
There are
Z
nt>O
/'/i
cells on the main diagonal. The sum of these three terms is the exponent ofq in (2.3).
We quickly sketch q~l using the notation in Bijection 2. Given 2, we construct t
biinfinite words in the letters N and E, w o . . . . . wt- 1. T h e j t h letter o f w i is E ifi is
exposed in region j of 2, otherwise the j th letter is N (not exposed). If 2 is a t-core,
then each word wl is an infinite sequence of E's followed by an infinite sequence of
N's. In this case, 2 = ~, and 21 = ~ for all i. Otherwise there is an E to the right of
some N. Find the rightmost E, say in positionj. Find the rightmost N to the left of
this E, say in position k < j. Delete a rim hook in 2 whose northeast head is the cell
corresponding to E, and whose southwest tail is adjacent to the cell corresponding
to N. Place a part of sizej - k in 21. The new partition has N ' s in w~ from positionj
on, thus the E's have been pushed to the left. This operation can be done in any
order whatsoever, to finally obtain the t-core of 2, ~,. The parts of each 2~ a p p e a r in
increasing order.
3. Cranks
In this section we give the cranks (Theorem 2) and the cycles which give bijections
for these crank classes.
Let r be a residue class of t, and consider p(tn + r). O n the right side of (2.3), all
exponents of q which are equivalent to r mod t lie in the multisum. Since ft. 1 = 0,
we have 89IIn II2 ~_ 0 m o d t. Thus we have
It should be noted that other identities for the generating functions of p(tn + r),
which yield R a m a n u j a n ' s congruences, have been found by others. The most
famous of these is R a m a n u j a n ' s [19, (17) p. 213] identity for p(5n + 4), which was
considered by H a r d y in agreement with M a c M a h o n as R a m a n u j a n ' s most beau-
tiful identity [19, p. xxxv]. R a m a n u j a n [19, (18) p. 213] also found an analog for
p(7n + 5). In fact for t = 5", 7" similar identities have been found by Watson [20].
Using the theory of m o d u l a r functions an analog for p(1 In + 6) was found by Fine
[8, (3.25)] and extended to higher powers of 11 by Atkin [4]. However, these other
identities are of a different nature than (3.2) and do not yield obvious cranks.
Further, Fine's identity for t = 11 and R a m a n u j a n ' s identity for t = 5 or t = 7 are
dissimilar so it is surprising that an identity like (3.2) holds for all three values t = 5,
7 and 11.
6 F. Garvan et al.
(t = 5) 4no + nl + n3 + 4n4 f o r 5n + 4,
(t = 7) 4no + 2nl + n2 + n4 + 2n5 + 4n6for 7n + 5,
(t = 11) 4n o + 9n~ + 5n 2 + 3n 3 + n 4 + n 6 + 3n 7 + 5n 8 + 9n 9 + 4n~ o for
lln+6.
The new crank is not equal to the rank or the old crank. One can verify this on
the 5 partitions of 9 which are 5-cores: 621,522, 51111, 33111, and 321111.
4. More cranks
T h e cranks in w depend only upon the t-core ~ of 2, and thus use Bijections 1 and 2.
In this section we give two simpler ways (Proposition 1 and T h e o r e m 3) of
computing crank(2), (one which is a polynomial in the parts of 2), thus avoiding
Bijections 1 and 2.
First, let rk(2) be the n u m b e r of cells in the t-residue diagram of 2 which are
labeled k rood t. Suppose that 2 is a t-core. A relation between the rk'S and the ni's
can be found by counting the cells in a row ending with i in region nl. It is
t--I
r k = ~, (n2/2 + niz(i >= k)) (4.1)
i=O
where
1/2 i f S is true,
x(S)= -1/2 if S is false .
(1) r 1 + 2 r 2 - 2 r 3 - r 4 f o r 5n+4,
(2) 2rl + r2 + r3 - r 4 - r 5 - 2r 6 f o r 7n + 5,
(3) - 6r 1 - 4r z - 2r 3 - 2r 4 - r 5 + r 6 + 2r 7 + 2r 8 + 4r 9 + 6 r i o f o r l l n + 6 .
P r o o f W e a l r e a d y k n o w from T h e o r e m 2 that c e r t a i n l i n e a r c o m b i n a t i o n s give the
c r a n k for t-cores, e.g. (2, - 1, 1, - 2) for t = 5. If we m u l t i p l y this l i n e a r c o m b i n a -
tion by 3, we o b t a i n (1) for t-cores. W e reverse the sign to o b t a i n (2), a n d (3) is
i m m e d i a t e from T h e o r e m 2. N o w c o n s i d e r (1)-(3) as definitions of a c r a n k for a n y
p a r t i t i o n 2, n o t j u s t t-cores. R e m o v i n g a rim h o o k of l e n g t h t from 2 reduces each
r k by one. T h e a b o v e linear c o m b i n a t i o n s do n o t change, since the s u m of all
of the coefficients is zero. T h u s the c r a n k c a n be defined b y P r o p o s i t i o n 1 for all
p a r t i t i o n s 2. []
Thus
Since q t ( t - 1 - i) = q~(i) rood t, and q,(i) is a linear function of pt(i), the result
follows. []
5. Associated q-series
From (2.1) there is an explicit generating function for the partitions of n which are t-
cores. We investigate these functions for t = 5, 7, and 11, and give explicit formulas
for as(n ) and a7(n ) in Theorems 4 and 5.
The five cycle in w implies that as(5n + 4) - 0 mod 5. However, much more is
true,
as(5n + 4) = 5as(n ) . (5.1)
We give two proofs of (5.1): one which is analytic, and proves more (Theorem 4),
and another which is a bijection.
Theorem 4. L e t n + 1 = 5CP~ 1 . 9 9 es'a~'~b'~l . . . qb, b e t h e p r i m e f a c t o r i z a t i o n of n + 1
into primes Pi = 1, 4 mod 5, qj ~ 2, 3 mod 5. T h e n
and
p~,+l _ 1 bi+l
as(n) = Y 1!I ~i2_~ 1LI qj + ( - 1 ) b~
i=i j=l qj +
Proof Clearly (2.1) implies
(qS;qS)~
as(n)q" =
,=o (q;q)oo
However an identity of Ramanujan ([2, (3.46)] or [6]) is
(q,;qS)~
q (q;q)~ -,=o g g-r
where ( b ) is the Legendre symbol. Clearly the right side of (5.2) is
n=l
so
Since (~)/d is multiplicative, (5.3) and [12, Theorem 265] implies that a s ( n - 1) is
multiplicative. It remains to evaluate a s ( p " - 1) for primes p, which can be done by
(5.3). []
The combinatorial proof of (5.1) is explicit: given a partition ~. of n which is a 5-
core, find five partitions 0o, 01, 02, 03, 04, of 5n + 4 which are also 5-cores. Let
q52(~.) = ff~. We now give the image under 4~2 of the five partitions of 5n + 4.
(1) ~bz(0o)=(m l + 2 m 2 + 2 m 4 + l , -m 1-mE+m3+m4+l,2ma+m2
+2m3, - 2 m 2 - 2 m 3 - m 4 - 1 , -2ml-m3-2m4-1),
Cranks and t-cores 9
Let a'(n), b(n), c(n) denote the coefficient of q" in the expansion of each of the
three functions in (5.4) so that
8aT(n) = a'(n + 2),
a'(n) + b(n) = c(n).
We will give in Lemmas 1 and 2 explicit formulas for b(n) and c(n), resulting in an
explicit formula for aT(n) in Theorem 5.
The proof of Theorem 4 analogously establishes the multiplicativity of c(n). We
delete the details. The resulting explicit formula is given in L e m m a 1.
Lemma 1. I f n . .7Cp"11
. . Ps,,sqlbi 9 9 9 qb, is the prime factorization of n into primes
Pl - l, 2, 4 m o d 7 , and qj --- 3, 5, 6 m o d 7 , then
q2bj+E+(__l)bJ
c(n) 72c 15 p2a,+2__l h
''
i=1 p l2 = i- j "="l q~ + 1
b(pm) = b(p)b(pm-1) - ( P ) p 2 b ( p m- 2)
Proof I f q = e 2~iz, the generating function B(z) for b(n) (see (5.4)) can be considered
a function of z in the upper half plane. In terms of the classical q-function it is
B(z) = (rl(z)q(7z)) 3, which is a cusp form of level 7, weight 3, and character
z(n) = (~) [14, Prob. 12, 13, p. 145]. Since this space of cusp forms is one-
dimensional, B(z) must be an eigenform for the Hecke operators T,. This proves the
multiplicativity of b(n), and the three term recurrence follows from the Euler
product for the associated Dirichlet series [14, p. 160 (5.11)]. []
To find an explicit formula for b(n), we need only find b(p) for all primes p. The
three term recurrence in Proposition 2 gives b(pm), and multiplicativity gives b(n)
for all n. The next proposition gives the values of b(p).
Proposition 3. Suppose p is an odd prime, l f p --- 3, 5 or 6 m o d 7 , then b(p) = O. I f
p - 1, 2 or 4 m o d 7, let p = x 2 + 7y 2, where x and y are positive integers. Then
b(p) = 2(x 2 - 7y2).
Remark. The result also holds for p = 2 except in this case x = y = 89
Proof F r o m Jacobi's identity for (q;q)3 1-12, T h m 357] we find that
b(p) = ~ ( - 1)m+"(2m + 1)(2n + 1).
m,n>O
( 2 m + 1) 2 + 7 ( 2 n + 1) 2 = 8 p
Let
2 = 2 = ~ "
It follows t h a t 2p factors as
b(n) = 0 if some bj is o d d ,
We can define a group G which acts on the set of partitions oftn + r: G = G 1 x St,
where G x is the a u t o m o r p h i s m group of the quadratic form in Bijection 2, and St is
the symmetric group on t letters. F o r example, for 5n + 4, G -- D 5 x $5, where D 5
is the dihedral group of order 10. We have concentrated on the action of G1 for
congruences. We can also use St for congruences, and do so in this section to find a
crank for
p(25n + 24) = 0 m o d 2 5 . (6.1)
The group G -- D 5 x $5 for 5n + 4 contains two c o m m u t i n g five cycles which
generate a subgroup of order 25. If each five cycle has no fixed points, then G will
have no fixed points, and the orbits of G will have size 25. We have seen that the five
cycle inside D 5 has no fixed points. Since the five cycle in $5 could have fixed points,
we consider two cases to define the crank, which will be an ordered pair of integers,
each between 0 and 4. This ordered pair could be considered as the base 5
expansion for a n u m b e r between 0 and 24.
Theorem 6. A crank statistic for partitions 2 of 25n + 24 is given by the following
algorithm.
(1) Find ~b1(2) = (~., 20, 21,2z, 23, 24) given by Bijection 1.
(2) Let crank(2) be the following ordered pair of integers:
Suppose that 20 = 2A = 22 = 23 = 24, so that ~ is a partition of 25s + 24 for
some s. Let #1 = 75s+4(2) and/~2 = 7s(Pl) be partitions of Ss + 4 and s respectively
(see w Put
crank(2) = (crank(lq ), crank(p2)). (i)
Suppose that some 2 i 4: 2~, so that the five cyclic permutations of(20, 21, 22, 23,
24) are distinct. Order these five tuples in lex order, and define the crank of the ith
tuple to be i - 1. Put
crank(2) = (crank(2), crank((2 o, 21, 22, 23, 24))). (ii)
Proof. The vectors Vn(0i) = ~. in w form an orbit under C5 _-< G1, so that the cranks
of these five partitions are {0, 1, 2, 3, 4}.
The second part of the definition similarly interprets C 5 x C5, as a s u b g r o u p
of G. []
C r a n k s a n d t-cores 13
In Theorem 6(2)(ii) the lex order crank can be replaced by the following
statistic. Find ~b1(2), and if
7. S e l f - c o n j u g a t e partitions
and
( • q• • q 2 • ) •
where (
Z2o(n) = ) 0 1 if (n, 10) > 1,
[
( _ 1)yr,- 1) otherwise.
Thus only odd n occur in (7.2), and the appropriate signs for odd n m o d 20 are
+ - 0 - + - + 0 + - . (7.2) follows from the 61//6 summation formula 1-2, (3.1)].
The identity (7.2) also follows from an identity of R a m a n u j a n [21, (1) p. 60] and
Jacobi's formula for r2(n ), the n u m b e r of representations of n as a sum of two
squares 1-12, T h m 278]. The functions r2(n ) and ascs(n) are related by
where
J(2, 4 . . . . . t - 1) for t odd
((1,3, ,t 1) forteven,
and It/2] is the integral part of t/2. Using (7.4) dissections of ( _q;q2)~ due to
Kolberg [16] can be easily derived.
A bijection analogous to Bijection 1 for partitions with distinct parts has been
given by Morris and Yaseen 1-17]. In this section we give the appropriate version of
Bijections 1 and 2 for these partitions.
We begin with notation. Let pd(n) be the number of partitions 2 of n with
distinct parts. Given such a 2, the shifted Ferrers diagram of 2, S(2), is the Ferrers
diagram of 2 with the ith row shifted to the right by i - 1 cells. The doubled
partition of 2, denoted 22, is defined by adding 2g cells to the i - 1st column of S(2).
For example, if 2 = 31, then 22 = 431. We let D D denote the set of doubled distinct
partitions 22. We define the t-core of 22 as the usual t-core of 22. Let DDt-core be
the set of partitions which are t-cores of doubled distinct partitions, and let add,(n)
Cranks and t-cores 15
be the number of these which are partitions of n. We state without proof that
DD~_ ~o~ ~ DD, thus addt(n) = 0 if n is odd.
By restricting Bijection 1, we find a bijection for doubled distinct partitions. We
must take the conjugate of the 2o in ~bx to find 20 for ~b3.
n= 0
pd(n)q ~ " = (_q2~;qZt)~
(q2t;qZt)~- 1)/2 n = O
~ aad,(n)q" for t odd (8.1a)
and
( __qt;qt)~ ~ ~o
~, pd(n)q 2" = (q2t;~2t)~-2)/~ n=~Oaddt(n)q" for t e v e n . (8.1b)
n=O =
where
= ~'(1, 3 . . . . . t -- 2) for t o d d ,
/. (2, 4, , t 2) for t e v e n .
9. Remarks
found. There is reason to believe these groups are larger than C 2. It seems that an
unusually high proportion of the coefficients of al l(n) are divisible by 11 so there
may be more 11-cycles. A higher proportion of the coefficients are divisible by 5. In
fact, using modular forms which appear in an analog of (5.4) for t = 11, we can
prove the following theorem.
References
1. Andrews, G.E.: The theory of partitions. Encyclopedia of Mathematics and Its Applications,
Vol. 2. Rota, G.-C. (ed.), Reading, MA: Addison-Wesley 1976 (reissued by Cambridge Univ.
Press, London and New York, 1985)
2. Andrews, G.E.: Applications of basic hypergeometric functions. SIAM Rev. 16, 441-484
(1975)
3. Andrews, G.E., Garvan, F.G.: Dyson's crank of a partition. Bull. Am. Math. Soc. 18, 167 171
(1988)
4. Atkin, A.O.L.: Proof of a conjecture of Ramanujan. Glasgow Math. J. 8, 14-32 (1967)
5. Atkin, A.O.L., Swinnerton-Dyer, P.: Some properties of partitions. Proc. Lond. Math. Soc.,
III. Ser. 4, 84 106 (1954)
6. Bailey, W.N.: A note on two of Ramanujan's formulae. Q. J. Math. Oxf. II. Ser. 3, 29-31 (1952)
7. Dyson, F.: Some guesses in the theory of partitions. Eureka (Cambridge), 8, 11~15 (1944)
8. Fine, N.: On a system of modular functions connected with the Ramanujan identities. Tohoku
Math. J. 8, 149 164 (1956)
9. Garvan, F.: New combinatorial interpretations of Ramanujan's partition congruences mod 5,
7 andl 1. Trans. Am. Math. Soc. 305, 47-77 (1988)
10. Garvan, F.: The crank of partitions mod 8, 9 and I0. Preprint
11. Garvan, F., Stanton, D.: Sieved partition functions and q-binomial coefficients. Math.
Comput. (to appear)
12. Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. London: Oxford
Univ. Press 1979
13. James, G., Kerber, A.: The Representation Theory of the Symmetric Group. Reading, MA:
Addison-Wesley 1981
14. Koblitz, N.: Introduction to Elliptic Curves and Modular Forms. New York: Springer, 1984
Cranks and t-cores 17
15. Kolberg, O.: Some identities involving the partition function. Math. Scand. 5, 77-92 (1957)
16. Kolberg, O.: An elementary discussion of certain modular forms. Univ. Bergen Arb. naturv, r.
Nr. 19. (1959)
17. Morris, A., Yaseen, K.: Some combinatorial results for shifted Young diagrams. Math. Proc.
Camb. Philos. Soc., 99, 23-31 (1986)
18. Olsson, J.: Frobenius symbols for partitions and degrees of spin characters. Math. Scand. 61,
223-247 (1987)
19. Ramanujan, S.: Collected Papers of S. Ramanujan. London, New York: Cambridge Univ.
Press 1927 (reprinted by Chelsea, New York, 1962)
20. Watson, G.N.: Ramanujans Vermutung /iber Zerf/illungsanzahlen. J. Reine Angew. Math.
179, pp. 97-128 (1938)
21. Watson, G.N.: Proof of certain identities in combinatory analysis. J. Ind. Math. Soc. 20, 57-69
(1933)
Oblatum 16-IX-1989