O Teorema dos Números Pentagonais

Escolha um número n e a página lista todas as formas de o escrever como soma de números inteiros positivos distintos, em diagramas de pontos, emparelhados pelo movimento de Franklin: um com um número par de parcelas ao lado de um com um número ímpar. No máximo um fica sem par, e apenas quando n é um número pentagonal. Abaixo, o produto (1 − x)(1 − x²)… é desenvolvido fator a fator, e os seus coeficientes contam a mesma história.

Exemplo resolvido — O Teorema dos Números Pentagonais

Número par de parcelas	7
Número ímpar de parcelas	8
Par menos ímpar	−1
p(12), por recorrência de Euler	77
p(100)	190.569.292

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — O Teorema dos Números Pentagonais

Teorema dos números pentagonais de Euler: (1 − x)(1 − x²)(1 − x³)… = 1 − x − x² + x⁵ + x⁷ − x¹² − x¹⁵ + …, uma soma sobre cada número inteiro k, positivo, negativo ou nulo, de (−1)ᵏ x^(k(3k − 1)/2). Os expoentes são os números pentagonais generalizados, e todos os coeficientes são 0, +1 ou −1.

O que significa cada símbolo

p(n): o número de partições de n: formas de o escrever como soma de inteiros positivos, ignorando a ordem
D₊(n), D₋(n): as partições de n em parcelas distintas com um número par, e com um número ímpar, de parcelas
k(3k ∓ 1)/2: os números pentagonais generalizados 1, 2, 5, 7, 12, 15, 22, 26, …

De onde vem a fórmula

Por que cada coeficiente é par menos ímpar. Expandir o produto (1 − x)(1 − x²)(1 − x³)… significa escolher, em cada fator, 1 ou −xᵏ. Optar por −xᵏ num determinado conjunto de fatores resulta em x elevado à soma desses k, com um sinal de menos para cada escolha. Logo, o coeficiente de xⁿ ganha +1 por cada forma de escrever n como soma de inteiros positivos distintos com um número par de parcelas, e −1 por cada forma com um número ímpar. O teorema afirma que essa diferença é zero, exceto nos números pentagonais, onde vale (−1)ᵏ.
Por que motivo o movimento de Franklin as emparelha. Num diagrama com diferentes comprimentos de linha, seja s a parcela menor e g a diagonal: quantas linhas, a contar de cima, diminuem de tamanho em exatamente um ponto de cada vez. Se s ≤ g, retira-se a linha inferior e adiciona-se um ponto ao final de cada uma das s linhas superiores; se s > g, retira-se um ponto do final de cada uma das g linhas superiores e forma-se com eles uma nova linha inferior de g pontos. De qualquer forma as linhas permanecem distintas, o total continua a ser n, e o número de linhas muda em um, logo par e ímpar alternam, e repetir o movimento reverte-o. Apenas é bloqueado quando a linha inferior e a diagonal partilham um ponto e s = g ou s = g + 1. Esses diagramas são k + (k + 1) + … + (2k − 1) e (k + 1) + … + 2k, cujos totais são k(3k − 1)/2 e k(3k + 1)/2.
Do teorema para p(n). Cada partição de n, com repetições permitidas, é contada por Σ p(n) xⁿ = 1/((1 − x)(1 − x²)(1 − x³)…). Multiplique ambos os lados pelo produto, que é a série pentagonal: (1 − x − x² + x⁵ + x⁷ − x¹² − …) × Σ p(n) xⁿ = 1. Para n ≥ 1 o coeficiente de xⁿ à direita é 0, portanto p(n) − p(n − 1) − p(n − 2) + p(n − 5) + p(n − 7) − … = 0. Esta é a recorrência de Euler, e o número dos seus termos cresce apenas como √n.

Duzentos fatores, e apenas 23 dos primeiros 201 coeficientes sobrevivem 🖖

Ao multiplicar (1 − x)(1 − x²) obtém-se 1 − x − x² + x³. Continue fator a fator com o seletor sob o gráfico de barras: os coeficientes crescem, chegando a 31 a meio do processo, e depois cancelam-se. Após 200 fatores, apenas 23 dos primeiros 201 coeficientes são não-nulos, todos eles +1 ou −1, e encontram-se em 0, 1, 2, 5, 7, 12, 15, 22, 26, … Estes são os números pentagonais, k(3k − 1)/2 e k(3k + 1)/2, e Euler descobriu o padrão ao desenvolver o produto.

