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
    Commented 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
    Commented 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
    Commented Feb 10, 2010 at 7:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .