Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 6 down vote accepted
+300

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$.

Edit:

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|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
1  
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

 
discard

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.