# Indexing simple multidimensional polynomials

Assume we have a multidimensional polynomials indexed by the powers of arguments: $$P_{(i_1, i_2, \dots, i_n)}(x_1, \dots, x_n) = x_1^{i_1}x_2^{i_2}\dots x_n^{i_n}$$ I would like to find a way to index these polynomials using a single integer in a way that there are no repetitions and that we start from polynomials with smaller degree. So I am after a function $I:\mathbb{N} \rightarrow \mathbb{N}^N$ such that:

• $P_{I(k_1)} \neq P_{I(k_2)}$ for $k_1 \neq k_2$
• $\sum I(k_1) \leq \sum I(k_2)$ for $k_1 \leq k_2$
• Every simple polynomial is indexed

The definition of $I$ can be recursive if its easier.

-

For example, if $k = 3$, you could take $1 < x_1 < x_2 < x_3 < x_1^2 < x_1 x_2 < x_1 x_3 < x_2^2 < x_2 x_3 < x_3^2 < x_1^3 < \dots$. So you would have $I(1) = (0,0,0), I(2) = (1,0,0), I(5) = (2,0,0), I(7) = (1,0,1), I(10) = (0,0,1)$, etc.
Usually in applications, the total order is more useful than the function $I$. That is, it's easier to compare which of two monomials is bigger directly rather than trying to determine and then compare the corresponding natural numbers in the preimage of $I$.
Isn't $I(10)=(0,0,2)?$ Just a typo –  Ross Millikan Jan 10 '12 at 18:37