Transcript q - Personal.psu.edu - Penn State University

Research in Integer Partitions:
Alive and Well
James Sellers
Associate Professor and Director,
Undergraduate Mathematics
Penn State University
Opening Thoughts
Thanks for this opportunity to speak.
It is a true privilege to do so.
Who Is This Guy?
Professionally: Director of UG Studies and
Associate Professor at PSU - administrator,
teacher, researcher, writer, …
Personally: Husband, father of five, assistant
football and baseball coach, webmaster for
four different organizations, Sunday School
teacher, …
Who Is This Guy?
Goals for the Talk
Share some important definitions and
examples related to partitions
Discuss the early study of integer
partitions (Leonhard Euler)
Share some 21st century research which
generalizes Euler’s early results
Basic Definitions
A partition of an integer n is a nonincreasing sequence of positive integers
which sum to n.
Each integer used in a partition is
known as a part.
Example
The partitions of n = 5 are:
5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
Notation
Let p(n) be the number of partitions of n.
p(3) = 3
p(5) = 7
p(50) = 204,226
Historical Motivation
In 1740, Philippe Naude sent a letter to
Leonhard Euler asking the following:
“How many ways can the number 50 be
written as a sum of seven different positive
integers?”
What an impact Naude’s question had on
mathematics!
Leonhard Euler
Born April 15, 1707 in
Basel, Switzerland
Died September 18, 1783 in
St. Petersburg, Russia
One of the most prolific
mathematicians of the 18th century
Leonhard Euler
Devout Protestant (father Paul was a
Protestant minister)
Married Katharina Gsell in 1734
Had 13 children; only 5 survived infancy
Claimed that he made some of his greatest
mathematical discoveries while holding a
baby in his arms with other children playing
round his feet
Leonhard Euler
Known for numerous mathematical
discoveries!
– Solution of the Basel Problem
– Even perfect numbers (converse of
Euclid’s result)
– Formula for polyhedra: v – e + f = 2
– Konigsberg Bridge Problem
(beginnings of graph theory)
– Integer partitions
– Much, much more!
An Advertising Break
Read William Dunham’s Euler: The
Master of Us All ! (MAA, 1999)
Generating Functions
A generating function for the sequence s(n) is
given by
S(q) = s(0) + s(1)q + s(2)q2 + s(3)q3 + …
As a result of answering Naude’s question,
Euler found a very natural infinite product
which served as the generating function for the
partition function p(n).
Generating Functions
Consider the following: Let
P(q) =
(1 + q + q2 + q3 + q4 + q5 + …) x
(1 + q2 + q4 + q6 + q8 + q10 + …) x
(1 + q3 + q6 + q9 + q12 + q15 + …) x
(1 + q4 + q8 + q12 + q16 + q20 + …) x
(1 + q5 + q10 + q15 + q20 + q25 + …) x
…
Generating Functions
This is, of course, the same as
P(q) =
(1 + q1 + q1+1 + q1+1+1 + q1+1+1+1 + …) x
(1 + q2 + q2+2 + q2+2+2 + q2+2+2+2 + …) x
(1 + q3 + q3+3 + q3+3+3 + q3+3+3+3 + …) x
(1 + q4 + q4+4 + q4+4+4 + q4+4+4+4 + …) x
(1 + q5 + q5+5 + q5+5+5 + q5+5+5+5 + …) x
…
Generating Functions
In fact, Euler proved that P(q) is the generating
function for the partition function p(n).
Thanks to the geometric series, note that P(q)
can also be written as
1
1
1
1
P(q) 



...
2
3
4
1 q 1 q 1 q 1 q
A Historical Sidenote
1
1
1
1
P(q) 



