§ Discrete Riemann Roch

§ Divisors

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

§ Degree of a divisor

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

§ Borrowing and lending at a vertex vv_\star

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

§ Borrowing and lending on a set SS:

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

§ Linear equvivalence

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

§ Partial ordering of divisors

We say that D1<D2D_1 < D_2 if for all vv, D1(v)<D2(v)D_1(v) < D_2(v).

§ Effective divisors

A divisor such that v,D(v)0\forall v, D(v) \geq 0 is called as an effective divisor. Sometimes written as D0D \geq 0. Our goal is given a divisor DD, to check if it is linearly equivalent to a divisor DD' such that D0D \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)f(v)+g(v)(f + g)(v) \equiv f(v) + g(v). This respects linear equivalence. Hence, [D1]+[D2][D1+D2][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 qVq \in V, there is an isomorphism of groups ϕq:Pic(G)Z×Jac(G)\phi_q: Pic(G) \rightarrow \mathbb Z \times Jac(G), where we send a divisor class [D][D] to ϕq([D])(deg(D),[Ddeg(D)q]\phi_q([D]) \equiv (deg(D), [D - deg(D)q].
  • Clearly, the new divisor [Ddeg(D)q][D - deg(D)q] has total degree 00, since deg(D)deg(D)has been subtracted off at qq.
  • We can recover the original divisor since we know deg(D)deg(D).

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

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

§ The discrete laplacian

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

§ Firing script

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

§ div is a group homomorphism

We see that div is a function from M(G)=VZM(G) = V \rightarrow \Z to Div(G)=VZDiv(G) = V \rightarrow \Z under the map:
div(s)vVs(v)(v+w) div(s) \equiv \sum_{v \in V} s(v) (-v+ w)
We show that div(s1s2)=div(s1)div(s2)div(s_1 - s_2) = div(s_1) - div(s_2) thereby checking the homomorphism property.
div(s1s2)=vV(s1s2)(v)(v+w)=vV(s1(v)s2(v))(v+w)=vVs1(v)(v+w)vVs2(v)(v+w)=div(s1)div(s2) \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 divdiv is balanced, in that for every v-v we have a +w+w. This makes the total degree zero.

§ Principal divisors: Prin(G)div(M(G))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 DD' is obtainable from DD by a series of lending and borrowing moves, then DDPrin(G)D' - D \in Prin(G).
  • This means that linear equivalence is a coset of the principal divisors: [D]=D+Prin(G)[D] = D + Prin(G).

§ Picard, Jacobian Class group as quotients

  • Pic(G)=Div(G)/Prin(G)Pic(G) = Div(G)/Prin(G).
  • Jac(G)=Div0(G)/Prin(G)Jac(G) = Div^0(G)/Prin(G).
  • Pic(G),Jac(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){div(s):sVZ} 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 DD, does there exist a vector xZVx \in \mathbb Z^V such that D+Lx0D + Lx \geq 0? Clearly, this is some sort of linear inequality. So, we expect polytopes to show up! Since xx 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 VV 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 s1+s2+sns_1 + s_2 + \dots s_nis in the kernel of divdiv: 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:VZs: V \rightarrow \mathbb Z such that div(s)=0div(s) = 0. TODO
This feels sheafy to me, in terms of "locally constant".

§ Reduced laplacian: Configurations on GG

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

§ 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 DD we want to find an effective divisor E0E \geq 0that DD is linearly equivalent to (ie, there exists a series of moves to convert DD to EE).
  2. Pick some benelovent vertex qVq \in V. Call qq the source. Let V=V/qV' = V/q be the non source vertices.
  3. Let qq 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 qq is in debt from this giving. qq makes no lending or borrowing moves. The non-source-vertices must get qq out of debt. Find a SVS \subseteq V' such that if everyone in SS lends, then no one in SS go into debt. Make the corresponding set-lending move. Repeat until no such SS remains. The resulting divisor is said to be qq-reduced.
In the end, if qq is no longer in debt, we win. Otherwise, DD is unwinnable.

§ Superstable configuration

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

§ Decomposition of divisor into superstable configuration

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

§ 4: Acylic orientations

§ Orientations

An orientation of a graph makes each edge directed. We think of edges now as tuples e(u,v)e \equiv (u, v) as an edge from uu to vv. We denote e=ue^- = u and e+=ve^+ = 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 OO is an orientation, define
indegO(u){eO:e+=u} indeg_O(u) \equiv |\{ e \in O : e^+ = u \}|
That is, to each uu, associate the number of edges whose end is at uu.

§ 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 GG:
|   |
v   v
b   c
  • This has indegrees (a=0,b=1,c=1)(a=0, b=1,c=1).
Now consider HH:
  • This has indegrees (a=0,b=1,c=1)(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 OGO_G, OGO'_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 nn. Now we have a graph with (n+1)(n+1) vertices. Find source in acyclic orientation OGO_G. This has no incoming edges, so has indegree zero. This must be the same in OGO'_G since OGO_G and OGO'_G have the same indegree sequence.
  • Now remove the sources that are structurally equal. We get a graph of HH of (n-1) vertices, and we get OHO_H and OHO'_H by removing the sources from OG,OGO_G, O_G'. Since OG=OGO_G = O_G' we must have that OH=OHO_H = O_H' since removing the same source from both graphs modifes the orientations the same way. Recurse into OH,OHO_H, O_H'.

§ Divisor for an orientation

For an orientation OO we define a divisor D(O)D(O) as:
D(O)vV(indegO(v)1)v 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: DD is “more winnable” than DD' if [D]0>[D]0[D]_{\geq 0} > [D']_{\geq 0}. Instead of measuring [D]0[D]_{\geq 0}, we choose to define another function, the rank, that measures "stability/robustness of winnability"
  • Fist, r(D)1r(D) \equiv -1 if DD is unwinnable: r(D)0r(D) \equiv 0 iff [D]0=[D]_{\geq 0} = \emptyset
  • Next, r(D)=1r(D) = 1 if DD is barely winnable. That is, DD is winnable, but there is some vertex vv such that DvD - v is unwinnable. That is, r(D)r(D)is barely winnable if the ability to win at DD can be destroyed by a single vertex losing a dollar.
  • In general, for k0k \geq 0, define that rr is at least kk winnable if the dollar game is winnable strating from all divisors obtained from DD by removing kkdollars. Formally, this becomes:
r(D)k    DEfor all E0 (E effective) of degree k 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)=lr(D) = l if there is some divisor EE of degree l+1l+1 such that DED - E is not winnable.

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

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

§ r(D)r(D+v)r(D)+1r(D) \leq r(D + v) \leq 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'): rank is super-linear.

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

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

§ Canonical divisor

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

§ References