§ 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

• Borrowing: $v$ takes 1 unit of money from all its neighbours

§ 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

• 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.

§ Addition of divisors

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:

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:

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:

if $s: V \rightarrow \mathbb Z$ is a firing script, then the divisor of the firing script $s$ is:

• 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:

We show that $div(s_1 - s_2) = div(s_1) - div(s_2)$ thereby checking the homomorphism property.

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,

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

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$.

§ 3: Winning

§ 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.

§ 4: Acylic orientations

§ 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

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:

§ 5: Riemann roch

§ 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:

This means that $r(D) = l$ if there is some divisor $E$ of degree $l+1$ such that $D - E$ is not winnable.

§ $r(D)$ is upper bounded by degree: $r(D) \leq deg(D)$

§ if $D$ is of degree 0, then rank is 0 iff $D$ is principal

§ $r(D) \leq r(D + v) \leq r(D) + 1$: adding a dollar can increase rank by at most 1

§ $r(D + D') \geq r(D) + r(D')$: rank is super-linear.

§ 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$:

§ References

• This answer on mathoverflow that asks about how to understand divisors of elliptic curves
• Specialization of linear systems from groups to graphs
• riemann-roch and abel-jacobi theory on a finite graph
• Divisors and Sandpiles: An Introduction to Chip-Firing