Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 6 (2013) 419–433 Simplicial arrangements revisited Branko Grünbaum Department of Mathematics, University of Washington Seattle, WA 98195-4350, USA Received 13 March 2013, accepted 12 November 2013, published online 2 December 2013 Abstract In connection with the publication of the catalogue [7] of known simplicial arrange- ments of lines in the real projective plane, and the note [8] about small simplicial arrange- ments of pseudolines, several developments of these topics deserve to be mentioned. The present paper puts these results in perspective, and provides appropriate illustrations. Keywords: Simplicial arrangement. Math. Subj. Class.: 51M16 1 Simplicial arrangements of pseudolines Very significant new results on simplicial arrangements of pseudolines are contained in the publications [1] by L. W. Berman and [3] by M. Cuntz. We recall that an arrangement of pseudolines is a family of simple curves in the real projective plane such that each differs from a straight line in a finite part only, and every two have a single point in common at which they cross transversally. Throughout, we model or interpret the real projective plane as the extended Euclidean plane, with added points “at infinity” and the line “at infinity” (indicated by∞ if included in a diagram) consisting of all the points at infinity. Developing an idea of Eppstein [4], Berman described a method of construction of simplicial arrangements of pseudolines that has a very general applicability; moreover, it is very easily adapted for investigation of linear simplicial arrangements (that is, consisting of straight lines). To explain this approach, we start with the case of linear arrangements. (It needs to be noted that our explanation differs somewhat from Berman’s; we shall return to this later on.) Starting with the lines of mirror symmetry of a regular k-gon (k ≥ 2) centered at the origin, we select one of the 2k wedges (angular regions) determined by a pair of adjacent rays formed by these k lines. Considering these rays as mirrors, we shine a (laser) ray (or several such rays) into the wedge, and let it (them) reflect on the two mirrors according to the laws of reflection; this generates a beam (or several beams). As is easily seen be elementary considerations, the laser ray will reflect only a finite number of times, and the final fate of each beam will be one of the following: E-mail address: grunbaum@math.washington.edu (Branko Grünbaum) Copyright c© 2013 DMFA Slovenije 420 Ars Math. Contemp. 6 (2013) 419–433 (i) The final segment will be perpendicular to one of the reflecting rays; this includes what can be considered a limiting case, where the starting laser ray is aimed at the origin; in particular, it includes the case where the mirrors are part of the arrange- ment. (ii) The last part of the beam will be a ray shooting out of the wedge. In this case there are two distinct portions of the beam — the incoming part and the outgoing part. Each of these parts is simple (has no selfintersections) but the two parts may have intersections. Such beams are called two-ended. In case of pseudoline arrangements, the same conditions are assumed, except that: • The reflections on the mirrors do not follow rules of optics but are simply endpoints of pairs of segments or rays; • Each segment or ray may be a pseudosegment or pseudoray (the purple line in Fig- ure 1 is an example); • The orthogonality in (i) is waived, and each of the two parts in (ii) is assumed to be simple. See examples in Figures 1, 2, 3 and 4. In any case, if the beam(s) satisfy some additional conditions, as detailed in [1], repeated reflection in the 2k rays yields a linear or pseudoline simplicial arrangement. We call these kaleido arrangements, to distinguish them from more general simplicial arrangements. Ex- amples of the latter kind (non-kaleido) are A(14, 3), A(16, 7), and others, in the notation of [7], as well as the linear arrangement in Figure 7. In Berman’s paper [1], only beams satisfying (i) or its modification for pseudolines are accepted. Detailed discussion of the conditions that lead to linear simplicial arrangements (and of their pseudoline analogs) is presented in [1] for up to three beams other than the mirrors. It may be assumed that analogous investigations may determine conditions under which beams as defined here lead to simplicial arrangements, but I have not determined these conditions. The main reason for introducing condition (ii) in the definition of kaleido arrangements is that it leads to the following result: Theorem 1.1. Each simplicial arrangement, with k-fold dihedral symmetry such that all mirrors are lines of the arrangement, is a kaleido arrangement. The theorem is valid equally for linear arrangements and for pseudoline arrangements. Proof. Let all the beams be marked as far as possible, starting with the incoming rays; the claim is that there are no unmarked segments (of straight or pseudolines) or rays. If any such segment were present, its continuation by reflection in the mirrors would have to close on itself, which is impossible. In [3], Cuntz first enumerates simplicial arrangements of at most 27 pseudolines, and then investigates their stretchability, that is, the isomorphism to linear arrangements. The bound 27 is due to limitations of the computing power available, but even with this bound several notable results are obtained and several conjectures of the present writer are re- solved. B. Grünbaum: Simplicial arrangements revisited 421 Figure 1: The simplicial pseudoline arrangement B1(15) (adapted from [7]) is a kaleido arrangement with k = 2 and seven beams, one of which (red) is two-ended. The blue beam and the black ones are aimed at the origin, the purple one is a pseudoray, and the green and yellow ones are rays ending at mirrors. The mirrors are heavily drawn black lines. The enumeration of simplicial arrangements of pseudolines in [3] shows that all sim- plicial arrangements with at most 14 pseudolines are stretchable, thus confirming a con- jecture made in [8]. The computer-assisted enumeration in [3] uses “wiring diagrams” introduced Goodman in [5], and elaborated in Goodman and Pollack [6] and other publica- tions, together with innovative arguments to reduce the computational effort. The results, in particular, disprove another conjecture in [8]: Namely, that there is a single unstretchable simplicial arrangement of 15 pseudolines and four of 16 pseudolines. In the paper [3] Cuntz establishes that there are precisely two such arrangements with 15, and precisely seven with 16 pseudolines. The second 15-pseudoline arrangement is shown in Figures 7 and 8 in two forms. Figure 7 shows a “wiring diagram” of this pseudoline arrangement, modified from Figure 2 of [3]. The presentation in Figure 8 exhibits the 3-fold rotational symmetry of this arrangement in the extended Euclidean model of the real projective plane. The colors of the lines, and the labels, establish the isomorphism between the two diagrams in Figures 7 and 8. As no pseudolines in this example are mapped onto themselves by reflection, this is not a kaleido arrangement. 2 Simplicial arrangements of straight lines Another result of [3] is the discovery of four new simplicial arrangements of (straight lines. A short review of the historical background seems appropriate to explain the significance of Cuntz’s results. The first introduction of the concept of simplicial arrangements of lines occurred in a 422 Ars Math. Contemp. 6 (2013) 419–433 Figure 2: A kaleido simplicial arrangement B2(16) of 16 pseudolines, with k = 3 and with five beams, one of which (red) is two-ended. paper by Melchior [11] in 1941, but the paper did not seem to have any immediate effect. Close to thirty years later, the fact that Melchior found only few such arrangements piqued my curiosity. Over time, I found that there are three infinite families of simplicial arrange- ments, and a large number of nonsystematic, “sporadic” ones. Details were published in [9] in 1971; however, the presentation there was very concise, and not “user friendly”. More recently, a more detailed version was published [7]. Ninety sporadic arrangements were shown in [9], and this number remained unchanged in [7] although one arrangement was a duplicate and was deleted, and a new one was found. The presentation in [7] seems to have attracted more attention; one of the results was the paper by Cuntz [3]. In this paper Cuntz disproves the present author’s longstanding conjecture, first stated in [9] in 1971 and repeated in other publications, notably in [7], that the list of 90 sporadic simplicial arrangements is complete. Cuntz found that the catalog [7] is complete regarding simplicial arrangements with up to 27 lines, except for one missing arrangement for each of 22, 23, 24, and 25 lines. These arrangements, missed in [7], form a “family” in the sense that the one with the largest number of lines (25) leads to the other three by omitting 1, 2, or 3 lines. A version of this arrangement, denoted A(25, 8) by Cuntz, is shown in Figure 9. This presentation is geometrically more symmetric than the one in Figure 1 of [3]. The lines that may be omitted are shown heavily drawn, and it is obvious that they play the same role in the arrangement. Therefore only a single additional arrangement arises on omitting 1, 2, or 3 of them. As a consequence, there are now 94 known sporadic simplicial arrangements of lines. As a further consequence, it is now more open to question whether there exist additional such arrangements with 28 or more lines? An inspection of the twenty known such ar- B. Grünbaum: Simplicial arrangements revisited 423 Figure 3: A kaleido simplicial pseudoline arrangement B(22), with k = 3 and with six beams, two of which are two-ended. It is the arrangement shown in Figure 22 of [1] rangements (depicted in [7]) shows clearly that the experimental discovery becomes very complicated with this range of the number of lines. Hence there is a real possibility that some of these arrangements have not been found so far. It would seem very desirable — but challenging — to find ways of ascertaining the completeness of the list in [7] of such arrangements augmented by the four Cuntz arrangements, or the lack of it. 3 Additional remarks on simplicial arrangement of lines and pseudo- lines It is not clear how to decide from the combinatorial (or topological) description of a sim- plicial arrangement of pseudolines what is the minimal number of non-straight ones. Nor is it obvious how that number depends on the order of the automorphism group of the ar- rangement. Another question is whether it is possible to have different numbers of beams for the same arrangement; this possibility arises since the reflections are not strictly optical ones. A still different question is what are the restrictions on k, the number of single-ended, and the number of two-ended beams. In particular, for a given number d of two-ended beams, what is the minimal number s of single-ended ones – for linear arrangements, and for pseudoline ones. Figure 3 shows that with k = 3, and d = 2, as few as b = 4 single-ended beams are possible; the new arrangement A(22, 5) shows the same for a linear arrangement. As another example we have in Figure 11 a linear arrangement A(15, 1) with three two-ended beams and two single-ended beams. As shown by examples, a (linear) kaleido arrangement may have isomorphic realiza- 424 Ars Math. Contemp. 6 (2013) 419–433 Figure 4: The simplicial linear kaleido arrangement A(25, 5), in the notation of [7], with k = 8 and with four beams (two black, one red and one green). It is isomorphic to the second (pseudoline) arrangement in Figure 11 of [1]. Without the line at infinity it is the arrangement A(24, 2) of [6]. With the eight additional pseudolines (only one shown, in gray) generated by the gray beam it is a simplicial kaleido arrangement with 33 pseudolines. It should be noted that the mirrors of a kaleido arrangement need not be parts of lines of the arrangement. Examples of kaleido arrangements with such “virtual” mirrors are shown in Figures 5 and 6. tions with different geometric symmetry groups. The arrangement A(6, 1) shown in Fig- ure 12 provides an example. 4 Additional remarks on simplicial arrangement of lines and pseudo- lines While it is not hard to show that the simplicial pseudoline arrangements shown in the above figures are not stretchable, it is not clear to what extent they fail to be stretchable. More precisely, at least how many non-straight pseudolines have to be used in every diagram of these arrangements? In Figure 1 there are two such pseudolines, in Figure 2 there are three, and in Figure 6 there are six. In all these cases this seems to be the minimal number of non- straight pseudolines. The four non-stretchable simplicial arrangements of 16 pseudolines described in Figures 5 and 6 of [8] have at least 2, 3, 3, resp. 1 non-straight pseudolines. According to a private communication by Prof. Cuntz, the four non-stretchable simplicial arrangements of 16 pseudolines described in Figures 5 and 6 of [7] have 2, 1, 1, resp. 1 non- straight pseudolines; also, the three new non-stretchable arrangements of 16 pseudolines B. Grünbaum: Simplicial arrangements revisited 425 ∞ Figure 5: The simplicial linear kaleido arrangement A(7, 1), with k = 3 and two beams, reflected on two virtual mirrors. mentioned in [3] but not described there, have each at least 2 non-straight pseudolines. It is not clear how to decide from the combinatorial (or topological) description of a simplicial arrangement of pseudolines what is the minimal number of non-straight ones. Nor is it obvious how that number depends on the order of the automorphism group of the arrangement. The pseudoline arrangement B2(15) of 15 pseudolines is listed in Table 3 of 2] as having 6-fold cyclic symmetry. This seems hard to reconcile with Figure 8 above. There is a regrettable error in the catalog [7]. The arrangement shown there on page 14 and labeled A(16, 7) is, in fact, isomorphic with the arrangement A(16, 5) shown just above it. A correct diagram of A(16, 7) is shown in Figure 13. Simplicial arrangements of (straight) lines lead to a number of other problems. Not only is the question of the completeness of the list in [6], as augmented in [3], debatable — but it is conceivable that there are infinitely many arrangements missing. In fact, there seems to be no known family of lines in the plane that could not be imbedded into a simplicial arrangement of lines, or at least of pseudolines. Even the belief that there are no additional infinite families of simplicial arrangements of lines beyond the three families described in [9] and [7], has no credible supporting evi- dence. On the other hand, it could be argued that the available facts concerning simplicial pseudoline arrangements make the existence of additional infinite families of straight-line simplicial arrangements more believable. Here are these facts. Already in [10, p.51] it is mentioned that there are at least seven infinite families of simplicial pseudoline arrangements. But this was rendered insignifi- cant through the work of Berman. In [1] Berman described constructions of many infinite families of simplicial arrangements of pseudolines, based on reflecting kaleidoscopically suitable zigzags in an angle. It may well be that some of these lead to linear arrangements. The difference between the definition of kaleido arrangements used here, and the one proposed by Berman is not as large as might be thought. In most cases one could replace one two-ended beam by two single-ended ones by accepting that the end-segment does not 426 Ars Math. Contemp. 6 (2013) 419–433 Figure 6: The simplicial linear kaleido arrangement A(15, 2), with k = 4 and three beams, one of which is a mirror; one mirror is a virtual mirror. meet the mirror perpendicularly. On the other hand, our definition of kaleido arrangements could be extended to arrangements that are not simplicial. There seems to be no interesting information available about such more general arrangements, but the concept may well be worth investigating. Finally, another result of Cuntz and collaborators should be mentioned. They investi- gated a particular class of linear simplicial arrangements called “crystallographic arrange- ments”; their definition is too involved to be repeated here and readers are referred to [2] and the references given there. In contrast to the uncertainties discussed above, this class has the notable property that its members have been completely determined and classified. Acknowledgements The author is grateful for the helpful comments and suggestions by Professors L. W. Berman, M. Cuntz and J. Malkevitch, and a referee. He also acknowledges the stay at the Helen Riaboff Whiteley Center at the Friday Harbor Laboratories of the University of Washington, which provided the atmosphere and conditions that contributed to the work reported here. The author is indebted to Marko Boben for help in getting the paper to publication. B. Grünbaum: Simplicial arrangements revisited 427 Figure 7: A wiring diagram of the new simplicial arrangement B2(15) of 15 pseudolines found by Cuntz. Adapted from Figure 2 of [3]. 428 Ars Math. Contemp. 6 (2013) 419–433 Figure 8: A presentation of the simplicial arrangement B2(15) of 15 pseudolines in the extended Euclidean model of the real projective plane. The colors and labels of the pseu- dolines correspond to those in Figure 7. B. Grünbaum: Simplicial arrangements revisited 429 Figure 9: A version of the linear simplicial arrangement denoted A(25, 8) by Cuntz [3]. Any number of the three heavily drawn lines can be deleted, resulting in the simplicial arrangements labeled A(22, 5), A(23, 2), and A(24, 4) in [3]. 430 Ars Math. Contemp. 6 (2013) 419–433 Figure 10: Cuntz’s A(25, 8) simplicial arrangement of lines is a kaleido arrangement with k = 3; it has two two-ended beams (red and green), and five other beams. B. Grünbaum: Simplicial arrangements revisited 431 ∞ Figure 11: The linear simplicial kaleido arrangement A(15, 1) with k = 2 has five beams, three of which are two-ended. Figure 12: Isomorphic realizations with different symmetries. 432 Ars Math. Contemp. 6 (2013) 419–433 Figure 13: A correct diagram of the simplicial arrangement A(16, 7); the diagram shown in [7] and labeled A(16, 7) is not correct. B. Grünbaum: Simplicial arrangements revisited 433 References [1] L. W. Berman, Symmetric simplicial pseudoline arrangements, Electronic J. Combinatorics 15 (2008), #R13. [2] M. Cuntz, Crystallographic arrangements: Weyl grupoids and simplicial arrangements, Bull. London Math. Soc 43 (2011), 734–744. [3] M. Cuntz, Simplicial arrangements with up to 27 lines, Discrete Comput. Geom. 48 (2012), 682–701. [4] D. Eppstein, Simplicial pseudoline arrangements, http://11011110.livejournal. com/15749.html (Retrieved November 20, 2012). [5] J. E. Goodman, Proof of a conjecture of Burr, Grünbaum, and Sloane, Discrete Math. 32 (1980), 27–35. [6] J. E. Goodman and R. Pollack, Semispaces of configurations, cell complexes of arrangements. J. Comb. Theory A 37(1984), 257 293. [7] B. Grünbaum, A catalogue of simplicial arrangements in the real projective plane, Ars Math. Contemp. 2 (2009), 1–25. [8] B. Grünbaum, Small unstretchable simplicial arrangements of pseudolines, Geombinatorics 18 (2009), 153–160. [9] B. Grünbaum, Arrangements of hyperplanes, in: R. C. Mullin et al. (eds.), Proc. Second Louisiana Conf. on Combinatorics, Graph Theory and Computing, Louisiana State University, Baton Rouge 1971, Congressus Numerantium 3 (1971), 41–106. [10] B. Grünbaum, Arrangements and Spreads, CBMS Regional Conference Series in Mathematics, Number 10, Amer. Math. Soc., Providence, RI, 1972. [11] E. Melchior, Über Vielseite der projectiven Ebene, Deutsche Mathematik 5 (1941), 461–475.