Arithmetic of arithmetic Coxeter groups

Edited by Kenneth A. Ribet, University of California, Berkeley, CA, and approved November 16, 2018 (received for review June 3, 2018)
December 26, 2018
116 (2) 442-449

Significance

Conway’s topograph provided a combinatorial-geometric perspective on integer binary quadratic forms—quadratic functions of two variables with integer coefficients. This perspective is practical for solving equations and easily bounds the minima of binary quadratic forms. It appears that Conway’s topograph is just the first in a series of applications of arithmetic Coxeter groups to arithmetic. Four other applications are described in this article, and dozens more may be possible.

Abstract

In the 1990s, J. H. Conway published a combinatorial-geometric method for analyzing integer-valued binary quadratic forms (BQFs). Using a visualization he named the “topograph,” Conway revisited the reduction of BQFs and the solution of quadratic Diophantine equations such as Pell’s equation. It appears that the crux of his method is the coincidence between the arithmetic group PGL2(Z) and the Coxeter group of type (3,). There are many arithmetic Coxeter groups, and each may have unforeseen applications to arithmetic. We introduce Conway’s topograph and generalizations to other arithmetic Coxeter groups. This includes a study of “arithmetic flags” and variants of binary quadratic forms.
Binary quadratic forms (BQFs) are functions Q:Z2Z of the form Q(x,y)=ax2+bxy+cy2, for some integers a,b,c. The discriminant of such a form is the integer Δ=b24ac. In ref. 1, J. H. Conway visualized the values of a BQF through an invention he called the topograph.

1. Conway’s Topograph

The Geometry of the Topograph.

The topograph is an arrangement of points, edges, and faces, as described below.
Faces correspond to primitive lax vectors: coprime ordered pairs v=(x,y)Z2, modulo the relation (x,y)(x,y). Such a vector is written ±v.
Edges correspond to lax bases: unordered pairs {±v,±w} of primitive lax vectors which form a Z basis of Z2. (Clearly this is independent of sign choices.)
Points correspond to lax superbases: unordered triples {±u,±v,±w}, any two of which form a lax basis.
Incidence among points, edges, and faces is defined by containment. A maximal arithmetic flag in this context refers to a point contained in an edge contained in a face. The geometry is displayed in Fig. 1; the points and edges form a ternary regular tree, and the faces are -gons. The group PGL2(Z)=GL2(Z)/{±1} acts simply–transitively on maximal arithmetic flags.
Fig. 1.
Conway’s geometry of primitive lax vectors, lax bases, and lax superbases.
On the other hand, the geometry of Fig. 1 also arises as the geometry of flags in the Coxeter group of type (3,). This is the Coxeter group with a diagram . The group W encoded by such a diagram is generated by elements S={s0,s1,s2} corresponding to the nodes, modulo the relations si2=1 (for i = 0, 1, 2), s0s2=s2s0, (s0s1)3=1. If TS is a subset of nodes, write WT for the subgroup generated by T; it is called a parabolic subgroup. The flags of type T are the cosetsW/WT The Coxeter group W acts simply–transitively on the maximal flags; i.e., the cosetsW/W=W.
The geometric coincidence reflects the fact that PGL2(Z) is isomorphic to the Coxeter group W of type (3,), a classical result known to Poincaré and Klein. But Conway’s study of lax vectors, bases, and superbases goes further, giving an arithmetic interpretation of the flags for the Coxeter group. This raises the natural question: Given a coincidence between an arithmetic group and a Coxeter group, is there an arithmetic interpretation of the flags in the Coxeter group?

Binary Quadratic Forms.

If one draws the values Q(±v) on the faces labeled by the primitive lax vectors ±v, one obtains Conway’s topograph of Q. Figs. 2 and 3 display examples. If u,v,e,f appear on the topograph of Q, in a local arrangement we call a cell, then Conway observes that the integers e,u+v,f form an arithmetic progression.
Fig. 2.
The topograph of Q(x,y)=x2+2y2, with arrows exhibiting the climbing principle. The well (source of the flow) is the cell at the center.
Fig. 3.
The topograph of Q(x,y)=x23y2, exhibiting a periodic river. Solutions to Pell’s equation x23y2=1 are found along the riverbank.
The discriminant of Q can be seen locally in the topograph, at every cell, by the formula Δ=u2+v2+e22uv2ve2eu=(uv)2ef.
A consequence of the arithmetic progression property is Conway’s climbing principle; if all values in a cell are positive, place arrows along the edges in the directions of increasing arithmetic progressions. Then every arrow propagates into two arrows; the resulting flow along the edges can have a source, but never a sink. This implies the existence and uniqueness of a well for positive-definite forms: a triad or cell which is the source for the flow. The well gives the unique Gauss-reduced form QGr in the SL2(Z)-equivalence class of Q. More precisely, every well contains a triple uvw of positive integers satisfying u+vw, with strict inequality at triad wells and equality at cell wells (Fig. 2). Depending on the orientation of u,v,w at the well, the Gauss-reduced form is given below; in the ambiguously oriented case with u=v, QGr(x,y)=ux2+(u+vw)xy+vy2. If u+v=w, both orientations occur in a cell well, and QGr(x,y)=ux2+vy2.
When Q is a nondegenerate indefinite form, Conway defines the river of Q to be the set of edges which separate a positive value from a negative value in the topograph of Q. Since all values on the topograph of Q must be positive or negative, the river cannot branch or terminate. The climbing principle implies uniqueness of the river. Thus, the river is a set of edges composing a single endless line. Bounding the values adjacent to the river implies periodicity of values adjacent to the river and thus the infinitude of solutions to Pell’s equation. This is described in detail in ref. 1.
Riverbends—cells with a river as drawn below—correspond to Gauss’s reduced forms in the equivalence class of Q.

