Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Inspired by this question.

Let $A$ be a subset of ${\mathbb Z}^d$ that generates the whole additive group ${\mathbb Z}^d$, and let $S$ be the additive semigroup generated by $A$.

Prove that there is a $d$-dimensional convex cone $C\subset {\mathbb R}^d$ so that all elements of $C \cap {\mathbb Z}^d$ with sufficiently large norm are contained in $S$.

P.S. Feel free to retag!

share|cite|improve this question
up vote 6 down vote accepted

Take $\mathcal{E}=(e_1,\ldots,e_d) \in A^d$ that is a basis of $\mathbb{Q}^d$. We choose the norm $|| \cdot ||$ to be $|| \cdot ||_{\infty,\mathcal{E}}$ (sup-norm of the coefficients in the basis $\mathcal{E}$).

$\mathbb{Z}e_1 + \ldots + \mathbb{Z}e_d$ contains $N \mathbb{Z}^d$ for some positive integer $N$. Let $C_0$ be the cone spanned by the $e_i$'s. Take $C$ to be the cone spanned by $f_1,\ldots,f_n$ where $f_i = e_i + \epsilon \sum_{j \neq i} e_j$, choosing $\epsilon>0$ small enough so that $(f_1,\ldots,f_n)$ is free. There exists $\eta>0$ (depending on $\epsilon$) such that for every $x \in C$, the coefficients of $x$ in the basis $\mathcal{E}$ are all $\geq \eta ||x||$, so $B(x,\eta ||x||) \subset C_0$ (draw a picture!).

Now choose $s_1,\ldots,s_k \in S$ exhausting $\mathbb{Z}^d/N\mathbb{Z}^d$. Let $M=\max_i ||s_i||$. Take $x \in C \cap \mathbb{Z}^d$, with $||x||>M/\eta$. There exists $i$ such that $x-s_i \in N \mathbb{Z}^d$, and $x-s_i \in B(x,M) \subset C_0$, so the coefficients of $x-s_i$ in $\mathcal{E}$ are non-negative integers.

As a consequence, $x=s_i+(x-s_i)$ is in $S$.


Just to add rigor to the statement with the "picture": if $x = \sum_i x_i f_i \in C$, and if $x_{i_0} = \max_i x_i$, then $x = \sum_i y_i e_i$ with $y_{i_0} = \max_i y_i \leq (1+(d-1)\epsilon ) x_{i_0}$ and $y_i \geq \epsilon x_{i_0}$ for each $i$, so that $y_i \geq \epsilon / (1+(d-1)\epsilon) ||x||$.

share|cite|improve this answer
Thanks very much for answering my question. There is one part of your argument that I'm not too clear about. Why can we exhaust ${\mathbb Z}^d/N{\mathbb Z}^d$ by members of $S$? Could you please elaborate on that point? Thanks! – Byron Schmuland Nov 2 '10 at 19:28
Every vector in $\mathbb{Z}^d$ is equal to $s-t$ for some $s,t \in S$, and $s-t=s+(N-1)t \mod N\mathbb{Z}^d$, with $s+(N-1)t \in S$. – Plop Nov 2 '10 at 22:03

Your Answer


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.