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.