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.

Let $R$ be a polynomial ring with $n_k$ variables of degree $k$, for $1\leq k\leq m$. Is there a writeable formula to express the dimension of the vector space $R_l$ of degree $l$ homogeneous polynomials?

If it is unlikely to have such an explicit formula, I'd be happy to know.

share|improve this question
    
This question was asked and deleted yesterday by me [I thought it was bad written] –  user17786 Dec 27 '11 at 10:04
    
What is "degree"? Is it the total degree of the polynomial? Or the degree of each variable? –  Srivatsan Dec 27 '11 at 10:05
    
At the end of the question means "total degree of the polynomial". –  user17786 Dec 27 '11 at 10:09
1  
If all $n_k\in\{0,1\}$ then knowing whether or not the dimension sought is zero is a form of the subset sum problem, which is known to be NP-complete. This means you have little hope of a reasonable explicit formula for the dimension. You can find a generating series expression easily though. –  Marc van Leeuwen Dec 29 '11 at 15:18

1 Answer 1

up vote 3 down vote accepted

Let's be careful because we have two notions of degree here, and they aren't the same. It looks like what you want to do is the following:

Let $k[x_1, ..., x_n]$ be a polynomial ring and give it a grading by declaring the gradings that each of the variables live in, which determines the grading of monomials. Then declare the $l$th graded piece to be the span of the monomials of grading $l$. We'll refer to the place where a homogeneous thing lives as its "grading" for the rest of the time, to avoid confusion. (This is somewhat uncommon usage, but we'll be talking about "dimension" so we can't use that, and "degree" might be confusing when talking about polynomials.)

Anyway, this type of ring comes up a lot in topology, and there's definitely a way to go about computing the dimension of each graded piece. The important notion is that of a "Poincare series", so I'll introduce that.

Let $R = \oplus_{n\ge 0} R_n$ be a graded vector space of finite type over a field. Then its Poincare series is just the power series given by $P_R(t) = \sum (\text{dim }R_n) t^n$. Notice that if $R_n$ is eventually zero, then this sum is finite and evaluating at $(-1)$ gives the Euler characteristic (if you're familiar with that). Anyway, this seems to be a perfectly innocent gadget, but we can exploit some formal properties of these guys to actually compute these things. Here's an exercise:

  • Show that if $R = S \otimes_k T$, where everything is graded so that $R_n = \oplus_{i+j = n} S_i \otimes T_j$, then $P_R = P_S \cdot P_T$. (Hint: This is easy.)

Here's another exercise:

  • Compute the Poincare polynomial of $k[x]$ where the grading of $x$ is $k$. I won't even give you a hint for this one and I certainly won't tell you that the answer is $1/1-x^k$.

Here's another exercise:

  • Show that $k[x_1, ..., x_n] = k[x_1]\otimes \cdots \otimes k[x_n]$, where the gradings are whatever you want.

Now put the last three exercises together and you have a generating function for your answer. From this you can compute the answer $a_l$ for as many $l$ as you like by expanding the power series, but if you want an explicit, useful closed form solution you'll probably need to do some partial fractions expanding and the feasibility will depend on how big your polynomial ring is.

share|improve this answer
    
thanks! It seems pretty clear that a recursive calculation is unavoidable. Do you have another hint for the noncommutative case (when the variables don't commute)? –  user17786 Dec 28 '11 at 14:14
    
In Free associative algebras p.5, a survey of Cohn, is the noncommutative version: If $R, S$ are a pair of free associative algebras over a commutative ring $k$, and $P_R(t), P_S(t)$ are the corresponding Poincare series (there called gocha), we have that $$P_{R*S}(t)^{-1} = P_R(t)^{-1} + P_S(t)^{-1} - 1$$. –  user17786 Dec 28 '11 at 17:10

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.