08 joao guerreiro

Prévia do material em texto

Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Partições de inteiros
Encontro de Novos Talentos em Matemática
João Guerreiro
6 de Setembro de 2008
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
O que é uma partição em inteiros?
Dado um inteiro n ≥ 0 uma partição em inteiros de n é uma
representação de n como uma soma (não ordenada) de inteiros
positivos.
Partições de 5:
5
4+ 1
3+ 2
3+ 1+ 1
2+ 2+ 1
2+ 1+ 1+ 1
1+ 1+ 1+ 1+ 1
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
O que é uma partição em inteiros?
Dado um inteiro n ≥ 0 uma partição em inteiros de n é uma
representação de n como uma soma (não ordenada) de inteiros
positivos.
Partições de 5:
5
4+ 1
3+ 2
3+ 1+ 1
2+ 2+ 1
2+ 1+ 1+ 1
1+ 1+ 1+ 1+ 1
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Função partição
Definição
Para n ≥ 0,
p(n) representa o número de partições de n.
Do exemplo anterior conclui-se que p(5) = 7.
Será que há uma fórmula para p(n)?
1, 2, 3, 5, 7, 11, 15, 22, 30, 42
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Fórmula
p(n) =
1
pi
√
2
∞∑
k=1
Ak(n)
√
k
[
d
dx
sinh(pik (
2
3(x − 124))1/2)
(x − 124)1/2
]
x=n
onde,
Ak(n) =
∑
0≤h<k, (h,k)=1
exp
pii k−1∑
j=1
j
k
(
hj
k
−
⌊
hj
k
⌋
− 1
2
)
− 2piihn
k

