Séminaire Lotharingien de Combinatoire 76 (2018), Article B76e

SL_{2}-TILINGS DO NOT EXIST IN HIGHER DIMENSIONS (MOSTLY)

LAURENT DEMONET, PIERRE-GUY PLAMONDON, DYLAN RUPEL, SALVATORE STELLA, AND PAVEL TUMARKIN

Abstract. We define a family of generalizations of SL_{2}-tilings to higher dimensions called ϵ-SL_{2}-tilings. We show that, in each dimension 3 or greater, ϵ-SL_{2}-tilings exist only for certain choices of ϵ. In the case that they exist, we show that they are essentially unique and have a concrete description in terms of odd Fibonacci numbers.

1. Introduction

An SL_{2}-tiling of the plane (see Definition 1) is, loosely speaking, obtained by assigning a positive integer to each integral point of the plane in such a way that all the 2 × 2 matrices formed by squares of adjacent entries have determinant 1. This definition was introduced by I. Assem, C. Reutenauer and D. Smith in [1], and was used by these authors to obtain explicit formulas describing cluster variables in cluster algebras of type A. SL_{2}-tilings can also be viewed as T -systems of type A_{1} (e.g. see [3, Remark 2.1]), where all variables are evaluated in positive integers.

The fact that SL_{2}-tilings of the plane even exist may be a little surprising in itself. On the contrary, already in [1] it was shown that there are infinitely many of them. More recently C. Bessenrodt, T. Holm and P. Jørgensen [2] classified all such tilings using triangulations of some suitable infinity-gon.

In this note, we introduce a higher-dimensional analogue of SL_{2}-tilings: integers will be assigned to points in ℤ^{n}, for n ≥ 2, and 2 × 2 matrices of adjacent entries in every slice will be required to satisfy a determinantal identity.

Although our definition seems like a natural generalization of the notion of SL_{2}-tilings, our main result (Theorem 12) states that, if n ≥ 3, then the objects it defines almost never exist.

2. SL_{2}-Tilings of the Plane

The aim of this note is to study higher-dimensional analogues of the following object.

Definition 1 ([1]). A bi-infinite array (a_{ij})_{i,j∈ℤ} with a_{ij} ∈ ℤ_{>0} is called an SL_{2}-tiling of ℤ^{2} if the entries satisfy the relation

(1)  a_{i,j+1}a_{i+1,j} − a_{ij}a_{i+1,j+1} = 1.

A bi-infinite array (b_{ij})_{i,j∈ℤ} with b_{ij} ∈ ℤ_{>0} is called an anti-SL_{2}-tiling of ℤ^{2} if the entries satisfy the relation

(2)  b_{i,j+1}b_{i+1,j} − b_{ij}b_{i+1,j+1} = −1.

The first author was partially supported by JSPS Grant-in-Aid for Young Scientist (B) 26800008.

The second author was partially supported by the French ANR grant SC3A (ANR-15-CE40-0004-01).

The notion of an anti-SL_{2}-tiling is not actually giving anything new as shown by the following lemma, however this notion will be useful for our considerations in higher dimensions.

Lemma 2. If (a_{ij})_{i,j∈ℤ} is an SL_{2}-tiling, then, by taking b_{ij} = a_{i,−j}, one obtains an anti-SL_{2}- tiling.

One should think of the difference between SL_{2}-tilings and anti-SL_{2}-tilings as viewing the lattice ℤ^{2} “from above” or “from below.” The following result from [1] was our starting point.

Theorem 3 ([1]). There exist infinitely many SL_{2}-tilings of ℤ^{2}.

In fact, it is shown in [1] that any admissible frontier of 1’s in the lattice can be completed into a unique SL_{2}-tiling. An interpretation of all possible SL_{2}-tilings was later given in [2] in terms of triangulations of a polygon with infinitely many vertices.

The following anti-SL_{2}-tiling will be relevant in our higher dimensional analysis. We will call it the staircase anti-SL_{2}-tiling of ℤ^{2}.

Example 4. Consider the anti-SL_{2}-tiling (a_{ij})_{i,j∈ℤ} of ℤ^{2} with a_{ij} = 1 if i + j ∈ {0, 1}. Using (2) and the well-known recursion F_{2r−1}F_{2r+3} = F_{2r+1}^{2} +1 (r ≥ 1) for the odd Fibonacci numbers, it is easy to see that

a_{ij} = \begin{cases}F_{2r−1} & if i + j = r ≥ 1; \\ F_{−2r+1} & if i + j = r ≤ 0; \end{cases}

where we number the Fibonacci numbers as:

\begin{matrix}F_{1} & F_{2} & F_{3} & F_{4} & F_{5} & F_{6} & F_{7} & ⋯ \\ 1 & 1 & 2 & 3 & 5 & 8 & 13 & ⋯ \end{matrix}

