REU 2005 · Discrete Mathematics · Lecture 9

Instructor: László Babai Scribes: T. Schedler, S. Chakraborty

July 8, 2005. Last updated July 11, 2005

1 Lecture 9

1.1 Monoids

Definition 1.1. Let M be a monoid, G a group and f : M → G an onto homomorphism we say that the pair (f, G) is a universal group of M and G is a universal group quotient of M if for any group H and any homomorphism h : M → H, there exists a unique g : G → H such that h = gf. That is, the following diagram commutes,

\xymatrix{M \ar@{->>}[rr]^{f} \ar[dr]_{h} & & G \ar@{-->}[dl]_{g} \\ & H} .

Theorem 1.2. Every monoid has a universal group quotient.

Proof. We can define it by generators and relations: G = ⟨M | multiplication table of M ⟩_{group}. So the whole set M is the set of generators.

For example, with the yo-yo M = {1, z, z^{2}, z^{3}, z^{4}, z^{5}, z^{6}, z^{7} = z^{4}}, we get that M = ⟨z | z^{4} = z^{7}⟩. Defining the universal group quotient as in the proof of the theorem, we get G = ⟨z | z^{4} = z^{7}⟩_{group} = ⟨z | 1 = z^{3}⟩ = C_{3}, the cyclic group of order 3.

Exercise 1.3. Finish the proof of the theorem: show that the G thus defined is the universal group quotient.

Observation 1.4. Additionally, every finite monoid has a unique minimal ideal.

Recall that I ◁ M is an ideal iff MIM = I. “Minimal” means nonempty, but does not properly contain any nonempty ideal.

For the proof, recall the following

Claim 1.5. If I, J ◁ M for I, J ≠ 0, then I ∩ J ◁ M is also nonempty.

Proof. IJ ⊆ I ∩ J is a nonempty ideal.

Definition 1.6. This minimal nonempty ideal is called the core:

core(M) := ⋂_{I◁M,I≠∅} I

Theorem 1.7. If M is a finite commutative monoid then core(M) is its universal group.

Note that the finiteness of M is needed: for example ℕ+k◁ℕ are ideals but ∩_{k∈ℕ}(ℕ+k) = ∅.

Proof. Now, let’s consider: why is core(M) a group? That is, for I := core(M), why is ax = b solvable in I? Well, I ◁ M ⇒ aI ◁ M because I = IM and aI = (aI)M, which shows that aI is a right ideal, which is the same as a two-sided ideal by commutativity. Now aI = I by minimality, since aI ⊂ I (I is itself an ideal). So we can solve ax = b for any a, b ∈ I.

Next, we need a map f : M ↠ I for I = core(M), where M is a finite commutative monoid. Take the identity u ∈ I of the core I (which is a group). Then we define

f :M ↠ I
f :x ↦ x · u

so that

xy ↦ (xu)(yu) = (xy)(uu) = xy · u,

as desired (this is indeed a homomorphism).

Claim 1.8. This map is onto.

Proof. For y ∈ I, y ↦ y · u = y and u is the identity of I. because y ∈ I.

Next, we need to check universality:

\xymatrix{M \ar@{->>}[rr]^{f} \ar[dr]_{h} &  & G \ar@{-->}[dl]_{∃!g} \\  & H}

Well, for y ∈ I we need to define g(y) so that (∀x ∈ M)(h(x) = g(f(x))). To do this, let’s just set g(y) = h(y). Then we need h(x) = g(f(x)) = g(x · u) = h(x · u) = h(x)h(u). This follows from the

Claim 1.9. h(u) = id_{H}.

Proof. u^{2} = u, so h(u^{2}) = h(u)^{2} = h(u). Thus h(u) is an idempotent, and since it lives in a group, h(u) is the identity.

So we have proved the theorem.

1.2 Sandpile Group

Recall that t_{v} for any vertex v in the configuration with one chip on t_{v} and none anywhere else.

Theorem 1.10. M is the monoid generated by {t_{i} : i ∈ V_{0}} subject to the relations

deg^{+}(v) · t_{v} = ∑_{j∈V_{0}} a_{ij}t_{j},  (1.1)

where a_{ij} is the multiplicity of the i → j arcs.

Proof. Let M̃ be the monoid defined by (1.1). M satisfies (1.1). So M̃ → M. On the other hand, using the relations (1.1) we can simulate chip-firing and so all elements of M̃ can be written as

∑_{i∈V_{0}} n_{i}t_{i}, 0 ≤ n_{i} ≤ deg^{+}(i).

Consequently |M̃| ≤ |M| and so M̃ = M.

Exercise 1.11. The sandpile group is defined as an abelian group by the same relations as the sandpile monoid. HINT: Use the fact that the sandpile grop is the universal group quotient of the sandpile monoid.

Recall that the Laplacian is the matrix

(\begin{matrix}deg^{+}(1) & & & & 0 \\ & . & . & . \\ 0 & & & & deg^{+}(n) \end{matrix}) − ( a_{ij} )

Note that the laplacian does not change if we add/remove loops.

The reduced Laplacian takes the Laplacian and deletes the row and column corresponding to the sink.

Then the relations (1.1), viewed as relations in an abelian group, become equivalent to