João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Grafos de Ferrers
Os grafos de Ferrers são uma forma de representar partições.
• • • • • • • •
• • • • •
• • • • •
• • • •
•
•
representa a partição 7+ 5+ 5+ 4+ 1+ 1.
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Exemplo
Teorema
p(n| ≤ m partes) = p(n|todas as partes ≤ m)
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Demonstração
Fazendo corresponder a cada partição o seu conjugado prova-se
facilmente o teorema.
• • • • • • • • • • • • • •
• • • • • • • • •
• • • • • 7−→ • • • •
• • • • • • • •
• • • •
• •
•
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Teorema de Euler
Teorema
p(n|partes distintas) = p(n|partes impares)
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Demonstração
Juntando e separando as partes podemos relacionar as partições de
ambos os conjuntos,
8+ 5+ 2 → (4+ 4) + 5+ (1+ 1)
→ (2+ 2) + (2+ 2) + 5+ 1+ 1
→ 5+ 1+ 1+ 1+ 1+ 1+ 1+ 1+ 1+ 1+ 1
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Demonstração
Para n = 7 obtemos a seguinte bijecção,
5+ 1+ 1 7−→ 5+ 2
3+ 3+ 1 7−→ 6+ 1
3+ 1+ 1+ 1+ 1 7−→ 4+ 3
1+ 1+ 1+ 1+ 1+ 1+ 1 7−→ 4+ 2+ 1
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Funções geradoras
Para que servem as funções geradoras?
Se quisermos calcular todas as partições com exactamente duas
partes ímpares < 6 basta fazer a seguinte multiplicação,
(q + q3 + q5)(q + q3 + q5) =
= q1+1+q1+3+q1+5+q3+1+q3+3+q3+5+q5+1+q5+3+q5+5 =
= q2 + 2q4 + 3q6 + 2q8 + q10
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Funções geradoras
Para que servem as funções geradoras?
Se quisermos calcular todas as partições com exactamente duas
partes ímpares < 6 basta fazer a seguinte multiplicação,
(q + q3 + q5)(q + q3 + q5) =
= q1+1+q1+3+q1+5+q3+1+q3+3+q3+5+q5+1+q5+3+q5+5 =
= q2 + 2q4 + 3q6 + 2q8 + q10
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Um resultado de Euler
(1+q1+q2+...)(1+q2+q4+...)(1+q3+q6+...)...(1+qk+q2k+...) =
=
∑
n≥0
p(n)qn
1
1− q .
1
1− q2 .
1
1− q3 ...
1
1− qk ... =
∑
n≥0
p(n)qn
∞∏
k=1
1
1− qk =
∑
n≥0
p(n)qn
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Um resultado de Euler
(1+q1+q2+...)(1+q2+q4+...)(1+q3+q6+...)...(1+qk+q2k+...) =
=
∑
n≥0
p(n)qn
1
1− q .
1
1− q2 .
1
1− q3 ...
1
1− qk ... =
∑
n≥0
p(n)qn
∞∏
k=1
1
1− qk =
∑
n≥0
p(n)qn
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Partições de um conjunto S
Podemos generalizar o resultado anterior para um conjunto S de
naturais (finito ou infinito).
∑∞
n=0 p(n|partes de S)qn =
∏
i∈S(1+ q
i + q2i + q3i + ...)
=
∏
i∈S
1
1−qi
O polinómio acima desgina-se por função geradora das partições
em partes de S.
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Partições de um conjunto S
Outro tipo de partições cuja função geradora pode ser obtida são
as partições em partes distintas.
∑∞
n=0 p(n|partes distintas de S)qn =
∏
i∈S(1+ q
i )
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Teorema de Euler
Após a introdução das funções geradoras podemos reescrever o
teorema de Euler:
Teorema∑∞
n=0 p(n|partes distintas)qn =
∑∞
n=0 p(n|partes impares)qn
Escolhendo o conjunto S como o conjunto dos naturais e dos
ímpares, respectivamente:∑∞
n=0 p(n|partes distintas)qn =
∏∞
n=1(1+ q
n)∑∞
n=0 p(n|partes impares)qn =
∏∞
n=1
1
1−q2n−1
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Demonstração
∞∏
n=1
(1+ qn) = (1+ q)(1+ q2)(1+ q3)...
=
(
1− q2
1− q
)(
1− q4
1− q2
)(
1− q6
1− q3
)(
1− q8
1− q4
)
...
=
1
(1− q)(1− q3)(1− q5)...
=
∞∏
n=1
1
1− q2n−1
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Demonstração
∞∏
n=1
(1+ qn) = (1+ q)(1+ q2)(1+ q3)...
=
(
1− q2
1− q
)(
1− q4
1− q2
)(
1− q6
1− q3
)(
1− q8
1− q4
)
...
=
1
(1− q)(1− q3)(1− q5)...
=
∞∏
n=1
1
1− q2n−1
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Demonstração
∞∏
n=1
(1+ qn) = (1+ q)(1+ q2)(1+ q3)...
=
(
1− q2
1− q
)(
1− q4
1− q2
)(
1− q6
1− q3
)(
1− q8
1− q4
)
...
=
1
(1− q)(1− q3)(1− q5)...
=
∞∏
n=1
1
1− q2n−1
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Identidades de Rogers-Ramanujan
Teorema
p(n|partes 2− distintas) = p(n|partes ≡ ±1 mod5)
p(n|partes 2− distintas > 1) = p(n|partes ≡ ±2 mod5)
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
p(n|partes 2− distintas)
Note-se que a função geradora das partições de m partes 2-distintas
pode ser escrita da forma seguinte:∑
0≤a1≤a2≤...≤am q
(1+a1)+(3+a2)+...+(2m−1+am) =
= qm
2∑
0≤a1≤a2≤...≤am q
a1+a2+...+am =
= qm
2∑
0≤a1≤a2≤...≤am−1
qa1+a2+...+2am−1
1−q =
= qm
2 1(1−q)(1−q2)...(1−qm)
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
p(n|partes 2− distintas)
Somando sobre a variável m obtém-se a função geradora destas
partições, ∑∞
m=0 q
m2 1
(1−q)(1−q2)...(1−qm)
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
p(n|partes ≡ ±1 mod5)
Para o termo do lado direito da equação também podemos obter
uma função geradora:
=
∏∞
n=1(1+ q
5n−1 + q2(5n−1) + ...)(1+ q5n−4 + q2(5n−4) + ...) =
=
∏∞
n=1
1
(1−q5n−1)(1−q5n−4)
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
2a Identidade de Rogers-Ramanujan
Analogamente, as funções geradoras que ocorrem na 2a Id. de
Rogers-Ramanujan são,∑∞
m=0 q
m2+m 1
(1−q)(1−q2)...(1−qm)∏∞
n=1
1
(1−q5n−2)(1−q5n−3)
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
As identidades
Teorema
∞∑
m=0
qm
2 1
(1− q)...(1− qm) =
∞∏
n=1
1
(1− q5n−1)(1− q5n−4)
∞∑
m=0
qm
2+m 1
(1− q)...(1− qm) =
∞∏
n=1
1
(1− q5n−2)(1− q5n−3)
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Outras identidades ’à Ramanujan’
∞∑
m=−∞
(−1)mqm(3m−1)/2 =
∞∏
n=1
(1− qn)
∞∑
m=0
(−1)mqm(m+1)/2(2m + 1) =
∞∏
n=1
(1− qn)3
∞∑
m=0
p(5n + 4)qm =
∞∏
n=1
5
(1− q5n)5
(1− q)6
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Conjectura de Alder
Tendo sido provado que,
p(n|partes 1− distintas) = p(n|partes ≡ ±1 mod4)
p(n|partes 2− distintas) = p(n|partes ≡ ±1 mod5)
Conjecturou-se,
p(n|partes d − distintas) = p(n|partes ≡ ±1 mod(d + 3))
que é falso para d>2.
Conjectura (Alder)
p(n|partes d − distintas) ≥ p(n|partes ≡ ±1 mod(d + 3))
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Outros problemas
Será que p(n) é primo para infinitos valores de n?
Será que a razão entre valores pares e ímpares de p(n) tende
para 1?
Será que, dados inteiros m e r , existem infinitas soluções da
equação p(n) ≡ r (mod m)?
João Guerreiro Partições de inteiros
Introdução Bijecções Funções geradoras Identidades de Rogers-Ramanujan Bibliografia
Bibliografia
Andrews, G.E., Eriksson,K. (2004). Integer Partitions. Cambridge
University Press
Andrews, G.E. (1971). On a partition problem of H. L. Alder.
Pac.J.Math. Vol. 36, No.2, 1971.
Berndt, B.C. (2006). Number Theory in the Spirit of Ramanujan.
American Mathematical Society
Berndt, B.C., Ono, K. (1999) Ramanujan’s unpublished manuscript
on the partition and tau functions with proofs and commentary
Sém. Lothar. Combin.
João Guerreiro Partições de inteiros
	Introdução
	Bijecções
	Funções geradoras
	Identidades de Rogers-Ramanujan
	Bibliografia