Fueter–Pólya theorem

The Fueter–Pólya theorem, first proved by Rudolf Fueter and George Pólya, states that the only quadratic polynomial pairing functions are the Cantor polynomials.

Introduction

In 1878, Georg Cantor showed that the so-called Cantor polynomial

$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}}$

is a bijective mapping from $\mathbb {N} ^{2}$ to $\mathbb {N}$. The polynomial given by swapping the variables is also a pairing function.

Fueter was investigating whether there are other quadratic polynomials with this property, and concluded that this is not the case assuming $P(0,0)=0$. He then wrote to Pólya, who showed the theorem does not require this condition.

Statement

If $P$ is a real quadratic polynomial in two variables whose restriction to $\mathbb {N} ^{2}$ is a bijection from $\mathbb {N} ^{2}$ to $\mathbb {N}$ then it is

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

or

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

Proof

The original proof is surprisingly difficult, using the Lindemann–Weierstrass theorem to prove the transcendence of $e^{a}$ for a nonzero algebraic number $a$. In 2002, M. A. Vsemirnov published an elementary proof of this result.

Fueter–Pólya conjecture

The theorem states that the Cantor polynomial is the only quadratic pairing polynomial of $\mathbb {N} ^{2}$ and $\mathbb {N}$. The conjecture is that these are the only such pairing polynomials, of any degree.

Higher dimensions

A generalization of the Cantor polynomial in higher dimensions is as follows:

$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}}$

The sum of these binomial coefficients yields a polynomial of degree $n$ in $n$ variables. This is just one of at least $(n-1)!$ inequivalent packing polynomials for $n$ dimensions.

Bibliography

• Cantor, Georg (1878). "Ein Beitrag zur Mannigfaltigkeitslehre". Journal für die reine und angewandte Mathematik (in German). 84: 242–258.
• Chowla, P. (1961). "On some polynomials which represent every natural number exactly once". Det Kongelige Norske Videnskabers Selskab Forhandlinger (Trondheim). 34: 8–9.
• Fueter, Rudolf; Pólya, Georg (1923). "Rationale Abzählung der Gitterpunkte" (PDF). Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich (in German). 68: 380–386. Retrieved 14 August 2026.
• Sánchez Flores, Adolfo (1995). "A family of (n−1)! Diagonal polynomial orders of Nⁿ". Order. 12 (2): 173–187. doi:10.1007/BF01108626.
• Smoryński, Craig (1991). Logical Number Theory I: An Introduction. Springer-Verlag. doi:10.1007/978-3-642-75462-3. ISBN 3-540-52236-0.
• Vsemirnov, M. A. (2002) [Russian original: Algebra i Analiz 13 (2001), no. 5, 1–15]. "Two elementary proofs of the Fueter–Pólya theorem on pairing polynomials". St. Petersburg Mathematical Journal. 13 (5): 705–715. Correction: ibid. 14 (2003), no. 5, p. 887.{{cite journal}}: CS1 maint: postscript (link)

External links

• Nathanson, Melvyn B. (2015). "Cantor polynomials and the Fueter-Polya theorem". arXiv:1512.08261 [math.NT].