# Is this Monoid Finitely Generated?

Let $$G$$ be a finitely generated abelian group, $$H\leq G$$, and $$S = \{g_1, \dots, g_n\}$$ be some finite generating set for $$G$$.

Let $$G’$$ be the set of negative-free linear combinations of elements of $$S$$. i.e. $$G’ = \{a_1g_1 + \dots + a_ng_n | a_1,\dots, a_n \in \mathbb{N}\}$$, and let $$H’= G’ \cap H$$.

Is $$H’$$ finitely generated as a monoid i.e. is there some finite subset of $$H’$$, $$S’$$ such that every element of $$H’$$ is a nonnegative linear combination of $$S’$$?

• Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be closed. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. Nov 23, 2023 at 20:11
• It's a good question. I hope that it doesn't get closed. Have you looked at some examples already? Nov 23, 2023 at 22:07
• First things first: are submonoids of finitely generated commutative monoids also finitely generated? If not, what is an example? Nov 23, 2023 at 22:43
• @MartinBrandenburg: A counterexample is the submonoid of $\mathbb{N}^2$ generated by $(1,n)$ for all $n$. That can’t give a counterexample for this question though since it isn’t closed under subtraction. Nov 23, 2023 at 22:50

$$\textbf{Lemma:}$$ Let $$A$$ be a non-empty subset of $$\mathbb{N}^n$$ equipped with the partial order $$(a_1, \ldots ,a_n)\leq(b_1, \ldots, b_n)$$ iff $$a_i\leq b_i$$ for all $$i=1, \ldots ,n$$. Then $$A$$ has only finitely many minimial elements.
Let us prove this by induction on $$n$$. For $$n=1$$ this is just the well-ordering principle. Assume the lemma holds for $$n\geq 1$$ and let $$A\subseteq \mathbb{N}^{n+1}$$ be non-empty. Clearly $$A$$ has some minimal element, say $$\mathbf{x}=(x_1, \ldots ,x_{n+1})\in A$$. Then any other minimal element of $$A$$ must have at least one coordinate that is less than the corresponding $$\mathbf{x}$$ coordinate. More precisely, any other minimal element of $$A$$ is contained in the union $$\bigcup\limits_{i=1}^{n+1}\bigcup\limits_{j=0}^{x_i-1} \{(a_1, \ldots ,a_{n+1})\in A: a_i=j\}.$$ Moreover, a minimal element of $$A$$ is in particular a minimal element of the corresponding $$\{(a_1, \ldots ,a_{n+1})\in A: a_i=j\}$$ set to which it belongs and by the induction hypothesis there are only finitely many of these. Since the union is finite it follows that $$A$$ has only finitely many minimal elements. $$\square$$
Now we use the lemma to show that $$H'$$ is finitely generated. Consider $$\bar{H}=\{(a_1, \ldots, a_n)\in \mathbb{N}^n\backslash\{\mathbf{0}\} : \sum\limits_{i=1}^n a_ig_i\in H\}.$$ This set has finitely many minimal elements, say $$\mathbf{a_1}, \ldots ,\mathbf{a_m}$$. Let $$h_1, \ldots h_m\in H'$$ be the corresponding group elements, more precisely, $$h_i=\sum\limits_{j=1}^n a_{i, j}g_j$$ where $$\mathbf{a_i}=(a_{i, 1}, \ldots ,a_{i, n})$$.
We claim that the $$h_i$$'s generate $$H'$$ as a monoid so let $$h=\sum\limits_{i=1}^n a_ig_i\in H'\backslash\{e\}$$. If $$\mathbf{a}=(a_1, \ldots ,a_n)$$ is a minimal element of $$\bar{H}$$ then $$h$$ is one of the $$h_i$$'s and we are done. If not, then there is a minimal element, say $$\mathbf{a_{i_1}}$$, with $$\mathbf{a_{i_1}}<\mathbf{a}$$. Since $$H$$ is a subgroup, we have $$\mathbf{a}-\mathbf{a_{i_1}}\in \bar{H}$$. If this element is minimal, say $$\mathbf{a}-\mathbf{a_{i_1}}=\mathbf{a_{i_2}}$$ then $$h=h_{i_1}+h_{i_2}$$ and we are done. If not, we continue as before. Eventually the process must terminate and we obtain that $$h=\sum\limits_{j=1}^k h_{i_j}$$ for some $$i_j$$'s.