MathOverflow is a question and answer site for professional mathematicians. 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

An affine monoid is a finitely generated commutative submonoid of $\mathbb Z^k$ for some positive integer k. Let S be an affine monoid and let G(S) be the group generated by S. We say the monoid S is normal if and only if for all $g \in G(S)$ and $n \in \mathbb N \setminus \{0\}$, $ng \in S$ implies $g \in S$.

Let $S$ be the submonoid generated by the finite set $T= \{(p_0,p_1, \cdots ,p_{n-1}) \in (\mathbb Z_{\geq 0})^n: \sum_{i=0}^{n-1}p_i=n \,\, and \,\, \sum_{i=0}^{n-1}i.p_i \cong 0 \pmod n\}$. Now my question is how to prove that $S$ is normal ?

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

I worked on this for a bit with Ricky Liu, who came up with this very quick solution:

Take your set T. Suppose $\sum p_i = kn$, where $k \geq 2$. Create the following set T': let $i$ appear $p_i$ times. This creates a set $T'$ with at least $2n$ elements (by your first constraint and $k \geq 2$), whose sum is divisible by $n$ by your second constraint.

However, by Erdos-Ginsberg-Ziv, there's a subset of $n$ elements which add to $n$, which exactly corresponds to your generator, so we're done.

share|cite|improve this answer
Thanks for your answer. Actually I want to prove EGZ theorem using this result, so I do not want to use EGZ to prove this result. I knew this proof already. – user3649 Feb 3 '10 at 8:45

Sorry, I did not get the above answer. Can somebody please explain me.

Suppose, $q.(p_0,p_1, \cdots ,p_{n-1}) \in S$, where $ q \in \mathbb N \setminus 0$ and $(p_0,p_1, \cdots ,p_{n-1}) \in G(S)$, why is it clear from the above answer that $(p_0,p_1, \cdots ,p_{n-1})$ is already in $S$. Some of the $p_i$'s can be negative as well. It is not at all clear to me. Thanks in advance.

share|cite|improve this answer
First of all: no p_i can be negative: since q{\bar p} is in S (where I write {\bar p} for (p_0, ..., p_{n-1}), it follows that qp_i >= 0 for all i. Since {\bar p} is in G(S), it follows that p_0 + ... + p_{n-1} = kn for some integer k. Moreover, k >= 0 (since each p_i >= 0). I guess the best way to understand the above proof will be by induction on k. If k = 1, then {\bar p} already is in S. Otherwise, as yanzhang suggests, by Erdos-Ginsberg-Ziv, there are 0<=i_1 < ... < i_k <= n-1 and j_1, ..., j_k such that (continued to the next comment) – auniket Feb 10 '10 at 7:44
1 <= j_m <= p_{i_m} for each m, j_1 + ... + j_k = n and i_1j_1 + ... + i_kj_k is divisible by n. Let {\bar q} := (q_0, ..., q_{n-1}) where q_s = j_s if m = i_s for some s, and q_s = 0 otherwise. Then {\bar q} is in T, and by induction {\bar p} - {\bar q} is in S. Done! – auniket Feb 10 '10 at 7:51

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.