# A multi-dimensional Frobenius problem

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!

-

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

-
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