Take the 2-minute tour ×
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.

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|improve this question
add comment

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

share|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
add comment

Your Answer

 
discard

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.