The following figure is a portion of this tiling. Note the bold frontier of 1’s; it is an “infinite staircase”.

1 1 2513 34 89 233 21 1 2513 34 89 521 1 2513 34 13 521 1 2513 34 13 521 1 25 89 34 13 521 1 2 233 89 34 13 521 1

610 233 89 34 13 521

3. SL_{2}-Tilings in Higher Dimensions

For a fixed integer n ≥ 2, denote vectors in ℤ^{n} by i = (i_{1} …, i_{n}) and let e_{k} be the k-th unit vector in the same lattice. A signature matrix is a symmetric n × n matrix ϵ = (ϵ_{kℓ}) with ϵ_{kℓ} = ±1 whenever k ≠ ℓ and ϵ_{kk} = −1.

Definition 5. Fix a signature matrix ϵ. An array (a_{i})_{i∈ℤ^{n}} with a_{i} ∈ ℤ_{>0} is called an ϵ-SL_{2}-tiling of ℤ^{n} if for all k and ℓ with k ≠ ℓ we have

(3)  a_{i+e_{ℓ}}a_{i+e_{k}} − a_{i}a_{i+e_{k}+e_{ℓ}} = ϵ_{kℓ}.

SL_{2}-TILINGS DO NOT EXIST IN HIGHER DIMENSIONS (MOSTLY) 3

The requirement on the diagonal entries of signature matrices might seem arbitrary right now because they do not play any role in the above definition; we will see later on that it is indeed a consistent choice.

In the case n = 2 there are only two possible signature matrices recovering the notions of SL_{2}-tilings and anti-SL_{2}-tilings of ℤ^{2}.

The following is a portion of an ϵ-SL_{2}-tiling of ℤ^{3} with all entries of ϵ equal to −1.

1 1 1 1 2 2 2 2 2 2 5 5 5 5 5 5 5 13 13 13 13 13 13 34 34 34 89

We will say that two n × n signature matrices ϵ and ϵ′ are equivalent if any ϵ-SL_{2}-tiling of ℤ^{n} can be made into an ϵ′-SL_{2}-tiling of ℤ^{n} by applying some linear transformation to its indices (i.e., elements of ℤ^{n}). By Lemma 2, all signature matrices with n = 2 are equivalent. The situation is more complicated when n ≥ 3 since not all signature matrices are equivalent. On the other hand, there are easy ways of constructing signature matrices equivalent to a given signature matrix ϵ.

Lemma 6. Let ϵ = (ϵ_{kℓ}) be any signature matrix and write ϵ^{(r)} for the matrix obtained from ϵ by changing the sign of all the entries in row r and column r, leaving the diagonal entries fixed. That is, ϵ^{(r)} = (ϵ′_{kℓ}) where ϵ′_{kℓ} = −ϵ_{kℓ} if exactly one of k and ℓ equals r and ϵ′_{kℓ} = ϵ_{kℓ} otherwise. If (a_{i})_{i∈ℤ^{n}} is an ϵ-SL_{2}-tiling, then, by taking b_{i} = a_{i−2i_{r}e_{r}}, one obtains an ϵ^{(r)} − SL_{2}-tiling.

Proof. Indeed, all the relations (3) not involving the index r are satisfied for (b_{i})_{i∈ℤ^{n}} because they are satisfied for (a_{i})_{i∈ℤ^{n}}. However, the relations involving the index r pick up a sign when passing from (a_{i})_{i∈ℤ^{n}} to (b_{i})_{i∈ℤ^{n}}, as desired. □

