Posted by: atri | April 19, 2009

Missing calculation from Lecture 37

In the lecture on Monday,  April 20 we will skip a calculation. Below is the calculation in its gory details.

The main definition is that of \mathbf{(1,k)}-weighted degree of a monomial. In particular, the (1,k)-weighted degree of the monomial X^iY^j is i+kj. The main question is the following:

Given a degree bound D, how many monomials in two variables are there that have (1,k) weighted degree at most D?

In other words we need to find out how many distinct tuples (i,j) with positive integers i,j\ge 0 exist such that i+kj\le D? Below we calculate a lower bound. For notational convenience, define \ell=\left\lfloor \frac{D}{k}\right\rfloor.

It is easy to check that the number of such tuples is

\displaystyle \sum_{j=0}^{\ell}\sum_{i=0}^{D-kj}1.

Unravelling the second sum, we get

\displaystyle \sum_{j=0}^{\ell} (D+1-kj).

Expanding the sum above, we obtain that the required number is

\displaystyle (D+1)(\ell+1)-k\frac{\ell(\ell+1)}{2}.

Moving the common (\ell+1) term outside, we get

\displaystyle \frac{(\ell+1)}{2}\cdot\left(2D+2-k\ell\right).

Till now we have not any approximation. However, we will do so now. Note that by the definition of \ell, we have k\ell\le D and \ell+1\ge D/k. This implies, that the number of monomials of (1,k)-weighted degree at most D is at least

\displaystyle \frac{D(D+1)}{2k},

which is the bound that we will use in the lecture.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: