Multidimensional Lattice Walk EnumerationThrough Coefficient Extraction OperatorsbyAleksandar VlasevB.Sc. Mathematics, Simon Fraser University, 2012A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Mathematics)The University of British Columbia(Vancouver)September 2015c© Aleksandar Vlasev, 2015AbstractIn this thesis, we investigate the enumeration of lattice walk models, with or without interactions,in multiple dimensions, through the use of linear operators comprised of coefficient or term extrac-tions. This is done with the goal of furthering our abilities to automate the derivation and solutionsof the functional equations for the generating functions for the models. In particular, for a fairlylarge class of d-dimensional lattice walk models with interactions and arbitrary step sets, the gen-erating function Q satisfies the functional equation p1 ´ tΓSqQ “ q, where Γ is an operator, andS and q are Laurent polynomials. We can automatically expand this equation to obtain an explicitfunctional equation satisfied by Q. For example, we derive an equation for d-dimensional latticewalks with interactions and small steps living in an orthant.We also use this operator approach to unify and extend the algebraic and obstinate kernel meth-ods through the use of a weighted orbit summation operator and substitutions. Other topics include:a partial classification of two-dimensional models with interactions and small steps on the quarterplane, explicit relations for Q and partially-interacting versions of itself for some models, and ananalysis of some of the more abstract properties of the operators involved.iiPrefaceMy advisor, Andrew Rechnitzer, introduced me to the idea of studying lattice walk models withinteraction, where he and his colleagues have studies some problem like this with varying success.He provided me with invaluable guidance and support along the way, and the occasional nudge tofinish the thesis. I, Aleksandar Vlasev, did all the research, write-up and proofreading by myself,with some good discussions with Andrew about different issues. Along the way, I have used resultsand/or ideas from other mathematicians, but I have made a note of each instance, to the best of myknowledge. If a proof is missing, it is left as an exercise because it is either easy or trivial.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Recent History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 One-dimensional Lattice Walk Models . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1 Derivation of the Functional Equation . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Solving Functional Equations For Various Step Sets . . . . . . . . . . . . . . . . . 122.2.1 The S “ δ or S “ δ ` x Case . . . . . . . . . . . . . . . . . . . . . . . . 122.2.2 The S “ δ ` x` x Case . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 Higher-dimensional Lattice Walk Models . . . . . . . . . . . . . . . . . . . . . . . . 163.1 Using Operators to Derive the Functional Equation . . . . . . . . . . . . . . . . . 193.2 Coefficient Extractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2.1 Using Operator Notation For Fast Coefficient Extraction . . . . . . . . . . 213.2.2 Kernel Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.3 First Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25iv3.3.1 Formal Neumann Series and Hadamard Products . . . . . . . . . . . . . . 253.3.2 Reducible Models and Groups For Walks With Small Steps . . . . . . . . 283.4 Specializing to Two Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.4.1 First Examples in the Plane . . . . . . . . . . . . . . . . . . . . . . . . . 313.4.2 Kernel Group Considerations . . . . . . . . . . . . . . . . . . . . . . . . 333.5 Solving Basic Two-dimensional Models . . . . . . . . . . . . . . . . . . . . . . . 343.5.1 Case 2.2 – Group of Order One . . . . . . . . . . . . . . . . . . . . . . . 343.5.2 Case 2.3 – Group of Order Two . . . . . . . . . . . . . . . . . . . . . . . 353.5.3 Counting Classes of Models . . . . . . . . . . . . . . . . . . . . . . . . . 364 The Algebraic Kernel Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.1 Models Without Interactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.2 Models With Interactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.2.1 Groups of Order Four . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.2.2 Groups of Order Six . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.2.3 Groups of Order Eight . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535 The Obstinate Kernel Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.1 Initial Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.1.1 Groups of Order Four . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.1.2 Groups of Order Six . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.1.3 Groups of Order Eight . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.2 Highly-symmetric Two-dimensional Models . . . . . . . . . . . . . . . . . . . . . 635.2.1 Cartesian Model – Steps N, S, E, W . . . . . . . . . . . . . . . . . . . . . 645.2.2 Diagonal Cartesian Model – Steps NE, NW, SE, SW . . . . . . . . . . . . 675.2.3 The Full Model – All Steps . . . . . . . . . . . . . . . . . . . . . . . . . . 716 Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746.1 Marking Operators And Functional Equations . . . . . . . . . . . . . . . . . . . . 746.1.1 Several Examples of Generalized Models . . . . . . . . . . . . . . . . . . 806.2 Further Properties of Marking Operators . . . . . . . . . . . . . . . . . . . . . . . 836.2.1 Marking Operators With Multiplication . . . . . . . . . . . . . . . . . . . 837 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 877.1 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89vList of TablesTable 2.1 Generating functions for walks with small steps on the non-negative half-line,where BpFQ0q “ BpFQq “ 0. . . . . . . . . . . . . . . . . . . . . . . . . . . 15Table 4.1 Reductions of group actions on Q01 and Q02 for groups of order four. . . . . . . . 45Table 4.2 Reductions of group actions on Q0i and Ki for groups of order six. . . . . . . . 50Table 4.3 Relations for A “ K1 and B “ K2 for groups of order six. . . . . . . . . . . . 51Table 4.4 Weight K0 for the orbit summation operators. . . . . . . . . . . . . . . . . . . 52Table 4.5 Step polynomials for models with group of order eight. . . . . . . . . . . . . . 53Table 4.6 Reductions of group actions on Q0i and Ki for groups of order eight. . . . . . . 53Table 5.1 Admissibility-preserving transformations with respect to roots of the kernel withgroup of order four. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56Table 5.2 Admissibility-preserving transformations with respect to roots of the kernel withgroup of order six for the models S11, S12, S13. . . . . . . . . . . . . . . . . 58Table 5.3 Admissibility-preserving transformations with respect to roots of the kernel withgroup of order six for the models S21, S22, S33. . . . . . . . . . . . . . . . . 59Table 5.4 Reductions of group actions on Q01 and Q02, group of order four. . . . . . . . . . 59Table 5.5 Admissibility-preserving transformations with respect to roots of the kernel withgroup of order eight for model S1. . . . . . . . . . . . . . . . . . . . . . . . . 60Table 5.6 Admissibility-preserving transformations with respect to roots of the kernel withgroup of order eight for model S2. . . . . . . . . . . . . . . . . . . . . . . . . 61Table 5.7 Reductions of group actions that preserve admissibility with respect to σ1. . . . 61Table 5.8 Functions S´12 pσ1q for highly-symmetric models. . . . . . . . . . . . . . . . . 64viList of FiguresFigure 3.1 Set of steps allowed in models that do not leave the origin. . . . . . . . . . . . 31Figure 3.2 Sets of steps allowed in models with an N step or an E step. . . . . . . . . . . 32Figure 3.3 Step sets for classical two-dimensional models coming from case 2.2. . . . . . 33Figure 3.4 Step sets for classical two-dimensional models coming from case 2.3. . . . . . 33Figure 3.5 Reducible classical two-dimensional models with an infinite group. . . . . . . 37Figure 3.6 Step sets for classical two-dimensional models with a finite group. . . . . . . . 37Figure 3.7 Step sets for classical two-dimensional models with an infinite group. Unlistedstep sets differ from these by one of the symmetries of the square. . . . . . . . 37Figure 4.1 Highly-symmetric models on the plane with two nontrivial group generators . . 47Figure 5.1 Step sets for models S11, S12, S13. . . . . . . . . . . . . . . . . . . . . . . . 59viiAcknowledgmentsI would like to express my deep gratitude for the financial and academic support from the Univer-sity of British Columbia, Dr. Andrew Rechnitzer and Dr. Kalle Karu. Thank you, Andrew, forintroducing me to such a wonderful topic of research and pushing me along the way to improve andfinally finish my thesis. Thank you my dear Victoria for loving me even during all the difficult times.Thank you mom and dad for not only raising me and bringing me to Canada, but also continuing tosupport and guide me through life. Last, but not least, I would like to thank my friends and coachesfor being understanding and letting me rant in difficult times. You helped me retain my sanity.viiiChapter 1IntroductionThe enumeration of lattice walks is a classical topic in combinatorics, but it has seen a resurgencein recent years, including the milestone of the full classification of the generating functions formodels with small steps on the quarter plane. Work is now being done on the classification ofthree-dimensional models on an orthant, and other generalizations. We may consider models withlarger step sizes set in different regions. A somewhat more difficult topic is that of self-avoidingwalks, where we can study the properties of the generating functions but we do not have closedform expressions for all but the most basic models. It is natural to consider weaker models of walksthat interact with themselves or with various points in the space.While these topics seem related, the behaviour of different models and the tools used in theirstudy can vary significantly. However, it seems that a lot of models can be related via the sameframework. For example, there is some progress towards the automation of the analysis for a lot ofmodels. In this thesis, we provide more evidence that such a unifying theory exists and we do soby recasting several methods of analysis into the language of operators. Furthermore, the change ofperspective allows us to derive the functional equations for a broad class of models.While lattice walk models have a rich mathematical theory, they also enjoy applications outsideof math, where aspects of the physical world can be modelled via walk models. For example,proteins and polymers can be modelled as self-avoiding walks or walks with interactions, and theirlarge-scale properties can be studied via parameters in the generating functions. And of course, theparts of the stock market can be modelled as a random walks, closely related to lattice walks.In what follows, we briefly recall some of the more recent results in the history lattice walkenumeration.11.1 Recent HistorySome lattice walk models are easy to enumerator. For example, if the walks can go anywhere viaany of their steps, the analysis does not even need generating functions — we just construct allpossible sequences of steps from a set S and then we find that the number of walks of length n isjust |S|n. In more complicated models we make use of the generating function. To help us, wedefine a step polynomial S keeping inventory of the step set S.The next step up in difficulty is to consider walks on half-spaces, where walks are not allowedto venture past points with one coordinate equal to zero. These cases are not as simple, but variousmethods allow us to solve them. Check [3, 4, 5, 6, 4, 12] for work in one or more dimensions. Itturns out that the generating functions we obtain are algebraic. Naturally, we are led to considercases where the region is an intersection of half-spaces. Even for two dimensions, the problem hasgenerated a rich theory, where some generating functions are not even D-finite, let alone algebraic.The main object of study in these cases is a group G of bi-rational transformations preserving thepolynomial K “ 1 ´ tS, called the kernel of the model. For a classification of two-dimensionalwalks with small steps in the quarter plane, see [8].Through the classification done in [7, 8, 9, 10, 12], we can see that when G is finite, we obtaina D-finite generating function. The main tool in the study of the finite group cases is the algebraickernel method where we sum different functional equations produced by group actions by elementsof G. This is done to cancel the majority of the terms in the functional equation and allow us to findout information about the model directly. We can also look beyond small steps. For example, see[11] for a treatment of models with finite groups and repeated steps.There are 56 non-equivalent cases of quarter plane walks with an infinite group. For 51 of them,the generating function is not D-finite [13] . The remaining five cases required a fair bit more work[14, 15]. The main tool used to solve these five cases is the iterated kernel method where we useproperties of the roots of the kernel K to show the generating function is not D-finite.With the classification completed, we are naturally led to investigate higher-dimensional models.Recently, the authors of [18] have classified lattice walk models with up to six steps by extendingthe algebraic kernel method to three dimensions. However, we do not need to restrict our analysison the positive orthant. For example, see [16, 17] for analysis of models where the region of interestis a Weyl chamber.For research on self-avoiding walks with various interactions, see [19, 20, 21, 22, 23, 24, 25].The topic of self-avoiding walks does not lend itself as nicely to using generating functions likethe ones considered so far, so we make simplifications. We drop the self-avoiding requirementbut include interactions. For example, see [26, 27] for walks with interactions in an octant. See2[28, 29, 30] for walks with interactions on the plane, where the authors used the obstinate kernelmethod to find relationships between walks with interactions and walks without them. There areboth examples of linear and nonlinear relations.Also, there has been progress towards the automation of the classification of random walk mod-els. For example, see [34] for some classification and [35] for analysis of some of the computationalchallenges involved in automation. There is some automation in the derivation of asymptotics forsome models, for example [37, 36, 38, 39]. A lot of the other works mentioned so far have alsodiscussed asymptotics. Since the enumeration of lattice walks is a combinatorial subject, thereare connections with automation in combinatorics too. For examples, see [31, 32] for details onsymmetric functions, and [33] for a holonomic approach to combinatorics.We hope that there is a general theory unifying the various kernel methods for enumeratinglattice walk models. By recasting some of the analysis in terms of operators, this thesis providesfurther evidence that such a theory may exist. Suppose that an algorithm exists where we caninput an arbitrary lattice walk model and the algorithm can output data about the model: functionalequation for the generating function, a solution of the equation or information about the function’sD-finiteness. Such an algorithm would not have difficulty with the particular model details andbecause of this, such an algorithm is no likely to exist.There may exist lattice walk models which we cannot solve, but the idea of the existence of ageneral algorithm has been a strong motivator in our pursuit of generalizations. Our work succeedsin demonstrating that the first task is achievable — for a general class of lattice walk models withinteractions we have the equationp1´ tΓSqQ “ q , (1.1)where Γ is an operator on the variables of Q and to find an explicit functional equation for Q, weonly need to determine how Γ acts on SQ. For a lot of models, we may find a short explicit form ofthe operator and this allows us to find the equation quickly. Here S is the Laurent step polynomialkeeping inventory of the steps in polynomial form, and q is a Laurent polynomial, serving as aninitial condition. The generating function Q is fully determined by this equation, since we caninvert it formally and obtain the series solutionQ “8ÿk“0pΓSqkp1q “ 1` tΓpSq ` t2ΓpSΓpSqq ` ¨ ¨ ¨ . (1.2)31.2 RoadmapIn this thesis we work towards a few different goals.1. Perform a partial classification of walks with small steps on the quarter plane but with inter-actions with the axes. Almost half of all models are either trivial or easy to solve.2. Extend the algebraic kernel method to interacting models with small steps in d dimensions.3. Extend the obstinate kernel method to interacting models with small steps in the quarter plane.4. Automate the derivation of functional equations for higher-dimensional models with moregeneral restrictions and interactions.In Chapter 2, we study the enumeration of one-dimensional lattice walk models with smallsteps and interactions with the origin. We derive explicit generating functions for all models and theanalysis includes some first examples of the methods that we use in later chapters. For example, wewill see how operators make the derivations easier.In Chapter 3, we use the powerful operator perspective to derive functional equations for thegenerating function enumerating higher-dimensional lattice walk models with small steps and inter-actions with the bounding hyperplanes. In the latter part of the chapter, we focus on the classificationof two-dimensional models and some first solutions. This chapter contains most of the definitionsrelevant in the analysis.In Chapter 4, we recast some of the algebraic kernel analysis in terms of operators and extendit to handle lattice walk models with interactions. We focus on two-dimensional models with finitegroups and see that if the method extends, we have some tighter constraints. In the end, we are ableto handle highly-symmetric models with group of order four, half of the models with group of ordersix, and all models with group of order eight.In Chapter 5, we investigate the obstinate kernel method for the two-dimensional models withinteractions and finite groups. Again, we recast the method in operator notation. For the interactingcases, the algebraic and the obstinate kernel methods are very similar. They can both be understoodin the language of weighted orbital operators.In Chapter 6, we investigate more general random walks models. That is, we find an operatorfunctional equation for a large class of random walk models — those with general regional andmarking constraints, general step sets and general starting conditions. The difficulty lies in findinga good representation for the operators involved.41.3 PreliminariesIn this thesis, we work in the setting of formal power and Laurent series, where formal convergencesuffices. Given a ringR, we may construct several formal objects with a commutative indeterminatex with coefficients in R.• Rrxs: Ring of polynomials with monomials xk for integers k ě 0.• Rrx, 1{xs: Ring of Laurent polynomials with monomials xk for integers k.• Rrrxss: Ring of formal power series with monomials xk for integers k ě 0.• Rppxqq: Field of formal Laurent series with monomials xk for integers k.We can also define their multivariate analogues Rrx1, . . . , xns and Rrx1, x1, . . . , xn, xns, and theirseries counterparts Rrrx1, . . . , xnss and Rppx1, . . . , xnqq. For a thorough treatment of the subject,please see [1]. When we work with a combination of objects coming from different rings/fields overthe indeterminate x, we consider all objects as part of the most general ring/field at the time. If indoubt, we can always work in the field of formal Laurent series. Given a sequence pwnq, we mayconsider its generating function W pxq, given by řnwnxn, which lives appropriately in one of therings over x and/or x. The multivariate case for a sequence pwn1,...,nmq is defined analogously asW px1, . . . , xmq “ÿn1,...,nmwn1,...,nmxn11 ¨ ¨ ¨xnmm , (1.3)whenever this is a formal Laurent series.A function W in one variable is a polynomial if it has only finitely many non-zero terms and itis rational if it can be expressed as a fraction of two polynomials. A more general class is that ofalgebraic functions. These are functions W that satisfy a polynomial equationa0 ` a1W ` ¨ ¨ ¨ ` anWn “ 0 (1.4)with polynomial coefficients ai, where an is non-zero. Polynomials and rational functions areexamples of algebraic functions. However, not all functions are algebraic and we need a moregeneral class — that of D-finite functions. Those are functions that satisfy a finite order differentialequationa0W ` a1W 1 ` ¨ ¨ ¨ ` anW pnq “ 0 (1.5)5with polynomial coefficients ai, where an is non-zero. Clearly, algebraic functions are D-finite. Theset of D-finite functions is closed under multiplication and taking linear combinations. However,not all functions are D-finite. The theory extends analogously to several variables.We often need to extract particular coefficients from the formal polynomial/series when wesolve enumeration problems via generating functions. We have the coefficient extraction operatorrxns that acts on functions W asrxnsW pxq “ wn . (1.6)The multivariate case is analogous with the caveat that, whenever the number of variables extractedis less than the number of variables present, we treat the remaining variables as parameters. For amore detailed discussion, please consult [2]. We construct more linear operators using coefficientextraction as building blocks. Here, a linear operator is a map between two vector spaces or modulesthat satisfies two properties — linear combinations of operators are operators as well and they cancombine via composition to form new ones.In the analysis of generating functions, we often work with functional equations. In this thesis,we discuss functional equations comprised of linear combinations of various coefficient extractionsof a function Q with coefficients that may be rational or algebraic functions. These functionalequations come from operator equations like LQ “ 1, where the operator is comprised of variouscoefficient extraction operators.Finally, we use some basic group theory. We define groups G via generators g1, . . . , gd, and weconstruct orbits of functions under those group actions defined by the elements of G. For example,we use the orbit stabilizer theorem in Chapter 4.6Chapter 2One-dimensional Lattice Walk Models2.1 Derivation of the Functional EquationOur analysis starts with the enumeration of one-dimensional lattice walk models to illustrate themethods and ideas we employ throughout the thesis. As part of the analysis, we use operators tosimplify large portions of the work. We focus on models with interactions and small steps, that is,models where the step size is at most one and we count interactions with the origin. The step setS Ď t´1, 0, 1} can be represented with the polynomialS “ S´1x` S0 ` S1x , (2.1)where Sk is 1 or 0 if k is in S or not, respectively.First, we look at a basic way of generating walks and then we find a way to encapsulate theprocess by an algebraic method. If we start with the empty walk at the origin, we can grow it bytaking one of the steps from S to obtain three walks. One of them ends on the negative axis, sowe remove it. We can continue growing the remaining two walks, each time producing a few morewalks and removing those that end on negative coordinates. At each step, the length of a walkincreases by one and if the walk steps on the origin, we increment a counter tracking the interaction.We can generate all the lattice walks in this way.We translate each of the steps in the process into a transformation on polynomials, and thisenables us to use the powerful of generating functions to extract information about the propertiesof lattice walks. We track the length of walks via powers of t, their interactions via powers ofa, and finally, their endpoints via powers of x. The empty walk has length zero and ends at theorigin, without interacting. Therefore, its corresponding monomial is a0x0t0 “ 1. Each of the steps7changes the end coordinate and this corresponds to multiplying the monomial by one of tx, 1, xu.The two surviving walks have monomials at and xt. It is a good exercise to check that the nextiteration of this algorithm yields the monomials a2t2, axt2, at2, xt2 and x2t2. If S is not the fullset, we have fewer walks.Instead of working with the monomials for individual walks, it is better to work with the wholeset simultaneously. To make computations easier, we keep inventory of all the monomials inside agenerating function Qpa, x; tq, given byQ “ Qpx, a; tq “8ÿk“0qkpx, aqtk , (2.2)where qk is the generating function for walks of length k. Extending a walk corresponds to multi-plying its monomial by a monomial for a step from S. Let us see what happens when we multiplyqk by S. When we expand this product, we obtain all combinations walks of length k and possibleextensions via steps from S. That is, we have extended all walks simultaneously.As in the algorithm above, we need to eliminate the monomials for walks that step on negativecoordinates and to multiply by a those for ones that step on the origin. Once we do that, we turnSqk into qk`1. The next important idea, and it is the kernel of this thesis, is to use some operator Γfor this task. Then we can simply write qk`1 “ ΓpSqkq and sum over powers of t. That is,8ÿk“0qk`1tk`1 “ t8ÿk“0ΓpSqkqtk “ tΓ˜S8ÿk“0qktk¸. (2.3)The expression on the left is Q´ q0 “ Q´ 1 and the expression on the right is tΓpSQq. This givesus a functional equation for Q in terms of S and the operator Γ. That is, the equation isQ “ 1` tΓSQ (2.4)and we rewrite it as p1´ tΓSqQ “ 1 to highlight the operator form.To find the operator Γ, note that when we multiply qk by S, the farthest a walk can go on thenegative axis is the coordinate x “ ´1, so it is enough to remove terms from Sqk with power of ´1of x. For the interaction with the origin, we need to multiply the monomial without x by a. All thiscan be achieved via the coefficient extraction operators rxs and rx0s. We can writeΓ “ 1´ xrxs ` pa´ 1qrx0s , (2.5)8where 1 is the identity operator. When we apply it on some Laurent polynomial F , the identitymakes a copy of F , the ´xrxs part removes the x term from it, and the pa´ 1qrx0s part multipliesthe x0 coefficient by a. This completes our derivation of the functional equation. We make theextractions explicit later on, but for first, we analyze the operator Γ in more detail.Suppose that we decided to obtain the operator step-by-step by finding operators E and L thatremove monomials with x and mark monomials with x0, respectively, and applying them sequen-tially. Then Γ “ LE or Γ “ EL by composition. The operators are given byE “ 1´ xrxs and L “ 1` pa´ 1qrx0s , (2.6)and if we let b “ a´ 1 and multiply them out, we find thatLE “ p1´ xrxsqp1` brx0sq “ 1` brx0s ´ xrxs ´ xrxsbrx0s “ 1` brx0s ´ xrxs . (2.7)Therefore Γ “ LE. Similarly, Γ “ EL, so the operators commute. The last term in the calcula-tion vanished because when we use rx0s, the resulting term is constant with respect to x, and theextraction of the x term yields nothing. Here is an example of how the operators work.Example 2.1. Suppose that S “ x` x. Starting with Q0 “ 1, we haveQ1 “ LESp1q “ p1` brx0s ´ xrxsqpx` xq “ x` x´ x “ x , (2.8)Q2 “ LESpQ1q “ p1` brx0s ´ xrxsqpx2 ` 1q “ x2 ` 1` b “ a` x2 , (2.9)Q3 “ LESpQ2q “ p1` brx0s ´ xrxsqpax` ax` x` x3q“ ax` ax` x` x3 ´ ax“ p1` aqx` x3 . (2.10)Therefore,Q “ Q0 `Q1t`Q2t2 `Q3t3 ` ¨ ¨ ¨“ 1` xt` pa` x2qt2 ` pax` x` x3qt3 ` ¨ ¨ ¨ . (2.11)Note that if we apply Γ on tSQ, we obtain Q with the first term missing.The theory we have presented so far is consistent with present methods for finding the functionalequation for Q because once we compute the explicit extractions in ΓSQ, we obtain the classicalexplicit equations. The difference lies in the ease of use of operators versus the trickier inclusion-exclusion process that becomes unwieldy for models with interactions in higher dimensions.9Next, we perform the extractions to find the explicit equation. Let Qk “ rxksQ. Then,rx0sSQ “ rx0sppS´1x` S0 ` S1xqQq“ pS´1rxs ` S0rx0s ` S1rxsqQ“ S´1Q1 ` S0Q0 ,(2.12)where last equality follows since Q´1 “ 0. Here we used the property that as an operator rxisxj “rxi´js. A similar computation shows that rxsSQ “ S´1Q0 and the explicit equation is given by1 “ Q´ tpSQ` brx0sSQ´ xrxsSqQ“ Q´ tpSQ` bpS´1Q1 ` S0Q0q ´ xS´1Q0q .(2.13)We can rewrite it in the following form:p1´ tSqQ´ tpbS0 ´ xS´1qQ0 ´ btS´1Q1 “ 1 . (2.14)Here Q “ Qpxq, Q0 “ Qp0q and Q1 “ Q1p0q. It turns out that we can eliminate Q1 by finding anequation for it via applying rx0s on both sides of the explicit equation. That is,1 “ Q01 ´ tpS´1Q1 ` S0Q0q ´ tbS0Q0 ´ btS´1Q1“ p1´ atS0qQ0 ´ atS´1Q1 ,(2.15)and substitute this solution for tS´1Q1 in the previous equation. After some simplification, weobtain the cleaner master functional equationp1´ tSqQ´ pc´ txS´1qQ0 “ a . (2.16)The operator L is actually invertible, so this allows us to take a shortcut and not have to performthe extraction and substitution. To undo the multiplication with a, we just need to multiply termsby 1{a. Therefore, the inverse is L´1 “ 1 ´ crx0s, where c “ 1 ´ a. This allows us to write thefunctional equation aspL´1 ´ tESqQ “ a (2.17)and when we perform the extractions, we obtain Equation 2.16 directly, that is, the left-hand side isL´1Q´ tESQ “ pQ´ cQ0q ´ tpSQ´ xS´1Q0q “ p1´ tSqQ´ pc´ txS´1qQ0 . (2.18)10It might seem like a similar amount of work, but in higher dimensions we need to solve 2dequation by back-substitution to obtain shorter functional equation. For example, in [30, 21] theauthors had to perform the back-substitutions for a two-dimensional model. Using L´1 provides aneat shortcut because we do not have to do any substitutions. We have the following result.Proposition 2.2. Given a one-dimensional lattice walk model with small steps restricted to thenon-negative axis, the generating function Q satisfies the functional equationspL´1 ´ tESqQ “ a , (2.19a)p1´ tSqQ´ pc´ txS´1qQ0 “ a . (2.19b)We call them the operator equation and the master functional equation for the model, respectively.The operator notation/perspective is powerful. With it, we can derive functional equations formany lattice walk models in arbitrary dimensions with ease. Usually, derivations have employedinclusion-exclusion and careful book-keeping (Lemma 4 in [8, p. 10], [15, p. 58]) to write masterfunctional equations, or their precursors, in a direct manner. Unfortunately, that approach is difficultto generalize to arbitrary dimensions and more difficult restrictions/marking.We can also do the coefficient extraction in a neater way. Instead of extracting the xk coefficientfrom the master functional equation, it is better to first go through the operator equation, since rxksinteracts with L and E in a nice way. We haverx0sL´1 “ rx0s ´ rx0scrx0s “ rx0s ´ crx0s “ arx0s , (2.20a)rx0sE “ rx0s ´ rx0sxrxs “ rx0s . (2.20b)When we extract the x0 term from the functional equation, we haverx0spL´1 ´ tESqQ “ parx0s ´ trx0sSqQ “ rx0spa´ tSqQ . (2.21)Therefore, we have a functional equation for the first coefficient:rx0sp1´ atSqQ “ 1 . (2.22)We can perform the extraction immediately and it simplifies top1´ atS0qQ0 ´ atS´1Q1 “ 1 . (2.23)11Extracting higher coefficients is not difficult either. If k ě 1, we haverxksL´1 “ rxks ´ rxkscrx0s “ rxks , (2.24a)rxksE “ rxks ´ rxksxrxs “ rxks . (2.24b)When we apply the extractions on both sides of the functional equation, we obtainrxksp1´ tSqQ “ 0 , (2.25)and after we expand and simplify the expression, we havep1´ S0tqQk ´ tpS´1Qk`1 ` S1Qk´1q “ 0 . (2.26)Proposition 2.3. Let S “ S´1x` S0 ` S1x be the step polynomial for a lattice walk model on thenon-negative axis. Then the function Q0 and Qk for k ě 1 satisfy the equationsp1´ atS0qQ0 ´ atS´1Q1 “ 1 , (2.27a)p1´ S0tqQk ´ tpS´1Qk`1 ` S1Qk´1q “ 0 . (2.27b)2.2 Solving Functional Equations For Various Step SetsIf some steps in the step set of a model cannot be taken by walks, then we can remove them andobtain a simpler model with the same lattice walks and generating function. For one-dimensionalmodels with small steps we can identify three major cases: S “ δ or S “ δ ` x or S “ δ ` x` x.2.2.1 The S “ δ or S “ δ ` x CaseThe condition allows us to find Q0 directly from the rx0s equation. That is,Q0 “ 11´ aδt , (2.28)and we can substitute it into the master functional equation to derive the following result.Proposition 2.4. Let S “ δ or S “ δ ` x. Then the generating function isQpx, a; tq “ a1´ tSˆ1` b1´ aδt˙“ 1´ δtp1´ aδtqp1´ tSq . (2.29)12Something interesting starts to happen once we consider the relationship betweenQpx, a; tq andpQ “ Qpx, 1; tq, its version without interactions. We compute thatpQ “ 1p1´ tSq (2.30)and we have the relationp1´ aδtqQ´ p1´ δtq pQ “ 0 , (2.31)that we can rewrite as Bpp1 ´ aδtqQq “ 0 with the operator B “ 1 ´ rb0s, and similarly for Q0.We find a similar relationships exist for higher-dimensional lattice walk models too.Proposition 2.5. Let B “ 1 ´ rb0s and let Q be the generating function for a lattice walk modelwith S “ δ or S “ δ ` x. Then Q and Q0 both satisfy the equation Bpp1´ aδtqF q “ 0.2.2.2 The S “ δ ` x` x CaseTo derive the generating function in this case, we use the obstinate kernel method as detailed inSection 4.2 of [30, p. 12] and Section 4.1 of [21, p. 13] for two-dimensional models. In this method,we substitute an x value in the functional equation that eliminates the term p1´tSqQ. It is sufficientto find roots of the kernel K “ 1´ tS. The equation K “ 0 is quadratic in x and has the rootsσ “ 1´ δt´ap1´ δtq2 ´ 4t22tand σ˚ “ 1´ δt`ap1´ δtq2 ´ 4t22t, (2.32)which multiply to 1, so σ “ σ˚. Assuming that the substitution eliminates KQ, we find that´pc´ tσqQ0 “ a , (2.33)and using this relation, we can solve for Q explicitly. We computeQ “ a1´ tSˆ1´ tx´ ctσ ´ c˙“ t1´ tSˆx´ σb´ aσt˙. (2.34)Proposition 2.6. Let S “ δ ` x` x. Then the generating functions for this model areQ0 “ 1aσt´ b and Q “tpσ ´ xqp1´ tSqpaσt´ bq , (2.35)where σ “ p1´ δt`ap1´ δtq2 ´ 4t2q{p2tq.As before, we find a relation between functions for models with interactions and ones without.13Proposition 2.7. Let S “ δ ` x` x. Then Q and Q0 satisfy the equation Bppaσt´ bqF q.In this case we can use the algebraic kernel method to obtain a linear relation for Q0. Thismethod is used extensively in the quarter plane model classification [8]. Here we find a polynomialfpa, tq, for which BpfQ0q “ c, instead of zero. Note that K is invariant under the map ˚ : x ÞÑ xand we can write a second functional equation to complement the first. That is, we have the systemp1´ tSqQ´ pc´ txqQ0 “ a , (2.36)p1´ tSqQ˚´ pc´ txqQ0 “ a . (2.37)To eliminate theQ0 term ,we multiply the first equation by c´tx, the second by c´tx, and subtractone equation from the other. We divide everything by 1´ tS and the equation that remains ispc´ txqQpxq ´ pc´ txqQpxq “ atpx´ xq1´ tS “ aF , (2.38)where F does not depend on a. We apply rxs on both sides to find a relation between Q1 and Q0:cQ1 ´ tQ0 “ aF1 . (2.39)If we set a “ 1 here, we find that F1 “ ´t pQ0 and we can substitute that into the previous equation.After we multiply both sides by a, we find thatbQ1 “ tpaQ0 ´ pQ0q . (2.40)Earlier we had the equationp1´ aδtqQ0 “ 1` atQ1 , (2.41)which we can solve for Q1 and insert the solution into the equation above. That is,bpp1´ aδtqQ0 ´ 1q “ t2apaQ0 ´ pQ0q . (2.42)Collecting coefficients and simplifying the result lead to the equationpcp1´ aδtq ´ at2qQ0 ´ p´t2q pQ0 “c , (2.43)and therefore, fpa, tq “ cp1´ aδtq ´ at2.Proposition 2.8. Let S “ δ ` x` x. Then Bppcp1´ aδtq ´ at2qQ0q “ c.We obtained a slightly different relationships upon applying the operator B.142.2.3 ConclusionFor one-dimensional models with small steps restricted to the non-negative axis, we were able tofind explicit solutions for Q0 and Q and various relationships for Q and pQ with the operator B. Inhigher dimensions, the analysis is more difficult, but sometimes we see the same situation. In moredifficult examples, we only find a relationship between the function for walks returning to the originand its various partially-marked versions. Here is a table showing the results so far.S Q0 Q F pa, tqδ11´ aδt11´ aδt 1´ aδtδ ` x 11´ aδt1´ δtp1´ tpδ ` xqqp1´ aδtq 1´ aδtδ ` x` x 1aσt´ btpσ ´ xqp1´ tpδ ` x` xqqpaσt´ bq aσt´ bTable 2.1: Generating functions for walks with small steps on the non-negative half-line,where BpFQ0q “ BpFQq “ 0.15Chapter 3Higher-dimensional Lattice WalkModelsWe begin the exploration of higher-dimensional models by making some useful definitions. Hereare the main ingredients for a model set in Zd.• A fixed finite set S of steps for travel between points in the space. It can involve arbitrarily-many finitely-sized steps with multiplicities at least one. Its corresponding Laurent polyno-mial is denoted by S.• A regionD Ď Zd, where the walks are free to grow but not venture outside of the boundaries.This can be the whole space, an orthant, a semi-infinite strip, finite boxes, and so on.• A subregionD0 ofD, where interactions take place. To each point p, there is a correspondinglabel ap whose power we can increment upon visits to p. Common subregions D0 includethe origin, the axes in two dimensions, various higher-dimensional hyperplanes, a cone, aninfinite strip, the sides of a box and so on.• A set Q of initial walks that we can evolve. It has a corresponding generating polynomial q.We grow lattice walks from an initial conditionQ, with steps S, within D in Zd, while countinginteractions within D0. The four sets determine the model completely.Definition 3.1. A lattice walk modelM is characterized by the following four parts: S, D, D0, Q.Definition 3.2. The classical d-dimensional lattice walk model is one with small steps in the positiveorthant in Zd. The classical interacting model is one with interactions with the hyperplanes xk “ 0bounding the non-negative orthant, with labels ak.16Example 3.3. The one-dimensional models from the previous chapter are examples of classicalinteracting models. Here D is the set of non-negative integers, D0 is the point at the origin withlabel a, and Q is the empty walk. Finally, S is one of the subsets of t´1, 0, 1u.Example 3.4. Consider classical models with interactions in two dimensions. HereD “ tpx1, x2q PZ2 | x1, x2 ě 0u and D0 made up of the non-negative axes. Note that the origin is marked withboth labels a1 and a2. As in the previous example,Q is the empty walk and S is a set of small steps.In order to enumerate lattice walks and their properties, we make use a generating function thattracks quantities like length and ending position. Since the sets S and Q are finite, the number ofwalks of any given length is finite as well. Therefore, the coefficients ofQ are Laurent polynomials.Definition 3.5. The generating function Q associated with a lattice walk model counts walks’lengths with t, ending locations with xi’s, and interactions withD0 with some variables a. We writeQ “ Qpx1, . . . , xd, a; tq “8ÿk“0qkpx1, . . . , xd, aqtk , (3.1)where the coefficients qk are Laurent polynomials in the x and a variables.Example 3.6. We examine the simplest kind of model — one whereD is the whole space, there areno interactions, and Q consists of the empty walk. Since the lattice walks can pick any step fromthe step set S, the walks of length one are enumerated via tS, the walks of length two, via t2S2, andso on, where S “ Spx1, . . . , xdq. Then the full generating function isQpx1, . . . , xd; tq “ 1` St` S2t2 ` ¨ ¨ ¨ “ 11´ St . (3.2)Example 3.7. Let S “ tNE, NW, SE, SWu, that is, S “ px1 ` x1qpx2 ` x2q. The only walk oflength one has monomial x1x2t. When we grow it, the walk can take any of the four steps, soQ “ 1` x1x2t` pa1 ` x1qpa2 ` x2qt2 ` ¨ ¨ ¨ . (3.3)We can extract coefficients too. For example, the walks ending on the x1 axis are given by settingx2 “ 0 or extracting the x02 coefficient. That is,rx02sQ “ 1` a2pa1 ` x1qt2 ` ¨ ¨ ¨ (3.4)and the walks returning to the origin are given byrx01x02sQ “ 1` a1a2t2 ` ¨ ¨ ¨ . (3.5)17It is difficult to do the analysis of classical higher-dimensional models without extra notation. Infact, the use of better notation paved the way to finding the operators and the functional equations.We usually see multi-index notation in the multivariate setting, but this is not sufficient for workingwith restricted regions, where some variables are missing. We have the following notation.Definition 3.8. Let 0 :“ p0, . . . , 0q and ˘1 :“ p˘1, . . . ,˘1q, where we have as many terms inthese sequences as needed in the specific context. Also, let rns “ t1, . . . , nu.Definition 3.9. Let x1, . . . , xd be indeterminates and let I “ pi1, . . . , imq and J “ pj1, . . . , jmq besequences of positive integers. Define the monomial xJI asxJI “ xj1i1 ¨ ¨ ¨xjmim , (3.6)with special cases x0I “ 1 and x1I “ xI and x´1I “ 1{xI “ xI . The coefficient extraction and termextraction operators are defined asrxJI sF “ rxj1i1 ¨ ¨ ¨xjmim sF “ F JI and rrxJI ss “ xJI rxJI s , (3.7)with special cases F JI “ F if I is empty, and F JI “ FJ if I is the full set of variables.Example 3.10. In the previous example we had rx02sQ “ Q02 and rx01x02sQ “ Q0,01,2. Furthermore,we have S˘1,˘11,2 “ 1 andS´11 “ rx1spx1 ` x1qpx2 ` x2q “ x2 ` x2 . (3.8)Because there are different variables involved, there may be some ambiguity in the result, de-pending on the order of extraction. We always perform coefficient extractions with respect to the xor a variables by first expanding any series in t, and then applying the extraction on the coefficients.Definition 3.11. Suppose that Γ is an operator involving x and a variables but not t. We apply Γon power series F “ ř8k“0 fktk in the following way:ΓF “8ÿk“0Γpfkqtk . (3.9)Definition 3.12. Given a label a, we let b “ a´ 1 and c “ b{a “ 1´ a. Also, aI extends like xI .Example 3.13. Here we derive the two-dimensional functional equation for classical interactingmodels, without the use of inclusion-exclusion or using case-by-case analysis to find a shorter equa-18tion. As in the one-dimensional case, we can grow the lattice walks by multiplying qkby S. Thenwe use an operator Γ that can fix the terms in Sqk, so we obtain the equation p1´ tΓSqQ “ 1.To find Γ, we make use of the following observation. Since E “ 1´ rrxss is idempotent, that isE2 “ E, this means that once we remove certain terms via E, we do not remove them again withrepeated application. Therefore, we can remove terms with negative x1 coordinate first, and oneswith negative x2 coordinate second, and the inclusion-exclusion is encoded inside the operators. Wefind that E “ E1E2, where Ek “ 1´ rrxkss. Multiplying these out, we find thatE “ 1´ rrx1ss ´ rrx2s ` rrx1x2ss . (3.10)Analogously, the marking operator is L “ L1L2, where Lk “ 1` bkrx0ks, and finally, we havethe equation pL´1´ tESqQ “ a1a2 since L is invertible. If we expand the expressions, we find thatQ “ 1` tSQ´ tx1S´11 Q01 ´ tx2S´22 Q02 ` tx1x2S´1,´11,2 Q0,01,2 . (3.11)Contrast this notation to the one in [8, p. 10]. For d-dimensional models, one can write down thefunctional equation as a sum over subsets of t1, . . . , du, as in the the non-interacting case in Equa-tion 5.1 in [15, p. 58], but this becomes difficult if we work with interactions. To add interactions,we have to modify the non-interacting functional equation. This has been done for two-dimensionalmodels in Section 3 of [30, p. 7] and Section 3.2 of [21, p. 11], where the authors add terms likepa1 ´ 1qT , where T is an expression involving extractions of Q and S. Instead of doing that, weuse the operator notation to handle the problem in a more efficient manner.3.1 Using Operators to Derive the Functional EquationAs we have seen in the previous example, it is not difficult to generalize the derivation of the func-tional equations if we use operators. The derivation of general case for d dimensions is analogousto the one in the example, so we omit most of it. In d dimensions, the interactions take place on thehyperplanes where xk “ 0, so we use the labels ak to mark those interactions. The operators hereare L “ L1 ¨ ¨ ¨Ld and E “ E1 ¨ ¨ ¨Ed, where order does not matter. We have L´1p1q “ ards, sinceeach operator L´1i marks a constant term with ai. Or in operator notation,L´1p1q “ p1´ c1rx01sq ¨ ¨ ¨ p1´ cdrx0dsqp1q “ÿIĎrdsp´1q|I|cI “ ards . (3.12)The higher-dimensional functional equation for the classical interacting model is given as follows.19Theorem 3.14. The classical interacting lattice walk models in d dimensions have generating func-tions Q satisfying the functional equationsp1´ tLESqQ “ 1 , (3.13)pL´1 ´ tESqQ “ ards , (3.14)where L, E and L´1 are of the form Γ “ Γ1 ¨ ¨ ¨Γd.The second functional equation has a lot fewer terms. To see this, we examine at the operatorLkEk “ 1` bkrx0ks ´ xkrxks . (3.15)Once we apply it in the functional equation, the number of terms increases by a factor of three, soin the end we have 3d different Q terms. On the other hand, if we apply L´1 on both sides of theequation, we only introduce 2d new terms but they are the same as the ones generated by E. Theresulting equation only has 2d terms Q, one for each subset I Ď rds. That is,L´1Q “ p1´ c1rx01sq ¨ ¨ ¨ p1´ cdrx0dsqQ “ÿIĎrdsp´1q|I|cIQ0I , (3.16a)ESQ “ÿIĎrdsp´1q|I|xIrxIspSQq “ÿIĎrdsp´1q|I|xIS´1I Q0I , (3.16b)where rxsSQ “ S´1I Q0I , since QPI “ 0 for any set P with more than one negative term. Finally,ÿIĎrdsp´1q|I|pcI ´ txIS´1I qQ0I “ ards . (3.17)Finally, we can write the master equation in d dimensions.Theorem 3.15. Let KI “ cI ´ txIS´1I for subsets I of t1, . . . , du. Then the generating function fora classical interacting d-dimensional lattice walk model satisfies the equationÿIĎrdsp´1q|I|KIQ0I “ ards . (3.18)Note that KH “ K here. Also, Equation 5.1 of [15, p. 58] is the non-interacting version of ourequation, and in our notation it can be written asKQ´ÿH‰IĎrdsp´1q|I|xIS´1I Q0I “ 1 . (3.19)203.2 Coefficient ExtractionsIn this section, we show how the operators L and E interact nicely with basic coefficient extractionto produce more equations. It is esier to use the operator form of the functional equation in orderto extract coefficients, than it is to use the explicit form. This makes for easier manual derivation,since we need to obtain functional equations for Q0I for I Ď rds like in the one-dimensional case.3.2.1 Using Operator Notation For Fast Coefficient ExtractionWe can obtain further functional equations with less variables by extracting the x0I coefficient fromthe master equation. The operator rxki s commutes with operators Mj “ L´1j and Ej when j ‰ i, sowe only need to consider the action on Mi and Ei. Similarly to Equation 2.20 and Equation 2.24,in the two-dimensional setting we haverxki sMi “ aδpk,0qi rxki s and rxki sEi “ rxki s . (3.20)Therefore, the operator rxki s eliminates both Mi and Ei modulo ai for rx0i sMi. If we extract the x0Icoefficient from the functional equation for I Ď rds, we haverx0I sards “ ards “ rx0I spMrds ´ tErdsSqQ“ `aIMrdszIrx0I s ´ tErdszIrx0I sS˘Q“ rx0I spaIMrdszI ´ tErdszISqQ ,(3.21)so thatardszI “ rx0I spMrdszI ´ aItErdszISqQ . (3.22)If we use the more general operator rx0IxPJ s, where P is a nonempty sequence of positive integersand I Y J “ K with no overlaps, through the same process as before we find the equationrx0IxPJ spMrdszK ´ aItErdszKSqQ “ 0 . (3.23)We perform the extractions explicitly in order to obtain equations like 3.16. First,rx0I sSQ “ S0IQ0I `RI , (3.24)where RI is a collection of S´PI QPI terms that involve sets P with some non-zero entries. When wesubstitute this term into Equation 3.22, we find that21ardszI “MrdszIrx0I sQ´ aItErdszIrx0I spSQq“MrdszIQ0I ´ aItErdszIpS0IQ0I `RIq“ pMrdszI ´ aItErdszIS0I qQ0I ´ aItErdszIRI .(3.25)We can rewrite this aspMrdszI ´ aItErdszIS0I qQ0I “ aIpards ` tR1Iq , (3.26)where R1I “ ErdszIRI . We compute the termsMrdszIQ0I “ÿJĎrdszIp´1q|J |cJQ0,0I,J , (3.27a)aItErdszIS0IQ0I “ÿJĎrdszIp´1q|J |aItxJS0,´1I,J Q0,0I,J , (3.27b)and rewrite the functional equation asÿJĎrdszIp´1q|J |pcJ ´ aItxJS0,´1I,J qQ0,0I,J “ aIpards ` tR1Iq . (3.28)Definition 3.16. For positive integer sets I and J that do not share any elements, we haveKJpIq “ cJ ´ aItxJS0,´1I,J . (3.29)I “ H, then KJpIq “ KJ . Equivalently, KJpIq “ rx0I sKJpaItq.Lemma 3.17. Let I be a subset of t1, . . . , du. Then the generating function Q0I for the classicalinteracting d-dimensional lattice walk model satisfies the functional equationÿJĎrdszIp´1q|J |KJpIqQ0,0I,J “ ardszI ` aItR1I , (3.30)where the R1I term only involves higher-order coefficient extractions from Q.This is a clean way to write down all the equations for Q0I in a unifying way. To find R1I , weexpand R1I “ ErdszI , where RI is a sum of terms S´PI QPI for various sets P of size |I| with non-negative entries, where not all of them are zero. Also, note that QPI “ 0 whenever P has negativeentries because QPI enumerates valid walks only. Let sq “ S´PI QPI . Then22Ejsq “ sq ´ xjpsqq´1j “ sq ´ xjs´1j q0j (3.31)and thus,EKsq “ÿJĎKp´1q|J |xJs´1J q0J . (3.32)This allows us to derive the following explicit form of R1I .Proposition 3.18. The functions R1I are given byR1I “ÿJĎrdszIp´1q|J |ÿPS´P,´1I,J QP,0I,J , (3.33)where the sum is over sets P with non-negative entries where some of them are positive.Of course, when d “ 1 or d “ 2, we do not need the full generality of the formula, but forhigher dimensions, it would be tedious to write the equations by hand without it.3.2.2 Kernel FormsWe can write out the functional equations in a way that highlights the role of the kernel K:p1´ tLESqQ “ LEKQ` p1´ LEqQ “ LEKQ` p1´ LqQ , (3.34)where EQ “ Q since there are no walks outside ofD. Setting all the ak’s to 1 in the last expressionis equivalent to removing the marking operator, that is, we have the equation, EpKQq “ 1, for anon-interacting model, and its form suggests that we use the following substitutionQ “ Wx1 ¨ ¨ ¨xdK . (3.35)We multiply both sides of the equation by x1 ¨ ¨ ¨xd and obtainx1 ¨ ¨ ¨xd “ x1 ¨ ¨ ¨xdEpKQq “ x1 ¨ ¨ ¨xdEpx1 ¨ ¨ ¨xdW q “ E1W , (3.36)where E1 “ E11 ¨ ¨ ¨E1d andE1k “ xkEkxk “ xkp1´ xkrxksqxk “ 1´ rx0ks . (3.37)23Proposition 3.19. Let Q be the generating functions for a classical model in the positive orthant.Then the function W “ x1 ¨ ¨ ¨xdKQ satisfies the equationE1W “ÿIĎrdsp´1q|I|W 0I “ x1 ¨ ¨ ¨xd . (3.38)andQ “ 1x1 ¨ ¨ ¨xdK¨˝x1 ¨ ¨ ¨xd ´ÿH‰IĎrdsp´1q|I|W 0I ‚˛ . (3.39)Example 3.20. In two dimensions, the equation the generating function is given byQpx1, x2q “x1x2 `W 01 px2q `W 02 px1q ´W 0,01,2x1x2p1´ tSq . (3.40)Example 3.21. Consider the one-dimensional model on the non-negative line with S “ x`x. Herethe solution for the interacting version of the model is given byQ “ tpσ ´ xqp1´ tSqpaσt´ bq , (3.41)so when we set a “ 1 and simplify the expression, we find that the generating function for thenon-interacting model is given bypQ “ x´ σxp1´ tSq , (3.42)as predicted by the analysis of this section. Here W0 “ σ.Interestingly enough, applying the derivatives B1 and B2 on both sides of the equation E1W “x1x2 leads to the PDE B1B2W “ 1 and a similar relationship exists in higher dimensions.Proposition 3.22. The generating function for a classical d-dimensional model satisfies the PDEB1 ¨ ¨ ¨ Bdpx1 ¨ ¨ ¨xdKQq “ 1 . (3.43)The results in this section are not difficult to generalize. We obtain a similar result if we uselarger steps or include interactions. We just need to pre-multiply both sides of the equation by ahigher order monomial xPrds and apply enough partial derivatives BNI .243.3 First Solutions3.3.1 Formal Neumann Series and Hadamard ProductsFormally, we can expand the operator p1 ´ tΓSq in Neumann series and express the generatingfunctions asQ “8ÿk“0tkpΓSqkp1q , (3.44)where pΓSqkp1q indicates repeated application of ΓS on 1. This gives us an explicit expression forQ that we can manipulate, but it is not a complete solution because we still need to compute theterms pΓSqk. However, this form allows us to derive a curious result that falls out of the operator no-tation — how we can build generating functions for some higher-dimensional models by Hadamardproducts of lower-dimensional ones.In Section 5 of [18, p. 14], the authors find solutions for non-interacting models with steppolynomials of the formSpx1, x2q “ S0px1q ` S1px1qS2px2q . (3.45)Here we find a similar result for the simpler case S “ S1px1qS2px2q, but with interactions, and itsgeneralization to higher dimensions.Example 3.23. When S “ S1px1qS2px2q the operator ΓS factors asΓS “ Γ1Γ2S1S2 “ pΓ1S1qpΓ2S2q , (3.46)since Γ2 does not interact with S1 and the operators commute. ThenpΓSqk “ pΓ1Γ2S1S2qk “ pΓ1S1qkpΓ2S2qk (3.47)and we use the Neumann series to findQ “8ÿk“0tkpΓSqk “8ÿk“0tkpΓ1S1qkpΓ2S2qk “˜ 8ÿk“0tkpΓ1S1qk¸d˜ 8ÿk“0tkpΓ2S2qk¸, (3.48)25where d denotes the Hadamard product of two power series with respect to t. By usingQipai, xi; tq “8ÿk“0tkpΓiSiqk (3.49)and reversing the iteration, we reach the functional equations p1 ´ tΓiSiqQi “ 1 for each i, whereQi is the generating function for a one-dimensional model with step set Si. Now, Q is expressed asQpa1, a2, x1, x2; tq “ Q1pa1, x1; tq dQ2pa2, x2; tq . (3.50)Example 3.24. Once we know the form of the solution, we can prove that it works by a methodthat does not use the series solution. Suppose that Qi is the solution of the functional equationpL´1i ´ tEiSiqQi “ ai (3.51)for i “ 1 and i “ 2. We show that Q “ Q1 dQ2 is a solution of the functional equationpL´1 ´ tESqQ “ a1a2 . (3.52)Since the operators act by multiplication of terms, they can be moved over the Hadamard product ifthey do not affect the variables of one of the functions. That is,pL´1 ´ tESqQ “ L´1pQ1 dQ2q ´ tESpQ1 dQ2q“ pL´11 Q1 d L´12 Q2q ´ tppE1S1Q1q d pE2S2Q2qq .(3.53)Then we substitute L´1i Qi “ ai ` tEiSiQi into the first term and expand it to findpL´11 Q1 d L´12 Q2q “ pa1 ` tE1S1Q1q d pa2 ` tE2S2Q2q“ a1 d a2 ` a1 d ptE2S2Q2q ` a2 d ptE1S1Q1q` ptE1S1Q1q d ptE2S2Q2qq .(3.54)The last term cancels and for each i we haveai d ptEjSjQjq “ airt0stEjSjQj “ 0 , (3.55)so we are done.26Lemma 3.25. Let S “ S1S2, where Si “ Sipxiq and consider the classical interacting models withthose step sets and generating functions Q, Q1 and Q2. ThenQpx1, x2, a1, a2; tq “ Q1px1, a1; tq dQ2px2, a2; tq . (3.56)This identity serves as the base case for the following general case.Theorem 3.26. Let S “ S1 ¨ ¨ ¨Sr, where Si and Sj do not share variables when i ‰ j, and considerthe classical interacting models with those step sets and generating functions Q, Q1, . . . , Qr. ThenQ “ Q1 d ¨ ¨ ¨ dQr.Example 3.27. Consider the two-dimensional model with S “ px1 ` x1qpx2 ` x2q, which wediscuss more in Chapter 5. The one-dimensional models are the same and have solutionsrQ0 “ σat´ bσ and rQ “ tpx´ σqxp1´ tpx` xqpat´ bσq , (3.57)whereσ “ 1´?1´ 4t22t. (3.58)We can expand and simplify rQ0 and rQ to findrQ0 “ 2´ a´ a?1´ 4t22p1´ a` a2t2q , (3.59)rQ “ pp1´ aqx` pa´ 2qt` 2axt2q ` pat` p1´ aqxq?1´ 4t22p1´ a` a2t2qpx´ t´ tx2q . (3.60)We have the expansionrQ “ 1` xt` pa` x2qt2 ` xp1` a` x2qt3 ` ¨ ¨ ¨ (3.61)and finally,Qpx1, x2, a1, a2; tq “ rQpx1, a1; tq d rQpx1, a2; tq“ 1` x1x2t` pa1 ` x21qpa2 ` x22qt2` x1x2p1` a1 ` x21qp1` a2 ` x22qt3 ` ¨ ¨ ¨ .(3.62)However, obtaining a closed form for the function via the Hadamard product seems to be difficult.The function is not algebraic since the unmarked variant is not algebraic either; see [8, p. 26].However, the function Q is D-finite since both functions in the product are.273.3.2 Reducible Models and Groups For Walks With Small StepsAs observed in [8, p.5] and already mentioned in Chapter 2, if the model has some steps that cannotbe used in the construction of lattice walks, then we can safely remove them from the step set, andwe still have the same generating function enumerating the lattice walks. This makes it easy to findQ for many models. This idea works for any step set and any regional constraints, so we make it adefinition.Definition 3.28. For a model with step set S, let S 1 consist of all steps that can be taken by walksin the model. We call S 1 a minimal step set. A model is reducible if S 1 is a proper subset of S.Proposition 3.29. The full generating function for a model is the same whether we use S or S 1.It should be easier to find Q if we have more functional equations and cancel out some of theterms. One way to find more equations is to apply a transformation on the tuple px1, . . . , xdq thatleaves intact as many parts of the functional equation as possible but still adds some information inthe form of a non-equivalent equation. This leads to the orbit summation method, a fruitful approachin the non-interacting case. See [8, p. 11] for details. We present it here as well.We map each x1, . . . , xd to some functions separately and then examine the group generatedby such maps. We often eliminate the kernel in front of Q in order to find equations for the ex-tracted forms of Q, so it is useful to consider transformations that preserve the kernel. We call thisgroup GpKq, although it is not the full group of rational transformations preserving the kernel. Forexample, a lot of the time px1, x2q ÞÑ px2, x1q is not in the group, but it is a valid transformationpreserving the kernel. If a transformation on px1, . . . , xdq preserves the kernel K “ 1´ tS, then itmust also preserve the step polynomial S. We can write S asS “ S´1k xk ` S0k ` S1kxk (3.63)for some k from 1 to d. We send xk ÞÑ yk and solve Spxkq “ Spykq for yk to determine the possibletransformations we can perform. After some simplification, we obtain the equationpS´1k ´ S1kxkykqpyk ´ xkq “ 0 (3.64)and we have three cases depending on which ones of S´1k and S1k are zero.1. If both are zero, the equation is trivially-true and all transformations preserve the kernel.2. If only one is zero, then yk “ xk and only the identity transformation preserves the kernel.3. If neither one is zero, we have yk “ xk or yk is the involution yk “ xkS´1k {S1k .28Case one and two are mostly trivial and we find properties of the generating function right away.1. If S´1k “ 0 and S1k “ 0, then S “ S0k and the model lives on the xk “ 0 hyperplane. There-fore, the model is equivalent to a lower-dimensional one with no xk coordinate. If qptq is thegenerating function in the latter case, then the earlier one is given by Qpxk, ak; tq “ qpaktq,where the rest of the variables have been suppressed. We can also find this solution from thefunctional equation directly. Let M “ M 1Mk and E “ E1Ek. Then by Equation 3.22 andthe observation that rx0ksSQ “ SQ and rx0ksQ “ Q, we havepM 1 ´ aktE1SqQ “ ardsztku , (3.65)This is just an equation for a pd´ 1q-dimensional model with an extra scaling of t by ak.2. If S´1k ‰ 0 and S1k “ 0, then the model is reducible to one with S “ S0k .3. If S´1k “ 0, S0k “ 0 and S1k ‰ 0, then the walks in the model leave the xk “ 0 hyperplane andnever return. Here we have an essentially lower-dimensional problem as well, since we haveS “ S1kxk. If the generating function for the lower-dimensional problem is qptq, then thegenerating function for this model is Qpxk, ak; tq “ qpxktq, where the rest of the variableshave been suppressed. We can also derive this result from the functional equation.All the other cases are more complicated and require more careful analysis. We can define a groupGS of the nontrivial transformations.Definition 3.30. Let GS be the group generated by nontrivial gk that preserve the polynomial S.It is easy to see that there are infinitely many such groups, just consider S “ śdk“1pxk ` xkqwith gkpxkq “ xk. The group here has order 2d. The orders of the finite groups set in 2 dimensionsare 1, 2, 4, 6 and 8, from Theorem 3 in [8, p. 8]. If we were to consider walks with multiple copiesof some steps, we could obtain even larger group orders as seen in Section 7 of [11, p. 11]. Thed-dimensional groups defined above are Coxeter groups — a generalization of the dihedral groupsencountered in two-dimensional models. Coxeter groups are defined as follows.Definition 3.31. A Coxeter group is defined asG “ xr1, . . . , rd | prirjqmi,j “ 1y , (3.66)where mi,i “ 1, and mi,j ě 2 for all i ‰ j. Here mi,j can be infinite.29We call these r’s reflections and when mi,j “ 2, they commute. Also, mi,j “ mj,i. The rankof G is the number of generators in this specific representation of G. Often G has more than onerepresentation with different numbers of generators. We can draw a graph for each Coxeter groupby going through the following steps.• Label vertices with the generators of G.• Connect the vertices gi and gj if mi,j ě 3.• Label the edges with mi,j if mi,j ě 4.If the graph has different components, the group factors as a direct product of Coxeter groups,represented by the individual components. We can see this in terms of the step polynomial S.Proposition 3.32. Let S “ TR with corresponding groups GS , GT and GR, where T and R do notshare variables. Then GS “ GT ˆGR.Proof. For some xi in the polynomial T , we haveSji “ rxji sS “ Rrxji sT “ RT ji (3.67)and therefore,gipxiq “ xiT´1i RT 1i R“ xiT´1iT 1i. (3.68)Similarly, gjpxjq “ xjR´1i {R1i where xj is some variable in R. Furthermore, gi and gj commutesince they do not share variables. Since i and j are arbitrary, the generators from different setscommute and the Coxeter graph of the group has two components, one associated with each factor.That is, the group itself factors as stated.3.4 Specializing to Two DimensionsUntil the end of the chapter we focus on two-dimensional models with interactions. We can setd “ 2 in Equation 3.18 and Equation 3.30 to find the two-dimensional master functional equations.30Corollary 3.33. The generating functions for classical interacting two-dimensional models satisfythe functional equationsKQ´K1Q01 ´K2Q02 `K1,2Q0,01,2 “ a1a2 ,p1´ ta1S01qQ01 ´ pc2 ´ ta1x2S0,´11,2 qQ0,01,2 ´ a1tpS´11 Q11 ´ x2S´1,´11,2 Q1,01,2q “ a2 ,p1´ ta2S02qQ02 ´ pc1 ´ ta2x1S´1,01,2 qQ0,01,2 ´ a2tpS´12 Q12 ´ x1S´1,´11,2 Q0,11,2q “ a1 ,p1´ a1a2tS0,01,2qQ0,01,2 ´ ta1a2tpS´1,´11,2 Q1,11,2 ` S´1,01,2 Q1,01,2 ` S0,´11,2 Q0,11,2q “ 1 .(3.69)3.4.1 First Examples in the PlaneWhile the classical two-dimensional models have been studied extensively, their interacting versionshave not. We want to extend the non-interacting methods to the interacting setting and if they turnout to be insufficient, create new ones. Since the generating functions for the interacting modelsneed to reduce to those for the non-interacting models, we do not expect to find closed form solutionsfor Q for all models. In fact, some of the classical models lead to non-D-finite generating functions,so their interacting counterparts are not D-finite either.For the rest of the models, we hope to find one of the functions Q and Q0,01,2 explicitly, but thisappears to be difficult in most nontrivial cases. Recent research has shown that sometimes relation-ships exist between Q or Q0,01,2 and their partially-marked versions [30]. As we saw in the previouschapter, the one-dimensional models admit a linear relationship with polynomial coefficients. Thereare also two other two-dimensional models that exhibit a rational relationship. However, there maybe models where neither a linear nor a rational relationship exists. In this section we cover the firstfew examples of quarter plane models with interactions.Our first task is to find all the reducible models and we can do this by looking at which of thesteps tN, NE, Eu they have in their step set.1. There are 32 reducible models, where none of the three steps are present and walks cannotleave the origin.Figure 3.1: Set of steps allowed in models that do not leave the origin.312. There is a 2 ¨ 24 “ 16 reducible models with an N step or an E step, where the models areequivalent to one-dimensional ones.Figure 3.2: Sets of steps allowed in models with an N step or an E step.3. There are two or more steps from tN, NE, Eu or NE Ď S. In this case, the models featurewalks that leave both axes and once that happens, such walks can use any step from the stepset. Therefore, these models are irreducible.Cases 1 and 2 contain all of the quarter plane models reducible to one-dimensional models. Welook at the case of a model equivalent to a one-dimensional model along the x2 axis. From theanalysis in the previous section, since both S´11 “ 0 and S11 “ 0, we have the first situation. If thesolution to the one-dimensional problem is qpx, a; tq “ qpx2, a2; tq, then the solution to the modelsin cases 1 and 2 is Qpx1, x2, a1, a2; tq “ qpx2, a2; a1tq. To see it in another way, consider thepolynomial S itself in the reduced models. Since S factors, the function Q is a Hadamard productbetween two one-dimensional models.Definition 3.34. Let Bk be the operator 1´ rb0ks and B “ B1 ¨ ¨ ¨Bd.Since the models are essentially one-dimensional , we also have a linear relationship using theoperators B1 and B2. If fpa, tq is the function that goes together with qpx, a, tq, then the functionF pa1, a2, tq that goes together with Qpx1, x2, a1, a2, tq is given byF pa1, a2, tq “ fpa2, a1tq . (3.70)Then we have B2pFQq “ 0 and consequently, B1B2pFQq “ 0. We wrap this section up with thefollowing proposition.Proposition 3.35. All 64 reducible models are equivalent to ones confined to an axis. Their gener-ating functions Q and their functions F , such that BpFQq “ 0, are given by one-dimensional oneswith t scaled by one of a1 or a2.323.4.2 Kernel Group ConsiderationsWe can also partition the models with respect to their groups G, that is, we write “case i.j” whenwe have case i for g1 and case j for g2, and it is equivalent to case j.i. From previous sections, cases1.j are comprised of reducible models, so we can skip them. We are left with the following cases.Case 2.2: In this case both transformations are the identity, so for each k, S´1k or S1k is zero. If S1k “ 0for some k, the model is reducible and therefore, already solved for. The only remaining caseis when both S´1k “ 0 and S1k ‰ 0 for each k. The only valid models are ones with steps intN, E, NEu, where we need to have positive x1 and x2 coordinates. Here are the models.Figure 3.3: Step sets for classical two-dimensional models coming from case 2.2.Case 2.3: In this case, the transformation for x1 is trivial and the one for x2 is g2. Therefore, S´11 “ 0 orS11 “ 0, but not both. The first case is reducible, so we only consider the second. Furthermore,S´12 ‰ 0 and S12 ‰ 0, so there must be at least one step in the positive x2 direction and one inthe negative x2 direction. If both NE and SE are in S, then we have 8 cases. If one of NE andSE is in S, but not both, then we have 8 more cases. Finally, if neither is in S, the other threesteps must be present in order to satisfy the conditions. We have 17 cases in total and all themodels are irreducible.Figure 3.4: Step sets for classical two-dimensional models coming from case 2.3.Case 3.3: This is the most interesting case, with two transformations for x1 and x2 each. Thus, theremust be at least one step going in a positive and one going in a negative direction, for each ofx1 and x2. If we look at which diagonal steps are present, similarly to case 2.2, we find thatthere are 145 such models. Previous results show that the group GpKq has orders 4, 6, 8 andinfinity, depending on the step set in question. All of these cases are irreducible.333.5 Solving Basic Two-dimensional Models3.5.1 Case 2.2 – Group of Order OneThe only irreducible models of this type are ones with S´11 “ 0 and S´12 “ 0. HereS “ δ ` αx1 ` βx2 ` γx1x2 (3.71)for some α, β, γ and δ. The functional equation and its zeroth coefficient extractions are given byp1´ tSqQ´ c1Q01 ´ c2Q02 ` c1c2Q0,01,2 “ a1a2 ,p1´ ta1pδ ` βx2qqQ01 ´ c2Q0,01,2 “ a2 ,p1´ ta2pδ ` αx1qqQ02 ´ c1Q0,01,2 “ a1 ,p1´ a1a2tδqQ0,01,2 “ 1 .(3.72)This is a linear system for Q0,01,2, Q01, Q02 and Q, and by back-substitution,Q “ 11´ tSˆa1a2 ` 11´ ta1a2δˆc11´ a1δt1´ ta1S01` c2 1´ a2δt1´ ta2S02´ c1c2˙˙(3.73)“ 11´ tSˆa1a2 ` 11´ a1a2δtpc1f1pa1, tq ` c2f2pa2, tq ´ c1c2q˙. (3.74)Note how Q depends on functions fi that are each missing one of the a variables. We shall see thatthe linear relation BpFQq “ 0 is satisfied by the functionF pa1, a2, tq “ 1´ a1a2δt . (3.75)First,Bpp1´ a1a2δtqa1a2q “ a1a2 ´ a2 ´ a1 ` 1 “ c1c2 , (3.76)Bpc1f1 ` c2f2 ´ c1c2q “ c1f1 ` c2f2 ´ c1c2 ´ c2f2 ´ c1f1 “ ´c2c2 . (3.77)Putting the two quantities together, along with dividing by 1 ´ tS, shows that BpFQq “ 0. Ofcourse, this works for Q0,01,2 too.343.5.2 Case 2.3 – Group of Order TwoIn this case only S´11 is zero, so the functional equations arep1´ tSqQ´ c1Q01 ´ pc2 ´ tx2S´11 qQ02 ` c1c2Q0,01,2 “ a1a2 ,p1´ ta1S01qQ01 ´ pc2 ´ ta1x2S0,´11,2 qQ0,01,2 “ a2 ,p1´ ta2S02qQ02 ´ c1Q0,01,2 ´ a2tS´12 Q12 “ a1 ,p1´ a1a2tS0,01,2qQ0,01,2 ´ ta1a2S0,´11,2 Q0,11,2 “ 1 .(3.78)We can identify a subproblem that is essentially one-dimensional and therefore, already solved. Tosee this, take the second and fourth equations, and make the six substitutions ai “ a, ci “ c, x2 “ x,a1t “ τ , S01 “ T and Q01px2q “ qpxq. The two equations becomep1´ τT qq ´ pc´ τxT´1qq0 “ a , (3.79)p1´ aτT0qq0 ´ aτT´1q1 “ 1 . (3.80)We can see that this is a one-dimensional problem again. The solution here is qpx, a; τq, obtainedby the methods in the previous chapter, so the original problem has solutionsQ01px2q “ qpx2, a2; a1tq and Q0,01,2 “ q0pa2; a1tq . (3.81)Since Q0,01,2 and Q01 are given by a one-dimensional model’s solution, they have a linear relationshipwith their partially-marked versions. Next, we rewrite the master equation asp1´ tSqQ´ pc2 ´ tx2S´12 qQ02 “ a1pa2 ` b1q ´ b1c2q0q “ a1φpx2q . (3.82)Since S´11 ‰ 0 and S12 ‰ 0, we have a root x2 “ σ2 that allows us to eliminate the p1´ tSqQ term.That is, we are finding a root for x2 again, since x “ x2 in the previous equations. We find thatQ02 “ ´ a1φpσ2qc2 ´ tσ2S´12(3.83)andQ “ 11´ tS˜a1φpx2q ´ c2 ´ tx2S´12c2 ´ tσ2S´12a1φpσ2q¸. (3.84)35We can simplify this form based on what q and q0 are from the one-dimensional setting. After aquick computation, we have Q02 “ a1a2φpσ2q pQ02 and we can writeKQ “ a1φ`K2a1a2φpσ2q pQ02 , (3.85)K pQ “ a2 `K2 pQ02 . (3.86)Therefore, after expanding the definitions of the various quantities, we haveKQ´ a1a2φpσ2qK pQ “ a1pφ´ φpσ2qq “ c1pq ´ qpσ2qq (3.87)Since q “ qpx2, a2; a1tq, there is a function f depending on a’s and t only, for which B2pfqq “ 0.The same function works for qpσ2q as well. Finally, there is a linear relationship between Q andits various partially-interacting versions. This time it seems that the relationship is not given byBpFQq “ 0 but rather a more complicated one, B2pfgpB1pQ{gqqq “ 0, where g “ a1a2φpσ2q.Finally, we can give the following theorem.Theorem 3.36. Reducible classical two-dimensional models and ones with group order one or twohave generating functions with linear relations with their partially-interacting variants.Miscellaneous CaseThere is one case with an infinite group that is both easy to solve and irreducible — the model withS “ x1x2 ` x1x2. The transformations are g1 “ x1x22 and g2 “ x2x21. If we apply them onpx1, x2q in an alternating sequence, each time the absolute powers of x1 and x2 increase in one ofthe coordinates, and therefore, the group is infinite. However, this case is easy to solve because themodel is essentially one-dimensional . It is equivalent to the model on the non-negative line withS “ x` x and marking visits to the origin with a, where x “ x1x2 and a “ a1a2. The solution isQpx1, x2, a1, a2; tq “ qpx1x2, a1a2; tq (3.88)and we can add this model to the theorem as well.3.5.3 Counting Classes of ModelsHere we tally all the models on the quarter plane. We have 64 reducible models, 5 new cases withgroup of order one and 34 new cases with group of order two. Also, there are 29 models with groupof order four, 6 with order six, and 4 with order eight, plus one easy case with infinite group. Sofar we have 143 cases of models we can solve easily or models with a finite group, some of which36we can solve easily. Next, by inspection of Table 4 in [8, p. 28], we see there are 120 models withinfinite groups: 12 with three steps, 40 with four steps, 44 with five steps, and 24 with six steps.Adding all of those together yields 263 cases. There are 7 reducible models with an infinite groupthat we have counted twice. The total count is 256 and we are done.Figure 3.5: Reducible classical two-dimensional models with an infinite group.So far we have solved the 64 reducible models, the 39 other models with group of order oneor two, and the single new case of easy-to-solve model with an infinite group, for a grand total of104 trivial or easy models. Out of the remaining 152 models, 113 have an infinite group, and theiranalysis is not part of this thesis. Finally, we have 39 cases left, with a group of order four, six oreight. The rest of the thesis handles the analysis of those cases.Figure 3.6: Step sets for classical two-dimensional models with a finite group.Figure 3.7: Step sets for classical two-dimensional models with an infinite group. Unlistedstep sets differ from these by one of the symmetries of the square.37Chapter 4The Algebraic Kernel MethodIn this chapter we explore the algebraic kernel method, as seen in Section 4 of [18, p. 9], and weextend it to handle models with interactions. First, we recast the non-interacting version of themethod in a form that uses operators. Then we generalize the operators by giving them weights, andthis allows us to investigate models with interactions.4.1 Models Without InteractionsAt the core of the algebraic kernel method we have the idea that we can apply transformations froma group G onto the master functional equation and acquire different equations for each g P G. Afterwe sum these equations in a nice way, we manage to eliminate the functions Q01, Q02, Q0,01,2 and theirorbits, only leaving the orbit of KQ and a term on the right-hand side. What makes this possible ispre-multiplying the whole equation by x1x2.The analysis also works in higher dimensions, as we show later. Although there has been somegeneralization already, as in [8, p. 11] for the two-dimensional case and [18, p. 10] for the three-dimensional one, we present it in a compact and easy-to-generalize way. Instead of summing equa-tions explicitly, like in [8], we use an operator DG that does the same thing. We focus on groupswith a full set of d generators.Definition 4.1. For a classical d-dimensional model with group G with d generators, define theorbit summation operator DG asDG “ÿgPGp´1q|g|g , (4.1)where |g| is the number of generators in the representation of g.38In two dimensions, we can find the whole group by iterating over the two generators. That is,we apply g1 and g2 sequentially and the group is t1, gi, gjgi, gigjgi, . . .u. However, we shall usethe equivalent orbit t1, gi, gigj , gigjgi, . . .u, where the iteration is on the right. To declutter thenotation, we use giji instead of gigjgi.Definition 4.2. For a sequence I “ pi1, . . . , inq of positive integers, definegL “ gi1,...,in “ gi1 ¨ ¨ ¨ gin . (4.2)If the group is finite for a classical two-dimensional model, then pg1g2qn “ 1 for some minimaln, so we can rewrite DG in a useful way [8]. The following lemma is a restatement of the orbitsummation method, found in [8, p. 10], recast in operator form.Proposition 4.3. For a classical two-dimensional model with group of order 2n, generated by g1and g2, we can write the operator DG asDG “ p1` gij ` ¨ ¨ ¨ ` pgijqn´1qp1´ giq . (4.3)Proof. We can just check the identity by expanding it asDG “ p1` gij ` ¨ ¨ ¨ ` pgijqn´1qp1´ giq“ 1´ gi ` gij ´ giji ` ¨ ¨ ¨ ´ pgijqn´1gi ,(4.4)giving us the orbit summation resulting from the second form of the obit.Here are some examples of small groups.Example 4.4. When the order is four, the orbit is t1, g1, g12 “ g21, g2u since g1 and g2 commute.The operator DG is p1` g12qp1´ g1q, but it also factors in a convenient way:DG “ 1´ g1 ´ g2 ` g12 “ p1´ g1qp1´ g2q . (4.5)When the order is six, the orbit is t1, g1, g21, g121 “ g212, g12, g2u and we can write the operator asDG “ p1` g12 ` g1212qp1´ g1q “ 1´ g1 ´ g2 ` g12 ` g21 ´ g121 . (4.6)We can generalize the result from the lemma for groups of higher-dimensional models, but weneed some results first.39Lemma 4.5. Consider a classical d-dimensional model with group G. The set H of elements witheven parity forms a subgroup.Proof. The proof is analogous to the proof that the set of even permutations forms a subgroup ofthe set of permutations of t1, . . . , nu. First, the identity i of G is in H , because i2 “ i has evenparity. Then H is closed under the group operation because the product of two elements with evenparity also has even parity. Finally, if x has even parity, then its inverse y has even parity, otherwise,i “ xy would not have even parity. Thus, H is a subgroup by the two-step subgroup test.The next corollary should be self-evident.Proposition 4.6. Let gi and gj be generators of G. Then gijpHq and gipHq “ gjpHq.Lemma 4.7. For a classical d-dimensional model with a finite group, DG “ DHp1 ´ gkq, whereH is the subgroup of even elements.Proof. First, note that gk is an involution that does not fix any element ofG, that is ggk ‰ g for any gin G. Since applying gk on a group element changes its parity, this means that gk induces a partitionof G into two parts: a set of even elements and a set of odd elements in one-to-one correspondence.That is, we can partition G as the union of H and Hgk. With the notation eh “ p´1q|g|, we canimmediately compute the form of DG from the statement of the lemma:DG “ÿgPHegg `ÿgPHp´1qegggk “˜ÿgPHegg¸p1´ gkq “ DHp1´ gkq . (4.7)Note that we could have also computed DG “ p1 ´ gkqDH if we multiplied gk on the left.With the previous generalization of the operator form, we obtain the d-dimensional generalizationto Proposition 5 in [8, p. 11] and Lemma 52 in [15, p. 59].Theorem 4.8. For a classical d-dimensional model with a finite group G,DGpx1 ¨ ¨ ¨xdKQq “ DGpx1 ¨ ¨ ¨xdq . (4.8)Proof. With the application of DGx1 ¨ ¨ ¨xd, all terms except KQ and 1 vanish since terms likexrdsxItS´1I Q0I are annihilated by DG because they miss one or more variable xi.In [8, p. 11] and [18, p. 13], the authors have found that sometimes the algebraic kernel methodfails. That is, DGpx1 ¨ ¨ ¨xdq “ 0 and the equation does not give us new information. The operatorform of the method allows us to find a more general instance of when this situation occurs.40Corollary 4.9. If an element h of G is an involution permuting the variables x1, . . . , xd, then theregular algebraic kernel method fails. That is, DGpx1 ¨ ¨ ¨xdKQq “ 0.Proof. Since h is an involution, the same method applies as before and we can factor the operatorDG asDHp1´hq for some groupH inG. The action 1´h eliminates the monomial x1 ¨ ¨ ¨xd.Example 4.10. In two dimensions, the algebraic kernel method fails precisely for those modelswhere we have a permutation as in the corollary. That is, hpx1, x2q “ hpx2, x1q and h has ordertwo. Proposition 6 in [8, p. 12] follows.For models with six steps in three dimensions, the algebraic kernel method fails in 62 of them[18, p. 13]. Here G contains a permutation hpxi, xjq “ pxj , xiq. It is not clear if all cases of failureof the method can be attributed to such a situation.Naturally, we need to find out if we can use DH instead of DG “ DHp1 ´ hq? The answer isyes. The operator DH eliminates some of the Q variables and introduces others, but the result is afunctional equation that is symmetric under permutation by h. One may hope to perform a methodanalogous to the half-orbit summation method to prove algebraicity or D-finiteness.Next, we generalize the orbit summation operator by including weights with each g in G.Definition 4.11. For a classical d-dimensional model with group G with d generators and givenweights Rg for g in G, define the weighted orbit summation operator D asD “ÿgPGegRgg . (4.9)The normal orbit summation operator is one with weights Rg “ 1. The action of such anoperator can be seen in [21, p. 11], where the authors use an orbit summation with weights. We cancapture various possible strategies in this notation.Proposition 4.12. Pre-multiplying the functional equation by a function T is equivalent to apply-ing a weighted orbital operator on the original equation. Application of more than one weightedoperator is equivalent to applying a single weighted operator.Proof. For the first statement, let T and f be some functions. Then we haveDGpTfq “ÿgPGeggpTfq “ÿgPGeggpT qgpfq “ÿgPGegRggpfq , (4.10)41where the weights are Rg “ gpT q. For the second statement, we multiply two operators asD1D2 “ÿgPGÿgPGegRggehThh “ÿgPGÿhPGRgeghTghgh “ÿgPG˜ÿhPGegh´1Rgh´1Tg¸g , (4.11)so we obtain a new weighted operator.The second statement of the lemma leads to the following proposition.Proposition 4.13. The set of weighted orbit summation operators associated with a group forms amonoid under composition.Proof. Composition of operators is associative and in the last example we showed that the set isclosed under composition. Thus we only need to show that the set has an identity. Let Rg “ 0 forall g in G except for R1 “ 1. Then DG for these weights is the identity operator.Because of the preceding lemma, it does not matter if we try to use a cleverly-chosen functionT or operators D1 and D2, to circumvent the failure of the algebraic kernel method. We just need tofocus on a weighted operator from the start. The procedure of eliminating terms from the functionalequation requires that those terms are removed generically, that is, whenever I ‰ J , the functionsQ0I and Q0J are treated as independent variables and thus, each of them needs to be annihilated byD on its own. Thus, we need D1ptxIS´1I Q0I q “ 0 for each nonempty set I . This allows us to showthat in general, when the method fails, all operators D1 that eliminate the unwanted terms in thefunctional equation must also eliminate the monomial x1 ¨ ¨ ¨xd.It is enough to work on the functional equation x1 ¨ ¨ ¨xdKQ “ x1 ¨ ¨ ¨xd with an operator D.Then we can find the original operator D1 from the relation D1 “ Dx1 ¨ ¨ ¨xd, where D1 acts on themaster functional equation by pre-multiplying it by x1 ¨ ¨ ¨xd and applying D. We show that all theweights of D must be the same.This observation turns the task into a linear algebra problem. We just need to apply D on thefunctions WI “ txIS´1I Q0I , which are missing the variables indexed by I , collect the differentresults and set their coefficients equal to zero. That is, for every f “WI we find the orbitOrbitGpfq “ tgpfq|g P Gu (4.12)and compute0 “ Dpfq “ÿgPGRggpfq “ÿf 1POrbitpfqR1gf 1 , (4.13)where we set42R1g “ÿgpfq“f 1gPGRg “ 0 . (4.14)Thus, we reach a linear system of |OrbitGpfq| equations in |G| unknowns. We can do this for eachof the 2d ´ 1 terms WI and solve the system of equation. Here is an example.Example 4.14. Consider the classical two-dimensional model with S “ x1`x2`x1x2, where thealgebraic kernel method fails [8, p.12]. Here both of the generators map xi to x1x2 and the groupis given by the orbit t1, g1, g21, g121, g12, g2u of px1, x2q. The orbit of 1 under G is trivial and bysymmetry of the group actions, the orbit of each of W1 “ f1px2q and W2 “ f2px1q is given bytfpx1q, fpx2q, fpx1x2qu. The relations we obtain areR´R1 `R21 ´R121 `R12 ´R2 “ 0 , (4.15)pR´R2qfpx1q ` pR21 ´R121qfpx2q ` pR12 ´R1qfpx1x2q “ 0 , (4.16)pR12 ´R121qfpx1q ` pR´R1qfpx2q ` pR21 ´R2qfpx1x2q “ 0 , (4.17)and if we set the coefficients to zero, we find that all the weights are the same.With a series of results, we now show that there are no clever weighted operators that let uscircumvent the failure of the algebraic kernel method.Lemma 4.15. The stabilizer of xk is given by the subgroup generated by actions gi for i ‰ k.Proof. We already know that gi fixes xk for every i ‰ k. Consider an element g “ ga1...an inG thatfixes xk. For a a given g we can sometimes obtain a shorter action g1 by the following procedure.If a1 or an is not k, then we can take ga1gxk “ ga2...anxk “ ga1xk “ xk. Also, if both a1 and anare equal to k, we can take gkggkxk “ gkxkgk “ xk. If we follow this procedure to its conclusionwe either obtain 1 or gk. However, the latter one does not fix xk so we must arrive at g “ 1 withthis procedure, and we have just proved that every g that fixes xk must have an even number of gk’sin its generating sequence. Such actions are equivalent to ones with no gk’s in their representation.That is, if g fixes xk, it has no gk’s in its generating set and we are done.Lemma 4.16. The stabilizer of Wk is given by t1, gku.Proof. If g stabilizes the generic function Wk, then it must also stabilize each xi for i ‰ k. Then gmust be in the stabilizer of xi for every i ‰ k. The intersection of these sets is precisely t1, gku.43Lemma 4.17. The actions h in H lead to distinct functions hpWkq.Proof. First, because hpWkq “ hgkpWk for every h in H , the orbit of W 0k is the same whether weuse H or G. By the orbit stabilizer theorem, the orbit of W 0k under G has size |G|{2 “ |H|, so allthe elements hpWkq must be distinct for different h’s.Lemma 4.18. Consider a weighted orbital operator that annihilates functions Wk for all k. Thenits weights satisfy the equations Rh “ Rhgk for all h in H .Proof. We just compute the action of the orbital operator asDpW 0k q “ÿgPGp´1q|g|RggpWkq “ÿhPHpRh ´RhgkqhpWkq (4.18)and since the functions hpWkq are distinct, their coefficients must be identically zero as well.Theorem 4.19. Consider a weighted orbital operator that annihilates functions Wk for all k. Thenall of its weights are the same.Proof. From the lemma, we see that Rh “ Rhgk for k and all h in H . That is, the weights are thesame if their corresponding group elements differ by a generator gk. Since we can reach any g in Gby applying a sequence of generators, Rg “ R1 for all g, and the weights are all the same.This has the implication that there is essentially one weighted orbital operator that annihilatesall the functionsW 0k and therefore, there is no clever weighted operator that allows us to circumventthe failure of the algebraic kernel method for classical models.Corollary 4.20. We cannot circumvent the failure of the algebraic kernel method through the useof a weighted orbital operator.4.2 Models With InteractionsThe orbit summation method is not sufficient for extending the algebraic kernel method to modelswith interactions, but we are able to use weighted operators to make progress. The analysis fortwo-dimensional models is particularly nice because we end up with the same number of equationsand unknowns, and we are able to find the required weights. The linear systems can be written asmatrix equations, where the determinants tell us when we have a useful weighted operators.In the end, the method does not extend fully because we do not eliminate theQ0,01,2 term, althoughnow the D-finiteness of Q depends on the D-finiteness of the function Q0,01,2 in a clearer way. Since44we use nontrivial generators only, the group has order 4, 6 or 8, and the functional equation in twodimensions isKQ´K1Q01 ´K2Q02 `K1,2Q0,01,2 “ α . (4.19)4.2.1 Groups of Order FourThe orbit summation operator for the non-interacting case isDG “ 1´ g1 ´ g2 ` g1g2 “ p1´ g1qp1´ g2q “ ∆1∆2 , (4.20)but this operator does not eliminate the unknown functions in the interacting case. Instead, weuse a weighted one and determine its weights. We find an appropriate linear system by applyinggroup actions on the master equation. The unknowns are the functions Q01 and Q02, and their orbitsunder G. If the associated matrix is invertible, the system has a unique solution and unfortunately,we cannot eliminate the variables. However, in some cases the determinant is zero and we caneliminate the unknowns.Since the transformations commute, we have giQ0i “ Q0i and gigjQ0i “ gjQ0i . The variablesand their orbits are given by the following table.Group action Effect on Q01 Effect on Q021 Q01 Q02g1 Q01 g1Q02g2 g2Q01 Q02g12 “ g21 g2Q01 g1Q02Table 4.1: Reductions of group actions on Q01 and Q02 for groups of order four.Therefore, the only variables that we need to eliminate are in the setE “ tQ01, Q02, g2Q01, g1Q02u . (4.21)The situation looks promising since we also have four equations. We rewrite the functional equationin a way that highlights those variables:K1Q01 `K2Q02 “ KQ`K1,2Q0,01,2 ´ α “ β . (4.22)45Then we apply the transformations to produce the system of equationsK1Q01 `K2Q02 “ β , (4.23)g1K1Q01 ` g1K2g1Q02 “ g1β “ β1 , (4.24)g2K1g2Q02 ` g2K2Q02 “ g2β “ β2 , (4.25)g12K1g2Q01 ` g12K2g1Q02 “ g12β “ β12 . (4.26)Using the order of variables in E, we can write the associated matrix M of the linear system asM4 “»————–K1 K2 0 0g1K1 0 0 g1K20 g2K2 g2K1 00 0 g12K1 g12K2fiffiffiffiffifl . (4.27)ThendetM4 “ K1g12K1g1K2g2K2 ´ g1K1g2K1K2g12K2“ K1g12K1g1K2g2K2 ´ g1pg1K1g12K1g1K2g2K2q“ ∆1pK1g12K1g1K2g2K2q .(4.28)The determinant must vanish if we are to eliminate variables, and that only happens when theexpression in ∆1 is in the operator’s kernel. The models with groups of order four exhibit at leastone symmetry across a line — either vertical or horizontal symmetry, or both. Without loss ofgenerality, let the model have symmetry across the x2 axis. That is, g1px1q “ x1, g1pSi2q “ Si2and g1pSi1q “ S´i1 , and we can compute some of the quantities. For example, g1K2 “ K2 andg1g2K2 “ g2g1K2. Therefore, ∆1 fixes both K2 and g2K2 anddetM4 “ ∆1pK1K2g12K1g2K2q “ K2g2K2∆1pK1g12K1q . (4.29)This quantity is zero if and only if ∆1pK1g12K1q “ 0, so we have∆1pK1g12K1q “ K1g12K1 ´ g1K1g2K2“ c1tpx1 ´ x1qpg2S´11 ´ S´11 q“ ´c1tpx1 ´ x1q∆2pS´11 q .(4.30)Therefore, this equation is true if and only if g2S´11 “ S´11 . We have46g2pS´1,´11,2 x2 ` S´1,01,2 ` S´1,11,2 x2q “ S´1,´11,2 x2µ2 ` S´1,01,2 ` S´1,11,2 x2µ2S´1,´11,2 x2µ2 ` S´1,11,2 x2µ2 “ S´1,´11,2 x2 ` S´1,11,2 x2 ,(4.31)and we can write it succinctly as S´1,´11,2 “ µ2S´1,11,2 ., where the S-terms are either both zero or theyare both one. If both are one, since the model has vertical symmetry, then S´12 “ S12 and the modelis highly-symmetric . If they are both zero, the vertical symmetry ensures that S1,11,2 and S1,´11,2 arealso zero. That is the model has no diagonal steps and since the group has two nontrivial generators,we must have both x2 and x2 present in S. Again, the model is highly-symmetric .Conversely, if we started with a highly-symmetric model, we would have obtained detM4 “ 0,and this leads to the following theorem.Proposition 4.21. The determinant of M4 is zero if and only if the model is highly-symmetric .Corollary 4.22. The algebraic kernel method extends to the non-interacting case for groups oforder four if and only if the model is highly-symmetric .Figure 4.1: Highly-symmetric models on the plane with two nontrivial group generatorsWe are finally ready to use the orbit summation method. There are 8 highly-symmetric two-dimensional models, but only five of them have two nontrivial generators for the group G. Further-more, two of the models are reflections of each other, so we are really left with four distinct cases.From left to right in the figure above, they are the Cartesian model, the Diagonal Cartesian model,the model with two horizontal steps missing, and the full model. If we eliminate all the variablesfrom the set E in the beginning of this section, we have a linear relation likeγβ ´ γ1β1 ´ γ2β2 ` γ12β12 “ 0 . (4.32)47Here the choice of signs is inspired by the orbit summation operators. Let ‚ and ˚ stand for appli-cations of g1 and g2, respectively. Note that we have K‚2 “ K2 and K1˚ “ K1. Next, we letx “ Q01 , y “ Q02 , u “ Q0,˚1 , v “ Q0,‚2 , (4.33)a “ K1 , b “ K‚1 , c “ K2 , d “ K2˚ . (4.34)The original equations attain a simplified format given byβ “ ax` cy , β1 “ bx` cv , (4.35)β2 “ dy ` au , β12 “ bu` dv . (4.36)Plugging these into the linear relation above yields0 “ pax` cyqγ ´ pbx` cvqγ1 ´ pdy ` auqγ2 ` pbu` dvqγ12“ paγ ´ bγ1qx` pcγ ´ dγ2qy ` pbγ12 ´ aγ2qu` pdγ12 ´ cγ1qv ,(4.37)and in order to eliminate the variables x, y, u and v, we need all their coefficients to vanish. Weobtain the equationsaγ “ bγ1 , cγ “ dγ2 , bγ12 “ aγ2, , dγ12 “ cγ1 . (4.38)If we set γ “ 1, then γ1 “ a{b and γ2 “ c{d and γ12 “ pacq{pbdq. So we can multiply them out bybd to find the relationbdβ ´ adβ1 ´ cbβ2 ` acβ12 “ 0 , (4.39)where we have successfully eliminated Q01, Q02, Q0,˚1 and Q0,‚2 . In terms of the K’s we have,K‚1K2˚ β ´K1K2˚ β‚ ´K‚1K2β˚ `K1K2β‚˚ “ 0 . (4.40)We can rewrite this equation in the following nicer way.Theorem 4.23. For a two-dimensional highly-symmetric model with a group with two nontrivialgenerators, we have the functional equation ∆pK‚1K2˚ βq “ 0, where β “ KQ`K1,2Q0,01,2 ´ α.This is a generalization of the result in Section 4.2 of [21, p. 16], where the authors use aweighted orbit sum to eliminate boundary terms. We can expand the functional equation to producea different form. Let K0 “ K‚1K2˚ . We find that48∆pK0βq “ ∆pK0pKQ`K1,2Q0,01,2 ´ αqq“ K∆pK0Qq `∆pK0K1,2qQ0,01,2 ´∆pK0qα ,(4.41)where the second equality follows since ∆ commutes with K and functions with some variables ximissing. All that remains is to expand the various quantities involved. Then we have∆giKi “ ´∆Ki “ ´pci ´ txiS´1i ´ ci ` txiS´1i q “ ´tpxi ´ xiqS´1i , (4.42)∆K0 “ ∆1pK‚1 q∆2pK2˚ q “ t2px1 ´ x1qpx2 ´ x2qS´11 S´12 . (4.43)Next,∆pK0K1,2q “ ∆1K‚1∆2K2˚K1,2 “ ∆1K‚1 pK2˚K1,2 ´K2K1˚,2q , (4.44)where, after expanding, the quantity in parentheses isK2˚K1,2 ´K2K1˚,2 “c1c2tS´12 px2 ´ x2q ´ c2tx2S´1,´11,2 px2 ´ x2q“c2tpx2 ´ x2qpc1S´12 ´ x1S´1,´11,2 q .(4.45)Finally,∆pK0K1,2q “ c2tpx2 ´ x2q∆1K‚1 pc1S´12 ´ x1S´1,´11,2 q . (4.46)To simplify this quantity, note that∆1K‚1c1S´12 “ c1S´12 ∆1K‚1 “ ´c1tS´12 px1 ´ x1q , (4.47)∆1K‚1x1S´1,´11,2 “ S´1,´11,2 ∆1K‚1x1 “ c1px1 ´ x1qS´1,´11,2 . (4.48)Once we substitute these back into the equation, we find that∆pK0K1,2q “ c1c2tpx1 ´ x1qpx2 ´ x2qptS´11 S´22 ´ S´1,´11,2 q , (4.49)We can write down the following corollary after we combine some of the terms and simplify them.Corollary 4.24. For a two-dimensional highly-symmetric model with a group with two nontrivialgenerators and K0 “ K‚1K2˚ , we have the functional equationK∆pK0Qq “ αtpx1 ´ x1qpx2 ´ x2q´tS´11 S´12 p1´ b1b2Q0,01,2q ` S´1,´11,2 Q0,01,2¯. (4.50)494.2.2 Groups of Order SixThe work here is similar to the previous case so we omit most of it. First, we tabulate all theunknowns Q0i and their orbits under G. For example, g1Q01 “ Q01 and we writeH. Alsog121Q01 “ g212Q01 “ g21Q01 . (4.51)In the following table we write a sequences L for group actions gL and reduced sequences thatproduce each element in the orbit.Sequence L Alternative Q01 Q02 K1 K21 21212 H 1 1 121 1212 2 21 21 21121 212 12 21 121 2122121 12 12 1 12 1212121 2 2 H 2 2Table 4.2: Reductions of group actions on Q0i and Ki for groups of order six.After we apply the group actions, we find six different functions that need to be eliminated. Letu1 “ Q01 , u2 “ g2Q01 , u3 “ g12Q01 , (4.52)v1 “ Q02 , v2 “ g1Q02 , v3 “ g21Q02 . (4.53)There are twelve different K1’s and K2’s that we label sequentially as A1, . . . , A6 and B1, . . . , B6.For example, A1 “ K1 and A2 “ g1K1 “ K1 and A3 “ g21K1. The matrix associated with thelinear system of equations isM6 “»—————————–A1 B1A2 B2A3 B3A4 B4A5 B5A6 B6fiffiffiffiffiffiffiffiffiffifl(4.54)50and it has determinantdetM6 “ A2A4A6B1B3B5 ´A1A3A5B2B4B6 . (4.55)The even index A’s are found by applying g1 on the odd index A’s, and vice versa for the B’s. ThendetM6 “ ∆1pA2A4A6B1B3B5q “ ∆1pg1pK1qg121pK1qg12pK1qK2g21pK2qg12pK2qq . (4.56)In the following table we show the relations between A’s and B’s for the six models with groupsof order six. S11, S12 and S13 have one group and S21, S22 and S23 have the other. There areno easy relations for S13 and S23. It is easy to check that when a model has nontrivial relation,detM6 “ 0. Also, using a a computer, we can check that the determinant is non-zero in the lasttwo cases where there are no relations.Model Name A-relations B-relationsS11 A1 “ A6, A2 “ A5, A3 “ A4 B1 “ B4, B2 “ B3, B5 “ B6S12 A1 “ A4, A2 “ A3, A5 “ A6 B1 “ B2, B3 “ B6, B4 “ B5S13 None NoneS21 A1 “ A6, A2 “ A5, A3 “ A4 B1 “ B2, B3 “ B6, B4 “ B5S22 A1 “ A4, A2 “ A3, A5 “ A6 B1 “ B4, B2 “ B3, B5 “ B6S23 None NoneTable 4.3: Relations for A “ K1 and B “ K2 for groups of order six.For the models with zero determinant, we seek the same type of relation on β and its orbit as inthe case of groups of order four. We have the following linear relation:0 “γβ ´ γ1β1 ` γ21β21 ´ γ121β121 ` γ12β12 ´ γ2β2“γpA1u1 `B1v1q ´ γ2pA6u2 `B6v1q ´ γ1A2u1 `B2v2q` γ12pA5u3 `B5v2q ` γ21pA3u2 `B3v3q ´ γ121pA4u3 `B4v3q .(4.57)51Expanding out and collecting terms produces the system of equationsA1γ “ A2γ1 , A3γ21 “ A6γ2 , A5γ12 “ A4γ121 , (4.58)B1γ “ B6γ2 , B5γ12 “ B2γ1 , B3γ21 “ B4γ121 . (4.59)It turns out that it does not have a nontrivial symbolic solution, so we need to use the relations here.There is a rational solution in each case, where γ is a free variable. We set γ to be the least commonmultiple of the denominators. We find that K0 “ γ in each of the four cases with relations, asillustrated in the following table.Model S-polynomial Weight γ “ K0 K-formx1x2 ` x1 ` x2 A3A5B6 g21pK1qg12pK1qg2pK2qx1x2 ` x1 ` x2 A2A5B6 g1pK1qg12pK1qg2pK2qx1x2 ` x1 ` x2 A2A3B5B6 g1pK1qg21pK1qg12pK2qg2pK2qx1x2 ` x1 ` x2 A2B6 g1pK1qg2pK2qTable 4.4: Weight K0 for the orbit summation operators.Here we have picked the representations ofA’s andB’s with the least number of transformationsto reach the resulting expression. We also tried finding a possible K0 by brute force for S13 andS23, but we did not find any among products of distinct A’s and B’s. It is likely that such a weightdoes not exist for these cases, and that the algebraic kernel method does not extend for them.Theorem 4.25. The algebraic kernel method extends for a classical interacting model with group oforder six if and only if detM6 “ 0. If we let β “ KQ`K1,2Q0,01,2´α, then we have the functionalequation DGpK0βq “ 0, where K0 depends on the step set.524.2.3 Groups of Order EightAs before, we omit most of the analysis. Here are the results.Model S-polynomialx1 ` x1 ` x1x2 ` x1x2x1 ` x1 ` x1x2 ` x1x2Table 4.5: Step polynomials for models with group of order eight.Sequence L Alternative Q01 Q021 2121212 H 121 121212 2 21121 21212 12 1212121 1212 212 12112121 212 212 21212121 12 12 11212121 2 2 HTable 4.6: Reductions of group actions on Q0i and Ki for groups of order eight.We name the A “ K1 and B “ K2 iterates as before. We have the same K0 since the relationsare the same in both models. That is,A1 “ A6 , A2 “ A5 , A3 “ A4 , A7 “ A8 , (4.60)B1 “ B4 , B2 “ B3 , B4 “ B8 , B6 “ B7 . (4.61)Theorem 4.26. The algebraic kernel method extends for all classical interacting models with groupof order eight. If β “ KQ`K1,2Q0,01,2 ´ α, then the functional equation is DGpK0βq “ 0 andK0 “ A2A3B5B6 “ g1pK1qg21pK1qg212pK2qg1212pK2q . (4.62)53Chapter 5The Obstinate Kernel MethodNext, we explore is the obstinate kernel method. For an application in a two-dimensional interactingmodel, see Section 4.2 of [30, p. 16]. The method is similar to the algebraic kernel method with aweighted operator, where underneath the operator notation, all we are doing is finding more validequations. We apply kernel-preserving actions on the master equation in both methods. However,in the obstinate kernel method we also make a substitution with one of the roots xk “ σkptq of thekernel. This is done in order to annihilate the KQ terms from the resulting equations. However,some transformations, taken together with the substitutions, do not lead to valid functional equationsbecause some of the generating functions fail to remain power series in t after the substitutiontakes place. That is, one or more of the terms gpQ0i q|xk“σk is not a power series in t for sometransformation g from G and some i and k. This inspires use the following language.Definition 5.1. A function fpx1, . . . , xd; tq is admissible if it is a valid power series in the variablet, that is, there are only non-negative orders of t with non-zero coefficients. A transformation g isadmissible if it preserves the admissibility of f with respect to a root σk of the kernel K, that is, ifgpfq|xk“σk is admissible.To recap, it is necessary that when we use a substitution xk “ σk, we only use transformationsg that preserve the admissibility of functions gQ0i for all i in the master equation. We focus ourwork on models with groups of order four, six and eight, where we have two nontrivial generatorsg1 and g2. In this case, S˘1i ‰ 0 for any i and choice of sign, and the roots of the kernel areσ˘k “1´ tS0k ˘bp1´ tS0kq2 ´ 4t2S1kS´1k2tS11, (5.1)with the identities54σ`k σk´ “S´1kS1kand σ`k ` σk´ “1´ tS0ktS1k. (5.2)If we expand the roots in series of t, we find thatσk´ “ S´1k t`Opt2q and σ`k “1S1kt´ S0kS1k´ S´1k t`Opt2q , (5.3)where the higher order terms are the same.Generally, only the σk´ substitution leads to admissibleQ0i terms for all i, but it also happens thatσk´ can do this too. For an example of this, see [30, p. 11]. We focus on the first case and leave theσ`k root analysis for future work. If we do not have enough valid equations with the σk´ substitution,we would have to see if the σ`k substitution can help. We only use σ “ σk´.It suffices to show that enough actions ofG preserve the admissibility of the functions x1 and x2,and thus, the pair px1, x2q, with respect to a root, to show that the functions Q0k are also admissibleunder the actions and substitution. That is, we only need to check for which j, k and g is gpxjq|xk“σkadmissible. Luckily, some models pass this test and we obtain enough valid functional equations,so that we can use the obstinate kernel method. For those cases where we find less equations, it maybe possible to show that the Q0k terms are power series in t via another method, like in [30].Proposition 5.2. Consider a classical two-dimensional model with group of order four, six or eight.Models with the same group have the same admissibility properties for x1 and x2, and the pairpx1, x2q. Models with group of order four all have the same admissibility properties.Proof. All we need to do is compute the actions on the functions and check if substituting σk´ leadsto admissible ones. This is tedious to do by hand but straight-forward to do on a computer. Theresults are summarized in tables in the following sections. However, we can perform the analysisfor groups of order four without difficulty.The transformations 1 and g2 fix x1, but the transformations g1 and g1g2 change it to x1S´11 {S11 .Note that σ1 “ σ`1 S11{S´11 , so g1px1q|x1“σ1 “ σ`1 and this function is not admissible. Thereforex1’s admissibility with respect to σ1 is preserved only by the transformations t1, g2u.Since models with groups of order four need to have one symmetry across an axis, without lossof generality, we can assume the symmetry is across the x1 axis. That is, g2px2q “ x2, and thex1 “ σ1 substitution trivially leads to an admissible function. Therefore, all of G preserves theadmissibility of x2 with respect to σ1 and finally, only 1 and g2 preserve the admissibility for bothx1 and x2 with respect to σ1. The analysis is analogous for the σ2 substitution.555.1 Initial ComputationsThis classification shows that we can treat all models with group of order four with the same method,but the analysis is more complicated for groups of order six or eight. Now, suppose that we havea set of valid equations for a substitution xk “ σk, forming a linear system in the unknowns Q0,01,2,Q01, Q02, and their orbits under the valid group actions. We hope for redundancy in these equations,because it allows us to eliminate some of the unknowns. That is, we find a weighted operator that,paired with the substitution xk “ σk, eliminates the unwanted terms. It turns out that it is enoughto have |G|{2 transformations preserving the admissibility for both x1 and x2.5.1.1 Groups of Order FourWe start with the admissibility table for groups of order four.Root x1ptq x2ptq x1ptq and x2ptqσ1ptq 1, g2 All 1, g2σ2ptq All 1, g1 1, g1Table 5.1: Admissibility-preserving transformations with respect to roots of the kernel withgroup of order four.The different σ substitutions lead to essentially the same analysis, so we will only work withthe first one, together with actions 1 and g2. Let F ˚ denote g2pF q. The functional equationscorresponding the the group actions areKQ´K1Q01 ´K2Q02 `K12Q0,01,2 “ α , (5.4)KQ˚´ K1˚Q0,˚1 ´K2˚Q02 ´K1˚2Q0,01,2 “ α . (5.5)Once we make the substitution, the function Q02 is difficult to expand, so we want to eliminate itfirst. We multiply the equations by K2˚ and K2, respectively, and subtract the second one from thefirst one. The resulting equation isK2˚KQ´K2KQ˚´ pK2˚K1Q01 ´K2K1˚Q0,˚1 q ` pK2˚K12 ´K2K1˚2qQ0,01,2 ´ αpK2˚ ´K2q “ 0 ,(5.6)56where we can set x1 “ σ1 to eliminate the K term. The substitution is implicit in the notation fromnow on. We havepK2˚K1Q01 ´K2K1˚Q0,˚1 q ´ pK2˚K12 ´K2K1˚2qQ0,01,2 ` αpK2˚ ´K2q “ 0 (5.7)and we can recast this elimination via the weighted orbital operatorD2 “ g2pK2q ¨ 1´K2g2 “ p1´ g2qK2˚ . (5.8)If we apply it on the master equation, we obtainD2p´KQ`K1Q01 `K2Q02 ´K12Q0,01,2 ` αq “ 0 ,´D2pKQq `D2pK1Q01q ´D2pK12Q0,01,2q `D2pαq “ 0 ,(5.9)and once we make the σ1 substitution, we find thatD2pK1Q01q ´D2pK12qQ0,01,2 `D2pαq “ 0 (5.10)and this is the same as Equation 5.6. The following notation is useful.Definition 5.3. Let L be a concatenated list, ∆L “ 1´gL and letX be some function. The operatorDLrXs is defined by its action on functions F asDLrXspF q “ ∆LpXF q “ p1´ gLqpXF q “ XF ´ gLpXF q . (5.11)We drop the X from the notation if it is clear from context. In particular, DLr1s “ ∆L.For example, D2 “ D2rK2˚ s “ D2rg2pK2qs.Example 5.4. If we use gLpXq instead of X in the definition above, we obtain the Ore operatorDLrgLpXqs “ gLpXq ´XgL . (5.12)We can expand some of the terms in the functional equation. First,D2pαq “ αpK2˚ ´K2q“ αppc2 ´ tx2µ2S´12 q ´ pc2 ´ tx2S´12 qq“ αtpx2 ´ x2µ2pσ1qqS´12 pσ1q .(5.13)57Then,D2pK12q “ K2˚K12 ´K2K1˚2“ c1c2tpx2 ´ x2µ2qS´12 ´ c2tσ1px2 ´ x2µ2qS´1,´11,2“ c2tpx2 ´ x2µ2pσ1qqpc1S´12 pσ1q ´ σ1S´1,´11,2 q .(5.14)Lemma 5.5. For models with groups of order four,D2pK1Q01q ´D2pK12qQ0,01,2 `D2pαq “ 0 , (5.15)whereD2pαq “ αtpx2 ´ x2µ2pσ1qqS´12 pσ1q , (5.16)D2pK12q “ c2tpx2 ´ x2µ2pσ1qqpc1S´12 pσ1q ´ σ1S´1,´11,2 q . (5.17)If the model is highly-symmetric , we see that g2S´11 “ S´11 and therefore, g2K1 “ K1, and wecan bring that factor outside of the operator, so D2pK1˚F q “ K1D2pF q for functions F . It turnsout that this happens for both substitutions if and only if the model is highly-symmetric , meaningthat the analysis is easier only in those cases. This is easily verified using a computer since thereare not that many models with group of order four. We investigate the highly-symmetric models inmore detail in Section 5.2.Proposition 5.6. Consider a classical model with a group of order four. If i ‰ j, then DirgiKjs “Kj∆i in the σj substitutions if and only if the model is symmetric across the xi axis. That is, the Kfunctions factor out of the operators in both cases if and only if the model is highly-symmetric.5.1.2 Groups of Order SixWe start with the admissibility tables for the two groups of order six.Root x1 x2 px1, x2qσ1 1, g2, g21, g121 1, g1, g2, g21 1, g2, g21σ2 1, g1, g2, g12 1, g1, g12, g121 1, g1, g12Table 5.2: Admissibility-preserving transformations with respect to roots of the kernel withgroup of order six for the models S11, S12, S13.58Root x1 x2 px1, x2qσ1 1, g2, g21, g121 1, g1, g12, g121 1, g121σ2 1, g2, g21, g121 1, g1, g12, g121 1, g121Table 5.3: Admissibility-preserving transformations with respect to roots of the kernel withgroup of order six for the models S21, S22, S33.We focus on the first three models because they are amenable to the straight-forward method.The latter three need more work, since there are too few valid actions.Figure 5.1: Step sets for models S11, S12, S13.For consistency, we work with σ1 where the actions are 1, g2, g21. From the previous chapter,we know these actions reduce on the function Q0i .Sequence L Q01 Q02H H H2 2 H21 2 21Table 5.4: Reductions of group actions on Q01 and Q02, group of order four.As in the previous section, we wish to eliminate X2 “ g2Q01 and Y “ Q02 because they involveσ once we make the substitution. Letβ “ K12Q0,01,2 ´ α “ αpb1b2Q0,01,2 ´ 1q , (5.18)so that we haveAX `BY “ β , (5.19)A2X2 `B2Y “ β2 , (5.20)A21X `B21Y21 “ β21 . (5.21)59We want a linear combination of β, β2 and β21 that eliminates X2 and Y . In this case, we can writeaβ ´ bβ2 ` cβ21 “ aAX ` paB ´ bB2qY ` pcA21 ´ bA2qX2 ` cB21Y21 (5.22)“ aAX ` cB21Y21 , (5.23)and for the elimination to work, we need aB “ bB2 and cA21 “ bA2. One solution for a, b and cwithout denominators isa “ A21B2 , b “ A21B , c “ A2B . (5.24)The elimination procedure yieldsAA21B2Q01 `A2BB21g21Q02 “ A21B2β ´A21Bβ2 `A2Bβ21“ pA21B2 ´A21B `A2Bqβ(5.25)and we can recast the whole process equation into operator notation.Proposition 5.7. LetDpF q “ A21B2F ´A21Bg2pF q `A2Bg21pF q . (5.26)ThenDpAX `BY q “ AA21B2Q01 `A2BB21g21Q02 “ βDp1q . (5.27)For each case, we can compute Dp1q, but since the expressions are somewhat complicated andcontain a square root, we do not list them here. Terms AA21B2 and A2BB21 contain roots too.5.1.3 Groups of Order EightWe start with the admissibility tables for the two groups of order eight.Root x1 x2 px1, x2qσ1 1, g2, g21, g212 All 1, g2, g21, g212σ2 1, g1, g2, g12, g121, g2121 1, g1, g12, g121 1, g1, g12, g121Table 5.5: Admissibility-preserving transformations with respect to roots of the kernel withgroup of order eight for model S1.60Root x1 x2 px1, x2qσ1 1, g2, g21, g212 All 1, g2, g21, g212σ2 1, g2, g21, g121, g212, g2121 1, g1, g12, g121 1, g121Table 5.6: Admissibility-preserving transformations with respect to roots of the kernel withgroup of order eight for model S2.We work on the model with step polynomialS “ x1 ` x1 ` x1x2 ` x1x2 , (5.28)since it has enough admissibility-preserving actions: 1, g2, g21, g212. Note that the model hereis equivalent to the one seen in [30], because they have the same step set and master functionalequation, so the analysis is the same. Using our notation and operators, we are able to redo some ofthe authors’ derivations in a cleaner way. First, we have the table of reductions for group action inthis model.Sequence L Q01 Q02H H H2 2 H21 2 21212 212 21Table 5.7: Reductions of group actions that preserve admissibility with respect to σ1.Similarly to previous sections, let β “ K12Q0,01,2 ´ α “ αpb1b2Q0,01,2 ´ 1q and X “ Q01 andY “ Q02. Note that β is left unchanged by group actions. We have the four equationsAX `BY “ β , (5.29)A2X2 `B2Y “ β , (5.30)A21X2 `B21Y21 “ β , (5.31)A212X212 `B212Y21 “ β , (5.32)where we wish to eliminate the functions X2, Y and Y21 because they contain σ1 as part of theirarguments. To do this, we first use the first two and latter two equations to eliminate Y and Y21,respectively. That is, we compute B2 times the first equation minus B times the second equation,61and B212 times the third equation minus B21 from the last equation. Then we use the resulting twoequations to eliminate X2. The first step of the procedure is the same as applying the following twooperators on the master functional equation and substituting x1 “ σ1. They areD2rB2s “ B2 ´Bg2 , (5.33)´g212D2rB2s “ g212Bg2 ´ g212B2 “ B212 g21 ´B21 g212 , (5.34)and we obtain the equationsAB2X ´A2BX2 “ βpB2 ´Bq , (5.35)A21B212X2 ´A212B21X212 “ βpB212 ´B21q . (5.36)To eliminate X2, we multiply the equations by A21B212 and A2B, add them together and obtainA21B212AB2X ´A2BA212B21X212 “ βpA21B212pB ´B2q `A2BpB212 ´B21qq . (5.37)This final equation is equivalent to applying the following operator on the master functional equa-tion:D “ A21B212D2rB2s ´A2Bg212D2rB2s“ pA21B212 ´A2Bg212qD2rB2s“ pA21B212 ´ g212A21B212qD2rB2s“ D212rA21B212sD2rB2s .(5.38)From the master functional equation, we haveDpβq “ βD212rA21B212spB2 ´Bq , (5.39)DpAX `BY q “ DpAXq“ D212rA21B212sD2rB2spAXq“ D212rA21B212spAB2X ´A2BX2q“ D212rA21B212spAB2Xq“ D212rAA21B2B212spXq .(5.40)Note that A212 “ A, so we can factor out A from the operator. We have the following result.62Proposition 5.8. For the first model with group of order eight,AD212rA21B2B212s`Q01˘ “ βD212rA21B212spB2 ´Bq , (5.41)where AL “ gLpK1q, BL “ gLpK2q and β “ αpb1b2Q0,01,2 ´ 1q, and the equality is valid only oncewe set x1 “ σ1 in this expression.To obtain an analogous statement for the σ2 substitution, switch the A’s and the B’s, and the1’s and the 2’s. It was found in [30] that the coefficients in front of the X and X212 terms becomeLaurent polynomials with the σk substitutions. The coefficient in front of β can be reduced to afunction involving a square root. The calculations are complicated and would be tedious to do byhand. The square root part does not depend on a2 in the first case, and a1 in the second case. Thisobservation allows the authors to find a relation for the different versions of Q0,01,2.5.2 Highly-symmetric Two-dimensional ModelsFor highly-symmetric models, the first equation in Lemma 5.5 has the simplified formx1 “ σ1 : ∆2pK2˚Q01q “ 1K1´∆2pK2˚K12qQ0,01,2 ´ αpK2˚ ´K2q¯, (5.42)x2 “ σ2 : ∆1pK1‚Q02q “ 1K2´∆1pK‚1K12qQ0,01,2 ´ αpK‚1 ´K1q¯. (5.43)It is enough to perform the analysis for one of the equations, since only the model with two horizon-tal or vertical steps removed requires working with both equations. In highly-symmetric models,µ2 “ S´12 {S12 “ 1 andαpK2˚ ´K2q “ αtpx2 ´ x2qS´12 pσ1q , (5.44)∆2pK2˚K12q “ c2tpx2 ´ x2qpc1S´12 pσ1q ´ σ1S´1,´11,2 q . (5.45)To compute ∆2pK2˚Q01q, we need to compute K2pσ1, x2q and K2˚ pσ1, x2q given byK2 “ c2 ´ tx2S´12 pσ1q and K2˚ “ c2 ´ tx2S´12 pσ1q , (5.46)where we can find that S´12 pσq is a rational function given byS´12 pσ1q “S1,11,2 ` tS0,11,2S1,01,2t´S1,01,2 ` S1,11,2px2 ` x2q¯ . (5.47)63Here is a table summarizing the values of this function for the different models.Model S0,11,2 S1,01,2 S1,11,2 S´12 pσ1q1 1 0 10 0 1 t{px2 ` x2q1 0 1 t{px2 ` x2q0 1 1 t{px2 ` 1` x2q1 1 1 p1` tq{px2 ` 1` x2qTable 5.8: Functions S´12 pσ1q for highly-symmetric models.Lemma 5.9. For highly-symmetric models with e “ S1,11,2 , f “ S1,01,2 and g “ S0,11,2 , we haveαpK2˚ ´K2qK1“ αpx2 ´ x2qpe` tfgqS11K1, (5.48)∆2pK2˚K12qK1“ c2px2 ´ x2qpc1pe` tfgq ´ etσ1S11qS11pc1 ´ tσ1S11q. (5.49)5.2.1 Cartesian Model – Steps N, S, E, WSince S´12 pσ1q “ 1, this is the simplest case to analyze. We essentially repeat the calculationsProposition 2.6, but for two dimensions. We obtain a rational relation for Q0,01,2, instead of a linearone. Afterwards, we find an expression for Q in terms of its partially-interacting versions. First,αpK2˚ ´K2q “ αtpx2 ´ x2q and ∆2pK2˚K12q “ c1c2tpx2 ´ x2q . (5.50)Then, if we set β “ 1´ b1b2Q0,01,2 and use the fact that K1 does not depend on x1 or c2,1K1pαpK2˚ ´K2q ´∆2pK2˚K12qq “ αβ tpx2 ´ x2qK1 “ αβfpx2, a1; tq . (5.51)Then we can rewrite the functional equation as∆2pK2˚Q01q ` αβfpx2, a1; tq “ 0 , (5.52)64and once we expand the first using Equation 5.46, we havepc2 ´ tx2qQ01px2q ´ pc2 ´ tx2qQ01px2q ` αβf “ 0 . (5.53)We extract the x2 and x2b02 terms to find the equationsc2Q0,11,2 ´ tQ0,01,2 ` αβf12 “ 0 , (5.54)´t qQ0,01,2 ` a1f12 “ 0 . (5.55)We can substitute the latter equation in the first one to obtain the identityb2Q0,11,2 “ tpa2Q0,01,2 ´ β qQ0,01,2q . (5.56)The proof of the folwing result is similar to the one we see in Corollary 5.13, so we omit it.Lemma 5.10. For non-negative integers m and n,b2Qm,n`11,2 “ tpa2Qm,n1,2 ´ β qQm,n1,2 q , (5.57)b1Qm`1,n1,2 “ tpa1Qm,n1,2 ´ β pQm,n1,2 q . (5.58)From the first equation we haveb2Q1,11,2 “ tpa2Q1,01,2 ´ β qQ1,01,2q (5.59)and if we multiply it by b1 and use the relations in the lemma, we find thatb1b2Q1,11,2 “ ta2tpa1Q0,01,2 ´ β pQ0,01,2q ´ tβtpa1 qQ0,01,2 ´ β qpQ0,01,2q“ t2pa1a2Q0,01,2 ´ a2β pQ0,01,2 ´ a1β qQ0,01,2 ` β2 qpQ0,01,2q . (5.60)Let G “ Q0,01,2, pG “ G1 and qG “ G2. From the x01x02 term of the master equation, we haveQ0,01,2 “ 1` ta1a2pQ1,01,2 `Q0,11,2q . (5.61)Multiplying it by b1b2 and using the relations above, leads tob1b2G “ b1b2 ` ta1a2pb2tpa1G´ βG1q ` b1tpa2G´ βG2q“ b1b2 ` t2a1a2pb2a1G` b1a2G´ b2βG1 ´ b1βG2q .(5.62)65Using the relation for β and simplifying the expression allows us to write G asG “ b1b´ 2´ t2a1a2pb2G1 ` b1G2qb1b2 ´ t2a1a2pa2b1 ` a1b2 ` b1b2pb2G1 ` b1G2qq . (5.63)If we let F “ pb2G1 ` b1G2q and perform the long division with respect to F , we find thatQ0,01,2 “1b1b2ˆ1´ b1b2p1´ b1b2q ´ t2a1a2pa1b2 ` a2b1qb1b2 ` t2a1a2pa1b2 ` a2b1 ` b1b2F q˙, (5.64)so G is a rational function of G1 and G2. To find an equation for Q we need to first take the secondset of equations in Lemma 5.10, multiply them by xn2 and sum them up. The resulting equations areb1Qm`11 “ tpa1Qm1 ´ β pQm1 q (5.65)and we can sum them with respect to x1 after, multiply them by xm`11 , to findb1pQ´Q01q “ x1tpa1Q´ β pQq . (5.66)We can solve this it for Q01 as obtainb1Q01 “ pb1 ´ a1x1tqQ` x1tβ pQ . (5.67)We substitute this expression, along with an analogous one for Q02, into the original functionalequation, and after some algebra, we find thatQ “ p1´ b1b2Gqpα` tx1b1K1 pQ` tx2b2K2 qQqK ´ p1´ c1x1tqK1 ´ p1´ c2x2tqK2 . (5.68)We recognize some of the quantities as modified Ki terms.Theorem 5.11. The Cartesian model has generating functions satisfying the equationsQ “ p1´ b1b2Q0,01,2qpα´ b1K1 pK‚1 pQ´ b2K2 qK2˚ qQqK ´ c1K1K‚1 ´ c2K2K2˚(5.69)andQ0,01,2 “ G “1b1b2˜1´ b1b2p1´ b1b2q ´ t2a1a2pa1b2 ` a2b1qb1b2 ` t2a1a2pa1b2 ` a2b1 ` b1b2pb2 pG` b1 qGqq¸. (5.70)This shows that Q is built from Q0,01,2 and from versions of itself, each with a single interaction.665.2.2 Diagonal Cartesian Model – Steps NE, NW, SE, SWThis model is similar to a model of two interacting walks confined in a semi-infinite strip, covered in[21]. The models are different because there is an extra term in their functional equation. Throughcalculations like the ones in the previous subsection, we find that Q0,01,2 has a linear relationship withits partially-marked versions. However we do not find an identity for Q. In this case,αpK2˚ ´K2qK1“ αpx2 ´ x2qK1px2 ` x2q , (5.71)∆2pK2˚K12qK1“ c2px2 ´ x2qpc1 ´ tσ1S11qS11pc1 ´ tσ1S11q“ c2px2 ´ x2qx2 ` x2 , (5.72)and the functional equation becomesK2˚Q1 ´K2Q1˚ ´ c2px2 ´ x2qx2 ` x2 Q1,2 ` αx2 ´ x2px2 ` x2qK1 “ 0 . (5.73)Surprisingly enough, the only remaining term depending on σ1 is K1, so it is of no consequence tothe rest of the analysis. To clear denominators, we multiply the equation by x2 ` x2. Here,R “ px2 ` x2qK2 “ c2px2 ` x2q ´ x2 “ c2x2 ´ a2x2 , (5.74)and this function satisfies the identitiesR˚ ´R “ vpK2˚ ´K2q “ x2 ´ x2 , (5.75)x2R˚ ´ x2R “ x2c2v ´ 1´ x2c2v ` 1 “ c2vpx2 ´ x2q . (5.76)Finally, using the function δ0 “ a1px2 ´ x2qK1, we can rewrite the equation asR˚Q01 ´RQ0,˚1 ´ c2px2 ´ x2qQ0,01,2 ` a2δ0 “ 0. (5.77)Next, we work towards finding equations like those in Lemma 5.10 but for diagonal steps. To dothat, we need to find higher order equations like 5.77. We start with the master functional equationp1´ tSqQ´ pc1 ´ tvx1qQ01 ´ pc2 ´ tx2S´12 qQ02 ` pc1c2 ´ tx1x2qQ0,01,2 “ a1a2 . (5.78)Upon extracting the x01 coefficient, we find thatQ01 “ a2 ` c2Q0,01,2 ` a1tvQ11 . (5.79)67We can extract higher order coefficients too. Let k ě 1. Then the xk2 coefficient is0 “ Qk1 ´ tS´11 Qk`11 ´ tS01Qk1 ´ tS11Qk´11 ´ c2Qk,01,2` tx2pS´1,´11,2 Qk`1,01,2 ` S0,´11,2 Qk,01,2 ` S1,´11,2 Qk´1,01,2 q“ Qk1 ´ tvQk`11 ´ tvQk´11 ´ c2Qk,01,2 ` tx2pQk`1,01,2 `Qk´1,01,2 q .(5.80)We can rewrite the last one in a form more convenient for the next few steps:Qk1 “ tvpQk`11 `Qk´11 q ` c2Qk,01,2 ´ tx2pQk`1,01,2 `Qk´1,01,2 q . (5.81)We have the equationsQ01 “ a2 ` c2Q0,01,2 ` a1tvQ11 , (5.82)Q0,˚1 “ a2 ` c2Q0,01,2 ` a1tvQ1,˚1 . (5.83)Combining them with Equation 5.77 gives0 “ R˚Q01 ´RQ0,˚1 ´ c2px2 ´ x2qQ0,01,2 ` a2δ0“ R˚pa2 ` c2Q0,01,2 ` a1tvQ11q ´Rpa2 ` c2Q0,01,2 ` a1tvQ1,˚1 q´ c2px2 ´ x2qQ0,01,2 ` a2δ0“ a1tvpR˚Q11 ´RQ1,˚1 q ` pR˚ ´Rqpa2 ` c2Q0,01,2q´ c2px2 ´ x2qQ0,01,2 ` a2δ0“ a1tvpR˚Q11 ´RQ1,˚1 q ` a2ppx2 ´ x2q ` δ0q ,(5.84)and we have the equationR˚Q11 ´RQ1,˚1 ` a2px2 ´ x2q ` δ0a1tv“ R˚Q11 ´RQ1,˚1 ` a2δ1 “ 0 . (5.85)This equation together with Equation 5.77 form the base cases for the following result.Lemma 5.12. Let m be an integer greater than zero. ThenR˚Qm1 ´RQm,˚1 ´ c2px2 ´ x2qQm,01,2 ` a2δm “ 0 , (5.86)where δm is not a function of a2.68Proof. We prove this by induction. We have the base cases m “ 0 and m “ 1. The latter onefits the pattern because Q1,01,2 “ 0, since we cannot have walks ending on p1, 0q. Assume that theformula is true for all cases up to and including m. Then we use Equation 5.81 to calculateR˚Qm1 ´RQm,˚1“tvpR˚Qm`11 ´RQm`1,˚1 q ` tvpR˚Qm´11 ´RQm´1,˚1 q` c2pR˚ ´RqQm,01,2 ´ tpx2R˚ ´ x2RqpQm`1,01,2 `Qm´1,01,2 q“tvpR˚Qm`11 ´RQm`1,˚1 q ` tvpc2px2 ´ x2qQm´1,01,2 ´ a2δm´1q` c2px2 ´ x2qQm,01,2 ´ c2tvpx2 ´ x2qpQm`1,01,2 `Qm´1,01,2 q“tvpR˚Qm`11 ´RQm`1,˚1 q ` c2px2 ´ x2qQm,01,2´ c2tvpx2 ´ x2qQm`1,01,2 q ´ a2tvδm´1q .(5.87)Combining this expression with the equation from the lemma leads to0 “ R˚Qm`11 ´RQm`1,˚1 ´ c2px2 ´ x2qQm`1,01,2 ` a2δm`1 , (5.88)whereδm`1 “ δmtv´ δm´1 (5.89)is independent from a2.Of course, there is an analogous statement for Qn2 if we follow the same analysis with thevariable names switched. We can expand R˚ and R to a form we can use:0 “ pc2x2 ´ a2x2qQm1 px2q ´ pc2x2 ´ a2x2qQm1 px2q´ c2px2 ´ x2qQm,01,2 ` a2δm .(5.90)We extract the x2 coefficient and obtain the equationc2Qm,21,2 ´ a2Qm,01,2 ´ c2Qm,01,2 ` c2Qm,01,2 ` rx12sa2δm “ 0c2Qm,21,2 ´ a2Qm,01,2 ` rx12sa2δm “ 0 .(5.91)We can also extract the xn`12 coefficient for n ě 1:c2Qm,n`21,2 ´ a2Qm,n1,2 ` rxn`12 sa2δm “ 0 . (5.92)69This formula also contains the n “ 0 case, so we can group them together. Set a2 “ 1 to find´ qQm,n1,2 ` rxn`12 sδm “ 0 , (5.93)and substitute the resulting expression into the equation above to obtainb2Qm,n`21,2 “ Qm,n1,2 ´ qQm,n1,2 . (5.94)We finally have the following result.Corollary 5.13. For integers m and n greater than zero, we have the following relationsb1Qm`2,n1,2 “ Qm,n1,2 ´ pQm,n1,2 , (5.95)b2Qm,n`21,2 “ Qm,n1,2 ´ qQm,n1,2 . (5.96)We can sum up those equations to retrieve the following functional equations.Corollary 5.14. For integers m greater than zero, we have the following identitiesQm1 ´ pQm1 “ b1Qm`21 , (5.97)x21pQn2 ´ pQn2 q “ b1pQn2 ´Q1,n1,2x1 ´Q0,n1,2 q , (5.98)x21pQ´ pQq “ b1pQ´ x1Q11 ´Q01q , (5.99)where we can also set a2 “ 1 to obtain further identities.In this case, we cannot solve for Q simply in terms of partially-marked variants of Q and Q0,01,2since the equations would have the terms Q11 and Q12. Now, we can move onto the main result aboutthe diagonal walks — the relation between Q0,01,2 and its non-interacting versions. We use the masterequation to extract the x01x02 and x11x12 coefficients and obtain the following identities:Q0,01,2 “ 1` ta1a2Q1,11,2 , (5.100)Q1,11,2 “ tpQ0,01,2 `Q2,01,2 `Q0,21,2 `Q2,21,2q . (5.101)We also haveb1b2Q2,21,2 “ b1pQ2,01,2 ´ qQ2,01,2q “ Q0,01,2 ´ pQ0,01,2 ´ qQ0,01,2 ` qpQ0,01,2 , (5.102)70together withb1b2Q2,01,2 “ b2Q0,01,2 ´ b2 pQ0,01,2 , (5.103)b1b2Q0,21,2 “ b1Q0,01,2 ´ b1 qQ0,01,2 . (5.104)Furthermore,b1b2Q1,11,2 “ tpb1b2Q0,01,2 ` b1b2Q2,01,2 ` b1b2Q0,21,2 ` b1b2Q2,21,2q“ tppb1b2 ` b1 ` b2 ` 1qQ0,01,2 ´ pb2 ` 1q pQ0,01,2 ´ pb1 ` 1q qQ0,01,2 ` qpQ0,01,2q“ tpa1a2Q0,01,2 ´ a2 pQ0,01,2 ´ a1 qQ0,01,2 ` qpQ0,01,2q .(5.105)Our final identity isb1b2Q0,01,2 “ b1b2 ` ta1a2b1b2Q1,11,2“ b1b2 ` t2a1a2pa1a2G´ a2G1 ´ a1G2 `G1,2q(5.106)where we have, as before GI “ rb0I sQ0,01,2. As a linear combination, it becomespc1c2 ´ a1a2t2qG` a2t2G1 ` a1t2G2 ´ t2G1,2 “ c1c2 , (5.107)Theorem 5.15. The generating function Q0,01,2 for the Diagonal Cartesian model satisfies the equa-tion BpfQ0,01,2q “ c1c2, where fpa1, a2, tq “ c1c2 ´ a1a2t2.5.2.3 The Full Model – All StepsThe situation here is more difficult because we no longer have a rational function in front of theQ0,01,2 term and we are not sure how to proceed from there. We start with the following computation:αpK2˚ ´K2qK1“ αpx2 ´ x2qp1` tqS11K1, (5.108)∆2pK2˚K12qK1“ c2px2 ´ x2qqS11ˆ1´ tc1 ´ tσ1S11˙. (5.109)To find a representation for that last fraction, we first compute the σ1 roots asσ1 “ u´?u2 ´ 4w22wand σ1 “ u`?u2 ´ 4w22w, (5.110)71where u “ 1´ tv and w “ tp1` vq. Then we havetc1 ´ σ1w “2t2c1 ´ u´?u2 ´ 4w2q “tp2c1 ´ u`?u2 ´ 4w2q2pc21 ´ c1u` w2q. (5.111)Let v “ x2 ` x2. Then the denominator has the termc21 ´ c1u` w2 “ c21 ´ c1p1´ tS01q ` t2pS11q2 “ a21b1 ´ a1b1vt` p1` vq2t2 (5.112)and the expression under the square root factors asu2 ´ 4w2 “ p1´ p3v ` 2qtqp1` pv ` 2qtq . (5.113)The first few terms of the square root areau2 ´ 4w2 “ 1´ vt´ 2p1` vq2t2 ´ 2vp1` vq2t3 ` ¨ ¨ ¨ . (5.114)We can give a series representation of the square root via the series?1´ z “8ÿn“0p2nq!p1´ 2nqpn!q24n zn . (5.115)That is, ap1` pv ` 2qtqp1´ p3v ` 2qtq“˜ 8ÿn“0p´1qnp2nq!pv ` 2qntnp1´ 2nqpn!q24n¸˜ 8ÿn“0p2nq!p3v ` 2qntnp1´ 2nqpn!q24n¸“8ÿn“0tn4nnÿk“0p´1qkp2kq!p2n´ 2kq!p1´ 2kqp1´ 2n` 2kqk!2pn´ kq!2 pv ` 2qkp3v ` 2qn´k ,(5.116)However, we are not sure if a closed form exists for these coefficients. Extracting x2 coefficientsfrom the overall expression is difficult because we would first need to expand it in series of t. Now,K2 and K2˚ have 1` v in their denominators, so we can multiply the whole functional equation by1` v to clear out these denominators. We havep1` vqK2 “ c2p1` vq ´ x2p1` tq “ pc2 ´ 1´ tqx2 ` c2 ` c2x2 , (5.117)p1` vqK2˚ “ c2p1` vq ´ x2p1` tq “ c2x2 ` c2 ` pc2 ´ 1´ tqx2 , (5.118)72andp1` vqαpK2˚ ´K2qK1“ αpx2 ´ x2qp1` tqK1“ αgpa1, x2, tq , (5.119)p1` vq∆2pK2˚K12qK1“ c2px2 ´ x2qfpa1, x2, tq , (5.120)wherefpa1, x2, tq “ 1´ tc1 ´ 1` tv `ap1` pv ` 2qtqp1´ p3v ` 2qtqc21 ´ c1 ` c1tv ` p1` vq2t2. (5.121)If we let A “ c2 ´ p1` tq, we can write the functional equation aspc2x2 ` c2 `Ax2qQ01px2q ´ pAx2 ` c2 ` c2x2qQ01px2q “ c2px2 ´ x2qf ´ αg . (5.122)As before, we try to find a relation for the walks returning to the origin via coefficients extractions.We extract the x2 coefficient from both sides to find thatc2Q0,21,2 ` c2Q0,11,2 ´ p1` tqQ0,01,2 “ ´αg12 ` c2pf22 ´ f02 qQ0,01,2 , (5.123)and then we set a2 “ 1 on both sides to find that´p1` tq qQ0,01,2 “ ´a1g12 . (5.124)When we finally substitute this quantity back into the equation, it simplifies tob2pQ0,21,2 `Q0,11,2q “ pb2pf22 ´ f02 q ´ a2p1` tqqQ0,01,2 ´ p1` tq qQ0,01,2 . (5.125)It appears that the quantity f22 ´ f02 has no closed form:´pf22 ´ f02 q “ 1` a1t` a21b1pa21 ´ a1 ´ 4qt3 ` 4a21b21pa31 ´ 3a21 ` 1qt4 ` ¨ ¨ ¨ . (5.126)Unfortunately, we have not been able to go further. We can make some assumptions about theform of the equations, like those for Qm,n1,2 in the previous cases, but even then, it is not clear ifwe can find a relation for Q0,01,2 like before. We would have six equations like 5.123, plus six morewhere bi “ 0 for the bi’s not present. Then we may use the four regular coefficient extractions fromthe master functional equation for Qm,n1,2 and m,n ď 1 plus twelve more, where we set one or moreof b1 and b2 to zero. We have a grand total of 28 equations in 36 unknowns, of which we need toeliminate 32. A quick attempt to do this via computer yielded no results.73Chapter 6GeneralizationsIn this final chapter, we examine lattice walk models in more generality and we prove that a largeclass of models satisfy functional equations of the types we have seen already, namely p1´tΓSqQ “q. There is already some work towards generalizations, but most of is on a smaller scale. Forexample, Definition 1.1 of [7, p. 2] has a functional equation for non-interacting lattice walks onthe quarter plane with larger positive steps while the negative steps are limited to size at most one.For quarter plane models with small steps where multiple copies of steps are allowed, see [11]. Forsome more general regions, check [28, 21, 29] for walks on a semi-infinite strip. In [27] the authorconsiders lattice walks in an octant with interactions along the diagonal. Our theory allow us towrite down functional equations for all of these cases automatically.We start by examining marking operators in more generality. Then we move onto finding func-tional equations for general models. Finally, we look at some examples and ideas generated fromthem. Unfortunately, time did not suffice to explore this area to its full potential.6.1 Marking Operators And Functional EquationsWe start with the observation that operators that remove monomials are just marking operators withlabels set to zero, and therefore, we only consider marking operators for the rest of this work. Arather general operator is one that marks each point p in Zd with a unique label ap. This serves asour most general definition. We work with marking functions first and then express their action onmonomials via operators.Definition 6.1. Given a set A of labels and constants from some space over indeterminates, leta : Zd Ñ A be a marking function.It is sufficient that the labels and constants come from a complex space over the indeterminates.74Definition 6.2. Given a set of labels A, let UA be a set of marking functions on the space Zd. Wedefine addition and multiplication term-wise on points of Zd, using the operations in the set A.Proposition 6.3. The set of marking functions onZd together with addition and multiplication formsa commutative ring with identity. Furthermore, the ring is an integral domain. The set of invertiblemarking functions is comprised of functions with non-zero labels.Proof. If A is the whole space of labels and constants, the set U is the same as a Cartesian productof infinitely many copies of A, and it is not difficult to see that the properties of a commutative ringand an integral domain are satisfied. Here the additive identity is the marking function whose labelsare all 0, and the multiplicative identity is one whose labels are all 1.Since we are working with marking operators on Laurent polynomials and series, we need arepresentation for marking operators that allow us to compute things easily.Definition 6.4. Given a marking function a, let Γa be a marking operator defined by its action onmonomials: Γaxp “ appqxp for all p in Zd. We extend this definition by linearity to formal Laurentseries u “ řp upxp, where Γau “ řp appqupxp, and we write Γa “ řp appqrrxpss.We need to check that this formal definition for marking operators behaves as expected and thatit preserve the ring of functions UA. Expanding the action Γau gives˜ÿpappqrrxpss¸˜ÿquqxq¸“ÿp,qappqrrxpssuqxq “ÿp,qappquqδp,qxq “ÿpappqupxp . (6.1)Furthermore addition and multiplication work as expected:Γ1 ` Γ2 “ÿpa1ppqrrxpss `ÿpa2ppqrrxpss “ÿppa1ppq ` a2ppqqrrxpss , (6.2)Γ1Γ2 “˜ÿpa1ppqrrxpss¸˜ÿ1a2ppqrrxpss¸“ÿp,qa1ppqa2pqqrrxpssrrxqss“ÿp,qa1ppqa2pqqδpp, qqrrxpss“ÿpa1ppqa2ppqrrxpss .(6.3)We just need the following notation to allow us to express certain operators easily.75Definition 6.5. Let the term extraction operator be defined asrrxPI ss “ÿKPZd´nrrxP,KI,J ss , (6.4)where I “ H gives the identity operator 1 “ řprrxpss.Proposition 6.6. The set UA of marking operators with addition and multiplication, as definedin the preceding discussion, forms a commutative ring with identity. Furthermore, the ring is anintegral domain.Lemma 6.7. The marking operator Γa, as defined by a sum, is well-defined and has the secondaryform Γ “ 1`řppappq ´ 1qrrxpss, where the sum runs over all points in Zd with appq ‰ 1.Proof. Assume that another operator Γ1 behaves in the same way as in the definition. ThenΓu´ Γ1u “˜ÿpappqrrxpss¸˜ÿquqxq¸´ÿpappqupxp“ÿpappqupxp ´ÿpappqupxp “ 0 ,(6.5)and so the operator is well-defined. The second form follows by writing Γ “ 1 ` pΓ ´ 1q andexpanding the latter quantity.The following lemma is self-evident.Lemma 6.8. For each point p, the monomial xp is an eigenfunction of Γa with eigenvalue appq.Proposition 6.9. The eigenspaces of formal Laurent series for each eigenvalue λ of Γa are gener-ated by sums of monomials xp with appq “ λ.Proof. Let Γu “ λu for some formal Laurent series. Then the only surviving terms in Γu´ λu arethose with appq ‰ λ. However, since the quantity is zero, they are also forced to add up to zero.Therefore, the series u is comprised of terms with monomials xp for appq “ λ in the first place.Proposition 6.10. The space of Laurent series annihilated by Γa is generated by series of terms xpwhere ap “ 0.For all the problems so far, we had marking operators comprised of finitely many term extrac-tions and the identity 1, where each term extraction has less variables than the dimension d. As thefollowing example shows, sometimes a marking operator comprised of infinitely many term extrac-tions can sometimes be rewritten in terms of finitely many term extractions with less variables.76Example 6.11. For example, consider the operator Γ “ řp arrxpss where all points receive thesame label. Then Γ “ a.Sometimes, depending on the model, we may even have a smaller operator that does the samework as the full marking operator because of the geometry of the regions involved.Example 6.12. Consider a classical one-dimensional model with no interactions. Because we donot want lattice walks to step on negative coordinates, the full marking operator is given byΓ “ 1´8ÿn“1rrxnss . (6.6)However, since the lattice walk can never reach negative coordinates beyond negative one, we havethe equivalent form Γ1 “ 1´rrxss. Although the operators are different in form, they are essentiallythe same with regards to the problem at hand. We say the two operators are model-equivalent.To make the equivalence work, we need to consider the whole model. With that in mind, wecan think of the lattice walk models as living completely within the sumset D ` S. This is how farwalks from the model can possibly reach from within D by taking a single step. We call this sumsetthe range of the model. In the enumeration of lattice walks, we must eliminate all walks that take astep outside of D, but they remain in D ` S, so it is enough to remove walks in the complement ofD inside the sumset. Note that the walks do not necessarily reach all points in D`S as one can seein the case of reducible models.Definition 6.13. Given sets A and B, we let their sumset beA`B “ ta` b | a P A, b P Bu . (6.7)Definition 6.14. Let D ` S be the range of a lattice walk model with domain D and step set S.Definition 6.15. LetM be a lattice walk model in Zd and let Γ and Γ1 be two marking operators.Then Γ ”M Γ1 if and only if Γ and Γ1 act identically on monomials from the range ofM. That is,the operators are model-equivalent if and only if Γxp “ Γ1xp for all p P D ` S.In the preceding example, the operators are equivalent because they act the same way onmonomials from the range of the model, that is, monomials xk with k ě ´1. Similarly, inthe two-dimensional problem we have an equivalence between the operator E and the operatorE1 “ p1´ rrx1ssqp1´ rrx2ssq.77Definition 6.16. A marking operator Γ is finite with respect to a given model if it is equivalent toan operator Γ1 comprised of finitely many terms. That is,Γ ”M Γ1 “ÿIĎrdsJĎZdaI,J rrxJI ss , (6.8)where each set J is finite and aI,J is a label. Also, we say Γ is infinite if it is not finite.Lemma 6.17. A finite product of finite marking operators is finite.Definition 6.18. Given a d-dimensional model, let L be an operator that marks locations inD0 andlet E be the operator that removes walks outside of D. Then the marking operator correspondingto the model is Γa “ LE with marking function a which sends points p in D0 to their respectivelabels, and points outside of D to zero.When we work within the framework set by a specific model, we do not distinguish between Γand Γ1. A natural question is to consider which models lead to finite operators. This depends on theregion D and the nature of the marking of region D0. We have some cases where it is easy to say.Lemma 6.19. LetD be a finite box and let S be finite. Then the marking operator Γ “ LE is finite.Proof. The operator L is finite since it marks only finitely many points inside the box. We findE next. Let the box have xk coordinates in rak, bks. Suppose that the xk coordinates of the stepsare bounded in size by nk. If nk “ 0, the walks do not leave the xk “ ak hyperplane and thereis nothing to remove. When nk ą 0, we need to remove all monomials xP11 ¨ ¨ ¨xPdd with Pk Prak ´ nk, ak ´ 1s Y rbk ` 1, bk ` nks. Then E “ E1, . . . , Ed, whereEk “ 1´nkÿj“1rrxak´jk ss ` rrxbk`jk ss , (6.9)and Ek “ 1 when n “ 0. Each of these is finite and so is E.Note that the operators Ek remove monomials outside of the range of the model too, but thatallows us to write the operator down in a neater way.Theorem 6.20. The operator Γ “ LE is finite for models with finite D and S.Proof. The region D lies within a bounding box B, so we can write E “ E1E2, where E1 “E1 ¨ ¨ ¨Ed from the lemma and E2 is the operator removing all monomials outside of D but insidethe interior of B. E2 is finite since there are only finitely many points in that region. Since we aremarking only finitely many points, L is finite too, and finally, Γ is finite.78Also, we can handle partially-infinite regions, corresponding to boxes extended to infinity onsome sides, if we are marking only finitely many points. Here one or more of ak and bk is infiniteand we actually lose parts of Ek since no terms need to be removed at infinity. We can push thissome more and obtain the following result.Proposition 6.21. If L is finite and D is a box, except for a finite region, then Γ “ LE is finite too.Proof. This follows from the observation thatEB is finite andEB´ED is finite as well. The secondfact is true because the regions differ in a finite region.Definition 6.22. A lattice walk model with finitely many steps is finite if its marking operator Γ “LE is finite, and its initial condition q has finitely many terms. Otherwise, the model is infinite.Example 6.23. All the models so far have been finite, but not all models are finite. Consider a one-dimensional model on the whole line, where for each integer i, we mark point xi with parameter aiusing operator L. Then all equivalent marking operators L1 have to have a term like pai ´ 1qrrxiss;otherwise, it does not act the same way on monomials in the model’s range Z. Therefore, L is notequivalent to a finite operator.Finite models are nicer because they have functional equations with finitely many terms andthere is a chance that they may be amenable to the sort of analysis we have performed for quarterplane walk models in the past.Theorem 6.24. The generating function Q for a lattice walk model satisfies the equationsp1´ tLESqQ “ q , (6.10)pL´1 ´ tESqQ “ L´1pqq “ α . (6.11)Proof. Because of how we have set up the notation so far, the proof is analogous to the one inChapter 2 and Chapter 3. The second functional equation is obtained by applying L´1 to the firstone, so it only remains to show that the first functional equation holds. When we apply LE to tSQwe remove all monomials for walks ending outside of D and we mark all monomials for walksending in D0. We have almost obtained Q again, but the first term q0 “ q is missing, so we add itin. That is LEptSQq ` q “ Q´ q ` q “ Q and we are done.Corollary 6.25. When the model is finite, we can perform the coefficient extractions in the functionalequations to obtain explicit equations relating Q to various QJI terms.This follows because there are only finitely many extractions in the marking operators. It isnot clear if can have explicit functional equations for models with infinite operators, because therewould be infinitely-many QJI terms in the equation. We would need more theory in order to do that.796.1.1 Several Examples of Generalized ModelsIn the first two examples, we see some more general analysis of models. After that we considersome more concrete situations.Example 6.26. Typically, we have an operator Γ “ LE where E removes unwanted terms. Theproblem is that E is not invertible. We can recast the analysis in a way that circumvents that but atsome cost. Instead of using an operator E to remove walks, we can just just a marking operator thatlabels walks for later deletion, for example, with a variable z. We have a new lattice walk model ĂMwith rD “ Zd and rD0 “ D0 Y Dc, where we mark monomials in Dc with z and those in D0 in thesame way as in modelM. Here rE is the identity operator since we do not remove any walks. Wehave the functional equationsp1´ trLSq rQ “ q , (6.12)prL´1 ´ tSq rQ “ rα . (6.13)The downside is that we have more extractions than if we split the operator as Γ “ LE and onlyappliedL´1. If we obtained a solution for rQ, then we could find the originalQ by takingQ “ rz0s rQ.Example 6.27. We can also keep track of the walks’ histories of where they have been. To do this,we let Γ give a generic label to each point in space, that is, Γxp “ ap. In this setup, a growinglattice walk picks up a label at each point that it steps on. As in Example 6.23, the operator is notfinite, so we would not have an explicit functional equation with finitely many terms. Nevertheless,this allows us to frame self-avoiding within our theory.Suppose that Q is the generating function for walks with histories and let W be the generatingfunction for self-avoiding walks on the same space. Then we can obtain W from Q by setting allhigher powers of ap to zero. This is equivalent to picking out the a0p and ap coefficients from Q viasome operator A. Since there are only finitely many walks of a given length and they are bounded,for each step size, A reduces to a finite operator Ak, that is, W “ AQ “ ř8k“0Akpqkqtk.Formally, we can write Γ “ śp Γp and A “ śpAp, where the products go over the wholespace and Γp “ 1 ` pap ´ 1qrrxpss and Ap “ rra0pss ` rrapss. Now, suppose that W is already inthe form that we desire, that is, there are only a0p and ap terms for every p. Now, we fix a “ ap andx “ xp for some p to declutter the next calculation. We haveΛp “ ApΓp “ prra0ss ` rrassqp1` pa´ 1qrrxssq (6.14)“ ra0s ` aras ` pras ` ara0s ´ ra0s ´ arasqrrxss (6.15)“ p1` pa´ 1qrrxssqra0s ` p1´ rrxssqaras , (6.16)80and we identify this operator as Λp “ Γprra0pss `Eprrapss where Ep removes the monomial rrxpss.We can interpret this result in terms of the actions of the operators themselves. Since W containsself-avoiding walks only, when we take tSW , we only run into problems for points p where eachwalk has been at p at some earlier time of its growth. Thus, we may take all the walks ending onp for the first time and mark them with a, and remove those that have been there already. This isexactly what the Λp operator does. We can finally write a functional equation for the generatingfunction for self-avoiding walks:p1´ tΛSqW “ a0 , (6.17)where Λ “śp Λp. This operator is no longer invertible, but we can write W as the infinite seriesW “8ÿk“0pΛSqpkqpa0q , (6.18)where pΛSqpkq is finite because it only sees finitely many points.For example, using S “ x1 ` x1 ` x2 ` x2, we can compute the first few terms of the series:W “ a0,0 ` tpa´1,0a0,0x1 ` a1,0a0,0x1 ` a0,´1a0,0x2 ` a0,1a0,0x2q ¨ ¨ ¨ . (6.19)The following examples look at particular models with small steps in the plane.Example 6.28. Consider an infinite strip comprised of all the points with coordinates pi, jq in Z2with 0 ď j ď n, where the model interacts with the lines x2 “ 0 and x2 “ n. The operators areE “ E´1En`1 “ p1´ rrx2ssqp1´ rrxn`12 ssq “ 1´ rrx2ss ´ rrxn`12 ss , (6.20)L “ L0Ln “ p1` b0rrx02ssqp1` bnrrxn2 ssq “ 1` b0rrx02ss ` bnrrxn2 ss , (6.21)and the functional equation for Q is given byKQ´ pc0 ´ tx2S´12 qQ02 ´ xn2 pcn ´ tx2S12qQn2 “ a0 . (6.22)If we extract the rx02s term, we find thatp1´ a0tS02qQ02 ´ tS´12 Q12 “ 1 (6.23)81and if we extract the rxn2 s term, we find thatp1´ antS02qQn2 “ tS12Qn´12 . (6.24)Similarly, we can extract the xk2 coefficients for 1 ď k ď n´ 1. We have n` 1 equations where weneed to solve for the n` 1 unknown functions Q02, . . . , Qn2 . Of course, we only need Q02 and Qn2 toobtain a solution for Q. In the simplest case, n “ 1 and the term extraction equations becomep1´ a0tS02qQ02 “ 1` tS´12 Q12 , (6.25)p1´ a1tS02qQ12 “ tS12Q02 . (6.26)The solutions areQ02 “ 1´ a1tS02p1´ a0tS02qp1´ a1tS02q ´ S12S´12 t2, (6.27)Q12 “ S12tp1´ a0tS02qp1´ a1tS02q ´ S12S´12 t2, (6.28)and we can find Q explicitly fromQ “ 1Kpa0 ` pc0 ´ tx2S´12 qQ02 ` x2pc1 ´ tx2S12qQ12q . (6.29)Example 6.29. Consider a finite rectangle comprised of all the points with coordinates pi, jq in Z2with 0 ď i ď m and 0 ď j ď n, for some positive integers m and n. There are also interactionslike in the previous example. We use the operatorsEi,j “ 1´ rrxji ss and Li,j “ 1` bi,jrrxji ss (6.30)to find the functional equation. For the model itself, we haveE “ E1,´1E1,m`1E2,´1E2,n , (6.31)L “ L1,0L1,mL2,0L2,n . (6.32)Once we obtain a functional equation, we find that it has terms of the form Qji and Qi,j1,2. If weperform the extractions rxji s only, we have even more Q terms. However, if we perform the extrac-tions rxji s for all points pi, jq in the rectangle, we obtain pm ` 1qpn ` 1q equations in that manyQi,j1,2 terms. Since there is a unique solution Q, we can solve this system and write Q directly. Thedifficulty lies is in solving this system symbolically.This example paves the way towards the following result for finite models on finite regions.82Theorem 6.30. The generating function for a finite lattice walk model set on a finite region is arational function in its variables.Proof. Let n be the number of points in D. Then for each point P , we can extract the xPrds termfrom the functional equation p1´ tΓSqQ “ q and we only have Q terms of the form QIrds for pointsI inD. We have a system of n equations in n unknowns, and since the function Q is unique, we cansolve this system uniquely. Each of the coefficients is a rational function of the variables x1, . . . , xd,the labels aP , and t, and therefore, the solution is rational too.Of course, once the region grows to a moderate size, it becomes prohibitively complicated tosolve this system. For a box of side m, the number of equations is md, making this a difficult wayof solving the problem. If the size of the region is large and the number of steps in S is small, theneachQi,j1,2 depends on a few neighbours only, so the resulting linear system is rather sparse. Still, thesolution fills a whole page for a three-by-three square, so the result is mostly of theoretical value.6.2 Further Properties of Marking OperatorsSince the function Q is given by Neumann series, which is connected to integral equations, it maybe possible to find an analogue to Fredholm theory. Also, it may be possible to find a sort ofSturm-Liouville theory for lattice walk enumeration problems. In the next few pages, we look atthe first few steps of such a theory, although there was insufficient time to analyze this problem inmore detail. For that we would need a suitable inner product that would allow us to see if certainoperators are self-adjoint. Finally, we would need to find eigenfunction expansions for the functionsinvolved.The operators we have seen so far are marking operators, like L and E, in combination ofmultiplication by another function, like ΓS, or a combination of operators, like L´1 ´ tES. Welook at their eigenvalues, eigenvectors, kernels and invertibility.6.2.1 Marking Operators With MultiplicationDefinition 6.31. We call an operator inhomogeneous if it consists of a marking operator Γ and aLaurent polynomial S, and acts in one of the following waysΓSpuq “ ΓpSuq or S Γu “ S ¨ Γu . (6.33)The two definitions are equivalent when it comes to finding the eigenpairs.Proposition 6.32. The pair pλ, uq is an eigenpair of ΓS if and only if pλ, Suq is an eigenpair ofS Γ. In particular, if λ “ 0, then kerpΓSq “ S kerpΓq.83Proof. Note that ΓSu “ λu is equivalent to S ΓpSuq “ λpSuq. Therefore, the operators have thesame eigenvalues and their eigenfunctions are u and Su, respectively. Next, we pick λ “ 0 to findthe kernels of the operators. We find that u P kerpΓSq if and only if Su P kerpS Γq “ kerpΓq.Since this characterizes the kernel of the operator, we assume that λ ‰ 0 from here on. Next,we find some eigenpairs. Let Γ “ LE as before. Recall that E2 “ E, since once the terms areremoved, they cannot be removed again. We can apply E on both sides of LESu “ λu to find thatEpλuq “ λEu “ ELESu “ LE2Su “ LESu “ λu , (6.34)and therefore, Eu “ u.Lemma 6.33. If u is an eigenfunction of the operator LES, then Eu “ u and u P kerE1, whereE1 “ E ´ 1 is the pure coefficient extraction part of E.Suppose that Γ “ LE. In the interest of performing fewer extractions, we rewrite the eigen-problem ΓSu “ λu as ESu “ λMu, where M “ L´1. Since each operator is the identity plus asum of extractions, we rewrite the operators as E “ E ´ 1` 1 “ 1`E1 and M “ 1`M 1, whereE1 and M 1 are purely extractions. Using these relations, we can rewrite the function u asu “ pλM1 ´ E1SquS ´ λ , (6.35)where if the operators are finite, the extraction in the numerator leads to a Laurent polynomialin the variables x1, . . . , xd. Because we used M 1 and E1 instead of the equivalent for LE, wehave fewer coefficients in the numerator. The resulting eigenfunction u depends on finitely manycoefficients. We can expand u in Laurent series around the origin, set the coefficients to zero, andthen solve the resulting system of equations to find the terms in the numerator. Curiously, if weapply D “ λM ´ ES on u we should find that Du “ 0, but here u has a new form and we obtainsome condition on the terms in the numerator.Example 6.34. Consider one of the classical one-dimensional model with interactions, where S “x` x and M 1 “ ´crx0s. First we use the full operator E1 “ ´ř8k“1rrxkss. Since u has no termsuk for k ď ´1, we see that´E1Su “8ÿk“1xkprxk`1s ` rxk´1squ “8ÿk“1xkpu´k´1 ` u´k`1q “ xu0 . (6.36)84Thenu “ ´λcu0 ` xu0x` x´ λ “p1´ cλxqu01´ λx` x2 “ u0 ` aλu0x` ¨ ¨ ¨ , (6.37)where u0 is a free variable, and there is an eigenfunction for every λ. Next, we use the equivalentoperator E “ 1´rrxss. We have no reason to believe that the operator has the same eigenfunctions,but it does. To show this, we first write u asu “ pλM1 ´ E1SquSλ“ ´cλu0 ` pu´2 ` u0qxx` x´ λ “u´2 ` p1´ cλxqu01´ λx` x2 , (6.38)We apply the D on u to find that ´bλu´2 “ 0, so u´2 “ 0 and the eigenfunctions are the same.It turns out that this is not a coincidence and we have the following striking result.Proposition 6.35. The set of eigenpairs of the full marking operator associated with a lattice walkmodel is a subset of the set of eigenpairs for any equivalent but reduced operator. Here reducedmeans a change to the marking portion and a reduction of terms in the extraction portion.Proof. Let Γ1 “ L1E1 be the full operator and Γ2 “ L2E2 be the reduced one. Here L1 and L2agree on D, and E1 and E2 agree on the range D`S. Suppose that Γ1Su “ λu for some eigenpairpλ, uq. By Lemma 6.33, u only contains terms from D and therefore, Su only contains terms fromthe range of the model. Therefore, Γ1Su “ L1E1Su “ L2E2Su due to the agreement of operators,and finally, Γ2Su “ λu.The proof here also shows us that Γ2 may have other eigenfunctions v, since here v may containterms from outside of the range of the model. However, if Γ2 is finite, we see that pλM 1´E1Squ hasfinitely many terms. Thus, each eigenvalue λ may lead to at most a finite-dimensional eigenspace.In the end, we need to work with the operator L “ 1 ´ tΓS since it is the one that is involvedin the functional equation for Q. If we are to find a theory where we can expand Q in terms ofeigenfunction of operators, we need to obtain the same results whether we use the full or reducedform of the operators. That is, most likely, we do not need the extra eigenpairs that the reducedoperator may have. We have the following definitions.Definition 6.36. Let L “ 1´ tΓS be a lattice walk operator.Definition 6.37. The natural eigenpairs of a marking operator are the eigenpairs associated withthe full operator. The natural eigenpairs of a lattice walk operator are those coming from the fullform of the marking operator within it.85Let pλ, uq be a natural eigenpair of L. We find thatpL´ λIqu “ u´ λu´ tΓSutΓSu “ p1´ λqu , (6.39)and the eigenpairs of L are closely related to those of ΓS. If λ “ 1, then u is in kerptΓSq “ S ker Γand we already know how to find these functions. If λ ‰ 1, we can find the eigenpairs by themethod in the previous section. Let µ “ 1´ λ. Thenu “ pp1´ λqM1 ´ tE1Squλ´K , (6.40)where K “ 1´ tS and the numerator only features monomials for points within D.Example 6.38. Consider a classical interacting two-dimensional model. The functional equationis pµ ´ tLESqu “ 0 and we let µ “ t{ν. If we apply M on both sides, we find that the naturaleigenpairs of L satisfy0 “ pνM ´ ESqu “ÿIĎrdsp´1q|I|pνcI ´ xIS´1I u0I q “ νÿIĎrdsp´1q|I|KIpνqu0I , (6.41)where KI “ KIpx, νq are Laurent polynomials as in the master functional equation. So the eigen-functions u satisfy an equation similar to the master functional equation for the associated latticewalk model. Take d “ 1, for example. Then u satisfies Ku´K1u0 “ 0 and it is given byu “ K1px, νqKpx, νq “c´ νxS´11´ νS u0 (6.42)for every ν ‰ 0. The constant u0 is arbitrary, so we set it to 1. If we let Sě0 “ S ´ xS´1, we canexpand u in terms of ν asupx, νq “ c´ aνpS ´ aSě0qp1` Sν ` S2ν2 ` ¨ ¨ ¨ q . (6.43)For the model S “ x` x in Chapter 2, we can solve for Q in terms of u. That is,Q “ 1aKpx, tqˆ1` K1px, tqK1pσ, tq˙“ 1aKpx, tq `upx, tqaK1pσ, tq , (6.44)so we have found a connection between Q and the eigenfunctions of the lattice walk operator. Thisis as far as we will go for now.86Chapter 7ConclusionIn this thesis, we looked at the problem of generalizing methods for handling lattice walk enumer-ation in many dimensions and with more general constraints, as well as models with interactions.In the earlier chapters, we used refined notation and a new perspective of applying operators onfunctions and functional equations. We were able to derive the functional equations for classicald-dimensional models with ease. This allowed us to generalize the methods to derive a functionalequation for a much more general class of models. This is one more step towards finding out if wecan automate the solving and classification of more complex lattice walk models. However, oneof the limitations of using operators is that it may be difficult to find finite equivalent operators forsome rather tame-looking regions, like a wedge. It is not clear if this is due to a shortcoming ofthe operator notation or if this is due to some more fundamental differences between quarter planemodels and those on wedges.We were also able to extend the algebraic and obstinate kernel methods to lattice walk modelswith interactions, although there is still a fair amount of work that needs to be done. First, the alge-braic kernel method does not work in a lot of cases of finite groups when the model has interactions,and in those cases that it does work, it does not succeed in eliminating the Q0,01,2 term. The resultingformulae still need to be worked through. At best, we hope that in those cases, if the function Q0,01,2is D-finite, then the full generating function Q is D-finite too.In the extension of the obstinate kernel method, we were able to find relations between Q0,01,2and its various partially-marked versions for two nontrivial models — the Cartesian and Diagonalmodels. However, we were not able to find such a relation for the Full model. It also remains to beseen if the cases with fewer transformations that preserve the admissibility of the functions Q0i canalso be tackled. The problem of solving functional equations in a closed form for more generalizedmodels is wide open.877.1 Future ResearchIn closing, the research for this thesis produced many ideas for future work, and since there weretoo many to pursue, we list them here for the interested reader.• Algebraic kernel method.– For finite group cases, can say that Q is D-finite if Q0,01,2 happens to be D-finite?– Determine if the method can be extended to higher-dimensional models with interac-tions and/or models with larger steps.– Consider annihilation of terms in the functional equations by other operators, like dif-ferential ones, and if this can be used to find out more about the generating functions.• Obstinate kernel method.– Can identities like BpFQ0,01,2q “ 0 be explained combinatorially? The one-dimensionalmodel relations would be a good place to start.– Find Q for the Diagonal model in terms of partially-marked versions of Q and Q0,01,2.– Find out if there is a similar relationship for Q0,01,2 in the Full model.– Solve some of the enumeration problems with other groups, like those of order six.• Kernel methods in general.– Determine if the algebraic and obstinate kernel methods can be combined into one holis-tic approach. This can involve classifying methods on the number of substitutions made.– Can the methods be extended to more generalized models?• Connections with other theory.– Using the Cauchy integral formula, we can rewrite extractions as complex integrals.This suggests that some of the equations can be turned into multivariable Fredholmintegral equations. Perhaps methods from that area can be adapted to this one.– Can we adapt Sturm-Liouville theory to lattice walk enumeration? In particular, can wefind a suitable inner product for Laurent series to test operators for self-adjointness andcan we expand Q in terms of eigenfunctions of the lattice walk operator?– Can we find asymptotics for lattice walks directly from the operator equations?88Bibliography[1] A. A. Monforte and M. Kauers, “Formal laurent series in several variables,” ExpositionesMathematicae, vol. 31, no. 4, pp. 350–367, 2013. Ñ pages 5[2] I. P. Goulden and D. M. Jackson, Combinatorial enumeration. Courier Corporation, 2004. Ñpages 6[3] I. M. Gessel, “A factorization for formal laurent series and lattice path enumeration,” Journalof Combinatorial Theory, Series A, vol. 28, no. 3, pp. 321–337, 1980. Ñ pages 2[4] M. Bousquet-Me´lou and M. Petkovsˇek, “Linear recurrences with constant coefficients: themultivariate case,” Discrete Mathematics, vol. 225, no. 1, pp. 51–75, 2000. Ñ pages 2[5] P. Duchon, “On the enumeration and generation of generalized dyck words,” DiscreteMathematics, vol. 225, no. 1, pp. 121–135, 2000. Ñ pages 2[6] C. Banderier and P. Flajolet, “Basic analytic combinatorics of directed lattice paths,”Theoretical Computer Science, vol. 281, no. 1, pp. 37–80, 2002. Ñ pages 2[7] M. Mishna, “Classifying lattice walks restricted to the quarter plane,” Journal ofCombinatorial Theory, Series A, vol. 116, no. 2, pp. 460–477, 2009. Ñ pages 2, 74[8] M. Bousquet-Me´lou and M. Mishna, “Walks with small steps in the quarter plane,” Contemp.Math, vol. 520, pp. 1–40, 2010. Ñ pages 2, 11, 14, 19, 27, 28, 29, 37, 38, 39, 40, 41, 43[9] M. Bousquet-Me´lou et al., “Walks in the quarter plane: Kreweras algebraic model,” TheAnnals of Applied Probability, vol. 15, no. 2, pp. 1451–1491, 2005. Ñ pages 2[10] A. Bostan and M. Kauers, “The complete generating function for gessel walks is algebraic,”Proceedings of the American Mathematical Society, vol. 138, no. 9, pp. 3063–3078, 2010. Ñpages 2[11] M. Kauers and R. Yatchak, “Walks in the Quarter Plane with Multiple Steps,” CHECK IT!,November 2014. Ñ pages 2, 29, 74[12] I. Kurkova and K. Raschel, “Explicit expression for the generating function counting gessel’swalks,” Advances in Applied Mathematics, vol. 47, no. 3, pp. 414–433, 2011. Ñ pages 289[13] A. Bostan, K. Raschel, and B. Salvy, “Non-d-finite excursions in the quarter plane,” Journalof Combinatorial Theory, Series A, vol. 121, pp. 45–63, 2014. Ñ pages 2[14] S. Melczer and M. Mishna, “Singularity analysis via the iterated kernel method,”Combinatorics, Probability and Computing, vol. 23, no. 05, pp. 861–888, 2014. Ñ pages 2[15] S. R. Melczer, Variants of the kernel method for lattice path models. MSc thesis, SimonFraser University, 2014. Ñ pages 2, 11, 19, 20, 40[16] I. M. Gessel and D. Zeilberger, “Random walk in a weyl chamber,” Proceedings of theAmerican Mathematical Society, vol. 115, no. 1, pp. 27–31, 1992. Ñ pages 2[17] D. J. Grabiner and P. Magyar, “Random walks in weyl chambers and the decomposition oftensor powers,” Journal of Algebraic Combinatorics, vol. 2, no. 3, pp. 239–260, 1993. Ñpages 2[18] A. Bostan, M. Bousquet-Me´lou, M. Kauers, and S. Melczer, “On 3-dimensional lattice walksconfined to the positive octant,” arXiv preprint arXiv:1409.3669, 2014. Ñ pages 2, 25, 38,40, 41[19] E. J. Van Rensburg and A. Rechnitzer, “Multiple markov chain monte carlo study ofadsorbing self-avoiding walks in two and in three dimensions,” Journal of Physics A:Mathematical and General, vol. 37, no. 27, p. 6875, 2004. Ñ pages 2[20] R. Brak, P. Dyke, J. Lee, A. Owczarek, T. Prellberg, A. Rechnitzer, and S. Whittington, “Aself-interacting partially directed walk subject to a force,” Journal of Physics A:Mathematical and Theoretical, vol. 42, no. 8, p. 085001, 2009. Ñ pages 2[21] T. Wong, A. Owczarek, and A. Rechnitzer, “Confining multiple polymers between stickywalls: a directed walk model of two polymers,” Journal of Physics A: Mathematical andTheoretical, vol. 47, no. 41, p. 415002, 2014. Ñ pages 2, 11, 13, 19, 41, 48, 67, 74[22] Y.-b. Chan and A. Rechnitzer, “A monte carlo study of non-trapped self-avoiding walks,”Journal of Physics A: Mathematical and Theoretical, vol. 45, no. 40, p. 405004, 2012. Ñpages 2[23] A. Bacher and M. Bousquet-Me´lou, “Weakly directed self-avoiding walks,” Journal ofCombinatorial Theory, Series A, vol. 118, no. 8, pp. 2365–2391, 2011. Ñ pages 2[24] A. Bedini, A. L. Owczarek, and T. Prellberg, “Lattice polymers with two competing collapseinteractions,” Journal of Physics A: Mathematical and Theoretical, vol. 47, no. 14, p. 145002,2014. Ñ pages 2[25] E. Dagrosa, A. Owczarek, and T. Prellberg, “Writhe-induced knotting in a lattice polymer,”Journal of Physics A: Mathematical and Theoretical, vol. 48, no. 6, p. 065002, 2015. Ñpages 290[26] H. Niederhausen, “Random walks in octants, and related structures,” Journal of statisticalplanning and inference, vol. 135, no. 1, pp. 165–196, 2005. Ñ pages 2[27] H. Niederhausen, “A note on the enumeration of diffusion walks in the first octant by theirnumber of contacts with the diagonal,” Journal of Integer Sequences, vol. 8, no. 2, p. 3, 2005.Ñ pages 2, 74[28] R. Brak, A. L. Owczarek, A. Rechnitzer, and S. G. Whittington, “A directed walk model of along chain polymer in a slit with attractive walls,” Journal of Physics A: Mathematical andGeneral, vol. 38, no. 20, p. 4309, 2005. Ñ pages 3, 74[29] A. L. Owczarek and T. Prellberg, “Enumeration of area-weighted dyck paths with restrictedheight,” Aust. J. Comb, 2012. Ñ pages 3, 74[30] R. Tabbara, A. Owczarek, and A. Rechnitzer, “An exact solution of two friendly interactingdirected walks near a sticky wall,” Journal of Physics A: Mathematical and Theoretical,vol. 47, no. 1, p. 015202, 2014. Ñ pages 3, 11, 13, 19, 31, 54, 55, 61, 63[31] I. M. Gessel, “Symmetric functions and p-recursiveness,” Journal of Combinatorial Theory,Series A, vol. 53, no. 2, pp. 257–285, 1990. Ñ pages 3[32] F. Chyzak, M. Mishna, and B. Salvy, “Effective scalar products of d-finite symmetricfunctions,” Journal of Combinatorial Theory, Series A, vol. 112, no. 1, pp. 1–43, 2005. Ñpages 3[33] M. Mishna, A holonomic systems approach to algebraic combinatorics. Montre´al: Universite´du Que´bec a` Montre´al, 2005. Ñ pages 3[34] A. Bostan and M. Kauers, “Automatic classification of restricted lattice walks,” DMTCSProceedings, no. 1, pp. 201–215, 2009. Ñ pages 3[35] M. Kauers and D. Zeilberger, “The computational challenge of enumerating high-dimensionalrook walks,” Advances in Applied Mathematics, vol. 47, no. 4, pp. 813–819, 2011. Ñ pages 3[36] S. Johnson, M. Mishna, and K. Yeats, “Towards a combinatorial understanding of lattice pathasymptotics,” arXiv preprint arXiv:1305.7418, 2013. Ñ pages 3[37] S. Melczer and M. Mishna, “Asymptotic lattice path enumeration using diagonals,”Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, p. 313,2014. Ñ pages 3[38] S. Melczer and M. Mishna, “Enumerating lattice paths with symmetries through multivariatediagonals,” arXiv preprint arXiv:1402.1230, 2014. Ñ pages 3[39] S. Johnson, Analytic combinatorics of planar lattice paths. MSc thesis, Simon FraserUniversity, 2013. Ñ pages 391
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Multidimensional lattice walk enumeration through coefficient...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Multidimensional lattice walk enumeration through coefficient extraction operators Vlasev, Aleksandar 2015
pdf
Page Metadata
Item Metadata
Title | Multidimensional lattice walk enumeration through coefficient extraction operators |
Creator |
Vlasev, Aleksandar |
Publisher | University of British Columbia |
Date Issued | 2015 |
Description | In this thesis, we investigate the enumeration of lattice walk models, with or without interactions, in multiple dimensions, through the use of linear operators comprised of coefficient or term extractions. This is done with the goal of furthering our abilities to automate the derivation and solutions of the functional equations for the generating functions for the models. In particular, for a fairly large class of d-dimensional lattice walk models with interactions and arbitrary step sets, the generating function Q satisfies the functional equation (1 - tΓS)Q = q, where Γ is an operator, and S and q are Laurent polynomials. We can automatically expand this equation to obtain an explicit functional equation satisfied by Q. For example, we derive an equation for d-dimensional lattice walks with interactions and small steps living in an orthant. We also use this operator approach to unify and extend the algebraic and obstinate kernel methods through the use of a weighted orbit summation operator and substitutions. Other topics include: a partial classification of two-dimensional models with interactions and small steps on the quarter plane, explicit relations for Q and partially-interacting versions of itself for some models, and an analysis of some of the more abstract properties of the operators involved. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2015-10-24 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0165809 |
URI | http://hdl.handle.net/2429/54805 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2015-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2015_november_vlasev_aleksandar.pdf [ 484.77kB ]
- Metadata
- JSON: 24-1.0165809.json
- JSON-LD: 24-1.0165809-ld.json
- RDF/XML (Pretty): 24-1.0165809-rdf.xml
- RDF/JSON: 24-1.0165809-rdf.json
- Turtle: 24-1.0165809-turtle.txt
- N-Triples: 24-1.0165809-rdf-ntriples.txt
- Original Record: 24-1.0165809-source.json
- Full Text
- 24-1.0165809-fulltext.txt
- Citation
- 24-1.0165809.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0165809/manifest