Metod Saniga
email: msaniga@astro.sk

Hans Havlicek
email: havlicek@geometrie.tuwien.ac.at

Frédéric Holweck
email: frederic.holweck@utbm.fr

Michel Planat
email: michel.planat@femto-st.fr

Petr Pracna
email: pracna@jh-inst.cas.cz

Veldkamp-Space Aspects of a Sequence of Nested Binary Segre Varieties

Keywords:

2) be a Segre variety that is N -fold direct product of projective lines of size three. Given two geometric hyperplanes H ′ and H ′′ of S (N ) , let us call the triple {H ′ , H ′′ , H ′ ∆H ′′ } the Veldkamp line of S (N ) . We shall demonstrate, for the sequence 2 ≤ N ≤ 4, that the properties of geometric hyperplanes of S (N ) are fully encoded in the properties of Veldkamp lines of S (N -1) . Using this property, a complete classification of all types of geometric hyperplanes of S (4) is provided. Employing the fact that, for 2 ≤ N ≤ 4, the (ordinary part of) Veldkamp space of S (N ) is P G(2 N -1, 2), we shall further describe which types of geometric hyperplanes of S (N ) lie on a certain hyperbolic quadric Q + 0 (2 N -1, 2) ⊂ P G(2 N -1, 2) that contains the S (N ) and is invariant under its stabilizer group; in the N = 4 case we shall also single out those of them that correspond, via the Lagrangian Grassmannian of type LG(4, 8), to the set of 2295 maximal subspaces of the symplectic polar space W(7, 2).

Introduction

Algebraic varieties that are Cartesian products of two or more projective spaces of the same or different dimensions were introduced as early as 1891 by Corrado Segre [START_REF] Segre | Sulle varietà che rappresentano le coppie di punti di due piani o spazi[END_REF] who, however, considered only the 'classical' case, viz. the field of real or complex numbers. Some seventy years later, Benjamino Segre [START_REF] Segre | Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane[END_REF] showed that the definition of Segre varieties, as well as a majority of their properties, carry over to other fields, in particular over finite (Galois) fields (see also [START_REF] Melone | Spazi pseudoprodotto e varietà di C. Segre[END_REF]). The past decade witnessed an increased interest in the topic, and this not only from a pure mathematical point of view (e. g., [START_REF] Bader | Partitioning Segre varieties and projective spaces[END_REF][START_REF] Landsberg | The border rank of the multiplication of 2 × 2 matrices is seven[END_REF][START_REF] Landsberg | On the ideals and singularities of secant varieties of Segre varieties[END_REF][START_REF] Lavrauw | Orbits of the stabiliser group of the Segre variety product of three projective lines[END_REF][START_REF] Coolsaet | On the classification of nonsingular 2 × 2 × 2 × 2 hypercubes[END_REF][START_REF] Shaw | Aspects of the Segre variety S 1,1,1[END_REF][START_REF] Shaw | Tetrads of lines spanning PG(7, 2)[END_REF]), but also due to important quantum physical applications. The latter case is remarkable in that alongside classical Segre varieties, and associated Segre maps, which provide a setup for geometrical construction of concurrence, one of principal measures of quantum entanglement (e. g., [START_REF] Brody | Geometric quantum mechanics[END_REF][START_REF] Miyake | Classification of multipartite entangled states by multidimensional determinants[END_REF][START_REF] Heydari | Complex multi-projective variety and entanglement[END_REF][START_REF] Heydari | General pure multipartite entangled states and the Segre variety[END_REF][START_REF] Holweck | Geometric descriptions of entangled states by auxiliary varieties[END_REF]), we also encounter Segre varieties defined over the smallest Galois field, which are intimately linked with the issue of quantum contextuality and the so-called black-hole-qubit correspondence through the properties of certain generalized multi-qubit Pauli groups (e. g., [START_REF] Planat | On the Pauli graph of N-qudits[END_REF][START_REF] Lévay | Black hole entropy and finite geometry[END_REF][START_REF] Holweck | A notable relation between N -qubit and 2 N -1 -qubit Pauli groups via binary LGr(N, 2N )[END_REF]). Interestingly enough, these 'quantum contextual' finite Segre varieties are found to lie within the family defined as S (N ) ≡ P G(1, 2)×P G(1, 2)ו • •×P G(1, 2) (N times), where P G(1, 2) represents the smallest projective line, being always contained/embedded in a distinguished finite geometry/point-line incidence structure.

The first physically relevant type of finite Segre variety is S [START_REF] Segre | Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane[END_REF] . It lives in the symplectic polar space W(3, 2), which underlies the commutation relations between the elements of twoqubit generalized Pauli group [START_REF] Planat | On the Pauli graph of N-qudits[END_REF][START_REF] Havlicek | Factor-group-generated polar spaces and (multi)qudits[END_REF]. The S (2) itself, being isomorphic to the smallest slim generalized quadrangle GQ(2, 1), is the geometry behind what is known as a Mermin magic square [START_REF] Mermin | Hidden variables and the two theorems of John Bell[END_REF]. It represents a set of nine observables placed at the vertices of a 3 × 3 grid and forming six maximum sets of pairwise commuting elements that lie along three horizontal and three vertical lines, each observable thus pertaining to two such sets. The observables are selected in such a way that the product of their triples in five of the six sets is +I, whilst in the remaining set it is -I, I being the identity matrix. Another prominent type of the Segre variety is S [START_REF] Melone | Spazi pseudoprodotto e varietà di C. Segre[END_REF] , which enters the quantum informational game in a more refined disguisenamely through its dual S ⋆

(3) . The latter lives in the generalized quadrangle of type GQ(2, 4), one of the key finite geometries in the context of the black-hole-qubit correspondence [START_REF] Lévay | Black hole entropy and finite geometry[END_REF]. GQ [START_REF] Segre | Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane[END_REF][START_REF] Bader | Partitioning Segre varieties and projective spaces[END_REF] encodes completely the entropy formula of black holes, or black strings, in certain D = 5 supergravity theories. This entropy formula features 27 charges and 45 terms of three charges each that correspond, respectively, to 27 points and 45 lines of GQ [START_REF] Segre | Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane[END_REF][START_REF] Bader | Partitioning Segre varieties and projective spaces[END_REF]. Take any three pairwise disjoint GQ(2, 1)s in GQ(2, 4) and remove their lines; what is left is a copy of S ⋆

(3) . Hence, our S ⋆ (3) represents an interesting sub-geometry of the entropy formula that still incorporates all 27 charges, but picks up only a particular subset of 27 terms out of the totality of 45 ones.

These findings are indicative of the fact that also the next type of Segre variety in the hierarchy, S (4) , is -up to duality -likely to be of relevance for quantum physics and thus deserves a closer look at. To perform such an inspection, we shall employ the notion of Veldkamp space of a point-line incidence geometry [START_REF] Buekenhout | Diagram Geometry: Related to Classical Groups and Buildings[END_REF]. This important concept has already been utilized to analyze the structure of W(3, 2) [START_REF] Saniga | The Veldkamp space of two-qubits[END_REF] and higher-rank symplectic polar spaces [START_REF] Vrana | The Veldkamp space of multiple qubits[END_REF] where it helped to reveal some finer traits of the structure of multiple-qubit Pauli groups, that of GQ(2, 4) [START_REF] Saniga | The Veldkamp space of GQ(2, 4)[END_REF] where it led to a deeper understanding of distinguished truncations of the above-described black-hole entropy formula, as well as that of the Segre variety S (3) [START_REF] Green | The Veldkamp space of the smallest slim dense near hexagon[END_REF]. Our reasoning will heavily rest on the results of the last-mentioned reference, where properties of both geometric hyperplanes and Veldkamp lines of S (3) were treated in much detail.

The paper is organized as follows. Section 2 highlights basic concepts, symbols and notation to be employed. In Section 3, Subsecs. 3.1 to 3.3, we shall describe, for the sequence 2 ≤ N ≤ 4, a diagrammatical recipe of how to ascertain the properties of Veldkamp points of S (N ) if we know the properties of Veldkamp lines of S (N -1) ; using this recipe, a complete classification of geometric hyperplanes of S (4) will be arrived at. In addition, for each S (N ) in the above-given sequence it shall be shown which types of its geometric hyperplanes lie on the unique hyperbolic quadric

Q + 0 (2 N -1, 2) ⊂ P G(2 N -1, 2
) that contains the S (N ) and is invariant under its stabilizer group. Finally, Section 4 will be devoted to a brief summary of the main findings as well as to pointing out certain resemblance between our 'generalized' concept of Veldkmap space and the notion of projective space defined over a ring.

Basic concepts, symbols and notation

In this section we shall make a brief inventory of basic concepts, symbols and notation employed in the sequel.

Our starting point is a point-line incidence structure C = (P, L, I) where P and L are, respectively, sets of points and lines and where incidence I ⊆ P ×L is a binary relation indicating which point-line pairs are incident (see, e. g., [START_REF] Shult | Points and Lines: Characterizing the Classical Geometries[END_REF]). The dual of a point-line incidence structure is the structure with points and lines exchanged, and with the reversed incidence relation. In what follows we shall encounter only specific point-line incidence structures where every line has the same number of points, every point is incident with the same number of lines and any two distinct points are joined by at most one line. A geometric hyperplane of C = (P, L, I) is a proper subset of P such that a line from C either lies fully in the subset, or shares with it only one point. Given a hyperplane H of C, one defines the order of any of its points as the number of lines through the point that are fully contained in H; a point of H is called deep if all the lines passing through it are fully contained in H. If C possesses geometric hyperplanes, then one can define the Veldkamp space of C as follows [START_REF] Buekenhout | Diagram Geometry: Related to Classical Groups and Buildings[END_REF]: (i) a point of the Veldkamp space is a geometric hyperplane of C and (ii) a line of the Veldkamp space is the collection

H ′ H ′′ of all geometric hyperplanes H of C such that H ′ ∩ H ′′ = H ′ ∩ H = H ′′ ∩ H or H = H ′ , H ′′ ,
where H ′ and H ′′ are distinct geometric hyperplanes. There exists a wide family of point-line incidence structures, including also those to be discussed below, where each line has three points and where a line of the Veldkamp space can equivalently be defined as {H ′ , H ′′ , H ′ ∆H ′′ }; here, the symbol ∆ stands for the symmetric difference of the two geometric hyperplanes and an overbar denotes the complement of the object indicated. Occasionally, H ′ ∆H ′′ will be called the Veldkamp sum of hyperplanes H ′ and H ′′ . To meet our needs, we shall use a slightly generalized notion of the Veldkamp space of C, V(C), which also includes C as the extraordinary geometric hyperplane and which features extraordinary Veldkamp lines, the latter being of type {H, H, C}. Moreover, we shall reserve the symbol ord-V(C) for the 'ordinary' part of V(C), i. e. that devoid of the extraordinary hyperplane and all the Veldkamp lines passing through it.

