6/25 meeting
===
---
The dollar game
---
[The dollar game](https://thedollargame.io/game/level/100/100/1)

---
### Definition

A *multigraph* $G = (V,H)$ is a pair of a set of *vertices* $V$ ans a multiset of *edges* $E$ comprised of unordered pairs $\{v,u\}$ of vertices.

Here we only consider a graph to be finite, connected, undirected multigraph without loop.

---
Divisors represent distributions of wealth on $G$: if $D=\sum_{v \in V} D(v)v$, then each vertex(person) has $D(v)$ dollars.

---

The colection of divisors of degree $k$ is denote $\text{Div}^k(G)$.

**Note.** For $v \in V$, $deg_G(v)$ denote its number of incident edges. If think of $v$ as a divisor, $deg(v)$.

---

Let $D \in \text{Div}(G)$ and $v,w \in V$.
$$
D \xrightarrow{v} D' \xrightarrow{w} D''' \\
$$$$
\begin{align}
D''' &= D' - \sum_{wu \in V}(w-u) \\
&= D - \sum_{vu \in V}(v-u) - \sum_{wu \in V}(w-u)
\end{align}
$$$$
D \xrightarrow{w} D'' \xrightarrow{v} D''' \\
$$
This show that the order of lending and borrowing moves does not matter.

---
For $v \in V$, consider $D \xrightarrow{V\backslash\{v\}} D'$
$$
\begin{align}
D' &= D - \sum_{u \in V\backslash\{v\}}\sum_{uw \in E}(u-w)\\
&= D - \sum_{uv \in E}(u-v)\\
&= D + \sum_{uv \in E}(v-u)
\end{align}
$$
It show that $D \xrightarrow{-v} D'$.

Borring from $v \in V$ is the same as set-lending by $V\backslash\{v\}$, and a set-lending by $V$ has not net effect.

---

For $D,D' \in \text{Div}(G)$, define $D \geq D'$ if $D(v) \geq D'(v)$ for all $v \in V$,
$D \geq 0$ if $D(v) \geq 0$ for all $v \in V$



---

**Corollary** If $\text{deg}(D) < 0$, then D is unwinnable

---
### Picard and Jacobian group

The sum of $D,F \in \text{Div}(G)$ is defined vertex-wise:
$$
D+F = \sum_{v\in V}(D(v)+F(v))v
$$
If $D' \sim D$ and $F' \sim F$, then $D+F \sim D'+F'$


> *Proof*
> Homomorphic: Trivial
> Injective: Suppose $\phi([A]) = (0,[e])$. Then $\text{deg}(A)=0$ and $[A - \text{deg}(A)q] = [e]$. So, $[A]=[e]$
> Surjective: Given $(n,[x]) \in \mathbb{Z}\times\text{Jac}(G)$. Let $D=x+nq$.
> Then $\phi([D]) = (n,[D - \text{deg}(D)q]) = (n,[x])$



---
Laplacian
---

---
**Note.** $\mathcal{M}(G) = \mathbb{Z}^V$
(we write $\chi_v$ for $\chi_{\{v\}}$)

Given any firing script $\sigma$, the result of applying the correspomding collection of lending moves to a divisor $D$ will be the divisor $D'$ given by:


$D' = D - \text{div}(\sigma)$. We see that $D'$ is linearly equivalent to $D$, denote $D \xrightarrow{\sigma} D'$.

:::spoiler proof
:::

**Definition.**
Divisors of the form $\text{div}(\sigma)$ is called *principal*.
The set of of principlal divisors forms a subgroup $\text{Prin}(G) < \text{Div}^0{G}$

If $D$ is linerly equialence to $D'$, then $D' = D - \text{div}(\sigma)$. Thus, $D -D' \in \text{Prin}(G)$

Hence, we can expressthe Picard and Jacobian groups as quotients:

---
---

Now we show that $\text{div}:\mathcal{M}(G) \rightarrow \text{Div}(G)$ and $L:\mathbb{Z}^V \rightarrow \mathbb{Z}^V$ are essentially the same.
Note that the mapping $v \mapsto \chi_v$ determines an isomorphis of $\text{Div}(G)$ with $\mathbb{Z}^V$.
:::spoiler proof
:::

---
To realize $L$ as a single matrix, fix an ordering $v_1,....v_n$ of the vertices of $G$, providing an ordered vasis for the free abelian group $\text{Div}(G)$ and a corresponding isomorphism with $\mathbb{Z}^n$. Writing $\chi_j := \chi_{v_j}$, it follows that $\{\chi_1,...,\chi_n\}$ is the dual basis of the free abelian group $\mathcal{M}(G) = \mathbb{Z}^V$.
$$
\chi_j(v_i) = \begin{cases}
1 \quad i = j\\
0 \quad i \neq j
\end{cases}
$$

$L$ is the $n \times n$ integer matrix with $ij$-entry
$$
L_{ij} = L(\chi_j)(v_i) = \begin{cases}
\text{deg}_G(v_i) & i =j \\
-(\# \text{ of edges between } v_i \text{ and } v_j) & i\neq j
\end{cases}
$$
**Proof**
Suppose $D' \sim D$. Then $D' = D + \sigma$ for some $\sigma \in \text{Prin}(G)$. Thus,
$$
\begin{align}
&(D'(v1),\cdots,D'(v_n)) = (D(v1)+\sigma(v_1),\cdots,D(v_n)+\sigma(v_n)) \\
\\
&(D(v1),\cdots,D(v_n)) - (D'(v1),\cdots,D'(v_n)) = (-\sigma(v_1),\cdots,-\sigma(v_n)) \in \text{im}(L)
\end{align}
$$

Isomorphism $\phi: \text{Pic}(G) \rightarrow \mathbb{Z}^n/\text{im}(L)$
$$
[D] \mapsto (D(v_1),\cdots,D(v_n))+\text{im}(L)
$$

Example
---

---

---


---
Fundamental theorem of finitely generated abelian groups
---

### Primary decomposition

Suppose $G$ is finitely generated abelian groups. Then $G$ is isomorphic to a direct product of cyclic groups in the form
$$
\mathbb{Z}_{p_1^{e_1}} \times \mathbb{Z}_{p_2^{e_2}} \times \cdots \mathbb{Z}_{p_n^{e_n}} \times \mathbb{Z} \times \cdots \times \mathbb{Z}
$$ where $p_i$ are primes(not need distinct). The direct product is unqiue except for possible rearrangement of the factors.

### Invariant factor decomposition
We can also write any finitely generated abelian group G as a direct sum of the form
$$\mathbb {Z} ^{n}\times \mathbb {Z}_{k_{1}} \times \cdots \times \mathbb {Z} _{k_{u}}$$ where $k_1$ divides $k_2$, which divides $k_3$ and so on up to $k_u$.

---
Let $A$ be abelian group. An element $a \in A$ is said to be a **torsion** element if it has finite order. The subset of all torsion elements of $A$ is a subgroup of $A$ is called the **torsion sugroup** of $A$, denote by $A_\text{tor}$ or $A_t$.

A abelian gourps is called a **torsion group** if $A =A_t$, that is all elements of $A$ are of finite order.

A group $G$ is said to be **torsion free** if whenever an element $x$ of $G$ has finite order, then $x# is the identity.

If $A$ is an abelian group and $p$ is a prime number, we denote by $A(p)$ the subgroup of all elements $x \in A$ whose order is a power of $p$.

Proof: method 1

Let $A$ be finitely generated abelian groups.

1. The finitely genrated torsion abelian group is finite.
2. $p$ is a primes such that $A(p) \neq 0$. Then
$$A_t \cong \prod_{p} A_t(p)$$
3. Every finite abelian $p$-group is isomorphic to a product of cyclic $p$-group.
4. $A/A_t$ is torsion-free, so it is free (abelian group).
5. $A \cong A_t \times A/A_t$

Proof: method 2

Let $A$ be abelian group generated by $\{a_1,\cdots,a_m\}$
Definie $\phi: \mathbb{Z}^m \rightarrow \ A$ by
$$
(x_1,\cdots,x_m) \mapsto \sum x_1a_1
$$
By the isomorphism theorems, $A \cong \mathbb{Z}^m/\ker(\phi)$
Suppose $\ker(\phi)$ is generated by
$$
\{(a_{1i},\cdots,a_{mi}) \mid i = 1 \sim n\}
$$
Let
$$
M = \begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & \cdots & \cdots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}\\
\end{pmatrix}_{m\times n}
$$
Thus,$A \cong \mathbb{Z}^m/\ker(\phi) \cong \mathbb{Z}^m/\text{im}(M)$

Consider the inetger row/column operations on an integer matrix:
• Switch two rows/columns.
• Multiply an invertible integer (which means ±1) to one row/column.
• Add an integer multiple of a row/column to another row/column.

Every operations is invitible.
Every row opertaions can be written as an invertible matrix $P_{n\times n}$, every column opertaions can be written as an invertible matrix $Q_{m \times m}$.

If a squence of inetger row/column operations transforming $M$ into $N$.
,then $PMQ = N$ where $P_{m\times m }$ and $Q_{n \times n}$ are invertible matrice.

**Theorem** $\mathbb{Z}^m/\text{im}(M) \cong \mathbb{Z}^m/\text{im}(N)$
::: spoiler proof
:::

e.g.

For any $M \in M_{m\times n}(\mathbb{Z})$, one cay apply a sequence of row and column operations to obtain a unique Smith normal form.
::: spoiler proof

:::

**Lemma** : $\mathbb{Z}^m/\text{im}(N) \cong \mathbb{Z}_{s_1} \times \cdots \mathbb{Z}_{s_k} \times \mathbb{Z}^{m-k}$, where $N$ is Smith normal form and $s_1,\cdots,s_k$ is invariant factors of $N$
*proof*
Define $f: \mathbb{Z}^m \rightarrow \mathbb{Z}_{s_1} \times \cdots \mathbb{Z}_{s_k} \times \mathbb{Z}^{m-k}$ by
$$
(a_1,a_2,\cdots,a_k,\cdots,a_m) \mapsto (a_1\mod s_1,\cdots,a_k\mod s_k,a_{k+1}\cdots,a_m)
$$
Then $\ker(f) = \text{im}(N)$
Hence, $\mathbb{Z}^m/\text{im}(N) \cong \mathbb{Z}_{s_1} \times \cdots \mathbb{Z}_{s_k} \times \mathbb{Z}^{m-k}$