Um emparelhamento demonstra-o: no 12 sobra exatamente uma partição 🖖

Prima n = 9. As 8 formas de escrever 9 como soma de inteiros positivos distintos dividem-se em 4 com um número par de parcelas e 4 com um ímpar, e o movimento de Franklin emparelha cada uma par com uma ímpar. Prima n = 12: 7 pares contra 8 ímpares, e uma partição não tem par, 5 + 4 + 3, cujo total, 12, é um número pentagonal. Clique nela e a página mostra por que motivo o movimento é bloqueado aí. O coeficiente de x¹² é par menos ímpar, −1, e o emparelhamento constitui toda a demonstração. Franklin, um aluno de Sylvester na Johns Hopkins, publicou-a em 1881.

p(1000) exige 50 consultas 🖖

Inverta o teorema e ele conta partições p(n), somas em qualquer ordem com repetições permitidas. A recorrência de Euler utiliza apenas valores anteriores a distâncias pentagonais: p(12) = p(11) + p(10) − p(7) − p(5) + p(0) = 77. Para p(1000), um número de 32 algarismos, isso significa 50 termos, e a tabela inteira de p(1) a p(1000) exige 33 475 consultas, em oposição às 500 500 adições feitas pelo método comum. Prima p(200) para ver 3 972 999 029 388, a última entrada na tabela de MacMahon para Hardy e Ramanujan. O primeiro termo da sua famosa fórmula encontra-se ainda 1,42% acima em n = 1000.

Problema resolvido na íntegra

A “lei extraordinária” de Euler: somas de divisores com os mesmos sinais 4 passos
Os sinais que constroem p(n) também constroem a soma dos divisores de n. Euler chamou-lhe uma lei das mais extraordinárias. Use-a para encontrar σ(12), a soma dos divisores de 12, com uma alteração à recorrência: onde seria necessário σ(0), use o próprio n.

Abrir este problema na ferramenta
1. A recorrência da página para p(12), o padrão a copiar:
  
  $p (12) = p (11) + p (10) - p (7) - p (5) + p (0) = 56 + 42 - 15 - 7 + 1 = 77$
2. Os mesmos desvios e sinais para σ(12). O último desvio é o próprio 12, por isso σ(0) passa a 12:
  
  $σ (12) = σ (11) + σ (10) - σ (7) - σ (5) + σ (0) \to 12$
3. Com σ(11) = 12, σ(10) = 18, σ(7) = 8 e σ(5) = 6:
  
  $σ (12) = 12 + 18 - 8 - 6 + 12 = 28$
4. Verifique somando os divisores diretamente:
  
  $1 + 2 + 3 + 4 + 6 + 12 = 28$
Resposta

σ(12) = 28. Euler documentou isto em 1747, e é válido para todo o n; a própria aritmética da página verifica-o até n = 500.

$σ (12) = 28; σ (n) = \sum_{k} (- 1)^{k + 1} σ (n - \frac{k ( 3 k \mp 1 )}{2}), σ (0) \to n$

Percurso de aprendizagem

Métodos de demonstração

Referências (3)

Franklin's involution as stated on this page (compare the smallest part with the slope; move one onto the other; blocked only at the pentagonal diagrams), with Franklin's 1881 paper and his place as Sylvester's student at Johns Hopkins: I. Pak, "Partition bijections, a survey", The Ramanujan Journal 12, 5–75 (2006); preprint, §5.2.
Euler's paper on the sum of divisors, where the pentagonal signs that give p(n) give σ(n) too, the worked problem: L. Euler, "Découverte d'une loi tout extraordinaire des nombres par rapport à la somme de leurs diviseurs", Bibliothèque impartiale 3, 10–31 (written 1747, published 1751); Eneström number E175, The Euler Archive.
The partition numbers, Euler's recurrence over the generalised pentagonal numbers, Hardy and Ramanujan's asymptotic formula, and MacMahon's table of p(n) up to 200: OEIS Foundation, "A000041: a(n) = number of partitions of n" and "A001318: Generalized pentagonal numbers", The On-Line Encyclopedia of Integer Sequences.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.