Next, let V (d + 1, q), d ≥ 1, denote a rank-(d + 1) vector space over the Galois field GF (q), q being a power of a prime. Associated with this vector space is a d-dimensional projective space over GF (q), P G(d, q), whose points, lines, planes,. . ., hyperplanes are rank-one, rank-two, rank-three,. . ., rank-d subspaces of V (d + 1, q). A quadric in P G(d, q), d ≥ 1, is the set of points whose coordinates satisfy an equation of the form d+1 i,j=1 a ij x i x j = 0, where at least one a ij = 0. Up to transformations of coordinates, there is one or there are two distinct kinds of non-singular quadrics in P G(d, q) according as d is even or odd, namely [START_REF] Hirschfeld | General Galois Geometries[END_REF]: Q(2N, q), the parabolic quadric formed by all points of P G(2N, q) satisfying the standard equation

x 1 x 2 + • • • + x 2N -1 x 2N + x 2 2N +1 = 0; Q -(2N -1, q)
, the elliptic quadric formed by all points of P G(2N -1, q) satisfying the standard equation

f (x 1 , x 2 ) + x 3 x 4 + • • • + x 2N -1 x 2N = 0,
where f is irreducible over GF(q); and Q + (2N -1, q), the hyperbolic quadric formed by all points of P G(2N -1, q) satisfying the standard equation

x 1 x 2 + x 3 x 4 + • • • + x 2N -1 x 2N = 0; where N ≥ 1.
In this paper we shall only be concerned with hyperbolic quadrics, in particular with those of q = 2; each such quadric is found to accommodate as many as (2 N -1 + 1)(2 N -1) points. Given a P G(2N -1, q) that is endowed with a symplectic form, the symplectic polar space W(2N -1, q) in P G(2N -1, q) is the space of all totally isotropic subspaces with respect to the symplectic form [START_REF] Cameron | Projective and Polar Spaces[END_REF], with its maximal totally isotropic subspaces, also called generators, having dimension N -1. For q = 2 this polar space contains |P G(2N -1, 2)| = 2 2N -1 = 4 N -1 points and (2 + 1)(2 2 + 1) • • • (2 N + 1) generators.

Last but not least, there comes a finite Segre variety [START_REF] Hirschfeld | General Galois Geometries[END_REF] S d1,d2,...,dN (q) ≡ P G(d 1 , q) × P G(d 2 , q) × . . . × P G(d N , q), whose simplest possible form, namely S 1,1,...,1 (2) ≡ S (N ) , will be of central interest to us. An easy count yields that S (N ) = P G(1, 2) × S (N -1) , when viewed as an abstract point-line incidence structure, has 3 N points and N 3 N -1 lines, with three points per a line and N lines through a point. 3 From the Veldkamp lines of S (N -1) to the Veldkamp points of S (N ) (2 ≤ N ≤ 4)

S (2) and its Veldkamp space

The Segre variety S (2) is a point-line incidence structure having 9 points and 6 lines, with two lines per a point. Using its diagrammatical representation as a 3 × 3 grid, one can readily check Figure 1: A diagrammatic representation of the types of geometric hyperplanes of S [START_REF] Segre | Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane[END_REF] . The number attached to a subfigure indicates how many distinct copies of a given hyperplane one gets by rotating the subfigure around its center. The top row illustrates all 9 copies of type one hyperplane, the middle row all 6 copies of type two hyperplane and, for the sake of completeness, the bottom row shows the extraordinary hyperplane. The encircled bullets in the top row denote deep points. (Obviously, all the nine points of the extraordinary hyperplane are deep (not indicated).)

