Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.