the set of homogeneous polynomials of degree $n$ and $I_n=I\cap{\mathbb{K}}_n[{\pmb{x}}]$, and both of them are linear spaces over ${\mathbb{K}}$.

Note that $\dim_{\mathbb{K}}{\mathbb{K}}_n[{\pmb{x}}]=(n)_{d-1}$ is the number of monomials of degree $n$, where $$(n)_{d-1}\triangleq\binom{n+d-1}{d-1}=(n+d-1)(n+d-2)\cdots(n+1)/(d-1)!.$$ And $H_I(n)=0$ means that $I$ contains all monomials of degree $\geq n$.

We invoke the Macaulay’s theorem [@FSM27] to estimate the value of Hilbert’s function $H_I$. To this end, we define a function $\operatorname{Inc}_k:{\mathbb{N}}\rightarrow{\mathbb{N}}$ for every natural number $k\geq 1$ as follows. When $k$ is given, any number $n\in{\mathbb{N}}$ can be uniquely decomposed as $$n=(n_1)_k+(n_2)_{k-1}+\cdots+(n_r)_{k-r+1}\triangleq(n_1,n_2...,n_r)_k,$$ where $0\leq r\leq k$ and $n_1\geq n_2\geq\cdots\geq n_r\geq 0$. In fact, $0=()_k$ with $r=0$; and for $n>0$, $n_1, n_2,\cdots,n_r$ are successively determined by $$\begin{split}
(n_1)_k&\leq n<(n_1+1)_k\\
(n_2)_{k-1}&\leq n-(n_1)_k<(n_2+1)_{k-1}\\
&\cdots
\end{split}$$ until $n=(n_1,n_2...,n_r)_k$ for some $r\geq 1$. Now we define $$\operatorname{Inc}_k((n_1,\cdots,n_r)_k)=(n_1,...,n_r)_{k+1}.$$ For instance, $\operatorname{Inc}_k(0)=0$, and $\operatorname{Inc}_3(11)=\operatorname{Inc}_3((2,0)_3)=(2,0)_4=16$ (note that $11=(2,0)_3$).

\[thm:Macaulay\] For any monomial ideal $I\subseteq{\mathbb{K}}[{\pmb{x}}]$, $H_I(n+1)\leq\operatorname{Inc}_n(H_I(n))$ for all $n\geq1$. Moreover, $H_I(n+1)=\operatorname{Inc}_n(H_I(n))$ if $\operatorname{gdeg}(I)\leq n$ and $I$ is $n$-compressed.

Upper bound of the length of polynomial ascending chains {#sec:bound}
========================================================

In this section, we investigate the length of polynomial ascending chains, which plays a key role in proving the decidability of the termination problem. In addition, this problem is independently of interest in mathematics and 