652 S. Fomin and L. Setiabrata points on the plane; these measurements include the squared distances between pairs of points as well as signed areas of oriented triangles formed by triples of points.
Just like the ordinary friezes, the Heronian ones are governed by rational recurrences.
The key distinction from the classical setting is that the quantities being updated as one moves along a Heronian frieze are not algebraically independent: they satisfy Heron's formulas. Crucially, these algebraic dependences propagate under the frieze recurrences.
We establish the basic properties of Heronian friezes, most importantly those concerning periodicity and Laurentness. We also study a related notion of a Cayley-Menger frieze, based on the eponymous equation involving the six squared distances between four coplanar points. To achieve unambiguous single-valued propagation in a Cayley-Menger frieze, we identify a subtle algebraic condition of coherence, which involves squared distances between six coplanar points.
We next provide a brief overview of the paper. Suppose one wants to describe a configuration of n points on the Euclidean plane A, viewed up to the action of the group Aut(A) of orientation-preserving rigid motions. The parameters (measurements) used in such a description must be Aut(A)-invariant. The standard approach of distance geometry is to use a subset of the squared distances between the points. Since the configuration space has dimension 2n -3, it is natural to start by measuring some appropriately selected 2n -3 squared distances. The simplest choice is to pick a triangulation of a convex n-gon by n -3 of its diagonals, view it as a graph with n vertices and 2n -3 edges, and measure the distances between the pairs of points in a configuration corresponding to the sides and diagonals of the polygon. Assuming that the configuration is sufficiently generic (namely all diagonal lengths are nonzero), this brings the dimension down to zero; in other words, the number of configurations with the given values of those 2n -3 measurements is finite. Unfortunately, this number is exponentially large: for each triangle of the triangulation, there are two possible orientations, and each of the 2 n-2 choices can be realized.
One way to resolve this ambiguity is to add additional "bracing" edges to the triangulation [13]. A frieze version of this approach is developed in Section 5, reviewed later in this introduction. In Section 2, we propose a different approach (inspired by classical invariant theory) that appears to allow for a better control of the computational and algebraic aspects of the problem: in addition to the 2n -3 squared distances, we measure the signed areas of the n -2 triangles of the triangulation.
In other words, for each of these triangles, we choose one of the two square roots in Heron's formula. It turns out that once such choices have been made, the rest of the Downloaded from https://academic.oup.com/imrn/article/2021/1/648/5825012 by University of Michigan user on 10 July 2021 Heronian Friezes 653 measurements (in particular, the squared distances for all n 2 pairs of points) can be computed using rational recurrences.
An explicit implementation of these recurrences leads us to the notion of a Heronian frieze, introduced in Section 3. We show that a sufficiently generic Heronian frieze is uniquely determined by a small proportion of its entries. We then prove, under the same genericity assumption, that any Heronian frieze possesses the glide symmetry and consequently is periodic; see Theorem 3.11. These periodicity properties parallel the analogous properties of Coxeter-Conway friezes.
In Section 4, we establish the Laurent phenomenon for Heronian friezes: every squared distance and every signed area of a triangle in an n-point configuration can be expressed as a Laurent polynomial in the initial measurement data associated with an arbitrary triangulation of an n-gon; see Theorems 4.1 and 4.18. Note that the 3n -5 initial measurements are not algebraically independent, so there is no canonical rational function that expresses an arbitrary measurement in terms of the initial ones.
Curiously, the only initial measurements that appear in the denominators of our Laurent expressions are those corresponding to the diagonals of the initial triangulation. While the absence of the squared distances corresponding to the sides of the polygon did not come as a surprise (given a similar phenomenon in cluster theory), we see no simple conceptual explanation for the absence of signed areas in the denominators. Another mystery is that in spite of having the same underlying combinatorics as cluster algebras of type A, this construction does not appear to fit into any (generalized) cluster algebras setup known to us.
Section 5 is essentially self-contained. It is devoted to an alternative construction of friezes adapted to Euclidean geometry of point configurations. This time, we do not use signed areas at all, keeping squared distances as the only entries of a frieze. The naïve idea is to use a propagation rule based on the Cayley-Menger equation satisfied by the six squared distances between pairs of vertices of a plane quadrilateral.
Unfortunately, this approach immediately runs into a serious complication: unlike the Ptolemy relation used in the classical theory of friezes, the Cayley-Menger equation is quadratic in each of the six variables, so the iterative process branches into two subcases at each step of the recurrence. (A similar situation arises in the study of the Kashaev equation [14,16].) To resolve the accumulating ambiguities, we employ an idea inspired by [16]: we identify an additional algebraic condition that must be satisfied by a Cayley-Menger frieze coming from a point configuration. This condition, which we call coherence by analogy with [16], involves 13 frieze entries associated with a 3 × 3 grid subpattern. The key advantage of the coherence equation is that it has degree 1 with respect to the rightmost (or leftmost) variable, so it can be used to set up a rational recurrence. Under this recurrence, the Cayley-Menger condition propagates and a coherent frieze is uniquely reconstructed from the initial data, subject to certain genericity conditions. We later use these propagation rules to establish the glide symmetry of coherent Cayley-Menger friezes, see Theorem 5.17.
In Section 6, we discuss the relationship between Heronian and Cayley-Menger friezes. We show that, subject to the aforementioned genericity conditions, the coherent Cayley-Menger friezes are precisely the restrictions of Heronian friezes. This relationship closely resembles the one between the hexahedron equation of R. Kenyon-R.
Pemantle [14] and Kashaev's equation. In fact, both relationships can be viewed as adaptations of [16,Section 10] to their respective contexts.
Why does an approach employing both squared distances and signed areas produce simpler recurrences than the one that only uses squared distances? One possible explanation comes from the fact that in the case of point configurations on the plane, Cayley-Menger varieties are given by equations of degree 3, namely the vanishing of the mixed Cayley-Menger determinants, see [3]. By contrast, the ring of SO(2) invariants of a collection of several vectors is generated in degree 2.
The results in this paper can be extended to other f lat real geometries (such as the cylinder and the torus) by passing to the universal cover. We intend to investigate the hyperbolic and/or spherical cases in subsequent work. It would also be interesting to develop the analogues of these results for higher-dimensional geometry.
Our work was inspired by several sources: the classical Coxeter-Conway theory of frieze patterns [5,6], the theory of rigidity phenomena in distance geometry (especially generic global rigidity on the plane [4,11,12]), classical invariant theory [18] (especially invariants of SO(2, C)), the theory of cluster algebras of type A [9,10] (especially their hyperbolic geometry models [8]), and A. Leaf's [16] theory of coherent solutions of the Kashaev equation.
Let V be a 2D vector space over C, endowed with a symmetric inner product (u, v) → u, v and an associated skew-symmetric volume form (u, v) → [u, v]. Without loss of generality, we can identify V with C 2 , with the two forms defined by
Let A be the corresponding affine space (the complex plane). Each pair of points A, B ∈ A gives rise to a vector -→ AB that moves A to B.
where we use the notation
There is also a "converse Heron theorem" (Lemma 2.2 below). To state it properly, we need to introduce the group Aut(A) of orientation-preserving isometries of A.
Lemma 2.2. Given complex numbers p, q, r, s satisfying s 2 = H(p, q, r), at least one of them nonzero, there exists a triangle ABC in A such that x(A, B) = p, x(A, C) = q,
x(B, C) = r, and S(A, B, C) = s. Moreover, such a triangle is unique up to the action of Aut(A).
Proof. We note that Aut(A) = SO(V) T(V), where T(V) is the group of translations by an element of V. Since SO(V) acts freely and transitively on the unit sphere in V, the claim will follow from Lemma 2.3 below.
Given A, B ∈ A with x(A, B) = p = 0, and three numbers q, r, s ∈ C satisfying s 2 = H(p, q, r), there exists a unique C ∈ A such that x(A, C) = q, x(B, C) = r, and S(A, B, C) = s.
)
for all distinct i, j, k ∈ {1, . . . , n}. We denote by
the labeled collection of all these measurements. This collection of numbers (or, depending on the point of view, functions on the configuration space A n ) satisfies many identities, including the obvious symmetries
and the Heron equations
)
) with all these seven conditions, for the sake of symmetry (cf. Proposition 2.12 below) as well as conceptual clarity.
Proposition 2.11. Let (a, b, c, d, e, p, q) be a 7-tuple of complex numbers satisfying equations 2.132.14. Assume that e = 0. Then, there exist unique f , r, s ∈ C such that (a, b, c, d, e, f , p, q, r, s) is a Heronian diamond. Specifically,
(2.23) Thus, we need to deduce (2.23) from (2.13)- (2.19). It will be convenient to denote g =
Dividing by 4e (here, we use that e = 0), we get (2.23).
Corollary 2.13. In a Heronian diamond (a, b, c, d, e, f , p, q, r, s), once the components a, b, c, d (shown in blue in Figure 3) have been fixed, the values e, p, q determine f , r, s uniquely (provided e = 0), and vice versa (provided f = 0).
Proof. Combine Propositions 2.11 and 2.12.
The next two lemmas will be needed in Section 3.
Lemma 2.14 (Heronian diamonds with a = q = r = 0). Complex numbers 0, b, c, d, e, f , p, 0, 0, s form a Heronian diamond if and only if
Proof. Under the assumptions a = q = r = 0, we have
Since 4eb -(-b + ce) 2 = H(b, c, e), the claim follows.
Lemma 2.15 (Heronian diamonds with c = p = s = 0). Complex numbers a, b, 0, d, e, f , 0, q, r, 0 form a Heronian diamond if and only if
Proof. The proof is completely analogous to the proof of Lemma 2.14. Alternatively, combine Lemma 2.14 with Proposition 2.12.
Corollary 2.16. In a Heronian diamond (a, b, c, d, e, f , p, q, r, s) with a = q = r = 0, the values e, b, p determine f , d, s uniquely, and vice versa. In a Heronian diamond (a, b, c, d, e, f , p, q, r, s) with c = p = s = 0, the values d, e, q determine b, f , r uniquely, and vice versa.
Remark 2.9 implies the following statement. satisfy the following identities, for any distinct i, j, k, ∈ {1, . . . , n}:
Motivated by Figure 4, we introduce the notion of a Heronian frieze, cf.
Definition 3.1 below. Informally, a Heronian frieze is a collection of numbers arranged in a pattern shown in Figure 5 and satisfying the Heronian diamond equations for all diamonds in the pattern (plus some additional conditions near the upper and lower boundaries). We next proceed to a formal definition.
We begin by introducing the relevant indexing sets. Definition 3.2. For n ≥ 4, let N n and L n be the sets defined by
The (disjoint) union I n = N n ∪ L n will serve as the indexing set for the Heronian friezes.
We visualize this set as follows, see Figure 6. We interpret Z 2 as the set of integer points for the coordinate system whose axes are rotated clockwise by π/4 with respect to the usual placement. The indices in N n ("the nodes") are the points (i, j) in the strip 0 ≤ ji ≤ n whose coordinates i, j are half-integers, with at least one of them an integer.
The indices in L n ("the lines") represent straight lines parallel to the coordinate axes, with half-integer offsets.
We will refer to the indices (i, j) ∈ N n with 1 ≤ ji ≤ n -1 as the interior nodes of N n .
Definition 3.1. A Heronian frieze of order n ≥ 4 is an array z = (z α ) α∈I n of complex numbers indexed by the set I n (see Definition 3.2), which satisfies the following local conditions. The main condition is that for every 10-tuple of indices shown in Figure 7 (with (i, j) ∈ N n ∩ Z 2 an interior node), we require the corresponding 10 entries
to form a Heronian diamond. (For a dictionary between this notation and the notation in Definition 2.3, compare Figures 3 and7.) In addition, we impose the boundary conditions
The notion of a Heronian frieze simplifies under the assumption that all entries indexed by the elements of the set L n (see (3.
2 ) = b for all i. Such a frieze can be thought of as an array z = (z (i,j) ) (i,j)∈N n of complex numbers indexed by the set N n (see (3.5)) and satisfying the boundary conditions (3.7) together with the following relations, which hold for every node (i, j) ∈ Z 2 with 1 ≤ ji ≤ n -1:
An example of an equilateral Heronian frieze (with b = 1) is shown in Figure 8.
The boundary conditions (3.7) imply the following identities.
Proposition 3.4. Let z = (z α ) α∈I n be a Heronian frieze of order n. Then
)
(3.9)
Proof. The diamond condition for the interior node (i, i + 1) says that the 10 numbers form a Heronian diamond. By (3.7), three of these numbers vanish:
2 ) = 0. Hence, Lemma 2.15 applies and z (i,i+1) = z (i+ 1 2 , ) by (2.29). Similarly, the diamond condition for the node (i -1, i) says that the 10 numbers
form a Heronian diamond. The three numbers z (i,i) , z (i-1 2 ,i) and z (i,i+ 1 2 ) are all zero, so Lemma 2.15 applies. By (2.30), we get z (i,i+1) = z (i+ 1 2 , ) , establishing (3.8).
Equation (3.9) is proven in a similar way, by applying Lemma 2.14 to the Heronian diamonds associated with the interior nodes (i, i + n -1) and
Definition 3.5. In light of Proposition 3.1 (also compare Figures 4 and7), any n-gon P in the plane A gives rise to a Heronian frieze z = z(P) of order n by setting
)
)
)
where m denotes the unique integer in {1, . . . , n} satisfying m ≡ m (mod n).
(Condition (3.7) holds because x ii = S i,i,i+1 = S i,i+1,i+1 = 0 for every i ∈ Z.)
Any frieze z(P) coming from a polygon P is necessarily periodic:
)
(3.17)
In fact, (3.15) can be strengthened as follows: z(P) possesses the glide symmetry
which also ref lects the symmetries x ij = x ji and S ijk = S jki of the measurements. (The same symmetries appear in the Coxeter-Conway theory of frieze patterns [5,6].) We will soon provide a partial converse to this phenomenon, cf. Theorem 3.11.
Although the definition of Heronian friezes was motivated by geometry, they are purely algebraic objects, merely tables of numbers satisfying some algebraic relations.
These relations can be viewed as recurrences: start by picking some initial data, then propagate away by repeatedly applying Corollary 2.13 (or Corollary 2.16) for the Heronian diamonds in the pattern. To describe this procedure in precise terms, we will need to specify the sets of indices corresponding to our choices of initial data. • (i 1 , j 1 ), . . . , (i 2n-3 , j 2n-3 ) are interior nodes in N n ;
• 1 , . . . , n-2 are lines in L n ;
• j 1i 1 = 1;
The following less formal description is perhaps more illuminating. Let us view N n as the vertex set of a graph, as shown in Figure 5, but without the dashed lines. Then
• (i 1 , j 1 ), . . . , (i 2n-3 , j 2n-3 ) are the nodes lying on the shortest path connecting the lower and upper boundaries of the strip of interior nodes;
• 1 , . . . , n-2 are the dashed lines intersecting this shortest path. Example 3.2. For n = 5 (cf. Figure 6), a traversing path consists of 3n -5 = 10 indices.
One example of such a path is (0, 1), (0, 3 2 ), (0, 2), (-1 2 , 2), (-1, 2), (-1, 5 2 ), (-1, 3), ( , 3 2 ), (-1 2 , ), ( , 5 2 ) .
Then, the entire frieze can be uniquely reconstructed from its entries lying on a single traversing path π .
Proof. Repeatedly apply the recurrences underlying Corollary 2.13 and Corollary 2.16 to all Heronian diamonds in the frieze, starting with the ones adjacent to π and expanding out.
To be more specific, the recurrences for rightward propagation in a Heronian Example 3.3. Figure 8 shows the fundamental domain for an equilateral frieze with respect to the glide symmetry.
The main result of this section is the following theorem.
say that G is trimmed with respect to {i, j}. See Figure 9.
Similarly, the trimming of G with respect to a triple
is the induced subgraph of G whose vertex set includes i, j, k, and the endpoints of all diagonals in D(G) that cross at least one of the diagonals {i, j}, {i, k}, {j, k}. Again, Then, each entry of z can be written as a Laurent polynomial in terms of the entries lying on an arbitrary traversing path π . The denominator of this Laurent polynomial is a monomial in the values indexed by the integer nodes lying on π . In the remainder of this section, we present an alternative approach to the Laurent phenomenon for Heronian friezes. While more technical than the proof of Theorem 4.1 given above, this approach produces a stronger (and more explicit) result. In the case of triangles, Remark 4.4 can be strengthened as follows.
Lemma 4.12. Let G be a triangulation trimmed with respect to a triple (i, j, k). Suppose that for any / ∈ {i, j, k}, the triangulation G is trimmed with respect to at least one of the triples (i, j, ), (i, k, ), (j, k, ). Then, G is trimmed with respect to at least one of {i, j}, {i, k}, or {j, k}. In particular, G is thin.
Proof. First, suppose that one of the sides of the triangle (i, j, k), say {i, j}, lies on the distinguished n-cycle; that is, i ≡ j ± 1 mod n. Since G is trimmed with respect to (i, j, k), we have
Then, there exists a vertex such that the diagonal {j, } crosses both D j and {i, k} but neither D i nor D k . We now observe that the diagonal D i does not cross any of the sides of (j, k, ), the diagonal D j does not cross any of the sides of (i, k, ), and the diagonal D k does not cross any of the sides of (i, j, ). In other words, the triangulation G is not trimmed with respect to each of the triples (i, j, ), (i, k, ), (
Remark 4.13. We already noted, cf. Remark 4.4 and the proof of Theorem 4.1, that it is sufficient to establish the Laurent phenomenon in the case when the triangulation G at hand is trimmed with respect to the measurement in question. In the case when the measurement is a squared distance x ij , this immediately implies that G is thin. In the case of a signed area S ijk , we can assume that the triangulation G, in addition to being trimmed with respect to (i, j, k), is also trimmed with respect to at least one of the triples (i, j, ), (i, k, ), (j, k, ). (Otherwise, we can invoke the additive identity (3.2) and then use trimming to induct on n, the number of vertices.) Hence, Lemma 4.12 applies, meaning that we may assume that G is trimmed with respect to one of the sides of (i, j, k), and in particular is thin. above; to be more precise,
We then define, for 2 ≤ j ≤ n -1:
It will also be helpful to introduce the following notation, for 2 ≤ a < b ≤ n: Proof. First, S j ∈ xS G (P) since S j is the rescaled area of the triangle whose two sides are D j and D j+1 (cf. (2.2) and (2.8)). Second, note that v jv j+1 is a vector linking two adjacent points on the perimeter of the polygon P. Consequently,
The statement concerning even (a, b) and odd (a, b) follows.
Proposition 4.16. In the notation of (4.2) and (4.5)-(4.6), we have:
In particular, both v a , v b and [v a , v b ] are Laurent polynomials with integer coefficients in the measurements in xS G (P). In each of these Laurent polynomials, the denominator is a square-free product of the measurements x ij ∈ x D(G) (P).
Let us adjoin a formal square root ε = √ -1 to C. In other words, our computations will be done in the ring
Furthermore, with the notation
, we have
Comparing (4.9) with (4.10), we conclude that
Rearranging equations (4.11) and (4.12) yields (4.7) and (4.8).
For 1 ≤ j < k ≤ n, consider the unique path in the spanning tree formed by D 2 , . . . , D n that connects j to k. We denote the length of this path by (j, k).
) be the indices of the edges forming this path, so that the set of these edges is {D i a : 1 ≤ a ≤ (j, k)}. Proposition 4.17. Let (P, G) be a thin triangulation of a plane n-gon, trimmed with respect to the diagonal D = {c, n}, see Definition 4.14. Then
where we use the notation
,
Now, the bilinearity of the forms For the readers interested in the computational aspects of these problems, we note that the above formulas lead to polynomial complexity algorithms: although the sums in (4.7)-(4.8) may contain exponentially many terms as n → ∞, they can be computed very fast via the product formula (4.9).
We conclude this section by providing an explicit version of Theorem 4.1 for the "fan" triangulation in which all diagonals are incident to a single vertex.
)
Also, for 1 < a < b < c ≤ n, we have:
Proof. Formula (4.18) is clear. Formula (4.16) is a special case of (4.13) (with the substitutions (4.7)), applied to the trimming of G with respect to the diagonal {a, b}.
Similarly, formula (4.17) is a special case of (4.14), with the substitutions (4.8).
Recall the following classical result; see for example, [
(see (3.6)) in which, for every (i, j) ∈ Z 2 satisfying 1 ≤ ji ≤ n -1, the 6-tuple i,j (z) def = (z (i,j+1) , z (i+ 1 2 , ) , z (i+1,j) , z ( ,j+ 1 2 ) , z (i,j) , z (i+1,j+1) )
(5.3) (see Figure 12) forms a Cayley-Menger diamond. In other words, we require that
In addition, we impose the following boundary conditions (cf. (3.8)-(3.9)):
)
(5.5)
An example of a Cayley-Menger frieze is shown in Figure 13.
)
where m denotes the unique integer in {1, . . . , n} satisfying m ≡ m (mod n). The boundary conditions (5.4)-(5.5) are easily checked, using the fact that x ii = 0 for all i ∈ {1, . . . , n}.
An example is shown in Figure 14.
Definition 5.1.
It will be helpful to introduce some nonconventional (but suggestive) notation for the partial derivatives of the Cayley-Menger polynomial M = M(a, b, c, d, e, f ) with respect to its 6 arguments. This notation makes reference to the placement of these arguments in the diamond, cf. Figure 11. We denote 15 for a visual representation). Then
(5.24)
Moreover, if x ij = x ij (P) are the measurements of a hexagon P = (A 1 , . . . , A 6 ), then Proof. Applying Lemma 5.6 to each Cayley-Menger diamond x i , we conclude that
where Let z be a Cayley-Menger frieze. Consider four adjacent diamonds sharing a common vertex (i, j), as shown in Figure 16. Proposition 5.8 implies that for any (i, j) ∈ Z 2 with 2 ≤ ji ≤ n -2, we have
where we use notation (5.3) for the diamonds of z. Consequently,
(5.28)
In general, the signs of the products appearing on both sides of (5. Proof. The coherence condition (5.29) for (i, j) ∈ Z 2 is precisely equation (5.25) for the (possibly degenerate) sub-hexagon (A i-1 , A i , A i+1 , A j-1 , A j , A j+1 ) of P. This equation holds by virtue of Proposition 5.13.
Remark 5.12. The coherence condition (5.29) involves 13 entries of the frieze whose indices are shown in Figure 16. The indexing set includes 9 integer points forming the 3 × 3 grid {i -1, i, i + 1} × {j -1, j, j + 1} together with 4 indices {(i ± 1 2 , ), ( , j ± 1 2 )} corresponding to slanted dashed lines. To write the coherence condition in a more explicit (but not too bulky) form, we introduce the temporary notation
z ( ,j-1 2)
z (i-1,j-1) z (i,j) z (i+1,j+1)
z (i,j-1) z (i+1,j) z (i+ 1 2 , ) z (i+1,j-1)
.
Using this notation along with (5.11), the coherence condition (5.29) becomes 13 is obtained from the polygon P in Figure 14, and is therefore coherent by Theorem 5.11.
Figure 17 shows a non-coherent Cayley-Menger frieze z of order 6.
The following result shows that the coherence condition can be used as a basis for a rational recurrence. The left-hand side of the last equation is nothing but M(x).