that it features two distinct kinds of geometric hyperplanes, which are depicted in Figure 1 and whose properties are summarized in Table 1. In the latter, the first column gives the type ('Tp') of a hyperplane, which is followed by the number of points ('Ps') and lines ('Ls') it contains, and the number of points of given order. The next two columns tell us about how many of 6 lines (S (1) 's) are fully located ('D') in the hyperplane and/or share with it a single point (which is the only ordinary hyperplane of S (1) ). The VL-column lists the types of Veldkamp lines of S (1) we get by projecting a hyperplane of the given type into a line of the S (2) . Finally, for each hyperplane type we give its cardinality ('Crd'). A brief inspection of Figure 1 shows that, given a point of S (2) , a type one hyperplane consists of the point and all the points that are not at maximum distance1 from it; in the language of near polygons (e. g., [START_REF] Bruyn | Near Polygons[END_REF]), this is usually termed a singular hyperplane. On the other hand, a type two hyperplane represents a maximum set of mutually non-collinear points, often referred to as an ovoid.

In order to get a deeper insight into the nature of the two (ordinary) types of geometric hyperplanes of S (2) , we shall have a look at Veldkamp lines of S [START_REF] Segre | Sulle varietà che rappresentano le coppie di punti di due piani o spazi[END_REF] . These are also of two different kinds, which we shall call ordinary (abbreviated as 'ord' in Table 1) and extraordinary ('ext') ones. The Veldkamp line of ordinary type is just a single one, namely that comprising all the three points of S (1) -as portrayed in Figure 2, top left, where the points are distinguished by different color. A Veldkamp line of extraordinary type features the extraordinary hyperplane (that is the whole S (1) ) and a point counted twice -see Figure 2, bottom left; clearly, there are three of them. Now, S (2) is endowed with two different spreads of lines, i. e. sets of three pairwise disjoint lines that partition the point-set of S (2) ; in our diagrammatical representation of S (2) , one spread consists of three 'horizontal' lines and the other comprises three 'vertical' lines. Let us take a geometric hyperplane of type two and project its points along the three lines of one spread onto a line of the second spread. If we keep the distinction between the three lines of the second spread, what we get is nothing but the ordinary Veldkamp line of S (1) . This fact is portrayed in Figure 2, top, where the projection is made along the lines of the 'vertical' spread. Making the same projection with a type one hyperplane results in an extraordinary Veldkamp line of S (1) -see Figure 2, bottom part. We further see that six different S (2) -hyperplanes of type two are projected into one and the same ordinary Veldkamp line of S (1) , whereas it is three distinct S (2) -hyperplanes of type one that map into the same extraordinary Veldkamp line of S [START_REF] Segre | Sulle varietà che rappresentano le coppie di punti di due piani o spazi[END_REF] . Reversing our reasoning, by blowing up S (1) to S (2) each of the three extraordinary Veldkamp lines of S (1) generates three geometric hyperplanes of S (2) of type one, whilst the single ordinary one gives rise to all the six hyperplanes of type two. We have thus explicitly demonstrated the fact that the types of geometric hyperplanes, that is Veldkamp points, of the Segre variety S (2) , as well as their cardinalities, can be fully derived/recovered from the properties of Veldkamp lines of the Segre variety of the preceding rank, S (1) . One of the main foci of this paper is to justify a conjecture that this remarkable relation between Veldkamp points of S (N ) and Veldkamp lines of S (N -1) holds, in fact, for any positive integer N ≥ 2 by illustrating its properties in sufficient detail on the two subsequent cases, viz. N = 3 and N = 4.

It is now obvious that in order to tackle properly the next (N = 3) case in the hierarchy, we have to ascertain how many types of Veldkamp lines of S [START_REF] Segre | Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane[END_REF] we have and what their properties are. Using our descriptive representation of geometric hyperplanes of S (2) (Figure 1), this is quite a straightforward task. For ordinary Veldkamp lines the corresponding information is collected in Table 2 and, in a visual form, in Figure 3, top. There are four types of them and their total number is 35; type one and type four are so-called homogenous Veldkamp lines as they both feature hyperplanes of the same type. As for extraordinary Veldkamp lines, we find only two types, namely the extraordinary hyperplane and H 1 counted twice (type I) and the extraordinary hyperplane and H 2 counted twice (type II), totaling to 15 -as depicted in the upper part of Figure 4, left and right, respectively. Table 2: The types of ordinary Veldkamp lines of S [START_REF] Segre | Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane[END_REF] . The first column gives the type, the next two columns tell us about how many points and lines belong to all the three geometric hyperplanes a line of the given type consists of, then we learn about the line's composition and, finally, the last column lists cardinalities for each type. We shall finalize this section by observing that the ordinary part of Veldkamp space of S (2) , ord-V(S (2) ), features 15 points (ordinary geometric hyperplanes of S (2) ) and 35 lines (ordinary Veldkamp lines of S (2) ), being isomorphic to P G(3, 2). The nine hyperplanes of type one then correspond to the nine points lying on a hyperbolic quadric

Core

Q + 0 (3, 2) ⊂ P G(3, 2).

S (3) and its Veldkamp space

The Segre variety S (3) , known also as the smallest slim dense near hexagon [START_REF] Bruyn | Near Polygons[END_REF] or the Gray configuration [START_REF] Marušič | The genus of the Gray graph is seven[END_REF], is a point-line incidence structure having 27 points and the same number of lines, with three points per line and the same number of lines through a point. It possesses nine S (2) 's, arranged into three distinct triples of pairwise disjoint members, each of which partitions the point-set. Analogously, S (3) contains three distinguished spreads of lines; a distinguished spread of lines is a set of nine mutually skew lines such that each line is incident with all the three S (2) 's from a given triple. 2 As already mentioned, S (3) , as an abstract point-line incidence Figure 5: A diagrammatic 3 × 3 × 3 grid representation of the types of (ordinary) geometric hyperplanes of S (3) (after [START_REF] Green | The Veldkamp space of the smallest slim dense near hexagon[END_REF], Figure 2). As in Figure 1, deep points are encircled. Note that one of the seven deep points of a type-one hyperplane stands on a different footing than the others, as each line passing through it features deep points; we shall call it the deepest point. structure, was thoroughly analyzed in [START_REF] Green | The Veldkamp space of the smallest slim dense near hexagon[END_REF] where it was found that ord-V(S (3) ) ∼ = P G(7, 2). As P G(7, 2) has 255 points and 10 795 lines (see, e. g., [START_REF] Hirschfeld | General Galois Geometries[END_REF]), S (3) features a total of 255 (ordinary) geometric hyperplanes and 10 795 (ordinary) Veldkamp lines. 1, the first column gives the type ('Tp') of a hyperplane, which is followed by the number of points ('Ps') and lines ('Ls') it contains, and the number of points of given order. The next three columns tell us about how many of 9 S (2) 's are fully located ('D') in the hyperplane and/or share with it a hyperplane of type H 1 or H 2 (see Table 1). The VL-column lists the types of (ordinary and extraordinary) Veldkamp lines of S (2) we get by projecting a hyperplane of the given type into an S (2) along the lines of all three distinguished spreads. Finally, for each hyperplane type we give its cardinality ('Crd'), the corresponding large orbit of 2 × 2 × 2 arrays over GF (2) ('BS') taken from Table 3 of [START_REF] Bremner | Canonical forms of 2 × 2 × 2 and 2 × 2 × 2 × 2[END_REF], and its weight, or rank in the language of [START_REF] Bremner | Canonical forms of 2 × 2 × 2 and 2 × 2 × 2 × 2[END_REF] ('W'). Let us first focus briefly on geometric hyperplanes of S (3) , referring the interested reader to [START_REF] Green | The Veldkamp space of the smallest slim dense near hexagon[END_REF] (as well as to Sec. 6 of [START_REF] Havlicek | On invariant notions of Segre varieties in binary projective spaces[END_REF]) for more details. Disregarding the extraordinary one, there are five distinct types of them, their basic properties being listed in Table 3 and their representatives depicted in Figure 5; we note that a type one hyperplane is the singular one, whereas that of type five is an ovoid. Type one hyperplanes, as already pointed out in [START_REF] Green | The Veldkamp space of the smallest slim dense near hexagon[END_REF], play a distinguished role in the sense that a hyperplane of any other type can be expressed as the Veldkamp sum of several type-one hyperplanes; the smallest such number is then called the weight of the hyperplane. A type two hyperplane also differs from the rest in being a blow-up of two different kinds of Veldkamp lines of S (2) , viz. those of type 1 ordinary (Figure 3, leftmost) and those of type II extraordinary (Figure 4, right), with its 36/18 copies originating from the former/latter process; hyperplanes of any of the remaining four types originate -as it can easily be verified from the corresponding parts of Figure 3 and Figure 4 -from S (2) -Veldkamp-lines of the same type.

Points of

Regarding hyperplanes as points of the P G(7, 2) ( ∼ = ord-V(S (3) )), it can be demonstrated that those points that correspond to hyperplanes of type one, two and four, and whose number totals to 135, all lie on a certain Q + 0 (7, 2) ⊂ P G(7, 2); note that these are exactly the three types whose members feature points of maximum order. It is also worth mentioning here that these three hyperplane types in their totality correspond to the image, furnished by the Lagrangian Grassmannian of LG(3, 6) type, of the set of 135 maximal subspaces of W(5, 2) [START_REF] Holweck | A notable relation between N -qubit and 2 N -1 -qubit Pauli groups via binary LGr(N, 2N )[END_REF][START_REF] Lévay | Grassmannian connection between three-and four-qubit observables, Mermin's contextuality and black holes[END_REF]. Table 4: The types of ordinary Veldkamp lines of S (3) , in the notation set up in Table 2. A slightly modified reproduction of Table 2 from [START_REF] Green | The Veldkamp space of the smallest slim dense near hexagon[END_REF], where the reader is referred to for detailed explanation of the meaning of all subscripts associated to some cardinalities of core's points and lines (columns two and three).

Core

0 - - 1 2 - 324 37 3 1 - - - 3 - 54 38 3 [1] 0 - 1 - - 2 54 39 3 [0] 0 - - 1 1 1 216 40 2 0 - - - 2 1 108 41 0 0 - - - - 3 4
Next, let us have an informative look at the (ordinary) Veldkamp lines of S (3) . As already mentioned, there are 10 795 of them and, as found in [START_REF] Green | The Veldkamp space of the smallest slim dense near hexagon[END_REF], they fall into 41 distinct types. The basic combinatorial characteristics of all the types are listed in Table 4 and a representative of each type is provided by Figure 6. Concerning extraordinary Veldkamp lines of S (3) , there are obviously as many types of them as there are types of ordinary geometric hyperplanes of S (3) ; we depict their representatives in Figure 7.

S (4) and its geometric hyperplanes

The Segre variety S (4) , known also as the smallest slim dense near octagon [START_REF] Bruyn | Near Polygons[END_REF], is a point-line incidence structure having 81 points and 108 lines, with three points per line and four lines through a point. It possesses 12 S (3) 's, arranged into four distinct triples of pairwise disjoint members, each of which partitions the point-set. Analogously, S (4) contains four distinguished spreads of lines; a distinguished spread of lines is a set of 27 mutually skew lines such that each line is incident with all the three S (3) 's from a given triple.

Table 5: The 29 types of geometric hyperplanes of S (4) ; also shown is partition of hyperplane types into 15 classes according to the number of points/lines. As in corresponding Tables 1 and3, one first gives the type ('Tp') of a hyperplane, then the number of points ('Ps') and lines ('Ls') it contains, and the number of points of given order. The next six columns tell us about how many of 12 S (3) 's are fully located ('D') in the hyperplane and/or share with it a hyperplane of type H i (see Table 3 above). The VL-column lists the types of ordinary and/or extraordinary Veldkamp lines of S (3) we get by projecting a hyperplane of the given type into S (3) 's along the lines of all four distinguished spreads. Finally, for each hyperplane type we give its cardinality ('Crd'), the corresponding large orbit of 2 × 2 × 2 × 2 arrays over GF (2) ('BS') taken from Table 5 of [START_REF] Bremner | Canonical forms of 2 × 2 × 2 and 2 × 2 × 2 × 2[END_REF], and its weight/rank ('W'). In order to find out how many different types of geometric hyperplanes S (4) is endowed with and what the cardinality is of a given hyperplane type, we shall make use of a 3 × 3 × 3 × 3 grid ('hypercube') representation of S (4) , whose rudiments are sketched in Figure 8, and simply blow-up the representatives of both ordinary and extraordinary Veldkamp lines of S (3) whose diagrammatic portrayals were given in the previous section. In particular, taking a representative of the Veldkmap line of S (3) of given type from Figure 6, we first blow-upemploying the procedure illustrated in Figures 3 and4 -all its nine S (2) -Veldkamp-sublines into S (3) -hyperplanes to get the character of intersection of the corresponding geometric hyperplane of S (4) with 9 out of its 12 S (3) 's, and then look up the character of the remaining three guys in Table 4. Let us illustrate this in more detail by taking an explicit example of the typeseven Veldkamp line of S (3) , whose representative sits in row four, column one of Figure 6. Let us name its nine S (2) -Veldkamp-lines according to the location of the corresponding S (2) 's as left, right, middle-left-right, top, bottom, middle-top-bottom, front, back, and middle-frontback. With the help of Figures 3 and4 we find out that the geometric hyperplanes of S (3) we get by the corresponding blow-ups are of type two, one, four, one, three, three, one, two and four, respectively. From Table 4 we extract that type-seven Veldkamp line of S (3) consists of hyperplanes of type one, three and three. Summarizing, we get that the geometric hyperplane of S (4) we get by blowing-up a representative of Veldkamp line of S (3) of type seven will feature four S (3) 's of type H 1 and H 3 , two S (3) 's of type H 2 and H 4 , and no S (3) 's of type H 5 or fully located in the hyperplane. To find the number points and lines this particular geometric hyperplane of S (4) possesses is also quite easy. One simply keeps in mind that each point colored green, blue and red represents a single point of the hyperplane, whilst a point colored black (i. e., point of the core) is blown up into three distinct points of the hyperplane. As the corresponding subfigure in Figure 6 has nine black points, we find that the hyperplane in question will have 9 × 3 + (27 -9) × 1 = 45 points. Similarly, if we take into account that each green, blue and red line, as well as each black point, is blown up into a single line of the hyperplane and each black line gives rise to three distinct lines of the hyperplane, we find that the hyperplane must feature 36 lines. We leave it with the interested reader to ascertain the order of individual points of this particular hyperplane type. Following the same procedure, we shall arrive at the same type of geometric hyperplane if we start with a representative of type-eight Veldkamp line of S (3) (shown in row four, column two of Figure 6). Concerning the question of how many distinct copies of this type of hyperplane we have, it suffices to recall and generalize our observation from Sec. 3.1 that an ordinary Veldkamp line of S (N -1) gives rise to six different hyperplanes of S (N ) . Since our hyperplane, as we have just seen, originates from two different types of ordinary Veldkamp lines of S (3) , namely seven and eight, and each of the latter has 324 members (see Table 4), we find that this hyperplane type has as many as 6 × 2 × 324 = 3888 members. Performing the same analysis with each representative depicted in both Figure 6 and Figure 7, we shall find that geometric hyperplanes of S (4) , totaling to 65 535 (= 2 16 -1 = |P G(15, 2)|) distinct members, fall into 29 different types whose basic combinatorial properties are collected in Table 5. In the table, the basic ordering is the same as in Tables 1 and3, i. e., the types featuring more points/lines precede those having less ones. However, unlike the previous two cases, we now encounter two or more types having the same number of point/lines, in which case the first goes that having more deep points; even if this number is the same (for example, types seven and eight), then we list first the one having more points of order three. One notes in passing that the hyperplane subject to a detailed examination above belongs to type nine.

# of Points of

Let us make a brief inspection of Table 5 and highlight the most prominent properties of the hyperplane types. Obviously, a type-one hyperplane is a singular hyperplane, that is a hyperplane comprising all the points that are not at maximum distance from a given point; the latter being called the deepest point. On the other hand, a type-29 hyperplane is an ovoid, that is, a set of 27 mutually non-collinear points. Next, let us call, adopting the terminology used for near polygons, a hyperplane of S (4) homogeneous if all its S (3) 's are of the same character. From Table 5 we discern that homogeneous hyperplanes are of types 8, 20 and 29; of course, for the extraordinary hyperplane all of its S (3) 's are deep, but there is no homogeneous hyperplane whose S (3) 's would be all of type H 1 or H 4 . At the opposite end of the spectrum, there is a type-17 hyperplane, which entails all types of S (3) 's except for that corresponding to S (3) 's fully located in it. This is also a hyperplane type that contains points of all orders; there are other five types enjoying this property, namely 9, 11, 15, 22 and 24. A type-22 hyperplane is also distinguished by the fact that this is the only type whose each member stems from three different types of Veldkamp lines of S [START_REF] Melone | Spazi pseudoprodotto e varietà di C. Segre[END_REF] . There are 15 types such that each originates from two different types of Veldkamp lines of S (3) ; each of the remaining 13 types being then a blow-up of a single type of Veldkamp lines of S (3) . We further observe that there are only three hyperplane types whose representatives exhibit just a single point of zeroth (i. e. minimum) order, and five types with a single point of the fourth (i. e. maximum) order. It is also worth mentioning that a hyperplane of type two, three and four, being of weight two, can be gotten as the Veldkamp sum of any two hyperplanes of type one whose deepest points are at distance two, three and four, respectively.

A further inspiring insight into the nature of hyperplane types is acquired if one looks at distinguished subconfigurations of the Veldkamp space of S (4) , V(S (4) ). We have already explicitly seen that ord-V(S (N ) ) ∼ = P G(2 N -1, 2) for 1 ≤ N ≤ 3. It is assumed that this property holds for any N , hence ord-V(S (4) ) ∼ = P G(15, 2). In the latter case there, indeed, exists a specific hyperbolic quadric Q + 0 (15, 2) ⊂ P G(15, 2) that is composed of 18 particular types of geometric hyperplanes shown in Table 6. Comparing the 'VL'-column of this table with the information displayed in Table 4 we find out that these are precisely hyperplane types that originate from those types of (ordinary) Veldkamp lines of S (3) whose cores feature odd number of points. This is, however, not the full story as we can look at those orbits of this particular Q + 0 (15, 2) that in their totality correspond to the image, furnished by the Lagrangian Grassmannian of type LGr(4, 8), of the set of 2295 maximal subspaces of the symplectic polar space W(7, 2) [START_REF] Holweck | A notable relation between N -qubit and 2 N -1 -qubit Pauli groups via binary LGr(N, 2N )[END_REF]. The corresponding hyperplane types are given in Table 7; note that they are exactly the types whose members feature no S (3) of type H 3 and H 5 , each of them also exhibiting points of maximum order (compare with the S (3) -case).

Conclusion

Based on the concept of the (generalized) Veldkamp space of a point-line incidence structure, we have had a detailed look at the structure of the Segre varieties that are N -fold direct product of projective lines of size three, S

(N ) ≡ P G(1, 2) × P G(1, 2) × • • • × P G(1, 2
), for the cases 2 ≤ N ≤ 4. In particular, given the fact that S (N ) = P G(1, 2) × S (N -1) , we have introduced a diagrammatical recipe that shows how to fully recover the properties of Veldkamp points (i. e. geometric hyperplanes) of S (N ) once we know the types (and cardinalities thereof) of Veldkamp lines of S (N -1) . After illustrating this recipe on the S (1) -to-S (2) (Sec. 3.1) and S (2) -to-S (3) (Sec. 3.2) cases, we have made its use to arrive at a complete classification of types of geometric hyperplanes of S (4) (Sec. 3.3, Table 5). In this latter case, employing the fact that the ordinary part of Veldkamp space of S (N ) , ord-V(S (N ) ), is isomorphic to P G(2 N -1, 2), which is conjectured to hold for any N ≥ 1, we were also able to ascertain (Table 6) which types of geometric hyperplanes of S (4) lie on a particular hyperbolic quadric Q + 0 (15, 2) ⊂ P G(15, 2) ∼ = ord-V(S (4) ) which contains the S (4) and is invariant under its stabilizer group, as well as to single out those of them (Table 7) that are mapped, via the Lagrangian Grassmannian of type LG [START_REF] Bader | Partitioning Segre varieties and projective spaces[END_REF][START_REF] Coolsaet | On the classification of nonsingular 2 × 2 × 2 × 2 hypercubes[END_REF], to the set of 2295 maximal subspaces of the symplectic polar space W(7, 2).

Finally, we would like to stress the following intriguing fact. In our conception of the Veldkamp space of a point-line incidence structure, the extraordinary geometric hyperplane was taken to stand on the same par as any other hyperplane. Otherwise, as it is readily discernible from Tables 1, 3 and 5, by employing our blow-up recipe it would not only be impossible to recover singular geometric hyperplanes of S (N ) from the Veldkamp lines of S (N -1) , but, as it is particularly evident in the N = 4 case (and envisaged to be gradually more pronounced as N increases), we could not get the correct cardinalities for certain other hyperplane types. The price to be paid for this is that our Veldkamp space is no longer a 'homogeneous' geometry, but it comprises a 'well-behaving' ordinary part and a rather 'ugly' extraordinary part. This is reminding us distantly of a situation with the concept of an N -dimensional projective space over an associative ring with unity, R, if one takes the points of this space to be represented by all free cyclic submodules (FCS's) of the left module R N +1 ; here, the 'ordinary' part of the space is generated by unimodular FCS's, whilst its 'extraordinary' part -which is, however, non-empty only for very specific rings, like rings of ternions -is represented by non-unimodular FCS's (see, e. g., [START_REF] Saniga | Twin "Fano-snowflakes" over the smallest ring of ternions[END_REF][START_REF] Havlicek | Vectors, cyclic submodules and projective spaces linked with ternions[END_REF] for some illustrative examples and [START_REF] Saniga | Space versus time: Unimodular versus non-unimodular projective ring geometries?[END_REF] for a possible physics behind).

Figure 2 :

 2 Figure 2: An illustration of the fact that the two types of geometric hyperplanes of S (2) (right) can be regarded as blow-ups of the Veldkamp lines of S (1) (left), or, vice versa, that a projection of a type two (top right) or type one (bottom right) hyperplane of S (2) onto a line of S (2) can be viewed, respectively, as the ordinary (top left) or an extraordinary (bottom left) Veldkamp line of S (1) .

Figure 4 :

 4 Figure 4: The same as in Figure 3, but for extraordinary Veldkamp lines of S (2) (top) and their S (3) blown-up cousins (bottom).

Figure 6 :

 6 Figure 6: A diagrammatic illustration, on a 3 × 3 × 3-grid, of representatives of all 41 types of ordinary Veldkamp lines of S (3) . As in Figure 3, top, the three geometric hyperplanes forming a Veldkamp line are distinguished by different coloring, with the points and lines shared by all of them (the core) being colored black.

27 Figure 7 :

 277 Figure 6: (Continued.)

Figure 8 :

 8 Figure 8: A tesseract-based frame for visualization of the structure of S (4) ; in order to avoid too crowded appearance of the configuration, there are only shown 24 (out of 81) points and 44 (out of 108) lines.

Table 1 :

 1 The two types of geometric hyperplanes of S (2) .

				Pts of Order S (1) 's Type
	Tp Ps Ls	0	1	2	D	H 1	VL Crd
	1	5	2	0	4	1	2	4	ext	9
	2	3	0	3	0	0	0	6	ord	6

  Top: -A descriptive illustration of the structure of the four distinct types (1 to 4, left to right) of ordinary Veldkamp lines of S (2) (Table2); the three geometric hyperplanes comprising a Veldkamp line are distinguished by different colors, with the points and lines shared by all of them being colored black. Bottom: -The four distinct types of geometric hyperplanes of S (3) , as well as the number of copies per each type, we get by blowing-up Veldkamp lines of S (2) of the type shown above the particular subfigure.

	6			18			9	2
	36	108			54		12
	H 2			H 3			H 4	H 5
	Figure 3:
					Comp'n
		Tp Ps Ls H 1 H 2 Crd
		1	3	1	3	-	6
		2	2	0	2	1	18
		3	1	0	1	2	9
		4	0	0	-	3	2

Table 3 :

 3 The 5 types of (ordinary) geometric hyperplanes of the Segre variety S (3) . As in Table

Table 6 :

 6 The types of geometric hyperplanes of S (4) lying on the unique hyperbolic quadric Q + 0 (15, 2) ⊂ P G(15, 2) that contains the S (4) (the first orbit) and is invariant under its stabilizer group.

	# of Points of Order		# of S (3) 's of Type
	Tp Ps Ls 0	1	2	3	4 D H 1 H 2 H 3 H 4 H 5	VL	Crd BS W
	1 65 76 0	0	0 32 33 4	8	0	0	0	0	I	81	2 1
	2 57 60 0	0 12 24 21 2	6	4	0	0	0	II, 1	324	3 2
	3 53 52 0	2 12 26 13 1	6	3	2	0	0	III, 2 1296	4 2
	5 49 44 0	8 12 16 13 1	3	6	0	2	0	IV, 4	648	6 3
	7 45 36 0 18 0 18 9	1	0	9	0	0	2	V, 6	144	7 3
	8 45 36 0	0 36 0	9	0	0	12	0	0	0	10	108 17 4
	9 45 36 2	4 18 16 5	0	4	2	4	2	0	7, 8 3888	8 3
	10 45 36 0	6 18 18 3	0	3	3	6	0	0	9, 11 2592	9 3
	12 41 28 8	0 24 0	9	0	4	0	0	8	0	14	162 14 4
	13 41 28 0 12 18 8	3	0	0	6	4	2	0	15, 18 1944 19 4
	14 41 28 0 14 12 14 1	0	1	3	6	2	0	17, 21 2592 15 4
	15 41 28 2	8 18 12 1	0	1	3	7	0	1	16, 20 2592 10 3
	16 41 28 0	8 24 8	1	0	0	4	8	0	0	19 1944 20 4
	21 37 20 4 16 12 0	5	0	0	4	0	8	0	29	972 18 4
	22 37 20 4 14 12 6	1	0	0	2	5	4	1	30-32 7776 21 4
	23 37 20 3 12 18 4	0	0	0	0	8	4	0	33 3888 24 4
	26 33 12 12 12 6	0	3	0	0	2	0	6	4	37, 38	648 26 5
	27 33 12 11 12 6	4	0	0	0	0	4	4	4	39 1296 29 5

Table 7 :

 7 Six types of hyperplanes lying on Q + 0 (15, 2) that in their totality correspond to the image of the set of 2295 maximal subspaces of the symplectic polar space W(7, 2). Interestingly, one orbit consists of homogeneous hyperplanes, viz. of those whose all S (3) 's are of type H 2 .

	# of Points of Order		# of S (3) 's of Type
	Tp Ps Ls 0 1	2	3	4 D H 1 H 2 H 3 H 4 H 5	VL Crd BS W
	1 65 76 0 0	0 32 33 4	8	0	0	0	0	I	81	2 1
	2 57 60 0 0 12 24 21 2	6	4	0	0	0	II, 1 324	3 2
	5 49 44 0 8 12 16 13 1	3	6	0	2	0	IV, 4 648	6 3
	8 45 36 0 0 36 0	9	0	0	12	0	0	0	10 108 17 4
	12 41 28 8 0 24 0	9	0	4	0	0	8	0	14 162 14 4
	21 37 20 4 16 12 0	5	0	0	4	0	8	0	29 972 18 4

Here the term 'distance' means the graph-theoretical distance between the corresponding vertices of the collinearity graph of the point-line incidence structure in question.

In analogy to S (2) , and to be compatible with the approach advanced in[START_REF] Green | The Veldkamp space of the smallest slim dense near hexagon[END_REF], we shall employ a handy descriptive representation of S (3) as a

× 3 × 3 grid (see Figure1of[START_REF] Green | The Veldkamp space of the smallest slim dense near hexagon[END_REF]).

Acknowledgment

This work was partially supported by the VEGA Grant Agency, Project 2/0003/13, as well as by the Austrian Science Fund (Fonds zur Förderung der Wissenschaftlichen Forschung (FWF)), Research Project M1564-N27.


Alexandre B -Massé

Srečko Brlek

Amy Glen

Sébastien Labbé

On the Critical Exponent of Generalized Thue-Morse Words

Keywords: Thue-Morse, critical exponent, occurrences

For certain generalized Thue-Morse words t, we compute the critical exponent, i.e., the supremum of the set of rational numbers that are exponents of powers in t, and determine exactly the occurrences of powers realizing it.

Introduction

It is a well-known fact that the Norwegian mathematician Axel Thue was the first to explicitly construct and study the combinatorial properties of an infinite overlap-free word over a 2-letter alphabet, obtained as the fixpoint of the morphism µ : {a, b} * → {a, b} * defined by µ(a) = ab; µ(b) = ba:

µ(m) = m = abbabaabbaababba • • • .
For a modern account of his papers, see Berstel [START_REF] Berstel | Axel Thue's work on repetitions in words[END_REF]. Rediscovered by M. Morse in 1921 in the study of symbolic dynamics, this overlap-free word is now called the Thue-Morse word. This "ubiquitous" sequence, already implicit in a memoir by Prouhet [START_REF] Prouhet | Mémoire sur quelques relations entre les puissances des nombres[END_REF] in 1851, appears in various fields, such as combinatorics on words, symbolic dynamics, differential geometry, number theory, and mathematical physics, as surveyed by Allouche and Shallit [START_REF] Allouche | The ubiquitous Prouhet-Thue-Morse sequence[END_REF]. That survey also mentions some generalizations of the Thue-Morse word, and recently other ones were considered in [START_REF] Allouche | Sums of digits, overlaps, and palindromes[END_REF][START_REF] Frid | Overlap-free symmetric D0L words[END_REF]. In particular, the following result was established in [START_REF] Allouche | Sums of digits, overlaps, and palindromes[END_REF]. It was also shown in [START_REF] Allouche | Sums of digits, overlaps, and palindromes[END_REF] that the word t b,m contains arbitrarily long squares, which extends a result previously established by Brlek [START_REF] Brlek | Enumeration of the factors in the Thue-Morse word[END_REF] for m. Moreover, it was mentioned ( [START_REF] Allouche | Sums of digits, overlaps, and palindromes[END_REF], p. 8) that,

It would be interesting to determine the largest (fractional) power that occurs in the sequence t b,m . For b ≤ m, we already know that 2 is sharp.

We solve this problem here. Specifically, we study the family T of generalized Thue-Morse words consisting of the words t b,m as well as letter-renamings of them (see Section 2). For any t ∈ T , we compute the critical exponent (i.e., the supremum of the set of rational numbers that are exponents of powers in t) and determine exactly the occurrences of powers realizing it, both in terms of b and m. A noteworthy fact is that the critical exponents of generalized Thue-Morse words are always realized, which is not necessarily true in general (see Remarks 2.1 and 2.4).

The next section contains all of the basic terminology on words, borrowed mainly from Lothaire [START_REF] Lothaire | Combinatorics On Words[END_REF], along with the generalized Thue-Morse words. Section 3 contains the technical lemmas, establishing combinatorial properties used for proving our main results. The critical exponent (Theorem 4.4) is then computed in Section 4, and Section 5 deals with the occurrences of factors realizing it (Theorem 5.5).

Let us mention that the notions of 'fractional power' and 'critical exponent' have received growing attention in recent times, especially in relation to Sturmian and episturmian words; see for instance [START_REF] Berstel | On the index of Sturmian words[END_REF][START_REF] Berthe | Initial powers of Sturmian sequences[END_REF][START_REF] Damanik | The index of Sturmian sequences[END_REF][START_REF] Glen | Powers in a class of A-strict standard episturmian words[END_REF][START_REF] Justin | Fractional powers in Sturmian words[END_REF][START_REF] Justin | Episturmian words and episturmian morphisms[END_REF][START_REF] Krieger | On critical exponents in fixed points of non-erasing morphisms[END_REF][START_REF] Mignosi | Repetitions in the Fibonacci infinite word[END_REF][START_REF] Vandeth | Sturmian words and words with a critical exponent[END_REF].

Definitions and notation

Let Σ denote a finite alphabet, i.e., a finite set of symbols called letters. A finite word over Σ is a finite sequence w = w 0 w 1 • • • w ℓ-1 , where each w i ∈ Σ. We often write w[i] for w i , when i is a complicated formula. The length of w is |w| = ℓ, and the empty word of length 0 is denoted by ε. The set of all finite words over Σ is denoted by Σ * .

A word u is a factor of w if w = pus for some words p, s. Moreover, such a word u is said to be a proper factor of w if u = w. We also say that u is a prefix (resp. suffix) of w if p = ε (resp. s = ε). The number |p| is called an occurrence of u in w, i.e., |p| is the beginning position of an appearance of u in w.

The set of all factors of a word w is denoted by F (w). A word v is a conjugate of w if there exists a word u such that uv = wu.

An overlap w is a word of the form w = auaua where a is a letter and u is a (possibly empty) word. For example, the English word alfalfa is an overlap and banana has the overlap anana as a suffix. A finite word is said to be overlap-free if it does not contain an overlap as a factor. Factors of the form uu are called squares.

The rational power of a word w is defined by w r = w ⌊r⌋ p where r is a rational such that r|w| ∈ N and p is the prefix of w of length (r -⌊r⌋)|w|. For example, the word cab abbacc abbacc abb bca contains a factor which is a 5 2 -power. A (right) infinite word (or simply a sequence) x over Σ is a sequence indexed by N with values in Σ, i.e., x = x 0 x 1 x 2 • • • where each x i ∈ Σ. All of the terminology above naturally extends to infinite words.

An ultimately periodic infinite word can be written as

uv ω = uvvv • • •, for some u, v ∈ Σ * , v = ε. If u = ε,
then such a word is periodic. An infinite word that is not ultimately periodic is said to be aperiodic.

For any factor w of an infinite word x, the index of w in x is given by the number

INDEX(w) = max{r ∈ Q | w r ∈ F (x)},
if such a number exists; otherwise, w is said to have infinite index in x. The critical exponent E(x) of an infinite word is given by

E(x) = sup {INDEX(w) | w ∈ F (x)\{ε}} .
It may be finite or infinite. A factor w of x is said to be a critical factor if its index realizes the critical exponent of x, that is, when INDEX(w) = E(x).

Remark 2.1 For any factor w of an infinite word x, INDEX(w) is always realized when finite, whereas the critical exponent E(x), even when finite, is not always realized; in particular, an infinite word may contain no critical factors. For example, the critical exponent of the well-known Fibonacci word f is

E(f ) = 2 + φ, where φ = √ 5+1 2
is the golden ratio (see [START_REF] Mignosi | Repetitions in the Fibonacci infinite word[END_REF]), but none of the factors of f realize E(f ).

A morphism is a function ϕ : Σ * → Σ * such that ϕ(uv) = ϕ(u)ϕ(v) for all u, v ∈ Σ * . For each letter a ∈ Σ, ϕ(a) is called a block.

Generalized Thue-Morse words

There exist many generalizations of the Thue-Morse word. Here, we introduce a morphism based formulation which is more convenient for our purposes.

µ(α) = b-1 i=0 σ i (α) = σ 0 (α)σ 1 (α)σ 2 (α) • • • σ b-1 (α).
Then the generalized Thue-Morse word t, beginning with α ∈ Σ, is the infinite word given by t = µ ω (α) = lim n→∞ µ n (α).

Hereafter, we study the family T of generalized Thue-Morse words t, for all b ≥ 2 , m ≥ 1 and α ∈ Σ.

Remark 2.3 The n-th letter of t is t[n] := σ s b (n) (α)
(△) = △♦♥△♦, µ(♦) = ♦♥△♦♥ and µ(♥) = ♥△♦♥△. By fixing α = ♦, we obtain the generalized Thue-Morse word t = µ ω (♦) = ♦♥△♦♥♥△♦♥△△♦♥△♦♦♥△♦♥ • • • . Example 2 With Σ = Z m , σ(i) = (i + 1) mod m and α = 0, Remark 2.3 implies that t[n] = σ s b (n) (0) = s b (n) mod m, (1)
which is the case proposed by Allouche and Shallit [START_REF] Allouche | Sums of digits, overlaps, and palindromes[END_REF].

Example 3 With Σ = Z m , σ(i) = (i + c
) mod m for some integer c > 0 and α = 0, we have µ(0

) = 0 c 2c • • • (b -1)c and µ(i) = i (i + c) (i + 2c) • • • i + (b -1)c = i b + µ(0)
where i ≡ i mod m. This is a subclass of the family of symmetric morphisms, defined by A. Frid [START_REF] Frid | Overlap-free symmetric D0L words[END_REF].

That paper also contains an extension of Proposition 1.1 to more general words.

It is important to note that words in T , up to letter renaming, are exactly those given in Equation (1). Our definition avoids modular arithmetic on integers, and simplifies proofs by using the combinatorial properties of T instead. For that purpose, we say that a word w = w 0 w Remark 2.4 Since t ∈ T is a fixpoint of a uniform non-erasing morphism, it follows immediately from Krieger's results in [START_REF] Krieger | On critical exponents in fixed points of non-erasing morphisms[END_REF] that the critical exponent of t is either infinite (if t is periodic) or rational. Moreover, since µ(α) and µ(β) neither begin nor end with a common word when α = β, it also follows from [START_REF] Krieger | On critical exponents in fixed points of non-erasing morphisms[END_REF] that the critical exponent, when finite, is reached (i.e., t contains critical factors).

1 • • • w ℓ-1 ∈ F (t) is σ-cyclic if w i = σ(w i-1 ) for 1 ≤ i ≤ ℓ -1, or equivalently, if w i = σ i (w 0 ) for 0 ≤ i ≤ ℓ -1. As a consequence, blocks of t are σ-cyclic.

Preliminary results

In this section, t ∈ T denotes an infinite generalized Thue-Morse word, as given in Definition 2.2. Lemma 3.1 [START_REF] Frid | Arithmetical complexity of symmetric D0L words[END_REF][START_REF] Morton | Digit patterns and transcendental numbers[END_REF] The word t is periodic if and only if m | (b -1). More precisely, if t is periodic then

t = m-1 i=0 σ i (α) ω . ✷ Lemma 3.2
Let w be a σ-cyclic factor of t of length ℓ. If there exists an occurrence of w overlapping three consecutive blocks, then t is periodic.

Proof: Suppose that there exists such an occurrence of w in t. Since w is σ-cyclic and since every block is σ-cyclic, those three consecutive blocks, say β 1 , β 2 and β 3 , satisfy the fact that

β 1 β 2 β 3 is σ-cyclic.
Let α 1 , α 2 and α 3 be the first letters of β 1 , β 2 and β 3 . Then α 2 = σ b (α 1 ) and α 3 = σ b (α 2 ), and α 1 α 2 α 3 = µ -1 (β 1 β 2 β 3 ) are three consecutive letters occurring in t. This means, in particular, that either α 1 α 2 or α 2 α 3 occur in the same block. Hence, either α 2 = σ(α 1 ) or α 3 = σ(α 2 ), which implies that

α 1 = σ b-1 (α 1 ) or α 2 = σ b-1 (α 2 ). Therefore, m | (b -1) and by Lemma 3.1, t is periodic. ✷ Lemma 3.3 Let w = w 0 w 1 • • • w ℓ-1 be a factor of t such that b | ℓ.
i) If wp occurs in t where p is any prefix of w, then p is σ-cyclic.

ii) If w e occurs in t for some rational e > 2, then w e is σ-cyclic.

Proof: Let p be any prefix of length ℓ ′ of w and assume v = wp occurs in t. Let v i be the i-th letter of v, with 0

≤ i ≤ ℓ + ℓ ′ -1. For 0 ≤ i ≤ ℓ ′ -2, either v i v i+1 or v i+ℓ v i+ℓ+1
is contained in the same block: if this was not the case, then b would divide (i + ℓ)i = ℓ, contradicting our assumption. Since

v i v i+1 = w i w i+1 = v i+ℓ v i+ℓ+1
, we have w i+1 = σ(w i ) so that the first result follows.

Since w e = www e-2 , w is σ-cyclic from i). Let x be the conjugate of w such that w 0 x = ww 0 . Then, w e = w 0 xxx e-2-1/ℓ and from i) x is σ-cyclic and so too is its factor w ℓ-1 w 0 . Hence, w e is σ-cyclic, which ends the second part. ✷ Proof: By contradiction, assume v = www 0 occurs in t, where w 0 is the first letter of w. Lemma 3.3 implies that v is σ-cyclic. Moreover, |v| = 2ℓ + 1 > 2b, which means that v overlaps at least three consecutive blocks of t. Thus, by Lemma 3.2, t is periodic which contradicts our assumption. ✷

Critical exponent

In this section, we use exactly the same notation as previously. Before proving Theorem 4.4, we need a few additional facts. The next two lemmas allow us to consider particular occurrences of factors of t. We say that an occurrence i of w in t is synchronized if b | i and b | (i + |w|). Lemma 4.1 Suppose w = w 0 w 1 • • • w ℓ-1 is a factor of t such that b | ℓ. Let p be a non-empty prefix of w such that bq + r is an occurrence of w n p in t, where q, r ∈ N, 0 ≤ r < b and n ≥ 1. Let s be the possibly empty suffix of w such that w = ps. Moreover, let bq ′ + r ′ = bq + r + |w n p|, where q ′ , r ′ ∈ N,

