Colorful Results on Euclidean Distance Graphs and Their Chromatic Numbers by Matt Noble A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 7, 2012 Keywords: Euclidean distance graphs, chromatic number, coloring the rationals Copyright 2012 by Matt Noble Approved by Peter D. Johnson, Chair, Professor of Mathematics and Statistics Chris Rodger, C. Harry Knowles Professor of Mathematical Sciences Dean Ho man, Professor of Mathematics and Statistics Abstract In this work, we study Euclidean distance graphs with vertex set Qn, the n-dimensional rational space. In particular, we deal with the chromatic numbers (and some related param- eters) of such graphs when n = 2 or n = 3. A short history of the topic is given before we approach a few open problems related to the subject. Some of these questions are resolved, either completely or partially. For the problems able to resist our advances, methods are given that hopefully will lead to answers in future work. ii Acknowledgments Professionally, I would like to thank the Auburn University Department of Mathematics { in particular, Peter D. Johnson for being a great advisor and a stand-up guy in general. Personally, I would like to thank Linda, Mark, Seth, and Abby. They know why. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Single-distance Graphs in Q3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Introduction and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Two-distance Graphs in Q2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.4 Further Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4 The Second Babai Number and Second Clique Number of Q3 . . . . . . . . . . . 25 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3 Further Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5 Un nished Business Concerning Single-distance Graphs in Q3 . . . . . . . . . . 36 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 iv 5.2 Number Theory Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.3 Non-existence of Triangles in G(Q3;p2k) . . . . . . . . . . . . . . . . . . . . 38 5.4 An Algorithmic Search for 4-chromatic Subgraphs of G(Q3;p2k) . . . . . . . 43 5.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 v List of Figures 1.1 The Moser Spindle, a 4-chromatic subgraph of G(R2;1) . . . . . . . . . . . . . . 5 2.1 Summing an odd number of length pn vectors . . . . . . . . . . . . . . . . . . 8 2.2 Pair of triangles in G(Z3;p2s) . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Alternate triangle parameterization in G(Z3;3p6s) . . . . . . . . . . . . . . . . 13 2.4 Three triangles in G(Z3;3p6s) . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1 Tile leading to a proper 3-coloring of G(Z2;f1;p26g) . . . . . . . . . . . . . . . 23 4.1 Regular pentagon with diagonals . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Similar triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.3 Regular octahedron with labeled vertices . . . . . . . . . . . . . . . . . . . . . . 31 4.4 Pair of triangles with vertices in Q3 . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.5 Triangle in Q3 with labeled sides and vertices . . . . . . . . . . . . . . . . . . . 34 5.1 Point (a;b) with its image in a rational rotation of R2 . . . . . . . . . . . . . . . 41 5.2 The Mycielski-Gr otzsch graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.3 Circles in R3 along with a 5-cycle in G(Q3;p10) . . . . . . . . . . . . . . . . . . 45 vi List of Tables 2.1 List of congruences modulo 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.1 The six possible two-distance con gurations in R3 . . . . . . . . . . . . . . . . . 26 vii Chapter 1 Introduction 1.1 De nitions The idea most fundamental to this work is that of the distance graph. Let (X; ) be a metric space where (x;y) denotes the distance between points x;y2X, and suppose that D (0;1). We de ne the distance graph G(X;D) as the graph with vertex set X where x;y 2 X are adjacent if and only if (x;y) 2 D. We denote by (X;D) the chromatic number of such a graph { that is to say, the minimum number of colors needed to color X such that no two adjacent vertices receive the same color. In the parlance associated with the subject, it is said that such a coloring \forbids" the set of distances D. In the case where D = fdg for some d > 0, we will often refer to the associated graph as a single-distance graph and write G(X;d) instead of the technically consistent but more awkward-looking G(X;fdg). As is standard, for any set X and positive integer n, we will write Xn for the set of all n-tuples whose individual entries are elements of X. Throughout this work, we will continue the tradition of using R and Q to denote the elds of real numbers and rational numbers respectively, and Z to denote the ring of integers. For any X R, we designate by X+ all x2X such that x> 0. One bit of notation that is perhaps non-standard is the description of vectors in the \arrowed bracket" component form instead of the more prevalent \i, j, k unit vector" form. Precisely de ned, for any v1;:::;vn2R, will be the vector with the origin as its initial point and (v1;:::;vn) as its terminal point. In almost all publications concerning the chromatic numbers of distance graphs, the distance metric is kept the same throughout the article. Indeed, that will be the case here. Throughout this work, for any distance graph mentioned, the distance function 1 used will be the usual Euclidean distance metric. In other words, if X Rn for some positive integer n and x;y 2 X where x = (x1;:::;xn) and y = (y1;:::;yn), (x;y) = p(x 1 y1)2 +:::+ (xn yn)2. Occasionally, it may be convenient to express this distance (x;y) using the alternate notation jx yj. The above notation and de nitions provide a nice starting point for acquaintance with the subject of Euclidean distance graph coloring. Rest assured that they will be omnipresent in this work. However, a few concepts such as the Babai numbers, clique numbers, and some terms from number theory will appear in an individual chapter and then not be needed again. We will save the introduction of these terms until the appropriate time. 1.2 History The most comprehensive investigation into the history of Euclidean distance graph coloring was done by Soifer in [26]. A full investigation into the research (both past and present) of Euclidean distance graphs on rational points is given in Johnson?s compendium work [14]. These are the facts of the case. In 1950 Edward Nelson, then an undergraduate at the University of Chicago, posed the following question to fellow student John Isbell: \What is the minimum number of colors needed to color the real plane such that no two points a distance 1 apart receive the same color?" The problem has come to be known as the \chromatic number of the plane". In the no- tation given in the previous section, Nelson?s question amounts to determining (R2;1). Nelson himself proved that 4 (R2;1) and Isbell, applying some ideas of Hugo Hadwiger [10], showed that (R2;1) 7. Amazingly and frustratingly, these bounds have not been improved. As time marched on, the chromatic number of the plane problem was slowly dissem- inated through the mathematical landscape. Major gures in its dispersal include Martin 2 Gardner [9], who made note of the problem in Scienti c American, the brothers Leo and Willy Moser [20], who provided the simplest proof that 4 (R2;1) with the creation of the Moser spindle (see Figure 1.1 at the end of this chapter), and the great Paul Erd}os, who served to popularize the subject of Euclidean distance graph coloring with frequent mentions in print and in lectures. In any account, Nelson?s problem had become well-known by the late 1960s. In 1973, Douglas Woodall [27] added a new wrinkle to the edgling industry of coloring Euclidean distance graphs. In an article primarily concerned with coloring R2, he included a relatively simple proof showing that (Q2;1) = 2. Although he never published anything else on the topic of coloring the rationals, Woodall?s result seems to be the rst instance of anyone considering the chromatic number of a distance graph with vertex set Qn for any positive integer n. A few years later, Miro Benda and Micha Perles made a much larger contribution to the subject with the creation of Colorings of Metric Spaces, the most in uential article ever written on coloring Qn. Note that the last sentence contains the word \creation" instead of \publication" as Benda and Perles? work did not appear in print until the year 2000 [2]. Even as such, copies of the manuscript were widely circulated through the mathematical community, and by the mid-1980s had achieved something of a legendary status (an account of its curious history is given in [16]). Major ndings of Colorings include the facts that (Q3;1) = 2 and (Q4;1) = 4. However, the most important element of Benda and Perles? work is the algebraic methods they used to obtain their results. These methods served to inspire Joseph Zaks, Kiran Chilakamarri, and Peter Johnson, each of whom published extensively on the subject and whose work has brought us where we are today. At present, I would guess that there have been over a hundred scholarly articles written solely on the topic of coloring the rational space Qn. Yet with all this work, there are still more open questions than there are questions that have been answered. In this dissertation, we will tackle a few of these open questions. 3 1.3 Outline Chapter 2 will be an investigation into the chromatic numbers of single-distance graphs with vertex set Q3. We will address the open question of determining (Q3;d) for arbitrary values of d leading to the result that for all odd, positive, square-free integers n whose prime factorization contains no factors congruent to 2 (mod 3), (Q3;p2n) = 4. As stated, this result may seem somewhat narrow, but combined with previous work it actually goes a long way toward fully resolving this open problem. In Chapter 3, we study distance graphs of the form G(Q2;D) where the set of distances D is of size 2. Su cient conditions are given on the set D for (Q2;D) = 3. This answers in the a rmative an existence question posed by Johnson in [14]. We then close the chapter with two additional questions related to such graphs along with a partial solution. Chapter 4 will consist of the study of two values closely related to the chromatic number of a Euclidean distance graph. We will rst de ne the nth Babai number and the nth clique number of a metric space (X; ) and then use previous results of several di erent authors to conclude that the second clique number of Q3 is 6 which in turn implies that the second Babai number of Q3 is greater than or equal to 6. A few observations are then made concerning a proper coloring of the graph G(Q3;f2;p2g) which hopefully may be used to further increase the lower bound for the second Babai number of Q3. Chapter 5 will act as something of a catch-all section. We will begin by revisiting the problem rst looked at in Chapter 2, that of determining (Q3;d) for an arbitrary distance d, and illustrating the di culties present when d is of the form p2n for some odd, posi- tive, square-free integer n which contains at least one prime factor congruent to 2 (mod 3). Unfortunately (or fortunately, depending on your point of view), this will necessitate the introduction of several terms and ideas from classical number theory. Once familiar with the basic facts and language of quadratic residues, we will demonstrate how Legendre?s Theorem may be used in conjunction with lemmata from graph theory and geometry as an aid to nd subgraphs of G(Q3;p2n) which have chromatic number 4. We close by putting all these 4 pieces together in the form of a search algorithm which hopefully can be used to determine (Q3;p10). Figure 1.1: The Moser Spindle, a 4-chromatic subgraph of G(R2;1) 5 Chapter 2 Single-distance Graphs in Q3 2.1 Introduction and Preliminaries In this chapter, we study single-distance graphs with vertex set Q3 and address the following question: Given arbitrary distance d, (Q3;d) = ? Before attempting an answer, we observe a lemma which will considerably lighten our workload. Lemma 2.1 For any q2Q+, D (0;1), and positive integer n, (Qn;D) = (Qn;qD). Proof Consider the function f : Qn!Qn where for any x2Qn such that x = (x1;:::;xn), f(x) = (qx1;:::;qxn). Certainly f is an isomorphism between the vertex set of G(Qn;D) and the vertex set of G(Qn;qD). For any x;y2Qn and d > 0, jx yj = d if and only if jf(x) f(y)j= qd. Thus the graphs G(Qn;D) and G(Qn;qD) are isomorphic and we have that (Qn;D) = (Qn;qD). Lemma 2.1 is a relatively simple observation (it was seen without proof in [14], [13], and probably elsewhere as well), but it is of vital importance to the study of distance graphs on rational points. With this in mind, and considering the fact that any distance realized between points of Q3 is of the formpq for some positive q2Q, the original question can be completely resolved by answering the following: Given any square-free positive integer z, (Q3;pz) = ? 6 Of course, for any d1;d2 > 0 where d1 and d2 are not rational multiples of each other, Lemma 2.1 does not apply and we have no immediate guarantee that (Q3;d1) = (Q3;d2). It is an interesting quirk of mathematical history that this fact went seemingly unnoticed for quite some time. As mentioned in the previous chapter, Woodall [27] in 1973 made the rst foray into coloring the rationals by showing that (Q2;1) = 2. Benda and Perles [2] also focused on the unit distance, showing that (Q3;1) = 2 and (Q4;1) = 4. Although they did not publish their ndings until much later, the results of Benda and Perles work were well-known in the late 1970s. It was not until 1989 that Johnson [17] strayed from the unit-distance pack with the following theorem. Theorem 2.1 Let D0 =f qp q : p;q are both odd positive integersg. Then (Q 3;D0) = 2. Johnson?s result is much stronger than what is needed for our current discussion; however it does immediately give us that for any odd positive integer z such that pz is a distance actually realized in Q3, (Q3;pz) = 2. In a 1993 paper [6], Chow characterized all single- distance graphs with vertex set Q3 which could not be properly 2-colored. Crucial to his work was the following lemma for which we provide an alternate proof. Lemma 2.2 Let n2Z+ where n 2 (mod 4). Then (Z3;pn) 3. Proof We will use the elementary graph theory fact that a simple graph has chromatic number greater than or equal to 3 if and only if it contains an odd cycle. Suppose n = 2d for some odd positive integer d. By a well-known characterization of integers representable as the sum of three squares (see [24]), we have that there exist integers a;b;c such that a2 +b2 +c2 = n. Since n is even but not divisible by 4, it must be that exactly two of a;b;c are odd. Without loss of generality, we may assume that a and b are both odd and that a;b;c 0. Now consider the vector V =. We will create an odd number of vectors, each of whose entries consist of rearrangements or negatives of the entries of V, which together 7 b 8 >< >: ... a 1 8 >< >: < b;a;c> ... < b;a;c> < b;c;a> + Figure 2.1: Summing an odd number of length pn vectors sum to the zero vector. We begin with b copies of the vector , a 1 copies of the vector < b;a;c>, and single copies of the vectors < b;c;a> and as shown in Figure 2.1. The total number of vectors is a+b+1 which is odd. Note that the x-component entries of these vectors together sum to c. Note also that the y-component entries of these vectors consist of one \c" entry, an even number of \a" entries, and an even number of \b" entries. Replace half of the \a" entries with \ a" and half of the \b" entries with \ b". Now the y-component entries together sum to c. Similarly, we may replace a+b 22 of the z-component \c" entries with \ c" and one of the two z-component \a" entries with \ a". Now the z-component entries together sum to c as well. So we are left with an odd number of lengthpn vectors which together sum to . We may easily create an odd number of length pn vectors which together sum to < c; c; c > by multiplying every entry in the previous collection of vectors by -1. Putting these facts together, we have that for any odd z2Z, it is possible to create an odd number of length pn vectors that sum to < zc;zc;zc > and whose x-components, y- components, and z-components each have an arbitrarily large number of \a" entries. So use the above process to construct an odd number of lengthpn vectors that sum to and whose x-, y-, and z-components each have at least c2 \a" entries. Now replace those c2 \a" entries in the x-, y-, and z-components with \ a" giving us an odd number of length pn vectors that sum to < 0;0;0 >. 8 In a 2007 article [13], Johnson, Schneider, and Tiemeyer provided a nice upper bound for the chromatic numbers in question. This bound was achieved by computing the rst Babai number of Q3, but we intend to delay the introduction of the Babai numbers until Chapter 4 and rephrase their result in terms more appropriate to the matter at hand with the following theorem. Theorem 2.2 For any d> 0, (Q3;d) 4. In light of Lemmas 2.1 and 2.2 and Theorems 2.1 and 2.2, the original question is narrowed down to the following: Given any odd, positive, square-free integer p, does (Q3;p2p) = 3 or does (Q3;p2p) = 4? The main result of this chapter is that for all such values of p whose prime factorization contains no factors congruent to 2 (mod 3), (Q3;p2p) = 4. We obtain this conclusion by proving two slightly stronger results on coloring Z3. We will need the help of the following lemmata. Lemma 2.3 Let a;b;c2Z such that gcd(a;b;c) = 1 and a + b + c 0 (mod 2). Let V be the group of vectors generated by < a; b; c>, < a; c; b >, < b; a; c >, < b; c; a >, < c; a; b >, < c; b; a > under the usual vector addition. Then V = f< x;y;z >: x;y;z 2 Z and x + y + z 0 (mod 2)g. Proof Clearly V f: x;y;z2Z and x+y+z 0 (mod 2)g. Since gcd(a;b;c) = 1 and a + b + c 0 (mod 2), it must be the case that exactly two of a;b;c are odd. Note that if < v1;v2;v3 >2 V and is any permutation of the set fv1;v2;v3g, then < (v1); (v2); (v3) >2V. Note also that for any even integersm;n, andp, , < nb;0;0 >, < pc;0;0 >2 V. Since gcd(a;b;c) = 1, there exist integers r;s;t such that ra + sb + tc = 1. But this gives us < 2ra;0;0 > + < 2sb;0;0 > + < 2tc;0;0 > = 9 < 2;0;0 >. Thus < 2;0;0 >, < 0; 2;0 >, < 0;0; 2 >2 V. So given any vector < x;y;z > satisfying x;y;z 2Z and x + y + z 0 (mod 2), we can select < 0;0;0 > or an appropriate vector from those used to generate V and add to it some combination of < 2;0;0 >,< 0; 2;0 >,< 0;0; 2 > to construct . Lemma 2.4 A square-free positive integer n can be represented as n = a2 +ab+b2 for some a;b2Z if and only if n contains no prime factor congruent to 2 (mod 3). Ionascu [12] attributes this result to Euler. However, the author?s own e orts to track down its genesis were ultimately unsuccessful. In any case, this lemma appears to be a fairly well-known fact and can be gleaned from the material presented in most beginning number theory textbooks. See Chapter 4 of [4] for a thorough treatment on representations of integers using binary quadratic forms. Lemma 2.5 Let n be a square-free positive integer which contains no prime factor congruent to 2 (mod 3). Then there exists a;b;c2Z such that a2 +b2 +c2 = 2n and a+b+c = 0. Proof Given some n as described above, by Lemma 2.4 there exists a;b 2 Z such that a2 +ab+b2 = n. )2a2 + 2ab+ 2b2 = 2n )a2 +b2 + ( a b)2 = 2n. Now if we let c = a b we have that a2 +b2 +c2 = 2n and a+b+c = 0. 2.2 Results Throughout this section, we will designate by S the set of all odd, positive, square-free integers whose prime factorization consists solely of factors congruent to 1 (mod 3). Theorem 2.3 For every s2S, (Z3;p2s) = 4. 10 Proof Let s2 S. As (Q3;p2s) 4 [13], clearly (Z3;p2s) 4 as well. By Lemma 2.5 there exists a;b;c 2 Z such that a2 + b2 + c2 = 2s and a + b + c = 0. Thus the vectors < a;b;c >, < b;c;a >, and < c;a;b > each have length p2s and together sum to the zero vector. We can use these vectors to create the equilateral triangles in Figure 2.2, each with side length p2s and vertices in Z3. ?2s ?2s ?2s ?2s ?2s (a,b,c) (0,0,0) (a+b,b+c,a+c)=(-c,-a,-b) (2a+b,2b+c,a+2c) Figure 2.2: Pair of triangles in G(Z3;p2s) We will now assume there exists some proper 3-coloring of G(Z3;p2s) and obtain a contradiction. The above diagram shows that in any proper 3-coloring of G(Z3;p2s), the vertices (0;0;0) and (2a + b;2b + c;a + 2c) must receive the same color. Furthermore, any arrow in Z3 representing the vector < 2a + b;2b + c;a + 2c > must have initial and terminal point colored the same color. By permuting the entries of (a;b;c) and (a + b;b + c;a + c) using the same permutation or by replacing corresponding entries of (a;b;c) and (a+b;b+c;a+c) with the negatives of those entries, it can be seen that each of the vectors < (2a+b); (2b+c); (a+2c) >, < (2a+b); (a+2c); (2b+c) >, < (2b+c); (2a+ b); (a + 2c) >, < (2b + c); (a + 2c); (2a + b) >, < (a + 2c); (2a + b); (2b + c) >, < (a + 2c); (2b + c); (2a + b) > must also have initial and terminal point colored the same color. Let V be the group of Z3 vectors generated under vector addition by these vectors. In any proper 3-coloring of G(Z3;p2s), any vector in V must have initial and terminal point colored the same color. Note that (2a+b)2 + (2b+c)2 + (a+ 2c)2 = 6s and since 6s 2 (mod 4), it must be the case that exactly two of (2a + b);(2b + c);(a + 2c) are odd. Also, since 6s is square-free, gcd(2a + b;2b + c;a + 2c) = 1. Then by Lemma 2.3, V =f: x;y;z2Z and x + y + z 0 (mod 2)g. This means that 2V 11 and consequently that (0;0;0) and (a;b;c) must be colored the same color which is our desired contradiction. Hence (Z3;p2s) = 4. It would be nice to complete the proof of our main result by focusing on the chro- matic number of G(Z3;p6s) but that simply will not work, as evidenced by the following intermediate result. Theorem 2.4 For every s2S, (Z3;p6s) = 3. Proof Let s2 S. By Lemma 2.5, there exist a;b;c2Z such that a2 + b2 + c2 = 6s and a+b+c = 0. Just as in the proof of Theorem 2.3, we can use the vectors, , and < c;a;b > to create a 3-cycle in G(Z3;p6s), thus ensuring that (Z3;p6s) 3. Let X;Y 2Z3 where X = (x1;x2;x3) and Y = (y1;y2;y3). Let i = xi yi for i2f1;2;3g and suppose that X and Y are adjacent in G(Z3;p6s). Then ( 1)2 + ( 2)2 + ( 3)2 = 6s. This means that ( 1)2 + ( 2)2 + ( 3)2 0 (mod 3) but ( 1)2 + ( 2)2 + ( 3)2 6 0 (mod 9), which in turn implies that i 6 0 (mod 3) for i2f1;2;3g. (Here we are using the very basic fact that given any integer n such that n6 0 (mod 3), n2 1 (mod 3).) So to properly 3-color G(Z3;p6s), we need only use ? : Z3 !f0;1;2g where for every X = (x1;x2;x3), ?(X) = x1 (mod 3). Theorem 2.5 For every s2S, (Z3;3p6s) = 4. Proof Let s2 S. Again, by the results of [13] we clearly have that (Z3;3p6s) 4. By Lemma 2.4 and 2.5, there exist a;b;c2Z such that a2 + ab + b2 = 3s, a2 + b2 + c2 = 6s, and a+b+c = 0. From this we get two facts. First notice that (3a)2 + (3b)2 + (3c)2 = 54s implying that the vertices (0;0;0) and (3a;3b;3c) are adjacent in G(Z3;3p6s). Secondly, the following points de ne an equilateral triangle with side length 3p6s and vertices in Z3 as given in Figure 2.3. Note: This triangle is obtained by a slight modi cation to the equilateral triangle pa- rameterizations given in [12]. 12 3?6s 3?6s 3?6s (-4a-3b,-a+3b,a) (0,0,0) (-3a+b,3a+4b,-b) Figure 2.3: Alternate triangle parameterization in G(Z3;3p6s) We can extend this gure into three equilateral triangles each with side length 3p6s and vertices in Z3 as in Figure 2.4. (-a-4b,-4a-b,a+b) (-4a-3b,-a+3b,a) (-3a+b,3a+4b,-b) (a+4b,4a+b,-a-b) (0,0,0) Figure 2.4: Three triangles in G(Z3;3p6s) Let V1 be the vector with initial point (a + 4b;4a + b; a b) and terminal point ( 4a 3b; a + 3b;a). Let V2 be the vector with initial point ( 3a + b;3a + 4b; b) and terminal point ( a 4b; 4a b;a + b). Using the same strategy as that in the proof of Theorem 2.3, we will again suppose that (Z3;3p6s) = 3 and obtain a contradiction. In any proper 3-coloring of G(Z3;3p6s) the initial and terminal point of V1 must be colored the same color and the initial and terminal point of V2 must be colored the same color. Writing V1 and V2 in component form we have that V1 =< 5a 7b; 5a+ 2b;2a+b> V2 =< 2a 5b; 7a 5b;a+ 2b> 13 a b Vector whose entries are each not congruent to 0 (mod 9) 1 (mod 9) 1 (mod 9) V2 1 (mod 9) 4 (mod 9) V1 1 (mod 9) 7 (mod 9) V2 4 (mod 9) 1 (mod 9) V2 4 (mod 9) 4 (mod 9) V1 4 (mod 9) 7 (mod 9) V1 7 (mod 9) 1 (mod 9) V1 7 (mod 9) 4 (mod 9) V2 7 (mod 9) 7 (mod 9) V1 2 (mod 9) 2 (mod 9) V1 2 (mod 9) 5 (mod 9) V2 2 (mod 9) 8 (mod 9) V1 5 (mod 9) 2 (mod 9) V1 5 (mod 9) 5 (mod 9) V1 5 (mod 9) 8 (mod 9) V2 8 (mod 9) 2 (mod 9) V2 8 (mod 9) 5 (mod 9) V1 8 (mod 9) 8 (mod 9) V1 Table 2.1: List of congruences modulo 9 We know that a2 + ab + b2 = 3s. This implies that either a and b are both congruent to 1 (mod 3) or a and b are both congruent to 2 (mod 3). Therefore, since a b (mod 3), the individual entries of V1 and of V2 are each congruent to 0 (mod 3). We now desire to show that at least one of V1 and V2 has all three entries not congruent to 0 (mod 9). This can be done through simple inspection. Table 2.1 lists all possible congruences modulo 9 for a and b along with a vector, either V1 or V2, whose individual entries are each not congruent to 0 (mod 9). With this information in mind, and also considering that V1 and V2 both have length 9p2s, it must be the case that at least one of V1;V2 can be written as < 3x;3y;3z > for some x;y;z2Z where x + y + z 0 (mod 2). Note also that gcd(x;y;z) = 1, as s is odd and square-free. Again using the same ideas as in the proof of Theorem 2.3, we have that in any proper 3-coloring of G(Z3;3p6s) each of the following vectors must have initial and terminal 14 point colored the same color: < 3x; 3y; 3z >, < 3x; 3z; 3y>, < 3y; 3x; 3z >, < 3y; 3z; 3x>, < 3z; 3x; 3y>, < 3z; 3y; 3x>. Let V be the group of vectors generated by those listed above under vector addition. By applying Lemma 2.3, we have that V =f< 3m;3n;3p>: m;n;p2Z and m+n+p 0 (mod 2)g. Any vector in V must have initial and terminal point colored the same color. But < 3a;3b;3c>2V and (0;0;0) is adjacent to (3a;3b;3c) in G(Z3;3p6s). Thus (Z3;3p6s) = 4. Theorem 2.3 and Theorem 2.5, along with the previously mentioned results of [13], imply the main result of this chapter. 2.3 Main Result To establish the main result of this chapter, we need only do a little bookkeeping with the results of the previous sections. Theorem 2.6 Let p be any positive, square-free integer which contains no prime factor congruent to 2 (mod 3). Then (Q3;p2p) = 4. Proof If p is not divisible by 3, we have 4 (Q3;p2p) (Theorem 2.2) (Z3;p2p) = 4: (Theorem 2.3) If p is divisible by 3, we have 15 4 (Q3;p2p) (Theorem 2.2) = (Q3;3p2p) (Lemma 2.1) (Z3;3p2p) = 4: (Theorem 2.3) 16 Chapter 3 Two-distance Graphs in Q2 3.1 Introduction As mentioned in Chapter 1, the best source of information on all things pertaining to coloring the rationals is Johnson?s compendium on the subject [14]. It is in fact a question posed in [14] that served as the impetus for the work done in this chapter. Johnson asks if there exists a set D (0;1), jDj= 2, such that (Q2;D) = 3. We naturally refer to such D as a two-distance set. Before we delve into an answer, a little historical perspective is needed. If the set D is restricted to containing a single distance, then pretty much everything is known about coloring Q2. Woodall became an unexpected pioneer in the eld of coloring Euclidean distance graphs on rational points with his 1973 result [27] that (Q2;1) = 2. This result was extended by Abrams and Johnson in 2001 [1], where they show that for any d realized as a distance in Q2, (Q2;d) = 2. Furthermore, Abrams and Johnson use this fact to conclude that for any two-distance set D, (Q2;D) 4. Although some results stand out (see [17] and [18]), work done calculating the exact value (Q2;D) for various two-distance sets D has been somewhat sparse. In this chapter, however, we will answer Johnson?s question in the a rmative and make a beginning attempt at characterizing all two-distance sets D such that (Q2;D) = 3. 3.2 Preliminaries Before the statement of our main result, it will be helpful to rehash a few past results pertaining to (Q2;D). First of all, it is important to know which distances are actually realized between points of Q2. The answer comes from a well-known theorem of Euler. 17 Theorem 3.1 A positive integer n can be written as n = a2 + b2 for a;b2Z if and only if in the prime factorization of n, factors congruent to 3 (mod 4) each appear to an even degree. We have the following immediate corollary. Corollary 3.1 A distance d is realized between points of Q2 if and only if d = qp q for rela- tively prime p;q2Z+ such that in the prime factorization of p and in the prime factorization of q, factors congruent to 3 (mod 4) each appear to an even degree. Proof Suppose distance d is realized between points of Q2 and let d = qp q for relatively prime p;q 2 Z+. Then qd is realized as a distance between points of Q2, which in turn implies the existence of x1;x2 2Q such that (x1)2 + (x2)2 = pq. Write x1 = ac and x2 = bc for a;b;c2Z. Then a2 + b2 = pqc2. Applying Theorem 3.1 and using the fact that p;q are relatively prime, we have that any prime factor congruent to 3 (mod 4) must divide either p or q an even number of times. Conversely, suppose that p;q are relatively prime positive integers such that in the prime factorization of each, factors congruent to 3 (mod 4) each appear an even number of times. Then pq = a2 + b2 for some a;b2Z) pq = (aq)2 + (bq)2 )d = qp q is a distance realized in Q2. It is also useful to recall Theorem 2.1 from the previous chapter. For any q2Q+ and set of distances D, the graphs G(Q2;D) and G(Q2;qD) are isomorphic, and thus (Q2;D) = (Q2;qD). So when attempting to determine (Q2;D) for arbitrary two-distance sets D, we really need only consider sets of the form D =fpz1;pz2g where z1;z2 are both positive integers and gcd(z1;z2) is square-free. Lastly, we have the following theorem from Jungreis, Reid, and Witte [18]. Theorem 3.2 Let D R+. No 2-coloring of Q2 forbids the distances D if and only if there are d1;d2 2D such that 18 (a) each of d1;d2 occurs as a distance between rational points in the plane and (b) there exist p;q2Z+ such that d1d2 = qp q and p+q is odd. Rephrasing this in terms more appropriate to the matter at hand, we obtain the following corollary. Corollary 3.2 Let D = fpz1;pz2g for z1;z2 2 Z+ where gcd(z1;z2) is square-free and pz 1; pz 2 are both realized as distances in Q2. Suppose either (a) one of z1;z2 is odd and the other even or (b) one of z1;z2 is congruent to 2 (mod 4) and the other congruent to 0 (mod 4). Then (Q2;D) 3. 3.3 Main Result Theorem 3.3 Let D = fpp1;pp2g where p1;p2 2Z+ and gcd(p1;p2) is square-free. Sup- pose that each of the following is true. (a) In the prime factorization of p1 and in the prime factorization of p2, factors congruent to 3 (mod 4) each appear to an even degree. (b) Either one of p1;p2 is odd and the other even or one of p1;p2 is congruent to 2 (mod 4) and the other congruent to 0 (mod 4). (c) p1 p2 (mod 3). Then (Q2;D) = 3. Proof By Corollary 3.1 and Corollary 3.2, hypotheses (a) and (b) imply that (Q2;D) 3. In order to show the existence of a proper 3-coloring of G(Q2;D), we will invoke the help of the famed de Bruijn-Erd}os Theorem [3]. 19 For any in nite graph G with nite chromatic number, there exists a nite subgraph H of G such that (G) = (H). The use of this theorem in coloring Euclidean distance graphs is certainly not a new idea, but it is of particular importance to the argument that follows, so perhaps an explanation of its use here may prove.......useful. By the previously mentioned results of [1], we have that (Q2;D) is nite. So let H be a nite subgraph of G(Q2;D) such that (H) = (Q2;D). Let P1;:::;Pm be the vertices of H where Pi = (aici; bidi) for ai;bi;ci;di2Z and i2f1;:::;mg. Let n = c1 cmd1 dm be the product of all the denominators of the individual entries of P1;:::;Pm. We now create a new distance graph H with vertices nP1;nP2;:::;nPm where vertices are adjacent if and only if they are distance npp1 or npp2 apart. The graphs H and H are isomorphic and thus have the same chromatic number. Note however that each point nP1;nP2;:::;nPm is a point of Z2. So in order to show the existence of a proper 3-coloring of G(Q2;D), it su ces to show the existence of a proper 3-coloring of G(Z2;fnpp1;npp2g) for each n2Z+. We will divide the task into three cases and use an induction argument similar to that presented by Burkert in [5]. Note that we do not have to worry about the case where p1 and p2 are both congruent to 0 (mod 3) as hypothesis (a) precludes that possibility. Case 1 Suppose p1 p2 1 (mod 3) and 3 does not divide n. Let X;Y 2Z2 where X = (x1;x2) and Y = (y1;y2). Let i = xi yi for i2f1;2g and suppose that X and Y are adjacent in G(Z2;fnpp1;npp2g). Then it must be the case that ( 1)2 + ( 2)2 = p1n2 or ( 1)2 + ( 2)2 = p2n2. We now use the elementary number theory fact that for any z 2 Z such that z 6 0 (mod 3), z2 1 (mod 3). Since 3 does not divide n and p1 p2 1 (mod 3), both p1n2 and p2n2 are congruent to 1 (mod 3). This implies that exactly one of 1 and 2 is congruent to 20 0 (mod 3). So to forbid distances npp1 and npp2 we need only color Z2 with the function : Z2 !f0;1;2g where for all X2Z2 of the form X = (x1;x2), (X) = x1 +x2 (mod 3). Case 2 Suppose p1 p2 2 (mod 3) and 3 does not divide n. Let X;Y 2Z2 be as previously described and suppose that X and Y are adjacent in G(Z2;fnpp1;npp2g). Again we have that ( 1)2 + ( 2)2 = p1n2 or ( 1)2 + ( 2)2 = p2n2. Since 3 does not divide n and p1 p2 2 (mod 3), it must be that ( 1)2 + ( 2)2 2 (mod 3). This implies that neither 1 nor 2 are congruent to 0 (mod 3). So here we need only color Z2 with the function : Z2 !f0;1;2g where for all X 2Z2 of the form X = (x1;x2), (X) = x1 (mod 3). Case 3 Suppose 3 divides n. Our plan here will be to set up an induction argument on the number of times 3 divides n. The base step of the induction was already taken care of in Cases 1 and 2. Suppose n = 3kc for k 1 and c2Z+ where 3 does not divide c. Furthermore, suppose that for each m2Z such that 0 m k 1, we can 3-color Z2 to simultaneously forbid distances 3mcpp1 and 3mcpp2. For every X2Z2, again using the form X = (x1;x2), we will write X as X = 3(q1;q2) + (r1;r2) where (q1;q2) 2Z2 and r1;r2 2f0;1;2g. Then we color X with the color that (q1;q2) would receive when coloring Z2 to forbid distances n pp 1 3 and npp2 3 . Why does this coloring do the trick? SupposeX andY are adjacent inG(Z2;fnpp1;npp2g). Again, we have that ( 1)2 + ( 2)2 = p1n2 or ( 1)2 + ( 2)2 = p2n2. 21 Since 3 divides n, both 1 and 2 are congruent to 0 (mod 3). Writing X = 3(q1;q2) + (r1;r2) and Y = 3(s1;s2) + (t1;t2) as described above, we have that (r1;r2) = (t1;t2). Let d denote the distance between X and Y. Then d = p (x1 y1)2 + (x2 y2)2 = p (3q1 +r1 3s1 t1)2 + (3q2 +r2 3s2 t2)2 = p (3q1 3s1)2 + (3q2 3s2)2 = 3 p (q1 s1)2 + (q2 s2)2 This implies that the distance between (q1;q2) and (s1;s2) is either n pp 1 3 or npp2 3 . By our induction hypothesis there exists a 3-coloring of Z2 to forbid distances n pp 1 3 and npp2 3 . Let : Z2 !f0;1;2g be such a coloring. We color the vertices of G(Z2;fnpp1;npp2g) with a function : Z2 !f0;1;2g such that (X) = (q1;q2) and (Y) = (s1;s2). Since (q1;q2)6= (s1;s2), X and Y must receive di erent colors. Thus (Q2;fpp1;pp2g) = 3. 3.4 Further Work Theorem 3.3, along with pretty much everything else in this chapter, appears in [23]. At the end of that article, the following two questions were raised. Question 1: Does there exist a two-distance set D such that (Q2;D) = 3 and qD does not t the hypotheses of Theorem 3.3 for any q2Q+? Question 2: Does there exist a two-distance set D = fpz1;pz2g for some z1;z2 2Z+ such that (Z2;D)6= (Q2;D)? 22 An answer to either of these questions remains elusive. However, it is worth noting that if the answer to Question 1 is no, then the answer to Question 2 is yes. To display this connection between the two, we will consider the chromatic numbers of the graphs G(Z2;f1;p26g) and G(Q2;f1;p26g). Theorem 3.4 (Z2;f1;p26g) = 3. Proof The points (0;0), (1;0), (2;0), (3;0), (4;0), (5;0), (5;1) are the vertices of a 7-cycle in G(Z2;f1;p26g). We now again use the fact that any graph containing an odd cycle is not bipartite, and therefore cannot be properly 2-colored. So certainly (Z2;f1;p26g) 3. Now observe that for any points Z1;Z2 2Z2, Z1 and Z2 are adjacent in G(Z2;f1;p26g) if and only if they constitute the initial and terminal points of one of the following vectors: < 1;0 >, < 0; 1 >, < 1; 5 >, < 5; 1 >. To properly 3-color G(Z2;f1;p26g) we execute a tiling of Z2 with the tile given in Figure 3.1, where R denotes the color red, G the color green, and B the color blue. G G G G G G G G G G B B B B B R R R R R R R R R R Figure 3.1: Tile leading to a proper 3-coloring of G(Z2;f1;p26g) In such a coloring, it is easily seen that any arrow representing the vector < 1;0 > or the vector < 0; 1 > will have initial and terminal points colored di erent colors. Any arrow representing the vector < 0; 5 > or the vector < 5;0 > will have initial point and terminal point colored the same color. Thus the distances 1 and p26 are forbidden by the coloring, and we have that (Z2;f1;p26g) = 3. 23 Suppose the answer to Question 1 is in fact no. Since 16 26 (mod 3), we would have that (Q2;f1;p26g) = 4. We have just shown that (Z2;f1;p26g) = 3 so Question 2 must be answered in the a rmative. 24 Chapter 4 The Second Babai Number and Second Clique Number of Q3 4.1 Introduction In this chapter, we set aside the study of chromatic numbers of Euclidean distance graphs in the traditional sense, and instead focus our discussion on two closely related values { the nth Babai number and the nth clique number of a metric space (X; ). Introduced by Abrams and Johnson in 2001 [1], the nth Babai number Bn(X) is de ned as Bn(X) = supf (X;D) where D (0;1) and jDj= ng: We now adopt the convention of using !(X;D) to denote the clique number of G(X;D). In other words, !(X;D) designates the largest integer m such that the complete graph Km is a subgraph of G(X;D). The nth clique number Cn(X) is then de ned as Cn(X) = supf!(X;D) where D (0;1) and jDj= ng: It is worth noting that when X Rm for some m2Z+ and is the usual Euclidean metric on Rm, in the de nitions of both Bn(X) and Cn(X) the \sup" is a \max"; Bn(X) is nite, and therefore so is Cn(X) [1]. In 2009 [15], Johnson and Tiemeyer investigated the second Babai number and second clique number of Q3, concluding that B2(Q3) 5 and C2(Q3) 5. Here we will better their e orts, showing that C2(Q3) = 6 which of course implies that B2(Q3) 6. We do this by recalling a 1960s result [8] of Einhorn and Schoenberg on certain con gurations of points in R3 and then showing which of those con gurations can be embedded in Q3. Recent results 25 [12] of Ionascu are then used to show exactly which distances d1;d2 result in G(Q3;fd1;d2g) containing a copy of K6 as a subgraph. We conclude with a few observations which could possibly be used in future work to further increase the lower bound for B2(Q3). 4.2 Main Results The following theorem is a summary of a few of the results found in Einhorn and Schoenberg?s 1966 work [8]. Theorem 4.1 Up to rotation, translation, and scaling, there are exactly six unique sets of six points in R3 with the property that only two pairwise distances are realized in the set. Furthermore, there is no set of seven points in R3 with the same property. A visual representation of the six con gurations is given in Table 4.1. I II III IV V VI Table 4.1: The six possible two-distance con gurations in R3 Einhorn and Schoenberg describe the six con gurations in detail, but for our purposes the following abbreviated descriptions will su ce. Con guration I is a regular octahedron. Con guration II is a triangular prism with three square faces. Con gurations III, IV, V, and VI each consist of six-point subsets of the twelve points that form the vertices of a regular icosahedron. Theorem 4.2 Con guration I can be embedded in Q3. 26 Proof We need only observe that the points (0;0;0);(1;1;0);(1;0;1), (1;0; 1);(2;0;0), and (1; 1;0) constitute the vertices of a regular octahedron. To show the impossibility of embedding Con gurations III, IV, V, and VI in Q3, we will make use of a classical geometric argument illustrated by the following lemma. Lemma 4.1 In any regular pentagon, the diagonal length divided by the side length is the golden ratio 1+ p5 2 . Proof By an easy calculation, each interior angle of a regular pentagon measures 108 . Suppose a given regular pentagon has side length s. Label four consecutive vertices A, B, C, and D and insert two line segments { one with endpoints A and C and another with endpoints B and D. Label the point of intersection of these two line segments E and ll in all relevant angle measures as in Figure 4.1. 36? 36? 36? 36?72 ? 72? 72? 72? 108? A B C D E s s Figure 4.1: Regular pentagon with diagonals Suppose line segment BE has length d. Then line segment EC has length d as well. Note also that line segment ED has length s, as the points E, D, and C form the vertices of an isosceles triangle. As seen in Figure 4.2, triangles BEC and DCB are similar. This allows us to set up the following proportion. s d = d+s s 27 36?36? 108? B Cs d d E 36?36? 108? D Bd+s s s C Figure 4.2: Similar triangles )d2 +ds s2 = 0 Solving for d, we nd that d = s+ ps2 (4)( s2) 2 )d = s+s p5 2 )d+s = s+s p5 2 )d+ss = 1 + p5 2 Thus the ratio of the diagonal length divided by the side length is 1 + p5 2 . Theorem 4.3 Con gurations III, IV, V, and VI cannot be embedded in Q3. Proof As described by Einhorn and Schoenberg (and which may be apparent from Table 4.1 above), Con gurations III, IV, V, and VI each have at least three of their six points constituting three of the ve vertices of a regular pentagon. Note that any distance realized between points of Q3 is of the form pq for some q2Q+. Thus the ratio of two distances both realized between points of Q3 must be of the form pq for some q 2 Q+. If any of 28 Con gurations III, IV, V, or VI could be embedded in Q3, we would by Lemma 4.1 have two distances each realized between points of Q3 whose ratio is 1+ p5 2 . To demonstrate the impossibility of embedding Con guration II in Q3, we will employ the following lemmata. Lemma 4.2 is a restatement of Chow?s 1993 result [6] and was seen in Chapter 2. Lemma 4.3 is a result of Ionascu?s [11] recent work counting equilateral triangles in Z3. Although at rst glance the subject of enumerating triangles may seem to have little in common with coloring distance graphs, Ionascu?s lemma has in fact proven very useful to the general study of Euclidean distance graphs with vertex set Q3. Lemma 4.2 Let z2Z+. Then (Z3;pz) 3 if and only if in the prime factorization of z, 2 appears to an odd degree. Lemma 4.3 Let T be an equilateral triangle with vertices in Z3. Then there exist a;b;c;d2 Z such that T is contained in a plane with normal vector and a2 +b2 +c2 = 3d2. Theorem 4.4 Con guration II cannot be embedded in Q3. Proof Suppose Con guration II can be embedded in Q3. Then a similar triangular prism can be embedded in Z3. Let T1 be the \top" equilateral triangle of such a triangular prism and let T2 be the \bottom" equilateral triangle. Let pz be the side length of each of these triangles. Then there exists vertex V1 2 T1 and vertex V2 2 T2 such that V1 and V2 are distance pz apart. If we let denote the vector with initial point V1 and terminal point V2, we have that a2 +b2 +c2 = z and a;b;c2Z. But since vector is normal to the plane containing T1, it must be that z = 3d2 for some d2Z. Thus 2 must appear to an even degree in the prime factorization of z. This contradicts Lemma 4.2, however, as the existence of triangles T1 and T2 clearly imply that (Q3;pz) 3. Of course, Theorem 4.1 and Theorem 4.2 imply the following. Theorem 4.5 C2(Q3) = 6 and B2(Q3) 6. 29 4.3 Further Work Abrams and Johnson note in [1] that for any X Rn, B1(X) m implies that B2(X) m2. In Chapter 2, Theorem 2.2 gives that for any d > 0, (Q3;d) 4. Combining these facts with the work done in the previous section, we have that 6 B2(Q3) 16. Clearly this result leaves much room for improvement. If one wished to sharpen these bounds, it seems the greatest chance of success would lie in attempting to increase the lower bound { in other words, for some d1;d2 > 0, nd a 7-chromatic subgraph of G(Q3;fd1;d2g). Of course, this may ultimately be a futile task. It may very well be the case that B2(Q3) = 6 and any attempt at nding such a subgraph is doomed from the start. But still, it cannot hurt to try. Thinking along these lines, it is natural to ask at this point what values of d1 and d2 result in the graph G(Q3;fd1;d2g) containing a copy of the complete graph K6. Furthermore, exactly how do these copies of K6 appear as subgraphs of G(Q3;fd1;d2g)? We answer these questions with the following two theorems, whose methods of proof mimic the arguments presented in [11]. Theorem 4.6 The graph G(Q3;fd1;d2g) contains K6 as a subgraph if and only iffd1;d2g= fqp2;2qg for some q2Q+. Proof The six points given in the proof of Theorem 4.2 constitute a copy ofK6 inG(Q3;fp2;2g). Recalling Lemma 2.1, we have that for any q2Q+ and any D (0;1), the graphs G(Q3;D) and G(Q3;qD) are isomorphic. Thus for any q 2 Q+, G(Q3;fqp2;2qg) contains K6 as a subgraph. Conversely, suppose that G(Q3;fd1;d2g) contains K6 as a subgraph. From the previous section, we know that those six points which form the vertices of this copy of K6 must also form the vertices of a regular octahedron, say of edge length s. Note that this gives fd1;d2g=fs;sp2g. We now label the vertices of such an octahedron as given in Figure 4.3. 30 V1 V2 V3 V4 V5 V6 Figure 4.3: Regular octahedron with labeled vertices V1;V2;V3 form the vertices of an equilateral triangle of side length s which we will call T1. V4;V5;V6 also form the vertices of an equilateral triangle of side length s which we will call T2. Now let V7 and V8 be the circumcenters of T1 and T2 respectively. Let u be the vector with initial point V7 and terminal point V8. Then u = for some a;b;c2Q. After a little computation, we nd that u has length q 2 3s and is normal to the plane containing T1. By slightly varying Lemma 4.3, we have that 23s2 = a2 + b2 + c2 = 3d2 )2s2 = 9d2 for some d2Q. This implies that s must be of the form qp2 for some q2Q+. Theorem 4.7 Any three points in Q3 constituting the vertices of an equilateral triangle of side length p2 also make up three of the six vertices of some copy of K6 in the graph G(Q3;fp2;2g). Proof Let v1;v2;v3 2Q3 constitute the vertices of an equilateral triangle of side lengthp2. Call this triangle T. Let c be the circumcenter of triangle T and note that c2Q3 as well. Form a new equilateral triangle T0 by rotating T 180 about point c such that T and T0 lie in the same plane. Label the vertices of T0 v01;v02;v03 as shown in Figure 4.4. If we let u1 denote the vector with initial point v1 and terminal point c, and let u2 denote the vector with initial point v1 and terminal point v01, we have that 2u1 = u2. Thus v01 2Q3. Similarly, v02;v03 2Q3 as well. Let P be the plane containing T (and also T0). We now form a new equilateral triangle T00 by translating T0 by a vector of length 2p3 perpendicular to plane P. The vertices of T00 together with the vertices of T constitute a copy of K6 in the graph G(R3;fp2;2g). It remains to be seen that the vertices of T00 lie in Q3. To accomplish this, we need only 31 v1 v2 v3 v prime1v prime3 v prime2 c Figure 4.4: Pair of triangles with vertices in Q3 show that a length 2p3 vector with initial point in Q3 and perpendicular to P has terminal point in Q3 as well. By Lemma 4.3, P has a normal vector of the form < a;b;c > where a2 + b2 + c2 = 3d2 and a;b;c;d2Z. Multiply this vector by the scalar 23d. The resulting vector < 2a3d; 2b3d; 2c3d > has length q 4a2+4b2+4c2 9d2 = 2 3 q 3d2 d2 = 2p 3. So it appears that the \easiest" way of increasing the lower bound of B2(Q3) lies in constructing an argument that will increase the lower bound of (Q3;fp2;2g) from 6 up to 7. This line of thought could be awed for at least two di erent reasons. As mentioned earlier, it could be the case that B2(Q3) = 6 and e orts to nd a 7-chromatic subgraph of G(Q3;fd1;d2g) for any distances d1 and d2 are simply a waste of time. We also have no guarantee that G(Q3;fp2;2g) has the largest chromatic number among all two-distance graphs with vertex set Q3 even though G(Q3;fp2;2g) has the largest clique number among such graphs. It could be the case that (Q3;fp2;2g) = 6 but for some fd1;d2g6=fp2;2g, (Q3;fd1;d2g) > 6. However, even if our search is in vain for either of these reasons, the eventual production of a proper 6-coloring of G(Q3;fp2;2g) would be of some interest in its own right. Applying Lemma 2.1 and Theorems 2.1 and 2.6 from Chapter 2, we have that (Q3;2) = 2 and that (Q3;p2) = 4. Let 1 : Q3 !f1;2g be a proper 2-coloring of G(Q3;2) and 2 : Q3 !f1;2;3;4g be a proper 4-coloring of G(Q3;p2). We can properly 8-color the graph G(Q3;fp2;2g) with the function 3 : Q3 !f11;12;13;14;21;22;23;24g where for 32 all q 2 Q3, 3(q) = 1(q) 2(q). So as it stands, 6 (Q3;fp2;2g) 8. For the rest of this chapter, we will assume that (Q3;fp2;2g) = 6 and make a few observations on the conditions a proper 6-coloring of G(Q3;fp2;2g) must satisfy. Hopefully, in future work we may use these observations to obtain a contradiction, thus showing that B2(Q3) > 6. Theorem 4.8 Suppose G(Q3;fp2;2g) has been properly 6-colored and T is an equilateral triangle with side length p2 and vertices in Q3. Suppose a new triangle T0 is formed by translating T by a length 4p3 vector normal to the plane containing T. Then the vertices of T and the vertices of T0 must be colored with the same three colors. Proof Let triangles T and T0 be as described above. By Theorem 4.7, there exists a triangle T00 such that the vertices of T together with the vertices of T00 constitute the vertices of a copy of K6 in G(Q3;fp2;2g). The vertices of T0 along with the vertices of T00 also form the vertices of a copy of K6 in G(Q3;fp2;2g). Thus in any proper 6-coloring of G(Q3;fp2;2g), the vertices of T and the vertices of T0 must be colored with the same three colors. Theorem 4.9 Let P be a plane containing an equilateral triangle with vertices in Q3, and let p1;p2 2P\Q3 where jp1 p2j=p6. Then there exist q1;q2 2P\Q3 such that p1;q1;q2 and p2;q1;q2 are each the vertices of an equilateral triangle of side length p2. Proof Without loss of generality, assume that p1 = (0;0;0) and p2 = (x;y;z). Let v be the vector lying in plane P with initial point (x2;y2;z2), having length p2 2 , and orthogonal to vector . As given in Figure 4.5, let (x0;y0;z0) be the terminal point of v. We need only show that (x0;y0;z0)2Q3. By Lemma 4.3, P has a normal vector of the form where a2 +b2 +c2 = 3d2 for some a;b;c;d2Z. If we let < n1;n2;n3 > be the cross-product of vectors < a;b;c > and < x;y;z >, we have that v = s < n1;n2;n3 > for some scalar s. We now need only show that s 2 Q. Since < a;b;c > and < x;y;z > are orthogonal, we have that jj=jjjj. Thus n21 + n22 + n23 = (3d2)(6) = 18d2. Since jvj= p2 2 , we have that s 2(n2 1 +n 2 2 +n 2 3) = 1 2 )s 2 = 1 2(18d2) )s = 1 6d )s2Q. 33 (x,y,z) (0,0,0) (x2,y2,z2) (x0,y0,z0) ?2 ?6 2 ?2 2 Figure 4.5: Triangle in Q3 with labeled sides and vertices Theorem 4.10 Suppose the graph G(Q3;fp2;2g) has been properly 6-colored. Let P be a plane containing an equilateral triangle of side length p2 with vertices in Q3, and let p2P\Q3. Then at least one of the following must be true: (i) Every rational point lying on the circle of radius p6 centered at p and lying in plane P must be colored the same color as p. (ii) For any n2Z+, every point a distance 4np3 from p along a vector normal to plane P must be colored the same color as p. Proof Let C be the circle of radius p6 centered at p and lying in plane P, and suppose that (i) is false. Then there exists q2C\Q3 such that p and q are colored with di erent colors. By Theorem 4.9, there exist points m1;m2 2P\Q3 such that p;m1;m2 and q;m1;m2 each form the vertices of equilateral triangles of side lengthp2. Let T1 be the triangle with vertices p;m1;m2 and let T2 be the triangle with vertices q;m1;m2. Translate each of these triangles by the same length 4p3 vector normal to plane P. By Theorem 4.8, we have that the vertices of this translate of T1 must be colored with the same three colors as the vertices of T1, and the vertices of this translate of T2 must be colored with the same three colors as the vertices of T2. This implies that the translate of p must be colored the same color as p. Repeating this argument, we have that (ii) must be true. 34 Theorem 4.10 gives a fairly strong condition that any proper 6-coloring ofG(Q3;fp2;2g) must satisfy. As mentioned earlier, it is our hope that with a little ingenuity, it can be used in future work to show that B2(Q3) 7. 35 Chapter 5 Un nished Business Concerning Single-distance Graphs in Q3 5.1 Introduction We now again turn our attention to single-distance graphs with vertex set Q3 and address the problem of determining (Q3;d) for an arbitrary d> 0. Considering the results of [6], [13], and [17], along with the work done in Chapter 2, a complete resolution of this question can be reached by answering the following: Given any odd, positive, square-free integer n which contains at least one prime factor congruent to 2 (mod 3), does (Q3;p2n) = 3 or does (Q3;p2n) = 4? For the sake of brevity, throughout this chapter we will designate by K the set of all odd, positive, square-free integers whose prime factorization contains at least one prime fac- tor congruent to 2 (mod 3). Recall the result from Chapter 2, in which it is shown that for any odd, positive, square-free integer n containing no prime factor congruent to 2 (mod 3), (Q3;p2n) = 4. The proof presented was heavily dependent on parameterizations of equilat- eral triangles with vertices in Q3, which were in turn used to generate 4-chromatic subgraphs of G(Q3;p2n). Unfortunately, these methods fall at on their faces when attempting to de- termine (Q3;p2k) for any k 2K, as the graph G(Q3;p2k) is triangle-free. This fact is immediately seen as a corollary to Ionascu?s work in [11]; however we will include an alter- nate proof in the pages ahead. Our proof will not have the bene t of economy of words (it is actually a bit longer than Ionascu?s proof), but in the process we will develop a lemma use- ful in search algorithms presented later in this chapter. Hopefully, these algorithms may be employed to eventually nd 4-chromatic subgraphs of G(Q3;p2k) and put this troublesome question to rest. 36 Before proceeding, we must make note of a few terms and theorems from the realm of number theory. All of this information may be found in Chapters 3, 4, and 6 of [22] or Chapters 3 and 5 of [19], or really any introductory number theory text worth its salt. 5.2 Number Theory Background In the subject of number theory, we will be primarily concerned with the topic of quadratic residues. Given two integers a and b, a is said to be a quadratic residue of b if there exists an integer k such that k2 a (mod b). If no such k exists, we say a is a quadratic non-residue of b. Very frequently the word \quadratic" is dropped in print as it will be clear from context. Volume after volume has been written on the subjects of residues and congruences, but for the purposes of our discussion we really need only concern ourselves with a few basic facts: 1) An integer a is a non-residue of a square-free integer b if and only if there exists a prime factor c of b such that a is a non-residue of c. 2) For any integers a;b;c with c prime, if a is a non-residue of c, and b is a residue of c where b6 0 (mod c), ab is a non-residue of c. Along with these observations, we will use two major theorems. Theorem 5.1 was proved by Adrien Marie Legendre in the late eighteenth century. Theorem 5.2 is the Law of Quadratic Reciprocity and is the most fundamental result of classical number theory. It was rst proved by Gauss in his groundbreaking 1804 manuscript Disquisitiones Arithmeticae. Theorem 5.1 (Legendre?s Theorem) Let a;b;c be non-zero integers, not each positive or each negative, and suppose that abc is square-free. Then the equation ax2 +by2 +cz2 = 0 has a non-trivial rational solution (x;y;z) if and only if each of the following are satis ed: (i) ab is a quadratic residue of c 37 (ii) ac is a quadratic residue of b (iii) bc is a quadratic residue of a. Theorem 5.2 (Law of Quadratic Reciprocity) Let p;q > 2 with p and q both prime. If at least one of p and q is congruent to 1 (mod 4), then p is a quadratic residue of q if and only if q is a quadratic residue of p. If both p and q are congruent to 3 (mod 4), p is a quadratic residue of q if and only if q is a quadratic non-residue of p. The Law of Quadratic Reciprocity is usually presented with the following supplement, of which we will make some use. Theorem 5.3 -1 is a quadratic residue of a prime p> 2 if and only if p 1 (mod 4). 5.3 Non-existence of Triangles in G(Q3;p2k) Lemma 5.1 Let P1;P2 2Q3 where the vector with initial point P1 and terminal point P2 is given by < a;b;c > where c 6= 0. Then for any q 2 Q+, there exists P3 2 Q3 with jP1 P3j = jP2 P3j = pq if and only if the following equation has a non-trivial rational solution (x;y;z): 1 + a 2 c2 x2 + 1 + b 2 a2 +c2 y2 q a 2 +b2 +c2 4 z2 = 0. Proof Without loss of generality, we may assume that P1 = (0;0;0) and P2 = (a;b;c). The set of all points distancepq from both P1 and P2, if such points exist, is given by the circle of radius r = q q a2+b2+c24 , centered at point (a2; b2; c2), and having normal vector . Here, by normal vector we just mean a vector normal to the plane containing the circle. Call this circle C. There exists P3 2Q3 with jP1 P3j = jP2 P3j = pq if and only if there exists a rational point on C. To make computation easier, we will translate each point of C by the vector < a2 ; b2 ; c2 >. This translate of C is a circle centered at the origin, which we 38 will designate C0. Certainly C0 contains a rational point if and only if C contains a rational point. Let (x0;y0;z0)2C0. Then we have that x02 +y02 +z02 = r2 (5.1) and ax0 +by0 +cz0 = 0: (5.2) Rewriting Equation 5.2 as z0 = ax0 by0c and substituting into equation 5.1 we nd that 1 + a 2 c2 x02 + 1 + b 2 c2 y02 + 2abx0y0c2 = r2: (5.3) We now make a linear transformation which will in e ect eliminate the x0y0 term. Let x0 = u+mv where m = aba2+c2 and y0 = v. Then Equation 5.3 becomes 1 + a 2 c2 (u2 + 2muv +m2v2) + 1 + b 2 c2 v2 + 2abc2 uv + 2abc2 mv2 = r2: (5.4) Collecting like terms, we may rewrite Equation 5.4 as 1 + a 2 c2 u2 + " 1 + a 2 c2 ab a2 +c2 2 + 1 + b 2 c2 + 2ab c2 ab a2 +c2 # v2 = r2: (5.5) Now we let w denote the coe cient before the v2 term and begin the arduous process of simplifying. We have w = a2 +c2 c2 a2b2 (a2 +c2)2 + c 2(a2 +c2)2 c2(a2 +c2)2 + b2(a2 +c2)2 c2(a2 +c2)2 2a2b2(a2 +c2) c2(a2 +c2)2 39 )w = a4b2 +a2b2c2 +a4c2 + 2a2c4 +c6 +a4b2 + 2a2b2c2 +b2c4 2a4b2 2a2b2c2 c2(a2 +c2)2 )w = c2(a2b2 +a4 + 2a2c2 +c4 +b2c2) c2(a2 +c2)2 )w = (a 2 +c2)(b2) + (a2 +c2)2 (a2 +c2)2 )w = a 2 +b2 +c2 a2 +c2 = 1 + b2 a2 +c2: So Equation 5.5 can be rewritten as 1 + a 2 c2 u2 + 1 + b 2 a2 +c2 v2 r2 = 0: (5.6) Now let u = xz and v = yz. Equation 5.6 can then be rewritten further as 1 + a 2 c2 x2 + 1 + b 2 a2 +c2 y2 q a 2 +b2 +c2 4 z2 = 0 (5.7) which has a non-trivial rational solution if and only if Equation 5.3 has a rational solution. One may nd the stipulation that c6= 0 to be limiting, but that is not the case. For any a;b;c2Q not all zero and any permutation of the set fa;b;cg, the initial and terminal points of the Q3 vector < a;b;c > have a rational point distance d from each if and only if the initial and terminal points of the vector < (a); (b); (c) > have a rational point distance d from each. So given any points P1;P2 2Q3, we can easily use Theorem 5.1 to decide if the equation in the statement of Lemma 5.1 has a non-trivial rational solution. 40 Lemma 5.2 There exist in nitely many values of , 0 < < 2 , such that a rotation of the plane R2 about the origin and through the angle is an isometry that maps Q2 onto itself. Proof Clearly such a rotation is an isometry. It is well-known that rational points are dense on the unit circle, so we have in nitely many choices for (r;s) 2Q2 such that r2 + s2 = 1. This gives r = cos and s = sin for some angle . Now suppose (a;b)2Q2 is mapped in the described rotation to the point (x;y) as given in Figure 5.1. (x,y) (a,b) ?? d d Figure 5.1: Point (a;b) with its image in a rational rotation of R2 We immediately extract from the above gure the relationships ad = cos , bd = sin , x d = cos( + ), and y d = sin( + ). Applying basic trigonometric identities, we have x d = cos cos sin sin ) x d = a dr b ds)x = ar bs. Similarly, we have y d = sin cos + cos sin ) y d = b dr + a ds)y = br +as. Thus (x;y)2Q 2. Theorem 5.4 Let P1;P2 2Q3, and let jP1 P2j=p2k for some k2K. Then there does not exist P3 2Q3 with jP1 P3j=jP2 P3j=p2k. Proof Without loss of generality, assume that P1 = (0;0;0) and P2 = (aq; bq; cq) where a;b;c;q2Z. In light of Lemma 5.2, we may assume that a;b;c are each non-zero. Suppose there exists P3 2 Q3 where P3 is distance p2k from both P1 and P2. This implies there exists a point P4 2Q3 distance qp2k from each of the points (0;0;0) and (a;b;c). Then by Lemma 5.1 the following equation has a non-trivial rational solution: 41 1 + a 2 c2 x2 + 1 + b 2 a2 +c2 y2 a2 +b2 +c2 a 2 +b2 +c2 4 z2 = 0: (5.8) If we let x = c(a2+b2+c2)q(a2+c2) x0 and z = 2z0, the above equation becomes (a2 +b2 +c2)2 q2(a2 +c2) x02 + a2 +b2 +c2 a2 +c2 y2 3 a2 +b2 +c2 z02 = 0: (5.9) We may now multiply both sides of this equation by (a2 +c2) and divide both sides by (a2 +b2 +c2) to obtain 2kx02 +y2 3(a2 +c2)z02 = 0 (5.10) which must also have a non-trivial rational solution. Let m be a prime factor of k congruent to 2 (mod 3). We have that 2q2k = a2 +b2 +c2. Write a = a1m , b = b1m , c = c1m where a1;b1;c1 2Z are each not divisible by m and ; ; are each non-negative integers. Note that we may apply any permutation to fa;b;cg in Equation 5.10 and the resulting equation must also have a non-trivial rational solution. With this in mind, we may without loss of generality assume that . Rewrite the previous equation as 2q2k = a21m2 + b21m2 + c21m2 and divide both sides by m2 . We are left with 2q2km2 = a21 +b21m2( ) +c21m2( ), and note here that 2q2km2 2Z and is divisible by m. If > , we have that (a21 + c21m2( )) = (b1m )2 2q2km2 implying that the square-free part of (a2 + c2) is a residue of m but is also not divisible by m. If = = , we are left with (a21 + c21) = b21 2q2km2 . Note here that m does not divide (a21 + c21) as that would imply mjb1, and thus the square-free part of (a2 + c2) must again be a residue of m but not divisible by m. Let d be the square-free part of (a2 +c2). For any integers u and v, u2 +v2 0 (mod 3) implies 3ju and 3jv. If 3jd we would have that 3ja and 3jc which in turn implies that d is the square-free part of (a3)2 + (c3)2. Repeating this argument, we would have that 3tja and 42 3tjc for all positive integers t. So as it stands, it must be the case that 3 does not divide d. Now applying Legendre?s Theorem and the basic facts of the previous section, we have that 3d must be a residue of m. The preceding arguments show that d is a residue of m, so we are left with -3 being a residue of m as well. We will consider two cases and apply the Law of Quadratic Reciprocity to obtain a contradiction. If m 1 (mod 4), we have that -1 is a residue of m. Now applying the Law of Quadratic Reciprocity, it must be that 3 and m are each residues of each other. This is a contradiction, however, as m 2 (mod 3) is a non-residue of 3. If m 3 (mod 4), we have that -1 is a non-residue of m. Again the Law of Quadratic Reciprocity gives us that m 2 (mod 3) must be a residue of 3 { the same contradiction. 5.4 An Algorithmic Search for 4-chromatic Subgraphs of G(Q3;p2k) Digressions aside, we now return to the issue at the beginning of this chapter { that of determining (Q3;p2k) for some k2K. This problem may be resolved in one of two ways. We could either exhibit a proper 3-coloring of the graph G(Q3;p2k) or show the existence of a 4-chromatic subgraph of G(Q3;p2k). Theorem 5.4 gives us that G(Q3;p2k) is triangle- free, but this fact in itself has no bearing on (Q3;p2k). In 1955, Jan Mycielski [21] showed the existence of triangle-free graphs of arbitrary chromatic number. His proof consisted of the construction of a sequence of triangle-free graphs (unsurprisingly now referred to as the Mycielskian graphs) with the property that each graph in the sequence has chromatic number one greater than the previous graph. For our purposes, the most notable of these graphs is the third Mycielskian, sometimes called the the Gr otzsch graph. It is the unique smallest triangle-free graph of chromatic number 4 [7], and is given in Figure 5.2. With this information in mind and considering the fact that at present no one has shown the existence of single d > 0 such that (Q3;d) = 3, it seems our greatest chance of success in resolving the aforementioned problem lies in the latter approach. 43 Figure 5.2: The Mycielski-Gr otzsch graph In the upcoming pages we will describe an algorithm that can potentially be used to construct 4-chromatic subgraphs of G(Q3;p2k) for k2K. In doing so we will stray from the standard format of mathematical writing { that of stating relevant lemmata, stating and proving a theorem, expounding upon the result, and then repeating the process. Instead we will illustrate our algorithm as it pertains to a speci c example { the graph G(Q3;p10). Along the way we will occasionally break to sample a needed result from graph theory or number theory. We begin by noting that the points (0;0;0);(3;1;0);(2;1;3);(2;0;0);(1;0;3) form the vertices of a 5-cycle in the graph G(Q3;p10). Let C1;:::;C5 be circles such that C1 is the set of all points distancep10 from both (1;0;3) and (3;1;0), C2 is the set of all points distance p10 from both (0;0;0) and (2;1;3), C 3 is the set of all points distance p10 from both (3;1;0) and (2;0;0), C4 is the set of all points distance p10 from both (2;1;3) and (1;0;3), and C5 is the set of all points distance p10 from both (2;0;0) and (0;0;0). A depiction of these circles and their orientation to the vertices of the previously listed 5-cycle is given in Figure 5.3. Please note at this point that Figure 5.3 is meant only as an aid to help visualize a graph we are attempting to construct. As depicted, it may seem that the points (0;0;0);(3;1;0);(2;1;3), (2;0;0);(1;0;3) form the vertices of a regular pentagon in Q3. That is impossible, however, as evidenced by Lemma 4.1 from the previous chapter. 44 (0,0,0) (1,0,3) (2,0,0) (2,1,3) (3,1,0) C1 C2 C3 C4 C5 Figure 5.3: Circles in R3 along with a 5-cycle in G(Q3;p10) A better description of C1;:::;C5 can be found by listing the center and radius of each circle along with a vector normal to the plane containing each circle. C1 is centered at (2; 12; 32), has radius p26 2 , and normal vector < 2;1; 3 >. C2 is centered at (1; 12; 32), has radius p26 2 , and normal vector < 2;1;3 >. C3 is centered at (52; 12;0), has radius p38 2 , and normal vector < 1;1;0 >. C4 is centered at (32; 12;3), has radius p38 2 , and normal vector < 1;1;0 >. C5 is centered at (1;0;0), has radius 3, and normal vector < 1;0;0 >. We now desire a characterization of the rational points on each of these circles. This can be found by applying a well-known number theory result, a proof of which can be found in [19], [25], or many other texts which place an emphasis on the study of Diophantine equations. Lemma 5.3 Let ax2 + bxy + cy2 + dx + ey + f = 0 be the equation of a conic where a;b;c;d;e;f2Q. If the conic contains one rational point, it contains in nitely many. Nagell goes further in [22], giving a parameterization of the rational solutions to the above equation. Lemma 5.4 Let ax2 + bxy + cy2 + dx + ey + f = 0 be the equation of a conic where a;b;c;d;e;f2Q. Suppose ( ; ) is a rational point on the conic. Additional rational points (x;y) on the conic may be parameterized as 45 x = d a b (2c +e)t+c t 2 a+bt+ct2 , y = a (2a +d)t (b +c +e)t2 a+bt+ct2 where the parameter t runs through all the rational numbers. The only rational point not obtained through this parameterization (should it actually exist on the conic) is the point ( ; b c ec ) and is found by letting t approach 1. Now suppose (x;y;z) is a point on C1. Then the following two equations must be satis ed: (x 2)2 + y 12 2 + z 32 2 = 132 (5.11) and 2(x 2) + y 12 3 z 32 = 0: (5.12) If we rewrite Equation 5.12 as z = 2x+y3 and then substitute into Equation 5.11, we may then simplify to obtain 13x2 + 4xy + 10y2 54x 18y = 0 (5.13) whose rational solutions are characterized by Lemma 5.4. We have that (0;0;0) is a rational point on C1, or in other words x = 0, y = 0 is a solution to Equation 5.13. Applying Lemma 5.4, we nd additional rational points on C1 parameterized as 54 + 18t 1 13 + 4t1 + 10t21; 54t1 + 18t21 13 + 4t1 + 10t21; 36 + 30t1 + 6t21 13 + 4t1 + 10t21 for t1 2Q. We may now repeat this process to nd rational points on circles C2;:::;C5, also in terms of a rational parameter. After some work, we nd that additional rational points on C2 are given by 13 + 42t 2 + 30t22 5 + 12t2 + 10t22 ; 9 + 6t2 8t22 5 + 12t2 + 10t22; 2t2 + 6t22 5 + 12t2 + 10t22 for t2 2Q. 46 Additional rational points on C3 are given by 6 6t 3 + 2t23 2 +t23 ; 6t3 +t23 2 +t23 ; 6 + 2t3 3t23 2 +t23 for t3 2Q. Additional rational points on C4 are given by 2 + 6t 4 + 2t24 2 +t24 ; 2 6t4 2 +t24 ; 2t4 + 6t24 2 +t24 for t4 2Q. And nally, additional rational points on C5 are given by 1; 3 + 3t 2 5 1 +t25 ; 6t5 1 +t25 for t5 2Q. If we can carefully select t1;:::;t5 2 Q yielding rational points P1 2 C1;:::;P5 2 C5 with the property that there exists P6 2Q3 distance p10 from each of P1;:::;P5, we would in e ect have embedded the Mycielski-Gr otzsch graph in G(Q3;p10), allowing us to claim (Q3;p10) = 4 and wipe our hands of the whole mess. That said, nding such t1;:::;t5 seems very di cult { for that matter, they may not even exist in the rst place. Instead we will attempt to embed a similar graph in G(Q3;p10). To see that this graph also has chromatic number 4, it will be best at this point to assume that (Q3;p10) = 3 and proceed by way of contradiction. We rst make note of a lemma. Lemma 5.5 Let C be an odd cycle which has been properly 3-colored { say with colors red, green, and blue. Then there exists vertices v1;v2;v3 of C such that v1 is colored red and is adjacent to vertices colored green and blue, v2 is colored green and is adjacent to vertices colored red and blue, and v3 is colored blue and is adjacent to vertices colored red and green. Proof Suppose C is described as above, and each red vertex is adjacent to either two green vertices or two blue vertices. We can then recolor each red vertex blue or green (whichever is necessary) so that C is properly colored using only two colors. This is a contradiction, however, as any odd cycle has chromatic number 3. Similarly, there must be a green vertex adjacent to red and blue vertices and a blue vertex adjacent to red and green vertices. 47 Supposing that G(Q3;p10) has been properly 3-colored { again say with the colors red, green, and blue, Lemma 5.5 implies that of the circles C1;:::;C5, one has each of its rational points colored red, one has each of its rational points colored green, and one has each of its rational points colored blue. We will describe such circles as being monochromatic. Now let C1 = fC1;C2;C3g, C2 = fC2;C3;C4g, C3 = fC3;C4;C5g, C4 = fC4;C5;C1g, and C5 = fC5;C1;C2g. After a little consideration, it is evident that for some i2f1;2;3;4;5g, Ci consists of three monochromatic circles { one red, one blue, and one green. We begin by considering C1, and attempting to nd rational points q1 2C1, q2 2C2, q3 2C3 such that there exists q4 2Q3 such thatjq1 q4j=jq2 q4j=jq3 q4j=p10. This q4 would imply that C1 cannot consist of three monochromatic circles. If we are successful in our search, we would then repeat the process for C2;:::;C5. Given points q1;q2;q3 as described above, determining whether such a q4 exists is a relatively simple matter. We illustrate the needed steps below. 1) Begin by selecting t1;t2;t3 2Q. 2) Plug these values into the parameterizations given earlier to obtain rational points q1 2C1;q2 2C2, and q3 2C3. 3) Let P1 and P2 be the planes consisting of all points equidistant from q1;q2 and q1;q3 respectively. If P1 and P2 happen to be parallel (in other words, if the points q1;q2;q3 are collinear), return to Step 1 and select new values of t1;t2;t3. 4) Let L be the line of intersection of P1 and P2, and let (x0;y0;z0) be any rational point on L. Such a point must exist as the circumcenter of the triangle with vertices q1;q2;q3 is in Q3 and also on L. Let be the cross product of vectors !q1q2 and !q1q3, and note that v1;v2;v3 2Q. 5) Parameterize L as x = x0 +v1s, Y = y0 +v2s, z = z0 +v3s. 6) Supposing q1 = (x1;y1;z1), solve the following quadratic equation for s: (x0 +v1s x1)2 + (y0 +v2s y1)2 + (z0 +v3s z1)2 = 10: (5.14) 48 If this equation has a rational solution for s, the desired q4 exists, and we conclude that C1 cannot consist of three monochromatic circles. 5.5 Concluding Remarks It seems incredibly unlikely that one would \arbitrarily" choose rational numbers t1;t2, and t3 and luckily stumble upon a rational solution for Equation 5.14. However, Q3 is countable, so we may put it in one-to-one correspondence with the natural numbers and institute a computer search to attempt to nd a triple (t1;t2;t3) leading to a rational s. This method of search cannot be exhaustive, but as we are only interested in showing the existence of a single rational solution, the idea seems promising. We can increase the e ciency of our search algorithm by rst narrowing down the list of rational triples (t1;t2;t3) that could possibly yield a rational solution to Equation 5.14. To do this, we put Q2 into one-to-one correspondence with the natural numbers and then for (t1;t2)2Q2, use Lemma 5.1 in conjunction with Legendre?s Theorem to decide whether the points q1 and q2 given by the previous parameterizations have a rational point q4 distance p10 from each. If they do not, we can for each p2Q rule out (t 1;t2;p) as possibly leading to a rational s. Should our search prove successful, we would of course be interested in using the same ideas to determine (Q3;p2k) for other k values. Additional complications could arise. We began our study of G(Q3;p10) with a 5-cycle which was seemingly plucked out of thin air. As far as we know, however, it is unknown whether or not for each k2K the graph G(Q3;p2k) contains a 5-cycle. Empirical evidence suggests that it does. In practice it has been very easy to construct such 5-cycles. In fact, we conjecture that the graph G(Z3;p2k) contains a 5-cycle for each k2K. Although it only springs up as a side issue in our current topic, resolution of this question would be a worthwhile goal in future research. 49 Bibliography [1] Aaron Abrams and P.D. Johnson, Jr., Yet another species of forbidden distances chro- matic number. Geombinatorics X (2001), no. 3, pp. 89-95. [2] Miro Benda and Micha Perles, Colorings of metric spaces. Geombinatorics IX (January, 2000), pp. 113-126. [3] N. G. de Bruijn and P. Erd}os, A colour problem for in nite graphs and a problem in the theory of relations. Indagationes Math. 13 (1951), pp. 369-373. [4] D. A. Buell, Binary Quadratic Forms: Classical Theory and Modern Computations. Springer-Verlag, New York, 1989. [5] Je rey Burkert, Explicit colorings of Z3 and Z4 with four colors to forbid arbitrary distances. Geombinatorics 13 (2009), no. 4, pp. 149-152. [6] T. Chow, Distances forbidden by two-colorings of Q3 and An. Discrete Math. 115 (1993), pp. 95-102. [7] Va sek Chv atal, The minimality of the Mycielski graph. Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973 ), Lecture Notes in Mathematics 406, Springer-Verlag, pp. 243-246. [8] S. J. Einhorn and I. J. Schoenberg, On Euclidean sets having only two distances between points II. Indagationes Math. 28 (1966), pp. 489-504. [9] M. Gardner, A new collection of \brain teasers". Scienti c American 206 (Oct. 1960), pp. 172-180. [10] H. Hadwiger, Uberdeckung des euklidischen Raum durch kongruente Mengen. Portu- galiae Math. 4 (1945), pp. 238-242. [11] E. J. Ionascu, A parametrization of equilateral triangles having integer coordinates. J. Integer Sequences, vol. 10 (2007), #07.6.7. [12] E. J. Ionascu, Counting all equilateral triangles inf0;1;:::;ng3. Acta Math. Univ. Come- nianae, vol. LXXVII, 1 (2008), pp. 129-140. [13] Peter Johnson, Andrew Schneider, and Michael Tiemeyer, B1(Q3) = 4. Geombinatorics 16 (April, 2007), pp. 356-362. 50 [14] Peter D. Johnson, Jr., Euclidean distance graphs on the rational points, in Ramsey Theory: Yesterday, Today, and Tomorrow, Alexander Soifer, editor. Progress in Math- ematics vol. 285 (2010), Birkhauser, pp. 97-113. [15] Peter D. Johnson, Jr. and Michael Tiemeyer, Which pairs of distances can be forbidden by a four-coloring of Q3?. Geombinatorics 18 (2009), no. 4, pp. 161-170. [16] P. D. Johnson, Jr., Introduction to \Colorings of Metric Spaces" by Benda and Perles. Geombinatorics IX (3) (2000), pp. 110-112. [17] P. D. Johnson Jr., Two-colorings of a dense subgroup of Qn that forbid many distances. Discrete Math. 79 (1989/1990), pp. 191-195. [18] Douglas Jungreis, Michael Reid, and Dave Witte, Distances forbidden by some two- coloring of Q2. Discrete Math. 82 (1990), no. 1, pp. 53-56. [19] William J. LeVeque, Fundamentals of Number Theory. Addison Wesley, Reading, Mas- sachusetts, 1977. [20] L. Moser and W. Moser, Solution to Problem 10. Can. Math. Bull. 4 (1961), pp. 187-189. [21] J. Mycielski, Sur le coloriage des graphes. Colloquium Mathematicum 3 (1955), pp. 161-162. [22] Trygve Nagell, Introduction to Number Theory. John Wiley & Sons, Inc., New York, 1951. [23] Matt Noble, Chromatic numbers of two-distance graphs in Q2. Geombinatorics XXI (3) (2012), pp. 110-116. [24] J. P. Serre, A Course in Arithmetic, Graduate Texts in Mathematics. Springer, 1973. [25] Joseph H. Silverman and John Tate, Rational Points on Elliptic Curves. Springer- Verlag, New York, 1992. [26] Alexander Soifer, The Mathematical Coloring Book. ISBN 978-0-387-74640-1, Springer, 2009. [27] D. R. Woodall, Distances realized by sets covering the plane. J. Combin. Theory Ser. A 14 (1973), pp. 187-200. 51