## § Discrete Riemann Roch

#### § Divisors

Function $V \rightarrow \mathbb Z$. We think of this as formal linear combination of vertices.

#### § Degree of a divisor

$deg(D) \equiv \sum_{v \in V} D(v)$.

#### § Borrowing and lending at a vertex $v_\star$

• Lending: $v$ gives 1 unit of money to all its neighbours
$f' = f + \sum_{vw \in E} -v + w$
• Borrowing: $v$ takes 1 unit of money from all its neighbours
$f' = f + \sum_{vw \in E} + v - w$

#### § Borrowing and lending on a set $S$:

• Lending on a set $S$: every vertex $v \in S$ gives 1 unit of money to all its neighbours
$f' = f + \sum_{v \in S}\sum_{vw \in E} -v + w$
• Borrowing defined similarly.
• See that borrowing at a vertex $v$ is the same as lending from $V / v$. The reason being, the lending between vertices of $V/v$ will cancel, and only lends into $v$ will be counted. This is the same as $v$ borrowing.

#### § Linear equvivalence

Two divisors $D_1, D_2$ are linearly equivalent iff there is a sequence of borrowing or lending moves that leads from $D_1$ to $D_2$. This is an equivalence relation on the space of divisors. Equivalence class of $D_1$ is represented by $[D_1]$.

#### § Partial ordering of divisors

We say that $D_1 < D_2$ if for all $v$, $D_1(v) < D_2(v)$.

#### § Effective divisors

A divisor such that $\forall v, D(v) \geq 0$ is called as an effective divisor. Sometimes written as $D \geq 0$. Our goal is given a divisor $D$, to check if it is linearly equivalent to a divisor $D'$ such that $D \geq 0$. If we can do so, then no one is in debt, and we have won the game.

We add divisors pointwise: $(f + g)(v) \equiv f(v) + g(v)$. This respects linear equivalence. Hence, $[D_1] + [D_2] \equiv [D_1 + D_2]$. This makes divisors, and their equivalence classes an abelian group

#### § The Picard Class Group (group of divisor classes)

The group of equivalence classes of divisors under pointwise addition is the picard group.

#### § Jacobian Class group (divisor classes of degree 0).

• Subgroup of picard group of degree 0.
• That is, all equivalence class elements of degree 0.
• This is well defined because all linearly equivalent divisors (divisors that can be gotten by lending/borrowing) all have the same degree (total money). This is because lending/borrowing does not change the total amount of money in the market, only redistributes it.

#### § Picard group decomposition in terms of Jacobian group

For each $q \in V$, there is an isomorphism of groups $\phi_q: Pic(G) \rightarrow \mathbb Z \times Jac(G)$, where we send a divisor class $[D]$ to $\phi_q([D]) \equiv (deg(D), [D - deg(D)q]$.
• Clearly, the new divisor $[D - deg(D)q]$ has total degree $0$, since $deg(D)$has been subtracted off at $q$.
• We can recover the original divisor since we know $deg(D)$.

#### § Complete linear system $[D]_{\geq 0}|$

The complete linear system of $D$ is the set of all winning configurations from $D$. That is:
$[D]_{\geq 0} \equiv \{ E \in [D] : E \geq 0 \}$
We win the game if $[D]_{\geq 0}$ is nonempty.

#### § The discrete laplacian

The laplacian is the map $L: (V \rightarrow \mathbb Z) \rightarrow (V \rightarrow \mathbb Z)$ defined by:
$L(f)(v) \equiv \sum_{vw \in E} (f(v) - f(w))$
That is, $L(f)(v)$ is the total deviation of $v$ from all of its neighbours $w$.

#### § Firing script

A firing script is a function $s: V \rightarrow \mathbb Z$ ( $s$ for script) that tells us how many times $v$ lends money to its neighbours).
• The collection of all firing scripts form an abelian group, and is denoted by $M(G)$. [TODO: why $M$? ]
• Set lending by a subset $W \subset V$ is denoted by $\chi_W$, where $\chi_W(v) \equiv 1$ if $v \in W$and $\chi_W(v) \equiv 0$ otherwise. Written in iverson notation, we have $\chi_W(v) \equiv [v \in_? W]$.
• The effect of running a firing script $s$ on a divisor $D$ to get a divisor $D'$ is:
\begin{aligned} D' \equiv D + \sum_{v \in V} s(v) (-v+ w) \\ \end{aligned}
if $s: V \rightarrow \mathbb Z$ is a firing script, then the divisor of the firing script $s$ is:
$div(s) \equiv \sum_{v \in V} s(v) (-v+ w)$
• The effect of running a firing script is to replace a divisor $D$ by a new divisor $D' = D + div(s)$. We denote this by $D \xrightarrow{s} D'$ and call this as script-firing

#### § div is a group homomorphism