0 ≤ r ′ < b. Then, i) v = t[bq] • • • t[bq + r -1] is a suffix of w, ii) u = t[bq ′ + r ′ ] • • • t[bq ′ + b -1] is a prefix of sp,
iii) bq is a synchronized occurrence of vw n pu in t.

Proof: Let v = v 0 v 1 • • • v r-1 = t[bq] • • • t[bq + r -1] and let s = s 0 s 1 • • • s r-1 be
the suffix of w of length r. We show that v = s. First note that vw 0 is contained in the block starting at position bq. Also, since b | ℓ, sw 0 is contained in one block. Both remarks imply that vw 0 and sw 0 are σ-cyclic. Hence,

v i = σ i-r (w 0 ) = s i for 0 ≤ i ≤ r -1,
which gives the result. The proof of ii) is symmetric to the proof of i), and iii) follows from i) and ii). ✷ Lemma 4.2 Let w be a word of length ℓ such that b | ℓ and suppose w e occurs in t for some rational e > 1. Then there exists a conjugate x of w and a rational f ≥ e such that both x and x f have a synchronized occurrence in t.

Proof: Let p be the non-empty prefix of w such that w e = w n p where n ∈ N + and let s be the suffix of w such that w = ps. Also, let bq + r be an occurrence of w e in t, where q, r ∈ N and 0 ≤ r < b. By Lemma 4.1, there exist a suffix v of w and a prefix u of sp such that bq is a synchronized occurrence of vw e u in t. Now let y be the prefix of w such that w = yv, and define x = vy. We have vw e u = v(yv) n pu = (vy) n vpu = x n vpu. Moreover, vpu is a prefix of vpsps = vw 2 = v(yv) 2 = x 2 v so that vw e u = x n vpu = x f for some rational f . Finally,

