# How to define a bijection between natural numbers and the set of all polynomials with natural coefficients and finite variables?

Is there an explicit algorithm which establish a bijection between polynomials with finite variables and natural coefficients and natural numbers. Does anyone have one of these?Thanks.

-
What do you mean by finite variables? Do you mean finitely many, like, $x_1 \dots x_n$? – Ben Millwood Sep 12 '12 at 10:08
Yes, thats what I mean exactly. – Hooman Sep 12 '12 at 10:11
Maybe powers of primes? (This won't actually work.) – wj32 Sep 12 '12 at 10:28
You ask for a bijection, which is possible but quite hard (especially if you ask an "explicit formula"). Answers so far involve algorithms (after all nobody even has an explicit formula for the $n$-th prime number) that produce an injection of polynomials into the natural numbers. If that suffices for you, you might want to edit your question so as to be less demanding. – Marc van Leeuwen Sep 12 '12 at 11:48

Here is an algorithm that produces for each such polynomial $q(X_1,\ldots, X_r)$ a natural number in an injective and reversible way:

Let $p_1$, $p_2$, $\ldots$ be the primes in ascending order, and let ${\mathbb N}^*:=\bigcup_{n=0}^\infty {\mathbb N}^n$ be the set of words over the alphabet ${\mathbb N}$. An element of ${\mathbb N}^*$ is a finite tuple of natural numbers. The function $$\psi: \ {\mathbb N}^*\to {\mathbb N}\ ,\qquad (x_1,x_2,\ldots, x_n)\ \mapsto \ p_1^{x_1}\ p_2^{x_2}\cdot\ldots\cdot p_n^{x_n}$$ is injective, by the fundamental theorem of arithmetic.

A polynomial $q:=q(X_1,\ldots, X_r)$ is a finite sum of monomials of the form $$a\ X_1^{x_1}\ X_2^{x_2}\ \cdots\ X_r^{x_r}\ ,$$ where $a$ and the $x_i$ are natural numbers. It follows that such a monomial can be encoded into the number $y:=\psi(a,x_1,x_2,\ldots, x_r)$. Do this for every monomial occurring in $q$, and you get a list of natural numbers, which you better arrange in decreasing order. Let $(y_1,y_2,\ldots, y_N)$ be the list so obtained. Then $$\Psi(q):=\psi(y_1,\ldots, y_N)$$ is the final code-number assigned to the polynomial $q$.

As an exercice we compute the code-number of the polynomial $q(X,Y):=3 XY +2 Y^3$. One has $$3XY=3X^1Y^1\ ,\quad 2 Y^3=2 X^0Y^3\ ;$$ therefore these two monomials determine $$y=\psi(3,1,1)=2^3\cdot3^1\cdot 5^1=120, \quad y'=\psi(2,0,3)=2^2\cdot 3^0\cdot 5^3=500\ .$$ As $500>120$ we obtain \eqalign{\Psi(q)=&\psi(500,120)=2^{500}\cdot 3^{120}=\cr &588231663803252819851242468885657\cr &737281191157147698980407385320166\cr &4929501083470168424157628631200921241\cr &1106855928867093446243479502053445791\cr &03336519115831609224583871650969534711\cr &779898967116298434135013195776\ .\cr}

-

For this question, I'm going to gloss over the question of whether or not $0\in\mathbb N$. There's a clear bijection between the two options in any case, so I'll only refer to positive integers and non-negative integers.

To understand how to do what you ask, it's probably easiest to understand how to encode finite sequences of non-negative integers as a positive integer, and then how to encode your polynomials as those.

The usual way of doing the former is in prime factorisations. Since prime factorisations are unique, if I have $a_1\dots a_n$ non-negative integers and $p_1 \dots p_n$ prime numbers, I can recover the $a_k$ from the prime factorisation of the positive integer $p_1^{a_1}p_2^{a_2}\dots p_n^{a_n}$.

With regards to the latter, you just need to pick an ordering of your terms and read off the coefficients. I might as well pretend you have infinitely many variables, and just all but finitely many have zero coefficients, but now there's some subtlety in how I order them so that I do eventually get to every one. I think what I'll do is call the variables $x_1, x_2 \dots$ and then define the combined degree of a term to be its degree plus the sum of the subscripts used in that term. That way, every term has finite combined degree, but crucially there are only finitely many terms of each combined degree, so if I just list the terms by increasing combined degree, any term will eventually be listed. Pedantically, I do also need to choose an ordering within each collection of terms of given combined degree, but that's not actually difficult - lexicographic order is as good as any. The listing would start $1, x_1, x_1^2, x_2, x_1^3, x_2^2, x_3, x_1^4, x_1x_2, x_2^3, x_3^2, x_4, \dots$

Under this correspondence, I encode $4 + 2x_3^2 + x_1x_2$ as the sequence $4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2$ and hence as the integer $p_1^4p_9p_{11}^2=2^4\times23\times31^2=353648$.

-