Definition 7. If ϵ is a signature matrix such that ϵ_{kℓ} = 1 (respectively ϵ_{kℓ} = −1 whenever k ≠ ℓ, we refer to an ϵ-SL_{2}-tiling as an SL_{2}-tiling (respectively anti-SL_{2}-tiling) of ℤ^{n}.

Lemma 8. Let n ≥ 3 and assume (a_{i})_{i∈ℤ^{n}} is either an SL_{2}-tiling or an anti-SL_{2}-tiling of ℤ^{n}. Then for any r ∈ ℤ the set {a_{i} : ∑_{j=1}^{n} i_{j} = r} consists of a single element.

Proof. We will show that the value of a_{i+e_{k}} depends only on a_{i}. This is enough to conclude our claim because any vector in ℤ^{n} whose entries sum up to a given integer r can be obtained from any other with the same property via “zig-zagging” up and down by simultaneously adding and subtracting unit vectors.

Pick any three distinct indices j, k, ℓ ∈ [1, n]. To prove our claim we compute a_{i+e_{j}+e_{k}+e_{ℓ}} in terms of a_{i}, a_{i+e_{j}}, a_{i+e_{k}}, a_{i+e_{ℓ}} in three different ways. For simplicity of notation we set

ϵ_{jk} = ϵ_{jℓ} = ϵ_{kℓ} = ϵ,  a_{i} = a,  a_{i+e_{j}} = x,  a_{i+e_{k}} = y,  a_{i+e_{ℓ}} = z.

The following picture will be useful.

z\frac{xz−ϵ}{a} x a\frac{yz−ϵ}{a} \frac{xy−ϵ}{a} y

Using (3) three times, we get

a_{i+e_{j}+e_{k}} = \frac{xy − ϵ}{a},  a_{i+e_{k}+e_{ℓ}} = \frac{yz − ϵ}{a},  a_{i+e_{j}+e_{ℓ}} = \frac{xz − ϵ}{a}.

Three more applications of (3) then lead to

a_{i+e_{j}+e_{k}+e_{ℓ}} = \{ \begin{matrix}\frac{a_{i+e_{j} +e_{k}} a_{i+e_{j} +e_{ℓ}}−ϵ}{a_{i+e_{j}}} = \frac{xyz}{a^{2}} − ϵ\frac{y+z}{a^{2}} − ϵ\frac{a^{2}−ϵ}{a^{2}x} \\ \frac{a_{i+e_{j} +e_{k}} a_{i+e_{k}+e_{ℓ}}−ϵ}{a_{i+e_{k}}} = \frac{xyz}{a^{2}} − ϵ\frac{x+z}{a^{2}} − ϵ\frac{a^{2}−ϵ}{a^{2}y} \\ \frac{a_{i+e_{j} +e_{ℓ}}a_{i+e_{k}+e_{ℓ}}−ϵ}{a_{i+e_{ℓ}}} = \frac{xyz}{a^{2}} − ϵ\frac{x+y}{a^{2}} − ϵ\frac{a^{2}−ϵ}{a^{2}z} \end{matrix}

It follows that \frac{x−y}{a^{2}} = \frac{a^{2}−ϵ}{a^{2}x} − \frac{a^{2}−ϵ}{a^{2}y} or (xy + a^{2} − ϵ)(x − y) = 0. But xy + a^{2} − ϵ ≥ 1 since a, x, y ≥ 1, hence x = y. Similarly y = z. The result then follows by iterating on all possible triples of distinct indices j, k, ℓ. □

We now come to our first main result: in dimension n, an “infinite staircase” of 1’s yields the only possible anti-SL_{2}-tiling.

Theorem 9. For n ≥ 3, there exists a unique (up to translation) anti-SL_{2}-tiling of ℤ^{n}. Any of its “two-dimensional slices” obtained by fixing all but two of the entries of i is a translation of the staircase anti-SL_{2}-tiling of ℤ^{2} from Example 4. In particular, all the integers appearing are odd Fibonacci numbers.

Proof. Assume (a_{i})_{i∈ℤ^{n}} is an anti-SL_{2}-tiling of ℤ^{n}. Pick i with a_{i} minimal. Applying (3), we get

a_{i+e_{1}}a_{i−e_{2}} = a_{i}a_{i+e_{1}−e_{2}} + 1 = a_{i}^{2} + 1,

where we used Lemma 8 in the last equality. If a_{i} > 1, this implies a_{i+e_{1}} < a_{i} or a_{i−e_{2}} < a_{i}, contradicting minimality, so we must have a_{i} = 1. In turn, again leveraging Lemma 8, this implies {a_{i+e_{k}}, a_{i−e_{k}}} = {1, 2} for any k ∈ [1, n]. Without loss of generality (by replacing i by i+e_{1} if needed) we will assume a_{i+e_{k}} = 2 and ∑_{j=1}^{n} i_{j} = 1. Then, applying (3) repeatedly, we see that a_{i}′ with ∑_{j=1}^{n} i′_{j} = r ≥ 1 is exactly the r^{th} odd Fibonacci number F_{2r−1} (see Example 4). Similarly one sees that a_{i}′ with ∑_{j=1}^{n} i′_{j} = r ≤ 0 is the odd Fibonacci number F_{−2r+1}. □

Proposition 10. There does not exist any SL_{2}-tiling of ℤ^{n} for n ≥ 3.

Proof. Since any 3-dimensional slice of an SL_{2}-tiling of ℤ^{n} is an SL_{2}-tiling of ℤ^{3}, it suffices to show that there is no SL_{2}-tiling of ℤ^{3}. Assume (a_{i})_{i∈ℤ^{3}} is an SL_{2}-tiling of ℤ^{3}. Pick i with a_{i} minimal. Applying (3), we get

a_{i+e_{1}}a_{i−e_{2}} = a_{i}a_{i+e_{1}−e_{2}} − 1 = a_{i}^{2} − 1,

where we used Lemma 8 in the last equality. But this implies a_{i+e_{1}} < a_{i} or a_{i−e_{2}} < a_{i}, contradicting minimality. □ Corollary 11. For n = 3, there are precisely 4 signature matrices ϵ for which there exists an ϵ-SL_{2}-tiling. For such ϵ, this ϵ-SL_{2}-tiling is unique (up to translation). More precisely, an ϵ-SL_{2}-tiling of ℤ^{3} exists if and only if ϵ_{12}ϵ_{13}ϵ_{23} = −1. Proof. The claim follows immediately from the observation that any signature matrix for n = 3 is either one of the two satisfying ϵ_{12} = ϵ_{13} = ϵ_{23} or is obtained from one of these with a single application of Lemma 6. □

We are finally ready to classify all ϵ-SL_{2}-tilings for any n ≥ 3. Theorem 12. For n ≥ 3, there are precisely 2^{n−1} signature matrices ϵ for which there exists an ϵ-SL_{2}-tiling of ℤ^{n}. They are precisely the signature matrices obtainable from the anti-SL_{2}-signature matrix by repeated application of Lemma 6. Whenever an ϵ-SL_{2}-tiling exists, it is unique up to translation. Proof. Let (a_{i})_{i∈ℤ^{n}} be an ϵ-SL_{2}-tiling of ℤ^{n}. Fixing all but any three distinct entries of i gives an ϵ′-tiling of ℤ^{3} whose signature matrix ϵ′ is the submatrix of ϵ with the corresponding rows and columns. Therefore, it follows from Corollary 11 that we have an inclusion E ⊂ E′, where E is the set of n × n signature matrices ϵ which admit an ϵ-SL_{2}-tiling, and E′ is the set of n × n signature matrices ϵ satisfying ϵ_{jk}ϵ_{kℓ}ϵ_{jℓ} = −1 for any triple of distinct indices j, k, ℓ.

Any row (or equivalently any column) of a matrix ϵ in E′ uniquely determines all the remaining entries of ϵ, moreover all possible choices of entries in this fixed row (or equivalently column) are allowed. Indeed, assume for the sake of clarity that the matrix ϵ has been computed using row 1, then

ϵ_{jk}ϵ_{kℓ}ϵ_{jℓ} = (−ϵ_{1k}ϵ_{1j})(−ϵ_{1k}ϵ_{1ℓ})(−ϵ_{1j}ϵ_{1ℓ}) = −1.

Therefore E′ is in bijection with {±1}^{n−1} and #E′ = 2^{n−1}.

Using Lemma 6, there is an action of (ℤ/2ℤ)^{n−1} on E given by ϵ ↦ ϵ^{(r)} for 1 ≤ r ≤ n − 1. This action is free; indeed the only element of (ℤ/2ℤ)^{n−1} leaving invariant the last column of any given matrix of E is the identity.

Due to Theorem 9, E is not empty, and so we compute #E ≥ 2^{n−1} = #E′ ≥ #E and deduce that E = E′.

The uniqueness claim also follows immediately from Corollary 11 by fixing all but any three distinct entries of i. □ Remark 13. It is now clear why we choose the diagonal entries of ϵ to be equal to −1: any ϵ-SL_{2}-tiling consists of odd Fibonacci numbers and (3) is satisfied also for k = ℓ.

Acknowledgements

These results were obtained while we were taking part in the Conference on Cluster Algebras and Representation Theory at the KIAS in Seoul, South Korea. We would like to thank the organizers of that meeting for the stimulating environment they provided.

We are especially grateful to Peter Jørgensen for his very inspiring talk at the same conference: the results presented here are the content of the exciting discussions he sparked.

References

[1] Ibrahim Assem, Christophe Reutenauer and David Smith, Friezes, Adv. Math. 225 (2010), 3134–3165.

[2] Christine Bessenrodt, Thorsten Holm and Peter Jørgensen, All SL_{2}-tilings come from infinite triangulations, preprint, arχiv:1603.09103.

[3] Philippe Di Francesco and Rinat Kedem, The solution of the quantum A_{1} T -system for arbitrary boundary, Commun. Math. Phys. 313 (2012), 329–350.

(Laurent Demonet) Graduate School of Mathematics, Nagoya University, Furocho, Chikusaku, 464-8602 Nagoya, Japan

Email address: Laurent.Demonet@normalesup.org

(Pierre-Guy Plamondon) Laboratoire de Mathématiques d’Orsay, Univ. Paris-Sud, CNRS, Univ. Paris-Saclay, 91405 Orsay, France.

Email address: pierre-guy.plamondon@math.u-psud.fr

(Dylan Rupel) Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556, USA.

Email address: drupel@nd.edu

(Salvatore Stella) INdAM - Marie Curie Actions fellow, Università “La Sapienza”, Roma, Italy.

Email address: stella@mat.uniroma1.it

(Pavel Tumarkin) Department of Mathematical Sciences, Durham University, South Road, Durham, DH1 3LE, UK.

Email address: pavel.tumarkin@durham.ac.uk