...
2
3
4
1 q 1 q 1 q 1 q
Euler considered the reciprocal of P(q)
and proved that it equals a very nice
power series. This result became known
as Euler’s Pentagonal Number Theorem.
A Historical Sidenote
Euler’s Pentagonal Number Theorem
leads to a very nice recurrence for p(n).
It was this recurrence which led English
mathematician Major Percy MacMahon
(1854 – 1929) to write down a table of
values of p(n) for n from 1 to 100.
A Historical Sidenote
And it was MacMahon’s table, broken up
into groups of five values each, which led
Srinivasa Ramanujan (1887 – 1920) to his
discoveries about congruences for p(n).
Back to Naude’s Question
Remember that Naude asked Euler
about the number of partitions of n
where the parts are distinct. How
does that change the generating
function in question?
Back to Naude’s Question
Well, instead of this…
P(q) =
(1 + q + q2 + q3 + q4 + q5 + …) x
(1 + q2 + q4 + q6 + q8 + q10 + …) x
(1 + q3 + q6 + q9 + q12 + q15 + …) x
(1 + q4 + q8 + q12 + q16 + q20 + …) x
(1 + q5 + q10 + q15 + q20 + q25 + …) x
…
we now want this…
Back to Naude’s Question
D(q) = (1 + q )(1 + q2)(1 + q3)(1 + q4) …
since “distinct parts” means each part can
appear at most one time.
Back to Naude’s Question
To Euler, this would have been a very
satisfactory result given his excellent
calculation skills.
Even without Euler’s excellent calculation
skills, this is indeed a very satisfactory result
today thanks to the advent of computer
algebra systems.
Back to Naude’s Question
So, for example, we have:
d(3) = 2
d(5) = 3
d(50) = 3658
Back to Naude’s Question
One last comment on Naude’s question is
in order. Naude asked:
“How many ways can the number 50 be
written as a sum of seven different
positive integers?”
The answer given by Euler is 522.
Back to Naude’s Question
Here is a “snapshot” of the opening
portion of one of Euler’s papers on
partitions.
This paper was originally published in
1753.
Euler’s Famous Discovery
Euler did not choose to be satisfied with
solving Naude’s question.
He considered how he could manipulate
D(q) = (1 + q )(1 + q2)(1 + q3)(1 + q4) …
and prove additional partitions results.
Euler’s Famous Discovery
Euler noted the following:
1 q
1 q 
1 q
2
That meant that Euler could rewrite D(q) as
Euler’s Famous Discovery
D(q) = (1 + q )(1 + q2)(1 + q3)(1 + q4) …
1 q 1 q 1 q 1 q





2
3
4
1 q 1 q 1 q 1 q
2
4
6
8
Notice that all the numerators cancel with
some of the denominators, leaving only
those denominators with odd exponents!
Euler’s Famous Discovery
That means we have
1
1
1
1
D ( q) 




3
5
7
1 q 1 q 1 q 1 q
Euler realized that this way of writing D(q)
had a never-before-seen partition-theoretic
interpretation!
Euler’s Famous Discovery
Theorem: For all positive integers n, the
number of partitions of n into distinct parts
equals the number of partitions of n into
odd parts.
Proof: The generating functions for the two
partition functions are the same.
Euler’s Famous Discovery
Example: n = 7
Distinct parts:
7
6+1
5+2
4+3
4+2+1
Odd parts:
7
5+1+1
3+3+1
3+1+1+1+1
1+1+1+1+1+1+1
Extension of Euler’s Theorem
To close this talk, I want to show you
two different sets of results related to
Euler’s famous theorem.
These were both recently published
(within the last few years).
Extension of Euler’s Theorem
Theorem: (Guy, 1958)
The number of partitions of n
into distinct parts with no
powers of 2 as parts equals the
number of partitions of n into
odd parts with no 1s as parts.
Extension of Euler’s Theorem
Theorem: (S, Sills, Mullen – EJC, 2004)
Let J be a set of non-multiples of m.
Let p1(n; m, J) be the number of partitions of n with
no part of the form mkj where j is an element of J
and where no part is allowed to appear more than
m - 1 times in any partition.
Let p2(n; m, J) be the number of partitions of n with
no part divisible by m and no part equal to j for each
element j of J.
Then, for all n, p1(n; m, J) = p2(n; m, J).
Extension of Euler’s Theorem
How does this fit with Euler and Guy?
Guy’s result is p1(n; 2, {1}) = p2(n; 2, {1}).
Euler’s result is p1(n; 2, {}) = p2(n; 2, {}).
Extension of Euler’s Theorem
Nifty corollary:
The number of partitions of n into distinct parts
where no part is the product of an odd prime and a
power of 2 equals the number of partitions of n
using only 1s and odd composites as parts.
This is just p1(n; 2, J) = p2(n; 2, J) where J is
the set of odd primes.
Extension of Euler’s Theorem
Theorem: (Plinio-Santos, 2001)
The number of partitions of n of the
form p1 + p2 + p3 + p4 + … such that
p1  2 p 2  p3  p 4  
equals the number of partitions of n
into odd parts.
Extension of Euler’s Theorem
Theorem: (S – Integers, 2003)
The number of partitions of n of the form p1 + p2 +
p3 + p4 + … such that
p1  k 2 p 2 k 3p3  k 4 p 4  
equals the number of partitions of n into 1s or
numbers of the form (k2+1)+ (k3+1) +…+ (km+1)
for some m.
Extension of Euler’s Theorem
Plinio-Santos’ result is the special case
k2 = 2, k3 = k4 = … = 1.
The proof technique in my paper
involves MacMahon’s Partition
Analysis, made popular in recent years
by Andrews, Paule, and Riese.
One More Advertising Break!
Conference on Undergraduate Research in
Mathematics (CURM)
Penn State University
November 9-10, 2007
www.math.psu.edu/ug/curm/
Closing Thoughts
Thanks again for the opportunity to
share!
I would be happy to answer any
questions you might have.