We see that div is a function from $M(G) = V \rightarrow \Z$ to $Div(G) = V \rightarrow \Z$ under the map:
$div(s) \equiv \sum_{v \in V} s(v) (-v+ w)$
We show that $div(s_1 - s_2) = div(s_1) - div(s_2)$ thereby checking the homomorphism property.
\begin{aligned} &div(s_1 - s_2) = \sum_{v \in V} (s_1 - s_2)(v) (-v+ w) \\ &= \sum_{v \in V} (s_1(v) - s_2(v)) (-v+ w) \\ &= \sum_{v \in V} s_1(v) (-v+ w) - \sum_{v \in V} s_2(v) (-v+ w) \\ &= div(s_1) - div(s_2) \end{aligned}
and is hence a group homomorphism.

#### § div produces divisors of degree 0: deg(div(s)) = 0.

See that $div$ is balanced, in that for every $-v$ we have a $+w$. This makes the total degree zero.

#### § Principal divisors: $Prin(G) \equiv div(M(G))$.

• Divisors of the form div(s) are called as Principal divisors . They are a subgroup of the degree 0 divisors.
• Moreover, if $D'$ is obtainable from $D$ by a series of lending and borrowing moves, then $D' - D \in Prin(G)$.
• This means that linear equivalence is a coset of the principal divisors: $[D] = D + Prin(G)$.

#### § Picard, Jacobian Class group as quotients

• $Pic(G) = Div(G)/Prin(G)$.
• $Jac(G) = Div^0(G)/Prin(G)$.
• $Pic(G), Jac(G)$ are class groups because we get equivalence classes of divisors, equivalent upto principal divisors.

#### § div is same as laplacian #### § Picard group is cokernel of L

Recall that Pic(G) = Div(G)/Prin(G), where Prin(G) was the collection of divisors that could be realised from a firing script. That is,
$Prin(G) \equiv \{ div(s) : s \in V \rightarrow \mathbb Z \}$
M(G) -div→ Div(G) -quotient→ Pic(G) → 0
|          |
f          g
|          |
v          v
Z^n  -L→   Z^n   -quotient'→ cok(L) ~= Z^n/Im L → 0

• The quotient map quotient is surjective.
• The map quotient' is also surjective

#### § Dollar game in terms of laplacian

given a divisor $D$, does there exist a vector $x \in \mathbb Z^V$ such that $D + Lx \geq 0$? Clearly, this is some sort of linear inequality. So, we expect polytopes to show up! Since $x$ is an integer point, we want integer points in polytopes.

#### § Kernel of laplacian in connected graph: all 1s vector

• first of all, see that lending by everyone in $V$ has no effect: everyone lends to all their neighbours, and all their neighbours lend to them, having zero net effect.
• Stated in terms of the firing script, this means that $s_1 + s_2 + \dots s_n$is in the kernel of $div$: the firing script creates a zero divisor. If we choose a basis, this is the all 1s vector.
• In terms of the laplacian, this is stating that the all ones vector is in the kernel of the laplacian.

#### § Kernel of laplacian in connected graph: constant functions (TODO)

Suppose we have a script $s: V \rightarrow \mathbb Z$ such that $div(s) = 0$. TODO
This feels sheafy to me, in terms of "locally constant".

#### § Reduced laplacian: Configurations on $G$

We build reduced laplacians to relate the jacobian (degree zero elements of divisor class group) and the laplacian. Fix a vertex $q \in V$. Define $\tilde{V} \equiv V /\{q\}$. A configuration on $G$ with respect to $q$ is an element of the subgroup
$Config(G, q) \equiv \mathbb Z \tilde{V} \subseteq ZV = Div(G)$
so we simply forget the value at $q$. Alternatively, we set the value of $q$ to zero and continue will our divisor definitions. We can perform lending and borrowing on a configuration divisor, by simply not tracking data at $q$.

#### § q-reduced configurations

We wish to solve the game by benelovence: have vertices lend to adjacent vertices. Here are the steps to convert such an intuition to a real algorithm:
1. Start with a divisor $D$ we want to find an effective divisor $E \geq 0$that $D$ is linearly equivalent to (ie, there exists a series of moves to convert $D$ to $E$).
2. Pick some benelovent vertex $q \in V$. Call $q$ the source. Let $V' = V/q$ be the non source vertices.
3. Let $q$ lend so much money to the non-source-vertices, such that the non-source-vertices, sharing amongst themselves, are out of debt.
4. Now only $q$ is in debt from this giving. $q$ makes no lending or borrowing moves. The non-source-vertices must get $q$ out of debt. Find a $S \subseteq V'$ such that if everyone in $S$ lends, then no one in $S$ go into debt. Make the corresponding set-lending move. Repeat until no such $S$ remains. The resulting divisor is said to be $q$-reduced.
In the end, if $q$ is no longer in debt, we win. Otherwise, $D$ is unwinnable.

#### § Superstable configuration

