\( \gdef\badDispatch#1{\textbf{\textcolor{e1432d}{#1}}} \gdef\rarrbar{ {\raisebox{-0.05em}{→}\mkern{-0.13em}{\large\shortmid}}} \gdef\larrbar{ { {\large\shortmid}\mkern{-0.13em}{\raisebox{-0.05em}{←}}}} \gdef\suptrans{^\mathsf{T}} \gdef\supdagger{^\dagger} \gdef\rawsymbol#1{\operatorname{#1}} \gdef\colorsymbol#1#2{\textcolor{#1}{\rawsymbol{#2}}} \gdef\lsymbol#1{\colorsymbol{262626}{#1}} \gdef\msymbol#1{\colorsymbol{b50800}{#1}} \gdef\osymbol#1{\colorsymbol{00427f}{#1}} \gdef\lstring#1{\textcolor{666666}{\textrm{\textquotedblleft{#1}\textquotedblright}}} \gdef\boldForm#1{\textbf{#1}} \gdef\rform#1{ {\textcolor{e1432d}{#1}}} \gdef\gform#1{ {\textcolor{4ea82a}{#1}}} \gdef\bform#1{ {\textcolor{3e81c3}{#1}}} \gdef\rgform#1{ {\textcolor{dc841a}{#1}}} \gdef\gbform#1{ {\textcolor{47a5a7}{#1}}} \gdef\rbform#1{ {\textcolor{c74883}{#1}}} \gdef\waform#1{ {\textcolor{6b6b6b}{#1}}} \gdef\wbform#1{ {\textcolor{929292}{#1}}} \gdef\wcform#1{ {\textcolor{c5c5c5}{#1}}} \gdef\barToken{\mathbf{|}} \gdef\filledRectangleToken{▮} \gdef\emptyRectangleToken{▯} \gdef\filledToken{∙} \gdef\emptyToken{∘} \gdef\cardinalRewrite#1#2{\rewrite{#1}{#2}} \gdef\primed#1{ {#1}^{\prime}} \gdef\tinybullet{ {\tiny●}} \gdef\forwardFactor{\uparrow} \gdef\backwardFactor{\downarrow} \gdef\neutralFactor{\mid} \gdef\arrowhead{⏵} \gdef\deSymbol{ { { {\raisebox{1.1pt}{\tinybullet}\mkern{-1pt}{→}}}\,}} \gdef\ueSymbol{ {\raisebox{1pt}{\tinybullet\raisebox{-0.03em}{\mkern{-0.3pt}{\tiny──}\mkern{-0.3pt}}\tinybullet}\,}} \gdef\ldeSymbol{ { { {\raisebox{1.1pt}{\tinybullet}\mkern{-1pt}{\longrightarrow}}}\,}} \gdef\lueSymbol{ {\raisebox{1pt}{\tinybullet\raisebox{-0.03em}{\mkern{-0.3pt}{\tiny────}\mkern{-0.3pt}}\tinybullet}\,}} \gdef\de#1#2{ { {#1} \deSymbol {#2}}} \gdef\ue#1#2{ { {#1} \ueSymbol {#2}}} \gdef\tde#1#2#3{ { {#1} \overset{#3}{\deSymbol} {#2}}} \gdef\tue#1#2#3{ { {#1} \overset{#3}{\ueSymbol} {#2}}} \gdef\ltde#1#2#3{ { {#1} \overset{#3}{\ldeSymbol} {#2}}} \gdef\ltue#1#2#3{ { {#1} \overset{#3}{\lueSymbol} {#2}}} \gdef\mapsfrom{\htmlClass{hreflect}{\mapsto}} \gdef\longmapsfrom{\htmlClass{hreflect}{\longmapsto}} \gdef\diffd{𝕕} \gdef\partialdof#1{\partial {#1}} \gdef\emptySet{\empty} \gdef\unknown{\wbform{\text{?}}} \gdef\notApplicable{\wbform{\text{---}}} \gdef\isomorphicSymbol{\cong} \gdef\homotopicSymbol{\simeq} \gdef\approxEqualSymbol{\approx} \gdef\defEqualSymbol{\;≝\;} \gdef\ruledelayed{:\to} \gdef\mathdollar{\text{\textdollar}} \gdef\hyphen{\text{-}} \gdef\endash{\text{--}} \gdef\emdash{\text{---}} \gdef\updownarrows{\uparrow\!\downarrow} \gdef\vthinspace{\mkern{1pt}} \gdef\dlq{\text{\textquotedblleft}} \gdef\drq{\text{\textquotedblright}} \gdef\dprime{ {\prime\prime}} \gdef\inverse#1{ { {#1}^{-1}}} \gdef\inverseSymbol{\inverse{□}} \gdef\groupInverse{\inverse} \gdef\groupPower#1#2{ {#1}^{#2}} \gdef\groupCommutator#1#2{\left[{#1},{#2}\right]} \gdef\groupoidInverse{\inverse} \gdef\latticeBFS#1{\textrm{bfs}({#1})} \gdef\pathHomomorphism#1{#1} \gdef\groupoidFunction#1{#1} \gdef\affineModifier#1{\overrightharpoon{#1}} \gdef\supercirc#1{#1^{\circ}} \gdef\supercircb#1{#1\!\degree} \gdef\toroidalModifier#1{\supercirc{#1}} \gdef\modulo#1{\supercirc{#1}} \gdef\dividesSymbol{\,|\,} \gdef\groupFunction#1{#1} \gdef\gl#1#2{GL({#1},#2)} \gdef\automorphisms{\operatorname{Aut}} \gdef\transportMap#1{\transportMapSymbol_{#1}} \gdef\transportMapSymbol{\tau} \gdef\cardinalGroup#1{G^*({#1})} \gdef\signed#1{ {#1}^*} \gdef\transportAtlas#1{T_{#1}} \gdef\negated#1{\underline{#1}} \gdef\mirror#1{\overline{#1}} \gdef\pathComposeSymbol{ {\,∷\,}} \gdef\pathCompose#1#2{ {#1}\pathComposeSymbol{#2}} \gdef\translateSymbol{\uparrow} \gdef\backwardTranslateSymbol{\downarrow} \gdef\pathTranslate#1#2{ {#1}\,\translateSymbol\,{#2}} \gdef\pathLeftTranslate#1{ {#1}{\,\translateSymbol}} \gdef\pathBackwardTranslate#1#2{ {#1}{\,\backwardTranslateSymbol\,}{#2}} \gdef\pathLeftBackwardTranslate#1{ {#1}{\,\backwardTranslateSymbol}} \gdef\forwardDifference{\Delta^{+}} \gdef\backwardDifference{\Delta^{-}} \gdef\centralDifference{\Delta} \gdef\pathForwardDifference#1{\forwardDifference_{#1}} \gdef\pathBackwardDifference#1{\backwardDifference_{#1}} \gdef\pathCentralDifference#1{\centralDifference_{#1}} \gdef\pathHeadVector#1{ {#1}^{\bullet}} \gdef\pathTailVector#1{ {#1}_{\bullet}} \gdef\pathReverse#1{ {#1}^{\dagger}} \gdef\pathIntegral#1#2{ {#1} \int {#2}} \gdef\pathIntegralSymbol{ {\int}} \gdef\pathDot#1#2{ {#1} \cdot {#2}} \gdef\pathDotSymbol{ {\cdot}} \gdef\compactBasis#1{\mathscr{B}} \gdef\length{\operatorname{len}} \gdef\signedLength{\operatorname{len^*}} \gdef\andFn{\operatorname{and}} \gdef\orFn{\operatorname{or}} \gdef\notFn{\operatorname{not}} \gdef\vertexList{\operatorname{vertices}} \gdef\vertexList{\operatorname{vertices}} \gdef\edgeList{\operatorname{edges}} \gdef\pathList{\operatorname{paths}} \gdef\cardinalList{\operatorname{cards}} \gdef\signedCardinalList{\operatorname{cards^*}} \gdef\wordOf{\operatorname{word}} \gdef\headVertex{\operatorname{head}} \gdef\tailVertex{\operatorname{tail}} \gdef\basis{\operatorname{basis}} \gdef\split{\operatorname{split}} \gdef\lcm{\operatorname{lcm}} \gdef\minimalContractionSets{\operatorname{MCSets}} \gdef\minimalContractions{\operatorname{MC}} \gdef\grade{\operatorname{grade}} \gdef\support{\operatorname{support}} \gdef\isPrime#1{#1\textrm{ prime}} \gdef\blank{\_} \gdef\emptyWord{} \gdef\wordSymbol#1{\mathtt{#1}} \gdef\word#1{#1} \gdef\pathMap#1{#1} \gdef\function#1{#1} \gdef\pathWord#1#2#3{ {#1}\!:\!{#2}\!:\!{#3}} \gdef\nullPath{\bot} \gdef\nullElement{\bot} \gdef\path#1{#1} \gdef\vert#1{#1} \gdef\tvert#1{\underset{\raisebox{0.3em}{.}}{#1}} \gdef\hvert#1{\dot{#1}} \gdef\edge#1{#1} \gdef\card#1{\mathtt{#1}} \gdef\path#1{#1} \gdef\quiver#1{#1} \gdef\bindSize#1#2{#1(#2)} \gdef\bindCards#1#2{#1[#2]} \gdef\subSize#1#2{#1_{#2}} \gdef\gridQuiver#1{\textrm{Grid}^{#1}} \gdef\treeQuiver#1{\textrm{Tree}^{#1}} \gdef\bouquetQuiver#1{\textrm{Bq}^{#1}} \gdef\lineQuiver{\textrm{L}} \gdef\cycleQuiver{\textrm{C}} \gdef\squareQuiver{\textrm{Sq}} \gdef\cubicQuiver{\textrm{Cbc}} \gdef\triangularQuiver{\textrm{Tri}} \gdef\hexagonalQuiver{\textrm{Hex}} \gdef\rhombilleQuiver{\textrm{Rmb}} \gdef\limit#1#2{\lim_{#2}\,#1} \gdef\groupoid#1{#1} \gdef\group#1{#1} \gdef\field#1{#1} \gdef\ring#1{#1} \gdef\semiring#1{#1} \gdef\sym#1{#1} \gdef\matrix#1{#1} \gdef\matrixDotSymbol{\cdot} \gdef\wordGroup#1{\Omega_{#1}} \gdef\basisPath#1#2{\mathbf{#1}_{#2}} \gdef\basisPathWeight#1#2{ {#1}_{#2}} \gdef\unitSymbol{\mathbf{e}} \gdef\unitVertexField{\unitSymbol_1} \gdef\forwardSymbol{f} \gdef\backwardSymbol{b} \gdef\symmetricSymbol{s} \gdef\antisymmetricSymbol{a} \gdef\wordVector#1#2{\unitSymbol_{#1}^{#2}} \gdef\gradOf#1{\grad\,{#1}} \gdef\grad{\nabla} \gdef\divOf#1{\div\,{#1}} \gdef\div{\dot{\nabla}} \gdef\laplacianOf#1{\laplacian\,{#1}} \gdef\laplacian{\ddot{\nabla}} \gdef\suchThat#1#2{ {#1}|{#2}} \gdef\chart#1{\chartSymbol_{#1}} \gdef\chartSymbol{C} \gdef\graphRegionIntersectionSymbol{\cap} \gdef\graphRegionUnionSymbol{\cup} \gdef\pathIso{\simeq} \gdef\power#1#2{ {#1}^{#2}} \gdef\repeatedPower#1#2{ {#1}^{#2}} \gdef\contractionLattice#1{\operatorname{Con}(#1)} \gdef\contractedRelation#1{\sim_{#1}} \gdef\isContracted#1#2{ {#1} \sim {#2}} \gdef\isContractedIn#1#2#3{ {#1} \sim_{#3} {#2}} \gdef\isNotContracted#1#2{ {#1} \not \sim {#2}} \gdef\isNotContractedIn#1#2#3{ {#1} \not \sim_{#3} {#2}} \gdef\contractionSum#1{#1} \gdef\contractionSumSymbol{\sqcup} \gdef\contractionProduct#1{#1} \gdef\contractionProductSymbol{ {\cdot}} \gdef\graph#1{#1} \gdef\graphHomomorphism#1{#1} \gdef\coversSymbol{\sqsupseteq} \gdef\coveredBySymbol{\sqsubseteq} \gdef\strictlyCoversSymbol{\sqsupset} \gdef\strictlyCoveredBySymbol{\sqsubset} \gdef\covering#1#2#3{ {#2} \sqsupseteq_{#1} {#3}} \gdef\powerSet#1{\powerSetSymbol({#1})} \gdef\powerSetSymbol{\mathsc{P}} \gdef\notted#1{\notSymbol {#1}} \gdef\andSymbol{\land} \gdef\orSymbol{\lor} \gdef\notSymbol{\lnot} \gdef\latticeElement#1{#1} \gdef\latticeMeetSymbol{\wedge} \gdef\latticeJoinSymbol{\vee} \gdef\latticeTop{\top} \gdef\latticeBottom{\bot} \gdef\latticeGreaterSymbol{>} \gdef\latticeGreaterEqualSymbol{\ge} \gdef\latticeLessSymbol{<} \gdef\latticeLessEqualSymbol{\le} \gdef\symmetricGroup#1{Sym_{#1}} \gdef\groupPresentation#1#2{\left\langle\,{#1}\,\,\middle|\mathstrut\,\,{#2}\,\right\rangle} \gdef\groupRelationIso{=} \gdef\groupGenerator#1{#1} \gdef\groupElement#1{#1} \gdef\groupoidElement#1{#1} \gdef\setConstructor#1#2{\left\{\,{#1}\,\,\middle|\mathstrut\,\,{#2}\,\right\}} \gdef\constructor#1#2{\left.{#1}\,\,\middle|\mathstrut\,\,{#2}\right.} \gdef\elemOf#1#2{ { {#1} \in {#2} }} \gdef\edgeOf#1#2{ { {#1} {\in}_E {#2} }} \gdef\vertOf#1#2{ { {#1} {\in}_V {#2} }} \gdef\pathOf#1#2{ { {#1} {\in}_P {#2} }} \gdef\vertices#1{ V_{#1} } \gdef\edges#1{ E_{#1} } \gdef\vertexField#1{#1} \gdef\edgeField#1{#1} \gdef\pathVector#1{\mathbf{#1}} \gdef\pathVectorSpace#1{\mathscr{#1}} \gdef\baseField#1{#1} \gdef\finiteField#1{\mathbb{F}_{#1}} \gdef\functionSpace#1#2{#2^{#1}} \gdef\pathGroupoid#1{ { \Gamma_{#1} }} \gdef\forwardPathQuiver#1#2{ {\overrightharpoon{#1}_{#2}}} \gdef\backwardPathQuiver#1#2{ {\overrightharpoon{#1}^{#2}}} \gdef\pathQuiver#1{ {\overrightharpoon{#1}}} \gdef\mto#1#2{ {#1}\mapsto{#2}} \gdef\mtoSymbol{\mapsto} \gdef\rewrite#1#2{ {#1}\mapsto{#2}} \gdef\rewritingRule#1#2{ {#1}\mapsto{#2}} \gdef\rewritingSystem#1{\mathcal{#1}} \gdef\multiwayBFS#1{\textrm{bfs}({#1})} \gdef\rewritingStateBinding#1#2{ {\left.{#1}\!\mid\!{#2}\right.}} \gdef\rewritingRuleBinding#1#2{#1{\left[\,{#2}\,\right]}} \gdef\namedSystem#1{\mathsf{#1}} \gdef\genericRewritingSystem{\namedSystem{System}} \gdef\stringRewritingSystem{\namedSystem{Str}} \gdef\turingMachineRewritingSystem{\namedSystem{TM}} \gdef\cellularAutomatonRewritingSystem{\namedSystem{CA}} \gdef\graphRewritingSystem{\namedSystem{Gr}} \gdef\hypergraphRewritingSystem{\namedSystem{HGr}} \gdef\petriNetRewritingSystem{\namedSystem{Petri}} \gdef\ncard#1{\card{\negated{#1}}} \gdef\mcard#1{\card{\mirror{#1}}} \gdef\nmcard#1{\card{\negated{\mirror{#1}}}} \gdef\assocArray#1{\left\langle {#1} \right\rangle} \gdef\list#1{\{ {#1} \}} \gdef\tuple#1{( {#1} )} \gdef\concat#1{ {#1} } \gdef\paren#1{\left( {#1} \right)} \gdef\ceiling#1{\lceil{#1}\rceil} \gdef\floor#1{\lfloor{#1}\rfloor} \gdef\translationVector#1{\left[{#1}\right]_{\textrm{T}}} \gdef\quotient#1#2{ {#1} / {#2}} \gdef\compactQuotient#1#2#3{ {#1}\;{\upharpoonright_{#2}}\;{#3}} \gdef\multilineQuotient#1#2{\frac{#1}{#2}} \gdef\idElem#1{e_{#1}} \gdef\minus#1{-{#1}} \gdef\elem{\ \in\ } \gdef\gmult{\,\ast\,} \gdef\Gmult{\,\ast\,} \gdef\ellipsis{\dots} \gdef\appliedRelation#1{#1} \gdef\setUnionSymbol{\cup} \gdef\setIntersectionSymbol{\cap} \gdef\cartesianProductSymbol{\times} \gdef\functionSignature#1#2#3{ { {#1} : {#2} \to {#3}}} \gdef\poly#1{#1} \gdef\quiverProdPoly#1{#1} \gdef\quiverProdPower#1#2{#1^{#2}} \gdef\quiverProdTimes#1{#1} \gdef\parenLabeled#1#2{#1\ ({#2})} \gdef\modLabeled#1#2{ {#1 }\textrm{ mod }{#2}} \gdef\cyclicGroup#1{\mathbb{Z}_{#1}} \gdef\componentSuperQuiverOfSymbol{\succ} \gdef\setCardinality#1{|{#1}|} \gdef\dependentQuiverProductSymbol{\,\times\,} \gdef\independentQuiverProductSymbol{\,⨝\,} \gdef\graphUnionSymbol{\sqcup} \gdef\graphProductSymbol{\times} \gdef\inlineProdSymbol{\mid} \gdef\serialCardSymbol{ {:}} \gdef\parallelCardSymbol{ {\mid}} \gdef\cardinalSequenceSymbol{ {:}} \gdef\cardinalProductSymbol{\inlineProdSymbol} \gdef\vertexProductSymbol{\!\inlineProdSymbol\!} \gdef\edgeProductSymbol{\inlineProdSymbol} \gdef\indexSum#1#2#3{ {\sum_{#2}^{#3} #1}} \gdef\indexProd#1#2#3{ {\prod_{#2}^{#3} #1}} \gdef\indexMax#1#2#3{ {\max_{#2}^{#3} #1}} \gdef\indexMin#1#2#3{ {\min_{#2}^{#3} #1}} \gdef\oneTo#1{1..{#1}} \gdef\zeroTo#1{0..{#1}} \gdef\qstring#1{\mathtt{"}{#1}\mathtt{"}} \gdef\qchar#1{\mathtt{'}{#1}\mathtt{'}} \gdef\lstr#1{\mathtt{#1}} \gdef\lchar#1{\mathtt{#1}} \gdef\string#1{ {#1}} \gdef\character#1{ {#1}} \gdef\translationCardinalValuation#1{\textrm{T}_{#1}} \gdef\starTranslationCardinalValuation#1{\textrm{T}^*_{#1}} \)
Lattice quivers

Lattice quivers

Recap

In previous sections we've seen how to construct the forward path quiver \(\forwardPathQuiver{\quiver{F}}{\vert{x}}\) from a quiver \(\quiver{F}\), and to define the quotient quiver \(\quotient{\forwardPathQuiver{\quiver{F}}{\vert{x}}}{\pathMap{ \mu }}\) with respect some path valuation \(\pathMap{ \mu }\). We examined the particularly simple case of affine path valuations \(\functionSignature{\pathMap{\affineModifier{\groupoidFunction{ \phi }}}}{\forwardPathQuiver{\quiver{F}}{\vert{x}}}{\group{G}}\) that are induced by a cardinal valuation \(\functionSignature{\groupoidFunction{ \phi }}{\cardinalList(\quiver{F})}{\group{G}}\), where \(\group{G}\) is a group, yielding quotients written \(\quotient{\forwardPathQuiver{\quiver{F}}{\vert{x}}}{\affineModifier{\groupoidFunction{ \phi }}}\) or more simply \(\compactQuotient{\quiver{F}}{\vert{x}}{\groupoidFunction{ \phi }}\).

We'll now put this to use to build lattice quivers, which are quotients of extremely simple fundamental quivers \(\quiver{F}\) by affine path valuations induced by simple Abelian groups that capture the translational symmetries of crystallographic lattices.

Representations

Group representations

Recall that a group action \(\function{A}\) is the binding of a group \(\group{G}\) to an object \(\sym{X}\) on which it acts, expressed as a structure-preserving map \(\functionSignature{\function{A}}{\tuple{\group{G},\sym{X}}}{\sym{X}}\). By currying on the first argument of the map \(\function{A}\) we obtain a family of maps \(\functionSignature{\function{\function{A}(\group{G})}}{\sym{X}}{\sym{X}}\), it is these maps that encode the behavior of the group \(\group{G}\), with function composing playing the role of group multiplication.

A common family of group actions is obtained by associating each element of \(\group{G}\) with some form of isomorphism of the object \(\sym{X}\). This can be formalized using a group homomorphism \(\functionSignature{\groupoidFunction{ \pi }}{\group{G}}{\automorphisms(\sym{X})}\), where \(\automorphisms(\sym{X})\) represents the group of relevant symmetries of the object \(\sym{X}\).

When \(\sym{X}\)is a set, the isomorphisms are permutations, so that \(\automorphisms(\sym{X}) = \symmetricGroup{\sym{X}}\), and the group actions are known as permutation representations.

When \(\sym{X}\) is a vector space, these group actions are known as linear representations. In that case, \(\automorphisms(\sym{X})\) is just the space of linear transformations of \(\sym{X}\), and if this space is also finite dimensional, we can represent these linear transformations as square matrices living in a subgroup of \(\gl{n}{\field{K}}\), for \(\field{K}\) some field, typically \(\field{\mathbb{R}}\) or \(\field{\mathbb{C}}\). A vast body of theory has been built around studying and classifying such representations with many applications in physics and elsewhere.

Group representations are models of groups: concrete instantiations of the behavior of the group in the form of transformations of a vector space. These instantiations can capture all the behavior, meaning that different group elements are sent to unique transformations, in which case they are called faithful. Or they might lose information; in the case of the trivial representation, every group element is represented as the identity transformation, and we've lost all the information about the original group.

Path representations

What is the analogous idea for the groupoid of the paths of a quiver?

Clearly it would involve a groupoid homomorphism \(\functionSignature{\pathMap{ \mu }}{\pathGroupoid{\quiver{G}}}{\gl{n}{\field{K}}}\). But we’ve already encountered a class of such homomorphisms in the form of path valuations. We saw that affine path valuations, \(\functionSignature{\function{\affineModifier{\groupoidFunction{ \phi }}}}{\pathGroupoid{\quiver{G}}}{\group{H}}\) (where \(\group{H}\) is a groupoid), which are induced by a choice of cardinal valuation \(\functionSignature{\function{ \phi }}{\cardinalList(\quiver{F})}{\group{H}}\), are particularly simple. If we now choose a linear representation of \(\group{H}\), via \(\functionSignature{\groupoidFunction{ \pi }}{\group{H}}{\gl{n}{\field{K}}}\), we can compose these to obtain a path representation of the form we desired: \(\functionSignature{\groupoidFunction{ \pi }}{\group{H}}{\gl{n}{\field{K}}}\).

As before, a path representation models paths as elements of \(\gl{n}{\field{K}}\), but by taking quotients we will be deliberately discarding information in order to conflate precisely those paths that we wish to lead to the same state. For suitable representations, this conflation will "fold" the tree produced by the forward path quiver into a finite-dimensional quiver. (In abstract algebra, this kind of construction is ubiquitous, generically referred to as taking a quotient of a freely generated object in order to impose some desired relations).

While we will be focused on simply using path quotients to construct lattice quivers, we will keep the path representation interpretation in mind for the remainder of this section, and the matrix machinery that goes along with group representations will be an useful tool to organize our work.

Computation

We wish to actually compute the quotient \(\compactQuotient{\quiver{F}}{\vert{x}}{\groupoidFunction{ \phi }}\), where \(\groupoidFunction{ \phi }\) is a map assigning a matrix \(\groupoidFunction{ \phi }(\card{c})\) to each cardinal \(\elemOf{\card{c}}{\cardinalList(\quiver{F})}\). Of course, this quiver is usually infinite, so we can only generate a finite part of it, which we'll generally call a fragment.

The following describes how we can use an elementary algorithm from computer science to compute the lattice quiver, known as a breadth-first graph traversal.

First, define a state as representing an equivalence class of paths starting at the base vertex \(\vert{v}\). We'll represent these states with pairs \(\tuple{\vert{x},\matrix{M}}\), where \(\vert{x}\) is a vertex of the fundamental quiver representing the head of the path, and \(\matrix{M}\) is the value of the path as represented by a matrix.

We start with a single state \(\tuple{\vert{x},\matrix{M}} = \tuple{\vert{v},\matrix{I}}\) representing the empty path at the the base vertex \(\vert{v}\), with path matrix \(\matrix{M}\) equal to the identity matrix \(\matrix{I}\). We then extend this empty path by all cardinals \(\card{c}_{\sym{i}}\) corresponding to edges \(\tde{\vert{v}}{\vert{w_i}}{\card{\card{c}_{\sym{i}}}}\) in the fundamental quiver, right-multiplying our current value of \(\matrix{M}\) by the corresponding cardinal matrices \(\groupoidFunction{ \phi }(\card{c})\) to obtain new states \(\tuple{\vert{w_i},\matrix{M}\matrixDotSymbol \groupoidFunction{ \phi }(\card{c}_{\sym{i}})}\).

We then go on to explore these new states in a first-in last-out fashion, stopping when we reach some depth. Sometimes we will encounter a state that we have created before: this is to say, we will find two different paths in the lattice quiver that produce the same path value, and we can avoid re-exploring these old states.

By storing only states and their adjacency, and not entire paths, we avoid performing an exponential amount of computation as the number of visited states increases (this is a form of so-called dynamic programming).

In other contexts, a graph so produced is variously known as a state-transition graph, multiway graph, or in the group-theory context, a Cayley graph (or in our language a Cayley quiver). In our context, these graphs are quivers, since the have an additional cardinal structure in which each edge is labeled with the cardinal we took to generate that particular state. Moreover, these quivers represent particular quotients of path quivers. When translation groups are used to generate these quotients, we'll simply use the term lattice quivers.

Notation

We will denote the quiver generated by exploring fundamental quiver \(\quiver{F}\), starting at vertex \(\vert{x}\), using the affine path valuation induced by cardinal valuation \(\groupoidFunction{ \phi }\), to depth \(\sym{n}\), with the expression:

\[ \latticeBFS{\quiver{F},\vert{x},\groupoidFunction{ \phi },\sym{n}} \]

By setting \(\sym{n} = \infty\) we represent the "ongoing breadth-first search" that typically does not ever terminate, which we interpret as computing the full forward path quiver quotient to arbitrary depth:

\[ \compactQuotient{\quiver{F}}{\vert{x}}{\groupoidFunction{ \phi }} = \limit{\latticeBFS{\quiver{F},\vert{x},\groupoidFunction{ \phi },\sym{n}}}{\sym{n} \to \infty } \]

This limit is true in the sense that every vertex / edge of the quotient will eventually be generated by the search for some sufficiently large \(\sym{n}\), and conversely every vertex / edge generated by the search corresponds to some vertex / edge of the quotient.

Translation matrices

While cardinal matrices \(\groupoidFunction{ \phi }(\card{c}_{\sym{i}})\) are in general \(\sym{n}\times \sym{n}\), we will be limiting ourselves to translation matrices, which can be put into a simple upper triangular form as follows:

\[ \translationVector{\sym{x}}\defEqualSymbol {\begin{pmatrix}1&\sym{x}\\0&1\end{pmatrix}}\quad \translationVector{\sym{x},\sym{y}}\defEqualSymbol {\begin{pmatrix}1&0&\sym{x}\\0&1&\sym{y}\\0&0&1\end{pmatrix}}\quad \translationVector{\sym{x},\sym{y},\sym{z}}\defEqualSymbol {\begin{pmatrix}1&0&0&\sym{x}\\0&1&0&\sym{y}\\0&0&1&\sym{z}\\0&0&0&1\end{pmatrix}}\quad \ellipsis \]

These matrices have the property that:

\[ \begin{aligned} \translationVector{\sym{x}}\matrixDotSymbol \translationVector{\primed{\sym{x}}} &= \translationVector{\sym{x} + \primed{\sym{x}}}\\ \translationVector{\sym{x},\sym{y}}\matrixDotSymbol \translationVector{\primed{\sym{x}},\primed{\sym{y}}} &= \translationVector{\sym{x} + \primed{\sym{x}},\sym{y} + \primed{\sym{y}}}\\ \translationVector{\sym{x},\sym{y},\sym{z}}\matrixDotSymbol \translationVector{\primed{\sym{x}},\primed{\sym{y}},\primed{\sym{z}}} &= \translationVector{\sym{x} + \primed{\sym{x}},\sym{y} + \primed{\sym{y}},\sym{z} + \primed{\sym{z}}}\\ \end{aligned} \]

Line lattice

To kick things off let’s look at probably the simplest possible fundamental quiver: a 1-bouquet quiver \(\bindCards{\bouquetQuiver{1}}{\rform{\card{r}}}\).

We'll associate its only cardinal \(\rform{\card{r}}\) with a \(2 \times 2\) matrix, representing a generator of the group \(\mathbb{Z}\).

Now, because this quiver only has one vertex, all of the paths in \(\quiver{F}\) are trivially composable, and the path groupoid \(\pathGroupoid{\quiver{Q}}\) it defines is hence a group (this group is also isomorphic to \(\mathbb{Z}\)).

We wish to generate the lattice quiver, which is the quotient \(\compactQuotient{\bindCards{\bouquetQuiver{1}}{\rform{\card{r}}}}{\vert{o}}{\groupoidFunction{ \phi }}\), where \(\groupoidFunction{ \phi }\) is the cardinal valuation \(\translationCardinalValuation{1}\defEqualSymbol \assocArray{\mto{\rform{\card{r}}}{\translationVector{1}}}\), and \(\vert{o}\) is the single vertex of the bouquet quiver. Of course, this quiver is infinite, so we can only compute a fragment of it.

We can traverse the single fundamental quiver edge \(\tde{\vert{x}}{\vert{x}}{\rform{\card{r}}}\) in the forward or reverse direction, so we can reach two states from the initial state. We continue this process until we have reached the specified traversal depth.

Here’s the lattice quiver for our simple fundamental quiver, explored to depth 4:

The origin vertex here is shown larger.

Let's label these vertices with their corresponding matrices to see better what is going on:

Note that the top-right entry of each matrix is effectively acting as a 1D coordinate.

We state without proof:

\[ \bindCards{\subSize{\lineQuiver }{ \infty }}{\rform{\card{r}}}\isomorphicSymbol \compactQuotient{\bindCards{\bouquetQuiver{1}}{\rform{\card{r}}}}{\vert{o}}{\bindCards{\translationCardinalValuation{1}}{\rform{\card{r}}}} \]

Square lattice

Let’s move on to a two-dimensional lattice quiver. We’ve added a cardinal \(\bform{\card{b}}\) to the fundamental quiver:

Notice that the generators of the representation are the two unit translation matrices for \(\mathbb{Z}^2\):

\[ \bindCards{\translationCardinalValuation{2}}{\rform{\card{r}},\bform{\card{b}}}\defEqualSymbol \assocArray{\mto{\rform{\card{r}}}{\translationVector{1,0}},\mto{\bform{\card{b}}}{\translationVector{0,1}}} \]

As you would expect, the lattice quiver this generates is a 2D grid, shown here to depth 3:

Again, notice the 2D “translation coordinates” that the representation matrices contain:

Note that negative integers are displayed as red, rather than with a minus sign.

Since all our matrices are translation matrices, we can extract the coordinate vector from each matrix for a cleaner graphic:

Again, we state without proof:

\[ \bindCards{\subSize{\squareQuiver }{ \infty }}{\rform{\card{r}},\bform{\card{b}}}\isomorphicSymbol \compactQuotient{\bindCards{\bouquetQuiver{2}}{\rform{\card{r}},\bform{\card{b}}}}{\vert{o}}{\bindCards{\translationCardinalValuation{2}}{\rform{\card{r}},\bform{\card{b}}}} \]

Paths and relations

Although the point should be quite clear, let's visualize how vertices in the lattice quiver correspond to paths in the fundamental quiver that have the same value.

Here we have two paths with words \(\word{\rform{\card{r}}}{\bform{\card{b}}}\) and \(\word{\bform{\card{b}}}{\rform{\card{r}}}\) in the fundamental quiver, shown on the right. The fact that terminate at the same vertex in the lattice quiver reflects the fact that the matrix values of those two paths are the same: \(\matrix{M_{\rform{\card{r}}}}\matrixDotSymbol \matrix{M_{\bform{\card{b}}}} = \matrix{M_{\bform{\card{b}}}}\matrixDotSymbol \matrix{M_{\rform{\card{r}}}}\). This must be true because the cardinal matrices \(\matrix{M_i}\) represent an Abelian group (namely a translation group) and in fact this path diagram is the defining relation of this particular group.

We'll call this a path relation of a lattice quiver, and write it algebraically as \(\word{\rform{\card{r}}}{\bform{\card{b}}}\pathIso \word{\bform{\card{b}}}{\rform{\card{r}}}\). The symbol \(\pathIso\) is understood to mean that the two paths with the given path words that share a tail vertex, also share a head vertex in the lattice quiver.

Triangular lattice

Perhaps a more interesting example of path relations comes from the following lattice quiver with three cardinals:

Here, the cardinal matrices are the following translations of \(\mathbb{Z}^3\):

\[ \bindCards{\starTranslationCardinalValuation{3}}{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}\defEqualSymbol \assocArray{\mto{\rform{\card{r}}}{\translationVector{1,-1,0}},\mto{\gform{\card{g}}}{\translationVector{0,1,-1}},\mto{\bform{\card{b}}}{\translationVector{-1,0,1}}} \]

This generates a triangular lattice, shown here to depth 3:

Although these matrices represent translations in \(\mathbb{Z}^3\), they are not linearly independent, and so their action is two dimensional, yielding a planar lattice quiver.

Let's visualize their translation vectors:

We can also look at a path diagram for the triangular lattice:

Again, the fact that \(\word{\gform{\card{g}}}{\rform{\card{r}}}\pathIso \word{\bform{\ncard{b}}}\) reflects the property of the matrices \(\matrix{M_{\rform{\card{r}}}}\), \(\matrix{M_{\gform{\card{g}}}}\), \(\matrix{M_{\bform{\card{b}}}}\) that \(\matrix{M_{\rform{\card{r}}}}\matrixDotSymbol \matrix{M_{\gform{\card{g}}}} = \inverse{\matrix{M_{\bform{\card{b}}}}}\), or more simply that \(\matrix{M_{\rform{\card{r}}}}\matrixDotSymbol \matrix{M_{\gform{\card{g}}}}\matrixDotSymbol \matrix{M_{\bform{\card{b}}}} = \matrix{I}\).

So, while we pulled these matrices out of a hat, we can interpret them as encoding the following path relations:

\[ \list{\word{\gform{\card{g}}}{\rform{\card{r}}}\pathIso \word{\rform{\card{r}}}{\gform{\card{g}}},\word{\gform{\card{g}}}{\bform{\card{b}}}\pathIso \word{\bform{\card{b}}}{\gform{\card{g}}},\word{\bform{\card{b}}}{\rform{\card{r}}}\pathIso \word{\rform{\card{r}}}{\bform{\card{b}}},\word{\rform{\card{r}}}{\gform{\card{g}}}{\bform{\card{b}}}\pathIso \word{1}} \]

The full set of relations can be illustrated as path diagrams as follows:

Lastly, we again state without proof:

\[ \bindCards{\subSize{\triangularQuiver }{ \infty }}{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}\isomorphicSymbol \compactQuotient{\bindCards{\bouquetQuiver{3}}{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}}{\vert{o}}{\bindCards{\starTranslationCardinalValuation{3}}{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}}} \]