Proposition 1.

Let u,v,e,f be the cell values at a riverbend, with e<0, f>0. Then a Gauss-reduced form in the SL2(Z)-equivalence class of Q is given by
QGr(x,y)=ux2+(u+ve)xy+vy2.

Proof:

Let b=(u+v)e=f(u+v) be the common difference at the cell. Then QGr(x,y)=ux2+bxy+vy2 is SL2(Z) equivalent to Q and we must prove Gauss’s reduction conditions (ref. 2, article 183):
0<b<ΔandΔb<2|u|<Δ+b.
Note that 0<b since e<f. Since b24uv=Δ, and u and v have opposite sign, we find that b2<Δ. Gauss’s first reduction condition 0<b<Δ follows.
Since (uv)2ef=Δ, and e and f have opposite sign, we find that Δ>(uv)2. Since u and v have opposite sign, this implies Δ>sgn(u)(uv). Multiplying by 4|u| yields 4|u|Δ>4u(uv). Replace 4uv by Δb2 to obtain 4|u|Δ>4u2+Δb2. Rearranging yields
4u24|u|Δ+Δ<b2.
Hence (2|u|Δ)2<b2, and so b<2|u|Δ<b. This verifies Gauss’s second reduction condition. □
The existence of riverbends gives a classical bound, by an argument we learned from Gordan Savin.

Theorem 2.

The minimum nonzero absolute value μQ of a nondegenerate indefinite BQF Q satisfies μQΔ/5.

Proof:

At a riverbend, one finds Δ=(uv)2ef=u2+v2uvvuef, the sum of five positive integers. It follows that one of u2,v2,uv,vu,ef must be bounded by Δ/5. Among |u|,|v|,|e|,|f|, one must be bounded by Δ/5.□
These are some highlights and applications of Conway’s topograph. In the next sections, we describe generalizations.

2. Gaussian and Eisenstein Analogues

Let G denote the Gaussian integers: G=Z[i]. Let E denote the Eisenstein integers: E=Z[e2πi/3].

Arithmetic Flags and Honeycombs.

One may generalize Conway’s vectors, bases, and superbases to arithmetic structures in G2 and E2. Guiding this are embeddings of PSL2(G) and PSL2(E) into hyperbolic Coxeter groups. In ref. 3, sections 1.I, 1.II, 3, and 6, Bianchi describes generators for SL2(G) and SL2(E) and fundamental polyhedra for their action on hyperbolic 3-space. Using reflections in the faces of these polyhedra, one may write explicit presentations of these groups; Fricke and Klein carry this out for SL2(G) in ref. 4, section I.8, where one finds a connection to the (later-named) Coxeter group of type (3,4,4). Schulte and Weiss give a detailed treatment, proving the following in ref. 5, theorems 7.1 and 9.1.

Theorem 3.

PSL2(G) is isomorphic to an index-two subgroup of (3,4,4)+. PSL2(E) is isomorphic to an index-two subgroup of (3,3,6)+.
Here (a,b,c)+ denotes the even subgroup of the Coxeter group of type (a,b,c). As the Coxeter groups of types (3,4,4) and (3,3,6) are commensurable to PSL2(G) and PSL2(E), respectively, we expect an arithmetic interpretation of the Coxeter geometries. Such an arithmetic incidence geometry is described below.
Cells correspond to primitive lax vectors: coprime ordered pairs v=(x,y)G2 (respectively E2), modulo the relation (x,y)(ϵx,ϵy) for all ϵG× (resp., ϵE×).
Faces correspond to lax bases: unordered pairs {ϵv,ϵw} of primitive lax vectors which form a G basis of G2 (respectively E basis of E2).
Edges correspond to lax superbases: unordered triples {ϵu,ϵv,ϵw}, any two of which form a lax basis.
Points of the Eisenstein topograph* correspond to lax tetrabases: unordered quadruples {ϵs,ϵt,ϵu,ϵv}, any three of which form a lax superbasis.
Points of the Gaussian topograph correspond to lax cubases: sets of three two-element sets {{ϵu1,ϵu2},{ϵv1,ϵv2},{ϵw1,ϵw2}}, such that all eight choices of i,j,k{1,2} give a lax superbasis {ϵui,ϵvj,ϵwk}.
Incidence is given by the obvious containments described above. We call this incidence geometry the topograph for E or G, and it is equipped with an action of PSL2(E) and PSL2(G), respectively. The terms tetrabasis and cubasis reflect the residual geometry around a point (Fig. 4). Both geometries produce regular hyperbolic honeycombs (ref. 6, chap. IV); the points, edges, and faces around each cell form square or hexagonal planar tilings in the Gaussian or the Eisenstein case, respectively.
Fig. 4.
The geometry of the Gaussian and Eisenstein topographs, displaying square and hexagonal faces and cubic and tetrahedral residues at a point.
The Gaussian and Eisenstein topographs are described by Bestvina and Savin in ref. 7, sections 7 and 8. Both topographs, and the following link to Coxeter geometries, are given in the PhD thesis of the second author (8).

Theorem 4.

The topographs for E2 and G2 are equivariantly isomorphic to the Coxeter geometries of types (3,3,6) and (3,4,4), respectively.
By equivariance, we mean that the isomorphism intertwines the natural actions of PSL2(E) and PSL2(G) on one hand with the actions of the Coxeter groups on the other, via the inclusion described in Theorem 3.

