J. Geom. 92 (2009), 28–59 c 2009 Birkh¨
auser Verlag Basel/Switzerland 0047-2468/010028-32, published online 30 January 2009 DOI 10.1007/s00022-008-1955-x
Journal of Geometry
A Missing Prime Configuration in the Hausdorff Metric Geometry Chantel C. Blackburn, Kristina Lund, Steven Schlicker, Patrick Sigmon and Alexander Zupan Abstract. The Hausdorff metric h was introduced by Felix Hausdorff in the early 20th century as a way to measure the distance between elements in the hyperspace H(Rn ) of non-empty compact subsets of Rn . The geometry this metric imposes on H(Rn ) has many interesting properties: lines in this geometry can have endpoints; there can be many elements at a given location between two sets in H(Rn ); the Fibonacci and Lucas numbers arise in a natural way in this geometry; and for infinitely many different values of the positive integer k, there is a configuration [A, B] in Rn so that there exist exactly k elements at each location between A and B. In this paper we will show that if k is between 1 and 18, there is always a configuration having exactly k elements at each location between the end elements and prove the surprising result that no such configuration exists if k equals 19. Mathematics Subject Classification (2000). 51F99; 54B20. Keywords. Hausdorff metric, configuration, betweenness, nineteen, metric geometry.
1. Introduction The Hausdorff metric h was introduced by Felix Hausdorff in the early 20th century as a way to measure the distance between compact sets. The geometry this metric imposes on H(Rn ), the hyperspace of all non-empty compact subsets of Rn , has many interesting properties. In [1], the authors show that lines in this geometry can have endpoints. In this case, the lines are actually halflines. Unlike standard Euclidean geometry in which there is exactly one point at each location This work was supported by National Science Foundation grants DMS-0137264 and DMS0451254.
Vol. 92 (2009)
A Missing Prime Configuration
29
on the line segment joining two distinct points, there can be many elements at a given location between two elements in H(Rn ). The Fibonacci and Lucas numbers arise in a natural way in this geometry in the context of string and polygonal configurations [9]. Moreover, for infinitely many different values of the positive integer k, there are elements A and B in H(Rn ) so that there exist exactly k elements at each location between A and B. In this paper we will show that if k is between 1 and 18, there are always elements A and B in H(Rn ) so that there are exactly k elements at each location between A and B, and prove the surprising result that no such sets A and B exist if k equals 19.
2. Betweenness in H(Rn ) The sets that will be the “points” in our geometry are the non-empty compact subsets of n-dimensional real space, Rn . We will denote this hyperspace by H(Rn ). The familiar definition of the Hausdorff metric h on H(Rn ) is as follows. Definition 2.1. Let A and B be elements in H(Rn ). The Hausdorff distance between A and B is h(A, B) = max d(A, B), d(B, A) , where d(A, B) = maxa∈A {minb∈B {dE (a, b)}} and dE is the standard Euclidean metric on Rn . To distinguish between Rn and H(Rn ), we will refer to “points” in Rn and “elements” in H(Rn ). In this paper, we will study the notion of “betweenness” in H(Rn ). Given two distinct elements A, B ∈ H(Rn ), we say that an element C ∈ H(Rn ) lies between A and B if h(A, B) = h(A, C) + h(C, B) . As in [3], we will adopt the notation ACB to indicate that C lies between A and B. Note that this is an extension of the notion of betweenness in Euclidean geometry. In fact, if A = {a} and B = {b} are single element sets in H(Rn ), then the elements in H(Rn ) that lie between A and B are exactly the single element sets C = {c} for c ∈ ab [6]. However, the notion of betweenness in H(Rn ) is more general than its counterpart in Euclidean geometry. As an example, consider the elements A = {(−2, 0)} and B the circle centered at (4,0) with radius 2 as shown in Figure 1. In this case, we have h(A, B) = d(B, A) = 8. Let C = (A)5 ∩ (B)3 be the grey shaded region in Figure 1 (where (A)t = {x ∈ Rn : d(x, A) ≤ t} is the t-hull (or tdilation) of A by the non-negative real number t and d(x, A) = mina∈A {dE (x, a)}). As Lemma 2.5 shows, for sufficiently small the elements C = C − N ((0, 0)) all satisfy AC B with h(A, C ) = h(A, C). So we have infinitely many different elements at this location between A and B. The existence of many elements in H(Rn ) at a given location between sets A, B ∈ H(Rn ) is well known. See [5, 10] for example.
30
C. C. Blackburn et al.
A
J. Geom.
(0,0)
B C
Figure 1. Infinitely many sets at a given location between A and B. We formalize the notion of elements at the same location between sets A and B in the next definition. Definition 2.2. Let A, B ∈ H(Rn ) and A 6= B. Two elements C, C 0 ∈ H(Rn ) are said to be at the same location between A and B if C and C 0 satisfy ACB and AC 0 B with h(A, C) = h(A, C 0 ) = t for some 0 < t < h(A, B). In [9], the authors find interesting situations in which a finite number of elements exist at each location between elements A and B – in particular, the Fibonacci and Lucas numbers appear as the number of elements at each location for certain types of elements A and B. We will consider the question of which finite numbers can arise as the number of elements that can exist at each location between elements A and B. We begin by showing that if there is a finite number of compact sets at a given location between A and B, then d(a, B) = d(b, A) = h(A, B) for every a ∈ A and b ∈ B. We use the notation Ns (b) = {x ∈ Rn : dE (x, b) < s} for the s−neighborhood of b ∈ Rn and Ns (b) for the closure of Ns (b). Lemma 2.1. Let A, B ∈ H(Rn ). If there is an r > 0 so that d(b, A) = r for all b ∈ B and h(A, B) = d(B, A) = r, then every point a ∈ A must satisfy d(a, B) = r. Proof. Let A, B ∈ H(Rn ). Suppose d(b, A) = r for all b ∈ B and h(A, B) = d(B, A) = r. Clearly, no a ∈ A exists such that d(a, B) > r, because that would imply h(A, B) > r. Assume then that there exists a point a0 ∈ A such that d(a0 , B) < r. Then there exists b0 ∈ B such that dE (a0 , b0 ) < r. However, this implies d(b0 , A) < r, a contradiction. Therefore, every a ∈ A satisfies d(a, B) = r. In certain situations there are only finitely many elements at each location between two sets, as described in the next lemmas. In these situations, there will always be the same finite number of elements at each location between the sets. The proof of the first of these lemmas is straightforward and left to the reader.
Vol. 92 (2009)
A Missing Prime Configuration
31
Lemma 2.2. Let r, s, t be positive real numbers with 0 < s < r and t = r − s. If a and b are two points in Rn so that dE (a, b) < r, then Ns (b) ∩ Nt (a) 6= ∅. Lemma 2.3. Let A and B be elements of H(Rn ). If d(B, A) > 0, then there exist b ∈ B and a ∈ ∂A so that dE (b, a) = d(b, A) = d(B, A). Proof. Assume r = d(B, A) > 0. Since d(B, A) = maxb0 ∈B {d(b0 A)}, there is a point b ∈ B so that d(b, A) = d(B, A). Also, d(b, A) = mina0 ∈A {dE (b, a0 )} implies that there is a point a ∈ A so that r = d(B, A) = d(b, A) = dE (b, a). Now we will show that a ∈ ∂A. Note that since A is closed, ∂A ⊆ A. We proceed by contradiction. Suppose a 6∈ ∂A. Then there is an > 0 such that N (a) ⊂ A. Let x = a + 2r (b − a) so that x is the point on the Euclidean line segment between a and b at the distance 2 from a. Notice that x ∈ N (a) ⊂ A, so x ∈ A and dE (b, x) = dE (b, a) − dE (a, x) = r − < r . 2 This implies that d(b, A) < r, which is a contradiction. Lemma 2.4. Let A, B ∈ H(Rn ), A 6= B. Let s, t > 0 such that s + t = h(A, B). Let Ct = (A)t ∩ (B)s . Assume there exists an with 0 < < min{t, s} and c ∈ Ct such that N (c) ⊂ Ct . Let C = Ct − N (c). If there exists cA , cB ∈ C so that d(cA , A) = d(Ct , A) and d(cB , B) = d(Ct , B), then C satisfies AC B with h(A, C ) = t. Proof. First note that C is a closed subset of Ct and is therefore an element in H(Rn ). From [5] (Lemma 3.6), we know that h(A, Ct ) = t and h(B, Ct ) = s. Since C ⊂ Ct and d(x, A) ≤ t for every x ∈ Ct , we have d(x, A) ≤ t for every x ∈ C . So d(C , A) ≤ d(Ct , A) ≤ t. Similarly, d(C , B) ≤ d(Ct , B) ≤ s. Now we show that d(A, C ) ≤ t and d(B, C ) ≤ s. Let x ∈ A. We consider two cases. First suppose that x ∈ N (c). Let c0 be the point on the boundary of N (c) closest to x. Since C is closed, it is the case that ∂N (c) ⊂ C . So c0 ∈ C and dE (x, c0 ) ≤ ≤ t. Thus, d(x, C ) ≤ t. For the second case, assume that x 6∈ N (c). Let cx ∈ Ct such that dE (x, cx ) = d(x, Ct ) ≤ t = h(A, Ct ). If cx 6∈ N (c), then cx ∈ C and d(x, C ) ≤ t. If cx ∈ N (c), let c0 be the point on ∂N (c) ∩ xcx . Then dE (x, c0 ) < dE (x, cx ) ≤ t and d(x, C ) ≤ t. Therefore, d(x, C ) ≤ t for every x ∈ A and d(A, C ) ≤ t. A similar argument shows d(B, C ) ≤ s. Now we verify that h(A, C ) = t. A similar argument shows that h(B, C ) = s. Since h(A, Ct ) = max{d(A, Ct ), d(Ct , A)}, there are two cases to consider. First suppose d(A, Ct ) = t. By Lemma 2.3, there are points a ∈ A and ca ∈ ∂Ct so that dE (a, ca ) = d(A, Ct ) = t. Now N (c) is a subset of the interior of Ct , so ∂Ct ⊆ C . Thus, ca ∈ C . It follows that d(a, C ) = t and d(A, C ) = t. For the second case, suppose d(Ct , A) = t. By hypothesis, there is a point cA ∈ C so that d(cA , A) = d(Ct , A) = t. Thus, d(C , A) = t. So we have either d(A, C ) = t or d(C , A) = t. This proves that h(A, C ) = t.
32
C. C. Blackburn et al.
J. Geom.
Lemma 2.5. Let A, B ∈ H(Rn ) with h(A, B) = r. If there exists a ∈ A such that d(a, B) 6= r or b ∈ B such that d(b, A) 6= r, then there are infinitely many elements C ∈ H(Rn ) that satisfy ACB and h(A, C) = t for any 0 < t < r. Proof. Let A and B be in H(Rn ) with h(A, B) = r. Assume there is a point a ∈ A so that d(a, B) 6= r (the case when there is a point b ∈ B so that d(b, A) 6= r is similar). Since h(A, B) = r, we must have d(a, B) < r. Let b ∈ B such that dE (a, b) = d(a, B). Let 0 < t < r, s = r − t, and let Ct = (A)t ∩ (B)s . By Lemma 2.2, there exists c ∈ Ns (b) ∩ Nt (a). Since Ns (b) ∩ Nt (a) is an open set, there exists δ > 0 such that Nδ (c) ⊂ (Ns (b) ∩ Nt (a)) ⊂ Ct . Let 0 < γ < δ and let Cγ = Ct − Nγ (c). Let cA , cB ∈ Ct such that d(cA , A) = d(Ct , A) and d(cB , B) = d(Ct , B). If cA , cB ∈ Cγ , then choose 0 < < γ and let c∗ = c. If one or both of cA , cB are in Nγ (c), then choose c∗ ∈ Nγ (c) such that c∗ 6= cA and c∗ 6= cB . Let 0 < < min{dE (c∗ , cA ), dE (c∗ , cB ), γ − dE (c∗ , c)}. In either case, N (c∗ ) ⊂ Nγ (c) and C = Ct − N satisfies the conditions of Lemma 2.4. Therefore, C satisfies AC B and h(A, C ) = t. Since there are infinitely many choices for , there are infinitely many choices for C . Lemma 2.6. Let A, B ∈ H(Rn ) be finite sets. If all points b ∈ B are equidistant from A and h(A, B) = d(B, A) ≥ d(A, B), then there is the same finite number of elements at every location between A and B. Proof. Let A, B ∈ H(Rn ) be finite sets such that |A| = m and |B| = k for some m, k ∈ N. Further, let h(A, B) = d(b, A) = r for all b ∈ B. Finally, let 0 < s < r and t = r − s. We want to show that there are finitely many elements between A and B that satisfy h(C, B) = s. We claim that it is sufficient to prove that |Ns (b) ∩ (A)t | ≤ m for all b ∈ B. To see this, first note that if b ∈ B, then r = d(b, A) ≤ dE (b, a) for every a ∈ A. If |Ns (b) ∩ (A)t | ≤ m, then X |(B)s ∩ (A)t | ≤ |Ns (b) ∩ (A)t | ≤ k · m . b∈B n
Now, any element C ∈ H(R ) satisfying ACB and h(B, C) = s must be a subset of (B)s ∩ (A)t . But this finite set contains only finitely many subsets. Thus, the number of elements in H(Rn ) at each location between A and B is finite. We now show that |Ns (b) ∩ (A)t | ≤ m for every b ∈ B. Let b ∈ B. Note that if dE (b, a) > r, then Ns (b) ∩ Nt (a) = ∅. So these points a do not contribute points to the intersection Ns (b) ∩ (A)t . We will count the points that do contribute to this intersection. Let Ab = {a ∈ A : dE (b, a) = r}. Since Ab ⊆ A, we have |Ab | ≤ m. Let a ∈ Ab . We next show that Ns (b) ∩ Nt (a) = {ca } for some ca ∈ Rn . First, we show that such a ca exists. Let ab denote the Euclidean line segment from a to b.
Vol. 92 (2009)
A Missing Prime Configuration
33
Then, from basic Euclidean geometry, there exists exactly one point ca ∈ ab with dE (a, ca ) = t and dE (ca , b) = s. By definition, ca is an element of Ns (b) ∩ Nt (a). Next, we claim that no other point ea exists in Rn such that ea ∈ Ns (b) ∩ Nt (a). Suppose to the contrary that such an ea exists. Then dE (a, ea ) ≤ t and dE (ea , b) ≤ s. This implies r = dE (a, b) ≤ dE (a, ea ) + dE (b, ea ) ≤ s + t = r . Thus dE (a, ea ) = t, dE (b, ea ) = s, and ea ∈ ab. But since there is only one such point on ab, it must be that ea = ca . Now, we know that Ns (b) ∩ (A)t = Ns (b) ∩ (Ab )t = Ns (b) ∩ ∪a∈Ab Nt (a) . We also know that, for every a ∈ Ab , there will be exactly one corresponding point in Ns (b) ∩ (∪a∈Ab Nt (a)). Since there are a maximum of m points in Ab , there can be at most m points in Ns (b) ∩ (∪a∈Ab Nt (a)). Notice finally that for each b ∈ B, the number of points in the intersection Ns (b) ∩ (∪a∈Ab Nt (a)) (and therefore the number of elements in H(Rn ) at each location between A and B), depends only on the cardinality of the set Ab . This cardinality is not altered by varying the values of s and t, implying that at each location between A to B we have the same finite number of elements in H(Rn ). In light of Lemma 2.5, if there are only finitely many elements at each location between A and B, then every point in A is at the same distance from B and every point in B is at the same distance from A. This leads us to the following definition which will be of fundamental importance in what follows. Definition 2.3. A pair of sets A, B ∈ H(Rn ) is a configuration with ends A and B if h(A, B) = d(b, A) = d(a, B) for all a ∈ A and b ∈ B . The configuration with ends A and B will be denoted by [A, B]. If both A and B are finite, then the configuration [A, B] is called finite, otherwise the configuration [A, B] is called infinite. We denote by #([A, B]) the number of elements at each location between A and B for a finite configuration [A, B]. Lemma 2.6 shows that if [A, B] is a finite configuration, then #([A, B]) is finite. However, it is not necessarily the case for an infinite configuration [A, B] that there are finitely many elements at a given location between A and B. As an example, let A be the union of the singleton at the center of Figure 2 and the outer solid circle while B is the inner solid circle in Figure 2. One element at distance t from A is the union of the two dashed circles labeled C. Moreover, the union of the outer dashed circle with any non-empty compact subset from the inner dashed circle will be another element between A and B that is at distance t from A. Thus, there are infinitely many elements between A and B at a distance t from A even
34
C. C. Blackburn et al.
J. Geom.
A
A
C
C
B
Figure 2. #([A, B]) = ∞ for an infinite configuration [A, B]. though [A, B] is a configuration. We also note that it is possible to have a finite number of elements at each location between A and B for an infinite configuration [A, B]. We leave it to the reader to construct examples.
3. Elements between A and B Betweenness in H(Rn ) is the main topic of this paper. In this section, we determine where to look for elements that lie at a given location between two distinct elements A and B. In [6], the authors show that any element C ∈ H(Rn ) that satisfies h(A, C) = t is a subset of the t-dilation (A)t of A. So (A)t is the largest element (in the sense of containment) that is at distance t from A. Consequently, when we want to look for elements in H(Rn ) that are between sets A and B and at a distance t from A (and a distance s from B, where s + t = h(A, B)), then we can restrict our search to compact subsets of (A)t ∩ (B)s . When [A, B] is a finite configuration, it will be the case that (A)t ∩ (B)s is a finite set and #([A, B]) is finite. For example, let A = {a1 , a2 } and B = {b1 , b2 } be the vertices of a square as in Figure 3. Notice that if s + t = h(A, B), then (A)t intersects (B)s only at the boundaries of the dilations as shown in the figure. The four point set C = (A)t ∩ (B)s = {c1 , c2 , c3 , c4 } is one element of H(Rn ) that satisfies ACB at the distance t from A. The elements C − {ci } for i = 1, 2, 3, 4, C − {c1 , c3 }, and C − {c2 , c4 } also all lie at the same location between A and B, giving us 7 elements at each location. We leave it to the reader to argue that there are no more elements at this location between A and B. 3.1. Adjacency In our study of betweenness, adjacency will play an important role. Definition 3.1. Let A, B ∈ H(Rn ) and a ∈ A, b ∈ B. The point a is said to be adjacent to b, denoted a m b, if dE (a, b) = h(A, B). The adjacency set, [a]B , is defined as the set {b ∈ B : b m a}.
Vol. 92 (2009)
A Missing Prime Configuration
b2
c4
35
a1 c3
c1
a2
c2
b1
Figure 3. Seven elements at each location between A and B. To count elements between sets A and B, we will introduce two new functions qA and qB . To recognize these as functions, we need the next lemma. Lemma 3.1. Let [A, B] be a configuration and let C = (A)t ∩ (B)s for some 0 < s, t with s + t = h(A, B). 1. 2. 3. 4.
For all c ∈ C we have d(c, A) = t and d(c, B) = s. If C 0 ⊆ C, then h(A, C) ≤ h(A, C 0 ). Let C 0 ⊆ C satisfy AC 0 B. If a ∈ A, then [a]C 0 6= ∅. If b ∈ B, then [b]C 0 6= ∅. Given c ∈ C, there exists exactly one a ∈ A such that c ∈ [a]C and exactly one b ∈ B such that c ∈ [b]C .
Proof. The proofs of parts 1 and 2 are straightforward and left to the reader. Note that the condition h(A, B) = d(a, B) = d(b, A) for all a ∈ A, b ∈ B is necessary to prove part 1. To prove 3, let C 0 be a subset of (A)t ∩ (B)s so that C 0 satisfies AC 0 B. Since C 0 ⊆ (A)t and C 0 ⊆ (B)s , part 2 of Lemma 3.1 shows that h(A, C 0 ) ≥ t and h(C 0 , B) ≥ s. Since C 0 also satisfies AC 0 B, it follows that s + t = h(A, B) = h(A, C 0 ) + h(C 0 , B). Therefore, h(A, C 0 ) = t and h(B, C 0 ) = s. Further, due to part 1 of Lemma 3.1 and the fact that C 0 ⊆ (A)t ∩ (B)s , it is true that d(c0 , A) = t for all c0 ∈ C 0 . In other words, dE (c0 , a0 ) ≥ t for all 0
a0 ∈ A and all
c0 ∈ C 0 .
(3.1)
0
Now choose a ∈ A. Because h(A, C ) = t, we also have d(a, C ) ≤ t, implying that there exists c0 ∈ C 0 such that dE (a, c0 ) ≤ t. But (3.1) shows that dE (c0 , a) ≥ t. Therefore, dE (a, c0 ) = t and c0 ∈ [a]C 0 . Thus, [a]C 0 6= ∅. A similar argument shows that [b]C 0 6= ∅ for any b ∈ B. To prove 4, let c ∈ C. Part 1 of Lemma 3.1 tells us that d(c, A) = t. So there exists a ∈ A with dE (c, a) = t. Thus, c ∈ [a]C . The same argument shows that c ∈ [b]C for some b ∈ B. We now show that each c ∈ C is a member of the adjacency set of only one element in A. The same argument will work for B. Suppose that there exists
36
C. C. Blackburn et al.
J. Geom.
a1 6= a2 ∈ A such that c ∈ [a1 ]C and c ∈ [a2 ]C . It follows that there exists at least one b ∈ B such that c ∈ [b]C . This implies that all three of the following are true: dE (c, a1 ) = t, dE (c, a2 ) = t, and dE (c, b) = s. Then by the Euclidean triangle inequality, dE (a1 , b) ≤ dE (a1 , c) + dE (c, b) = t + s = r and dE (a2 , b) ≤ dE (a2 , c) + dE (c, b) = t + s = r. Since d(b, A) = r, we know dE (b, a1 ) ≥ r and dE (b, a2 ) ≥ r. Therefore, dE (a1 , b) = dE (a2 , b) = r. Then dE (a1 , b) = dE (a1 , c)+dE (c, b) = r and ← → dE (a2 , b) = dE (a2 , c) + dE (c, b) = r and a1 and a2 are on the Euclidean line cb at the same location. The properties of Euclidean lines ensure that a1 = a2 . Lemma 3.1 shows that qA and qB as given in Definition 3.2 are well-defined and surjective functions. Definition 3.2. Let [A, B] be a configuration and let C = (A)t ∩ (B)s for some 0 < s, t with s + t = h(A, B). Define functions qA : C → A and qB : C → B by qA (c) = a
when c ∈ [a]C
and qB (c) = b when c ∈ [b]C .
So qA (c) is the element a ∈ A that is adjacent to c. 3.2. Counting the number of elements between A and B Using adjacency, we will be able to identify and count the number of elements at each location between two elements making up any configuration [A, B]. We will adopt the following notational conventions: For a subset C in a topological space T , we let C c be the complement of C in T ; if A is a subset of a topological space T with topology U, then the induced topology on A is the collection, UA = {U ∩ A : U ∈ U }. For our purposes we will be considering the topology (Rn , U) where U is defined by the Euclidean metric topology on Rn . In what follows, for a configuration [A, B] we admit the following conventions: • CA,B,t = (A)t ∩ (B)s for positive s, t such that s + t = h(A, B); • KA,B,t = {C 0 : C 0 satisfies AC 0 B} is the set of all elements between A and B at a distance t from A; • ΥA,B,t is the collection of sets U ∈ UCA,B,t with the property that 1. for all a ∈ qA (U ) there exists c ∈ [a]CA,B,t such that c 6∈ U and 2. for all b ∈ qB (U ) there exists c ∈ [b]CA,B,t such that c 6∈ U . The set ΥA,B,t will provide another way to count the number of elements at a location between end elements, as Theorem 3.1 will show. In order to prove this theorem we need the following lemma. Lemma 3.2. Let [A, B] be a configuration, C = CA,B,t , and let U ∈ UC . If for all a ∈ qA (U ) there exists c ∈ [a]C such that c 6∈ U and for all b ∈ qB (U ) there exists c ∈ [b]C such that c 6∈ U , then the element C 0 = C − U satisfies AC 0 B. Proof. Let [A, B] be a configuration and let U ∈ UC . Suppose U = ∅. Then C 0 = C − U = C which satisfies ACB.
Vol. 92 (2009)
A Missing Prime Configuration
37
Suppose now that U 6= ∅ and for all a ∈ qA (U ) there exists c ∈ [a]C such that c 6∈ U and for all b ∈ qB (U ) there exists c ∈ [b]C such that c 6∈ U . First, notice that the set C 0 = C − U = C ∩ U c is closed since it is the intersection of two closed sets. Further, C 0 is bounded because it is a subset of a bounded set, thus C 0 ∈ H(Rn ). Let a ∈ A. If a 6∈ qA (U ), then there exists c ∈ [a]C such that c 6∈ U by part 3 of Lemma 3.1. If a ∈ qA (U ), then there exists c ∈ [a]C with c 6∈ U by hypothesis. So, for all a ∈ A there exists c ∈ [a]C such that c 6∈ U ; in other words, c ∈ C 0 = C − U . Therefore, for all a ∈ A, a m c for some c ∈ C 0 ; so d(A, C 0 ) ≤ t. Since C 0 ⊆ C ⊆ (A)t , it follows that d(c0 , A) ≤ t for each c0 ∈ C 0 . Thus d(C 0 , A) ≤ t and h(C 0 , A) ≤ t. Now, part 2 of Lemma 3.1 shows that t = h(A, C) ≤ h(A, C 0 ), so h(A, C 0 ) = t. A similar argument shows that h(B, C 0 ) = s. Therefore C 0 satisfies AC 0 B.
Theorem 3.1. Let [A, B] be a configuration and let C = CA,B,t . The mapping f : ΥA,B,t → KA,B,t defined by f (U ) = C − U is a bijection. Proof. Let [A, B] be a configuration and let C = CA,B,t . First note that if U ∈ ΥA,B,t then f (U ) = C − U ∈ KA,B,t by Lemma 3.2. So f maps ΥA,B,t to KA,B,t . Now we show that f is a surjection. Let C 0 ∈ KA,B,t . Then C 0 ⊆ C and C 0 satisfies AC 0 B. If C 0 = C, then f (∅) = C − ∅ = C = C 0 . If C 0 6= C, then let U = C − C 0 . Since C 0 is closed, (C 0 )c is open, which means that U = C − C 0 = C ∩ (C 0 )c ∈ UC . Also, because C 0 satisfies AC 0 B and C 0 ⊆ C = (A)t ∩ (B)s , part 3 of Lemma 3.1 shows that [a]C 0 6= ∅ for all a ∈ A. Therefore, for all a ∈ qA (U ) there exists c ∈ [a]C such that c ∈ C 0 and hence c 6∈ U . Note that a similar argument holds for all b ∈ qB (U ). Thus, U ∈ ΥA,B,t and f (U ) = C. Therefore, f is a surjection. Finally, we show that f is an injection. Suppose f (U ) = f (V ) for some U, V ∈ ΥA,B,t . Since U, V ⊆ C and C − U = C − V , we conclude U = V . Therefore f is injective and a bijection. Therefore we see that for any configuration [A, B], either infinite or finite, the set ΥA,B,t counts the number of elements between A and B at the distance t from A. Again, we can look at the example from Figure 3 and see the action of the mapping f : ΥA,B,t → KA,B,t , with f (∅) = C, f ({ci }) = C − {ci } for i = 1, 2, 3, 4, f ({c1 , c3 }) = {c2 , c4 }, and f ({c2 , c4 }) = {c1 , c3 }. As we observed earlier, #([A, B]) = 7, and we also see that |ΥA,B,t | = |KA,B,t | = 7.
4. Equivalent configurations The number of elements at each location between elements A and B in a finite configuration [A, B] is only dependent on the adjacencies between the points in
38
C. C. Blackburn et al.
J. Geom.
Figure 4. Two equivalent configurations. A and B and not the exact location of these points. We formalize this idea with equivalent configurations. Definition 4.1. A finite configuration [X, Y ] is equivalent to a finite configuration [A, B] if there are bijections f : A → X and g : B → Y such that for any a ∈ A and b ∈ B, a m b if and only if f (a) m g(b). When [X, Y ] is equivalent to [A, B] we write [X, Y ] ∼ [A, B]. We will pictorially represent a finite configuration using filled dots to represent points in A and open dots to represent points in B. We draw line segments between adjacent points. As an example, Figure 4 shows two equivalent finite configurations. Clearly, the relation ∼ is an equivalence relation. As the next theorem shows, the number of elements at each location between elements defining equivalent finite configurations is an invariant. Theorem 4.1. If a finite configuration [X, Y ] is equivalent to a finite configuration [A, B], then #([X, Y ]) = #([A, B]). Proof. Let the finite configuration [X, Y ] be equivalent to the finite configuration [A, B] and let f : A → X and g : B → Y be bijections as described in the definition. Since we know the number of elements at each location between A and B or X and Y is always the same, let t, t0 ∈ R with 0 < t < h(A, B) and 0 < t0 < h(X, Y ). Let C be an element satisfying ACB with h(A, C) = t. We will construct an element ZC satisfying XZC Y and h(X, ZC ) = t0 . Part 3 of Lemma 3.1 shows that for each c ∈ C there is one pair (a, b) ∈ A × B such that {c} = ({a})t ∩ ({b})h(A,B)−t . Let x = f (a) and y = g(b). Let {zc } = ({x})t0 ∩ ({y})h(X,Y )−t0 . Let ZC = {zc : c ∈ C}. Now we show ZC satisfies h(X, ZC ) = t0 . Since [X, Y ] is a configuration and ZC by construction is a subset of (X)t0 ∩ (Y )h(X,Y )−t0 , part 1 of Lemma 3.1 shows that d(z, X) = t0 for all z ∈ ZC . So d(ZC , X) = t0 . Now all we need do is to show that d(X, ZC ) ≤ t0 . To do this, we show that for each x ∈ X there is a zx ∈ ZC so that dE (x, zx ) = t0 . Let x ∈ X. Let ax ∈ A so that f (ax ) = x. Let cx ∈ C so that dE (ax , cx ) = t. Then zcx ∈ ZC satisfies dE (x, zcx ) = t0 . Thus, h(X, ZC ) = t0 . A similar argument shows that h(Y, ZC ) = h(X, Y ) − t0 . Thus, ZC satisfies XZC Y with h(X, ZC ) = t0 . Therefore, #([A, B]) ≤ #([X, Y ]). Since equivalence is symmetric, the same argument shows #([X, Y ]) ≤ #([A, B]). Theorem 4.1 shows that the actual location of points in a finite configuration is irrelevant – the only important consideration is adjacency. The dilations (A)t and
Vol. 92 (2009)
A Missing Prime Configuration
39
Figure 5. A standard loop L4 . (B)s where s + t = h(A, B) will intersect in the same way regardless of how the points are oriented. One can easily see this in the equivalent configurations in Figure 4.
5. Special configurations: strings and loops Let [A, B] be a finite configuration. Choose a1 ∈ A. Then choose distinct points (if possible) b1 ∈ [a1 ]B , a2 ∈ [b1 ]A , b2 ∈ [a2 ]B , . . .. The sequence of points a1 , b1 , a2 , b2 , . . . forms a “string” of adjacent points in [A, B] until some point is repeated. If it happens that ak = aj for some j < k, then the set of points aj , bj , . . . , bk−1 forms a “loop” in [A, B]. These “strings” and “loops” form basic building blocks of finite configurations. We formally define strings and loops in this section. Definition 5.1. Let m be a positive integer. 1. An m-string Sm is any finite configuration equivalent to the configuration [A, B] with A = {xk : k odd} and B = {xk : k even} where x1 , x2 , . . . , xm are m uniformly spaced points in order on a line. 2. A 2m-loop L2m is any finite configuration equivalent to the configuration [A, B], where A = {x1 , x2 , . . . , xm } and B = {y1 , y2 , . . . , ym } and x1 , y1 , x2 , y2 , . . ., xm , ym are the consecutive vertices of a regular 2m-gon. For example, two equivalent configurations for S4 are shown in Figure 4 and a representation of a loop L4 is shown in Figure 5. In [9] the authors show that #(Sm ) is given by the m − 1st Fibonacci number and #(L2m ) is given by the 2mth Lucas number. So we see that there are configurations [Ak , Bk ] so that #([Ak , Bk ]) = k for infinitely many different values of k. A natural question to ask is, given any positive integer k, does there exist a configuration [A, B] so that #([A, B]) = k. We will address this question shortly.
6. Adjoining configurations Adjoining of configurations will allow us to build up more complicated configurations from simpler ones and will provide techniques to determine #([A, B]) for certain types of configurations.
40
C. C. Blackburn et al.
a
J. Geom.
y
Figure 6. Adjoining a point to a loop L4 . 6.1. Adjoining a point to a configuration First, we adjoin a single point to a finite configuration. Definition 6.1. Let [A, B] be a finite configuration. A configuration [A, B](a, y) obtained by adjoining a point y 6∈ A ∪ B to [A, B] at the point a ∈ A is any configuration equivalent to the configuration [A, B 0 ], where B 0 = B ∪ {y} and [y]A = {a}. As an example, Figure 6 shows the result of adjoining a point to a loop at the point a. Adjoining a point to a finite configuration [A, B] creates a new configuration that contains [A, B] as a subconfiguration. Definition 6.2. A configuration [A, B] is a subconfiguration of a configuration [A0 , B 0 ] if A ⊆ A0 and B ⊆ B 0 . If [A, B] is a configuration and a ∈ A has the property that |[a]B | = 1, then a is in some sense “isolated” in the configuration. Definition 6.3. Let [A, B] be a finite configuration. A point a ∈ A is an endpoint of the configuration [A, B] if a is adjacent to exactly one point in B. Adjoining a point to a finite configuration [A, B] may or may not alter #([A, B]) as described in the next theorem. Theorem 6.1. Let [A, B] be a finite configuration. 1. If [A0 , B 0 ] is a subconfiguration of [A, B], then #([A, B]) ≥ #([A0 , B 0 ]). 2. If a ∈ A is adjacent to an endpoint, then #([A, B](a, y)) = #([A, B]) for any y 6∈ A ∪ B. 3. If [X, Y ] is a configuration with h(A, B) = h(X, Y ), dE (a, y) > h(A, B) for all a ∈ A and y ∈ Y , and dE (b, x) > h(A, B) for all b ∈ B and x ∈ X, then #([A ∪ X, B ∪ Y ]) = #([A, B])#([X, Y ]). Proof. To prove 1, let 0 < t < h(A, B) = r. Let Ct = (A)t ∩ (B)r−t , Ct0 = (A0 )t ∩ (B 0 )r−t , and C ∗ = Ct − Ct0 . If C 0 is any element satisfying A0 C 0 B 0 , then C = C ∗ ∪ C 0 satisfies ACB. Thus, #([A, B]) ≥ #([A0 , B 0 ]). To prove 2, assume a ∈ A is adjacent to an endpoint b ∈ B. Adjoin a point y to [A, B] at a. Let B 0 = B ∪ {y}. Suppose C 0 satisfies AC 0 B 0 . Let {z} = ({a})t ∩
Vol. 92 (2009)
A Missing Prime Configuration
41
({b})r−t and {w} = ({a})t ∩ ({y})r−t . Since b and y are endpoints, both w and z must be in C 0 . Clearly, the element C = C 0 −{w} satisfies ACB. Thus, #([A, B]) ≥ #([A, B](a, y)) and we obtain equality by part 1. To prove 3, assume [A, B] and [X, Y ] are configurations with r = h(A, B) = h(X, Y ), dE (a, y) > h(A, B) for all a ∈ A and y ∈ Y , and dE (b, x) > r for all b ∈ B and x ∈ X. First we show [A ∪ X, B ∪ Y ] is a configuration. Let u ∈ A ∪ X. Without loss of generality, assume u ∈ A. By hypothesis, we know d(u, Y ) > r and since [A, B] is a configuration we know d(u, B) = r. Therefore, d(u, B ∪ Y ) = r. Similarly, d(v, A ∪ X) = r for all v ∈ B ∪ Y . Therefore, [A ∪ X, B ∪ Y ] is a configuration. Now we show #([A ∪ X, B ∪ Y ]) ≥ #([A, B])#([X, Y ]). Let C satisfy ACB and C 0 satisfy XC 0 Y with h(A, C) = h(X, C 0 ) = t. We show C ∪ C 0 satisfies (A ∪ X)(C ∪ C 0 )(B ∪ Y ) with h(A ∪ X, C ∪ C 0 ) = t. Let e ∈ C ∪ C 0 . Without loss of generality, assume e ∈ C. Then d(e, A) = t and d(e, B) = r − t. Now we show d(e, X) > t and d(e, Y ) > r − t. Choose ae ∈ A and be ∈ B such that dE (e, ae ) = t and dE (e, be ) = r − t. Let x ∈ X so that dE (e, x) = d(e, X). Then r < dE (x, be ) ≤ dE (x, e) + dE (e, be ) = dE (x, e) + (r − t) which shows dE (e, x) > t. Thus, d(e, X) > t. Similarly, d(e, Y ) > r − t. So d(e, A ∪ X) = t and d(e, B ∪ Y ) = r − t. Therefore, d(C ∪ C 0 , A ∪ X) = t and d(C ∪ C 0 , B ∪ Y ) = r − t. Now we argue that d(A ∪ X, C ∪ C 0 ) = t and d(B ∪ Y, C ∪ C 0 ) = r − t. Let u ∈ A ∪ X. Without loss of generality, assume u ∈ A. Then d(u, C) = t. Let c ∈ C so that dE (u, c) = t. Let c0 ∈ C 0 so that dE (u, c0 ) = d(u, C 0 ). Then let yc0 ∈ Y so that dE (c0 , yc0 ) = r − t. Then r < dE (u, yc0 ) ≤ dE (u, c0 ) + dE (c0 , yc0 ) = dE (u, c0 ) + (r − t) which shows that dE (u, c0 ) > t. So d(u, C 0 ) > t and d(A ∪ X, C ∪ C 0 ) = t. A similar argument shows d(B∪Y, C∪C 0 ) = r−t. Thus, C∪C 0 satisfies (A∪X)(C∪C 0 )(B∪Y ) with h(A ∪ X, C ∪ C 0 ) = t and #([A ∪ X, B ∪ Y ]) ≥ #([A, B])#([X, Y ]). Finally, we show that #([A, B])#([X, Y ]) ≥ #([A ∪ X, B ∪ Y ]). Let Z satisfy (A ∪ X)Z(B ∪ Y ) with h(A ∪ X, Z) = t. We show that Z is a union of elements C and C 0 satisfying ACB and XC 0 Y with h(A, C) = h(X, C 0 ) = t. Let z ∈ Z. Then there is an element uz ∈ A ∪ X and an element vz ∈ B ∪ Y so that dE (z, uz ) = t and dE (z, vz ) = r − t. Suppose uz ∈ A. If vz ∈ Y , then dE (uz , vz ) ≤ dE (uz , z) + dE (z, vz ) = r, which contradicts d(uz , Y ) > r. So vz ∈ B. Similarly, if uz ∈ X, then vz ∈ Y . Let C = {z ∈ Z : dE (z, uz ) = t for some uz ∈ A} and C 0 = {z ∈ Z : dE (z, uz ) = t for some uz ∈ X}. We will show C satisfies ACB with h(A, C) = t. A similar argument shows C 0 satisfies XC 0 Y with h(X, C 0 ) = t. Let c ∈ C. Then there exist ac ∈ A and bc ∈ B such that dE (c, ac ) = t and dE (c, bc ) = r − t. Since [A, B] is a configuration, we know dE (c, u) ≥ t for all u ∈ A and dE (c, v) ≥ r − t for all v ∈ B. Thus, d(c, A) = t and d(c, B) = r − t. Therefore, d(C, A) = t and d(C, B) = r − t. Now let a ∈ A. There is an element w ∈ Z such that dE (a, w) = t. By definition, w ∈ C so d(a, C) ≤ t. If
42
C. C. Blackburn et al.
b
J. Geom.
a
Figure 7. A disconnected configuration [A, B]. dE (a, d) < t for some d ∈ C, then dE (a, Z) < t. However, this contradicts the fact that [A ∪ X, B ∪ Y ] is a configuration. Therefore, d(A, C) = t and h(A, C) = t. Similarly, d(B, C) = r − t and h(B, C) = r − t. Thus, C satisfies ACB with h(A, C) = t. Therefore, #([A, B])#([X, Y ]) ≥ #([A∪X, B∪Y ]) and, consequently, #([A ∪ X, B ∪ Y ]) = #([A, B])#([X, Y ]). In light of part (3) of Theorem 6.1, we define connected configurations. Definition 6.4. A finite configuration [U, V ] is connected if there are no subsets A and X of U and B and Y of V so that 1. A ∪ X = U , 2. B ∪ Y = V , 3. and [A, B] and [X, Y ] are configurations with (a) h(A, B) = h(X, Y ) = h(U, V ), (b) dE (a, y) > h(U, V ) for all a ∈ A and y ∈ Y , and (c) dE (b, x) > h(U, V ) for all b ∈ B and x ∈ X. For example, if U is the set of filled points and V the set of open points in Figure 7, then [U, V ] is a disconnected configuration (let A = {a} and B = {b}). The configurations in Figures 5 and 6 are connected configurations. As the next theorem shows, a configuration is connected if there is a substring connecting any two points. We first explain the terminology, then prove the theorem. Connected configurations will be important later when we look for a configuration [A, B] with #([A, B]) = 19. Definition 6.5. Let [A, B] be a finite configuration. Points a ∈ A ∪ B and b ∈ A ∪ B are string connected (denoted a ' b) if either a = b or there exists m > 1 and a sequence x1 , x2 , . . . , xm in A∪B such that a = x1 , xi m xi+1 for each 1 ≤ i ≤ m−1 and xm = b. A straightforward argument (left to the reader) proves the following lemma. Lemma 6.1. Let [A, B] be a finite configuration. The relation ' is an equivalence relation. Theorem 6.2. A finite configuration [U, V ] is connected if and only if p ' q for any points p ∈ U and q ∈ V .
Vol. 92 (2009)
A Missing Prime Configuration
43
Proof. Let [U, V ] be a finite configuration. To prove the forward implication, assume [U, V ] is connected. We proceed by contradiction and assume that there are points p ∈ U and q ∈ V so that p 6' q. Let Vp = {v ∈ V : v ' p}. We know Vp is non-empty since [U, V ] is a configuration. Let Up = {u ∈ U : u ' p}. Clearly p ∈ Up and Up 6= ∅. Let X = U − Up and Y = V − Vp . We know q 6∈ Vp , so Y 6= ∅. To show X 6= ∅, let x ∈ U so that x m q. So x ' q. If x ∈ Up , then x ' p. Then q ' x ' p, a contradiction. Therefore, Y 6= ∅. Now we show that [Up , Vp ] and [X, Y ] are configurations. Let u ∈ Up . Since [U, V ] is a configuration, there is a point v ∈ V such that u m v. So u ' v. Since u ' p, we know v ' p and v ∈ Vp . Thus, d(u, Vp ) = h(U, V ). Similarly, d(v, Up ) = h(U, V ) for every v ∈ Vp . Thus, [Up , Vp ] is a configuration. Now let x ∈ X. Then there exists y ∈ V such that x m y. So x ' y. If y ∈ Vp , then y ' p and, consequently, x ' p, a contradiction. Therefore, y ∈ Y and d(x, Y ) = h(U, V ). Similarly, d(y, X) = h(U, V ) for all y ∈ Y . Thus, [X, Y ] is a configuration. Finally, we show d(a, y) > h(U, V ) for all a ∈ Up and y ∈ Y . A similar argument will show d(b, x) > h(U, V ) for all b ∈ Vp and x ∈ X. Let a ∈ Up and y ∈ Y . Suppose d(a, y) = h(U, V ). Then a m y. But then p ' a ' y and y ∈ Vp , a contradiction. Therefore, [U, V ] is disconnected. Since [U, V ] is connected by hypothesis, we conclude that p ' q. Now we prove the reverse implication by contradiction. Assume that [U, V ] is disconnected. Let A and X be subsets of U and B and Y subsets of V so that A ∪ X = U , B ∪ Y = V , and [A, B] and [X, Y ] are configurations with h(A, B) = h(X, Y ) = h(U, V ), dE (a, y) > h(U, V ) for all a ∈ A and y ∈ Y , and dE (b, x) > h(U, V ) for all b ∈ B and x ∈ X. Let p ∈ A and q ∈ Y and let x1 , x2 , . . . , xm ∈ U ∪V so that p = x1 , xi m xi+1 for each 1 ≤ i ≤ m − 1 and q = xm . Let i be the smallest index so that xi ∈ Y (we know i exists because xm = q ∈ Y ). Now i > 2 since x1 ∈ A and dE (x1 , xi ) > h(U, V ). Then xi−2 ∈ B and xi−2 m xi−1 , so xi−1 ∈ A. But then dE (xi−1 , xi ) > h(U, V ), a contradiction. Thus, [U, V ] must be a connected configuration. If [A, B] is a finite configuration and points p ∈ A and q ∈ B are string connected, then [A, B] contains a string subconfiguration defined by the points x1 , x2 , . . . , xm given in Definition 6.5. One useful counting technique determines the number of elements at each location between elements in a configuration obtained by adjoining one point to a configuration. The proof can be found in [9]. Theorem 6.3. Let [A, B] be a finite configuration. Assume a is adjacent to k points b1 , b2 , . . . , bk in B, none of which are endpoints. Then #([A, B](a, y)) = #([A, B]) + #([A − {a}, B]). For example, let [A, B] = L4 . We use Theorem 6.3 to find #([A, B](a, y)) as shown in Figure 6. From [9] we know that #(L4 ) = 7 and #(S3 ) = 1, so #([A, B](a, y)) = #(L4 ) + #(S3 ) = 7 + 1 = 8.
44
C. C. Blackburn et al.
J. Geom.
6.2. The configuration construction theorem Definition 4.1 shows that the equivalence class of any finite configuration is determined by its adjacencies. Let [A, B] be a finite configuration with A = {a1 , a2 , . . ., ak }, B = {b1 , b2 , . . ., bm }. We can store the adjacency information of a configuration succinctly in a symmetric matrix M = [mi,j ] (an adjacency matrix), where mi,j = 1 if dE (ai , bj ) = h(A, B) and mi,j = 0 if dE (ai , bj ) > h(A, B). Note that each row and column of M will contain at least one 1. For example, a matrix for the configuration in Figure 6 is [ 11 11 10 ]. Note that there can be more than one matrix for a given configuration, but any matrix for a given configuration can be obtained from another by a suitable sequence of row interchanges and column interchanges. Note that we could alternately define equivalent configurations using adjacency matrices: two finite configurations are equivalent if they have adjacency matrices that are equal. Definition 6.6. An adjacency matrix is any k × m matrix M whose entries consist only of 0s or 1s such that each row and each column contains at least one 1. Every finite configuration has a corresponding adjacency matrix. In this section we prove that, given an adjacency matrix there exists a finite configuration with the indicated adjacencies. This result will allow us to adjoin finite configurations together to build new configurations. Theorem 6.4 (The Configuration Construction Theorem). Let M = [mi,j ] be an α × β adjacency matrix. Then there exists a positive real number r and finite configuration [A, B] with A = {a1 , a2 , . . . , aα } and B = {b1 , b2 , . . . , bβ } in Rβ+2 such that dE (ai , bi ) = r if mi,j = 1 and dE (ai , bj ) > r if mi,j = 0. Proof. Let M = [mi,j ] be an α × β adjacency matrix. If β = 1 the problem is trivial – we simply place α points (in A) on a √ circle around the single point in B. So suppose β ≥ 2. Fix c ∈ N such that c > β. For 1 ≤ i ≤ β let bi = ( 1c )ei , where ei is the ith standard unit vector in Rβ+2 . Let B = {bi : 1 ≤ i ≤ β}. To find the set A in our configuration, we first show that infinitely many points can be placed equidistant from any collection of points in B. q Let Bi be the (β + 1)-sphere of radius 1 − c12 around each point bi : β+2 1 X 2 1 β+2 Bi = (x1 , . . . , xβ+2 ) ∈ R : xi = , xj = 1 − 2 . c j=1 c j6=i
We will now show that the intersection of any collection of these (β + 1)-spheres contains a smaller dimensional sphere. Let {Bi1 , Bi2 , . . . , Biq } with 2 ≤ q ≤ β be √ a set of q of these (β + 1)-spheres. Notice that since c > β and β ≥ q, we have
Vol. 92 (2009)
A Missing Prime Configuration
45
c2 > q, or 1 > cq2 . We show that the intersection ∩k Bik of all of these (β+1)-spheres contains the (β + 2 − q)-sphere defined by
xi1 , xi2 , . . . , xiq =
1 , c
β+2 X
x2j = 1 −
j=1 j6=i1 ,...,iq
q . c2
(6.1)
Let z = (z1 , . . . , zβ+2 ) be a point on the (β + 2 − q)-sphere described by (6.1). So zi1 , . . . , ziq = 1c . To verify that z is on the (β + 1)-sphere Bik (where 1 ≤ k ≤ q), note that β+2 X j=1 j6=ik
β+2 X
zj2 =
j=1 j6=i1 ,...,iq
zj2 +
q 1 = 1− 2 + q· 2 c c 1 =1− 2 . c
q X
! zi2l
− zi2k
l=1
−
1 c2
Hence our (β + 2 − q)-sphere (6.1) lies on Bik for all 1 ≤ k ≤ q and is therefore contained in the intersection ∩k Bik . Note that if we take the intersection of all of our (β + 1)-spheres, B1 through Bβ , we will get the circle defined by x1 , . . . , x β =
1 , c
x2β+1 + x2β+2 = 1 −
β . c2
So any intersection of any collection of the (β + 1)-spheres contains an infinite number of points. Now we construct a set A = {a1 , a2 , . . . , aα } so that [A, B] is a desired configuration. Let ap = (w1 , . . . , wβ+2 ) ∈ A and let s1 , s2 , . . . , st be the columns of M so that mp,si = 1 for i from 1 to t. We show that ap can be located so that ap is adjacent to exactly the points bs1 , . . . , bst . We place ap on the intersection of the (β + 1)-spheres Bs1 through Bst , such that r
t+1 1 − 2 < wβ+2 < c
r
t 1− 2 , c
r and
−
1−
t < wq < 0 c2
for all 1 ≤ q ≤ β + 1 with q 6= s1 √ , . . . , st (note that we must have ws1 = ws2 = · · · = wst = 1c ). Notice that c > β, so c2 > β, or c2 ≥ β + 1 ≥ t + 1. Thus, 1 1 ≥ t+1 c2 > 0 and wβ+2 is always defined. Notice also that dE (ap , bsi ) = 1 − c2 for
46
C. C. Blackburn et al.
J. Geom.
each 1 ≤ i ≤ t. If bv ∈ B − {bs1 , bs2 , . . . , bst }, then 2 β+2 X 2 1 dE (ap , bv )2 = w + − w v j c j=1 j6=v
=
β+1 X
j=1 j6=v,s1 ,...,st
=
t X
wj2 +
! ws2k
k=1
β+1 X
j=1 j6=v,s1 ,...,st
wj2
2 + + wβ+2
1 − wv c
2
1 + t· 2 c
+
2 wβ+2
+
1 − wv c
2 .
q Now, substituting the inequalities wβ+2 > 1 − t+1 c2 and wv < 0, we get 2 X β+1 1 1 2 2 w + t · + w + − w v j β+2 c2 c j=1 j6=v,s1 ,...,st
1 t· 2 c
1 ≥ + + − wv c 2 1 t+1 1 > t· 2 + 1 − 2 + −0 c c c = 1. 2 wβ+2
2
q q Therefore, d(ap , bsi ) = 1 − c12 for 1 ≤ i ≤ t and dE (ap , bv ) > 1 − c12 for v 6= s1 , s2 , . . . , st . Recall that the intersection of any of the collection of Bi is infinite, so we can place any finite number of distinct points in any intersection of the Bi . Thus, we can distribute α points a1 , a2 , . . . , aα in any intersection we like to form the adjacencies indicated in M . Since every row and column in M contains a 1, we know also that every point in B is adjacent to at least one point q in A and vice versa. Therefore, we have d(a, B) = 1 − c12 for all a ∈ A and q d(b, A) = 1 − c12 for all b ∈ B. So [A, B] is a configuration with exactly the adjacencies indicated in the adjacency matrix M . 6.3. Adjoining configurations We now define the adjoin of any two finite configurations. The Configuration Construction Theorem ensures that these adjoins exist.
Vol. 92 (2009)
A Missing Prime Configuration
a
47
a y
g(y)
Figure 8. Adjoining two configurations.
Figure 9. Adjoining two strings to a loop.
Definition 6.7. Let [A, B] and [X, Y ] be finite configurations and let a ∈ A and y ∈ Y . Let M be an adjacency matrix for [A, B] whose last row corresponds to the point a and M 0 an adjacency matrix for [X, Y ] whose first column corresponds to y. The adjoin [A, B][a] ⊕ [X, Y ][y] of the configurations [A, B] and [X, Y ] at the A points a and y is a configuration with adjacency matrix [ M ], where A = [ai,j ] 0 M0 with all entries 0 except for a|A|,1 = 1. In other words, the adjoin of the finite configurations [A, B] and [X, Y ] at points a and y is a configuration that retains the adjacencies in [A, B] and [X, Y ] and adds a new adjacency between a and y. As an example, if we adjoin the separate configurations shown at left in Figure 8 at the points a and y, we obtain the new configuration shown at right in Figure 8. We are especially interested in adjoining strings and loops together to create new configurations. To simplify the notation for strings and loops, we give numeric labels to the points in these configurations as follows. For a string Sm , label one of the endpoints as 1, the point adjacent as 2, then next adjacent point as 3, and so on. For a loop L2m , pick any point and label it as 1. Choose an orientation and label the point adjacent with that orientation as 2 and proceed with this labeling according to adjacencies. Of course, these labelings aren’t unique, but that won’t matter for our purposes. We then use the notation L2m ⊕ Sk [i] to be the configuration that results from adjoining Sk at an endpoint to L2m at point labeled i. Additionally, we denote by L2m ⊕{Sk [i]; Sl [j]} the configuration obtained by adjoining two strings Sk and Sl at their endpoints to a loop L2m at the points labeled i and j, respectively. For example, the configuration L4 ⊕ {S2 [1]; S2 [3]} is shown in Figure 9. Similarly, we denote the adjoin of a string Sk to a string Sm at position i as Sm ⊕ Sk [i].
48
C. C. Blackburn et al.
J. Geom.
Table 1. A library of configurations 1–18. #(S3 ) = 1 #(S4 ) = 2 #(S5 ) = 3 #(S5 ⊕ S1 [3]) = 4 #(S6 ) = 5 #(S6 ⊕ S1 [3]) = 6 #(L4 ) = 7 #(S7 ) = 8 #(L4 ⊕ {S1 [1]; S1 [3]}) = 9
#(L4 ⊕ {S1 [3]; S1 [4]}) = 10 #(S6 ⊕ S2 [3]) = 11 #(S7 ⊕ {S1 [3]; S1 [4]}) = 12 #(S8 ) = 13 #(S6 ⊕ {S1 [3]; S2 [4]}) = 14 #(L4 ⊕ S2 [1]) = 15 #(S8 ⊕ S1 [3]) = 16 #(S7 ⊕ S2 [4]) = 17 #(S8 ⊕ {S1 [3]; S1 [5]}) = 18
7. Finite configurations 1–18 With our adjoin construction, we can build from strings and loops to obtain new finite configurations [A, B] that have different numbers of elements at each location between A and B. To illustrate, Table 1 shows various configurations [A, B] in H(Rn ), where #([A, B]) = k for k from 1 to 18. Theorem 6.3 provides a useful technique for making these calculations. The verification of these computations is left to the reader. For any positive integer k, one might expect there to exist a configuration [A, B] with #([A, B]) = k to extend Table 1. However, in the next sections we prove the surprising result that there is no finite configuration [A, B] such that #([A, B]) = 19.
8. Searching the finite cases for 19 To consider all of the finite cases, we take a brute force approach. Suppose [A, B] is a finite configuration. As we saw earlier, every finite configuration contains a string or a loop as a subconfiguration. Theorem 6.1 shows that any configuration [A, B] containing a subconfiguration [A0 , B 0 ] with #([A0 , B 0 ]) > 19 will satisfy #([A, B]) > 19. In light of property 3 of Theorem 6.1 and the fact that 19 is prime, when we look for a configuration [A, B] for which #([A, B]) = 19, we only need to look at connected configurations. So we begin our search for a finite configuration [A, B] satisfying #([A, B]) = 19 with configurations that contain the largest loops as subconfigurations and then configurations with the largest possible stings as subconfigurations. We adjoin additional points one at a time until we reach a case where there are more than 19 elements in H(Rn ) at each location in our configuration or it is clear that the addition of another point leads to more than 19 elements at each location. In this way, we will exhaust all of the finite configurations [A, B] for which it is possible that #([A, B]) = 19. We address infinite configurations in Section 9.
Vol. 92 (2009)
A Missing Prime Configuration
49
Figure 10. Configurations X4,1 (left) and X4,2 (right). We begin with the loops. In [9] the authors show that #(L2m ) > 19 for m ≥ 4. Thus, we need not consider any configurations that contain a subconfiguration loop of more than 6 points. 8.1. Building on the loop of length 6 From [9] we know #(L6 ) = 18. Any larger configuration that contains L6 as a subconfiguration must contain at least one more point. If we adjoin one point to L6 (it doesn’t matter at which point we adjoin this point), we obtain a configuration equivalent to #(L6 ⊕ S1 [1]) (or a configuration that contains #(L6 ⊕ S1 [1]) as a subconfiguration). Theorem 6.3 shows #(L6 ⊕ S1 [1]) = #(L6 ) + #(S5 ) = 21, so any configuration [A, B] containing L6 as a subconfiguration either satisfies #([A, B]) = 18 or #([A, B]) ≥ 21. Therefore, no configuration [A, B] that contains L6 can satisfy #([A, B]) = 19. 8.2. Building on the loop of length 4 Now we consider configurations containing a subconfiguration loop L4 . From [9] we know #(L4 ) = 7. We consider all the ways points can be adjoined to configurations containing L4 . However, by Theorem 6.1, we don’t need to consider adjoining a point to a configuration at a point adjacent to an endpoint. • If one point is adjoined to L4 , there are two possible results: a configuration equivalent to L4 ⊕ S1 [1] or a configuration X4,1 with adjacency matrix [ 11 11 11 ] as shown in Figure 10. – We showed earlier that #(L4 ⊕ S1 [1]) = 8. – A direct calculation shows that #(X4,1 ) = 25. Any configuration X containing X4,1 as a subconfiguration will satisfy #(X) ≥ 25, so we need not consider such configurations. • There are three ways two points can be adjoined to L4 without containing a subconfiguration X4,1 : adjoin two single points, adjoin a string of length 2, or adjoin two points to obtain the configuration X4,2 with adjacency matrix 1 1 0 1 1 1 as shown in Figure 10. Adjoining two points to L4 results in the equiv101 alence classes of L4 ⊕ S2 [1], L4 ⊕ {S1 [1]; S1 [2]} (note that L4 ⊕ {S1 [1]; S1 [4]} is equivalent to L4 ⊕ {S1 [1]; S1 [2]}), and L4 ⊕ {S1 [1]; S1 [3]}. Now – #(L4 ⊕ S2 [1]) = #(L4 ⊕ S1 [1]) + #(L4 ) = 15, – #(L4 ⊕ {S1 [1]; S1 [2]} = #(L4 ⊕ S1 [1]) + #(S4 ) = 10,
50
C. C. Blackburn et al.
J. Geom.
– #(L4 ⊕ {S1 [1]; S1 [3]} = #(L4 ⊕ S1 [1]) + #(S3 ⊕ S1 [2]) = 9, – #(X4,2 ) = 43. • Adjoining three points to L4 (either by adjoining three individual points or one point and a string of length two) without obtaining subconfigurations of X4,1 or X4,2 results in the equivalence classes of L4 ⊕S3 [1], L4 ⊕{S2 [1]; S1 [1]}, L4 ⊕ {S2 [1]; S1 [2]}, L4 ⊕ {S2 [1]; S1 [3]}, and L4 ⊕ {S1 [1]; S1 [2]; S1 [3]}. Now – #(L4 ⊕ S3 [1]) = #(L4 ⊕ S2 [1]) + #(L4 ⊕ S1 [1]) = 23, – #(L4 ⊕ {S2 [1]; S1 [1]}) = #(L4 ⊕ S2 [1]) + #(S3 )#(S2 ) = 16, – #(L4 ⊕ {S2 [1]; S1 [2]}) = #(L4 ⊕ S2 [1]) + #(S5 ) = 18, – #(L4 ⊕{S2 [1]; S1 [3]}) = #(L4 ⊕S2 [1])+#(S4 ⊕S1 [2]) = #(L4 ⊕S2 [1])+ #(S4 ) = 17, – #(L4 ⊕ {S1 [1]; S1 [2]; S1 [3]}) = #(L4 ⊕ {S1 [1]; S1 [2]}) + #(S4 ⊕ S1 [3]) = #(L4 ⊕ {S1 [1]; S1 [2]}) + #(S4 ) = 12. • When four points are adjoined to L4 , we can omit configurations containing L4 ⊕ S3 [1], since #(L4 ⊕ S3 [1]) already exceeds 19. The remaining equivalence classes obtained when adjoining four points to L4 are the classes of L4 ⊕ {S2 [1]; S2 [1]}, L4 ⊕ {S2 [1]; S1 [1]; S1 [2]}, L4 ⊕ {S2 [1]; S1 [1]; S1 [3]}, L4 ⊕ {S2 [1]; S1 [2]; S1 [3]}, L4 ⊕ {S2 [1]; S1 [2]; S1 [4]}, L4 ⊕ {S2 [1]; S2 [3]}, and L4 ⊕ {S1 [1]; S1 [2]; S1 [3]; S1 [4]}. Now – #(L4 ⊕ {S2 [1]; S2 [1]}) = #(L4 ⊕ {S2 [1]; S1 [1]}) + #(L4 ⊕ S2 [1]) = 31, – #(L4 ⊕ {S2 [1]; S1 [1]; S1 [2]}) = #(L4 ⊕ {S2 [1]; S1 [1]}) + #(S5 ⊕ S1 [3]) = #(L4 ⊕ {S2 [1]; S1 [1]}) + #(S5 ) + #(S2 )#(S2 ) = 20, – #(L4 ⊕ {S2 [1]; S1 [1]; S1 [3]}) = #(L4 ⊕ {S2 [1]; S1 [1]}) + #(S4 ⊕ {S1 [2]; S1 [2]}) = #(L4 ⊕ {S2 [1]; S1 [1]}) + #(S4 ) = 18, – #(L4 ⊕ {S2 [1]; S1 [2]; S1 [3]}) = #(L4 ⊕ {S2 [1]; S1 [2]}) + #(S5 ⊕ S1 [3]) = 22, – #(L4 ⊕ {S2 [1]; S1 [2]; S1 [4]}) = #(L4 ⊕ {S2 [1]; S1 [2]}) + #(S5 ⊕ S1 [2]) = #(L4 ⊕ {S2 [1]; S1 [2]}) + #(S5 ) = 21, – #(L4 ⊕ {S2 [1]; S2 [2]}) = #(L4 ⊕ {S2 [1]; S1 [2]}) + #(L4 ⊕ S2 [1]) = 33, – #(L4 ⊕ {S2 [1]; S2 [3]}) = #(L4 ⊕ {S2 [1]; S1 [3]}) + #(L4 ⊕ S2 [1]) = 32, – #(L4 ⊕{S1 [1]; S1 [2]; S1 [3]; S1 [4]}) = #(L4 ⊕{S1 [1]; S1 [2]; S1 [3]})+#(S5 ⊕ S1 [3]) = 16. • If a fifth point is adjoined to L4 at any location, the result is a configuration containing a previously considered configuration [A, B] with #([A, B]) > 19. Therefore, we have considered all possible configurations that contain the loop L4 and no configuration [A, B] containing a copy of L4 can satisfy #([A, B]) = 19. Consequently, no configuration [A, B] containing a loop can satisfy #([A, B]) = 19. We now consider configurations that contain strings, but no loops. In the remainder of this section, we simply list the computations for the distinct equivalence classes of configurations.
Vol. 92 (2009)
A Missing Prime Configuration
51
8.3. Building on the string of length 8 From [9] we know that #(Sm ) > 19 for m ≥ 9. Thus, we need not consider any configurations that contain a string of more than 8 points. We also know that #(S8 ) = 13. Note that a configuration obtained by adjoining a point at the first or last position of Sm will result in Sm+1 . • One point adjoined to S8 : – #(S8 ⊕ S1 [3]) = #(S8 ) + #(S2 )#(S5 ) = 16, – #(S8 ⊕ S1 [4]) = #(S8 ) + #(S3 )#(S4 ) = 15. • Two – – – – – –
points adjoined to S8 : #(S8 ⊕ S2 [3]) = #(S8 ⊕ S1 [3]) + #(S8 ) = 29, #(S8 ⊕ {S1 [3]; S1 [4]}) = #(S8 ⊕ S1 [3]) + #(S4 )#(S4 ) = 20, #(S8 ⊕ {S1 [3]; S1 [5]}) = #(S8 ⊕ S1 [3]) + #(S4 )#(S3 ) = 18, #(S8 ⊕ {S1 [3]; S1 [6]}) = #(S8 ⊕ S1 [3]) + #(S5 ⊕ S1 [3])#(S2 ) = 20, #(S8 ⊕ {S1 [4]; S1 [5]}) = #(S8 ⊕ S1 [4]) + #(S5 )#(S3 ) = 18, #(S8 ⊕ S2 [4]) = #(S8 ⊕ S1 [4]) + #(S8 ) = 28.
• Three points adjoined to S8 : – #(S8 ⊕{S1 [3]; S1 [4]; S1 [5]}) = #(S8 ⊕{S1 [3]; S1 [5]})+#(S4 )#(S5 ) = 24, – #(S8 ⊕{S1 [3]; S1 [5]; S1 [6]}) = #(S8 ⊕{S1 [3]; S1 [5]})+#(S6 ⊕S1 [3])#(S2 ) = #(S8 ⊕ {S1 [3]; S1 [5]}) + (#(S6 ) + #(S2 )#(S3 ))#(S2 ) = 24. All other configurations contain a subconfiguration X with #(X) > 19. Therefore, no configuration [A, B] containing a copy of S8 can satisfy #([A, B]) = 19. 8.4. Building on the string of length 7 From [9] we know #(S7 ) = 8. Note that we do not need to consider any configurations containing a subconfiguration equivalent to S8 . • One point adjoined to S7 : – #(S7 ⊕ S1 [3]) = #(S7 ) + #(S2 )#(S4 ) = 10, – #(S7 ⊕ S1 [4]) = #(S7 ) + #(S3 )#(S3 ) = 9. • Two – – – –
points adjoined to S7 : #(S7 ⊕ S2 [3]) = #(S7 ⊕ S1 [3]) + #(S7 ) = 18, #(S7 ⊕ {S1 [3]; S1 [4]}) = #(S7 ⊕ S1 [3]) + #(S4 )#(S3 ) = 12, #(S7 ⊕ {S1 [3]; S1 [5]}) = #(S7 ⊕ S1 [3]) + #(S4 )#(S2 ) = 12, #(S7 ⊕ S2 [4]) = #(S7 ⊕ S1 [4]) + #(S7 ) = 17.
• Three points adjoined to S7 : (Note that S7 ⊕ S3 [3] includes a string of length 8, which we have already considered.) – #(S7 ⊕ {S2 [3]; S1 [3]}) = #(S7 ⊕ S2 [3]) + #(S2 )#(S2 )#(S4 ) = 20, – #(S7 ⊕ {S2 [3]; S1 [4]}) = #(S7 ⊕ S2 [3]) + #(S5 )#(S3 ) = 21, – #(S7 ⊕ {S2 [3]; S1 [5]}) = #(S7 ⊕ S2 [3]) + #(S5 ⊕ S1 [3])#(S2 ) = 22, – #(S7 ⊕ {S1 [3]; S2 [4]}) = #(S7 ⊕ {S1 [3]; S1 [4]}) + #(S7 ⊕ S1 [3]) = 22,
52
C. C. Blackburn et al.
J. Geom.
– #(S7 ⊕ {S1 [3]; S1 [4]; S1 [5]}) = #(S7 ⊕ {S1 [3]; S1 [4]}) + #(S5 ⊕ S1 [3])#(S2 ) = 16, – #(S7 ⊕ S3 [4]) = #(S7 ⊕ S2 [4]) + #(S7 ⊕ S1 [4]) = 26, – #(S7 ⊕ {S2 [4]; S1 [4]}) = #(S7 ⊕ S2 [4]) + #(S3 )#(S3 )#(S2 ) = 18. • Four points adjoined to S7 : – #(S7 ⊕ {S2 [4]; S2 [4]}) = #(S7 ⊕ {S2 [4]; S1 [4]}) + #(S7 ⊕ S2 [4]) = 35. • Adjoining any additional points to S7 will result in a configuration containing one we have considered previously. Therefore, no configuration [A, B] containing a copy of S7 can satisfy #([A, B]) = 19. 8.5. Building on the string of length 6 From [9] we know #(S6 ) = 5. • One point adjoined to S6 : – #(S6 ⊕ S1 [3]) = #(S6 ) + #(S2 )#(S3 ) = 6. • Two points adjoined to S6 : – #(S6 ⊕ S2 [3]) = #(S6 ⊕ S1 [3]) + #(S6 ) = 11, – #(S6 ⊕ {S1 [3]; S1 [4]}) = #(S6 ⊕ S1 [3]) + #(S4 )#(S2 ) = 8. • Three points adjoined to S6 : – #(S6 ⊕ {S2 [3]; S1 [3]}) = #(S6 ⊕ S2 [3]) + #(S2 )#(S2 )#(S3 ) = 12, – #(S6 ⊕ {S2 [3]; S1 [4]}) = #(S6 ⊕ S2 [3]) + #(S5 )#(S2 ) = 14. • Four points adjoined to S6 : (Note that S6 ⊕S3 [3] contains a string of length 7.) – #(S6 ⊕ {S2 [3]; S2 [3]}) = #(S6 ⊕ {S2 [3]; S1 [3]}) + #(S6 ⊕ S2 [3]) = 23, – #(S6 ⊕ {S2 [3]; S1 [3]; S1 [4]}) = #(S6 ⊕ {S2 [3]; S1 [3]}) + #(S5 ⊕ S1 [3])#(S2 ) = 16, – #(S6 ⊕ {S2 [3]; S2 [4]}) = #(S6 ⊕ {S2 [3]; S1 [4]}) + #(S6 ⊕ S2 [3]) = 25. • Adjoining any additional points to S6 will result in a configuration containing one we have considered previously. Therefore, no configuration [A, B] containing a copy of S6 can satisfy #([A, B]) = 19. 8.6. Building on the string of length 5 From [9] we know #(S5 ) = 3. • One point adjoined to S5 : – #(S5 ⊕ S1 [3]) = 4, as seen earlier. • Two points adjoined to S5 : – #(S5 ⊕ S2 [3]) = #(S5 ⊕ S1 [3]) + #(S5 ) = 7.
Vol. 92 (2009)
A Missing Prime Configuration
53
• Three points adjoined to S5 : (Note that S5 ⊕ S3 [3] contains a string of length 6.) – #(S5 ⊕ {S2 [3]; S1 [3]}) = #(S5 ⊕ S2 [3]) + #(S2 )#(S2 )#(S2 ) = 8. • Four points adjoined to S5 : – #(S5 ⊕ {S2 [3]; S2 [3]}) = #(S5 ⊕ {S2 [3]; S1 [3]}) + #(S5 ⊕ S2 [3]) = 15. • Five points adjoined to S5 : – #(S5 ⊕ {S2 [3]; S2 [3]; S1 [3]}) = #(S5 ⊕ {S2 [3]; S2 [3]}) + #(S2 )4 = 16. • Six points adjoined to S5 : – #(S5 ⊕ {S2 [3]; S2 [3]; S2 [3]}) = #(S5 ⊕ {S2 [3]; S2 [3]; S1 [3]}) + #(S5 ⊕ {S2 [3]; S2 [3]}) = 31. • Adjoining any additional points to S5 will result in a configuration containing one we have considered previously. Therefore, no configuration [A, B] containing a copy of S5 can satisfy #([A, B]) = 19. 8.7. Building on smaller strings Adjoining any points to a string of length smaller than 5 will result in either a configuration that provides no new elements at each location or a configuration that we have already considered. Therefore, we see that there is no finite configuration [A, B] in H(Rn ) with #([A, B]) = 19.
9. Infinite configurations In the previous section we saw that there are no finite configurations [A, B] for which #([A, B]) = 19, but what about infinite configurations? If [A, B] is an infinite configuration, we denote by #([A, B]t ) the number of elements (if finite) between A and B at the distance t from A, where 0 < t < h(A, B). In the remainder of this paper we will show that for every infinite configuration [A, B] with #([A, B]t ) < ∞, there is a finite configuration [A, B]F with #([A, B]F ) = #([A, B]t ). This will finish our proof that no configuration [A, B], finite or infinite, exists having exactly 19 elements at any location between A and B. 9.1. Finite conversion algorithm Now we begin investigating infinite configurations. From Theorem 6.4 we know that there is a finite configuration that realizes any desired finite collection of adjacencies. Now we introduce the Finite Conversion Algorithm to take an infinite configuration [A, B] with #([A, B]t ) < ∞ and make finite elements and adjacencies to create a finite configuration [A, B]F where #([A, B]t ) = #([A, B]F ). We begin with two preliminary lemmas. The proof of the first is straightforward and left to the reader.
54
C. C. Blackburn et al.
J. Geom.
Lemma 9.1. Let C ∈ H(Rn ) with U ∈ UC , the subspace topology of C. If |U | = ∞, then there exist infinitely many subsets V ⊂ U with V ∈ UC . Lemma 9.2. Let [A, B] be a configuration and let C = CA,B,t . If |U | = ∞ for some U ∈ ΥA,B,t , then |ΥA,B,t | = ∞. Proof. Suppose |U | = ∞ for some U ∈ ΥA,B,t . By Lemma 9.1, there exist infinitely many subsets V ⊂ U with V ∈ UC . Choose V to be one of these sets. 1. If a ∈ qA (V ), then a ∈ qA (U ). So there exists c ∈ [a]C such that c ∈ / U and, hence, c ∈ / V. 2. If b ∈ qB (V ), then b ∈ qB (U ). So there exists c ∈ [b]C such that c ∈ / U and, hence, c ∈ / V. Thus, we have V ∈ ΥA,B,t for all V ⊂ U , and |ΥA,B,t | = ∞.
Now we introduce the Finite Conversion Algorithm that shows us how to construct a finite configuration [A, B]F from an infinite configuration [A, B] with #([A, B]t ) < ∞. Later we will show that #([A, B]F ) = #([A, B]t ). Finite Conversion Algorithm. Let [A, B] be an infinite configuration with #([A, B]t ) = k for some k ∈ N, k ≥ 2 and 0 < t < h(A, B). Define CA,B,t and ΥA,B,t as before, and let QA = {a : a ∈ qA (U ) for some U ∈ ΥA,B,t } and QB = {b : b ∈ qB (U ) for some U ∈ ΥA,B,t }. By Lemma 9.2 and our assumption that #([A, B]t ) = k, we know that |U | is finite for all U ∈ ΥA,B,t . Thus |QA | and |QB | must be finite. Let l = |QA | and m = |QB |. Define the finite configuration [A, B]F = [Y, Z] with finite elements Y and Z as follows. Step 1: For each ai ∈ QA (where 1 ≤ i ≤ l), place a point yi ∈ Y . Similarly, for each bj ∈ QB (where 1 ≤ j ≤ m), place a point zj ∈ Z. Step 2: For each ai ∈ QA (where 1 ≤ i ≤ l), if there exists at least one point c ∈ [ai ]C such that c ∈ / U for every U ∈ ΥA,B,t , place an endpoint zyi ∈ Z and make yi ∈ Y adjacent to zyi . Step 3: For each bj ∈ QB (where 1 ≤ j ≤ m), if there exists at least one point c ∈ [bj ]C such that c ∈ / U for every U ∈ ΥA,B,t , place an endpoint yzj ∈ Y and make zj ∈ Z adjacent to yzj . Step 4: For each c ∈ [ai ]C , if c ∈ U for some U ∈ ΥA,B,t , make yi adjacent to the zj ∈ Z which corresponds to the bj ∈ B such that c ∈ [bj ]C . For any [a]C , let [a]C(ΥA,B,t ) = {c ∈ [a]C : c ∈ U for some U ∈ ΥA,B,t }. If |[a]C(ΥA,B,t ) | = ∞, then we would have either an infinite U or an infinite number of U ’s containing a finite number of elements, both of which contradict the fact that |ΥA,B,t | = k. Thus, |[a]C(ΥA,B,t ) | is finite for every [ai ]C . So we have all we need to ensure that |Y | and |Z| are finite. Additionally, Y and Z must be bounded, and as the finite union of sets of single points, they must also be closed. Therefore, Y and Z are in H(Rn ).
Vol. 92 (2009)
A Missing Prime Configuration A
B b0
55
a0
b1
c0
c1
a1
b2
c2
a2
c3
c4
A
b3 c5
a3 c6
B
Figure 11. Infinite configuration [A, B] with #([A, B]) = 9. zy
0
y0
z1
y1
zy
yz
z2
2
1
y2
z3
yz
3
Figure 12. Finite configuration [A, B]F with #([A, B]F ) = 9. We also know that each point in Y is adjacent to a certain subset of points in Z. Furthermore, any point zj will either be adjacent to some point yi or yzj in Y . So by construction, [Y, Z] = [A, B]F is a finite configuration. To see how the Finite Conversion Algorithm works, consider the infinite configuration [A, B] in Figure 11 where A and B are the indicated union of points and the largest set C between A and B is the collection of lighter shaded points. We note that #([A, B]t ) = 9. In this example, ΥA,B,t = {∅, {c1 }, {c2 }, {c4 }, {c5 }, {c1 , c4 }, {c1 , c5 }, {c2 , c4 }, {c2 , c5 }}. So QA = {a0 , a1 , a2 } and QB = {b1 , b2 , b3 }. In step 1 of the Finite Conversion Algorithm we make y0 , y1 , y2 ∈ Y and z1 , z2 , z3 ∈ Z. In step 2 we have zy0 , zy1 ∈ Z, and step 3 gives yz2 , yz3 ∈ Y . Finally, using the additional adjacencies from step 4, we arrive at the configuration [A, B]F as illustrated in Figure 12. Notice that #([A, B]F ) = 9. 9.2. Matching configurations Now that we can construct a finite configuration [A, B]F from any infinite configuration [A, B] with #([A, B]t ) < ∞ using the Finite Conversion Algorithm, we are ready to prove that #([A, B]t ) = #([A, B]F ). Suppose that we convert a configuration [A, B] to a finite configuration [Y, Z] as described above. For 0 < t < h(A, B), let C = CA,B,t . If 0 < t0 < h(Y, Z), let W = WY,Z,t0 = (Y )t0 ∩(Z)h(Y,Z)−t0 . Then h(Y, W ) = t0 and h(W, Z) = h(Y, Z)−t0 . We have defined ΥY,Z,t0 as the set of all UF ∈ UW such that 1. for all y ∈ qY (UF ), there exists w ∈ [y]W such that w ∈ / UF , and 2. for all z ∈ qZ (UF ), there exists w ∈ [z]W such that w ∈ / UF . Theorem 9.1. Let [A, B] be an infinite configuration with #([A, B]t ) < ∞ for some 0 < t < h(A, B) and [Y, Z] the corresponding finite configuration as described in
56
C. C. Blackburn et al.
J. Geom.
the Finite Conversion Algorithm. Let ΥA,B,t and ΥY,Z,t0 be defined as above. Then |ΥA,B,t | = |ΥY,Z,t0 |. Proof. Fix t and t0 and let Υ = ΥA,B,t and ΥF = ΥY,Z,t0 . We know that the null set is in both Υ and ΥF , so we can focus our attention on the nonempty elements of both of these sets. To demonstrate the desired equality, we prove |Υ| ≤ |ΥF | and |ΥF | ≤ |Υ|. We begin by showing |Υ| ≤ |ΥF |. Suppose U ∈ Υ. We know that |U | = m for some m ∈ N, so U = {c1 , . . . , cm }, where ck ∈ C for all 1 ≤ k ≤ m. So for each k, ck m ack and ck m bck for some ack ∈ A and bck ∈ B. This means that ack m bck , implying that the corresponding points yck ∈ Y and zck ∈ Z are adjacent by step 4 of our algorithm. Each pair of these points yck , zck must have a corresponding wk ∈ W which lies between them. Let UF = {wk : 1 ≤ k ≤ m}. We will show that UF ∈ ΥF . Let y ∈ qY (UF ). There is a k so that y = qY (wk ) and y is adjacent to wk . For the corresponding ck , we know [ack ]C contains some c0 ∈ C so that c0 6∈ U . If c0 is in some other U 0 ∈ Υ, then c0 is between ack and some bc0 ∈ B, where bc0 ∈ qB (U 0 ). Thus we have corresponding adjacent points y = yck and zc0 in [X, Y ], and a point between them, wc0 ∈ W . If wc0 were in UF , then c0 ∈ U , a contradiction. On the other hand, if c0 is not in U 0 for every U 0 ∈ Υ, then we know that yck is adjacent to the endpoint zyck by step 2 of our algorithm, and the point w ∈ [yck ]W adjacent to zyck is not in UF . In either case, [y]W contains a point w ∈ / UF . Similarly, every [z]W ∈ qZ (UF ) contains a w ∈ / UF . Hence, UF ∈ ΥF . Now we show that each element of Υ corresponds to a unique element of ΥF . Suppose that we have U 6= U 0 ∈ Υ. Without loss of generality, we assume that there exists some c0 ∈ U 0 with c0 ∈ / U . Let UF0 be the set corresponding to U 0 using the process described above. We know that c0 m a0 and c0 m b0 for some a0 ∈ A and b0 ∈ B, so UF0 will contain a point w0 between the corresponding points y 0 and z 0 in [Y, Z]. However, no such point will be created in UF , since c0 ∈ / U . Therefore, we have UF 6= UF0 . This means that every element of Υ corresponds to some unique element of ΥF , so |Υ| ≤ |ΥF | .
(9.1)
Now we show |ΥF | ≤ |Υ|. Let UF ∈ ΥF . We will show that there is a set U ∗ ∈ Υ related to UF . Since [Y, Z] is a finite configuration, we know that UF is finite, so UF = {w1 , . . . , wm } for some m ∈ N. Choose k so that 1 ≤ k ≤ m. Then wk m ywk and wk m zwk for some ywk ∈ Y and zwk ∈ Z. So ywk m zwk . There are three possible ways to obtain the adjacency ywk m zwk from the Finite Conversion Algorithm: 1. zwk is an endpoint (zwk = zywk from step 2 of the algorithm), 2. ywk is an endpoint (ywk = yzwk from step 3 of the algorithm), 3. ywk m zwk (from step 4 of the algorithm).
Vol. 92 (2009)
A Missing Prime Configuration
57
In the first case, the only point in UF adjacent to zywk is wk , so [zywk ]W = {wk }, which contradicts the fact that for all z ∈ qZ (UF ) there must exist w ∈ [z]W so that w 6∈ UF . The second case will create a similar contradiction. Hence, this adjacency relationship must have been created by step 4 of the algorithm. Thus, there exist adjacent points awk ∈ A and bwk ∈ B that have some point ck between them, where ck ∈ U for some U ∈ Υ. Let U ∗ = {ck : 1 ≤ k ≤ m}. Now we show that U ∗ ∈ Υ. Let a ∈ qA (U ∗ ). Then [a]C = [awk ]C for some awk adjacent to some ck . We proceed by contradiction. Let 1 ≤ k ≤ m and suppose that for every c ∈ [awk ]C , we have c ∈ U ∗ . This means that awk is only adjacent to points of the form bwl where 1 ≤ l ≤ m. Then the corresponding point ywk is only adjacent to points of the form zwl . For each l, there is a point cl ∈ U ∗ between awk and bwl , and a corresponding point wl between ywk and zwl . However, then [ywk ]W contains only the points wl ∈ UF , but this contradicts our condition that for all y ∈ qY (UF ) there is a point w ∈ [y]W such that w 6∈ UF . Thus, we have that for all a ∈ qA (U ∗ ), there exists c ∈ [a]C such that c ∈ / U ∗ . A similar argument shows that for all b ∈ qB (U ∗ ), there exists c ∈ [b]C such that b ∈ / U ∗ . Therefore, U ∗ ∈ Υ. Now, suppose that we have UF 6= UF0 ∈ ΥF . Without loss of generality, we assume that there exists a w0 ∈ UF0 with w0 ∈ / UF . We create U ∗ ∈ Υ from UF and U 0∗ 0 from UF using the process given above. We know that there will exist a point c0 ∈ U 0∗ that corresponds to w0 , but because w0 ∈ / UF , we have c0 ∈ / U ∗ . Thus, ∗ 0∗ F U 6= U , and we have that each UF ∈ Υ corresponds to a unique U ∗ ∈ Υ. Hence, |ΥF | ≤ |Υ| .
(9.2)
Finally, if we combine the inequalities (9.1) and (9.2), we find that |Υ| = |ΥF |. The Finite Conversion Algorithm and Theorem 9.1 show that #([A, B]t ) is independent of t for an infinite configuration [A, B]. Recall that the creation of the configuration [A, B]F depends on the sets QA and QB (which are independent of t) and the set Ct = (A)t ∩ (B)h(A,B)−t . Now if a ∈ A and b ∈ B such that a m b, then the point ct on ab with dE (a, ct ) = t is in Ct . For each 0 < t0 < h(A, B) there is a corresponding point ct0 ∈ Ct0 = (A)t0 ∩ (B)h(A,B)−t0 with ct0 on ab with dE (a, ct0 ) = t0 . So there is a one-to-one correspondence between Ct and Ct0 with corresponding adjacencies. The construction of [A, B]F depends only on these adjacencies, which are independent of t. Therefore, #([A, B]t ) is independent of t and we write #([A, B]) for an infinite configuration if there is a finite number of elements at each location between A and B. From Section 8 we know that there exists no finite configuration [A, B]F such that #([A, B]F ) = 19. When combined with the fact that for each infinite configuration [A, B] we can construct a finite configuration [A, B]F with #([A, B]) = #([A, B]F ), the next theorem follows.
58
C. C. Blackburn et al.
J. Geom.
Theorem 9.2. There is no configuration [A, B], infinite or finite, such that #([A, B]) = 19.
10. Conclusion In Section 7 we constructed configurations [A, B] satisfying #([A, B]) = k for k from 1 to 18. In Section 8, we found additional configurations [A, B] for which #([A, B]) = k for k from 20 to 26, 28, 29, 31 to 33, and 35. Using the multiplicative property of configurations from Theorem 6.1, combining the configurations S5 = [A1 , B1 ] and L4 ⊕ {S1 [3]; S1 [4]} = [A2 , B2 ] will create a configuration [A, B] = [A1 ∪ A2 , B1 ∪ B2 ] with #([A, B]) = 27. Similarly, combining S6 with S6 ⊕ S1 [3] creates a configuration [A, B] satisfying #([A, B]) = 30, combining S4 with L4 ⊕ {S2 [1]; S1 [3]} creates a configuration [A, B] satisfying #([A, B]) = 34, and combining S6 ⊕S1 [3] with itself provides a configuration [A, B] with #([A, B]) = 36. This gives us configurations [A, B] satisfying #([A, B]) = k for every k between 1 and 36, excluding k = 19. That there are no configurations [A, B] for which #([A, B]) = 19 is interesting in and of itself, but there are also applications of this fact to graph theory. It is not surprising that finite configurations can be connected to graphs and in [2] the authors show that there exists no bipartite graph G with exactly 19 edge covers.
11. Acknowledgements The authors want to thank the National Science Foundation for their support of this project. In addition, we express our appreciation to the referee whose thorough review and valuable suggestions made for a much better paper.
References [1] C. Bay, A. Lembcke, and S. Schlicker, When lines go bad in hyperspace, Demonstratio Math. 38 (2005), 689–701. [2] C. Blackburn, K. Honigs, S. Schlicker, and A. Zupan, Graph theory applications of the Hausdorff metric geometry, in preparation. [3] L. M. Blumenthal, Theory and Applications of Distance Geometry, Oxford University Press, 1953. [4] A. Bogdewicz, On affine and metric lines in the space of convex bodies, Rend. Circ. Mat. di Palermo (2) Suppl. 70 (2002), 57–78. [5] A. Bogdewicz, Some metric properties of hyperspaces, Demonstratio Math. XXXIII (2000), 135–149. [6] D. Braun, J. Mayberry, A. Powers, and S. Schlicker, A singular introduction to the Hausdorff metric geometry, Pi Mu Epsilon Journal 12 (2005), 129–138. [7] W. W. Fairchild, C. Ionescu Tulcea, Topology, W. B. Saunders Company, 1971.
Vol. 92 (2009)
A Missing Prime Configuration
59
[8] T. Koshy, Fibonacci and Lucas Numbers with Applications, John Wiley & Sons, Inc., New York, 2001. [9] K. Lund, P. Sigmon, and S. Schlicker, Fibonacci sequences in the space of compact sets, Involve 1 (2008), 197–215. [10] R. Schneider, Convex Bodies: The Brunn–Minkowski Theory, Cambridge University Press, 1993. Chantel C. Blackburn Department of Mathematics University of Arizona Tucson, Arizona 85721-0066 e-mail:
[email protected] Kristina Lund 5541 Rivertown Circle SW Wyoming, MI 49418 USA e-mail:
[email protected] Steven Schlicker Department of Mathematics Grand Valley State University Allendale, MI 49401-9403 e-mail:
[email protected] Patrick Sigmon 11641 Broadfield Court Raleigh, NC 27617 e-mail:
[email protected] Alexander Zupan Department of Mathematics University of Iowa Iowa City IA 52242 e-mail:
[email protected] Received: 30 June 2006. Revised: 14 October 2008.