# 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.

-

## 1 Answer

If I understand what you are looking for, you basically wanted graded lexicographic order or graded reverse lexicographic order. (Any graded total order will work, but these two are probably the easiest to implement.)

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
Yes, I think that's pretty much what I need. I want to use it as a basis for doing polynomial approximation, so when I implement it I need some simple rules how to generate these monomials in order. E.g. how to calculate the function I(1) in code. – Grzenio Jan 11 '12 at 9:48