Binary Hermitian Forms.

An integer-valued binary Hermitian form (BHF), over E or G, is a function H:E2Z or G2Z, of the form
H(x,y)=axx¯+βx¯y+β¯xȳ+cyȳ.
Here we assume a,cZ, and β(1ω)1E or β(1+i)1G (the inverse different of E or G, respectively). The discriminant of H is the integer defined by
Δ=(3or4)(ββ¯ac),forEorG, respectively.
Fricke and Klein discuss reduction theory of Hermitian forms over G, using the geometry of SL2(G), in ref. 4, section III.1,1–8. The topographs give a new approach, pursued by Bestvina and Savin (7).
Let H be a BHF over E or G. Recalling that cells of the topographs correspond to primitive lax vectors, we define the topograph of H to be the result of placing the value H(ϵv) at the topograph cell marked by the primitive lax vector ϵv. The most interesting case occurs when H is nondegenerate indefinite (taking positive and negative values, but never zero on a nonzero vector input). In this case, Conway’s river is replaced by the ocean—the set of faces separating a cell with positive value from one with negative value. Bestvina and Savin prove (ref. 7, theorems 5.3 and 6.1) that this ocean is topologically an open disk, locally CAT(0) as a metric space, and the unitary group U(H) acts cocompactly on the ocean.
Reduced indefinite BQFs correspond to riverbends in Conway’s topograph. In a similar way, one finds reduced indefinite BHFs at the points of the ocean of negative curvature, i.e., where more than four ocean squares (for G) or more than three ocean hexagons (for E) meet at a point. From this, Bestvina and Savin (ref. 7, theorem 8.7) recover the optimal bound on the minima of nondegenerate indefinite BHFs over E. The bound for G can be obtained by the same method.

Theorem 5.

Let H be a nondegenerate indefinite BHF. Then the minimum nonzero absolute value μH satisfies μHΔ/6.

Proof:

The Eisenstein case is proved in ref. 7, so we prove the Gaussian case. Consider a vertex at which the ocean of H has negative curvature; such a point exists by ref. 7, corollary 6.2. The residue of the topograph at this vertex is a cube, whose faces are labeled by the values of H. The intersection of the ocean with this cube forms a simple closed path on the edges, separating positive-valued faces from negative ones.
Form I corresponds to a Euclidean vertex; forms II, III, and IV correspond to ocean vertices of negative curvature. Label the values of H on the cube by a,b,c,u,v,w, with a opposite u, b opposite v, and c opposite w. In ref. 7, proposition 7.1, Bestvina and Savin demonstrate that a+u=b+v=c+w. This excludes form IV, since the sum of two positive numbers cannot equal the sum of two negative numbers. Ref. 7, section 7 also gives a formula for the discriminant,
Δ=z22au2bv2cw,wherez=a+u=b+v=c+w.
In forms II and III, we may place a,u,b,v so that a and u have opposite signs, and b and v have opposite signs. Expressing z as c+w yields
Δ=c2+w22au2bv.
As the right side is a sum of positive terms, we find
min{|a|,|b|,|c|,|u|,|v|,|w|}Δ/6.

3. Real Quadratic Arithmetic

Dilinear Algebra.

Here we introduce a family of “dilinear groups” associated to certain real quadratic rings. Let σ>1 be a square-free positive integer, and let Rσ=Z[σ] be the quadratic ring of discriminant 4σ. We define the dilinear group DL2(Rσ) to be the group of all matrices abcdGL2(Rσ) such that
(a,dZσandb,cZ)or(a,dZandb,cZσ).
Let DL2+(Rσ) denote its subgroup consisting of matrices with a,dZ and b,cZσ. While the dilinear groups seem a bit mysterious at first, DL2+(Rσ) is GL2(Q(σ)) conjugate to a congruence subgroup of GL2(Z): If g=diag(1,σ), then
gDL2+(Rσ)g1=Γ0(σ)αβγδGL2(Z):γσZ.
We thank the referee for this insight.
A divector over Rσ will mean a vector in Rσ2 of red or blue type. Red divectors are those of the form (u,vσ) for some u,vZ. Blue divectors are those of the form (uσ,v) for some u,vZ. A red divector (u,vσ) is called primitive if GCD(u,σv)=1. A blue divector (uσ,v) is called primitive if GCD(uσ,v)=1.

Theorem 6.

The dilinear group DL2(Rσ) acts transitively on the set of primitive divectors, and DL2+(Rσ) acts transitively on the set of primitive red (or blue) divectors.

Proof:

A matrix in DL2(Rσ) has a determinant in ZZ[σ]×={±1}. It follows that a matrix in DL2(Rσ) sends primitive divectors to primitive divectors. For transitivity, consider a primitive red divector (u,vσ). Since GCD(u,σv)=1, there exist s,tZ such that sutvσ=1. Observe that
utσvσs10=uvσ.
Hence DL2+(Rσ) acts transitively on the set of primitive red vectors. Since the matrix 0110DL2(Rσ) swaps primitive red and blue divectors, the result follows. □
Define PDL2(Rσ)=DL2(Rσ)/{±1}. When σ=2 or σ=3, Johnson and Weiss (ref. 9, section 4) present PDL2(Rσ) by generators and relations, proving the following.

Theorem 7.