f = ℓn + |vpu| ℓ ≥ ℓn + |p| ℓ = e,
which ends the proof, since x and x f both satisfy the required conditions. ✷

The next lemma deals with factors w of t of length ℓ not divisible by b.

Lemma 4.3 Suppose t is aperiodic and let w be a factor of t of length ℓ such that b | ℓ. Then

INDEX(w) ≤ 2b/m if b > m, 2 if b ≤ m.
Proof: We distinguish three cases according to ℓ, b and m. We are now ready to prove the main theorem of this section, which gives the critical exponent of t.

Theorem 4.4 The critical exponent of t is given by

E(t) =    ∞ if m | (b -1), 2b/m if m | (b -1) and b > m, 2 if b ≤ m.
Lemma 5.2 Let w be a critical factor of t of length ℓ such that b | ℓ.

i) In the overlap case, ℓ = m and w e = β 1 β 2 , where β 1 , β 2 are two consecutive blocks.

ii) In the square case, write w 2 = w (1) w (2) . Then w (2) occurs at the beginning of a block. Otherwise, if w e overlaps three consecutive blocks, then from Lemma 3.2 t is periodic, a contradiction. On the other hand, if ℓ > b, then from the last section we know that INDEX(w) = 2b/m > 2. This contradicts Lemma 3.4; hence there is no such critical factor.

Square case (b ≤ m). Again, we distinguish two cases. First assume ℓ < b. Note that each block of t contains distinct letters. Also, w 2 is a factor of t and, from Lemma 3.3, w is σ-cyclic. If α i denotes the i-th letter of w 2 with 0 ≤ i < 2ℓ, then α i = α i+ℓ for all 0 ≤ i < ℓ. This implies that α 0 and α ℓ are not in the same block so that there exist two consecutive letters α i-1 and α i , where 1 ≤ i ≤ ℓ, which are not contained in the same block. Suppose 1 ≤ i < ℓ. Then, α i and α i+ℓ belong to the same block since ℓ < b. This is a contradiction because α i = α i+ℓ . We conclude that the pair α ℓ-1 and α ℓ is not contained in the same block. In other words, w (2) occurs at the beginning of a block.

Lastly, consider the case ℓ > b. From Lemma 3.3, w is σ-cyclic. Suppose w (2) does not occur at the beginning of a block. Then the pair w ℓ-1 w 0 formed by the last and the first letter of w is in the same block and is σ-cyclic. Hence, the whole factor w 2 of length 2ℓ > 2b is σ-cyclic. This factor overlaps three consecutive blocks so t is periodic from Lemma 3.2, a contradiction. ✷

It has already been noticed that squares of certain factors of length 3 appear in the Thue-Morse word (see [START_REF] Brlek | Enumeration of the factors in the Thue-Morse word[END_REF] for example). The following lemma proves the uniqueness of this fact. Proof: Suppose that w is critical factor of t of length ℓ > b such that b | ℓ. In the proof of Lemma 5.2, we saw that in the overlap case there is no such critical factor. In the square case, we know also from Lemma 5.2 that if w 2 = w (1) w (2) then w (2) occurs at the beginning of a block. Moreover, Lemma 3.3 implies that w is σ-cyclic. Since ℓ > 2b implies that w overlaps three consecutive blocks, it follows from Lemma 3.2 that b < ℓ < 2b.

Hence w 2 overlaps exactly four consecutive blocks, say β 1 , β 2 , β 3 and β 4 . Let α i be the first letter of the block β i , i ∈ {1, 2, 3, 4}, and let r = 2bℓ be the distance between α 1 and the first letter of w 2 . Then α 3 = w 0 = σ r (α 1 ). Also, since w is σ-cyclic, we have α 2 = σ b (α 1 ) and α 4 = σ b (α 3 ) = σ b+r (α 1 ). Moreover, it follows that α 1 α 2 α 3 α 4 = µ -1 (β 1 β 2 β 3 β 4 ) is a factor of t. Assume α 1 α 2 is in the same block, then α 2 = σ(α 1 ); but then, since α 2 = σ b (α 1 ), we get that α 1 = σ b-1 α 1 , and so m | (b -1), which is in contradiction with b ≤ m. Assuming α 3 α 4 is in the same block gives the same contradiction. Hence, neither α 1 α 2 nor α 3 α 4 are in the same block. We conclude from the last observation that b = 2 since α 2 α 3 = σ b (α 1 )σ r (α 1 ) must form a block. Therefore ℓ = 3 and r = 1. Also, m divides b+1-r = b and m = b = 2 because the block α 2 α 3 is σ-cyclic, which ends the proof.

Note that α 2 = α 1 , α 4 = α 3 , α 3 = σ(α 1 ) and w = σ(α 1 )α 1 σ(α 1 ), which has already been noticed in [START_REF] Brlek | Enumeration of the factors in the Thue-Morse word[END_REF].

✷

We now prove the following lemma which is a more general result than Lemma 5 in [START_REF] Allouche | Sums of digits, overlaps, and palindromes[END_REF].

Proposition 1 . 1 [ 2 ]

 112 Let m ≥ 1, b ≥ 2 be integers and let s b (n) denote the sum of the digits in the base b representation of n ∈ N. Then the infinite word t b,m := (s b (n) mod m) n≥0 over the alphabet Σ m := {0, 1, . . . , m -1} is overlap-free if and only if b ≤ m. ✷

Definition 2 . 2

 22 Let b ≥ 2, m ≥ 1 be integers, Σ an alphabet of m letters, σ : Σ → Σ a cyclic permutation and µ : Σ * → Σ * the morphism given by

Example 1

 1 where s b (n) denotes the sum of the digits in the base b representation of n ∈ N. Let b = 5, m = 3, Σ = {△, ♦, ♥} and σ : △ → ♦ → ♥ → △. This gives the following morphism : µ

Example 4

 4 With Σ = {a, b}, σ : a → b → a and α = a, we get µ(a) = ab, µ(b) = ba and t = µ ω (a) = abbabaabbaababba • • • which is the original Thue-Morse word m.

Lemma 3 . 4

 34 Suppose t is aperiodic. If w is a factor of t of length ℓ ≥ b with b | ℓ, then INDEX(w) ≤ 2.

Case 1 :Case 3 :

 13 ℓ > b. By Lemma 3.4, we have INDEX(w) ≤ 2. Case 2 : ℓ < b and b > m. Let w 0 be the first letter of w and e = INDEX(w). If e > 2, then by Lemma 3.3 w e is σ-cyclic. In particular, w 0 = σ ℓ (w 0 ), i.e., m | ℓ and ℓ ≥ m. However, by Lemma 3.2, we know that |w e | ≤ 2b. Therefore, ℓ < b and b ≤ m. As above, let e = INDEX(w) and suppose e > 2, which means w e is σ-cyclic and m | ℓ. The latter statement is not possible since 1 ≤ ℓ < b ≤ m. We conclude in this case that INDEX(w) ≤ 2. ✷

Proof:

  Overlap case (b > m). We consider separately the cases ℓ < b and ℓ > b. If ℓ < b, then we have ℓ = m and |w e | = 2b by inequality (2). It follows that w e is composed of two consecutive blocks.

