§ 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 onlylends 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 becauselending/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 denotedby 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 newdivisor D=D+div(s)D' = D + div(s). We denote this by DsDD \xrightarrow{s} D' and callthis 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 inthe 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 nonsource 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 ifeveryone in SS lends, then no one in SS go into debt. Make the corresponding set-lendingmove. 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'thappen.
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:
--a--
|   |
v   v
b   c
  • This has indegrees (a=0,b=1,c=1)(a=0, b=1,c=1).
Now consider HH:
a
|
v
b
|
v
c
  • 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 sourcesby removing current sources.
  • Theorem is immediate with only one vertex. Assume holds for nn. Now we havea graph with (n+1)(n+1) vertices. Find source in acyclic orientation OGO_G. This hasno incoming edges, so has indegree zero. This must be the same in OGO'_G sinceOGO_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 removingthe same source from both graphs modifes the orientations the same way. Recurseinto 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 singlevertex losing a dollar.
  • In general, for k0k \geq 0, define that rr is at least kk winnable if the dollargame 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