If σ=2 or σ=3, then PDL2(Rσ) is isomorphic to the Coxeter group of type (2σ,).
Explicitly, Johnson and Weiss (8) note that PDL2(Rσ) is generated by the triple of matrices (modulo ±1),
s1=0110,s2=10σ1,s3=1001,
which satisfy the Coxeter relations s12=s22=s32=±1, (s1s2)2σ=±1, (s1s3)2=±1. From their result, we were led to “dilinear” arithmetic interpretations of the geometries of types (4,) and (6,).

Arithmetic Flags.

The “dilinear” variant of Conways’s topograph is as follows. Assume σ=2 or σ=3.
Faces correspond to primitive lax divectors over Rσ, i.e., primitive divectors modulo ±1.
Edges correspond to lax dibases: unordered pairs of lax divectors generating Rσ2 as an Rσ module. This implies that the divectors are primitive, have opposite color, and form the rows of a matrix in DL2(Rσ).
Points correspond to lax pinwheels: cyclically ordered 2σ-tuples of lax divectors such that any adjacent pair forms a lax dibasis (and hence has opposite color).

Theorem 8.

The geometry of primitive lax divectors, lax dibases, and pinwheels for Rσ is equivariantly isomorphic to the Coxeter geometry of type (2σ,) (Fig. 5).
Fig. 5.
The Coxeter geometries of type (4,) and (6,) are labeled by primitive lax divectors for Z[2] and Z[3], respectively. Around each point is a pinwheel.

Binary Quadratic Diforms.

Let us return to the general case of a square-free positive integer σ again. A binary quadratic diform (BQD) is a function of the form
Q(x,y)=ax2+bσxy+cy2,wherea,b,cZ.
We restrict (x,y) to be a divector in Rσ2, so the values of Q are integers. We define the discriminant of Q by Δ=σ(b2σ4ac).
Restricting Q to red and blue divectors yields a pair Qred,Qblue of BQFs over Z of discriminant Δ; explicitly,
Qred(u,v)Q(u,vσ)=au2+bσuv+cσv2,
Qblue(u,v)Q(uσ,v)=aσu2+bσuv+cv2.
This pair of BQFs can be related through an accessory form we call AΔ. Namely, whenever σΔ, define
AΔ(u,v)=σu2Δ4σv2ifΔσ10mod4;σu2+σuvΔσ24σv2ifΔσ1/0mod4.
Write Cl(Δ) for the group of SL2(Z)-equivalence classes of primitive BQFs of discriminant Δ, following Bhargava (ref. 10, theorem 1). If Q is a BQF of discriminant Δ, write [Q] for its SL2(Z)-equivalence class. Since AΔ is an ambiguous form (its first coefficient divides its middle coefficient), its class in Cl(Δ) satisfies [AΔ]2=1. The class of AΔ has another characterization below.

Lemma 9.

If Q is a BQF of discriminant Δ that represents σ, and σΔ, then [Q]=[AΔ].

Proof:

The square-freeness of σ is used repeatedly in what follows. If Q represents σ, then Q is SL2(Z) equivalent to a BQF of the form σu2+buv+cv2. Since σΔ=b24σc, we find that σb. It follows that σu2+buv+cv2 is ambiguous and equivalent to σu2+ϵuv+kv2 for some kZ and ϵ{0,1}.
If ϵ=0, then Δ=4σk and Δσ10 mod 4. In this case k=Δ/4σ. If ϵ=1, then Δ=σ24σk and Δσ1σ4k/0 mod 4. In this case k=(Δσ2)/(4σ).□
Thus, with σ fixed and σΔ, we find that [AΔ] is the unique class in Cl(Δ) which represents σ; it happens to be a 2-torsion element in the class group. The following relates Qred and Qblue via AΔ.

Theorem 10.

Suppose that a, bσ, and c are pairwise coprime. In Cl(Δ), one has [Qred]=[AΔ][Qblue]. Conversely, if Q1,Q2 are primitive BQFs of discriminant Δ, and σΔ, and [Q1]=[AΔ][Q2], there exists a BQD Q such that [Qred]=[Q1] and [Qblue]=[Q2].

Proof:

Consider the cube of integers below.
Let (Mi,Ni) be the partition of this cube into a pair of two-by-two matrices, in a front–back, left–right, and top–bottom fashion according to whether i=1,2,3, respectively, as in ref. 10, section 2.1. From these matrices, Bhargava constructs a triple of binary quadratic forms Qi(u,v)=det(MiuNiv):
Q1(u,v)=au2+bσuv+cσv2;Q2(u,v)=cu2+bσuv+aσv2;Q3(u,v)=σu2+bσuv+acv2.
By ref. 9, theorem 1, we have [Q1][Q2][Q3]=1 in Cl(Δ). Observe that Q1 is precisely Qred. Next, observe that Q2 is related to Qblue by switching u and v; it follows that [Q2]=[Qblue]1. By Lemma 9, [Q3]=[AΔ]. Since [AΔ]2=1, we have
[Qred]=[AΔ][Qblue]and[Qblue]=[AΔ][Qred].
For the converse, suppose that Q1 and Q2 are primitive BQFs of discriminant Δ, σΔ, and [Q2]=[AΔ][Q1]. Write Q1(u,v)=αu2+βuv+γv2, so σβ24αγ. If σγ, then σβ, and Q1=Qred for the diform
Q(x,y)=αx2+βσ1σxy+γσ1y2.
If σ does not divide γ, then there exists an integer v satisfying the congruence α+βv+γv20modσ. One may check this by working one prime divisor of σ at a time; the quadratic formula applies for odd prime divisors. Modulo two, 2σβ24αγ implies that β is even and the congruence has a solution.
Hence Q1(1,v)0 mod σ. Since Q1 represents a multiple of σ, Q1 is equivalent to a form au2+βuv+cσv2. The fact that σ divides the discriminant implies β=bσ for some bZ.
Thus, whether σ divides γ or not, [Q1]=[Qred] for some diform Q. Since [Q2]=[AΔ][Q1], and [Qblue]=[AΔ][Qred], we find that [Q2]=[Qblue]. □
Let SDL2+(Rσ) be the subgroup of DL2+(Rσ) consisting of matrices of determinant one. We say that two diforms Q,Q are SDL2+(Rσ) equivalent if there exists ηSDL2+(Rσ) satisfying Q(v)=Q(ηv) for all divectors v. We write [Q]σ=[Q]σ when the diforms Q and Q are SDL2+(Rσ) equivalent. One may check directly that [Q]σ=[Q]σ implies [Qred]=[Qred]and[Qblue]=[Qblue]. From this, we may reframe Theorem 10 in terms of equivalence classes.