Lemma 5 . 3

 53 The Thue-Morse word m is the unique word in T containing a critical factor w of length ℓ > b such that b | ℓ. Moreover, ℓ = 3.

Acknowledgements. The authors wish to thank the anonymous referees for carefully reading the proofs and providing helpful comments that improved the presentation.

† Supported by a NSERC (Canada) scholarship. ‡ Research supported by a NSERC (Canada) grant. § Supported by CRM-ISM-LaCIM postdoctoral fellowship (Montréal, Canada). ¶ Supported by a NSERC (Canada) scholarship.

1365-8050

First we show that E(t) ≥ E b,m . If b ≤ m, it is easy to see that there is a square in the first two blocks of t, as noticed in [START_REF] Allouche | Sums of digits, overlaps, and palindromes[END_REF]. On the other hand, if b > m, there exists a 2b/m-power in t. Indeed, let β 2 we know that there exists a factor x of length ℓ and a rational f ≥ e such that both x and x f are synchronized with the blocks. Let p be the proper prefix of x such that

By the induction hypothesis, we have

✷ 5 Occurrences of critical factors

In this section, we assume that t is aperiodic, i.e., m | (b -1). We say that b > m is the overlap case and that b ≤ m is the square case and denote by e the critical exponent of t.

Here, we describe the occurrences and the lengths of the critical factors of t.

Lemma 5.1 Let w be a critical factor of t of length ℓ. Then the following properties hold.

If w e is not synchronized with the blocks, then Lemma 4.1 contradicts the maximality of e. Therefore, both w and w e are synchronized and their preimages under µ are well-defined. Finally, from inequality (3), we obtain the index of the preimage. ✷

In view of Lemma 5.1, it is enough to consider only the case b | ℓ when describing the occurences of critical factors of length ℓ in t.

✷ From Bezout's Identity, we know that for any x, y ∈ Z there exist s, t ∈ Z such that gcd(x, y) = sx+ty where s can be chosen positive. Let g ∈ Z and

The set S g x,y is non-empty when gcd(x, y) | g. Moreover, let us define the following three sets:

We are now ready to state the main theorem of this section, which gives the set of occurrences where critical factors in an aperiodic generalized Thue-Morse word t realize the critical exponent e = E(t).

The proof of Theorem 5.5 follows easily from Lemma 5.1 and the next lemma. Lemma 5.6 Let w be a critical factor of t of length ℓ such that b | ℓ. Then, the set of occurrences of w e in t is

Proof: Overlap case (b > m). From Lemma 5.2, we know that w e = β 1 β 2 , where β 1 and β 2 are blocks. Suppose p is an occurence of w e and let kb q be the starting position of β 2 where b | k and k, q ∈ N + . Then p = kb qb. Now, let γ 1 = t[kb q -1] be the last letter of β 1 and α 2 = t[kb q ] be the first letter of β 2 . Since w e = β 1 β 2 is σ-cyclic from Lemma 3.3, we have

and hence m | q(b -1). Therefore, there exists t ∈ Z such that mt = q(b -1). In particular, we have m = q(b -1) -(t -1)m where q ∈ S m b-1,m which ends the first part.

Square case (b ≤ m). If we write w 2 = w (1) w (2) , then from Lemma 5.2 we know that w (2) occurs at the beginning of a block. We distinguish two cases. First consider the case ℓ < b. Suppose p is an occurrence of w 2 and let kb q be the starting position of w (2) (i.e., the second block) where b | k and k, q ∈ N + . Then p = kb qℓ, and hence

The last equation holds if and only if m divides q(b -1)ℓ, in which case there exists t ∈ Z such that ℓ = q(b -1)tm, that is q ∈ S ℓ b-1,m . Now consider ℓ > b. From Lemma 5.

From Lemma 5.6, we obtain the following easy fact generalizing Theorem 7(a) in [START_REF] Allouche | Sums of digits, overlaps, and palindromes[END_REF], which states that t contains the square of a single letter if and only if gcd(b -1, m) = 1. ✷


C Robinson Tompkins
email: tompkicr@math.sc.edu

Latin Square Thue-Morse Sequences are Overlap-Free

Keywords:

Introduction

In his 1912 paper, Axel Thue introduced the first binary sequence that does not contain an overlap [START_REF] Thue | Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen[END_REF]. It is now called the Thue-Morse sequence: 01101001100101101001011001101001 . . . . An overlap is a string of letters in the form cxcxc where c is a single letter and x is finite string that is potentially empty. Overlaps begin with a square, namely ww where w = cx as given above. It is easy to observe, as Thue did, that any binary string of four or more letters must contain a square.

There are several ways to define the Thue-Morse sequence [START_REF] Allouche | The ubiquitious Prouhet-Thue-Morse sequence[END_REF]. We will derive it as a fixed point of a morphism. Let Σ be an alphabet and let Σ * ∪ Σ ω be the set of all finite or infinite strings over Σ. A morphism is a mapping h : Σ * ∪ Σ ω → Σ * ∪ Σ ω that obeys the identity h(xy) = h(x)h(y), for x a finite string and y ∈ Σ * ∪ Σ ω [1, p. 8].

By [1, p. 16], define the Thue-Morse morphism on Σ = {0, 1} as µ(t) = 01, for t = 0 10, for t = 1 .

(

) 1
The sequence found by applying 0 to the the nth iterate of µ converges to the Thue-Morse sequence, We can identify the binary alphabet of the Thue-Morse sequence with Z/2Z the integers modulo 2. It is natural to then generalize it to Z/nZ, by considering the alphabet Σ = {0, 1, . . . , n -1}, and for i ∈ Σ, defining the morphism

φ n (i) = i + 0 i + 1 . . . i + (n -1),
where i is the residue modulo n. Notice that for Σ = {0, 1}, φ 2 (i) = µ(i). In 2000, Allouche and Shallit proved that φ ω n is overlap-free [START_REF] Allouche | Sums of Digits, Overlaps, and Palindromes[END_REF]. In this paper, we generalize φ n , which is based on the Cayley table of Z/nZ, to Latin squares of arbitrary finite size n. We define our morphism based the Latin square, and prove that the fixed point of the Latin square morphism is an overlap-free sequence. Note that the Cayley table for Z/nZ is a Latin square, but not every Latin square is a Cayley table.

Latin Square Morphisms produce Tilings

Allouche and Shallit's morphism can be seen as a mapping of i to the i th row (that begins with i) of the Cayley table for Z/nZ. For example when n = 3, we have

φ 3 0 → 0 1 2 1 → 1 2 0 2 → 2 0 1
This suggests a natural generalization to any Latin square.

Begin with a generic alphabet of n letters, which we may assume to be {1, 2, . . . , n}. Recall that a Latin square L is an n×n table with n different letters such that each letter occurs only once in each column and only once in each row. We will concern ourself with the Latin squares in which the first column retains the natural order of our alphabet (1, 2, . . . , n). For n = 3, there are two such Latin squares. The one that does not come from Z/3Z directly is  

1 3 2 2 1 3 3 2 1   .
Let L t denote the t th row of our Latin square L. For each t ∈ Σ we define the Latin square morphism by ℓ(t) = L t . For example we can use the above Latin square for n = 3 to define the following morphism,

ℓ(t) =    132, for t = 1 213, for t = 2 321, for t = 3
Given any t ∈ Σ, ℓ(t), ℓ 2 (t), ℓ 3 (t), . . . converges to a sequence ℓ ω (t), which is a fixed point of the morphism ℓ. So,

ℓ(ℓ ω (t)) = ℓ ω (t) (2)
In fact every fixed point of ℓ is of the form ℓ ω (t) for some t ∈ Σ [1, p. 10].

Express the sequence as ℓ ω (t 1 ) = t 1 t 2 t 3 . . ., so ℓ ω (t 1 ) = ℓ(ℓ ω (t 1 )) = ℓ(t 1 t 2 t 3 . . .) = ℓ(t 1 )ℓ(t 2 )ℓ(t 3 ) . . . Thus, we have a tiling of our sequence (and of the natural numbers) by the rows of our Latin square L.

Again, in terms of our example where n = 3 we have three tiles 132, 213, and 321 and so

ℓ ω (1) = 132321213321213132 . . . = |132|321|213|321|213|132| . . . .
Now, consider the subsequence created by taking the first letter of each tile. Notice that this sequence is in fact our original sequence. Thus our sequence contains itself as a subsequence. These two observations, our sequence as a tiling and our sequence equaling a subsequence of itself, will be critical for the proof of our main result.

3 Overlap-Free Latin Square Sequences

In this section we prove our main result.

Theorem 1 Let Σ = {1, 2, . . . , n}, and let L be an n × n Latin square using the letters from Σ, with the first column in its natural order. For an arbitrary t ∈ Σ, let L t denote the row of L corresponding to t in the first column. If we define the Latin square morphism as

ℓ(t) = L t ,
then we have that for any t ∈ Σ, ℓ ω (t) is an overlap-free sequence.

Remark 1 The Latin square for n = 3 above can be seen to be the Cayley table for Z/3Z with the last two columns transposed. Frid has shown that all morphisms based upon such Latin squares for Z/nZ produce overlap-free sequences as their fixed points [START_REF] Frid | Overlap-Free Symmetric D0L words[END_REF]. Of course not every Latin square comes from a group Cayley table . For an example of a Latin square that is not a group Cayley table see below [4, p. 27].

        1
        Proof: Let ℓ ω (t 1 ) = t 1 t 2 t 3 .
. . so the j th letter in the sequence is t j . Similarly, the m th tile in the sequence is T m . We will be also using the notion of length of a string of letters, meaning the number of letters in a string. For an arbitrary string w the length of w will be denoted |w|. Use r to denote the location of t j on its tile T m , so j = (m -1)n + r with |T m | = n and r ∈ {1, 2, . . . , n}.

Assume for a contradiction that ℓ ω (t 1 ) contains an overlap; moreover that cxcxc is the shortest overlap in ℓ ω (t 1 ). Write ℓ ω (t 1 ) = AcxcxcB, where c is a single letter, x is a finite string with |cx| ≥ n, A is a finite string, and B is the infinite tail of our sequence. We have that |cx| ≥ n (bound by the length of the tiles) because each tile is a permutation of 1, 2, . . . , n, and we cannot have two of the three copies of c contained in one tile. Our subscripts place this overlap in our sequence. For i ∈ {1, 2, 3}, let j i denote the subscript of the i th c. Thus,

A = t 1 • • • t j1-1 c = t j1 = t j2 = t j3 x = t j1+1 • • • t j2-1 = t j2+1 • • • t j3-1 B = t j3+1 t j3+2 t j3+3 • • • , (3)
Our argument proceeds as follows: there are two cases |cx| ≡ 0 (mod n) and |cx| ≡ 0 (mod n). In the first case we use the fact that we have a tiling of ℓ ω (t 1 ) by the rows of a Latin square, to show that the overlap cxcxc is not possible. In the second case, when |cx| ≡ 0 (mod n), we argue based upon the fact that ℓ ω (t 1 ) contains itself as a subsequence that the existence of the overlap cxcxc leads to the existence of a shorter overlap, and thus a contradiction.

