Science, Faculty of
Mathematics, Department of
DSpace
UBCV
Nicolas, Folinsbee
Doctor of Philosophy - PhD
University of British Columbia
In this thesis, we discuss modelling with (virtual) k-diagrams a class of functions from â¤â¿ to â¤, which we call Riemann functions, that generalize the graph Riemann-Roch rank functions of Baker and Norine. The graph Riemann-Roch theorem has seen significant activity in recent years, however, as of yet, there is not a satisfactory homological interpretation of this theorem. This may be viewed as disappointing given the rich homological theory contained in the classical Riemann-Roch theorem. For a graph Riemann-Roch function, we will be able to express the associated graph Riemann-Roch formula as a (virtual) Euler characteristic of the modelling (virtual) k-diagram. From the development of this approach, we obtain a new formula for computing the graph Riemann-Roch rank of the complete graph Kn.
Riemann Functions, Their Weights,and Modeling Riemann-RochFormulas as Euler CharacteristicsbyNicolas FolinsbeeB.Sc., McGill University, 2014M.Sc., McGill University, 2015A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)December 2021© Nicolas Folinsbee 2021The following individuals certify that they have read, and recommendto the Faculty of Graduate and Postdoctoral Studies for acceptance, thedissertation entitled:Riemann Functions, Their Weights, and Modeling Riemann-RochFormulas as Euler Characteristicssubmitted by Nicolas Folinsbee in partial fulfillment of the requirementsfor the degree of Doctor of Philosophy in Mathematics.Examining Committee:Professor Joel Friedman, Computer Science, UBCSupervisorProfessor Kalle Karu, Mathematics, UBCSupervisory Committee MemberProfessor Brian Marcus, Mathematics, UBCUniversity ExaminerProfessor Lutz Lampe, ECE, UBCUniversity ExaminerAdditional Supervisory Committee Members:Professor Lior Silberman, Mathematics, UBCSupervisory Committee MemberiiAbstractIn this thesis, we discuss modelling with (virtual) k-diagrams a class offunctions from Zn to Z, which we call Riemann functions, that generalizethe graph Riemann-Roch rank functions of Baker and Norine. The graphRiemann-Roch theorem has seen significant activity in recent years, how-ever, as of yet, there is not a satisfactory homological interpretation of thistheorem. This may be viewed as disappointing given the rich homologi-cal theory contained in the classical Riemann-Roch theorem. For a graphRiemann-Roch function, we will be able to express the associated graphRiemann-Roch formula as a (virtual) Euler characteristic of the modelling(virtual) k-diagram. From the development of this approach, we obtain anew formula for computing the graph Riemann-Roch rank of the completegraph Kn.iiiLay SummaryIn mathematics, a duality theory typically refers to a one to one correspon-dence between two seemingly different classes of objects such that the dualof the dual of an object is once again the original object. Duality is of inter-est to mathematicians as knowledge of an object can tell us about its dualand vice versa, and in some cases the dual object is easier to work with.Sheaf theory was developed in the mid-twentieth century as a meansof studying certain questions in geometry. The subsequent advancementof sheaf theory has lead an explosion of research in numerous branches ofmathematics. In this thesis, we will adapt the tools of sheaf theory to thecombinatorial setting. We aim to develop a way of understanding a largeclass of what we call Riemann-Roch formulas, as a form of mathematicalduality.ivPrefaceThis dissertation is original, unpublished work by the author, Nicolas Folins-bee, and Joel Friedman. The writing and finding of the results contained inchapters 1 to 5, with the exception of section 5.4, was done jointly with JoelFriedman. Section 5.4 and chapter 6 was done independently by the author.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Summary of Main Results . . . . . . . . . . . . . . . . . . . 21.1.1 Brief Background on the Graph Riemann-Roch The-orem . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.2 Riemann Functions and Riemann-Roch Formulas . . 31.1.3 Weights . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.4 Ideal Models . . . . . . . . . . . . . . . . . . . . . . . 71.1.5 Diagrams of vector spaces . . . . . . . . . . . . . . . 71.1.6 An ideal model for Riemann functions that count per-fect matchings . . . . . . . . . . . . . . . . . . . . . . 91.1.7 Modeling Riemann functions Zn â Z with virtual di-agrams . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2 Organization of the Thesis . . . . . . . . . . . . . . . . . . . 12viTable of Contents2 Basic Terminology and Combinatorial Results . . . . . . . 132.1 Basic Terminology . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Riemann Functions . . . . . . . . . . . . . . . . . . . . . . . 142.2.1 Examples of Riemann Functions . . . . . . . . . . . . 142.3 The Weight of a Riemann Function, Mo¨bius Inversion, Gen-eralized Riemann Functions, and Modular Functions . . . . . 192.4 Riemann-Roch Formulas and Self-Duality . . . . . . . . . . . 222.5 The Weight of the Riemann-Roch Rank of the CompleteGraph and Related Graphs . . . . . . . . . . . . . . . . . . . 242.5.1 Standard Facts about the Graph Riemann-Roch Rank 242.5.2 A Generalization of a Fundamental Lemma of Coriand Le Borgne . . . . . . . . . . . . . . . . . . . . . . 252.5.3 The First Coordinates for Pic, Dâapre`s Cori-Le Borgne 262.5.4 An Intermediate Weight Calculation: (1â tnâ1)rBN . 282.5.5 The Second Coordinates for Pic . . . . . . . . . . . . 302.5.6 The Second Coordinates: Practical Aspects . . . . . . 312.5.7 Computation of (1â tn)(1â tnâ1)rBN and, finally, of W 352.6 Perfect Matchings and r-fold Matchings . . . . . . . . . . . . 392.7 Writing n = 2 Riemann Weights as Perfect Matchings . . . . 422.8 Fundamental Domains and the Proofs of Theorems 2.3.4and 2.3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.8.1 Definition of Fundamental Modular Domains . . . . . 462.8.2 Proof of Theorem 2.3.4 Without Reference to Cubisms 462.8.3 Cubmisms: Motivation, Definition, and Implication ofDomain Fundamentality . . . . . . . . . . . . . . . . 492.8.4 Second Proof of Theorem 2.8.3 . . . . . . . . . . . . . 502.8.5 Other Examples of Cubisms and the Proof of Theo-rem2.3.5 . . . . . . . . . . . . . . . . . . . . . . . . . 523 Diagrams, Betti Numbers, and Models for Riemann Func-tions that Count Perfect Matchings . . . . . . . . . . . . . . 543.1 Betti Numbers, Fredholm Maps, and Direct Sums . . . . . . 543.2 k-Diagrams: Diagrams of k-Vector Spaces . . . . . . . . . . . 55viiTable of Contents3.3 Conventions on Sets, Multisets, Induced Vector Spaces, andMW,d for Non-Negative Weights . . . . . . . . . . . . . . . . 573.4 The Euler Characteristic of MW,d as a Function of d . . . . 593.5 The Betti Numbers of MW,d for Perfect Matchings . . . . . 603.6 The Constant Diagram and Related Diagrams . . . . . . . . 623.7 Direct Sums and Morphisms of Diagrams . . . . . . . . . . . 633.8 Direct Sums and Proof of Theorem 3.5.1 . . . . . . . . . . . 653.9 Indicator k-Diagrams and Sums of Perfect Matchings . . . . 663.10 A Simple Duality Theorem . . . . . . . . . . . . . . . . . . . 693.10.1 The Fine Print Regarding F(â) and H1(F) . . . . . 714 Riemann Functions for n = 2 and Virtual Euler Character-istics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734.1 Virtual Diagrams and Virtual Fredholm Diagrams . . . . . . 734.2 Riemann Functions as Virtual Direct Sums . . . . . . . . . . 755 Modeling General Riemann Functions . . . . . . . . . . . . 785.1 Isomorphisms That Are Simple Along the A1 Values . . . . . 795.2 Combinatorial Versions of the Isomorphism Lemmas . . . . . 825.3 Proof of Theorem 5.0.2 . . . . . . . . . . . . . . . . . . . . . 855.4 Vertex Clearing . . . . . . . . . . . . . . . . . . . . . . . . . 876 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906.1 Towards a Strong Duality Theorem . . . . . . . . . . . . . . 906.2 Further Questions Which Interest Us . . . . . . . . . . . . . 93Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95viiiList of Figures1.1 Our Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.2 The Diagram MW,d . . . . . . . . . . . . . . . . . . . . . . . 92.1 The example n = 4 in ãb, iã coordinates, b = (b1, b2) â{0, 1, 2, 3}2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.2 A cubism for Dncoord with n = 2. . . . . . . . . . . . . . . . . . 512.3 Degree cubism . . . . . . . . . . . . . . . . . . . . . . . . . . 533.1 Our Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.2 A Model for W and sW . . . . . . . . . . . . . . . . . . . . . 583.3 The Diagram k and Related Diagrams . . . . . . . . . . . . . 623.4 A morphism of diagrams Ï : F â G, depicted in thick lines . 643.5 The Indicator k-Diagram Iaâ¤d? . . . . . . . . . . . . . . . . . 675.1 Implications of Ï(A1) = identity, for a Ï : MW1,d â MW2,d(where we omit the quantifiers âa1 â Z and âa2 â Z) . . . . . 806.1 The Diagram of Rings, Or . . . . . . . . . . . . . . . . . . . . 92ixAcknowledgementsI would like to thank Joel Friedman for his indispensable help and guidancein writing this thesis. I would also like to thank my family and friends fortheir support throughout my time in Vancouver.xChapter 1IntroductionSheaf theory was developed in the mid-twentieth century as a means ofstudying questions in algebraic topology [18, 25]. The subsequent advance-ment of sheaf theory has lead an explosion of research in numerous branchesof mathematics, notably in algebraic geometry [9, 19, 31]. In this thesis, wewill adapt the tools of sheaf theory to the combinatorial setting, as was donepreviously in [16]. We aim to develop a way of understanding a large class ofwhat we call Riemann-Roch formulas, as a formula that expresses an Eulercharacteristic computation. This is motivated by the question of Baker-Norine [6] as to whether their graph Riemann-Roch formula can be viewedas such an Euler characteristic formula and if it satisfies a form of SerreDuality. However, our main results apply to any formula that arises from amuch wider and simpler class of functions that we call Riemann functions.Roughly speaking, our main results says that any formula of this type canbe modelled as such, provided that (1) one is willing to work with âformaldifferencesâ of Euler characteristics, and (2) one is willing to make a numberof ad hoc choices in building the model (which one can ultimately prove donot change the isomorphism class of the model). We therefore view this asa first step in modeling such formulas that we hope will ultimately lead tomore ideal models of Riemann-Roch formulas. Beyond this, the foundationswe develop to construct our models have a number of interesting byproducts.We emphasize that the main results in the thesis do not assume any priorknowledge beyond some basic combinatorics and linear algebra. We do notassume the reader is familiar with the Baker-Norine formula for any of ourmain results nor do we assume any familiarity with sheaf theory (either ongraphs, as in [16], or in the classical setting) or the Riemann-Roch formula,although our techniques do mimic ideas from there.11.1. Summary of Main Results1.1 Summary of Main ResultsIn this section we summarize our main results, using notation that is com-mon in the literature and made precise starting in the next chapter. We useZ for the integers, Zâ¤d for the integers less than or equal to d, similarly forZâ¥d, and N = Zâ¥1 = {1, 2, . . .} for the natural numbers. For n â N we use[n] to denote {1, . . . , n}.We typically denote vectors with bold face, writing d â Zn, and theircomponents with plain face, writing d = (d1, . . . , dn). We define the degreeof d â Zn to be deg(d) = d1 + · · Â·+ dn, and endow Zn with its usual partialorder, writing dâ² â¤ d to mean dâ²i â¤ di for all i â [n].1.1.1 Brief Background on the Graph Riemann-RochTheoremFor a multigraph G, with vertex set V (G) and edge set E(G), a divisord on G is an element of Z|V (G)|, which we identify with an integer valuedfunction on V (G). We say two divisors d and dâ² are linearly equivalent(denoted d â¼ dâ²) if d â dâ² â im(âG), where âG denotes the Laplacianmatrix of G. A divisor d is said to be effective if d â¥ 0. The rank r(d) ofa divisor d is defined asr(d) =ï£±ï£²ï£³â1 if d is not linearly equivalent to an effective divisorminiâ[n]{r(dâ ei)}+ 1 otherwise,where ei denotes the divisor taking value 1 in the i-th component and0 elsewhere. For a vertex vi â V (G) we denote by deg(vi) the number ofedges incident to vi. We define the genus of a graph, denoted g, to be|E(G)| â |V (G)|+ 1 and the canonical divisor K is defined asK =âviâV (G)(deg(vi)â 2) · vi.The graph Riemann-Roch theorem states that for a multigraph G with21.1. Summary of Main Resultsno self-loops, the formular(d)â r(Kâ d) = deg(d)â g + 1 (1.1)holds for all d. Crucially, in (1.2), the spaces of functions f : Z|V (G)| â Zobeying {f |âG(f) â¥ âd)}, with d a given divisor, are not vector spaces andso proofs of the classical Riemann-Roch theorem do not carry over directly.1.1.2 Riemann Functions and Riemann-Roch FormulasWe say that a function f : Zn â Z is a Riemann function if (1) f(d) = 0when deg(d) = d1 + · · Â·+dn is sufficiently small, and (2) f(d) = deg(d) +Cfor a constant C when deg(d) is sufficiently large; we refer to C as the offsetof f . If f is as above, then for each K â Zn there is a unique function fâ§Ksuch thatf(d)â fâ§K(Kâ d) = deg(d) + C, (1.2)for all d â Zn. We furthermore observe that fâ§K is also a Riemann function(and that the function d 7â fâ§K(Kâd) is independent of K). We refer to theabove formula as a Riemann-Roch formula for f . We easily see that (fâ§K)â§K =f , and we say that (1.2) is self-dual if fâ§K = f . Roughly speaking, the goal ofthis thesis is to model any formula (1.2) as expressing the Euler characteristicof a simple kind of sheaf, in a way that the sheaves involved may shed lighton aspects of this formula, including when self-duality holds. Again, weavoid any essential reference to sheaf theory, and instead refer to certaindiagrams of vector spaces. Moreover, we can view each such diagram asproducing merely a linear transformations of vector spaces (similar to [15]),which technically arises as a cohomology computation from a projectiveresolution of the constant diagram (see [14â16]).The point of articles such as [3, 6] is to study certain Riemann functionsof interest, f , and determine if such f = fâ§K for some K. Our approachdiffers in that we develop combinatorics and models for any Riemann-Rochformula, and only at times consider whether or not self-duality holds.The motivating example is that if G is a graph whose vertex set is31.1. Summary of Main Results[n] = {1, . . . , n}, then 1 plus the rank of d in the sense of Baker-Norine[6] (with d â Zn), is a Riemann function. There is a large literature onthese functions [3, 4, 6, 12], which are related to chip firing games and thesandpile model; see [5, 7, 8, 10, 12, 26, 29] and the references there for morehistorical context. Furthermore, there has been numerous generalizations ofthe graph Riemann-Roch theorem to tropical curves and other settings inrecent years [2, 5, 11, 17, 21, 23, 28]. Tropical curves are related to Tate-Mumford curves [30]. Although this thesis is organized primarily for thereader interested in this area, all of our main theorems do not require anyknowledge of the Baker-Norine rank and related functions. Our motivationfor the term Riemann function is the classical Riemannâs theorem for curves;later we will elaborate on such examples.1.1.3 WeightsWe say that a function f : Zn â Z is initially zero if f(d) = 0 wheneverdeg(d) is sufficiently small (i.e., deg(d) â¤ C for some C depending only onf). If so, then there is a unique function W : Zn â Z that is initially zeroand for whichâd â Zn, f(d) =âdâ²â¤dW (d).We refer to W as the weight of f , and also say that f counts W . The weight,W , can be written in terms of f as W = mf , where(m(f))(d) =âIâ[n](â1)|I|f(dâ eI)where eI is the vector that is 1 in components in I, and 0 elsewhere; this isa standard type of Mo¨bius inversion formula on a poset (partially orderedset), e.g., [32].Our main interest in the weights of a Riemann function is to build modelsof Riemann-Roch formulas as expressing Euler characteristics. However,weights seem to hold many interesting combinatorial properties and theyappear to organize the Riemann functions and Riemann-Roch formulas in a41.1. Summary of Main Resultsuseful way. Let us provide some evidence.First, if W : Zn â Z is any function and L â Zn, let W âL : Zn â Z denotethe function given as W âL(d) = (â1)nW (Lâ d). Of course, (W âL)âL = W . Itcan also be seen that if f is a Riemann function of weight W , and K â Zn,then the weight of fâ§K in (1.2) is given by WâL where L = K + 1. Theoperation that passes from W to W âL is simpler than the operation passingfrom f to fâ§K.Second, if f : Z2 â Z is initially zero, then f is a Riemann function iffits weight W has all row sums and all column sums equal to 1, i.e.,âa1 â Z,âa2âZW (a1, a2) = 1, and âa2 â Z,âa1âZW (a1, a2) = 1. (1.3)Third, in (1.3), if W takes on only non-negative values, then clearly eachrow and column of W contains a single 1 and is otherwise 0; hence there isa bijection pi : Zâ Z such that W (i, j) is 1 if pi(i) = j, and 0 otherwise. Inthis case we say that W is a perfect matching, and that f counts a perfectmatching. For such f :f(d) =â£â£{m â Z | m â¤ d1 and pi(m) â¤ d2}â£â£ (1.4)and we will have a simple model with some remarkable properties, includinga version of Serre duality.Fourth, if f = f(d) is a Riemann function Z2 â Z that is non-decreasingin d (this is true of any restriction in both the classical and graph Riemann-Roch settings), then each row and column of W is an alternating sequenceof +1âs and â1âs interspersed between 0âs. To model a general Riemannfunction f : Z2 â Z, we will need to write f asf = f1 + · · Â·+ fs â fË1 â · · · â fËsâ1, (1.5)where the fi and fËi are Riemann functions that count perfect matchings.51.1. Summary of Main ResultsOur approach to doing so is to write the weight, W , of f asW = W1 + · · Â·+Ws â WË1 â · · · â WËsâ1 (1.6)where the Wi and WËi are non-negative, which then immediately gives adecomposition (1.5). It seems much easier to write W as (1.6) than todirectly attempt to write f as in (1.5).Finally, from the ideal models of the fi and fËi we can model f as a formaldifference of ideal models. A n-dimensional Riemann function, f = f(d),for n â¥ 3, will be modelled by varying 2 variables at a time (fixing the othern â 2 variables), and appealing to our models for n = 2 and piecing themtogether.As an attestation to the value of using weights to understand the graphRiemann-Roch rank, consider the complete graph Kn on n vertices. IfrankKn : Zn â Zâ¥â1 is the Baker-Norine rank of Kn, and f equals oneplus rankKn , then f(d) (or rankKn(d)) does not appear to have a simplemeaning (although [12] gives an algorithm which after sorting d1, . . . , dnâ2requires only an additional O(n) operations to compute this rank). However,we will prove that the weight of this function is given by a simple formula(2.28). In the process of computing some examples of Kn for small n, wealso discovered the formulaâa1, . . . , anâ2 â {0, . . . , nâ 1},f(a1, . . . , anâ2, 0, a)â f(a1, . . . , anâ2,â1, a) ={1 if a â¥ 0, and0 if a â¤ â1,which is easy to verify using standard facts about the Baker-Norine rankand one elegant and rather ingenious idea in [12] (the proof of half of theirProposition 10). This gives another O(n) time formulaf(a) =â£â£â£â£{j = 0, . . . ,deg(a) | nâ2âi=1((ai + j) mod n) â¤ deg(a)â j}â£â£â£â£to compute the rank f(d) (once one sorts d1, . . . , dnâ2).61.1. Summary of Main Results1.1.4 Ideal ModelsLet k be a field (typically this field is arbitrary and unimportant to us).By a k-Fredholm map we mean a linear transformation of k-vector spacesÏ : B â A whose kernel and cokernel are finite dimensional. In this case wedefineH0(Ï)def= ker Ï, H1(Ï)def= coker Ï,and define its Betti numbers to be bi(Ï)def= dimkHi(Ï) and its index or Eulercharacteristic, to be Ï(Ï) = b0(Ï) â b1(Ï). Our Fredholm maps will have acertain structure, but one can think of our models in broad terms as merelyproducing Fredholm maps.We say that an ideal model of a Riemann function f consists of givingfor each d â Zn a k-Fredholm map Ïd : Bd â Ad such thatâd â Zn, f(d) = b0(Ïd), (1.7)and letting ei denote the i-th standard basis vector of Zn,âi â [n],âd â Zn, Ï(d + ei) = Ï(d) + 1. (1.8)Of course, ideally these conditions should be simple to verify, and whenf counts a perfect matching they are (once we develop some formalitiesregarding our models). If so, then for any d,K â Zn it follows thatb1(Ïd) = fâ§K(Kâ d),and (1.2) can be viewed as an Euler characteristic formula.We will give an ideal model for Riemann functions f : Z2 â Z that countperfect matchings in a sense we now describe.1.1.5 Diagrams of vector spacesOur ideal models Ïd for Riemann functions that count perfect matchings arebased on a certain type of diagram of vector spaces.By a diagram of k-vector spaces, F , we mean a diagram depicted in71.1. Summary of Main ResultsF(B1)F(B2)F(B3)F(A1)F(A2)F(Ï1,1)F(Ï2,2)F(Ï3,1)F(Ï3,2)Figure 1.1: Our DiagramsFigure 1.1: specifically a diagram of k-vector spaces, or simply a k-diagram,is the data, F , consisting of:1. five k-vector spaces F(A1),F(A2),F(B1),F(B3),F(B2), which we callthe values of F , and2. four linear transformations, F(Ï1,1),F(Ï3,1),F(Ï3,2),F(Ï2,2), whereF(Ïi,j) is a morphism F(Bi) â F(Aj) which we call the restrictionmaps of F (and F(Ïi,j) does not exist for (i, j) equal to (1, 2) and(2, 1)).We setF(B) = F(B1)âF(B3)âF(B2), F(A) = F(A1)âF(A2),and define the differential of F to be the linear map F(â) : F(B)â F(A)F(â)(Î²1, β3, β2) =(F(Ï11)Î²1 âF(Ï31)Î²3,F(Ï22)Î²2 âF(Ï32)Î²3).We will give a number of standard tools to understand and work withk-diagrams. For example, an element of the kernel of F(â) is equivalentto a global section of F , and also to a morphism k â F where k is theconstant diagram k. As another example, the seemingly innocuous directsum of k-diagrams will be a powerful tool (1) to decompose the diagramsMW,d below into very simple k-diagrams, (2) to better understand Bettinumbers, and (3) to prove that our models for general Riemann functionsare independent of the ad hoc choices we make.81.1. Summary of Main ResultsM(B1) = kâZâ¤d1M(B2) = kâZâ¤d2M(B3) = kâZM(A1) = kâZM(A2) = kâZkâinclusionkâinclusionkâIdentitykâpiFigure 1.2: The Diagram MW,d1.1.6 An ideal model for Riemann functions that countperfect matchingsGiven a Riemann function f that counts a perfect matching, W , let pi be theassociated bounded bijection Zâ Z. To such a W we associate the diagramMW,d depicted in Figure 1.2. Here Zâ¤d denotes the integers at most d; therest of the notation is fairly common and is explained later. We later definea diagramMW,d for any bounded weight W : Z2 â Zâ¥0; the only differenceis MW,d(B3) (and its restriction maps). Setting Ïd = MW,d(â) we easilyverify that Ïd is a family of Fredholm maps that satisfies (1.7) and (1.8).1.1.7 Modeling Riemann functions Zn â Z with virtualdiagramsWe now model any Riemann function f : Zn â Z using virtual Fredholmmaps and virtual diagrams, in the usual sense of the Grothendieck group(as used in K-Theory). Namely, by a virtual k-Fredholm map we mean apair (Ï1, Ï2) of k-Fredholm maps, and we say that this pair is equivalent toanother pair (Ï â²1, Ï â²2) if there is another Fredholm map Ï0 and an isomorphismÏ0 â Ï1 â Ï â²2 â Ï0 â Ï â²1 â Ï2.We verify that this relation is, indeed, an equivalence relation, and we use[(Ï1, Ï2)] to denote the equivalence class of (Ï1, Ï2). We refer to the equiv-alence classes of virtual k-Fredholm maps as the Grothendieck group of k-91.1. Summary of Main ResultsFredholm maps. We will usually write (Ï1, Ï2) and [(Ï1, Ï2)] more suggestivelyas, respectively, Ï1 Ï2 and [Ï1 Ï2]; we easily verify that is a well-definedoperation on the Grothendieck group of Fredholm maps, and â, satisfythe same rules as +,â do (on Z or R). Furthermore, settingH i(Ï1 Ï2) def= H i(Ï1) H i(Ï2)one gets a virtual finite dimensional k-vector space, giving well-defined co-homology groups for the Grothendieck group of k-Fredholm maps, and well-defined Betti numbers, i.e., dimensions of the cohomology groupsbi(Ï1 Ï2) = bi(Ï1)â bi(Ï2)in Z, as well as a well-defined Euler characteristicÏ(Ï1 Ï2) = Ï(Ï1)â Ï(Ï2).One similarly defines the Grothendieck group of diagrams of k-vectorspaces, F , under the condition that F(â) is a Fredholm map. Now we areprepared to discuss our models.We prove that if f is a Riemann function Z2 â Z, then we may writef = f1 + · · Â·+ fs â fË1 â · · · â fËsâ1 (1.9)for some s â N, where the fi and fËi count perfect matchings. For each wayof writing f as such we get a virtual diagram of k-vector spaces, and weprove that its equivalence class[MW1,d â · · · âMWs,d MWË1,d · · · MWËsâ1,d]is independent of how we express f in (1.9). This gives a model of f interms of virtual diagrams of k-vector spaces.We can now describe how we model a Riemann function f : Zn â Z forn â¥ 3. We choose distinct i, j â [n], and consider the Riemann functionfi,j,d : Z2 â Z obtained by varying f(d) in only the i-th and j-th coordinate101.1. Summary of Main Resultsof d, i.e.,fi,j,d(ai, aj)def= f(d + aiei + ajej);hence fi,j,d(0, 0) = f(d). According to the n = 2 results above, this yields afamily of virtual diagrams of k-vector spaces F(ai,aj) varying over (ai, aj) âZ2. We set [Mf,i,j,d] to be [F(di,dj)]. It follows thatb0([Mf,i,j,d]) = f(d), Ï([Mf,i,j,d]) = d1 + . . .+ dn + C â²i,j ,where C â² = C â²i,j the constant such that for ai + aj sufficiently large,fi,j,d(ai, aj) = ai + aj + Câ²i,j .We easily check that C â²ij = deg(d) + C where C is the constant for whichf(d) = deg(d) + Cfor d sufficiently large. HenceÏ([Mf,i,j,d]) = deg(d) + C(independent of i, j). It follows that [Mf,i,j,d] satisfies the properties wedesire of a model, except that we are only varying two of the coordinatesof d at a time. The saving grace of this construction is that we can provethat [Mf,i,j,d] is independent of i, j. In addition, we will prove that fori, iâ², j â [n] distinct, if fi,j,d and fiâ²,j,d count perfect matchings W and W â²âso that we can model both as diagrams instead of virtual diagramsâthenMW,d andMW â²,d are isomorphic as diagrams. This is the case, for example,for the Baker-Norine rank of certain graphs, G, such as those where each twovertices are joined by a fixed number of edges. In this case, we have identifieda single diagramâup to isomorphismânamely Mf,i,j,d = MWi,j,d,0, foreach d.111.2. Organization of the Thesis1.2 Organization of the ThesisThe rest of the thesis is organised as follows.In chapter 2, we introduce the preliminary material for Riemann func-tions and Riemannian weights and study the basic properties of these ob-jects. As a demonstration of the usefulness of the expression of Riemannfunctions as a Riemannian weight, we compute the weight of the graphRiemann-Roch rank of the complete graph and use this to provide a for-mula for the graph Riemann-Roch rank of Kn.In chapter 3, we introduce our sheaf models for perfect matchings. Wedefine the Betti numbers and Euler characteristic of these and show they canbe decomposed into âbasicâ sheaves. We use this to show a duality theoremfor these sheaves.In chapter 4, we model a general Riemann function f : Z2 â Z as avirtual Euler characteristic. This is done by first decomposing the weight ofthe Riemann function into a difference of perfect matchings then using thesheaves introduced in the previous chapter for perfect matchings. We showthe virtual sheaves are independent (up to isomorphism) of the decomposi-tion into perfect matchings.In chapter 5, we discuss modelling arbitrary Riemann functions f :Zn â Z by pasting together our models for Riemann functions Z2 â Z.12Chapter 2Basic Terminology andCombinatorial ResultsIn this section we give some basic terminology and results to describe thefunctions we will model and, in later sections, our models. All terminologyand results in this section are combinatorial, without any reference to linearalgebra and k-diagrams.2.1 Basic TerminologyWe introduce the terminology which we will use throughout the rest of thearticle.We use Z,N to denote the integers and positive integers; for a â Z, weuse Zâ¤a to denote the integers less than a or equal to a, and similarly forthe subscript â¥ a. For n â N we use [n] to denote {1, . . . , n}. We usebold face d = (d1, . . . , dn) to denote elements of Zn, using plain face forthe components of d; by the degree of d, denoted deg(d) or at times |d|, wemean d1 +. . .+dn. We use ei â Rn (with n understood) be the i-th standardbasis vector (i.e., whose j-th component is 1 if j = i and 0 otherwise), andfor I â [n] (with n understood) we seteI =âiâIei;hence in case I = â is the empty set, then eâ = 0 = (0, . . . , 0).For n â N, we endow Zn with the usual partial order, that isdâ² â¤ d iff dâ²i â¤ di âi â [n],132.2. Riemann Functionswhere [n] = {1, 2, . . . , n}.2.2 Riemann FunctionsDefinition 2.2.1. If f, g are functions Zn â Z, we say that f equals ginitially (respectively, eventually) if f(d) = g(d) for deg(d) sufficiently small(respectively, sufficiently large); similarly, we say that that f is initiallyzero (respectively eventually zero) if f(d) = 0 for deg(d) sufficiently small(respectively, sufficiently large). We say the f is a Riemann function if itis initially zero and for some C, f(d) = deg(d) + C for deg(d) sufficientlylarge; we refer to C as the offset of f .2.2.1 Examples of Riemann FunctionsThe following subsection is not essential to the rest of this article, except thatit defines the Baker-Norine rank; it may be skipped by the reader interestedonly in modeling Riemann functions.Example 2.2.2. Let X be an algebraic curve over an algebraically closedfield k, and K be its function field; one understands either (1) K is a finiteextension of k(x) where x is an indeterminate (i.e., transcendental) and X isits set of discrete valuations1 (e.g., [24], Section 1.2), or (2) X is projectivecurve in the usual sense (e.g., [20], Section 4.1), and K is its function field.(For k = C one can also view X as a compact Riemann surface, and K asits field of meromophic functions.) To each f â K {0} one associates thedivisor (i.e., Weil divisor) equal to (f) =âvâX ordv(f)v [24]2. For eachdivisor D one setsL(D) = {0} âª {f â K | (f) â¥ âD},1Riemannâs theorem arose from Riemann study of integrals of the formâ«p(x)âq(x) dxwhere p, q are rational functions, such as the arc length of an ellipse. In this case, therelevant K is C(x)[y]/(y2 â q(x)).2Here ordv(f) is (1) 0 if f(v) is finite and non-zero, (2) the multiplicity of the zero atv if f(v) = 0, and (3) minus the multiplicity of the pole at v if f(v) =â.142.2. Riemann Functionswhere we regard 0 â K as having divisor (0) â¥ âD for all D; this makesL(D) â K a k-linear subspace, and we setl(D) = dimk L(D)For a divisor D we use deg(D) to denote the sum of the Z-coefficients in D.For f â K {0}, f has the same number of zeroes and poles, counted withmultiplicity, i.e., deg((f)) = 0. It follows that l(D) = 0 when deg(D) < 0.Riemannâs theorem says that for the genus g â Zâ¥0 of X, for any divisor Dwith deg(D) sufficiently large,l(D) = deg(D) + 1â g.Hence for any points P1, . . . , Pn â X we havef(d)def= l(d1P1 + · · Â·+ dnPn) (2.1)is a Riemann function. The modern approach to Riemannâs theorem asso-ciates to each Weil divisor, D, an invertible sheaf (i.e., a line bundle) L(D)([20], Section 4.1), whose set of global sections, Î(X,L(D)), is isomorphicto L(D), and hence b0(L(D)), the 0-th Betti number of L(D), equals l(D)above.Next we describe some general types of Riemann functions inspired by[6].Example 2.2.3. For n â N and a â Z, letZna = {d â Zn | deg(d) = a}, Zndegâ¤a =âbâ¤aZnb .Let n â N and N â Rn such that1. for some m,M â Z we haveZndegâ¤m â N â Zndegâ¤M , (2.2)152.2. Riemann Functionsand2. setting M to be the largest degree of an element of N , then thereexists a C such that if d â ZnM , then then some dâ² â N â© ZnM hasâdâ dâ²â1 â¤ C.Considerf(d) = ÏL1(d,N ) = mindâ²âNâdâ dâ²âL1 . (2.3)For d with deg(d) â¥ M any path from d to N will have length at leastdeg(d)âM , hence,f(d) â¥ deg(d)âM.For d with deg(d) â¥M we denote by Sd the setsSd = {dâ² â ZnM |dâ² â¤ d}.These will be regular k-simplicies. Choosing CË sufficiently large so that thecenter of Sd is distance at least C + 1 from ZnM â Sd and thus for any dwith deg(d) â¥ CË + M , we know Sd will contain an element of N . As theL1 distance from d to Sd is deg(d)âM , it follows thatf(d) = deg(d)âMfor deg(d) â¥ CË +M , and hence f is a Riemann function of offset âM .Example 2.2.4. Condition (2) on N above follows from the followingstronger condition: for any N â Zn, say that d â Zn is an invariant trans-lation of N if for all dâ² â Zn, dâ² â N iff d + dâ² â N . We easily see thatthe set, T = T (N ) of all invariant translations is a subgroup of the additivegroup Zn, and that under (2.2), T â Zn0 . If T is a full rank subgroup of Zn0(i.e., of rank nâ 1), then Condition (2) is automatically satisfied.Example 2.2.5. In typical examples N above is a downset, i.e., d â N anddâ² â¤ d implies that dâ² â N . In this case if the closest point in N to somed â Zn is dâ² â N , then clearly dâ² â¤ d, and f(d) = d â dâ² and we easily162.2. Riemann Functionsverify the converse, i.e.,f(d) = min{deg(dâ dâ²) | dâ² â N , dâ² â¤ d}= min{deg(dâ dâ²) | f(dâ²) = 0}.Example 2.2.6. Let G = (V,E) be a connected graph without self-loops(but possibly multiple edges) on n vertices. Let âG : Zn â Zn0 be the usualgraph Laplacian (e.g., [6]), and let L = Image(â). Say that d,dâ² â Zn areequivalent, written d â¼ dâ², if dâdâ² â L, and say that d is effective if d â¥ 0.Let N be the elements of Zn that are not equivalent to an effective elementof Zn. Then (2.3) is a Riemann function, and the Baker-Norine rank of d,denoted rBN(d), is f(d)â1. Hence rBN(d) is initially equal to â1, not 0; allsubsequent papers in this direction, e.g., [3, 12] and many others, follow thisconvention. The offset of f is therefore the maximum degree of a point of N ,which is well-known and easily proven to be |V | â |E| using the philosophyof parking functions or reduced divisors: namely, if we consider the d oflargest degree M that lies in N , i.e., that is not equivalent to an effectivedivisor, we may find a vn-reduced divisor linearly equivalent to d so thatd1 â¤ degG(1)â1, where degG(i) denotes the degree of i in the graph G, andd2 â¤ degGâ²(2) â 1, where Gâ² is G with the vertex 1 and all incident edgesremoved, d3 â¤ degGâ²â²(3)â1, etc., until dn â¤ degG(nâ1)(nâ1)â1 (where G(`)is G with vertices 1, . . . , ` removed and all their incident edges). However,taking d` = degG(`)(`)â 1 attains equality in all these inequalities, and it isnot hard to see that this divisor lies in N , and its degree, M , is |E| â |V |.Hence the offset of f is âM = |V | â |E|.Example 2.2.7. More generally, all the definitions aboveâequivalent, ef-fective, and Nâwork if L is any lattice, i.e., additive subgroup of Zn0 . Oneeasily sees that f as in (2.3) is a Riemann function iff L is of full rank (i.e.,rank n â 1). The rank r(d) = f(d) â 1 is defined in [3], page 5, and theydefine a quantity gmax(L) for which 1â gmaxL is the offset of f .We remark that if L â Zn0 is not of full rank, then condition (2) inExample 2.2.3 fails to hold, and we easily see that ÏL1(d,N ) fails to be a172.2. Riemann FunctionsRiemann function.Example 2.2.8. Let f : Zn â Z be any Riemann function with f(d) =deg(d) +C for deg(d) sufficiently large. Then for any distinct i, j â [n] andd â Zn, the function fi,j,d : Z2 â Z given asfi,j,d(ai, aj) = f(d + aiei + ajej)(2.4)is a Riemann function Z2 â Z, and for ai + aj large we havefi,j,d(ai, aj) = ai + aj + Câ², where C â² = deg(d) + C. (2.5)[It will be important in Section 5 that C â² depends only on d and not on i, j.]We call fi,j,d a two-variable restriction of f ; we may similarly restrict f toone variable or three or more variables, and any such restriction is clearly aRiemann function.Let us describe some typical properties of Riemann functions above.Definition 2.2.9. We say that a function f : Zn â Z is1. slowly growing if for all d â Zn and i â [n] we havef(d) â¤ f(d + ei) â¤ f(d) + 1,and2. p-periodic for a p â N if for all i, j â [n] and all d â Zn we havef(d + p ei â p ej) = f(d).We easily see:1. in Example 2.2.2, f as in (2.1) is always slowly growing, but notgenerally periodic;2. in Example 2.2.3, f given by (2.3) is slowly growing whenever N is adownset, i.e., when d â N and dâ² â¤ d implies dâ² â N ;182.3. The Weight of a Riemann Function, Mo¨bius Inversion, Generalized Riemann Functions, and Modular Functions3. in Example 2.2.7, f is p-periodic such that each element of Zn0/L is oforder p (hence p = |Zn0/L| works);4. in Example 2.2.8, if f : Zn â Z is either slowly growing or p-periodicfor some p, then the same holds of any restriction of f to two or more(or even one) of its variables.2.3 The Weight of a Riemann Function, Mo¨biusInversion, Generalized Riemann Functions,and Modular FunctionsIn this article we focus on modeling Riemann functions. However, we thinkit interesting to state our results more generally when possible.Since a Riemann function Z2 â Z eventually equals d1 + d2 + C, onemay consider that one possible generalization of this notion for a functionZ3 â Z might be a function that eventually equals d1d2 + d1d3 + d2d3plus lower order terms. We now define a generalized Riemann function thatincludes these types of functions, as well.If f is initially zero, then there is a unique initially zero W â Zn â Zfor which f = sW where(sW )(d) =âdâ²â¤dW (dâ²), (2.6)since we can determine W (d) inductively on deg(d) setW (d) = f(d)ââdâ²â¤d, dâ² 6=dW (dâ²).Proposition 2.3.1. Consider the operator m on functions Zn â Z definedvia(mf)(d) =âIâ[n](â1)|I|f(dâ eI). (2.7)Then if f = sW is as above and in (2.6), then W = mf .192.3. The Weight of a Riemann Function, Mo¨bius Inversion, Generalized Riemann Functions, and Modular FunctionsThe above can be viewed as the Mo¨bius inversion formula for the partialorder â¤ on Zn.Proof. We have f(d) = 0 whenever deg(d) â¤ C for some C, and then (2.7)shows that (mf)(d) = 0 for deg(d) â¤ C as well. Since there is a uniqueinitially zero W with sW = f , it suffices to show that smf = f . Since f isinitially zero, for any d â Zn write (smf)(d) as(smf)(d) =âdâ²â¤dâIâ[n](â1)|I|f(dâ eI)which is a double sum of finitely many terms since f is initially zero; hencewe may rearrange terms, set dâ²â² = dâ eI and write this double sum asâdâ²â²â¤df(dâ²â²) adâ²â² , where adâ²â² =âI s.t. dâ²â²+eIâ¤d(â1)|I|;it follows that ad = 1, since the sum is over only I = â , and otherwiseadâ²â² = 0, since the sum is over all I â J where J is the set of j such thatdâ²â²j < dj .Definition 2.3.2. Throughout this article we reserve the symbols m, s fortheir meanings in (2.6) and (2.7). If f,W are initially zero functions Zn â Zwith f = sW , we say that f counts W and that W is the weight of f . Afunction h : Zn â Z is modular if f â kerm (i.e., mf is the zero function).We say that f : Zn â Z is a generalized Riemann function if if it initiallyzero and eventually equals a modular function, i.e., for some h â kerm wehave f(d) = h(d) for deg(d) sufficiently large.Definition 2.3.3. A function W : Zn â Z is a Riemannian weight (respec-tively, generalized Riemannian weight) if W = mf where f : Zn â Z is aRiemann function (respectively, generalized Riemann function).We will be especially interested in Riemann functions Z2 â Z and theirweights W = mf . It is useful to notice that for such functions we that that202.3. The Weight of a Riemann Function, Mo¨bius Inversion, Generalized Riemann Functions, and Modular Functionsfor any fixed d1 and d2 sufficiently large,f(d1, d2)â f(d1 â 1, d2) = 1,and hence, for fixed d1,ââd2=ââW (d1, d2) = 1, (2.8)and similarly, for fixed d2 we haveââd1=ââW (d1, d2) = 1. (2.9)Viewing W as a two-dimensional infinite array of numbers indexed in ZÃZ,one can therefore say that W : Z2 â Z is a Riemann weight iff all its ârowsumsâ (2.8) and all its âcolumn sumsâ (2.9) equal one.At times it is convenient to write m using the âdownward shift opera-tors,â ti for i â [n], where ti is the operator on functions Zn â Z givenby(tif)(d) = f(dâ ei);one easily verifies that the ti commute with one another, and thatm = (1â t1) . . . (1â tn),(where 1 is the identity operator). In particular, it follows that if f = f(d)is independent of its i-th variable, then (1â ti)f = 0, and hence mf = 0. Inparticular mf = 0 if (1) f is a sum of functions, each of which is independentin some variable, and, in particular, (2) if f is a polynomial of degree at mostnâ 1. Hence deg(d) + C is a modular function for any n â¥ 1, and hence aRiemann function is, indeed, a generalized Riemann function.We now characterize modular functions in two different ways.Theorem 2.3.4. A function h : Zn â Z is modular iff it can be written asa sum of functions each of which depends on only nâ 1 of its n variables.212.4. Riemann-Roch Formulas and Self-DualityWe postpone its proof to Subsection 2.8 The following description ofmodular functions will be needed when we discuss what we call Riemann-Roch formulas.Theorem 2.3.5. If a â Z, n â N, and h is any integer-valued functiondefined on d â Zn with a â¤ deg(d) â¤ a + n â 1, then h has a uniqueextension to a modular function Zn â Z.We also postpone the proof of this theorem to Subsection 2.8.According to this theorem, if h1, h2 are two modular functions, then h1and h2 are equal whenever they are eventually equal (i.e., h1(d) = h2(d)for deg(d) sufficiently large), then h1 = h2. In particular, if f : Zn â Zis a generalized Riemann function, then the modular function h that iseventually equal to f is uniquely determined.2.4 Riemann-Roch Formulas and Self-DualityDefinition 2.4.1. Let f : Zn â Z be a generalized Riemann function, andh the modular function eventually equal to f . The K-dual of f , denotedfâ§K, refers to the function Zn â Z given byfâ§K(d) = f(Kâ d)â h(Kâ d). (2.10)We equivalently writef(d)â fâ§K(Kâ d) = h(d) (2.11)and refer to this equation as a generalized Riemann-Roch formula.In particular, if f is a Riemann function, then the formula readsf(d)â fâ§K(Kâ d) = deg(d) + C. (2.12)We now make some remarks about generalized Riemann-Roch formulas.222.4. Riemann-Roch Formulas and Self-DualityDefinition 2.4.2. If W : Zn â Z is any function and L â Zn, the L-dualweight of W , denoted W âL refers to the function given byW âL(d) = W (Lâ d).It is immediate that (W âL)âL = W .Theorem 2.4.3. Let f : Zn â Z be a generalized Riemann function, andK â Zn.1. Setting W = mf and L = K + 1 (where 1 = e[n] is the all 1âs vector),we have thatm(fâ§K)= W âL. (2.13)2. fâ§K is a generalized Riemann function, and a Riemann function if fis.3. (fâ§K)â§K = f .Definition 2.4.4. We say that a generalized Riemann function f : Zn â Zis self-dual if either of the equivalent conditions holds:1. for some K â Zn, fâ§K = f ;2. for some L â Zn, W âL = W .Let us remark on the uniqueness of K and L in the above definition:if W âL1 = WâL2, it follows that W is translation invariant by L1 â L2, andsimilarly if fâ§K1 = fâ§K2then f is translation invariant by K1 âK2. Hence ifT â Zn0 is the set of invariant translations of f , then it is the same for W ,and the K and L of self-dual Riemann functions in the definition above areunique up to an element of T .Example 2.4.5. Baker-Norine [6] showed that for a graph G = (V,E) onn-vertices with V = [n] rBN(G; d) satisfies the Riemann-Roch formularBN(G; d)â rBN(G; Kâ d) = deg(d) + 1â g,232.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphswhere g = |E| â |V |+ 1 and K = ei(degG(i)â 2). Since f = rBN,G â 1, theLHS above also equals f(d)â fâ§K(Kâ d), and hence f = fâ§K is self-dual.Example 2.4.6. Amini and Manjunath [3] give conditions for f as in (2.3)with N as in Example 2.2.7 to satisfy self-duality. The first is that allmaximal point of N have the same degree (gmin = gmax in [3]); the secondis more technical; they give a number of examples.2.5 The Weight of the Riemann-Roch Rank ofthe Complete Graph and Related GraphsThis subsection is not essential to the rest of the paper.The point of this subsection is to give a self-contained computation ofthe remarkably simple weight function of the Baker-Norine rank for thecomplete graph and related graphs. We remark that the use of sheaf theoryin [16, 22]âorganizes information in a useful way thatâafter additionalworkâleads to some interesting theorems. We believe that the same may besaid of the weight of Riemann functions and the models they help produce.Our proof uses many standard ideas in the graph Riemann-Roch litera-ture [3, 5, 6, 12], but also one rather ingenious idea of [12].2.5.1 Standard Facts about the Graph Riemann-Roch RankTo state and prove our main theorem most conveniently, let us recall somestandard facts used in studying the graph Riemann-Roch rank, used byBaker-Norine [6] and many subsequent papers. Recall the notation in Ex-ample 2.2.6.If f : Zn â Z is slowly growing and dâ²,d â Zn with dâ² â¤ d, then clearlyf(dâ²) â¥ f(d)â deg(dâ dâ²); (2.14)we say that f is maximally decreasing from d to dâ² if equality holds. It iseasy to see that3 if dâ²â² â¤ d â¤ d and f is slowly growing, then f is maximally3The above This is Lemma 5 of [12], but is used in most papers we have seen involving242.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphsdecreasing from d to dâ²â² iff it is so from both d to dâ² and dâ² to dâ²â².For example, consider any Riemann function of the form (2.3) where Nis a downset. Then if d â Zn, and dâ²â² â N is such thatâdâ dâ²â²â = mindâ²âNâdâ dâ²â,then f is maximally decreasing from d to dâ²â².2.5.2 A Generalization of a Fundamental Lemma of Coriand Le BorgneNext we give an elegant and rather ingenious observation of [12] (half ofthe proof of Proposition 10 there) that is the starting point of their (andour) study the Baker-Norine rank for the complete graph; we state theirobservation in slightly more general terms.Lemma 2.5.1. Fix n â N, and let Kn = (V,G) be the complete graphon vertex set V = [n], i.e., E consists of exactly one edge joining any twodistinct vertices. Consider the Baker-Norine rank rBN : Zn â Z on Kn. Ifa â¥ 0 and i â [n], thenai = 0 â rBN(a) = rBN(aâ ei) + 1. (2.15)Proof. Since a â¥ 0, rBN(a) â¥ 0, and hence rBN is maximally decreasing froma to aâ b for some b â¥ 0 with rBN(aâ b) = â1. In this case aj â bj â¤ â1for some j â [n] (or else rBN(a â b) â¥ 0), and hence bj â¥ aj + 1 â¥ 1 andrBN is maximally decreasing from a to aâ² = aâ bjej . But the vectoraâ²â² = aâ ajej â (bj â aj)eiis merely the vector aâ² followed by an exchange of the i-th and j-th coordi-nates (if i = j then aâ²â² = aâ²). Hence aâ²â²,aâ² have the same degree and samevalue of rBN. Sinceaâ²â² â¤ aâ ei â¤ athe Baker-Norine rank, e.g., [3, 5, 6].252.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphsand f is maximally decreasing from a to aâ²â², f is maximally decreasing froma to aâ ei as well, and hence (2.15) holds.Remark 2.5.2. If n,m â N, we use Kmn = (V,E) to denote the graphwith V = [n] and m edges between any two vertices (so K1n = Kn). ThenrBN,Kmn (d) is again a symmetric function of its variables (d1, . . . , dn) = d,and the same argument shows that for any b â Zâ¥0, a â¥ b1 and ai = bimplies that f(d) = f(d â ei) + 1. We believe it is possible to use thisobservation, specifically for b = m, to give an analog of Theorem 2.5.12below regarding Kmn .2.5.3 The First Coordinates for Pic, Dâapre`s Cori-LeBorgneLet us recall some more standard graph Riemann-Roch terminology, andthen give our first set of coordinates for the Picard group of a graph. Thesecoordinates are implicit in [12].We set Zni to be the elements of Zn of degree i, and setPici(G) = Zni /Image(âG).Then |Pic0(G)| equals (1/n) detâ²(âG), where detâ² denotes the product ofthe nonzero eigenvalues of âG (and Kirchoffâs theorem says that this is thenumber of unrooted spanning trees of G). For G = Kn it is a standard factthat this number of trees is nnâ2, i.e.,|Pic0(Kn)| = nnâ2. (2.16)Next we pick a convenient set of representatives for each class inZn/Image(âKn).Lemma 2.5.3. Fix n â N, and let Kn = (V,G) be the complete graphon vertex set V = [n], i.e., E consists of exactly one edge joining any twodistinct vertices. LetA = {a | a1, . . . , anâ2 â {0, . . . , nâ 1}, anâ1 = 0}. (2.17)262.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related GraphsThen for all d â Zn there exists a unique a â A with d â¼ a (i.e., d â a âImage(âKn)), where a is given by: for i â [nâ 2], ai = (di â dnâ1) mod n,i.e., ai is the element of {0, . . . , n â 1} congruent to di â dnâ1 modulo n,anâ1 = 0, and an = deg(d)â a1 â · · · â anâ2.Proof. Existence is shown in Algorithm at the end of Section 2.1 of [12]: iteasily follows from the fact that Image(âKn) contains both (1, . . . , 1, 1â n)and, for any i â [n], n(ei â en).To prove uniqueness, we first note thatA0 def= A â© Zn0 = {a â A | deg(a) = 0}has size nnâ2, since any a1, . . . , anâ2 â {0, . . . , n â 1} determine uniqueanâ1, an, namelyanâ1 = 0, an = âa1 â · · · â anâ2for which a = (a1, . . . , an) lies in A0. So if uniqueness fails, some a,aâ² â Awould be equivalent, which would imply |Pic0(Kn)| < nnâ2, contradicting(2.16).Notation 2.5.4. For any n â N and i â Z, we use Adeg i to denote the setAdeg i def= A â© Zndeg i = {a â A | deg(a) = i}.Note thata â Adeg i â an = iâ a1 â · · · â anâ2and hencea â Adeg i â(an â¥ 0 ââ a1 + · · Â·+ anâ2 â¤ i)(2.18)a â Adeg i â(an = 0 ââ a1 + · · Â·+ anâ2 = i)(2.19)272.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphs2.5.4 An Intermediate Weight Calculation: (1â tnâ1)rBNThe weight, W , of rBN or of 1 + rBN of any graph on n vertices is given byW = (1â t1) . . . (1â tn)rBN.After numerically (i.e., via computer experiment) noticing the simple pat-tern to W , it was unclear to us how one could prove this. After someexperimentation, we noticed a simple pattern of (1â tnâ1)rBN, and then of(1â tnâ1)(1â tn)rBN.These are both intermediate steps to computing W above. The point ofthe following subsections is to prove the numerically observed pattern for(1â tnâ1)rBN.Theorem 2.5.5. Fix n â N, and let Kn = (V,G) be the complete graphon vertex set V = [n], i.e., E consists of exactly one edge joining any twodistinct vertices. Consider the Baker-Norine rank rBN : Zn â Z on Kn. Ifa â A â© Zni , thenan â¥ 0 ââ rBN(a) = rBN(aâ enâ1) + 1. (2.20)We remark that (2.20) generalizes Proposition 10 of [12].Proof. Combining (2.21) with Lemma 2.5.1 we geta1 + · · Â·+ anâ2 â¤ i â rBN(a) = rBN(aâ ei) + 1 (2.21)We now prove the reverse implication, essentially by a sort of counting thatshows that there is âno other roomâ for rBN(a)ârBN(aâei) to be 1 otherwise,given that we know the offset of 1 + rBN,Kn .So letMi =â£â£{a â A â© Zni | rBN(a) = rBN(aâ enâ1) + 1}â£â£282.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphsand letNi =â£â£{a â A â© Zni | a1 + · · Â·+ anâ2 â¤ i}â£â£Then (2.21) implies Mi â¥ Ni, and (2.20) holds provided that we can showMi = Ni for all i. Of course, Mi = Ni = 0 for i â¤ â1; also, for i â¥ n(nâ 2)and a â A we havea1 + · · Â·+ anâ2 â¤ n(nâ 2) â¤ i,and hence for such i we have Ni = |Pici | = nnâ2, and hence Mi = nnâ2 aswell.Let us take a large ` â Z and consider N0 + · · · + N`: for each a â Awith deg(a) â¥ ` for large `, we haveâ`i=0(rBN(aâienâ1)ârBN(aâ(iâ1)enâ1))= rBN(a)ârBN(aâenâ1`) = deg(a)âg+1.Hence from the definition of the Mi, for ` large we haveM0 + . . .+M` = nnâ2(`â g + 1).Next consider N0 + · · Â·+N` for ` large: let us prove that for all i â Z wehave Ni +N(nâ2)(nâ1)âiâ1 = nnâ2. Consider the bijection {0, . . . , nâ 1}nâ2to itself taking (a1, . . . , anâ2) to (b1, . . . , bnâ2) = (nâ1âa1, . . . , nâ1âanâ2):we have a1+Â· · Â·+anâ2 is either â¤ i or â¥ i+1 iff b1+Â· · Â·+bnâ2 is, respectively,â¤ (nâ 1)(nâ 2)â 1 or â¥ (nâ 1)(nâ 2). Hence for ` â¥ (nâ 1)(nâ 2)â 1we haveN0+. . .+N` = nnâ2((nâ 1)(nâ 2)2+ `â (nâ 1)(nâ 2))= nnâ2(`âg+1),where we used the fact g = (nâ1)(nâ2)2 â n+ 1 for Kn. Hence,N0 + . . .+N` = nnâ2(`â g + 1) = M0 + · · Â·+M`for ` large. But since Ni â¥ Mi for all i, we must have Ni = Mi for all292.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphs0 â¤ i â¤ `; hence Ni = Mi for all i.2.5.5 The Second Coordinates for PicTo take our computation of (1 â tnâ1)rBN and multiply it by (1 â tn), andthen by (1 â t1) . . . (1 â tnâ2), we use a new set of coordinates. We warnthe reader that these second coordinates turn out to represent Pic as be asemi-direct productPic = (Z/nZ)nâ2 n Z, (2.22)but not a direct product. Because we are working with a semidirect product,the calculations require a little extra care.Notation 2.5.6. For any n â N and i â Z, we use1. B to denote the set {0, . . . , nâ 1}nâ2; and2. for any b = {0, . . . , nâ 1} â B and i â Z, we use ãb, iã to denoteãb, iã = (b1, . . . , bnâ2, 0, iâ b1 â · · · â bnâ2) â Ai. (2.23)Hence each element d â Zn is equivalent to a unique element of the formãb, iã with i = deg(d). It follows that for fixed i, the mapB Ã {i} â Aiis injective. Since B is the same size as each Ai for fixed i, namely ofsize nnâ2, it follows that each element of Pici for each fixed i has a uniquerepresentative of the form ãb, iã â BÃZ, which we call the second coordinatesor ãb, iã-coordinates of each element of Pici. Varying i, the set B Ã Z is aset of coset representatives of Zn modulo the image of the Laplacian of thecomplete graph, i.e., a set of coset representatives for Pic.Let us now describe some practical aspects of these second coordinates,and explain why the group law inherited from Pic (or, equivalently, fromZn) turns the second coordinates into a semidirect product (2.22).302.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphs2.5.6 The Second Coordinates: Practical AspectsIn this subsection we describe the important, practical aspects of the secondcoordinates defined above.Proposition 2.5.7. Let n â N with n â¥ 3, and let â¼ denoted congruencemodulo the image of the Laplacian of the complete graph on n vertices. Letd â Zn with dnâ1 = 0. If (b, i) â B Ã Z is the unique pair such thatd â¼ ãb, iã, then bj = dj mod n for j = 1, . . . , nâ 2, bnâ1 = 0, andi = (b1 â d1) + · · Â·+ (bnâ2 â dnâ2) + deg(d).Of course, bnâ1 also equals dnâ1 mod n in the proposition above. Thereason this proposition is useful to us is that if we start with a vector writtenin second coordinates,ãb, iã = (b1, . . . , bnâ2, 0, iâ b1 â · · · â bnâ2),and we only apply differencing operators tj with j â¤ nâ 2, then all vectorsinvolved have a vanishing (nâ1)-th coordinate, and we may apply the aboveproposition. Note that if dnâ1 6= 0, then we can writed â¼ dâdnâ1(1, 1, . . . , 1, 1ân) =(d1âdnâ1, . . . , dnâ2âdnâ1, 0, dnâ(1ân)dnâ1)and the expression on the right-hand-side has vanishing (nâ1)-st coordinate;then we can apply the above proposition to determine the unique ãb, iã towhich d is linearly equivalent.We also remark that in the above proposition, i and deg(d) are alwayscongruent modulo n.Example 2.5.8. Applying the above methods, we see thate1 â¼ ãe1, 1ã, . . . , enâ2 â¼ ãenâ2, 1ã, enâ1 â¼ ã(nâ 1)1, 1ã, en â¼ ã0, 1ã.Now let us give some examples of how addition and subtraction in thegroup law of Pic, inherited from that on Zn, works out in the second coor-312.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphsdinates ãb, iã.Example 2.5.9. It is helpful to see how addition in Pic (or Zn) gives riseto an addition law in B Ã Z in the above coordinates. Let ãb, iã, ãbâ², iâ²ã betwo elements of B Ã Z. Thenãb, iã+ ãbâ², iâ²ã = (b1 + bâ²1, · · · , bnâ2 + bâ²nâ2, 0, i+ iâ²)which lies in B Ã Z iff bj + bâ²j â¤ nâ 1 for all j = 1, . . . , nâ 2. If bj + bâ²j â¥ nfor some j, then we haveãb, iã+ ãbâ², iâ²ãis linearly equivalent toãbâ²â², iâ²â²ã,wherebâ²â²j = (bj + bâ²j) mod n,andiâ²â² = i+ iâ² + nâ£â£â£{j | bj + bâ²j â¥ n}â£â£â£.Hence bâ²â² is the same as b + bâ² if we identify B with (Z/nZ)nâ2, but those jsuch that bj+bâ²j â¥ n require us to adjust the iâ²â² accordingly. Hence endowingB Ã Z with its addition law we get an group homomorphismB Ã Zâ (Z/nZ)nâ2,so that the addition law in B Ã Z gives it the structure of a semidirectproduct.Example 2.5.10. For j â [n â 2] and b = (b1, ..., bnâ2) in Zn coordinateswe haveãb, iãâãej , 1ã =ï£±ï£²ï£³(b1, ..., bjâ1, bj â 1, bj+1, ..., bnâ2, 0, iâ 1â b1 â ...â bnâ2)if bj > 0, and(b1, ..., bjâ1, nâ 1, bj+1, ..., bnâ2, 0, iâ nâ 1â b1 â ...â bnâ2)if bj = 0.322.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related GraphsIt follows thatãb, iã â ãej , 1ãï£±ï£²ï£³= ãbâ ej , iâ 1ã if bj > 0, andâ¼ ãb + (nâ 1)ej , iâ 1ã if bj = 0(and we note that in the second case we do not have an =, since ãb, iãâãej , 1ãhas a â1 in its j-th component).When considering general J â [nâ 2] and corresponding eJ =âjâJ ej ,we arrive at a similar formula for ãb, iãâãeJ , |J |ã by iterating the subtractionof the vectors ãej , 1ã above.To determine rBN,Kn or related functions such as m(rBN,Kn), it sufficesto determine their values on each element of Pic, or equivalently on eachelement of ãb, iã â B Ã Z.The following general proposition will clarify aspects of the proof ofTheorem 2.5.12.Proposition 2.5.11. Let f : Zn â Z be any function that is invariant undertranslation by the image of the Laplacian of the complete graph. Say thatfor all (b, i) â B ÃZ, f(ãb, iã) = g(b1 + · · Â·+ bnâ2 â i) for some function g,i.e., f depends only on b1 + · · Â·+ bnâ2 â i. Then1. if bj > 0 for some j â [nâ 2], then ((1â tj)f)(ãb, iã) = 0;2. if bj > 0 for some j â [n â 2], and if J â [n â 2] with j /â J , thensettingtJ =âjâ²âJtjâ² ,we have ((1â tj)tJf)(ãb, iã) = 0;3. if b 6= 0, i.e., if bj > 0 for some j â [nâ 2],((1â t1) . . . (1â tnâ2)f)(ãb, iã) = 0; (2.24)and332.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphs4. (in the remaining case, b = 0)((1â t1) . . . (1â tnâ2)f)(ã0, iã) =nâ2âk=0(â1)k(nâ 2k)g(iâ kn). (2.25)The proof below shows that claims (1) and (2) above hold, more gener-ally, wheneverf(ãb, iã) = g(b1, . . . , bjâ1, bj â i, bj+1, . . . , bnâ2)for some g, i.e., f is an arbitrary function, except that its dependence on bjand i is only on bj â i and the rest of the bjâ² .Proof. Proof of (1): if bj > 0, thenãb, iã â ej = ãbâ ej , iâ 1ãand hence((1â tj)f)(ãb, iã) = f(ãb, iã)â f(ãbâ ej , iâ 1ã)= g((b1 + · · Â·+ bnâ2)â i)â g((b1 + · · Â·+ bnâ2 â 1)â (iâ 1)) = 0.Proof of (2): if J â² is the set of j â J with bj = 0, we have(tJf)(ãb, iã) = f(ãbâeJ +neJ â² , iâ|J |) = g(b1 + · · Â·+bnâ2â i+n|J â²|â |J |),and(t{J,j}f)(ãb, iã) = f(ãbâeJ+neJ â²âej , iâ|J |â1) = g(b1+Â· · Â·+bnâ2âi+n|J â²|â|J |),and (2) follows.Proof of (3): we have(1â t1) . . . (1â tnâ2) =âJâ[nâ2]{j}(â1)|J |(1â tj)tJ ,342.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphsso (2) implies (3).Proof of (4): for any J â [nâ 2] we havef(ã0, iã â eJ) = f(ã(nâ 1)eJ , iâ |J |ã) = g(n|J | â i),and hence (4) follows from this equation and the expansion(1â t1) . . . (1â tnâ2) =âJâ[nâ2](â1)|J |tJ .2.5.7 Computation of (1â tn)(1â tnâ1)rBN and, finally, of WTheorem 2.5.12. Fix n â N, and let Kn = (V,G) be the complete graphon vertex set V = [n], i.e., E consists of exactly one edge joining any twodistinct vertices. Consider the Baker-Norine rank rBN : Zn â Z on Kn.1. If a â A â© Zni , then(1â tn)(1â tnâ1)rBN,Kn(a) ={1 if a1 + · · Â·+ anâ2 = i, and0 otherwise.(2.26)2. For all b â B and i â Z,(1â tn)(1â tnâ1)rBN,Kn(ãb, iã) ={1 if b1 + · · Â·+ bnâ2 = i, and0 otherwise.(2.27)3. The weight, W = m(rBN,Kn), is given byWguess(ãaâ², iã) ={(â1)`(nâ2` ) if aâ² = 0 and i = n` for some ` = 0, . . . , nâ 20 otherwise.(2.28)Proof. (1): By and (2.20) we have that for a â A â© Zni ,a1 + · · Â·+ anâ2 â¤ i ââ rBN(a) = rBN(aâ enâ1) + 1,352.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphsand clearlyrBN(a) = rBN(aâ enâ1) + 1 ââ (1â tnâ1)rBN,Kn(a) = 1;it follows that:1. if a1 + · · Â·+ anâ2 â¤ iâ 1, then(1â tnâ1)rBN,Kn(a) = (1â tnâ1)rBN,Kn(aâ en) = 1,and hence(1â tn)(1â tnâ1)rBN,Kn(a) = 1â 1 = 0;2. if a1 + · · Â·+ anâ2 â¥ i+ 1, then(1â tnâ1)rBN,Kn(a) = (1â tnâ1)rBN,Kn(aâ en) = 0,and hence(1â tn)(1â tnâ1)rBN,Kn(a) = 0â 0 = 0;and3. if a1 + · · Â·+ anâ2 = i, then(1â tnâ1)rBN,Kn(a) = 1, (1â tnâ1)rBN,Kn(aâ en) = 0,and hence(1â tn)(1â tnâ1)rBN,Kn(a) = 1â 0 = 1.(2): is an immediate consequence of (1).(3): When going through this proof it may be helpful to consider theexample n = 4, and to consider what (2.27) means in terms of the ãb, iãcoordinates, namely that b1 + b2 = i; see Figure 2.1.362.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related Graphsi = 0 i = 1 i = 20 1 2 3ï£«ï£¬ï£­ï£¶ï£·ï£¸0 1 0 0 01 0 0 0 02 0 0 0 03 0 0 0 00 1 2 3ï£«ï£¬ï£­ï£¶ï£·ï£¸0 0 1 0 01 1 0 0 02 0 0 0 03 0 0 0 00 1 2 3ï£«ï£¬ï£­ï£¶ï£·ï£¸0 0 0 1 01 0 1 0 02 1 0 0 03 0 0 0 0i = 3 i = 4 i = 50 1 2 3ï£«ï£¬ï£­ï£¶ï£·ï£¸0 0 0 0 11 0 0 1 02 0 1 0 03 1 0 0 00 1 2 3ï£«ï£¬ï£­ï£¶ï£·ï£¸0 0 0 0 01 0 0 0 12 0 0 1 03 0 1 0 00 1 2 3ï£«ï£¬ï£­ï£¶ï£·ï£¸0 0 0 0 01 0 0 0 02 0 0 0 13 0 0 1 0i = 60 1 2 3ï£«ï£¬ï£­ï£¶ï£·ï£¸0 0 0 0 01 0 0 0 02 0 0 0 03 0 0 0 1Figure 2.1: The example n = 4 in ãb, iã coordinates, b = (b1, b2) â{0, 1, 2, 3}2.372.5. The Weight of the Riemann-Roch Rank of the Complete Graph and Related GraphsIn terms of Proposition 2.5.11, claim (2) shows that for all b â B andi â Z, settingf(ãb, iã) = ((1â tnâ1)(1â tn)rBN)(ãb, iã)and extending f to be invariant under â¼, we have that f is of the formg(b1 + · · Â·+ bnâ2 â i),where g(0) = 1 and elsewhere g vanishes. SinceW = (1â t1)(1â tnâ2)f,we may apply Proposition 2.5.11 and conclude that if b â B is nonzero, then(2.24) implies thatW (ãb, iã) = 0,and if b = 0, thenW (ã0, iã) =nâ2âk=0(â1)k(nâ 2k)g(nk â i).Hence W (ã0, iã) = 0 unless i is of the form nk, with 0 â¤ k â¤ nâ 2, in whichcaseW (ã0, nkã) = (â1)k(nâ 2k).We get the following variant of formulas in [12].Corollary 2.5.13. Let n â Z, and A be as in (2.17). For any a â A wehaverBN,Kn(a) = â1+â£â£â£â£{j = 0, . . . ,deg(a) | nâ2âi=1((ai+j) mod n) â¤ deg(a)âj}â£â£â£â£.(2.29)As in [12], (1) for any d â Zn, we can find an equivalent element to d that382.6. Perfect Matchings and r-fold Matchingslies inA by O(n) operations, and (2) for any a â A, after sorting a1, . . . , anâ2in non-decreasing order, one can evaluate (2.29) in O(n) operations, sincethe function of jg(j) =nâ2âi=1((ai + j) mod n)has g(j + n) = g(j) for all j, andg(j) = â(nâ 2â ij)n+nâ2âi=1ai,where ij is unique integer with aij â¥ nâ j > aijâ1.Another important consequence of Theorem 2.5.12 is that for any d âZn, and any distinct i, j â [n] we have((1â ti)(1â tj)W)(d) â¥ 0.This will play a role when we model f = 1 + rBN,Kn by k-diagrams inSection 5.2.6 Perfect Matchings and r-fold MatchingsThe following theorems will be needed in building our models for Riemannfunctions with n = 2.Definition 2.6.1. Let W be initially and eventually zero. For i â Z, thei-th row sum of W (respectively, column sum) isâjâZW (i, j) (respectively,âjâZW (j, i)). For any r â N, we say that W is an r-fold matching all valuesof W are non-negative and all the row sums and all the column sums of Wequal r; we also call a 1-fold matching a perfect matching.If W is a perfect matching, then clearly there is a unique pi : Zâ Z suchthatW (i, j) ={1 if j = pi(i), and0 otherwise;(2.30)392.6. Perfect Matchings and r-fold Matchingswe easily see that pi is a bijection and that is bounded in the sense thatpi(m)+m is bounded over all m â Z; conversely, if pi : Zâ Z is any boundedbijection, clearly W as in (2.30) gives a perfect matching.Definition 2.6.2. If W is a perfect matching, we refer to the pi satisfying(2.30) as the bijection associated to W .It is conceptually useful to note the following theorem, which is a variantof Hallâs theorem. As pointed out by Robert Cori, the following theorem wasoriginally proven by Tutte [33] and uses a similar compactness argument.Theorem 2.6.3. Let W be an s-fold matching. Then there exist perfectmatchings W1, . . . ,Ws whose sum is W . Furthermore, if W is r-periodic forsome r â N, then we may choose W1, . . . ,Ws to be r-periodic.Our proof is based on a general principle that Hallâs marriage theoremholds on a bipartite graph with countably many vertices on each side, pro-vided that each vertex has finitely many neighbours (namely, in our case, atmost r neighbours).Proof. It suffices to show that there is a perfect matching W1 such thatW1(i, j) â¤ W (i, j) for all i, j, and then to prove the above theorem byinduction on s.To find W1 in the case where W is p-periodic, we can simply apply toHallâs theorem as follows: let G = (V,E) be the bipartite graph, whereV = VL q VR and all edges run from left to right, where VL = VR ={0, 1, . . . , pâ 1}, and the number of edges running from i â VL to j â VR isjuste(i, j) =âmâ¡j mod pW (i, j).Then G is a finite bipartite graph that is r-regular on both sides, i.e., eachvertex is incident upon exactly r edges. It then follows that if V â² â VL, andÎ(V â²) denotes the set of neighbours of VL, i.e., of vertices (in VR) adjacentto some vertex of V â², then |Î(V â²)| â¥ |V â²| (since V â² is incident upon r|V â²|edges, whose right endpoints span at least |V â²| vertices). Similarly if V â² â402.6. Perfect Matchings and r-fold MatchingsVR, then also |Î(V â²)| â¥ |V â²|. Then Hallâs theorem implies that G has aperfect matching, i.e., a subgraph Gâ² = (V,Eâ²) where each vertex is adjacentto exactly one vertex. This gives us a bijection pi : VL â VR such thate(i, pi(i)) â¥ 1. For each i choose a j = pi1(i) such that j â¡ pi(i) mod p suchthat W (i, j) â¥ 1. Now extend pi1(i) : {0, . . . , pâ1} â Z as a function Zâ Zby setting for all m â Z and i â {0, . . . , pâ 1}pii(i+ rm) = pi(i)â rm.It follows that pi is a bijection, and that its associated weight, W1, satisfiesW (i, j) â¥ 1 whenever W1(i, j) = 1. Hence W1 â¤W and we have our desiredW1.To find W1 when W is not periodic, we modify the above, which es-sentially gives an infinite version of Hallâs theorem: namely, consider thebipartite graph, G = (V,E), V = VL q VR with VL = VR = Z, and wherethe number of edges from i â VL to j â VR is W (i, j). Let V be enumeratedas v1, v2, . . . . Again, |Î(V â²)| â¥ |V â²| since G is r-regular on both sides, andhence the augmenting path technique to prove Hallâs theorem shows thatfor any m there is a matching Gm = (Vm, Em) â G, meaning that eachvertex of Vm is adjacent via Em to exactly one other vertex of Vm, with theproperty that {v1, . . . , vm} â Vm. Now we use G1, G2, . . . to build a perfectmatching Gâ² â G.Namely, since v1 â Vm for m â¥ 2, and v1 is adjacent to at most r-verticesin G, there is an (infinite) subsequence of G1, G2, . . . in which v1 is adjacentto some fixed vertex of V ; next we choose a further infinite subsequencein which v2 is adjacent to some fixed vertex of V ; we similarly apply thisprocess to v3, v4, . . .. This gives a fixed matching defined on v1, v2, . . ., andtherefore on all of V . Hence we get a bijection pi1 : Zâ Z such that for alli â Z, W (i, pi1(i)) â¥ 1. Hence we take W to be the weight associated topi1.412.7. Writing n = 2 Riemann Weights as Perfect Matchings2.7 Writing n = 2 Riemann Weights as PerfectMatchingsRecall that a Riemann weight Z2 â Z is the weight of a Riemann functionZ2 â Z, and that W : Z2 â Z is a Riemann weight iff it is initially andeventually zero and satisfies for all x â Z,âyâZW (x, y) =âyâZW (y, x) = 1, (2.31)In this subsection we give an analogue of Theorem 2.6.3 when we donot assume that the weight W attains only non-negative values. Withoutsuch an assumption, it is far more subtle to write W in terms of perfectmatchings.Example 2.7.1. If W1, . . . ,Ws, WË1, . . . , WËsâ1 are perfect matchings, thenW = W1 + · · Â·+Ws â WË1 â · · · â WËsâ1is a Riemann weight. Consider the case where W1, . . . ,Ws, WË1, . . . , WËsâ1have with disjoint supports (e.g., each equals 0 unless the value of x â y issome constant, and all weights have a different such constants): in this case,each row sum and column sum of |W (x, y)| equals 2sâ 1.Hence when we do not assume that a Riemann weight, W , has non-negative values, |W | can have arbitrarily large row and column sums, andhence to write W as a difference of sums of perfect matchings can be farmore complex.The following lemma explains our interest in perfect matchings and isthe basis of our models for any Riemann function Z2 â Z.Lemma 2.7.2. Let W : Z2 â Z be a Riemann weight such that for somea, b â Z, W (d) 6= 0 implies that a â¤ deg(d) â¤ b. Then if |W | is boundedabove by a constant C, then for some k â N we may writeW = (W1 +W2 + · · Â·+Wk)â (WË1 + · · · â WËkâ1) (2.32)422.7. Writing n = 2 Riemann Weights as Perfect Matchingswhere W1, . . . ,Wk and WË1, . . . , WËkâ1 are perfect matchings Z2 â Z of de-grees between a and b, i.e., Wi(d) 6= 0 implies a â¤ deg(d) â¤ b.Lemma 2.7.3. If in Lemma 2.7.2 we make the additional assumption thatW is r-periodic, then the Wi and WËi in (2.32) can be chosen with the addi-tional constraint that each Wi and WËi are r-periodic.A similar lemma holds whenever W is initially and eventually zero, andall row and column sums of W equal a fixed integer.The rest of this subsection is devoted to proving the above lemmas, andis independent of the rest of this article.To prove this, we will show that for every Riemann weightW , there existsperfect matchings Wâ²i and Wâj such that the difference of perfect matchingsW + (Wâ²1 + · · Â·+Wâ²k)â (W â1 + · · Â·+W âkâ1)is supported in degrees a and a + 1. Assuming this, the result follows asany Riemann weight function supported in two degrees is itself a differenceof perfect matchings.Lemma 2.7.4. If W is Riemann Weight supported in degrees a and a + 1then W may be written as a difference of perfect matchings.Proof. Picking any d of degree a, if W (d) = c then we must have W (d +(1, 0)) = âc+1 as for a Riemann weight the rows sum to 1. As the columnsalso sum to 1 we have W (d + (1, 0) + (0,â1)) + W (d + (1,â1)) = âc + 1.Iterating, we see that the weight is c at all divisors of degree a and the weightis âc + 1 at all divisors of degree a + 1. If we define Pb to be the perfectmatching such that Pb(d) = 1 if deg(d) = b and Pb(d) = 0 otherwise, we maydecompose W as the difference of perfect matchings c Â·Paâ(câ1) Â·Pa+1.The following completes the proof.Lemma 2.7.5. Suppose W is a Riemann weight supported in degrees be-tween a and a + j with j â¥ 2. Then there exists perfect matchings W â²i andW âj such that W + (Wâ²1 + · · · + Wâ²k) â (W â1 + · · · + W âkâ1) is supported indegrees between a+ 1 and a+ j.432.7. Writing n = 2 Riemann Weights as Perfect MatchingsProof. It will be enough to show that there exists perfect matchings suchthat Wâ²i and Wâj such thatW + (Wâ²1 + · · Â·+Wâ²k)â (W â1 + · · Â·+W âkâ1)is supported in degrees between a and a + j and furthermore such that|W (d)| â¤ Câ 1 for deg((d)) = a as then applying the process at most Câ 1more times gives us a difference of perfect matchings supported in degreesbetween a+ 1 and a+ j. Given W , define Wa,even asWa,even(d1, d2) =ï£±ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£²ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£³sgn(W (d1, d2)) d1 + d2 = a and d1 is evenâsgn(W (d1 â 1, d2)) d1 + d2 = a+ 1 and d1 is oddâsgn(W (d1, d2 â 1)) d1 + d2 = a+ 1 and d1 is evensgn(W (d1 â 1, d2 â 1)) d1 + d2 = a+ 2 and d1 is odd0 otherwise,where sgn denotes the sign function. The support of Wa,even in Z2 is con-tained in infinitely many 2Ã 2 squares, each square of which has its bottomleft corner at a divisor d(d1, d2) of degree a with d1 even. If W (d1, d2) > 0with d1 + d2 = a and d1 is even then the square with bottom left cor-ner at (d1, d2) will have valuesâ1 11 â1 , if W (d1, d2) < 0 then1 â1â1 1 and ifW (d1, d2) = 0 then 0 00 0 . While Wa,even is not itself a perfect matching,we may decompose it a a difference of two perfect matchings Wa,even,P andWa,even,N where:Wa,even,P (d1, d2) =ï£±ï£²ï£³1 if Wa,even(d1, d2) = 1 or Wa,even(d1, d2) = 0 and d1 + d2 = a+ 10 otherwiseandWa,even,N (d1, d2) =ï£±ï£²ï£³1 if Wa,even(d1, d2) = â1 or Wa,even(d1, d2) = 0 and d1 + d2 = a+ 10 otherwise,442.8. Fundamental Domains and the Proofs of Theorems 2.3.4 and 2.3.5so that Wa,even = Wa,even,P âWa,even,N . We similarly define Wa,odd asWa,odd(d1, d2) =ï£±ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£²ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£³sgn(W (d1, d2)) d1 + d2 = a and d1 is oddâsgn(W (d1 â 1, d2)) d1 + d2 = a+ 1 and d1 is evenâsgn(W (d1, d2 â 1)) d1 + d2 = a+ 1 and d1 is oddsgn(W (d1 â 1, d2 â 1)) d1 + d2 = a+ 2 and d1 is even0 otherwisewith Wa,odd,P and Wa,odd,N defined analogously to Wa,even,P and Wa,even,N .By construction,W â (Wa,odd,P +Wa,even,N âWa,odd,N âWa,even,P )will be supported in degrees between a and a + j and we furthermore willhave itâs value bounded by C â 1 at divisors d of degree a as desired.For r-periodic weights, modifying the construction above slightly by re-placing Wa,even and Wa,odd with Wa,0,Wa,1, ...,Wa,râ1 defined asWa,j(d1, d2) =ï£±ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£²ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£´ï£³sgn(W (d1, d2)) d1 + d2 = a and d1 â¡ j (mod r)âsgn(W (d1 â 1, d2)) d1 + d2 = a+ 1 and d1 â¡ j + 1 (mod r)âsgn(W (d1, d2 â 1)) d1 + d2 = a+ 1 and d1 â¡ j (mod r)sgn(W (d1 â 1, d2 â 1)) d1 + d2 = a+ 2 and d1 â¡ j + 1 (mod r)0 otherwiseproves 2.7.3.2.8 Fundamental Domains and the Proofs ofTheorems 2.3.4 and 2.3.5[The following subsection can be omitted by the reader interested only inRiemann functions and not generalized Riemann functions.]452.8. Fundamental Domains and the Proofs of Theorems 2.3.4 and 2.3.5In this subsection we prove the theorems in Subsection 2.3 using a studyof what we call fundamental modular domains.2.8.1 Definition of Fundamental Modular DomainsDefinition 2.8.1. Let D â Zn. We call D a fundamental modular do-main (respectively subfundamental, superfundamental) if for every functionf : D â Z there exists a unique (respectively, at least one and at most one)modular function h : Zn â Z such that f = h on D.We remark that our terminology results from the following almost im-mediate facts: a subset of a subfundamental modular domain is subfunda-mental, and a strict subset of a fundamental domain is not fundamental;similarly for superfundamental domains.2.8.2 Proof of Theorem 2.3.4 Without Reference toCubismsTo prove Theorem 2.3.4 requires a the relatively easy Lemma 2.8.2 and themore subtle Theorem 2.8.3. We will give a second proof of Theorem 2.8.3in terms of what we will call cubisms, a notion that requires additionaldefinitions but seems easier to illustrate in figures (e.g., Figure 2.2).Lemma 2.8.2. Let Dncoord â Zn given byDncoord = {d |di = 0 for at least one i â [n]}. (2.33)Then every function f : Dcoord â Z can be written asnâi=1hiwhere hi : Zn â Z is a function hi(d) that is independent of the i-th vari-able. Moreover, such a function has at least one extension, g, to a modularfunction Zn â Z.Let us make some remarks on the proof below.462.8. Fundamental Domains and the Proofs of Theorems 2.3.4 and 2.3.5The second claim in the lemma, regarding the existence of g, is immediatefrom any representation asâi hi above. However this is a crucial observationto our proof of Theorem 2.8.3, so we include this in the statement of thelemma.Next consider the first claim in the lemma. The case n = 1 is immediate.The proof is essentially the inclusion-exclusion formula, perhaps in disguise:for example, for n = 2, if we considerg(d1, d2) = f(d1, 0) + f(0, d2)â f(0, 0),then we easily that the right-hand-side is well-defined for all (d1, d2) andis of the desired formâi hi; on the other hand, we see by a case analysisthat g(x) = f(x) whenever at least of d1, d2 is zero; indeed, by symmetry itsuffices to check this in case d2 = 0, whereupong(d1, 0) = f(d1, 0) + f(0, 0)â f(0, 0) = f(d1, 0).Similarly for n = 3, andg(d1, d2, d3) = f(d1, d2, 0)+f(d1, 0, d3)+f(0, d2, d3)âf(d1, 0, 0)âf(0, d2, 0)âf(0, 0, d3)+f(0, 0, 0),where if d3 = 0 we get g(d1, d2, 0) = f(d1, d2, 0).Formalizing the argument for general n seems a bit more involved, but isreally just a statement about a Boolean hypercube endowed with the usualinclusion-exclusion sign pattern. Here is a formal proof.Proof. For d â Zn and I â [n], introduce the notationdI =âi/âIdiei,so that if I = i, dI has component 0 in position i and di elsewhere. Considerthe function g : Zn â Z given byg(d) =âIâ[n], I 6=â f(dI)(â1)|I|+1 (2.34)472.8. Fundamental Domains and the Proofs of Theorems 2.3.4 and 2.3.5(which makes sense, since dI â Dncoord whenever I 6= â ). We claim thatg = f when restricted to d â Dncoord; by symmetry it suffices to check thecase dn = 0, whereupon each term except for f(d1, . . . , dnâ1, 0) is cancelledwith another, namely the term f(dI) for each I with n â I with the termcorresponding to I n. The only term that remains is I = {n}, since I = â is missing from the sum in (2.34)Of course, the right-hand-side (2.34) is of the desired formâi hi as inthe statement of the lemma.Theorem 2.8.3. The subset Dncoord of (2.33) is a fundamental modulardomain.We alert the reader that the proof we give of this theorem is roughlyequivalent to our second proof of this theorem based on the more systematicnotion of cubisms below (which require a few extra definitions).Proof. Let us prove that Dncoord is superfundamental. Let f : Dncoord â Z bea function. Let us show that if h is a modular function such that f = h onDncoord, then h is unique. By symmetry it suffices to show that the values ofh on the setNn = {d | di > 0 for all i â [n]}are uniquely determined. But if h is modular, thenh(d) =âIâ[n], I 6=â (â1)|I|+1h(dâ eI),which determines h(d) for d â Nn by induction on deg(d).Now let us prove that Dncoord is subfundamental. If h : Dncoord â Z is anarbitrary function, according to Lemma 2.8.2, the function g in (2.34) agreeswith h on Dncoord, and clearly g is modular. Hence Dncoord is subfundamental.Hence Dncoord is subfundamental and superfundamental, and hence fun-damental.482.8. Fundamental Domains and the Proofs of Theorems 2.3.4 and 2.3.5Proof of Theorem 2.3.4. One direction is immediate; it suffices to show thatany modular function, h, can be written as a such a sum. Since Dncoordis a fundamental modular domain, the restriction of h to Dncoord uniquelydetermines h. But we have that g as in (2.34) agrees with h on Dncoord, andhence h = g on all of Zn, and g is the sum of functions, each of which isindependent of at least one variable.2.8.3 Cubmisms: Motivation, Definition, and Implication ofDomain FundamentalityThe above proof that Dncoord is superfundamental showed that by ârankingâthe elements d â Nn not on the coordinate axes asrank(d) = d1 + · · Â·+ dn â (nâ 1),one sees by induction on rank(d) that there is at most one way of extendinga function on Dncoord to Dncoord âª Nn and maintaining modularity. With alittle more care, this idea can be used to prove that many other subsets ofZn are fundamental domains.Definition 2.8.4. For d â Zn, the d-cube refers to the setCube(d) = {dâ² â Zn | dâ 1 â¤ dâ² â¤ d}.If D â Zn, we say that function r : Zn â N is a cubism of D if, settingDm = D âªâr(d)â¤mCube(d) (2.35)for m â Zâ¥0 (hence D0 = D), we have1. if r(d) = r(dâ²) = m, thenCube(d) â© Cube(dâ²) â Dmâ1,and492.8. Fundamental Domains and the Proofs of Theorems 2.3.4 and 2.3.52. for all d â Zn with r(d) = m we haveâ£â£Cube(d) Dmâ1â£â£ = 1 (2.36)Example 2.8.5. In Figure 2.2 we illustrate an example of a cubism of D,with D = Dcoord as above, suggested by the above proof of Theorem 2.8.3and n = 2 (so the n-cubes are really squares).Proposition 2.8.6. If D â Zn has a cubism, then D is fundamental.Proof. By induction on m â N we see that any function h : D â Z has aunique extension to a function, gm : Dm â Z such that (mgm)(d) = 0 forall d with r(d) â¤ m. Since the Dm exhaust Zn, it easily follows that if g(d)is defined as gm(d) for m = r(d), then g is the unique extension of h to amodular function Zn â Z.[Straying a bit, one could define a subcubism by replacing the = 1 in(2.36) by â¥ 1, and the same proof shows that a D with a subcubism issubfundamental; similarly for supercubism and â¤ 1.]2.8.4 Second Proof of Theorem 2.8.3The proof of Theorem 2.8.3 above can be viewed as giving a cubism (e.g.,Figure 2.2 for n = 2).Second proof of Theorem 2.8.3. For each d â Zn, let r(d) denote the L1distancer(d) = |d1|+ · · Â·+ |dn|+â£â£{i â [n] | di â¤ 0}â£â£â n+ 1(so if all di â¥ 0, this becomes d1 + · · Â·+ dn â n+ 1, and otherwise we needabsolute values and minor corrections for those di < 0). Now we claim thatr is a cubism.To show that r attains only positive integer values, we can write r asr(d) = 1 +nâi=1max(di â 1,âdi);502.8. Fundamental Domains and the Proofs of Theorems 2.3.4 and 2.3.5Di, i = 0 Di, i = 1Di, i = 2 Di, i = 3(a) New points Di Diâ1in red, old points, Diâiin blue111122222222333333333333(b) The cubism after 4steps.Figure 2.2: A cubism for Dncoord with n = 2.512.8. Fundamental Domains and the Proofs of Theorems 2.3.4 and 2.3.5since max(diâ1,âdi) is non-negative for any di â Z, r attains only positivevalues. We leave the verification of (1) and (2) in the definition of a cubismto the reader.We also remark thatâunlike the above exampleâthere is no need forrâ1({m}) to be finite; in fact, the next example shows that it can be conve-nient for râ1{m} to be infinite.2.8.5 Other Examples of Cubisms and the Proof ofTheorem2.3.5Proof of Theorem 2.3.5. LetD = {d | a â¤ deg(d) â¤ a+ nâ 1}.Define r : Zn â N asr(d) ={deg(d)â a+ n+ 1 if deg(d) â¥ a+ n, anda+ nâ deg(d) if deg(d) < a+ n.Setting D0 = D and, for m â N, Dm as in (2.35), we easily see that thatif r(d) = m then Cube(d) Dmâ1 consists of a single point, namely d ifdeg(d) â¥ a + n, and otherwise the single point d â 1. Since these singlepoints sets are distinct, it follows that r is a cubism of D.Example 2.8.7. One can show by a cubism argument that the set D â Z2given by{(0, 0)} âª {d â Z2 | deg(d) = ±1}is fundamental, by defining r(d) to be |d1| if deg(d) = 1 and otherwise||deg(d)| â 1|; we depict this cubism in Figure 2.3. It follows that anysubset of D is subfundamental (e.g., removing (0, 0)), and any superset ofD is superfundamental.It is intriguingâbut not relevant to this articleâto consider the variousother fundamental modular domains of Zn.522.8. Fundamental Domains and the Proofs of Theorems 2.3.4 and 2.3.5Di, i = 0 Di, i = 1Di, i = 2 Di, i = 3(a) New points in red,old points in blue11112222 223 333333333(b) The cubism after 4steps.Figure 2.3: Degree cubism 53Chapter 3Diagrams, Betti Numbers,and Models for RiemannFunctions that Count PerfectMatchingsIn this section we introduce our basic models and develop some of theirproperties. We will especially study those related to Riemann functionsZ2 â Z that count perfect matchings; such functions have a number ofespecially remarkable properties.3.1 Betti Numbers, Fredholm Maps, and DirectSumsIf k is a field and Ï : B â A is a linear map of k-vector spaces B,A, fori = 0, 1 we define the i-th cohomology group of Ï to be, respectivelyH0(Ï)def= ker(Ï), H1(Ï)def= coker(Ï),and the i-th Betti number of Ï to be bi(Ï) = dimkHi(Ï); we say that Ïis Fredholm if both Betti numbers are finite, and if so we define the Eulercharacteristic of Ï (also known is its index) to beÏ(Ï) = b0(Ï)â b1(Ï);if exactly one of b0(Ï) and b1(Ï) is infinite, we may also define Ï(Ï) as Â±â.543.2. k-Diagrams: Diagrams of k-Vector SpacesIf {Bi}iâI is a family of k-vector spaces indexed on a set I, we define itsdirect sum, denoted âiâIBi as usual, i.e., the vector space of tuples {bi}iâIsuch that each bi â Bi and all but finitely many of the bi are zero. IfÏi : Bi â Ai is a family of k-linear maps of vector spaces indexed on i â I,we define the direct sum of {Ïi}iâI as usual, i.e., as the mapâiâIÏi :âiâIBi ââiâIAi;we easily check that for j = 0, 1 we have a simple isomororphismHj(âiâIÏi)'âiâIHj(Ïi),and hence Betti numbersbj(âiâIÏi)=âiâIbj(Ïi),so that if all the Ïi are Fredholm maps, where all but finitely many of theÏi have both Betti numbers equal to zero, we get a finite and well-definedEuler characteristicÏ(âiâIÏi)=âiâIÏ(Ïi).3.2 k-Diagrams: Diagrams of k-Vector SpacesOur models of Riemann functions will be k-linear maps Ï : B â A whichare built from one fixed type of âdiagramâ of vector spaces, depicted inFigure 3.1 and which we now make precise.Definition 3.2.1. Let k be a field. By a diagram of k-vector spaces, orsimply a k-diagram we mean a collection, F , of data consisting of:1. five k-vector spaces,F(B1),F(B2),F(B3),F(A1),F(A2)553.2. k-Diagrams: Diagrams of k-Vector SpacesF(B1)F(B2)F(B3)F(A1)F(A2)F(Ï1,1)F(Ï2,2)F(Ï3,1)F(Ï3,2)Figure 3.1: Our Diagramscalled the values of F ; and2. k-linear maps F(Ïi,j) : F(Bi)â F(Aj) for the pairs (i, j) where (i, j) â{(1, 1), (2, 2), (3, 1), (3, 2)} (i.e., F(Ï1,2) and F(Ï2,1) donât exist); wecall the F(Ïij) the restriction maps of F .To this diagram we associate the vector spacesF(B) = F(B1)âF(B2)âF(B3), F(A) = F(A1)âF(A2),and the linear transformation F(â) : F(B) â F(A), called the differentialof F , given byF(â)(b1, b2, b3) =(F(Ï1,1)(b1)âF(Ï3,1)(b3),F(Ï3,2)(b3)âF(Ï2,2)(b2)),and define the zeroth and first cohomology groups of F to be, respectivelyH0(F) def= ker(F(â)), H1(F) def= coker(F(â)),i.e., the kernel and cokernel of F(â). If (b1, b2, b3) â H0(F), and aj =F(Ïjj)bj for j = 1, 2, then the tuple (b1, b2, b3, a1, a2) satisfies F(Ïij)bi = ajwhenever F(Ïij) is defined, and we refer to (b1, b2, b3, a1, a2) as a globalsection of F .Note that if (b1, b2, b3, a1, a2) is a global section, then (b1, b2, b3) â H0(F);this therefore gives a bijection between global sections of F and H0(F), i.e.,563.3. Conventions on Sets, Multisets, Induced Vector Spaces, andMW,d for Non-Negative Weightsthe kernel of the differential F(â) of F . [Global sections tend to be con-ceptually more useful, equivalent descriptions are useful in certain compu-tations; we will later give another equivalent description of global sectionsas elements of Hom(k,F), useful when considering the Yoneda pairing.]In section 3.10.1 we will explain that our choice of F(â) and H1(F)which really represent a choice of basis for each of two one-dimensionalvector spaces (the kËâ of (3.13)) rather than a sort of canonical description,which is true of H0(F). This will only be mildly problematic to us insection 3.10.3.3 Conventions on Sets, Multisets, InducedVector Spaces, and MW,d for Non-NegativeWeightsDefinition 3.3.1. Let k be a field. If S is a set, we use kâS to denote thek-vector space that is direct sum of one copy of k for each element of S,i.e., whose elements are collections {vs}sâS with vs 6= 0 for at most finitelymany values of s; for s â S, we use es to denote the vector that is 1 incomponent s and 0 elsewhere. If T is another set and α : S â T a mapof sets, then α gives rise to a unique k-linear transformation, denoted kâÎ±,from kâS â kâT taking es to eα(s). If S â T , then the inclusion mapι : S â T gives an injection kâÎ¹ which we call the inclusion map (of kâS tokâT ).In the above it is clear that if α is an injection, surjection, or bijection,then the same is true of kâÎ±. Next we fix a convention for multisets (anyreasonable one would suffice).Definition 3.3.2. Let S1, S2 be sets, and W : S1 Ã S2 â Zâ¥0 âª {â}. Themultiset on S1 Ã S2 with multiplicities W refers to the setMulti(W ) = {(s1, s2, i) â S1 Ã S2 Ã N | i â¤W (s1, s2)}, (3.1)where if W (s1, s2) = â, then we view all i as satisfying i â¤ W (s1, s2). We573.3. Conventions on Sets, Multisets, Induced Vector Spaces, andMW,d for Non-Negative WeightsB1 = kâZâ¤d1B2 = kâZâ¤d2B3 = kâWkâZ = A1kâZ = A2Ï1,1 = inclusionÏ2,2 = inclusionÏ3,1Ï3,2Figure 3.2: A Model for W and sWrefer to the maps R â S1 and R â S2 taking (s1, s2, i) to, respectively, s1and s2, as, respectively, the first and second projections. We use the notationkâW to denote kâMulti(W ), which comes with mapsproji : kâW â kâSi (3.2)induced by the first and second projections. The support of W is the setof (s1, s2) â S1 Ã S2 such that W (s1, s2) â¥ 1. When W takes on only thevalues {0, 1}, then with mild abuse of notation we may identify Multi(W )with its support, since W can be viewed as merely identifying a subset ofS1 Ã S2.Example 3.3.3. If W : Z2 â Z is a perfect matching, and pi : Zâ Z is itsassociated bijection, then kâW has one copy of k for each pair (a1, pi(a1)) âZ2 varying over all a1 â Z. In this case we may identify kâW with kZ, wherethe first projection is the identity map on kZ, and the second projection is themap kZ â kZ takes ea1 to epi(a1). Hence both maps (3.2) are isomorphisms.Definition 3.3.4. Let k be a field, W : Z2 â Zâ¥0 âª {â}, and d â Z2. Weuse MW,d to denote the following k-diagram (Definition 3.2.1):1. for i = 1, 2, MW,d(Bi = kâZâ¤di , Ai = kâZ), Ïi,i is the inclusion,2. B3 = kâW , and for j = 1, 2, Ï3,j are the projection maps (as in (3.2)).We depict these k-diagrams in Figure 3.2.583.4. The Euler Characteristic ofMW,d as a Function of d3.4 The Euler Characteristic of MW,d as aFunction of dIt is almost immediate that (1.8) holds for Ïd = MW,d for arbitrary fixedW : Z2 â Zâ¥0 âª {â}. Let us explain.Lemma 3.4.1. Let Ï : B â A be a linear map of k-vector spaces, andlet Bâ² â B be a subspace of codimension one, and let Ï â² = Ï |Bâ², i.e., therestriction of Ï to Bâ². Then eitherb0(Ï) = b0(Ï â²) + 1 and b1(Ï) = b1(Ï â²) (3.3)orb0(Ï) = b0(Ï â²) and b1(Ï) = b1(Ï â²)â 1 (3.4)(allowing for this number to equal â, in which case â± 1 means â). Inparticular, if at least one of bi(Ï) is finite, then Ï(Ï) is well defined, as isÏ(Ï â²), andÏ(Ï) = Ï(Ï â²) + 1.The proof is straightforward: since Bâ² has codimension 1 in B, ker(Ï â²) =ker(Ï) â© Bâ² has either codimension 1 or 0 in ker(Ï); we easily verify thatcodimension 1 implies (3.3) and codimension 0 implies (3.4).Theorem 3.4.2. Let W : Z2 â Zâ¥0. Then for any d â Z2 and i = 1, 2,we have that the conclusions of Lemma 3.4.1 hold for Ï =MW,d+ei(â) andÏ â² =MW,d(â).[In terms of sheaf theory, the above lemma and theorem express the factthat the two k-diagramsMW,d andMW,d+ei fit into a short exact sequencewith a skyscraper sheaf supported at Bi whose value is k.]593.5. The Betti Numbers ofMW,d for Perfect Matchings3.5 The Betti Numbers of MW,d for PerfectMatchingsIn the case W : Z2 â {0, 1} is a perfect matching, it is easy to determine itsBetti numbers.Theorem 3.5.1. Let W : Z2 â Z be a perfect matching. Then1. b0(MW,d) equals the number of a â Z2 such that W (a) = 1 and a â¤ d;2. more precisely, H0(MW,d) has a basis consisting of(ea1 , e(a1,a2), ea2) â ker(MW,d(â)) s.t. a â¤ d; (3.5)3. b1(MW,d) equals the number of a â Z2 such that W (a) = 1 and a â¥d + 1; and4. more precisely, if pi is the bijection associated to W , then H1(MW,d)has a basis consisting of the images in H1(MW,d) ofea1 âMW,d(A1) s.t. a1 â¥ d1 + 1, a2 â¥ d2 + 1. (3.6)In particular, if W is initially and eventually zero, then bi(MW,d) is finitefor all i = 0, 1 and all d â Z2, and is zero when i = 0 and d is sufficientlysmall or when i = 1 and d is sufficiently large; we haveÏ(MW,d) = d + Cfor some constant C; more precisely, for all d,K â Z2 and L = K + 1 wehaveb0(MW,d) = (sW )(d), b1(MW,d) = (sW âL)(Kâ d).Proof. It suffices to prove (2) and (4); the proofs are straightforward: toprove (2), we note that MW,d(B3) = kâW , so the vectors(ea1 , e(a1,a2), ea2) âMW,d(B) =MW,d(B1)âMW,d(B3)âMW,d(B2)603.5. The Betti Numbers ofMW,d for Perfect Matchingsranging over all a1, a2 such that W (a1, a2) = 1 are linearly independent inMW,d(B) by considering merely their MW,d(B3) component. Consider anelement(b1, b3, b2) â ker(MW,d(â));thenb3 =âW (a1,a2)=1e(a1,a2)ca1,a2for some ca1,a2 â k; the condition that (b1, b3, b2) lies in the kernel is equiv-alent tob1 =âW (a1,a2)=1ea1ca1,a2 âMW,d(B1) = kâZâ¤d1 , b2 =âW (a1,a2)=1ea2ca1,a2 âMW,d(B2) = kâZâ¤d2 ,which holds iff a1 â¤ d1 and a2 â¤ d2 whenever ca1,a2 6= 0. Hence each suchtriple (b1, b3, b2) is a unique linear combination of the vectors in (3.5).To prove (4), since MW,d(Ï31),MW,d(Ï32) are isomorphisms, it followsthatV =(MW,d(A1)âMW,d(A2))/Image(MW,d(B3))has (ea1 , 0) as a basis, where a1 ranges over all of Z. The image ofMW,d(B1)in V is precisely the span of all (ea1 , 0) with a1 â¤ d1, and henceV â² = V/Image(MW,d(B1))has a basis consisting of all the (ea1 , 0) with a1 â¥ d1 + 1; finally the imageof MW,d(B2) in V â² is precisely the span of all (0, ea2) with a2 â¤ d2, each ofwhich equals (âea1 , 0) for the unique a1 with W (a1, a2) = 1. HenceH1(F) = V â²â²/Image(MW,d(B2))has a basis as claimed in (3.6).Note that if W : Z2 â Zâ¥0 has W (a1, a2) â¥ 2 for some a1, a2 â Z,then kâW has a copy of k for the two elements (a1, a2, 1) and (a1, a2, 2) of613.6. The Constant Diagram and Related Diagramskkkkkk0kkkkk/B1k0kkkk/B200kkkk/B1,B2Figure 3.3: The Diagram k and Related DiagramsMulti(W ) (recall (3.1)). Hence the element(0, e(a1,a2,1) â e(a1,a2,2), 0)lies in H0(MW,d). It similarly follows that for any d,b0(MW,d) â¥âW (a1,a2)â¥2(W (a1, a2, )â 1).We will later describe the Betti numbers and cohomology groups of MW,dfor any d and any W : Z2 â Zâ¥0 âª {â}. This will prove, for example, thatb0(MW,d) can be infinite for all d, even when W has all values either 0 or1.3.6 The Constant Diagram and RelatedDiagramsTo prove Theorem 3.5.1 we now define the constant diagram k, denoted k,and some important related diagrams; they are depicted in Figure 3.3, whereall maps k â k are the identity maps.Definition 3.6.1. Let k be a field. Consider the four possible diagrams, F ,such that:1. all values of F equal k or 0;2. F(B3) = F(A1) = F(A2) = k;623.7. Direct Sums and Morphisms of Diagrams3. all restriction maps k â k are the identity map.We use the notation k to refer to F as above with F(B1) = F(B2) = k andcall it the constant diagram k; for i = 1, 2 we use the notation k/Bi to referthe same diagram except with F(Bi) = 0; and we use the notation k/B1,B2to refer to the last diagram, i.e., with F(B1) = F(B2) = 0. We refer tothese four diagrams collectively as the four basic k-diagrams.The importance of the above four diagrams is that if W : ZÃZâ {0, 1}is a perfect matching, then for any d â Z2, MW,d is isomorphic to a directsum of diagrams of these four types. Let us make this notion of direct sumprecise.3.7 Direct Sums and Morphisms of DiagramsDefinition 3.7.1. Let k be a field, and F ,G two k-diagrams. By a morphismF â G we mean the data, Ï, of linear maps on each value of F to thecorresponding value on G in a way that commutes with the restriction maps:i.e., Ï consists of k-linear maps Ï(Bi) : F(Bi) â G(Bi) for i = 1, 2, 3 andÏ(Aj) : F(Aj) â G(Aj) for j = 1, 2 such that G(Ïij)Ï(Bi) = Ï(Aj)F(Ïij)whenever F(Ïij),G(Ïij) exist (i.e., i = j or i = 3 and any j).We illustrate a morphism of k-diagrams in Figure 3.4.Example 3.7.2. If V is a k-vector space, then a map k â V is specifiedby its image of 1 â k. For any k-diagram, F , we see that an elementÏHomk(k,F) is specified by(b1, b3, b2, a1, a2) =(Ï(b1)(1), . . . , Ï(a2)(1)),which is a global section of F . We easily see that this gives an isomorphismbetween Homk(k,F) to the global sections of F , and restricting to (b1, b2, b3)therefore gives an isomorphism to H0(F).Example 3.7.3. We easily check that Homk(k, k/B1) ' k, butHomk(k/B1 , k) ' 0. This reflects a general fact that if X is a topologi-cal space, and j : Z â X is the inclusion of a closed subset, then there is633.7. Direct Sums and Morphisms of DiagramsF(B1)F(B2)F(B3)F(A1)F(A2)F(Ï1,1)F(Ï2,2)F(Ï3,1)F(Ï3,2)G(B1)G(B2)G(B3)G(A1)G(A2)G(Ï1,1)G(Ï2,2)G(Ï3,1)G(Ï3,2)Ï(B1)Ï(B2)Ï(B3)Ï(A1)Ï(A2)F GÏFigure 3.4: A morphism of diagrams Ï : F â G, depicted in thick linesa canonical map F â FZ where FZ = jâjâF is the restriction of F to Zand extended by 0. (However, there is generally no nonzero map FZ â F .)In this way, all four basic diagrams are naturally quotients of F , i.e., admitsurjections (value-by-value) from k.Once one defines the morphisms as above, we get category of diagramsof k-vector spaces, and there results a number of notions: for example, anisomorphism is a morphism with an inverse, and a direct sum of diagramsis the coproduct (the category of k-diagrams has a zero object). Let us givea more concrete description of the direct sum.Definition 3.7.4. Let k be a field and I a set. The direct sum of a family{Fi}iâI of diagrams of k-vector spaces is diagram whose values are the directsums of the corresponding values of the Fi, and whose restriction maps arethe direct sum of the corresponding restriction maps of the Fi.The reader who is so inclined can prove that our definition of directsum corresponds to the category theoretic definition in the category of k-diagrams ([1] Corollaire I.3.2, or [20] Exercise II.1.9 for finite direct sums inthe context of sheaves). It is immediate from the Definition 3.7.4 that thedifferential of a direct sum of diagrams is the direct sum of the differentialof the diagrams. Hence we conclude the following proposition.643.8. Direct Sums and Proof of Theorem 3.5.1Proposition 3.7.5. Let k be a field and {Fi}iâI a family of diagrams ofk-vector spaces, and let F be their direct sum. Thenker(F(â)) =âiâIker(Fi(â)), coker(F(â)) =âiâIcoker(Fi(â)),and hence for j = 0, 1 we havebj(F) =âiâIbj(Fi).3.8 Direct Sums and Proof of Theorem 3.5.1We now combine the definitions and properties of direct sums to prove The-orem 3.5.1.Lemma 3.8.1. Let W : Z2 â {0, 1} be a perfect matching. Then for eachd, MW,d is isomorphic to a direct sum of our four basic k-diagrams (Defi-nition 3.6.1), where1. the number of times k appears is the number of a â¤ d such thatW (a) = 1, and2. the number of times k/B1,B2 appears is the number of a â¥ d + 1 suchthat W (a) = 1.More precisely, MW,d is the direct sum of Φi over all i â Z where Φi equals:1. k if pr1(i) â¤ d1 and pr2(i) â¤ d2;2. k/B1,B2 if pr1(i) > d1 and pr2(i) > d2;3. k/Bj for j = 1 or j = 2 if prj(i) > dj and pr3âj â¤ d3âj.The more precise portion of the lemma is immediate, and the rest of thelemma follows.An easy calculation shows the following lemma.Lemma 3.8.2. For any field k, we have b0(k) = 1, b1(k) = 0, the reverseholds for k/B1,B2, and both Betti numbers vanish for k/Bj for j = 1, 2.653.9. Indicator k-Diagrams and Sums of Perfect MatchingsProof of Theorem 3.5.1. The theorem follows from the above two lemmasand the discussion of the direct sum.3.9 Indicator k-Diagrams and Sums of PerfectMatchingsIn this section we prove a theorem about the direct sums of perfect matchingsneeded for what is to come. To give a conceptually simple proof we firstintroduce indicator k-diagrams: these families of k-diagrams, depending ond, illustrate that in Theorem 3.5.1, the direct sum decomposition into ourfour basic k-diagrams can actually be done as a family of four basic k-diagrams depending on d.Definition 3.9.1. Let k be a field and a â Z2. The â¥ a-indicator familyof k-diagrams refers to the family of k-diagrams indexed on d, denoted{Iaâ¤d?}dâZ2 , where for each d we set1. Iaâ¤d? = k if a â¤ d,2. Iaâ¤d? = k/B1,B2 if a â¥ d + 1,3. Iaâ¤d? = k/B2 if a1 â¤ d1 and a2 â¥ d2 + 1, and4. Iaâ¤d? = k/B1 if a2 â¤ d2 and a1 â¥ d1 + 1.Equivalently, for each d, Iaâ¤d? is equal to one of the four basic k-diagrams,where for each j = 1, 2, Iaâ¤d?(Bj) = k iff aj â¤ dj .We depict the indicator diagram in Figure 3.5.Definition 3.9.2. If W : Z2 â Zâ¥0âª{â}, the W -sum indicator k-diagram,denoted IWd , refers to the direct sumIWd =âaâZ2(Iaâ¤d?)âW (a),where if W (a) =â, then âW (a) refers to âN, i.e., the summand involvedis the direct sum of a countably infinite number of copies of Iaâ¤d?.663.9. Indicator k-Diagrams and Sums of Perfect MatchingsIaâ¤d?(B1) ={k if a1 â¤ d1,0 otherwise.Iaâ¤d?(B2) ={k if a2 â¤ d2,0 otherwise.kkkInclusionInclusionIdentityIdentityFigure 3.5: The Indicator k-Diagram Iaâ¤d?The following proposition is immediate, but worth stating.Proposition 3.9.3. Let W : Z2 â {0, 1} be a perfect matching. Then fori = 1, 2, there are isomorphismskâZ â IWd (Ai), kâZâ¤di â IWd (Bi),which yield an isomorphismιd : MW,d â IWdwhere ιd(B3) : MW,d(B3)â IWd (B3) is given by e(a1,a2) 7â ea1.Proof. The proof is a straightforward consequence of âunpackingâ the def-initions of these k-diagrams. For W : Z â Zâ¥0 we define its columns sumsto beColSumW (a1)def=âa2âZW (a1, a2);then(IWd )(A1) =âa1âZkâColSumW (a1), (3.7)and similarly for the A2 values and the analogously defined row sums of W .Hence if W is a perfect matching, we have(IWd )(A1) =âa1âZk = kâZ; (3.8)673.9. Indicator k-Diagrams and Sums of Perfect Matchingshence the map ι(A1) : MW,d(A1) â IWd (A1) taking ea1 â MW,d(A1) tothe a1-component of IWd (A1) is an isomorphism; there is a similarly definedisomorphism ι(A2). Viewing the values of the two diagrams in questionâMW,d and IWd âat B1 as subsets of the values at A1, ι(A1) restricts toan isomorphism ι(B1), since the a1-component of the A1 value is 0 or kaccording to whether or not a1 â¤ d1 in both of these k-diagrams; similarly forthe B2 values. Finally each k component of MW,d(B3) = kâW correspondsto a pair (a1, a2) at which W (a1, a2) = 1, and mapping this component tothe a1-component of IWd (B3), we see that this gives an isomorphism at ι(B3)compatible with the restriction maps of the two k-diagrams in question.If any of the row or column sums is zero, one is missing a copy of k inthe corresponding A1 or A2 value, and if any sum is two or more, one hastoo many copies of k there.Proposition 3.9.4. For any W : ZÃ Zâ Zâ¥0 âª {â},b0(IWd ) =âaâ¤dW (a),b1(IWd ) =âaâ¥d+1W (a),and hence, if one of these two Betti numbers is finite, we haveÏ(IWd ) =ï£«ï£­âaâ¤dW (a)ï£¶ï£¸âï£«ï£­ âaâ¥d+1W (a)ï£¶ï£¸ .Our main interest in Proposition 3.9.4 is for W that are s-fold perfectmatchings in the following sense.Definition 3.9.5. We say that a function W : Z2 â Zâ¥0 is an s-fold match-ing if it can be written as the sum of s (bounded) perfect matchings.To build models for general Riemann functions Z2 â Z we will requirethe following strengthening of Proposition 3.9.4.683.10. A Simple Duality TheoremProposition 3.9.6. Let {Wi}iâI be a finite or countably infinite set of func-tions Wi : Z2 â Zâ¥0 âª {â}, and let W =âiâIWi. ThenIWd 'âiâIIWid . (3.9)Let W : Z2 â Zâ¥0 be an s-fold matching, and W = W1 + · · · + Ws be adecomposition of W into perfect matchings. Then for any d â Z2 there isan isomorphismIWd 'MW1,d â · · · âMWs,d. (3.10)In particular, if W = W â²1 + · · · + W â²s is another decomposition of W intoperfect matchings, then we haveMW1,d â · · · âMWs,d 'MW â²1,d â · · · âMW â²s,d (3.11)Proof. (3.9) follows from the easily verified fact that any direct sum of directsums is the direct sum of all summands in the double summation (this is,more generally, valid in any additive category, since this is an inductive limitof inductive limits, see e.g., [1], Section I.2.5.0). (3.10) follows from (3.9)and Proposition 3.9.4. (3.11) follows from (3.10).3.10 A Simple Duality TheoremA Riemann-Roch formula is an equation involving certain integers; herewe prove a duality theorem, meaning a theorem about two k-vector spacesbeing isomorphic, which implies our Riemann-Roch formulas. Our dualitytheorem exhibits an isomorphism:H0(MW,d) ' H1(MW âL,Kâd)âfor any perfect matching W , fixed d,L â Z2, fixed K = Lâ 1. This impliesthe equality of integersb0(MW,d) = b1(MW âL,Kâd),693.10. A Simple Duality Theoremwhich is equivalent to a Riemann-Roch formula. Unfortunately, the dualitytheorem we prove in this section is based on specific combinatorial consid-erations, and seems less powerful (but simpler) than the version of Serreduality we allude to in .For any field k and diagrams Φ,Ψ of k-vector spaces, we easily see thatHom(Φ,Ψ) is a k-vector space (where addition and scalar multiplication isperformed on each restriction map). We also see that if {Î¦}iâI is a familyof diagrams, thenHom(âiÎ¦i,Î¨) =âiHom(Î¦i,Î¨).For example, we see thatdimk Hom(Φ, k) = 1whenever Φ = k, k/B1 , k/B2 , k/B1,B2 . By contrast, we see thatdimk Hom(Φ, k/B1,B2) ={0 if Φ = k, k/B1 , k/B2 , and1 if Φ = k/B1,B2 .Recall that if I is a set, then kI is the product of copies of k, one foreach i â I; its elements are {vi}iâI , although the vi â k are arbitrary, i.e.,we do not require that vi 6= 0 for only finitely many I. In particular, if Iis infinite then kâI is a proper subset of kI , and the dimension of kI is oflarger cardinality than that of I.Proposition 3.10.1. Let F be a diagram of k-vector spaces that is a directsum {Fi}iâI , where each Fi is one of k, k/B1 , k/B2 , k/B1,B2. Then there is anatural morphismHom(F , k) ' (kâ)I ,where kâ is the dual of the k-vector space k; hence this morphism is anisomorphism if I is finite; similarly, there is a natural morphismcoker(F(â))â Hom(F , k/B1,B2) ' (kâ)J703.10. A Simple Duality Theoremwhere J â I is the set of j â I such that Fi = k/B1,B2, and this morphismis an isomorphism if J is finite.Corollary 3.10.2. Let W : Z2 â {0, 1} be a perfect matching that is ini-tially and eventually zero. Then there is a natural isomorophism:H1(MW,d)â â Hom(MW,d, k/B1,B2)â â kJ ,where J is the set of a â¥ d + 1 such that W (a) = 1. In particular, for anyK â Z2 and L = K + 1 there are natural isomorphismsH1(MW,d)â â kJ â H0(MW âL,Kâd). (3.12)Notice that the duality in (6.2) is due to the fact that both sides areisomorphic to kJ . Hence we get a duality mapH1(MW,d)â â H0(MW âL,Kâd)based on the combinatorial meaning of these cohomology groups.3.10.1 The Fine Print Regarding F(â) and H1(F)Our definition of H0(F) is reasonable. However, experts will likely notethat our description of F(â) and H1(F) is one of convenience: it is betterto say that our definition of H1(F) is convenient rather than canonical.The truth is that if µ : k2 â k is the map taking (x1, x2) to x1 + x2, andkË = ker(µ), then kË is a one-dimensional space without a canonical basisvector, although (1,â1) or (â1, 1) seem like reasonable choices. There is areasonably canonical projective resolution of the constant presheaf k, P1 âP0 â k, where P1 is the sum of coskyscraper sheaves at A1 and A2 withvalues kË. Hence H1(F), as computed with this projective resolution is mostnaturally the quotient of(kË)â âk F(A1)â (kË)â âk F(A2) (3.13)713.10. A Simple Duality Theoremwhere (kË)â is the dual space, again a one-dimensional k-vector space. Ourdefinition of F(â) and H1(F) represent a choice of generator of the twoappearances of (kË)â in (3.13).Of course, there is no unique projective or injective resolution of k or anypresheaf (in the sense of Grothendieck) or sheaf (in the classical sense). Onthe other hand, resolving k by taking P0 to be the direct sum of coskyscrapersheaves at B1, B2, B3 whose values there are k seems reasonably âcanonical.â72Chapter 4Riemann Functions for n = 2and Virtual EulerCharacteristicsIn this chapter we model a general Riemann function f : Z2 â Z as a virtualEuler characteristic, roughly as follows. In brief, we show that W = mf canbe written asW = (W1 + · · Â·+Ws)â (WË1 + · · Â·+ WËsâ1)for some k, where the Wi are perfect matchings. Using this we model f asb0 of the virtual sheaf (âiMWi,d,âiMWËi,d),which is a âformal differenceâ of the first sheaf âminusâ the second. We thenshow that the isomorphism class of the virtual sheaf is independent of thechoice of k and W1, . . . ,Ws and WË1 + . . .+ WËsâ1.4.1 Virtual Diagrams and Virtual FredholmDiagramsWe now introduce a group of formal differencesâeither of diagrams orFredholm mapsâthat one sees in, say, K-theory, which is often calledthe Grothendieck completion or the Grothendieck group (of a commutative734.1. Virtual Diagrams and Virtual Fredholm Diagramsmonoid).Definition 4.1.1. Let k be a field. By a virtual k-diagram (respectively,virtual Fredholm k-diagram, virtual k-linear map, virtual k-linear Fredholmmap) of k-vector spaces we mean a pair (F1,F2) of k-diagrams (respectively,Fredholm k-diagrams, k-linear maps, Fredholm k-linear maps); we write(F1,F2) â¼ (F â²1,F â²2) if there is an isomorphism ÏÏ : F1 âF â²2 âF0 â F â²1 âF2 âF0for some k-diagram F0 (respectively, Fredholm k-diagram, etc.). At timeswe use the notation F1 F2 to denote (F1,F2).We easily see that â¼ is an equivalence relation, and that that â and behave like + and â regarding parenthesis, e.g.,F1 (F2 F3) ' (F1 âF3) F2.We remark that virtual k-vector spaces are not particularly interesting,in that k â¼ 0 since there is an isomorphism k â kN â kN; however, virtualfinite-dimensional k-vector spaces have kb ka â¼ kbâ² kaâ² iff bâ a = bâ²â aâ²,and hence they have a well-defined dimension in Z. For similar reasons,virtual Fredholm k-diagrams, but not virtual k-diagrams, have well definedBetti numbers (and virtual cohomology groups).Definition 4.1.2. If F F â² is a virtual Fredholm k-diagram, for i = 0, 1we define H i(F F â²) to be the virtual finite dimensional k-vector spaceH i(F) H i(F â²), and we setbi(F ,F â²) = bi(F)â bi(F â²).Lemma 4.1.3. Let F1 F â²1 and F2 F â²2 be isomorphic virtual Fredholmk-diagrams; then these diagrams have the same Betti numbers bi, i = 0, 1.Moreover, for i = 0, 1, H i(F1 F â²1) is isomorphic to H i(F2 F â²2).744.2. Riemann Functions as Virtual Direct SumsProof. For any F0 Fredholm k-diagram we haveH i(F0 âF1 âF â²2) ' H i(F0)âH i(F1)âH i(F â²2),and by definition the right-hand-side are all finite dimensional k-vectorspaces. Hence if F1 F â²1 and F2 F â²2 are isomorphic, then for i = 0, 1we havebi(F0) + bi(F1) + bi(F â²2) = bi(F0) + bi(F â²1) + bi(F2)and hencebi(F1 F â²1) = bi(F2 F â²2).The statement about H iâs follows from dimension counting.Remark 4.1.4. Ideally one would like to turn the virtual Fredholm k-diagrams into a category. Ideally a morphism F1 F â²1 to F2 F â²2 could bedefined as a morphismF0 âF1 âF â²2 â F0 âF â²1 âF2;this has a natural âcomposition of morphismsâ rule. The problem is that thenotion of isomorphism seems in general awkwardârequiring us to declarecertain morphisms âisomorphisms,â which amounts to the âlocalizationâ ofthe category, unless we work with a limited subcategory of virtual Fredholmk-diagrams that has a strong âcancellationâ property.4.2 Riemann Functions as Virtual Direct SumsDefinition 4.2.1. Let f : Z2 â Z be a Riemann function, and W = mf . Weuse the notation [MW,d] to refer to the class of virtual Fredholm k-diagrams(MW1,d â · · · âMWs,d ,MWË1,d â · · · âMWËsâ1,d)754.2. Riemann Functions as Virtual Direct Sumssuch that each Wi and WËi is a perfect matching of bounded support withW = (W1 + · · Â·+Ws)â (WË1 + · · Â·+ WËsâ1).The following proposition immediately implies the main result of thechapter.Proposition 4.2.2. For any weight, W , of a Riemann function, and anyd â Z2, the class [MW,d] consists of a single virtual Fredholm k-diagram.Proof. More generally if W1,W2,Wâ²1,Wâ²2 are any sums of finitely many per-fect matchings such that W1 âW2 = W â²1 âW â²2, then W1 + W â²2 = W â²1 + W2is the same s-fold matching for some s. Now apply Proposition 3.9.6.Example 4.2.3. In this example we want to stress the diversity of structurethat can occur in the isomorphisms between the sums of theMWi andMWËj ,even when W is the sum of two perfect matchings. So consider this case,where W = W1 + W2 = WË1 + WË2 has W (i, j) = 1 iff for some t we havei, j â {2t, 2t+ 1} for some t â Z (or equivalently the floor of i/2 equals thatof j/2). The number of ways of writing W = W1 +W2 for perfect matchingsW1,W2 is the number of W1 that for each t â Z matches 2t with either 2tor 2t + 1. Hence there are uncountably many ways of doing so (unless oneimposes additional conditions on W1,W2, e.g., r-periodicity for some evenr). In particular, if we fix WË1, WË2 whose sum is W as above, then whenwe vary W1, each of the basic families of k-diagrams that comprise W1 canbelong either to WË1 or to WË2. In particular, this correspondence of basicfamilies can happen in uncountably many ways.One can generalize the above proposition to indicator k-diagram sums.Proposition 4.2.4. Let W1, . . . ,W4 be functions Z2 â Zâ¥0 such that W1âW2 = W3 âW4. Then for all d we haveIW1d IW2d â¼ IW3d IW4d .764.2. Riemann Functions as Virtual Direct SumsProof. Indeed, if W = W1 +W4 = W2 +W3, then clearlyIW1d â IW4d ' IWd ' IW2d â IW3d .77Chapter 5Modeling General RiemannFunctionsIn this section we model any Riemann function f : Zn â Z by pastingtogether the models we have developed for n = 2.Definition 5.0.1. Let f : Zn â Z be a Riemann function. If i, j â [n] withi 6= j and d â Zn, let fi,j,d : Z2 â Z be the two-variable restriction (2.4).We set W = Wf ;i,j,d to be the weight of fi,j,d, and call[Mf ;i,j,d] def= [MW,0] = [MWf ;i,j,d,0].the i, j restriction of f at d, which is a single class of virtual Fredholmk-diagram.Since fi,j,d is a Riemann function, we haveb0([Mf ;i,j,d]) = fi,j,d(0) = f(d);(2.4) implies that for deg(a) large we have fi,j,d(a) = deg(a) + Câ² whereC â² = d + C, it follows thatÏ([Mf ;i,j,d]) = C â² = deg(d) + C.It follows that for fixed f, i, j,d, and any K â Z2, [Mf ;i,j,d] models theRiemann-Roch formula (2.12) as expressing b0â b1 on the left, and Ï on theright.The main goal of this section is to prove the following theorem whichstates that the virtual Fredholm k-diagram [Mf ;i,j,d] is independent of the785.1. Isomorphisms That Are Simple Along the A1 Valueschoice of i, j.Theorem 5.0.2. Let n â N with n â¥ 3, d â Zn, f : Zn â Z be a Riemannfunction, and i, j, jâ² â [n] be three distinct integers. Then1. [Mf ;i,j,d] = [Mf ;i,jâ²,d], and more generally for any a â Z we have[MWf ;i,j,d,(a,0)] = [MWf ;iâ²,j,d,(a,0)],2. if the two-variable functions fi,j,d and fi,jâ²,d both count perfect match-ings, so that Mf ;i,j,d and Mf ;i,jâ²,d can be viewed as k-diagrams (with-out speaking of virtual k-diagrams), then these k-diagrams are isomor-phic; more generally for all a â Z we haveMWf ;i,j,d,(a,0) 'MWf ;i,jâ²,d,(a,0)The rest of this section is dedicated to the proof of this theorem.This theorem, and the isomorphism it gives, are based on the equalityâa â Z, fi,j,d(0, a) = f(d + aej) = fi,jâ²,d(0, a). (5.1)The other idea is that we look for an isomorphism that is very simple alongthe A1 values ofMW,d, and to see what conditions this requires elsewhere; itturns out that it is only along the B2 value that one needs some conditions,and those conditions turn out to be exactly (5.1). Let us give the details.5.1 Isomorphisms That Are Simple Along the A1ValuesThe simplest case of Theorem 5.0.2 occurs when fi,j,d and fi,jâ²,d both countperfect matchings. In this case we will need the following lemma.Lemma 5.1.1. Let W,W â² be perfect matchings, and pi, piâ² their associatedbijections. Then for any d â Z2 the following are equivalent:795.1. Isomorphisms That Are Simple Along the A1 ValueskâZâ¤d1kâZâ¤d2kâW1kâZkâZea1 7â ea1ea2 7â ea2e(a1,pi1(a1)) 7â ea1e(a1,pi1(a1)) 7â epi1(a1)kâZâ¤d1kâZâ¤d2kâW1kâZkâZea1 7â ea1ea2 7â ea2e(a1,pi2(a1)) 7â ea1e(a1,pi2(a1) 7â epi2(a1)Ï(B1) = identityIs Ï(B2) defined?Ï(B3)e(a1,pi1(a)) = e(a1,pi2(a1))Ï(A1) = identityÏ(A2)(epi1(a1)) = epi2(a1)MW1,d MW2,dÏFigure 5.1: Implications of Ï(A1) = identity, for a Ï : MW1,d â MW2,d(where we omit the quantifiers âa1 â Z and âa2 â Z)1. there exists an isomorphism of k-diagrams Ï : MW,d â MW â²,d suchthat Ï(A1) is the identity; and2.âa â Zâ¤d1 , pi(a) â¤ d2 ââ piâ²(a) â¤ d2. (5.2)We remark that to prove Theorem 5.0.2, we need know only that (2) â(1).Proof. Consider a morphism Ï with Ï(A1) the identity. From Figure 5.1âwhere Ï(A1) being the identity is depicted in a thick line, and the inferencesabout the other values of Ï are depicted in dashed linesâwe see that:1. Ï(B1) is forced to be the identity,2. Ï(B3) must take e(a1,pi1(a1)) to e(a1,pi2(a1)) for all a1 â Z,3. Ï(A2) is forced to take epi(a1) to epi2(a1) for all a1 â Z, and4. Ï(B2) is uniquely determined if it exists, and it exists iff for all a1 â Zwith pi(a1) â¤ d2, the vector the epi2(a1) lies in kâZâ¤d2 .805.1. Isomorphisms That Are Simple Along the A1 ValuesHence Ï(B2) exists iffâa1 â Z, pi1(a1) â¤ d2 â pi2(a1) â¤ d2;and hence Ï(B2) exists and is an isomorphism iff (5.2) holds.We similarly prove the following generalization.Lemma 5.1.2. Let W1, · · · ,Ws and W â²1, · · · ,W â²s be two sequences of perfectmatchings Z2 â Z. Let d â Z2, and for each a1 â Z and j â [s], let eai,j andeâ²ai,j denote, respectively, the standard basis vector ea1 â kZ in, respectivelyMWj ,d(A1) and MW â²j ,d(A1). LetW = W1 + · · Â·+Ws, W â² = W â²1 + · · Â·+W â²s,andMd =MW1,d â · · · âMWs,d, Mâ²d =MW â²1,d â · · · âMW â²s,d.Then for any d â Z2, the following are equivalent:1. there exists an isomorphism Ï : M â Mâ² that for each a1 â Zâ¤d1,such that Ï(A1) restricted to ea1,1, . . . , ea1,s yields a bijection from thisset to eâ²a1,1, . . . , eâ²a1,s;2. letting pir, piâ²r for r â [s] denote the bijections associated to Wr,W â²r, forall a1 â¤ d1, â£â£{r | pir(a1) â¤ d2}â£â£ = â£â£{râ² | piâ²râ²(a1) â¤ d2}â£â£. (5.3)Proof. We haveMd(A1) =âa1âZSpan(ea1,1, . . . , ea1,s)and similarly with Mâ² and the eâ²a1,i, and we have insisted that for each815.2. Combinatorial Versions of the Isomorphism Lemmasa1 â Z there is a permutation Ï = Ïa1 on [s] such thatMd(A1)(ea1,i) = eâ²a1,Ïai (i).But the isomorphism MWi,d ' IWid allows us to writeMd 'âa1âZ, iâ[s]I(a1,i))â¤d?in a way that ea1,i â Md(A1) corresponds to the vector standard basis invector (with the same indices) ea1,i. Since the same is true of Mâ²d, a Ïa1that gives the desired isomorphism must have that for all a1 â Z and i â [s]I(a1,i)â¤d? ' I(a1,Ïa1 i)â¤d?;similar to the argument in the proof of Lemma 5.1.1, this holds automaticallyfor the B1, B3, A2 values, and holds at the B2 value iffpii(a1) â¤ d2 ââ piâ²Ïa1 i(a1) â¤ d2. (5.4)Hence, for each a1 â Z, such a Ïa1 exists iff (5.4) holds.5.2 Combinatorial Versions of the IsomorphismLemmasNow we give combinatorial versions of the isomorphism lemmas above. No-tice that (5.4) is really a generalization of (5.2).Lemma 5.2.1. Let W,W â² be perfect matchings, and pi1, pi2 their associatedbijections. Then for any d â Z2 the following are equivalent:1. there exists an isomorphism of k-diagrams Ï : MW1,d âMW2,d suchthat Ï(A1) is the identity; and2.âa â Zâ¤d1 , pi1(a) â¤ d2 ââ pi2(a) â¤ d2; (5.5)825.2. Combinatorial Versions of the Isomorphism Lemmasand3. setting f1 = sW1 and f2 = sW2 we haveâa â Zâ¤d1 , f1(a, d2) = f2(a, d2). (5.6)Proof. (2) â (3): for any a â Z we havef1(a, d2)âf1(aâ1, d2) =âa2â¤d2W1(a, a2) ={1 if pi1(a) â¤ d2, and0 otherwise,(5.7)and similarly with f2,W2, pi2 replacing f1,W1, pi1. Now f1(a, d2) =f2(a, d2) = 0 for a sufficiently small, and hence (5.6) holds for a â¤ aâ² forsome aâ². Assuming (2), (5.7) implies that for all a â¤ d1 we havef1(a, d2)â f1(aâ 1, d2) = f2(a, d2)â f2(aâ 1, d2)and thereforef1(a, d2)â f2(a, d2) = f1(aâ 1, d2)â f2(aâ 1, d2).Hence we can use induction on a from aâ² + 1 to d1 to infer that (5.5) holdsfor all a â¤ d1.(3) â (2): (5.5) implies that for any a we havef1(a, d2)â f1(aâ 1, d2) = f2(a, d2)â f2(aâ 1, d2)and hence (5.7) and the same for f2,W2, pi2 implies that for each a â¤ d1,pi1(a) â¤ d2 iff pi2(a) â¤ d2.The above lemma will be used whenMf ;i,j,d andMf ;i,jâ²,d are diagrams.When they are virtual diagrams, we will a generalization of the above lemma.Lemma 5.2.2. Let W1, · · · ,Ws and W â²1, · · · ,W â²s be two sequences of perfectmatchings Z2 â Z. Let d â Z2, and for each a1 â Z and j â [s], let eai,j and835.2. Combinatorial Versions of the Isomorphism Lemmaseâ²ai,j denote, respectively, the standard basis vector ea1 â kZ in, respectivelyMWj ,d(A1) and MW â²j ,d(A1). LetW = W1 + · · Â·+Ws, W â² = W â²1 + · · Â·+W â²s,andMd =MW1,d â · · · âMWs,d, Mâ²d =MW â²1,d â · · · âMW â²s,d.Then for any d â Z2, the following are equivalent:1. there exists an isomorphism Ï : M â Mâ² that for each a1 â Zâ¤d1,Ï(A1) restricts to a bijection from ea1,1, . . . , ea1,s to eâ²a1,1, . . . , eâ²a1,s(and, moreover, in this case one can also take from the subset of ea1,rwith pir(a1) â¤ d2 to those eâ²a1,r with piâ²r(a1) â¤ d2 where pir, piâ²r are thebijections associated to Wr,Wâ²r);2. letting pir, piâ²r for r â [s] denote the bijections associated to Wr,W â²r, forall a1 â¤ d1, â£â£{r | pir(a1) â¤ d2}â£â£ = â£â£{r | piâ²r(a1) â¤ d2}â£â£;3.âa1 â¤ d1,âa2â¤d2W (a1, a2) =âa2â¤d2W â²(a1, a2);4. if f = sW and f â² = sW â², thenâa1 â Zâ¤d1 , f(a1, d2) = f â²(a1, d2).Moreover, if the above conditions hold, then all maps Ï(A1) are determinedas those that for each a1 â Z restricts to a bijection{ea1,r | pir(a1) â¤ d2} â {eâ²a1,r | piâ²r(a1) â¤ d2}845.3. Proof of Theorem 5.0.2and to a bijection{ea1,r | pir(a1) â¥ d2 + 1} â {eâ²a1,r | piâ²r(a1) â¥ d2 + 1}.Another way to think of this lemma is to recall that if W1, . . . ,Ws areperfect matchings, and W = W1+Â· · Â·+Ws, thenMW1,dâ· · Â·âMWs,d ' IWd .Hence this lemma shows that IWd ' IWâ²d .Proof. (1) ââ (2): this is Lemma 5.1.2.(2) ââ (3): this is by definition: if W is any perfect matching, thenpi is the unique bijection such that W (a, pi(a)) = 1 for all a â Z. Hence, forany d2 and a1 we haveâa2â¤d2W (a1, a2) =â£â£{r | pir(a1) â¤ d2}â£â£.Similarly âa2â¤d2W â²(a1, a2) =â£â£{r | piâ²r(a1) â¤ d2}â£â£.So if for some a1, the number of values of r such that pir(a1) â¤ d2 is thenumber of râ² with pirâ²(a1) â¤ d2, then for this particular value of a1,âa2â¤d2W (a1, a2) =âa2â¤d2W â²(a1, a2)Now we apply this fact to all a1 â¤ d1.(3) ââ (4): similar to (5.7), we have for all a â Z,f1(a, d2)â f1(aâ 1, d2) =âa2â¤d2W (a, a2) =â£â£{r | pir(a) â¤ d2}â£â£. (5.8)5.3 Proof of Theorem 5.0.2To prove Theorem 5.0.2, we need only the following part of Theorem 5.2.2.855.3. Proof of Theorem 5.0.2Corollary 5.3.1. Let W1, · · · ,Ws and W â²1, · · · ,W â²s be two sequences of per-fect matchings Z2 â Z, and let fi = sWi, f â²i = sW â²i . Say that for somed2 â Z we haveâa1 â Z, f(a1, d2) = f â²(a1, d2).Then for all d1 â Z, the k-diagramsMd =MW1,d â · · · âMWs,d, Mâ²d =MW â²1,d â · · · âMW â²s,d,(with d = (d1, d2)) are isomorphic.Notice that in the application below, there is a fixed Riemann functionof n variables, and f represents a restriction to the components i and j, andthe f â² to components i and jâ² with i, j, jâ² distinct. So, depending on how wedefine f, f â², it may seem more natural to write the condition in the corollaryasâa1 â Z, f(a1, d2) = f â²(a1, d3),where d2, d3 are not necessarily equal. In this case, one could say that forany d1, we have an isomorphism betweenM(d1,d2) and Mâ²(d1,d3),simply by introducing f â²â²(a1, a2) to be defined as f â²(a1, a2 â d2 + d3) andapplying the corollary with f â²â² replacing f â², so that f(a1, d2) = f â²â²(a1, d2) =f â²(a1, d3). This is just a bit more awkward to state; the passing from f â² tof â²â² just translates the weight from mf â² to mf â²â² in the second variable.Proof of Theorem 5.0.2. By definitionfi,j,d(a1, 0) = f(d + eia1) = fi,jâ²,d(a1, 0)for all a1 â Z; now apply Corollary 5.3.1.865.4. Vertex Clearing5.4 Vertex ClearingWe now discuss a combinatorial question related to our models. When doesa single family of sheaves suffice for our models? This section is simplydesigned as an introduction to this topic.Definition 5.4.1. Let G be a graph and {vi1 , vi2 , ..., vik} â V (G) a subsetof its vertex set. We say that G is (vi1 , vi2 , ..., vik)-clearable if for any divisord on G, there exists some dâ² linearly equivalent to d such that dâ²(vl) = 0for all l 6= i1, i2, ..., ik. For k â N, we will also say that G is k-clearableif there exists a subset {vi1 , vi2 , ..., vik} â V (G) of size k such that G is(vi1 , vi2 , ..., vik)-clearable.Even if G is k-clearable it is not necessarily (vj1 , vj2 , ..., vjk)-clearable forevery subset {vj1 , vj2 , ..., vjk} â V (G) of size k. The construction we use tomodel the graph Riemann-Roch rank of divisors on certain graphs involvesfixing the value of divisors on all but two vertices ofG. Graphs which are also2-clearable are of particular interest as they will admit a sheaf model whichrequires a single family of (virtual) sheaves rather than multiple families asis the case in general.Theorem 5.4.2. A graph G is 1-clearable iff it is a tree. .Proof. This follows from Kirchhoffâs theorem on spanning trees as the num-ber of spanning trees of a graph G is equal to |Div0(G)im(âG) | (see [6] section 1.3).Here, Div0(G) denotes the set of divisors of degree 0 on G and âG denotesthe Laplacian of G.Theorem 5.4.3. Let G be a graph of genus 1 and u, v â V (G) adjacentvertices both on the only cycle in G. Then G is (u, v)-clearable.Proof. We may assume without loss of generality that G is a cycle as anydivisor on G is linearly equivalent to a divisor supported on the unique cycleof G. Now let u = v0, v1, v2, ..., vn = v be the path from u to v. As thereis only a single edge between vertices vi and vi+1, we may successively clearthe vertex vi by performing firing moves at vi+1. Such firing moves at vi+1875.4. Vertex Clearingdo not send chips to previously cleared vertices. Hence, after a sequenceof such vertex clearings starting at v2 and ending at vn = v, the resultingdivisor is supported on u and v.The following example gives a characterization of the 2-clearable graphson 3 vertices.Example 5.4.4. On three vertices, the graph will be 2-clearable iff at leasttwo of r, s, t are coprime. First, suppose WLOG that s and t were coprime.By Be´zoutâs identity there exists a, b â Z such that as+ bt = 1. If d(v3) = cthen, performing ac borrowing moves at v1 and bc borrowing moves at v2clears out the divisor at v3. Conversely, suppose the graph were (v1, v2)-clearable. As the graph is (v1, v2)-clearable, a divisor of the form (a, b, 1)must lie in the image of the Laplacian. Any divisor in the image of theLaplacian can be written as a combination of borrowing and lending movesat the vertices v1 and v2 hence, there must thus exists integers c and d suchthat cs+ dt = 1. By Be´zoutâs identity, s and t are coprime.t. ..r. . .. . .sv3v1 v2Theorem 5.4.5. A graph is (vi1 , vi2 , ..., vik)-clearable iff for every vj /â{vi1 , vi2 , ..., vik} there exists a divisor dvj in the image of the Laplacian suchthat dvj (vj) = 1 and dvj (vl) = 0 for all vl /â {vi1 , vi2 , ..., vik , vj}.Proof. The existence of such a divisor for every vj is necessary as otherwisethe divisor with value 1 at vj and 0 elsewhere could not be (vi1 , vi2 , ..., vik)-clearable. The existence of such divisors is also sufficient as they allow usto successively clear every vj /â {vi1 , vi2 , ..., vik}.Example 5.4.6. Consider the graph G below:885.4. Vertex Clearingv1v2v3v4We show G is (v1, v2)-clearable. To see this we consider the graph Lapla-cian âG of G and computeï£«ï£¬ï£¬ï£¬ï£¬ï£­3 â1 â1 â1â1 4 â1 â2â1 â1 2 0â1 â2 0 3ï£¶ï£·ï£·ï£·ï£·ï£¸ï£«ï£¬ï£¬ï£¬ï£¬ï£­â2100ï£¶ï£·ï£·ï£·ï£·ï£¸ =ï£«ï£¬ï£¬ï£¬ï£¬ï£­7â610ï£¶ï£·ï£·ï£·ï£·ï£¸and ï£«ï£¬ï£¬ï£¬ï£¬ï£­3 â1 â1 â1â1 4 â1 â2â1 â1 2 0â1 â2 0 3ï£¶ï£·ï£·ï£·ï£·ï£¸ï£«ï£¬ï£¬ï£¬ï£¬ï£­1â100ï£¶ï£·ï£·ï£·ï£·ï£¸ =ï£«ï£¬ï£¬ï£¬ï£¬ï£­4â501ï£¶ï£·ï£·ï£·ï£·ï£¸Hence by theorem 5.4.5, G is (v1, v2)-clearable.89Chapter 6ConclusionIn this thesis, we gradually constructed virtual k-diagram models for Rie-mann functions and we showed a general duality theory for what we callRiemann-Roch formulas. Furthermore, if f is a Riemann function arising asa graph Riemann-Roch rank function, we showed that the modeling virtualk-diagrams expresses the graph Riemann-Roch formula as an Euler char-acteristic. The approach we took of first expressing a Riemann functionusing its Riemannian weight seems to hold promise for future research asattested to by the new and relatively simple formula obtained for the graphRiemann-Roch rank of the complete graph. However, the material in thisthesis does not yet exhibit the full strength of the underlying sheaf theoryused in our models. We elaborate on this.6.1 Towards a Strong Duality TheoremWe believe there is a strong duality theorem which holds for Riemann func-tions f : Z2 â Z that count a perfect matching pi. We sketch the outline ofthis here; this section is based on preliminary work.If W is the Riemannian weight associated to a perfect matching pi, thenwe takeMpi;d to meanMWd. We have found this notation to be convenientwhen working toward this new duality theory. For any K â Z2, set L =K + 1; we easily show that fâ§K counts the perfect matching piâL given bypiâL(L1 â d1) = L2 â pi(d1).906.1. Towards a Strong Duality TheoremIt follows that for all d â Z2b1(Mpi;d) = b0(MpiâL;d).By a strong duality theorem we mean the stronger assertion that gives anisomorphismH1(Mpi;d)â H0(MpiâL;d)â, (6.1)where â indicates the dual space, or equivalently, a perfect pairingH1(Mpi;d)ÃH0(MpiâL;d)â k, (6.2)meaning a map of the tensor product of finite dimensional k-vector spacesH1(Mpi;d)âk H0(MpiâL;d)â kthat is non-degenerate, hence yielding the isomorphism (6.1).There seems to be a remarkable proof of this duality theorem involves acanonical diagram, in the spirit of Serre duality. Let us first describe thesecanonical diagrams, in the case of perfect matchings pi that are r-periodicfor some r â N, in the sense that pi(x + r) = pi(x) â r for all x â Z; wewill use r-periodic pi to model any Riemann function f : Zn â Z that isr-periodic in the sense thatâi, j â [n], d â Zn, f(d) = f(d + rei â rej).The short story is that for any two r-periodic perfect matchings, pi, piâ²,and d,dâ² â Z2, there is a natural r-periodic tensor product diagram of k-vector spacesMpi;d ârMpiâ²;dâ² (6.3)(this k-diagram is never of the formMpiâ²â²;dâ²â² when r â¥ 2, and it depends onlyon pi, piâ² and d + dâ²). The tensor product (6.3) has the following remarkableproperty: b1 of this diagram vanishes for all d+dâ² iff there exists no L â Z2such that piâ² = piâL; hence the tensor product can detect when two Riemann916.1. Towards a Strong Duality TheoremOr(B1) = k[y1]Or(B2) = k[1/x2]Or(B3) = k[v, 1/v]Or(A1) = k[x1, 1/x1]Or(A2) = k[x2, 1/x2]y1 7â 1/x1y2 7â 1/x2v 7â xr1v 7â xâr2Figure 6.1: The Diagram of Rings, Orfunctions counting perfect matchings, f, f â², satisfy a relation f â² = fâK forsome K. Our practical interest in the tensor product is that if piâ² = piâL forsome L â Z2, then setting K = L â 1 we define the canonical diagram ofpi,L to beÏpi,L =Mpi;0 ârMpiâ²;K; (6.4)we will see that b1(Ï) = 1, and Ï can be used to give a duality theoryresembling Serre duality. However, for r â¥ 2, b0(Ï) = â, which is anindication that our duality theorem was some awkwardness not present inSerre duality.The longer story is that if O is any diagram of rings, defined analogouslyto a diagram of vector spaces, then there is a notion of a O-module, whereany two O-modules F ,G have a tensor product, F âO G, and the set ofO-module morphisms HomO(F ,G), from F to G. For example, a diagramof k-vector spaces is the same thing as a k-module, where k denotes theâconstant diagram k;â the set Homk(F ,G) of morphisms F â G of diagramsof vector spaces turns out to be a crucial tool to us. The other example, isthe diagram of rings Or defined for any r â N, depicted in Figure 6.1, and isthe basis of our analog of Serre duality. If pi is r-periodic, thenMpi;d has thestructure of an Or-module, and the r-periodic tensor product (6.3) turns outto be just their tensor product as Or-modules. Our version of Serre dualityturns out to be more awkward than the usual one: namely, given notation926.2. Further Questions Which Interest Usas in (6.4), we seek a perfect (i.e., non-degenerate) pairingH1(F âMpi;0)ÃHomOr(F ,Mpiâ²;K)â k. (6.5)for certain O-modules, F . To do we use a canonical mapHomOr(F ,Mpiâ²;K)â HomOr(FâOrMpi;0,Mpiâ²;KâOrMpi;0) = HomOr(FâOrMpi;0, Ïpi,L),which we combine with Yoneda pairing (although very easy to describe inour case)H1(F âMpi;0)ÃHomOr(F âOrMpi;0, Ïpi,L)â H1(Ïpi,L) ' k,which gives us the pairing we desire.6.2 Further Questions Which Interest UsWe conclude with a few questions concerning our sheaf models which couldbe of interest in future research.Can the sheaf models be improved? Part of the awkwardness of ourmodels for Riemann functions of n â¥ 3 is the need to piece togetherthe virtual sheaves we constructed and the need of making some ad hocchoices. Do there exist virtual sheaves can which can more naturallymodel Riemann functions in higher dimensions? It is certainly possibleand straightforward to construct such a âhigher dimensionalâ familyof sheaves Ïd with b0(Ïd) = f(d) for all d. However, the authors arenot aware of any higher dimensional families of sheaves like this whereH1(Ïd) does not end up being unwieldy.Combinatorial questions For instance, is there a nice characterisation ofgraphs which only require a single family of sheaves to be modeled(i.e. is there a characterisation of 2-clearable graphs as in section5.4)? We can also ask for which graphs are our virtual sheaf modelsgenuine sheaves, that is, when can a virtual sheaf model [MW1,d â936.2. Further Questions Which Interest Us· · · âMWs,d MWË1,d · · · MWËsâ1,d] simply be written as MW,d?This is the case for example if the graph G is a cycle, but also, asshown by 2.5, this is true for complete graphs Kn.Are there further applications of weights? Recently, there has beensome interest in algorithms computing the graph Riemann-Roch rank[12, 13, 27]. It is possible Riemannian weights have further applicationsto such computations. For instance, following numerical experimenta-tion, we believe the Riemannian weights for the graph K ln (with Klndenoting the graph with l edges between every two vertices) will be lintertwined copies of the weights for Kn. Does this lead to a formulafor the graph Riemann-Roch rank of K ln as in the Kn case?94Bibliography[1] The´orie des topos et cohomologie e´tale des sche´mas. Tome 1: The´oriedes topos. Springer-Verlag, Berlin, 1972. Se´minaire de Ge´ome´trieAlge´brique du Bois-Marie 1963â1964 (SGA 4), Dirige´ par M. Artin,A. Grothendieck, et J. L. Verdier. Avec la collaboration de N. Bour-baki, P. Deligne et B. Saint-Donat, Lecture Notes in Mathematics, Vol.269.[2] Omid Amini and Lucia Caporaso. Riemann-roch theory for weightedgraphs and tropical curves, 2013.[3] Omid Amini and Madhusudan Manjunath. Riemann-Roch for sub-lattices of the root lattice An. Electron. J. Combin., 17(1):ResearchPaper 124, 50, 2010.[4] Yang An, Matthew Baker, Greg Kuperberg, and Farbod Shokrieh.Canonical representatives for divisor classes on tropical curves and thematrix-tree theorem. Forum Math. Sigma, 2:Paper No. e24, 25, 2014.[5] Spencer Backman. Riemann-Roch theory for graph orientations. Adv.Math., 309:655â691, 2017.[6] Matthew Baker and Serguei Norine. Riemann-Roch and Abel-Jacobitheory on a finite graph. Adv. Math., 215(2):766â788, 2007.[7] Norman L. Biggs. Chip-firing and the critical group of a graph. Journalof Algebraic Combinatorics, 9:25â45, 1999.[8] Anders Bjo¨rner and La´szlo´ Miklo´s Lova´sz. Chip-firing games on di-rected graphs. Journal of Algebraic Combinatorics, 1:305â328, 1992.95Bibliography[9] Armand Borel and Jean-Pierre Serre. Le the´ore`me de Riemann-Roch.Bull. Soc. Math. Fr., 86:97â136, 1958.[10] Lucia Caporaso, Yoav Len, and Margarida Melo. Algebraic and com-binatorial rank of divisors on finite graphs. Journal de Mathe´matiquesPures et Applique´es, 104:227â257, 2014.[11] Filip Cools, Jan Draisma, Sam Payne, and Elina Robeva. A tropicalproof of the brill-noether theorem. Advances in Mathematics, 230:759â776, 2010.[12] Robert Cori and Yvan Le Borgne. On computation of Baker andNorineâs rank on complete graphs. Electron. J. Combin., 23(1):Paper1.31, 47, 2016.[13] Michele DâAdderio and Yvan Le Borgne. The sandpile model on Km,nand the rank of its configurations, 2016.[14] Joel Friedman. Cohomology of Grothendieck topologies and lowerbounds in Boolean complexity. 2005. preprint, 70 pages. Availableat http://arxiv.org/abs/cs/0512008 and http://www.math.ubc.ca/jf, specifically http://www.math.ubc.ca/~jf/pubs/web_stuff/groth1.pdf http://arxiv.org/abs/cs/0512008.[15] Joel Friedman. Linear transformations in Boolean complexity theory. InCiE â07: Proceedings of the 3rd conference on Computability in Europe,pages 307â315, Berlin, Heidelberg, 2007. Springer-Verlag.[16] Joel Friedman. Sheaves on graphs, their homological invariants, and aproof of the Hanna Neumann conjecture: with an appendix by WarrenDicks. Mem. Amer. Math. Soc., 233(1100):xii+106, 2015. With anappendix by Warren Dicks.[17] Andreas Gathmann and Michael Kerber. A Riemann-Roch theorem intropical geometry. Math. Z., 259(1):217â230, 2008.96Bibliography[18] Roger Godement. Topologie alge´brique et the´orie des faisceaux. Actu-alites Scientifiques et Industrielles. 1252. Publications de lâInstitut deMathematique de lâUniversite de Strasbourg. XIII. Paris: Hermann &Cie. VIII, 283 p. (1958)., 1958.[19] Alexandre Grothendieck. The´ore`me de dualite´ pour les faisceauxalge´briques cohe´rents. Se´m. Bourbaki 9(1956/57), No. 149, 25 p.(1959)., 1959.[20] Robin Hartshorne. Algebraic geometry. Springer-Verlag, New York,1977. Graduate Texts in Mathematics, No. 52.[21] Jan Hladky´, Daniel Kra´l, and Serguei Norine. Rank of divisorson tropical curves. Journal of Combinatorial Theory, Series A,120(7):1521â1538, Sep 2013.[22] Alice Izsak. Abelian girth and gapped sheaves. 2015. Doctoral thesis,Available as https://open.library.ubc.ca/cIRcle/collections/ubctheses/24/items/1.0223486.[23] Rodney James and Rick Miranda. A riemann-roch theorem for edge-weighted graphs. Proceedings of the American Mathematical Society,141(11):3793â3802, Jul 2013.[24] Serge Lang. Introduction to algebraic and abelian functions, volume 89of Graduate Texts in Mathematics. Springer-Verlag, New York-Berlin,second edition, 1982.[25] Jean Leray. Sur la forme des espaces topologiques et sur les points fixesdes repre´sentations. J. Math. Pures Appl. (9), 24:95â167, 1945.[26] Criel Merino Lo´pez. Chip firing and the tutte polynomial. Annals ofCombinatorics, 1:253â259, 1997.[27] Madhusudan Manjunath. The rank of a divisor on a finite graph: ge-ometry and computation, 2011.97Bibliography[28] Madhusudan Manjunath and Bernd Sturmfels. Monomials, binomials,and riemann-roch, 2012.[29] Fatemeh Mohammadi and Farbod Shokrieh. Divisors on graphs, con-nected flags, and syzygies. International Mathematics Research Notices,2014:6839â6905, 2012.[30] David Mumford. An analytic construction of degenerating curves overcomplete local rings. Compositio Mathematica, 24:129â174, 1972.[31] Jean-Pierre Serre. Faisceaux alge´briques cohe´rents. Ann. Math. (2),61:197â278, 1955.[32] Richard P. Stanley. Enumerative combinatorics. Volume 1, volume 49of Cambridge Studies in Advanced Mathematics. Cambridge UniversityPress, Cambridge, second edition, 2012.[33] William T. Tutte. The factorization of locally finite graphs. CanadianJournal of Mathematics, 2:44â49, 1950.98
Thesis/Dissertation
eng
Mathematics
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Friedman, Joel, 1962-
Riemann functions, their weights, and modeling Riemann-Roch formulas as Euler characteristics
Text