Corollary 11.

Assume σΔ. The map Q(Qred,Qblue) yields a surjective function from
the set of SDL2+(Rσ)-equivalence classes of binary quadratic diforms of discriminant Δ to…
the set of ordered pairs ([Q1],[Q2]) in Cl(Δ) satisfying [Q1]=[AΔ][Q2].
It seems interesting to determine the fibers of this map. As we will see, for σ=2 and σ=3, the question is how two of Conway’s topographs can be interlaced in a single topograph of a diform.

Dilinear Topographs.

Here we return to the assumption that σ=2 or σ=3. The topograph of a binary quadratic diform Q is obtained by replacing each primitive lax divector by the corresponding value of Q. Every value on the topograph of Q thus appears on the topograph of Qred or of Qblue. In this way, values from two of Conway’s topographs interlace in the topograph of a binary quadratic diform. More precisely, we have the following.

Proposition 12.

If z appears on the topograph of Qred, then (i) z appears on the topograph of Q or (ii) σz and zσ1 appears on the topograph of both Qblue and Q. Similarly, if z appears on the topograph of Qblue, then (i) z appears on the topograph of Q or (ii) σz and zσ1 appears on the topographs of both Qred and Q.

Proof:

Suppose z occurs on the topograph of Qred. Thus, Qred(u,v)=z for some coprime u,vZ. If GCD(u,σv)=1, then (u,vσ) is a primitive divector, and Q(u,vσ)=Qred(u,v)=z appears on the topograph of Q.
If GCD(u,σv)1, then σu and GCD(σ1u,v)=1. We compute σ1z=σ1Qred(u,v)=Qblue(σ1u,v)=Q(σ1uσ,v). Hence σ1z appears on the topograph of both Qblue and Q. □

Corollary 13.

Let μred and μblue be the minimum nonzero absolute values of Qred and Qblue. Then min{μred,μblue} is the minimum nonzero absolute value of Q.
The discriminant of a binary quadratic diform is locally visible in its topograph, according to the formulas below:
Δ=(2uv)2efifσ=2;(3uv)2ef=(4u3v)2mn4ifσ=3.
[1]
Polarization for the quadratic form Q implies the following.

Theorem 14.

At every cell in the topograph of Q, as in Fig. 6, one finds arithmetic progressions as below.
i)
σ=2: The triples (e,2u+v,f) and (e,u+2v,f) are arithmetic progressions of the same step size.
ii)
σ=3: The triples (e,3u+v,f) and (e,u+3v,f) are arithmetic progressions of the same step size δ and the triples (m,4u+3v,n) and (m,3u+4v,n) are arithmetic progressions of the same step size 2δ.
Fig. 6.
Cells in the range topograph for σ=2 (Left) and σ=3 (Right).

Proof:

In both cases σ=2,3, the integers e,u,v,f of a cell in Fig. 6 arise as values of Q of the form
e=Q(σvw),u=Q(v),v=Q(w),f=Q(σv+w).
By the polarization identity for quadratic forms, the sequence
Q(σvw),Q(σv)+Q(w),Q(σv+w)
is an arithmetic progression with step size δBQ(σv,w). Here BQ is the bilinear form associated to the quadratic form Q. Similarly, the integers e,f arise as values of Q:
e=Q(vσw),f=Q(v+σw).
The sequence
Q(vσw),Q(v)+Q(σw),Q(v+σw)
is an arithmetic progression with step size δBQ(v,σw). Note that δ=δ, Q(σv)=σu, and Q(σw)=σv. Hence (e,σu+v,f) and (e,u+σv,f) are arithmetic progressions of the same step size.
When σ=3, the values m,n arise as values of Q: m=Q(2v3w) and n=Q(2v+3w). The polarization identity, applied again, shows that (m,4u+3v,n) and (m,3u+4v,n) are arithmetic progressions of the same step size 2δ. □
Similar computations give linear relations among the values around any vertex in the topograph.

Proposition 15.

(Refer to the vertex diagrams above.) When σ=2, a+c=b+d. When σ=3, a+d=b+e=c+f and also a+c+e=b+d+f.
We draw an arrow on each edge to represent the direction of increasing progressions or a circle if all progressions are constant. Fig. 7 displays some examples. The climbing principle is the same as Conway’s: Arrows always propagate when one looks at a cell of positive values. By the same argument as that of Conway, one obtains unique wells—a reduction theory for positive-definite diforms.
Fig. 7.
Topographs for the definite binary quadratic diform Q(x,y)=x2+2xy+3y2 over Z[2] and the indefinite diform Q(x,y)=x22y2 over Z[3].

Proposition 16.