Case 1: |cx| ≡ 0 (mod n)

For each i ∈ {1, 2, 3}, let r i ∈ {1, 2, . . . , n} such that r i ≡ j i (mod n). In other words t ji is the r th i letter in its tile in ℓ ω (t 1 ). Also, we will refer to the tile containing t ji as T mi . It is now possible to write the length of cx as |cx| ≡ r 2r 1 ≡ r 3r 2 (mod n). So,

r 3 ≡ 2r 2 -r 1 (mod n).
(4)

Six Cases

Since r 2r 1 ≡ |cx| ≡ 0 (mod n) there are two main cases that we will first consider: r 1 < r 2 and r 2 < r 1 . However, for the explicit details of our conclusions we will consider all six of the following possibilities depending on the value of r 3 ,

r 3 = 2r 2 -r 1 ←→ r 1 < r 2 < r 3 r 3 < r 2 < r 1 r 3 = 2r 2 -r 1 -n ←→ r 1 ≤ r 3 < r 2 r 3 < r 1 < r 2 r 3 = 2r 2 -r 1 + n ←→ r 2 < r 1 ≤ r 3 r 2 < r 3 < r 1
The equalities on the left arise out of equation ( 4) and the fact that the integer 2r 2r 1 satisfies, -n ≤ 2r 2r 1 ≤ 2n. This means that r 3 is the element in the set {2r 2r 1 + n, 2r 2r 1 , 2r 2r 1 -n} that lies in the interval 0 < r 3 ≤ n. Notice that r 3 = 2r 2r 1 in both cases when r 1 < r 2 and r 2 < r 1 .

G and the beginning of each cx

When r 1 < r 2 , we pick G ⊂ Σ to be the last r 2r 1 letters in T m1 such that G has no specific order and G = ∅. Of course, the remainder of the letters in T m1 are in G, the complement of G. Notice that this puts c = t j1 ∈ G. By equating the letters in T m1 with the corresponding letters in t j2 xt j3 , we find that the last nr 2 + 1 letters of T m2 (starting with c = t j2 ) are in G. Also, we find that the first r 2r 1 letters of T m2+1 are G. When r 2 < r 1 , we pick G ⊂ Σ to be the last r 1r 2 letters in T m2 such that G has no specific order and G = ∅. Obviously, the remainder of letters in T m2 must be those that make up G again placing c = t j2 ∈ G. By equating the letters in T m2 with the corresponding letters in t j1 xt j2 we find that the last nr 1 + 1 letters of T m1 (starting with c = t j1 ) are in G. Also, we find that the first r 1r 2 letters of T m1+1 are G.

We have discussed the appearance of G and its complement G in the beginning of each cx. So, we set forth to describe G and G at the end of each cx.

Following G through the overlap

It is a basic observation that because each tile is a permutation of the letters in Σ, each tile can be partitioned into G and its complement G. It is fundamental to our argument that because of the equality t j1 xt j2 = cxc = t j2 xt j3 , the letters in G form a contiguous collection of elements in each tile involved in our overlap excluding T mi (each of which will need further description), either the beginning or the ending of each tile. The idea involved in following G through the overlap is quite simple, we illustrate it in one particular case r 1 < r 2 < r 3 .

We have explicitly described the location of G at the beginning of each cx. We will now use our example r 1 < r 2 < r 3 to show to the reader how the tiling of our sequence can be used to find the location of G at the end of each cx. In doing so, we will refer to Figure 1.

In Figure 1, we have displaced the overlap from our sequence (represented by the continuous solid horizontal line). We have also split our overlap in half leaving T m2 intact for equality purposes. We have placed t j1 xt j2 over t j2 xt j3 with t j1 directly over t j2 and t j2 directly over t j3 so that we can see equality of terms simply by looking straight up or straight down (displayed by vertical arrows). The set of letters G is represented by a horizontal solid line above and below our sequence line, and the set of letters G is represented by horizontal dotted lines above and below the sequence line. Also, notice that we have drawn in the edges of the tiles with smaller vertical black lines.

tj 1 tj 2 G G G G tj 2 tj 3 O O O O O O O O O O O O O O • • • Figure 1: The situation when r 1 < r 2 < r 3 .
Now notice that by using the tiles we can equate letters in t j1 xt j2 with t j2 xt j3 all the way through the overlap. Since we know that G occurs in the first r 2r 1 letters of T m2+1 , then G is the last n -(r 2r 1 ) letters of T m2 + 1. This causes G to be the first n -(r 2r 1 ) letters of T m1+1 , and thus G appears in the last r 2r 1 letters of T m1+1 . Thus we can conclude that G occurs in the last r 2r 1 letters of all the tiles in t j1 xt j2 except for T m2 . We can also conclude that G occurs in the first r 2r 1 letters of all the tiles in t j2 xt j3 up through T m3-1 . We can approach every case by the same process.

G and how each cx ends

We now will explain the conclusions for the six possible cases that we defined earlier, leaving the actual drawing to the reader.

Case r 1 < r 2 < r 3 (as seen in Figure 1). After we follow G through the overlap, we find that G occurs in the first r 2r 1 letters of T m3 . Recall r 3 = 2r 2r 1 . So, we have that the next r 3 -(r 2r 1 ) = r 2 letters of T m3 are not in G. Notice that the size of G, r 2r 1 , added to r 2 make up all of r 3 . This places the boundary between T m2-1 and T m2 exactly in line with the end of G in T m3 and the beginning of G. We then equate the first letters in T m3 with those in T m2 to find that G occurs nowhere in T m2 . So now, we have described T m2 fully. Earlier we defined G such that G occurred from t j2 to the end of the tile, and we have just shown that the first r 2 letters of T m2 (which includes t j2 ) must be in G. So G does not appear in anywhere in T m2 , and since G = ∅, we must have a contradiction.

Cases r 1 ≤ r 3 < r 2 and r 3 < r 1 < r 2 . After we follow G through the overlap, we find that G occurs in the first r 2r 1 letters of T m3-1 . So, G occurs in the final n -(r 2r 1 ) letters of T m3-1 causing the first n -(r 2r 1 ) letters of T m2 to be G. Notice that r 2 = [n -(r 2r 1 )] + r 3 . So the boundary between G and G in T m2 coincides with the boundary between T m3-1 and T m3 . This means that t j2 ∈ G, but we assumed that c / ∈ G earlier which is a contradiction.

Case r 3 < r 2 < r 1 . After we follow G through the overlap, we find that G occurs in the last r 1r 2 letters of T m3-1 . This causes G to occur in the first r 1r 2 letters of T m2 by equality of t j1 xt j2 and t j2 xt j3 . To describe the remaining letters of T m2 up to and including t j2 consider r 2 -(r 1r 2 ) = r 3 . So G occurs in the next r 3 letters after G. Thus we have that G is repeated twice in T m2 so we have our contradiction.

Cases r 2 < r 1 ≤ r 3 and r 2 < r 3 < r 1 . After we follow G through the overlap we find that G occurs in the first r 1r 2 letters of T m2-1 . This causes G to occur in the final n -(r 1r 2 ) letters of T m2-1 and thus the first n -(r 1r 2 ) letters of T m3 . Since r 2 = r 3 -[n -(r 1r 2 )], we see that the left boundary of T m2 coincides with the right boundary of these first n -(r 1r 2 ) letters of T m3 . In particular, this means that the last r 1r 2 letters of T m3 , which include c, are in G. But, this contradicts the fact that c / ∈ G.

Case 2: |cx| ≡ 0 (mod n)

We begin by considering some π ∈ S n the symmetric group on n letters. Note that we may apply π to any string by requiring π to act on each individual letter, so π(t

: N → N by d (a,n) (m) = (m -1
)n + a. Now if we let M = (t s ) be a sequence, then define the sequence given by the function D (a,n) (M ) to be the subsequence (t d (a,n) (s) ) of M . So for i ∈ {1, 2, . . . , n} arbitrary we have that

D (i,n) (ℓ ω (t 1 )) = t i t i+n t i+2n . . . . Define π i : Σ → Σ with π i ∈ S n , such that if L t1 = {t 1 , t 2 , . . . , t i , . . . , t n }, π i (t 1 ) = t i .
Recall that L t refers to the t th row of our Latin square L. So we have that π i maps each letter in the first column of our Latin square, to the i th letter of its corresponding row. Now, we want to show that π i (ℓ ω (t)) = D (i,n) (ℓ ω (t)) for all t ∈ Σ. So take D (i,n) (ℓ ω (t 1 )) = D (i,n) (ℓ(ℓ ω (t 1 )) = D (i,n) (ℓ(t 1 )ℓ(t 2 )ℓ(t 3 ) • • • ) = π i (t 1 )π i (t 2 )π i (t 3 ) • • • = π i (ℓ ω (t 1 )).

Since π i ∈ S n is invertible we can conclude that D (i,n) (ℓ ω (t 1 )) contains an overlap if and only if ℓ ω (t 1 ) contains an overlap. Since |cx| ≡ 0 (mod n) pick i ≡ j 1 ≡ j 2 ≡ j 3 (mod n). By applying D (i,n) to (4) we obtain

D (i,n) (ℓ ω (

  1365-8050 c 2007 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France denoted µ ω (0), which of course is infinite. In particular,µ(0) = 01 µ 2 (0) = µ(µ(0)) = µ(01) = µ(0)µ(1) = 0110 µ 3 (0) = µ(µ 2 (0)) = µ(0110) = 01101001 . . . µ ω (0) = 01101001100101101001011001101001 . . . .Notice that µ ω (µ(0)) = µ ω (0) and µ(µ ω (0)) = µ ω (0). This second observation says that the Thue-Morse sequence is a fixed point of µ [1, p. 10].

  t 1 )) = A i t j1 x i t j2 x i t j3 B iwhereA i = D (i,n) (A) = t i t i+n t i+2n . . . , x i = D (i,n) (x) = t j1+n t j1+2n . . . t j1+(m-1)n = t j2+n t j2+2n . . . t j2+(m-1)n , B i = D (i,n) (B) = t j3+n t j3+2n t j3+3n . . . ,and m = |cx|/n. Observe that D (i,n) (ℓ ω (t 1 )) contains a shorter overlap which implies that ℓ ω (t 1 ) also contains a shorter overlap, a contradiction of our assumption. ✷4 AcknowledgementsI would like to thank Dr. Griff Elder, my research advisor for his guidance. I would also like to thank Dr. Dan Farkas for introducing me to the Thue-Morse sequence at Virginia Tech's Undergraduate Research workshop in 2006 funded by the NSA and for the idea that lead to the argument for |cx| ≡ 0 (mod n).Lastly, I would like to thank the referees and Professor Anca Muscholl for helping me correct my notation.