Let $c \in Config(G, q)$. It is called superstable if $c \geq 0$ and has no legal non-empty set firings. That is, for each non-empty $S \subseteq V/q$, we have some $v \in S$ such that firing $v$ would cause $v$ to go into debt; that is, $c(v) < outdeg_S(v)$.

#### § Decomposition of divisor into superstable configuration

Every divisor can be written as $D = c + kq$ where $c \in Config(G, q) \geq 0$. In this form, $D$ is $q$-reduced iff $c$ is superstable! This follows from the definition of $q$-reduced: there is no subset $S$ which can be fired such that $S$ stays out of debt. Now, if $q \geq 0$, then we win, from what we know of $q$-reduced configurations.

#### § Orientations

An orientation of a graph makes each edge directed. We think of edges now as tuples $e \equiv (u, v)$ as an edge from $u$ to $v$. We denote $e^- = u$ and $e^+ = v$ to be the source and sink vertices of the orientation.

#### § Acylic orientations

An orientation is acyclic if there are no cycles. Every acylic orientation must have at least one sink and a source. It must have at least one source . Assume the acyclic orientation does not have any sources.

#### § Acylic orientation has at least one source

Pick any vertex . If it is a source, done. If it is not a source, it has a parent. Go to parent that has NOT BEEN PICKED YET, repeat check. We will eventually:
• Find a source vertex (vertex with no parent)
• All parents of current vertex have been picked (ie, we find a cycle). Can't happen.
Thus all acyclic orientations have at least one source.

#### § Indegree sequence of an acyclic orientation.

If $O$ is an orientation, define
$indeg_O(u) \equiv |\{ e \in O : e^+ = u \}|$
That is, to each $u$, associate the number of edges whose end is at $u$.

#### § WRONG: Acylic orientation determined by indegree sequence?

The book claims that acyclic orientation is determined by the indegree sequence. I don't believe this. Consider the graph $G$:
--a--
|   |
v   v
b   c

• This has indegrees $(a=0, b=1,c=1)$.
Now consider $H$:
a
|
v
b
|
v
c

• This has indegrees $(a=0, b=1, c=1)$ but the graphs are not equal!

#### § Acylic orientation determined by indegree sequence

OK, the above is not what the book claims. The book claims that two orientations $O_G$, $O'_G$ of the same graph are equal if their indegree sequences are equal. This is believeable, because if the orientations point differently, their indegrees will change.
• Proof strategy: induction on number of vertices + forcing sources to be the same + creating new sources by removing current sources.
• Theorem is immediate with only one vertex. Assume holds for $n$. Now we have a graph with $(n+1)$ vertices. Find source in acyclic orientation $O_G$. This has no incoming edges, so has indegree zero. This must be the same in $O'_G$ since $O_G$ and $O'_G$ have the same indegree sequence.
• Now remove the sources that are structurally equal. We get a graph of $H$ of (n-1) vertices, and we get $O_H$ and $O'_H$ by removing the sources from $O_G, O_G'$. Since $O_G = O_G'$ we must have that $O_H = O_H'$ since removing the same source from both graphs modifes the orientations the same way. Recurse into $O_H, O_H'$.

#### § Divisor for an orientation

For an orientation $O$ we define a divisor $D(O)$ as:
$D(O) \equiv \sum_{v \in V}(indeg_O(v) - 1) v$

#### § The rank function

In one sense, the “degree of winnability” of the dollar game is measured by the size of complete linear systems: $D$ is “more winnable” than $D'$ if $[D]_{\geq 0} > [D']_{\geq 0}$. Instead of measuring $[D]_{\geq 0}$, we choose to define another function, the rank, that measures "stability/robustness of winnability"
• Fist, $r(D) \equiv -1$ if $D$ is unwinnable: $r(D) \equiv 0$ iff $[D]_{\geq 0} = \emptyset$
• Next, $r(D) = 1$ if $D$ is barely winnable. That is, $D$ is winnable, but there is some vertex $v$ such that $D - v$ is unwinnable. That is, $r(D)$is barely winnable if the ability to win at $D$ can be destroyed by a single vertex losing a dollar.
• In general, for $k \geq 0$, define that $r$ is at least $k$ winnable if the dollar game is winnable strating from all divisors obtained from $D$ by removing $k$dollars. Formally, this becomes:
$r(D) \geq k \iff |D - E| \neq \emptyset \text{for all E \geq 0 (E effective) of degree k}$
This means that $r(D) = l$ if there is some divisor $E$ of degree $l+1$ such that $D - E$ is not winnable.

#### § Lower bound on rank: $r(D) \geq deg(D) - g$

Won't prove this here, depends on other results (if $deg(D) \geq g$, then $D$ is winnable)

#### § Canonical divisor

For any orientation $O$, define $O_{rev}$ to be the reversed orientation. Now define the canonical divisor $K$ to be $K \equiv D(O) + D(O_{rev})$. See that for every $v \in V$:
\begin{aligned} K(V) = indeg_O(v) + outdeg_O(v) = deg_G(v) \end{aligned}