Teorema de Fueter–Pólya

O teorema de Fueter–Pólya, provado pela primeira vez por Rudolf Fueter e George Pólya, afirma que as únicas funções de pareamento polinomial quadráticas são os polinômios de Cantor.

Introdução

Em 1873, Georg Cantor mostrou que o chamado polinômio de Cantor

$P(x,y):={\frac {1}{2}}((x+y)^{2}+3x+y)={\frac {x^{2}+2xy+3x+y^{2}+y}{2}}=x+{\frac {(x+y)(x+y+1)}{2}}={\binom {x}{1}}+{\binom {x+y+1}{2}}$

é um mapeamento bijetivo de $\mathbb {N} ^{2}$ para $\mathbb {N}$. O polinômio dado pela troca das variáveis ​​também é uma função de pareamento.

Fueter estava investigando se existem outros polinômios quadráticos com esta propriedade e concluiu que este não é o caso, assumindo $P(0,0)=0$. Ele então escreveu para Pólya, que mostrou que o teorema não requer essa condição.

Declaração

Se $P$ é um polinômio quadrático real em duas variáveis ​​cuja restrição a $\mathbb {N} ^{2}$ é uma bijeção de $\mathbb {N} ^{2}$ para $\mathbb {N}$ então é

$P(x,y):={\frac {1}{2}}((x+y)^{2}+3x+y)$

ou

$P(x,y):={\frac {1}{2}}((y+x)^{2}+3y+x).$

Prova

A prova original é surpreendentemente difícil, usando o teorema de Lindemann-Weierstrass para provar a transcendência de $e^{a}$ para um número algébrico diferente de zero $a$. Em 2002, M. A. Vsemirnov publicou uma prova elementar deste resultado.

Conjectura de Fueter–Pólya

O teorema afirma que o polinômio de Cantor é o único polinômio de pareamento quadrático de $\mathbb {N} ^{2}$ e $\mathbb {N}$. A conjectura é que esses são os únicos polinômios de pareamento desse tipo, de qualquer grau.

Dimensões superiores

Uma generalização do polinômio de Cantor em dimensões superiores é a seguinte:

$P_{n}(x_{1},\ldots ,x_{n})=\sum _{k=1}^{n}{\binom {k-1+\sum _{j=1}^{k}x_{j}}{k}}=x_{1}+{\binom {x_{1}+x_{2}+1}{2}}+\cdots +{\binom {x_{1}+\cdots +x_{n}+n-1}{n}}$

A soma desses coeficientes binomiais produz um polinômio de grau $n$ em $n$ variáveis. Este é apenas um de pelo menos $(n-1)!$ polinômios de empacotamento não equivalentes para $n$ dimensões.