Let Q be a positive-definite BQD over Rσ, with σ=2 or σ=3. Then the topograph of Q exhibits a unique well—either a single vertex or an edge (double well) from which all arrows emanate.
The river of a BQD is the set of segments separating positive values from negative ones in its topograph. The most interesting forms, just as for BQFs, are the nondegenerate indefinite forms.

Proposition 17.

If Q is a nondegenerate indefinite diform, then its topograph contains a single endless nonbranching river.

Proof:

The existence and uniqueness of a river follows from the same argument as for Conway’s case. Namely, as one travels from a positive face to a negative face, one must at some point cross a river from positive to negative. This gives existence. The climbing principle (propagation of growth arrows) demonstrates that as one travels away from a river, one cannot hit another river, giving uniqueness. The crux of Proposition 17 is that rivers cannot branch.
For if a river branched, the faces around the branch point would alternate signs as they cross each river segment. Hence the rivers may branch only with even degree at a vertex. The possibilities, up to symmetry, are displayed below.
We apply Proposition 15 repeatedly. When σ=2, the identity a+c=b+d yields a contradiction if the signs of a and c are equal and opposite to the signs of b and d. Similarly, when σ=3, the identity a+c+e=b+d+f yields a contradiction if the signs of a,c,e are equal and opposite to the signs of b,d,f. Branch-forms I and II are excluded.
It also happens that, when σ=3, then a+d=b+e=c+f. Thus, we find a contradiction if the signs of a,d are equal and opposite to the signs of c,f. This excludes form III. We also find a contradiction if the signs of b,e are equal and opposite to the signs of a,d. This excludes form IV. Hence the river cannot branch. □
As we have an endless nonbranching river, analysis of riverbends gives a minimum-value bound for diforms.

Theorem 18.

Let Q be a nondegenerate indefinite BQD, and let μQ denote its minimum nonzero absolute value.
i)
σ=2: If Q is not DL2(Rσ) equivalent to a multiple of x2y2, then μQΔ/10.
ii)
σ=3: If Q is not DL2(Rσ) equivalent to a multiple of x2y2, then μQ2Δ/25.

Proof:

The entire river cannot be adjacent to a single region, because its values opposite such a region would form a biinfinite quadratic sequence with positive sign and negative acceleration or negative sign and positive acceleration. Hence the river must “bend.” If one finds riverbends as in Figs. 8 and 9, Eq. 1 gives the stated minimum value bound or better (as derived in Figs. 8 and 9). If no such riverbends of those shapes occur, then the river must maintain one of the three shapes of Fig. 10 throughout its entire length.
Fig. 8.
Riverbend types for σ=2.
Fig. 9.
Riverbend types for σ=3.
Fig. 10.
One more river shape for σ=2 and two more shapes for σ=3.
The isometry group of such a homogeneous river includes a translation along the river. Replacing Q by a DL2(Rσ)-equivalent form if necessary, we may place this river through the segment separating ±(1,0) and ±(0,1). Translation along the homogeneous rivers is then given by the matrices
R=2112,S=2332,T=3213
in the three cases shown in Fig. 10. Periodicity of the river implies that Re, Se, or Te is an isometry of Q for some e>0.
The eigenvectors of R and S are (1,1) and (1, −1). If λ and μ denote their eigenvalues, then
Q(1,1)=λ2eQ(1,1)andQ(1,1)=μ2eQ(1,1).
But a quick computation demonstrates that λ,μR and λ,μ/{1,1}. Hence Q(1,1)=Q(1,1)=0 in the two straight-river cases. Writing the diform as Q(x,y)=ax2+bσxy+cy2, this implies a+bσ+c=abσ+c=0. Hence a=c and b=0. We have proved that an endless straight river occurs only if Q is equivalent to a multiple of x2y2 (when σ=2 or σ=3).
It remains to study the third shape of the homogeneous river, on which T acts by translation. The eigenvectors of T are (2,±1), with eigenvalues 3±2, respectively. Hence, if Te is an isometry of Q for some e>0, then Q(2,1)=Q(2,1)=0. In this case, 2a+b6+c=2ab6+c=0. Hence b=0 and c=2a. We have proved that an endless homogeneous river of the third form occurs if and only if Q is equivalent to a multiple of x22y2 (displayed in Fig. 7). The discriminant of the diform x22y2 is 24, while its minimum absolute value is μQ=1. The estimate μQ2Δ/25 can be directly checked in this case, finishing the proof. □
The discriminant of the diform x2y2 is 4σ and its minimal value is μQ=1. Thus, when σ=2, the estimate μQΔ/10 is violated; when σ=3, the estimate μQ2Δ/25 is violated. Hence the exceptional diforms x2y2 cannot be removed from Theorem 18.

Corollary 19.

Suppose that Q1 and Q2 are nondegenerate indefinite BQFs of discriminant Δ, with σΔ and [Q2]=[AΔ][Q1]. Then
i)
σ=2: If Q1 and Q2 are not equivalent to a multiple of x22y2, then min{μQ1,μQ2}Δ/10.
ii)
σ=3: If Q1 and Q2 are not equivalent to a multiple of x23y2, then min{μQ1,μQ2}Δ/13.

Proof:

This follows directly from Theorems 18 and 10, except that 2/25 has been replaced by 1/13. This replacement is possible, due to a gap in the Markoff spectrum between 12 and 13; see ref. 11, section 1, proof of theorem 3.3.□

4. Conclusion

