THC Science

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[edit]

In 1873, Georg Cantor showed that the so-called Cantor polynomial^[1]

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.^[2]

Statement[edit]

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[edit]

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

Fueter–Pólya conjecture[edit]

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.

Higher dimensions[edit]

A generalization of the Cantor polynomial in higher dimensions is as follows:^[5]

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.^[6]

References[edit]

^ G. Cantor: Ein Beitrag zur Mannigfaltigkeitslehre, J. Reine Angew. Math., Band 84 (1878), Pages 242–258
^ Rudolf Fueter, Georg Pólya: Rationale Abzählung der Gitterpunkte, Vierteljschr. Naturforsch. Ges. Zürich 68 (1923), Pages 380–386
^ Craig Smoryński: Logical Number Theory I, Springer-Verlag 1991, ISBN 3-540-52236-0, Chapters I.4 and I.5: The Fueter–Pólya Theorem I/II
^ M. A. Vsemirnov, Two elementary proofs of the Fueter–Pólya theorem on pairing polynomials. St. Petersburg Math. J. 13 (2002), no. 5, pp. 705–715. Correction: ibid. 14 (2003), no. 5, p. 887.
^ P. Chowla: On some Polynomials which represent every natural number exactly once, Norske Vid. Selsk. Forh. Trondheim (1961), volume 34, pages 8–9
^ Sánchez Flores, Adolfo (1995). "A family of $(n-1)!$ diagonal polynomial orders of $\mathbb {N} ^{n}$ ". Order. 12 (2): 173–187. doi:10.1007/BF01108626.

[1] G. Cantor: Ein Beitrag zur Mannigfaltigkeitslehre, J. Reine Angew. Math., Band 84 (1878), Pages 242–258

[2] Rudolf Fueter, Georg Pólya: Rationale Abzählung der Gitterpunkte, Vierteljschr. Naturforsch. Ges. Zürich 68 (1923), Pages 380–386

[3] Craig Smoryński: Logical Number Theory I, Springer-Verlag 1991, ISBN 3-540-52236-0, Chapters I.4 and I.5: The Fueter–Pólya Theorem I/II

[4] M. A. Vsemirnov, Two elementary proofs of the Fueter–Pólya theorem on pairing polynomials. St. Petersburg Math. J. 13 (2002), no. 5, pp. 705–715. Correction: ibid. 14 (2003), no. 5, p. 887.

[5] P. Chowla: On some Polynomials which represent every natural number exactly once, Norske Vid. Selsk. Forh. Trondheim (1961), volume 34, pages 8–9

[6] Sánchez Flores, Adolfo (1995). "A family of $(n-1)!$ diagonal polynomial orders of $\mathbb {N} ^{n}$ ". Order. 12 (2): 173–187. doi:10.1007/BF01108626.

[1]

[2]

[3]

[4]

[5]

[6]