4
$\begingroup$

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 ?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user3649
    Feb 3, 2010 at 8:45
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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) $\endgroup$
    – pinaki
    Feb 10, 2010 at 7:44
  • $\begingroup$ 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! $\endgroup$
    – pinaki
    Feb 10, 2010 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.