In each of the discussed examples, there is a coincidence between a Coxeter group and an arithmetic group. For Conway’s topograph, it is the coincidence between the Coxeter group of type (3,) and the arithmetic group PGL2(Z). The dilinear groups, of Coxeter types (2σ,) for σ=2,3, are arithmetic subgroups of PGU1,1Q(σ)/Q(Q), the projective unitary similitude group for a Hermitian form relative to Q(σ)/Q.
When such a coincidence occurs, the Coxeter group is arithmetic, and the following two questions are natural.
i)
Is there an arithmetic interpretation for the flags in the Coxeter group?
ii)
Does the Coxeter geometry give a new reduction theory for a class of quadratic (or Hermitian) forms?
The first question is reminiscent of the classical theory of flag varieties. When G is a simple simply connected linear algebraic group over a field k, one can often identify a “standard” representation of G on a k-vector space V. Every k-parabolic subgroup of G is the stabilizer of some sort of k flag in V. If G is a symplectic or spin or unitary group, these are the isotropic flags in the standard representation. In type G2, these are the nil flags in the split octonions. In an 11-part series of papers (Beziehungen der E7 und E8 zur Oktavenebene I–XI, published 1954–1963, refs. 1216), Freudenthal studied the “metasymplectic” geometry which describes flags in representations of exceptional groups.
Now it appears that arithmetic Coxeter groups provide a parallel industry, examining their representations on various modules over Euclidean domains. Arithmetic flags are generalized bases of these modules. The geometry of arithmetic flag varieties seems (so far) to be the combinatorial geometry of Coxeter groups. We do not yet see algebraic geometry in the picture, as one finds in flag varieties G/P.
The applications to arithmetic (the arithmetic of arithmetic Coxeter groups) include Conway’s approach to binary quadratic forms and new generalizations. The reduction theory for quadratic and Hermitian forms is a classical subject, sometimes tedious in its algebra—the Coxeter geometry and Conway’s theory of wells and rivers give an intuitive approach. Beyond reframing old results, it seems unlikely that one would find the reduction theory of our “diforms” (or suitable pairs of binary quadratic forms) without considering the Coxeter group. In this way, arithmetic Coxeter groups offer applications to number theory.
This paper has discussed five arithmetic Coxeter groups, of types (3,), (3,3,6), (3,4,4), (4,), and (6,). If this is a game of coincidences, when might it end? In ref. 17, Belolipetsky surveys the arithmetic hyperbolic Coxeter groups; following his treatment, we review the classification of such Coxeter groups.
The groups we have studied are simplicial hyperbolic arithmetic Coxeter groups. In ref. 18, Vinberg proves there are 64 such groups in dimension at least 3. These fall into 14 commensurability classes by ref. 19, as shown in Table 1. It would not be surprising if each one offered a notion of arithmetic flags (e.g., superbases, etc.) and quadratic/Hermitian forms. For example, the Coxeter group of type (3,3,3,4,3) is arithmetic, commensurable with PGL2(A) where A is the Hurwitz order in the quaternion algebra Q+Qi+Qj+Qk. Arithmetic flags in this case can be interpreted as lax vectors, bases, superbases, 3-simplex bases, 4-simplex bases, and 5-orthoplex bases, in the A-module A2.
Table 1.
Commensurability classes of simplicial hyperbolic arithmetic Coxeter groups of dimension at least 3 (extracted from ref. 19)
DimensionCoxeter types
3(3,3,6) and (3,4,4)
4(3,3,3,5) and (3,3,3,4) and (3,4,3,4)
5(3,3,3,4,3) and (3,3[5])
6(4,32,32,1) and (3,3[6])
7(32,2,2) and (4,33,32,1) and (3,3[7])
8(34,3,1)
9(36,2,1)
Table 1 displays only groups of dimension at least 3. In dimension 2, we find Conway’s topograph and its dilinear variants. One might also consider arithmetic hyperbolic triangle groups, classified by Takeuchi in refs. 20 and 21. Up to commensurability, there are 19 of these, each associated to a quaternion algebra over a totally real field. Vertices, edges, and triangles in the resulting hyperbolic tilings surely correspond to arithmetic objects—What are they?
If one wishes to depart from the simplicial groups, there are nonsimplicial arithmetic hyperbolic Coxeter groups. In the results of Vinberg (22), all examples occur in dimension at most 30; there are finitely many up to commensurability. One may be able to explore the arithmetic of arithmetic Coxeter groups for a long time—what is currently missing is a general theory of arithmetic flags and forms to make predictions in a less ad hoc manner.
Departing from the setting of Coxeter groups may also be appealing, especially in low dimension. For example, the Coxeter geometry makes the reduction theory of BHFs particularly appealing over Z[i] and Z[ω]. But Bestvina and Savin (7) are able to work over other quadratic imaginary rings although the geometry lacks homogeneity. One might study diforms over other real quadratic rings, in the same way. More arithmetic may be found in “thin” rather than arithmetic groups, e.g., in the work of Stange (23) on Apollonian circle packings. Still, Coxeter groups seem an appropriate starting place, where arithmetic applications are low-hanging fruit.

Acknowledgments

The authors thank the anonymous referee for comments and insights. M.H.W. is supported by the Simons Foundation Collaboration Grant 426453.

References