(deg^{+}(i) − a_{ii})t_{i} − ∑_{j,j≠i} a_{ij}t_{j} = 0;  (1.2)

corresponding to the rows of the (reduced) Laplacian.

Corollary 1.12. The sandpile group does not change if we add/delete loops.

Recall that a finitely generated abelian group is something of the form G = ⟨Σ_{i=1}^{k}c_{i}g_{i}|c_{i} ∈ ℕ⟩. A free abelian group on k generators is of the form ⟨t_{1}, …, t_{k} |⟩ ≅ ℤ^{k}.

Define a homomorphism f : ℤ^{k} → G by

Σc_{i}t_{i} ↦ Σc_{i}g_{i}.

Exercise 1.13. Proove that this is a well-defined map and is in fact a surjective homomorphism.

Let K = Ker(f) = f^{−1}(0). We describe this by the sequence

\xymatrix{K \ar[r] & ℤ^{k} \ar@{->>}[r]^{f} & G} .

Exercise 1.14. G ≅ ℤ^{k}/K (the set of cosets with natural addition).

Let K be generated by k_{i} = (α_{i1}, ⋯, α_{ik}) ∈ ℤ^{k}, i = 1, ⋯, m. We permit m to be infinite, although this turns out to be unnecessay. Now consider the m × k matrix A =

(\begin{matrix}α_{11} & α_{12} & … & α_{1k} \\ α_{21} & α_{22} & … & α_{2k} \\ ⋮ & & ... \\ α_{m1} & α_{m2} & … & α_{mk} \end{matrix})

Then G = ⟨t_{1}, …, t_{k} | A⟩, where K = all integer combinations of the rows of A = the subgroup of ℤ^{k} generated by the rows of A.

Note that

Exercise 1.15. Elementary row operations on A don’t change the group K.

Exercise 1.16. If we perform an elementary column operation, then this does not change G; only the generators change. For example, b_{j} ↦ b_{j} + λb_{i}, replacing the generator t_{i} by t_{i} − λt_{j}.

Now, suppose A is in Smith Normal Form. (We note that this works even if A has infinitely many rows). Then we get

(\begin{matrix}1 & & & & & & & & 0 & 0 \\ & 1 & & & & & & & 0 & 0 \\ & & 2 & & & & & & 0 & 0 \\ & & & 6 & & & & & 0 & 0 \\ & & & & 6 & & & & 0 & 0 \\ & & & & & 18 & & & 0 & 0 \\ & & & & & & 0 & & 0 & 0 \\ & & & & & & & 0 & 0 & 0 \end{matrix}) ,

so that t_{1} = 0 = t_{2}, and 2t_{3} = 0 = 6t_{4} = 6t_{5} = 18t_{6}, with no equations involving t_{7}, t_{8}, t_{9}, or t_{10}, so we get the group C_{2} × C_{6} × C_{6} × C_{18} × ℤ^{4}. In this case, it is really easy to read off the structure of the group! And by the preceding, we can reduce the matrix A to this by row and column operations and thus read off the structure of the group G.

Thus we have proved the FUNDAMENTAL THEOREM OF FINITELY GEN-ERATED ABELIAN GROUPS

Recall that the rank of an abelian group is the minimum number of generators. We have the Exercise 1.17. If the invariants of a finitely generated abelian group are n_{1} | n_{2} | … | n_{r} (i.e. the numbers along the diagonal of the Smith Normal Form for A as considered above) for n_{1} ≥ 2, then the rank = r.

For example, ⟨ℤ, +⟩ ≥ ⟨5, 8⟩ = ℤ, and in general ⟨a, b⟩ = ⟨gcd(a, b)⟩, so all subgroups of ℤ have rank = 1.

Exercise 1.18. (Recall direct products from June 27) C_{35} ≅ C_{5}×C_{7} = ⟨a, b | 5a = 0, 7b = 0⟩.

Dhar wrote a significant article about the sandpile group for the n × n-grid, where you add one sink and attach one edge from each points on the perimeter of the grid to the sink, except for the corners which are attached by two edges to the sink (i.e. so that the valence of every vertex remains 4).

For this sandpile, we have V_{0} = {(i, j) | 1 ≤ i, j ≤ n} and

M = ⟨t_{v} : v ∈ V_{0}, t_{ij} = t_{i−1,j} + t_{i+1,j} + t_{i,j−1} + t_{i,j+1}⟩

Theorem 1.19. (Dhar) The rank of this sandpile group is n.

Exercise 1.20. Prove that rank(G) ≤ n by proving that t_{i,1}, i = 1, ⋯, n generate G.

Exercise 1.21. Prove that the mod-2 rank of G for the n × n grid is ≥ n. (HINT: The mod-2 rank of G is the rank of G/2G. If G = ⟨t_{1}, ⋯, t_{n}|A⟩ then G/2G is the quotient of ℤ_{2}^{n} by the row-space of A over 𝔽_{2}. So the mod-2 rank of G is n − rk_{2}(A).)

Exercise 1.22. If A is an integer matrix then rk_{p}(A) ≤ rk(A). Here rk_{p}(A) is the rank of A mod p (over 𝔽_{p}).