ISSN 2590-9770 The Art of Discrete and Applied Mathematics 4 (2021) #P3.14 https://doi.org/10.26493/2590-9770.1408.f90 (Also available at http://adam-journal.eu) Connected geometric (nk) configurations exist for almost all n Leah Wrenn Berman Department of Mathematics and Statistics, University of Alaska Fairbanks, 513 Ambler Lane, Fairbanks, AK 99775, USA Gábor Gévay* Bolyai Institute, University of Szeged, Aradi vértanúk tere 1, Szeged, 6720 Hungary Tomaž Pisanski† University of Primorska, Koper, Slovenia, and Institute of Mathematics, Physics and Mechanics, University of Ljubljana, Ljubljana, Slovenia Received 10 March 2021, accepted 14 April 2021, published online 30 September 2021 Abstract In a series of papers and in his 2009 book on configurations Branko Grünbaum de- scribed a sequence of operations to produce new (n4) configurations from various input configurations. These operations were later called the “Grünbaum Incidence Calculus”. We generalize two of these operations to produce operations on arbitrary (nk) configurations. Using them, we show that for any k there exists an integer Nk such that for any n ≥ Nk there exists a geometric (nk) configuration. We use empirical results for k = 2, 3, 4, and some more detailed analysis to improve the upper bound for larger values of k. IN MEMORY OF BRANKO GRÜNBAUM Keywords: Axial affinity, geometric configuration, Grünbaum calculus. Math. Subj. Class.: 51A45, 51A20, 05B30, 51E30 *Corresponding author. Supported by the Hungarian National Research, Development and Innovation Office, OTKA grant No. SNN 132625. †Supported in part by the Slovenian Research Agency (research program P1-0294 and research projects N1- 0032, J1-9187, J1-1690, N1-0140, J1-2481), and in part by H2020 Teaming InnoRenew CoE. E-mail addresses: lwberman@alaska.edu (Leah Wrenn Berman), gevay@math.u-szeged.hu (Gábor Gévay), tomaz.pisanski@fmf.uni-lj.si (Tomaž Pisanski) cb This work is licensed under https://creativecommons.org/licenses/by/4.0/ 2 Art Discrete Appl. Math. 4 (2021) #P3.14 1 Introduction In a series of papers and in his 2009 book on configurations [11], Branko Grünbaum de- scribed a sequence of operations to produce new (n4) configurations from various input configurations. These operations were later called the “Grünbaum Incidence Calculus” [13, Section 6.5]. Some of the operations described by Grünbaum are specific to producing 3- or 4-configurations. Other operations can be generalized in a straightforward way to pro- duce (nk) configurations from either smaller (mk) configurations with certain properties, or from (mk−1) configurations. LetNk be the smallest number such that for any n, n ≥ Nk there exists a geometric (nk) configuration. For k = 2 and k = 3, the exact value of Nk is known, and for k = 4 it is known that N4 = 20 or 24. We generalize two of the Grünbaum Calculus operations in order to prove that for any integer k there exists an integer Nk and we give bounds on Nk for k ≥ 5. The existence of geometric 2-configurations is easily established. The only (connected) combinatorial configuration (n2) is an n-lateral. For each n, n ≥ 3, an n-lateral can be realized as a geometric multilateral (for the definition of a multilateral, see [11]). As a specific example, an (n2) configuration can be realized as a regular n-gon with sides that are extended to lines. (For larger values of n it can also be realized as an n-gonal star- polygon, but the underlying combinatorial structure is the same.) Hence: Proposition 1.1. A geometric (n2) configuration exists if and only if n ≥ 3. In other words, N2 = 3. For 3-configurations, N3 is known to be 9 (see [11, Section 2.1]); for example, Branko Grünbaum provides a proof (following that of Schröter from 1888, see the discussion in [11, p. 65]) that the cyclic combinatorial configuration C3(n), which has starting block [0, 1, 3], can always be realized with straight lines for any n ≥ 9. That is: Proposition 1.2. A geometric (n3) configuration exists if and only if n ≥ 9. In other words, N3 = 9. Note that there exist two combinatorial 3-configurations, namely (73) and (83), that do not admit a geometric realization. For k = 4, the problem of parameters for the existence of 4-configurations is much more complex, and the best boundN4 is still not known. For a number of years, the smallest known 4-configuration was the (214) configuration which had been studied combinatorially by Klein and others, and whose geometric realization, first shown in 1990 [12], initiated the modern study of configurations. In that paper, the authors conjectured that this was the smallest (n4) configuration. In a series of papers [6, 7, 8, 9] (summarized in [11, Sections 3.1-3.4]), Grünbaum showed thatN4 was finite and less than 43. In 2008, Grünbaum found a geometrically realizable (204) configuration [10]. In 2013, Jürgen Bokowski and Lars Schewe [3] showed that geometric (n4) configurations exist for all n ≥ 18 except possibly n = 19, 22, 23, 26, 37, 43. Subsequently, Bokowski and Pilaud [1] showed that there is no geometrically realizable (194) configuration, and they found examples of realizable (374) and (434) configurations [2]. In 2018, Michael Cuntz [5] found realizations of (224) and (264) configurations. However, the question of whether a geometric (234) geometric configuration exists is currently still open. In this paper, N̄k will denote any known upper bound for Nk and NRk will denote currently best upper bound for Nk. Summarizing the above results, we conclude: L. W. Berman, G. Gévay and T. Pisanski: Connected geometric (nk) configurations 3 Proposition 1.3. A geometric (n4) configuration exists for n = 18, 20, 21, 22 and n ≥ 24. Moreover, either N4 = 20 or N4 = 24 (depending on whether or not a (234) configuration exists). In other words, NR4 = 24. The main result of the paper is the following result. Theorem 1.4. For each integer k ≥ 2 the numbers Nk exist. To simplify subsequent discussions, we introduce the notion of configuration-realiza- bility, abbreviated as realizability, of numbers. A number n is k-realizable if and only if there exists a geometric (nk) configuration. We may rephrase Proposition 1.3 by stating that the numbers n = 18, 20, 21, 22 and n ≥ 24 are 4-realizable. Also note that the number 9 is 2- and 3-realizable but not k-realizable for any k ≥ 4. 2 Generalizing two constructions from the Grünbaum incidence cal- culus In this section, we generalize two constructions of the Grünbaum Incidence Calculus which we will use to prove the existence of Nk for any k. As input to examples of these construc- tions, we often will use the standard geometric realization of the (93) Pappus configuration P , shown in Figure 1. Figure 1: The standard geometric realization of the (93) Pappus configuration P . The first, which we call affine replication and denote AR(m, k), generalizes Grün- baum’s (5m) construction; it takes as input an (mk−1) configuration and produces a ((k + 1)mk) configuration with a pencil of m parallel lines. The second, which we call affine switch, is analogous to Grünbaum’s (3m+) construc- tion. It takes as input a single (mk) configuration with a set of p parallel lines in one direc- tion and a set of q parallel lines in a second direction which are disjoint (in terms of config- uration points) from the pencil of p lines, and it produces a configuration (((k−1)m+r)k) for any r with 1 ≤ r ≤ p+ q. Applying a series of affine switches to a single starting (mk) configuration with a pencil of q parallel lines produces a consecutive sequence (or “band”) of configurations (((k − 1)m+ 1)k), . . . , (((k − 1)m+ q)k) which we will refer to as AS+(m, k, q). 4 Art Discrete Appl. Math. 4 (2021) #P3.14 2.1 Affine replication Starting from an (mk−1) configuration C we construct a new configuration D which is a ((k + 1)mk) configuration. A sketch of the construction is that k − 1 affine images of C are carefully constructed so that each point P of C is collinear with the k − 1 images of P , and each line of C and its images are concurrent at a single point. Then D consists of the points and lines of C and its images, the new lines corresponding to the collinearities from each point P , and the new points of concurrence corresponding to the lines of C and their images. The details of the construction are as follows: (1) Let A be a line that (i) does not pass through the intersection of two lines of C, whether or not that intersection point is a point of the configuration; (ii) is perpendicular to no line connecting any two points of C, whether or not that line is a line of the configura- tion; (iii) intersects all lines of C. (2) Let α1, α2, . . . , αk−1 be pairwise different orthogonal axial affinities with axisA. Con- struct copies C1 = α1(C), C2 = α2(C),. . . , Ck−1 = αk−1(C) of C = C0. (3) Let ` be any line of C. Since A is the common axis of each αi, the point A ∩ ` is fixed by all these affinities. This means that the k-tuple of lines `, α1(`), . . . , αk−1(`) has a common point of intersection lying on A. We denote this point by F`. By condition (i) in (1), for different lines `, `′ ∈ C the points F`, F`′ differ from each other; they also differ from each point of the configurations Ci (i = 1, 2, . . . , k− 1). We denote the set {F` : ` ∈ C} of points lying on A by F . (4) Let P be any point of C. Since the affinities αi are all orthogonal affinities (with the common axis A), the k-tuple of points P, α1(P ), . . . , αk−1(P ) lies on a line perpen- dicular to A (and avoids A, by condition (i)). We denote this line by `P . Clearly, we have altogether m such lines, one for each point of C, with no two of them coinciding, by condition (ii). We denote this set {`P : P ∈ C} of lines by L. (5) Put D = C0 ∪ C1 ∪ · · · ∪ Ck−1 ∪ F ∪ L. The conditions of the construction imply that D is a ((k+ 1)mk) configuration. Moreover, by construction, D has a pencil of m parallel lines. Figures 2 and 3 show two examples of affine replication, first starting with a (42) configuration to produce a (163) configuration, and then starting with the (93) Pappus configuration to produce a (454) configuration. Remark 2.1. The orthogonal affinities used in the construction are just a particular case of the axial affinities called strains [4]; they can be replaced by other types of axial affini- ties, namely, by oblique affinities (each with the same (oblique) direction), and even, by shears (where the direction of affinity is parallel with the axis) [4], while suitably adjusting conditions (i–iii) in (1). We may summarize the above discussion as follows: Lemma 2.2. If affine replication AR(m, k) is applied to any (mk−1) configuration, the result is a (((k + 1)m)k) configuration with a pencil of m parallel lines. L. W. Berman, G. Gévay and T. Pisanski: Connected geometric (nk) configurations 5 Figure 2: Affine replication AR(4, 3) applied to a quadrilateral, i.e. a (42) configuration; it results in a (163) configuration. The corresponding ordinary quadrangles are shaded (the starting, hence each of the three quadrangles are parallelograms). The axis A is shown by a dashed line. 2.2 Affine switch In our description of this construction, we are inspired by Grünbaum [11, §3.3, pp. 177– 180] but we have chosen a slightly different approach (in particular, we avoid using 3- space). At the same time, we generalize it from (m4) to (mk). A sketch of the construction is as follows: Suppose that C is an (mk) configuration that contains a pencil P of p parallel lines in one direction, and a pencil Q of q parallel lines in a second direction, where the two pencils share no common configuration points; we say that the pencils are independent. For each subpencil S of P and T of Q containing s parallel lines and t parallel lines respectively, with 1 ≤ s ≤ p and 0 ≤ t ≤ q, we form the subfiguration Ĉ by deleting S and T from C (here we use the term subfiguration in the sense of Grünbaum [11]). We then carefully construct k−2 affine images of Ĉ in such a way that for each (deleted) line ` in S and for each point P1, P2, . . . , Pk on `, the collection of lines through each Pi and its images all intersect in a single point Y`, and simultaneously, for each line `′ in T and for each point Q1, Q2, . . . , Qk on `′, the collection of lines through Qi and its images all intersect in a single point X`′ . Let D be the collection of all the undeleted points and lines of Ĉ and its affine images, and for each of the deleted ` and `′, the new lines through each point Pi Qi and their images, the points Y`, and the points X`′ ; then D is a (((k − 1)m+ s+ t)k) configuration. As a preparation, we need the following two propositions. Proposition 2.3. Let α be a (non-homothetic) affine transformation that is given by a diagonal matrix with respect to the standard basis. Note that in this case α can be written as a (commuting) product of two orthogonal affinities whose axes coincide with the x- and y-axis, respectively:( a 0 0 b ) = ( a 0 0 1 )( 1 0 0 b ) = ( 1 0 0 b )( a 0 0 1 ) . 6 Art Discrete Appl. Math. 4 (2021) #P3.14 Figure 3: Affine replication AR(9, 4) applied to the (93) Pappus configuration, which yields a (454) configuration. The starting figure is indicated by thick segments, while the first image is highlighted by red segments. The axis A is shown by a dashed line. The construction is chosen so as to exemplify that ordinary mirror reflection can also be used. Note that the resulting configuration contains a pencil of 9 parallel lines arising from the construction, shown in green. L. W. Berman, G. Gévay and T. Pisanski: Connected geometric (nk) configurations 7 Let P0(x0, 0), P1(x0, y1), . . . , Pk(x0, yk) be a range of k + 1 different points on a line which is perpendicular to the x-axis and intersects it in P0. Then the k lines connecting the pairs of points (P1, α(P1)), . . . , (Pk, α(Pk)) form a pencil with centre Cx such that Cx lies on the x-axis, and its position depends only on α and x0. Likewise, letQ0(x0, y0), Q1(x1, y0), . . . , Qk(xk, y0) be a range of k+1 different points on a line which is perpendicular to the y-axis and intersects it in Q0. Then the k lines connecting the pairs of points (Q1, α(Q1)), . . . , (Qk, α(Qk)) form a pencil with centre Cy such that Cy lies on the y-axis, and its position depends only on α and y0. Proof. An elementary calculation shows that Cx = Cx ( 0, a− b b− 1 x0 ) , resp. Cy = Cy ( 0, b− a a− 1 y0 ) is the common point of intersection of any two, hence of all the lines in question. Proposition 2.4. Let h ≥ 3 be a positive integer, and for each j with j = 1, . . . , h− 1, let the affine transformation αj be given by the matrix Mj =  h− jh 0 0 h+ j h  . (2.1) Then for any point P , the points P, α1(P ), . . . , αh−1(P ) are collinear. Proof. Choose any j′ and j′′, and form the difference matrices Mj′ − U and Mj′′ − U with the unit matrix U . Observe that these matrices are such that one is a scalar multiple of the other. Hence the vectors −−→ PP ′ and −−→ PP ′′ are parallel, where P ′ = αj′(P ) and P ′′ = αj′′(P ). This means that the points P , P ′ and P ′′ lie on the same line. Now we apply the following construction. Let C be an (mk) configuration such that it contains a pencil P of p ≥ 1 parallel lines and a pencil Q of q ≥ 1 parallel lines, too, such that these pencils are perpendicular to each other and are independent. Note that any configuration containing independent pencils in two different directions can be converted by a suitable affine transformation to a configuration in which these pencils will be perpendicular to each other. Choose a position of C (applying an affine transformation if necessary) such that these pencils are parallel to the x-axis and y-axis, respectively. (1) Remove lines `1, . . . , `s (s ≤ p) from the pencil P parallel to the x-axis and `s+1, . . . , `s+t (0 ≤ t ≤ q) from the pencil Q parallel to the y-axis. Let Ĉ denote the substructure of C obtained in this way. (2) Let h be a positive integer (say, some suitable multiple of k), and for each j, j = 1, . . . , k − 2, let αj be an affine transformation defined in Proposition 2.4. Form the images αj(Ĉ) for all j given here. 8 Art Discrete Appl. Math. 4 (2021) #P3.14 Figure 4: Illustration for Propositions 2.3 and 2.4. Affine transformations with parameters h = 8 and j = 1, . . . 5 are applied on a square. (3) Let P be a point of Ĉ that was incident to one of the lines `i removed from C. Take the images αj(P ) for all j given in (2). By Proposition 2.4, all the k − 1 points P, αj(P ) are collinear. Let ci(P ) denote this line. (4) Take all the configuration points on `i and repeat (3) for each of them. By Proposi- tion 2.3, the k-set of lines {ci(P ) : P ∈ `i} form a pencil whose centre lies on the x-axis or the y-axis according to which axis `i is perpendicular to. (5) Let r = (s + t) ∈ {1, 2, . . . , p + q} be the number of lines removed from the pencils of C in the initial step of our construction. Repeat (4) for all these lines. Eventually, we obtain rk new lines and r new points such that the set of the new lines is partitioned into r pencils, and the new points are precisely the centres of these pencils (hence they lie on the coordinate axes). Observe that there are precisely k lines passing through each of the new points, and likewise there are precisely k points lying on each of the new lines. (6) Putting everything together, we form a (((k − 1)m+ r)k) configuration, whose • points come from the (k − 1)m points of the copies of Ĉ, completed with the r new points considered in (5). • lines come from the (k − 1)(m− r) lines of the copies of Ĉ, completed with the rk new lines considered in (5). We use the notation AS(m, k, r) to represent the (((k − 1)m + r)k) configuration described above. Summarizing the discussion above, we conclude: Lemma 2.5. Beginning with any (mk) configuration with independent pencils of p ≥ 0 and q ≥ 1 parallel lines, for each integer r with 1 ≤ r ≤ p + q, the affine switch construction produces an (nk) configuration, where n = (k − 1)m+ r. L. W. Berman, G. Gévay and T. Pisanski: Connected geometric (nk) configurations 9 Note that p+q independent lines in an (mk) configuration covers k(p+q) ≤ m points. This gives an upper bound p + q ≤ m/k, where the equality is attained only if m divides k. In this paper we use the above Lemma 2.5 in connection with Lemma 2.2 only for the case of a single pencil of parallel lines, such that p = 0. Corollary 2.6. From any starting (mk) configuration that has a pencil of q parallel lines, we can apply a sequence of affine switches by removing 1, 2, . . . , q lines in sequence, so as to construct a sequence of consecutive configurations [(((k − 1)m+ r)k)]qr=1 = [AS(m, k, r)] q r=1. This collection of consecutive configurations is represented by the notation AS+(m, k, q). That is, AS+(m, k, q) = [AS(m, k, r)]qr=1. Example 2.7. Figure 5 illustrates an application of this construction to the Pappus configu- rationP (cf. Figure 1). Removing only one line from the horizontal pencil results in a (193) configuration, shown in Figure 5(a). Removing two or three lines results in a (203) or (213) configuration, respectively, shown in Figures 5(b) and 5(c). (Observe that since the Pappus configuration has 9 points, the maximal total number of lines in independent pencils is 3, since any three disjoint lines in the configuration contain all the points of the configuration.) Taken together the three configurations, we have: [(193), (203), (213)] = AS+(9, 3, 3). (a) A (193) configuration (b) A (203) configuration (c) A (213) configuration Figure 5: Configurations (193), (203), and (213), constructed by applying the affine switch construction to the realization of the Pappus configuration with a pencil of 3 parallel lines, shown in Figure 1, by deleting one, two, or three lines respectively. (The vertical axis of affinity, denoted by dashed line, does not belong to the configuration.) Since axial affinities play a crucial role in the constructions described above, we recall a basic property. The proof of the following proposition is constructive, hence it provides a simple tool for a basically synthetic approach to these constructions, which is especially useful when using dynamic geometry software to construct these configurations. 10 Art Discrete Appl. Math. 4 (2021) #P3.14 Proposition 2.8. An axial affinity α is determined by its axis and the pair of points (P, P ′), where P is any point not lying on the axis, and P ′ denotes the image of P , i.e. P ′ = α(P ). Proof. In what follows, for any point X , we denote its image α(X) by X ′. Let Q be an arbitrary point not lying on the axis and different from P . Take the line PQ, and assume that it intersects the axis in a point F (see Figure 6a). Thus PQ = FP . Take now the line F ′P ′, i.e., the image of FP . Since F is a fixed point, i.e. F ′ = F , we have F ′P ′ = FP ′. This means that Q′ lies on FP ′, i.e. P ′Q′ = FP ′. To find Q′ on FP ′, we use the basic property of axial affinities that for all points X not lying on the axis, the lines XX ′ are parallel with each other (we recall that the direction of these lines is called the direction of the affinity). Accordingly, a line passing through Q which is parallel with PP ′ will intersect FP ′ precisely in the desired point Q′. (a) (b) Figure 6: Construction of the image of a pont Q under axial affinity; the axis is the vertical red line, the direction of affinity is given by the blue line. Here we use oblique affinity, but the construction given in the proof is the same in any other types of axial affinities. On the other hand, if PQ is parallel with the axis, then clearly so is P ′Q′. In this case Q′ is obtaned as the fourth vertex of the parallelogram determined by P ′, P and Q (see Figure 6b). Remark 2.9. In using integer parameters h and j above, we followed Grünbaum’s original concept [11] (as mentioned explicitly at the beginning of this subsection). However, the theory underlying Propositions 2.3 and 2.4 makes possible using continuous parameters as well, so that the procedure becomes in this way much more flexible. In what follows we outline such a more general version, restricted to using only one pencil of lines to be deleted. Start again with a configuration C, and assume that the pencilP is in horizontal position; accordingly, the axis that we use is in vertical position (see e.g. Figure 5). Choose a line ` in P , and a configuration point P0 on `; then, remove `. P0 will be the initial point of our construction (e.g., in Figure 5 the “north-west” (black) point of the starting configuration). Choose a point C` on the axis such that the line C`P0 is not perpendicular to the axis (in our example, this is the red point in Figure 5a). Now let t ∈ R be our continuous parameter. Take the point P = tC` + (1− t)P0; (2.2) L. W. Berman, G. Gévay and T. Pisanski: Connected geometric (nk) configurations 11 thus P is a point on the line C`P0, and as t changes, P slides along this line. Moreover, by Proposition 2.8 we see that the pair of points (P0, P ) determines two orthogonal affinities whose axes are perpendicular to each other. In particular, the axes are precisely the coor- dinate axes. These affinities act simultaneously, i.e. P0 is sent to P by their (commuting) product. Using coordinates, such as P0(x0, y0) and P (x, y), we also see that the ratio of these affinities is y/y0 (for that with horizontal axis), respectively x/x0 (for that with ver- tical axis). (Note that these ratios, using the relation (2.2), can also be expressed by the parameter t and by the prescribed coordinates of P0 and C`. Furthermore, similarly, the matrix (2.1) above can also be parametrized by t; we omit the details.) It is easily checked that both Proposition 2.3 and Proposition 2.4 remains valid with this continuous parameter t. Hence, for any P , we can construct the corresponding affine image of C (or its substructures Ĉ with lines of any number r removed), together with the new lines (which are denoted by red in our example of Figure 5). In particular, in case of k-configurations, we need to choose altogether k − 2 points on the line C`P0 (note the for t = 0, the starting copy C returns; for t = 1 the image of C collapses to a segment within the y-axis, and for a third value depending on the slope of C`P0, it collapses to a segment within the x-axis; these cases thus are to be avoided). 3 Proof of the main theorem In this section we prove the main theorem of our paper. For notational convenienence, given integers a < b, let [a : b] denote the range {a, a + 1, . . . , b}. Similarly, for integer function f(s) the range {f(a), f(a + 1), . . . , f(b)} will be denoted by [f(s)]bs=a. The crucial step in the proof will be provided by the following Lemma. Lemma 3.1. Assume that for some k ≥ 3, Nk−1 exists and that N̄k−1 is any known upper bound for it. Then Nk exists and: N̄k = (k2 − 1) max(N̄k−1, k2 − 2) is an upper bound for it. Moreover, if we have two upper bounds, say N̄k−1 < Ñk−1 for Nk−1, the better one will produce a better upper bound for Nk. This Lemma will be proven with the tools from previous section by applying affine replication and affine switch. More precisely, Lemma 2.2 and Corollary 2.6 will be used. Proof of Lemma 3.1. Let N̄k−1 denote any known upper bound for Nk−1. By definition, the sequence of consecutive numbers a = N̄k−1, a+ 1, . . . , a+ s, . . . (3.1) are all (k− 1)-realizable; in other words, for each s, s = 0, 1, . . . , there exists a geometric ((a+ s)k−1) configuration (recall the definition of realizability, given in the Introduction). Apply affine replication to these configurations; by Lemma 2.2, the sequence of numbers (k + 1)a, (k + 1)(a+ 1), . . . , (k + 1)(a+ s), . . . (3.2) are all k-realizable. Note that this is an arithmetic sequence with difference (k + 1). Fur- thermore, observe that for eachX ≥ a, the geometric k-configuration realizing the number (k + 1)X that was produced by affine replication has X new parallel lines. Hence, we can apply a sequence of affine switch constructions to each of these configurations ((k+1)Xk). 12 Art Discrete Appl. Math. 4 (2021) #P3.14 By Corollary 2.6, the sequences AS+((k + 1)X, k,X) of configurations is produced. It follows that the sequences of numbers [(k − 1)(k + 1)a+ 1 : (k − 1)(k + 1)a+ a], [(k − 1)(k + 1)(a+ 1) + 1 : (k − 1)(k + 1)(a+ 1) + (a+ 1)], [(k − 1)(k + 1)(a+ 2) + 1 : (k − 1)(k + 1)(a+ 2) + (a+ 2)], . . . (3.3) are all k-realizable. Observe that from the initial outputs of affine replication, n = X(k + 1) is realizable as long as X ≥ N̄k−1. Thus, every “band” of consecutive configurations produced by affine switches can be extended back one step, so there exists a band of consecutive k- configurations [(k − 1)(k + 1)X : (k − 1)(k + 1)X +X)] for each initial configuration (Xk−1). Another way to say this is that we can fill a hole of size 1 between the bands of configurations listed in equation (3.3) using the output of the initial affine replications, listed in equation (3.2). To determine when we have either adjacent or overlapping bands, then, it suffices to determine when the last element of one band is adjacent to the first element of the next band; that is, when (k − 1)(k + 1)X +X + 1 ≥ (k − 1)(k + 1)(X + 1). It follows easily that X ≥ k2 − 2. Hence, as long as we are guaranteed that a sequence of consecutive configurations (qk−1), ((q + 1)k−1), . . . exists, it follows that we are guaranteed the existence of consec- utive k-configurations Qk, (Q + 1)k, . . . , where Q = (k2 − 1)(k2 − 2). However, since we do not know whether that consecutive sequence exists, in the (extremely common) case where N̄k−1 > (k2 − 1)(k2 − 2), the best that we can do is to conclude that Nk ≤ (k2 − 1) max{N̄k−1, k2 − 2}. This result gives rise to an elementary proof by induction for the main theorem. Proof of Theorem 1.4. Let s = 2. The number Ns = N2 = 3 exists. This is the basis of induction. Now, let s = k − 1. By assumption, Nk−1 exists and some upper bound N̄k−1 is known. By Lemma 3.1, N̄k = (k2 − 1) max(N̂k−1, k2 − 2) is an upper bound for Nk. Therefore Nk exists and the induction step is proven. Recall that we let NRk denote the best known upper bound for Nk. The same type of result follows if we start with the best known upper bound NRs for some s ≥ 2. However, the specific numbers for upper bounds depend on our starting condition. Table 1 shows the difference if we start with s = 2, 3, 4. The reason we are using only these three values for s follows from the fact that only NRs , 2 ≤ s ≤ 4 have been known so far. The rightmost column of Table 1 summarises the information given in other columns by computing the minimum in each row and thereby gives the best bounds that are available using previous knowledge and direct applications of Lemma 3.1. L. W. Berman, G. Gévay and T. Pisanski: Connected geometric (nk) configurations 13 Table 1: Bounds on Nk from iterative applications of Lemma 3.1. Different bounds are produced if the iteration is started with NR2 = N2 = 3, N R 3 = N3 = 9 or with N R 4 = 24. Boldface numbers give best bounds using this method and current knowledge. k N̄k with NR2 = 3 N̄k with N R 3 = 9 N̄k with N R 4 = 24 N R k 2 3 - - 3 3 56 9 - 9 4 840 210 24 24 5 20 160 5 040 576 576 6 705 600 176 400 20 160 20 160 7 33 868 800 8 467 200 967 680 967 680 8 2 133 734 400 533 433 600 60 963 840 60 963 840 9 170 698 752 000 42 674 688 000 4 877 107 200 4 877 107 200 10 16 899 176 448 000 4 224 794 112 000 482 833 612 800 482 833 612 800 If new knowledge about best current values of NRk for small values of k becomes available, we may use similar applications of Lemma 3.1 to improve the bounds of the last column. Since, the values for k = 2 and k = 3 are optimal, the first candidate for improvement is k = 4. A natural question is what happens if someone finds a geo- metric (234) configuration. In this case Lemma 3.1 would give us for k = 5 the bound (k2 − 1) max(NRk−1, k2 − 2) = (52 − 1) max(20, 52 − 2) = 24× 23 = 552, an improve- ment over 576. An alternative feasible attempt to improve the bounds would be to use other methods in the spirit of Grünbaum calculus to improve the current bound 576 for k = 5. However, there is another approach that can improve the numbers even without introducing new methods. It is presented in the next section. 4 Improving the bounds Recall that NR3 = N3 = 9, and N R 4 = N4 = 21 or 24, according to whether or not a (234) configuration exists. If we apply the procedure in Lemma 3.1 using as in- put information N3 = NR3 = 9 (that is, beginning with a sequence of 3-configurations (93), (103), (113) . . .), Lemma 3.1 says that Nk ≤ (k2 − 1) max{NRk−1, k2 − 2} =⇒ N4 ≤ (15) max{9, 14} = 210. However, we know observationally that N4 = 21 or 24. Thus, we expect that Theo- rem 1.4 is likely to give us significant overestimates on a bound for Nk for larger k. For k = 5, the best we can do at this step with these constructions is the bound given by Lemma 3.1, beginning with the consecutive sequence of 4-configurations ((244), (254), (264), . . .). In this case, Lemma 3.1 predicts that N5 ≤ (24) max(24, 23) = 576. In a sub- sequent paper, we will show that this bound can be significantly decreased by incorporating other Grünbaum-calculus-type constructions and several ad hoc geometric constructions for 5-configurations. However, we significantly decrease the bound on Nk for k ≥ 6 by refining the con- struction sequence given in Lemma 3.1: instead of beginning with NRk−1 determined by iterative applications of the sequence in Lemma 3.1, we consider all possible sequences determined by applying a series of affine replications, followed by a final affine switch. 14 Art Discrete Appl. Math. 4 (2021) #P3.14 First we introduce a functionN(k, t, a, d) with positive integer parameters k, t, a, d and t < k. Define for t < k − 1: N(k, t, a, d) := (k2 − 1) ( k! (t+ 1)! ) max { a, (k2 − 1)d } , and for t = k − 1: N(k, k − 1, a, d) := (k2 − 1) max { a, (k2 − 1)d− 1 } . This value N(k, t, a, d) is precisely the smallest n after which we are guaranteed there exists a sequence of consecutive k-configurations produced by starting with an initial se- quence of t-configurations a, a + d, ..., and sequentially applying affine replications fol- lowed by a final affine switch as described above. The following Lemma gives us a quite general and powerful tool for bound improve- ments without making any changes in constructions. Lemma 4.1. Let t ≥ 2 be an integer and let a, a+d, a+ 2d, . . . be an arithmetic sequence with integer initial term a and integer difference d such that for each s = 0, 1, . . . geometric configurations ((a + sd)t) exist. Then for any k > t the value N(k, t, a, d) defined above is an upper bound for Nk; i.e., N(k, t, a, d) ≥ Nk. Proof of Lemma 4.1. Beginning with an arithmetic sequence of t-configurations, we con- struct a consecutive sequence of k-configurations by iteratively applying a sequence of affine replications to go from t-configurations to (k − 1)-configurations; a final affine replication to go from (k − 1)-configurations to k-configurations with a known number of lines in a parallel pencil; and finish by applying affine switch on that final sequence of k-configurations to produce bands of consecutive configurations. We then analyze at what point we are guaranteed that the bands either are adjacent or overlap. Specifically, starting with a sequence of t-realizable numbers a, a + d, a + 2d, . . . we successively apply k−t affine replications to the corresponding sequence of configurations to form sequences of s-realizable numbers for t ≤ s ≤ k: a, a+ d, a+ 2d, . . . AR(·,t+1)−−−−−−→ (t+1)-cfgs (t+ 2)a, (t+ 2)(a+ d), (t+ 2)(a+ 2d), . . . AR(·,t+2)−−−−−−→ (t+2)-cfgs (t+ 3)(t+ 2)a, (t+ 3)(t+ 2)(a+ d), (t+ 3)(t+ 2)(a+ 2d), . . . ... AR(·,k)−−−−−→ k-cfgs (k + 1)! (t+ 1)! a, (k + 1)! (t+ 1)! (a+ d), (k + 1)! (t+ 1)! (a+ 2d), . . . (4.1) By Lemma 2.2, each of the k-configurations corresponding to the realizable numbers in equation (4.1) produced from a starting configuration X has a pencil of k!(t+1)!X parallel L. W. Berman, G. Gévay and T. Pisanski: Connected geometric (nk) configurations 15 lines. To those configurations we apply the affine switch operation: (k + 1)! (t+ 1)! a, (k + 1)! (t+ 1)! (a+ d), (k + 1)! (t+ 1)! (a+ 2d), . . . AS+(·,k,·)−−−−−−→ k-cfgs [ (k − 1)(k + 1)! (t+ 1)! a+ 1 : (k − 1)(k + 1)! (t+ 1)! a+ k! (t+ 1)! q ] ,[ (k − 1)(k + 1)! (t+ 1)! (a+ d) + 1 : (k − 1)(k + 1)! (t+ 1)! (a+ d) + k! (t+ 1)! (a+ d) ] , . . . (4.2) As in the proof of Theorem 1.4, observe that the (nk) configurations described in (4.1) all have n as a multiple of (k+1)!(t+1)! . That is, any n divisible by (k+1)! (t+1)! is k-realizable as long as when n = (k+1)!(t+1)!X , X is larger than N R t . We thus can extend our band of consecutive realizable configurations back one step, to be of the form[ (k − 1)(k + 1)! (t+ 1)! X : (k − 1)(k + 1)! (t+ 1)! X + k! (t+ 1)! X ] for a starting t-realizable number X . Successive bands of this form are guaranteed to either exactly meet or to overlap when the end of one band, plus one, equals or is greater to the beginning of the next, that is, when (k − 1)(k + 1)! (t+ 1)! X + k! (t+ 1)! X + 1 ≥ (k − 1)(k + 1)! (t+ 1)! (X + d) =⇒ X ≥ (k2 − 1)d− (t+ 1)! k! . (4.3) When t = k − 1, (t+1)!k! = 1, while when t < k − 1, (t+1)! k! < 1, and moreover, inequality (4.3) holds as long as X is greater than the bound on t-realizable configurations. We refine and improve the upper bounds of Table 1 with Theorem 4.2. This proof proceeds by showing, given a starting arithmetic sequence of consecutive t-configurations, a construction method for producing a sequence of consecutive k-configurations. Theorem 4.2. Recursively define N̂k = (k 2 − 1) min 3≤t 576 (and the values N̂t for 6 ≤ t ≤ 9 much larger than either), the min- imum of that list is actually 10!6! 576, and the computation for N̂10 starts with the sequence of consecutive 5-configurations (5765), (5775), . . . rather than with (244), (254), . . .. Se- quences with t = 5 begin to dominate when 6(k2 − 1) > 576 = (52 − 1)2; that is, when k ≥ d √ 97e = 10. Sequences with t = 6 begin to dominate when 7(k2 − 1) > 6(62 − 1)2 = 7350, or k ≥ ⌈√ 1051 ⌉ = 33. Sequences with t = 7 will dominate when 8(k2 − 1) > 7 · 6 · (72 − 1)2, that is k ≥ d √ 12097e = 110. However, note that these bounds are absurdly large; N̂110 ≈ 4.6× 10182. In addition, observe that since k = 25 is the smallest positive integer satisfying k2−1 > 576, the bounds for N̂25 use the 252−1 choice rather than N̂5 in taking the maximum, even though both N̂24 and N̂25 are starting with the same initial sequence of 5-configurations, and there is a similar transition again at k = 86, when the function is using 6-configurations to produce the maximum. At this position, since 852−1 = 7224 and 862−1 = 7395, N̂85 uses N̂6 = 7350, but N̂86 transitions to using 862 − 1 to compute the maximum. 5 Future work With better boundsNRt developed experimentally for small values of t, in the same way that NR4 = 24 has been determined experimentally, we anticipate significantly better bounds NRk , for k > t, without changing the methods for obtaining the bounds. One obvious approach is to improve the bookkeeping even further. For instance, in Theorem 4.2 we only used arithmetic sequences with d = 1 in N(k, t, a, d) and ignoring any existing configuration (mt) for m < Nt. In particular, for t = 4, we could have used N(k, 4, 18, 2) since 18, 20, 22, 24, . . . form an arithmetic sequence of 4-realizable numbers. Our experiments indicate that this particular sequence has no impact in improving the bounds. However, by carefully keeping track of the existing t-configurations belowNRt , other more productive arithmetic sequences may appear. Another approach is to sharpen the bounds for Nk, for general k. This can be achieved, for instance, by generalizing some other “Grünbaum Calculus” operations, which we plan for a subsequent paper. We also plan to apply several ad hoc constructions for 5- and 6- configurations to further sharpen the bound for N5 and N6, which will, in turn, lead to significantly better bounds for Nk for higher values of k. However, based on the work in- volved in bounding N4 and the fact that N4 is not currently known (and on how hard it was to show the nonexistence of an (194) configuration), we anticipate that even determining N5 exactly is an extremely challenging problem. Finally, very little is known about existence results on unbalanced configurations, that is, configurations (pq, nk) where q 6= k. While some examples and families are known, it would be interesting to know any bounds or general results on the existence of such configurations. ORCID iDs Leah Wrenn Berman https://orcid.org/0000-0003-0935-5724 Gábor Gévay https://orcid.org/0000-0002-5469-5165 Tomaž Pisanski https://orcid.org/0000-0002-1257-5376 18 Art Discrete Appl. Math. 4 (2021) #P3.14 References [1] J. Bokowski and V. Pilaud, On topological and geometric (194) configurations, European J. Combin. 50 (2015), 4–17, doi:10.1016/j.ejc.2015.03.008. [2] J. Bokowski and V. Pilaud, Quasi-configurations: building blocks for point-line configurations, Ars Math. Contemp. 10 (2016), 99–112, doi:10.26493/1855-3974.642.bbb. [3] J. Bokowski and L. Schewe, On the finite set of missing geometric configurations (n4), Com- put. Geom. 46 (2013), 532–540, doi:10.1016/j.comgeo.2011.11.001. [4] H. S. M. Coxeter, Introduction to geometry, John Wiley & Sons, Inc., New York-London- Sydney, 2nd edition, 1969. [5] M. J. Cuntz, (224) and (264) configurations of lines, Ars Math. Contemp. 14 (2018), 157–163, doi:10.26493/1855-3974.1402.733. [6] B. Grünbaum, Which (n4) configurations exist?, Geombinatorics 9 (2000), 164–169. [7] B. Grünbaum, Connected (n4) configurations exist for almost all n, Geombinatorics 10 (2000), 24–29. [8] B. Grünbaum, Connected (n4) configurations exist for almost all n—an update, Geombina- torics 12 (2002), 15–23. [9] B. Grünbaum, Connected (n4) configurations exist for almost all n—second update, Geombi- natorics 16 (2006), 254–261. [10] B. Grünbaum, Musings on an example of Danzer’s, European J. Combin. 29 (2008), 1910– 1918, doi:10.1016/j.ejc.2008.01.004. [11] B. Grünbaum, Configurations of Points and Lines, volume 103 of Graduate Studies in Mathe- matics, American Mathematical Society, Providence, RI, 2009, doi:10.1090/gsm/103. [12] B. Grünbaum and J. F. Rigby, The real configuration (214), J. London Math. Soc. (2) 41 (1990), 336–346, doi:10.1112/jlms/s2-41.2.336. [13] T. Pisanski and B. Servatius, Configurations from a Graphical Viewpoint, Birkhäuser Advanced Texts, Birkhäuser, New York, 2013, doi:10.1007/978-0-8176-8364-1.