Summary

Named cardinal valuations

We collect the cardinal valuations \(\groupoidFunction{ \phi }\) used above:

\[ \begin{aligned} \bindCards{\translationCardinalValuation{1}}{\rform{\card{r}}} &\defEqualSymbol \assocArray{\mto{\rform{\card{r}}}{\translationVector{1}}}\\ \bindCards{\translationCardinalValuation{2}}{\rform{\card{r}},\bform{\card{b}}} &\defEqualSymbol \assocArray{\mto{\rform{\card{r}}}{\translationVector{1,0}},\mto{\bform{\card{b}}}{\translationVector{0,1}}}\\ \bindCards{\translationCardinalValuation{3}}{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}} &\defEqualSymbol \assocArray{\mto{\rform{\card{r}}}{\translationVector{1,0,0}},\mto{\gform{\card{g}}}{\translationVector{0,1,0}},\mto{\bform{\card{b}}}{\translationVector{0,0,1}}}\\ \bindCards{\starTranslationCardinalValuation{3}}{\rform{\card{r}},\gform{\card{g}},\bform{\card{b}}} &\defEqualSymbol \assocArray{\mto{\rform{\card{r}}}{\translationVector{1,-1,0}},\mto{\gform{\card{g}}}{\translationVector{0,1,-1}},\mto{\bform{\card{b}}}{\translationVector{-1,0,1}}}\\ \end{aligned} \]

Transitive lattice quivers

This allows us to express how to generate the four transitive lattice quivers succintly in the following table:

namequiverfun. quivergroup
line quiver\(\subSize{\lineQuiver }{ \infty }\)\(\bouquetQuiver{1}\)\(\translationCardinalValuation{1}\)
square quiver\(\subSize{\squareQuiver }{ \infty }\)\(\bouquetQuiver{2}\)\(\translationCardinalValuation{2}\)
triangular quiver\(\subSize{\triangularQuiver }{ \infty }\)\(\bouquetQuiver{3}\)\(\starTranslationCardinalValuation{3}\)
cubic quiver\(\subSize{\cubicQuiver }{ \infty }\)\(\bouquetQuiver{3}\)\(\translationCardinalValuation{3}\)