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
**