A Universe of Sorts

§ 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

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]

\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}

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

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

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

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$ ).
Pick some benelovent vertex $q \in V$ . Call $q$ the source. Let $V' = V/q$ be the non source vertices.
Let $q$ lend so much money to the non-source-vertices, such that the non-source-vertices, sharing amongst themselves, are out of debt.
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

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

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.

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

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

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

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

\begin{aligned} K(V) = indeg_O(v) + outdeg_O(v) = deg_G(v) \end{aligned}

§ Discrete Riemann Roch

§ Divisors

§ Degree of a divisor

§ Borrowing and lending at a vertex v⋆v_\starv⋆​

§ Borrowing and lending on a set SSS:

§ Linear equvivalence

§ Partial ordering of divisors

§ Effective divisors

§ Addition of divisors

§ The Picard Class Group (group of divisor classes)

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

§ Picard group decomposition in terms of Jacobian group

§ Complete linear system [D]≥0∣[D]_{\geq 0}|[D]≥0​∣

§ The discrete laplacian

§ Firing script

§ div is a group homomorphism

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

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

§ Picard, Jacobian Class group as quotients

§ div is same as laplacian

§ Picard group is cokernel of L

§ Dollar game in terms of laplacian

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

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

§ Reduced laplacian: Configurations on GGG

§ 3: Winning

§ q-reduced configurations

§ Superstable configuration

§ Decomposition of divisor into superstable configuration

§ 4: Acylic orientations

§ Orientations

§ Acylic orientations

§ Acylic orientation has at least one source

§ Indegree sequence of an acyclic orientation.

§ WRONG: Acylic orientation determined by indegree sequence?

§ Acylic orientation determined by indegree sequence

§ Divisor for an orientation

§ 5: Riemann roch

§ The rank function

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

§ if DDD is of degree 0, then rank is 0 iff DDD is principal

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

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

§ Lower bound on rank: r(D)≥deg(D)−gr(D) \geq deg(D) - gr(D)≥deg(D)−g

§ Canonical divisor

§ References

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

§ Borrowing and lending on a set $S$ :

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

§ `div` is a group homomorphism

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

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

§ `div` is same as laplacian

§ Reduced laplacian: Configurations on $G$

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