1
JH Conway, The Sensual (Quadratic) Form. Carus Mathematical Monographs (Mathematical Association of America, Washington, DC), Vol 26. (1997).
2
CF Gauss, Disquisitiones Arithmeticae, trans Clarke AA, revised by Waterhouse WC, Greither C, and Grootendorst AW (Springer, New York). (1986).
3
L Bianchi, Geometrische darstellung der gruppen linearer substitutionen mit ganzen complexen coefficienten nebst anwendungen auf die zahlentheorie [Geometric representation of groups of linear substitutions with complex coefficients and applications to number theory]. Math Ann 38, 313–333 (1891).
4
R Fricke, F Klein, Vorlesungen über die Theorie der Automorphen Functionen [Lectures on the theory of automorphic functions] (B. G. Teubner, Leipzig, Germany), Vol 1. (1897).
5
E Schulte, AI Weiss, Chirality and projective linear groups. Discrete Math 131, 221–261 (1994).
6
HSM Coxeter Regular Polytopes (Dover Publications, Inc., 3rd Ed, New York, 1973).
7
M Bestvina, G Savin, Geometry of integral binary Hermitian forms. J Algebra 360, 1–20 (2012).
8
CD Shelley, An arithmetic construction of the Gaussian and Eisenstein topographs. PhD thesis (University of California, Santa Cruz, CA). (2013).
9
NW Johnson, AI Weiss, Quadratic integers and Coxeter groups. Canad J Math 51, 1307–1336 (1999).
10
M Bhargava, Higher composition laws. I. A new view on Gauss composition, and quadratic generalizations. Ann Math 159, 217–250 (2004).
11
Jr M Hall, The Markoff spectrum. Acta Arith 18, 387–399 (1971).
12
H Freudenthal, Beziehungen der E7 und E8 zur Oktavenebene [Relationship of E7 and E8 with the Cayley plane], I–II. Nederl Akad Wetensch Proc Ser A 57, 363–368 (1954).
13
H Freudenthal, Beziehungen der E7 und E8 zur Oktavenebene [Relationship of E7 and E8 with the Cayley plane], III. Nederl Akad Wetensch Proc Ser A 58, 151–157 (1955).
14
H Freudenthal, Beziehungen der E7 und E8 zur Oktavenebene [Relationship of E7 and E8 with the Cayley plane], IV. Nederl Akad Wetensch Proc Ser A 58, 277–285 (1955).
15
H Freudenthal, Beziehungen der E7 und E8 zur Oktavenebene [Relationship of E7 and E8 with the Cayley plane], V–IX. Nederl Akad Wetensch Proc Ser A 62, 447–474 (1959).
16
H Freudenthal, Beziehungen der E7 und E8 zur Oktavenebene [Relationship of E7 and E8 with the Cayley plane], X–XI. Nederl Akad Wetensch Proc Ser A 66, 455–487 (1963).
17
M Belolipetsky, Arithmetic hyperbolic reflection groups. Bull Am Math Soc 53, 437–475 (2016).
18
EB Vinberg, Discrete groups generated by reflections in Lobačevskiĭ spaces. Math USSR Sbornik 1, 429–444 (1967).
19
NW Johnson, R Kellerhals, JG Ratcliffe, ST Tschantz, Commensurability classes of hyperbolic Coxeter groups. Linear Algebra Appl 345, 119–147 (2002).
20
K Takeuchi, Commensurability classes of arithmetic triangle groups. J Fac Sci Univ Tokyo Sect IA Math 24, 201–212 (1977).
21
K Takeuchi, Arithmetic triangle groups. J Math Soc Jpn 29, 91–106 (1977).
22
EB Vinberg, The nonexistence of crystallographic reflection groups in Lobachevskiĭ spaces of large dimension. Funktsional Anal i Prilozhen 15, 67–68 (1981).
23
KE Stange, The sensual Apollonian circle packing. Expo Math 34, 364–395 (2016).

Information & Authors

Information

Published in

Go to Proceedings of the National Academy of Sciences
Proceedings of the National Academy of Sciences
Vol. 116 | No. 2
January 8, 2019
PubMed: 30587588

Classifications

Submission history

Published online: December 26, 2018
Published in issue: January 8, 2019

Keywords

  1. arithmetic
  2. Coxeter group
  3. quadratic form
  4. topograph

Acknowledgments

The authors thank the anonymous referee for comments and insights. M.H.W. is supported by the Simons Foundation Collaboration Grant 426453.

Notes

This article is a PNAS Direct Submission.
*The Eisenstein topograph was first described in 2007, in the unpublished master’s thesis of Andreas Weinert.

Authors

Affiliations

Suzana Milea
Department of Mathematics, University of California, Santa Cruz, CA 95064;
Christopher D. Shelley
Private address, Bolinas, CA 94924
Department of Mathematics, University of California, Santa Cruz, CA 95064;

Notes

1
To whom correspondence should be addressed. Email: [email protected].
Author contributions: S.M., C.D.S., and M.H.W. designed research, performed research, analyzed data, and wrote the paper.

Competing Interests

The authors declare no conflict of interest.

Metrics & Citations

Metrics

Note: The article usage is presented with a three- to four-day delay and will update daily once available. Due to ths delay, usage data will not appear immediately following publication. Citation information is sourced from Crossref Cited-by service.


Citation statements




Altmetrics

Citations

If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.

Cited by

    Loading...

    View Options

    View options

    PDF format

    Download this article as a PDF file

    DOWNLOAD PDF

    Get Access

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Personal login Institutional Login

    Recommend to a librarian

    Recommend PNAS to a Librarian

    Purchase options

    Purchase this article to access the full text.

    Single Article Purchase

    Arithmetic of arithmetic Coxeter groups
    Proceedings of the National Academy of Sciences
    • Vol. 116
    • No. 2
    • pp. 339-700

    Media

    Figures

    Tables

    Other

    Share

    Share

    Share article link

    Share on social media