Maximal Dimension of Unit Simplices

Christian Elsholtz^{1} and Walter Klotz^{2}

1Department of Mathematics Royal Holloway University of London Egham Surrey TW20 0EX UK christian.elsholtz@rhul.ac.uk

2Institut für Mathematik Technische Universität Clausthal D-38678 Clausthal-Zellerfeld Germany klotz@math.tu-clausthal.de

Abstract Abstract. For an arbitrary field 𝔽 the maximal number ω(𝔽^{n}) of points in 𝔽^{n} mutually distance 1 apart with respect to the standard inner product is investigated. If the characteristic char(𝔽) is different from 2, then the values of ω(𝔽^{n}) lie between n − 1 and n + 2. In particular, we answer completely for which n a simplex of q points with edge length 1 can be embedded in rational n-space. Our results imply for almost all even n that ω(ℚ^{n}) = n and for almost all odd n that ω(ℚ^{n}) = n − 1.

Keywords: equidistant points, unit-distance graph.

2000 Mathematics Subject Classification: Primary 51K05, 52C35. Secondary 05C69.

1 Introduction

1.1 Motivation

It is well known that the unilateral triangle cannot be embedded into ℚ^{2}. In ℚ^{8} we easily find the regular unilateral simplex spanned by the following 9 points:

( \frac{1}{2} ; ±\frac{1}{2} ; 0 ; 0 ; 0 ; 0 ; 0 ; 0) , ( 0 ; 0 ; \frac{1}{2} ; ±\frac{1}{2} ; 0 ; 0 ; 0 ; 0) , ( 0 ; 0 ; 0 ; 0 ; \frac{1}{2} ; ±\frac{1}{2} ; 0 ; 0) , ( 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; \frac{1}{2} ; ±\frac{1}{2} ) , (\frac{1}{2} 0 \frac{1}{2} 0 \frac{1}{2} 0 \frac{1}{2} 0)

In ℝ^{n} we can obviously place exactly n+1 points defining a unilateral simplex. If we define ω(𝔽^{n}) to be the maximal number of points mutually at unit distance over the field 𝔽, then ω(ℝ^{n}) = n + 1. (For a precise definition of the distance function see the next subsection.) On the other hand, ω(ℚ^{n}) had previously only been determined up to the solution of a diophantine equation, see Chilakamarri [4]. In this paper we solve this diophantine equation and thus determine ω(ℚ^{n}) completely. It turns out that the prime factorizations of n and n+1 are an important ingredient in the classification. A consequence of this result is that ω(ℚ^{n}) = n for almost all even n and ω(ℚ^{n}) = n − 1 for almost all odd n.

The problem of determining ω(𝔽^{n}) is loosely connected to the problem of the chromatic number of 𝔽^{n}. Let χ(𝔽^{n}) be the minimum number of colours needed to colour 𝔽^{n} so that no two points of the same colour are one unit apart. Even the determination of the chromatic number of the plane is a major outstanding problem. It is only known that 4 ≤ χ(ℝ^{2}) ≤ 7. For a survey see [10] and [11]. We may interpret ω(𝔽^{n}) as the clique number of the unit-distance graph G_{1}(𝔽^{n}), which has vertex set 𝔽^{n} with vertices x, y connected by an edge, if they are at unit distance, compare [5]. Then ω(𝔽^{n}) is a lower bound for the chromatic number χ(G_{1}(𝔽^{n})) = χ(𝔽^{n}). For 𝔽 = ℚ some exact values are known. χ(ℚ^{2}) = χ(ℚ^{3}) = 2, χ(ℚ^{4}) = 4 ([1] and [12]), χ(ℚ^{5}) ≥ 7 ([8]). This compares very well with ω(ℚ^{2}) = ω(ℚ^{3}) = 2 and ω(ℚ^{4}) = ω(ℚ^{5}) = 4. While ω(ℚ^{n}) ≤ ω(ℝ^{n}) = n + 1 the chromatic numbers χ(ℚ^{n}) and χ(ℝ^{n}) increase exponentially, see [6] and [9].

1.2 Results

As many of our arguments hold for arbitrary fields, we start with a rather general setting. The most interesting applications are perhaps to subfields of ℝ.

Let 𝔽 be an arbitrary field, x = (x_{i}) ∈ 𝔽^{n} and y = (y_{i}) ∈ 𝔽^{n}, n a positive integer. Define the quadratic distance of points x and y by the standard inner product:

Δ(x, y) = (x − y)^{2} = ∑_{i=1}^{n}(x_{i} − y_{i})^{2}.

By ω(𝔽^{n}) we denote the maximal number of points in 𝔽^{n}, which mutually have quadratic distance 1.

We call the standard inner product of 𝔽^{n} nonisotropic, if

x · x = 0 ⟺ x = 0 for every x ∈ 𝔽^{n}.

Observe that e.g. for char(𝔽) = 2 and n ≥ 2 the standard inner product is not nonisotropic, while it is nonisotropic for real fields.

In case of nonisotropic inner product the next theorem completely determines ω(𝔽^{n}) up to the solution of a quadratic equation in the very last case, with values bounded by n−1 ≤ ω(𝔽^{n}) ≤ n+2. For the proof we combine methods from design theory (Bruck-Ryser type arguments, see [3]) with those from linear algebra and number theory.

Theorem 1.

A) If char(𝔽) = 2, then ω(𝔽^{n}) = 2 for every n ≥ 1.

B) If char(𝔽) ≠ 2 and n is even, then the following statements hold true:

1) If \sqrt{n + 1} ∉ 𝔽, then ω(𝔽^{n}) = n.

2) Suppose that \sqrt{n + 1} ∈ 𝔽.

If n = −2 in 𝔽, then ω(𝔽^{n}) = n + 2, otherwise ω(𝔽^{n}) = n + 1.

C) If char(𝔽) ≠ 2 and n is odd, then the following statements hold true:

1) Suppose that \sqrt{(n + 1)/2} ∈ 𝔽. If n = −2 in 𝔽, then ω(𝔽^{n}) = n + 2, otherwise ω(𝔽^{n}) = n + 1.

2) Suppose that \sqrt{(n + 1)/2} ∉ 𝔽.

If the equation

u^{2} + 2(n − 1)v^{2} = n  (1)

has a solution with u ∈ 𝔽 and v ∈ 𝔽, then ω(𝔽^{n}) = n.

If the standard inner product of 𝔽^{n} is nonisotropic and if equation (1) is unsolvable in 𝔽, then ω(𝔽^{n}) = n − 1.

Theorem 1 immediately implies the following corollary:

Corollary 1.

The smallest field 𝔽 over ℚ such that ω(𝔽^{n}) = n+1 for every positive integer n is 𝔽 = ℚ[\sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{7}, …].

The next theorem describes the complete evaluation of ω(ℚ^{n}).

Theorem 2.

A) Let n be even. If n + 1 is the square of an integer, then ω(ℚ^{n}) = n + 1, otherwise ω(ℚ^{n}) = n.

B) Let n be odd.

1) If (n + 1)/2 is the square of an integer, then ω(ℚ^{n}) = n + 1.

2) Suppose that (n+1)/2 is not the square of an integer. Let n = n_{1}n_{2}^{2} be the factorization of n with unique squarefree divisor n_{1}. If n_{1} has no prime divisor p ≡ ±3 modulo 8, then ω(ℚ^{n}) = n, and ω(ℚ^{n}) = n − 1 otherwise.

Let N_{even}(t) denote the number of even integers n ≤ t with ω(ℚ^{n}) ≠ n and N_{odd}(t) the number of odd integers n ≤ t with ω(ℚ^{n}) ≠ n − 1. Evidently, part A) of Theorem 2 implies N_{even}(t) ∼ \frac{\sqrt{t}}{2}. Landau’s method [7, §§177-183] on estimating the number of positive integers ≤ t with specified prime factors only, allows us to conclude from part B) of Theorem 2 that we have

N_{odd}(t) ∼ c\frac{t}{(log t)^{1/2}} for some positive constant c. So we may state the

following consequence.

Corollary 2.

1) ω(ℚ^{n}) = n for almost all even integers n.

2) ω(ℚ^{n}) = n − 1 for almost all odd integers n.

Theorem 2 and its Corollary 2 have the following geometric interpretation. For those n with ω(ℚ^{n}) = n + 1 it is possible to rotate the regular ndimensional simplex with edge length 1 in ℝ^{n} so that all coordinates of the n + 1 vertices become rational. For almost all dimensions n however, this type of rotation does not exist and only a unilateral simplex with up to n (for even n), respectively n − 1 (for odd n) vertices can be embedded into ℚ^{n}.

We would like to thank the unknown referees for their helpful comments.

2 Proof of Theorem 1

First we settle the case char(𝔽) = 2 and establish the upper bounds. Let x_{0}, ..., x_{m} be m + 1 points in 𝔽^{n} mutually at quadratic distance 1. We may suppose x_{0} = 0. Then the other vectors x_{j}, j ≥ 1, have unit length and for i, j ≥ 1, i ≠ j, we have

(x_{i} − x_{j})^{2} = x_{i}^{2} − 2x_{i}x_{j} + x_{j}^{2} = 1, 2x_{i}x_{j} = 1.

If char(𝔽) = 2 and m ≥ 2, then the last equation implies a contradiction. This proves A).

From now on we assume char(𝔽) ≠ 2. Let the m × n-matrix A be formed by the rows x_{1}, …, x_{m}. Then AA^{T} is an m × m-matrix with entries 1 in the main diagonal and \frac{1}{2} in the other positions so that

det AA^{T} = (m + 1)\frac{1}{2^{m}} .  (2)

If m ≠ −1 in 𝔽, then det AA^{T} ≠ 0, so that

rank AA^{T} = m ≤ rank A ≤ n.  (3)

For m = n+1 and n ≠ −2 in 𝔽 inequality (3) leads to a contradiction, which implies

ω(𝔽^{n}) ≤ n + 1, if n ≠ −2 in 𝔽.  (4)

If n = −2 in 𝔽, then a contradiction in (3) occurs for m = n+2, which shows

ω(𝔽^{n}) ≤ n + 2, if n = −2 in 𝔽.  (5)

Let m = n. Then (2) may be written as

n + 1 = 2^{n}(det A)^{2}.

If n is even, then n + 1 is the square of an element in 𝔽, i.e. \sqrt{n + 1} ∈ 𝔽. If n is odd, then

(n + 1)/2 = 2^{n−1}(det A)^{2}

is the square of an element in 𝔽, i.e. \sqrt{(n + 1)/2} ∈ 𝔽. So we know:

ω(𝔽^{n}) ≤ n, if \{ \begin{matrix}n is even and \sqrt{n + 1} ∉ 𝔽 \\ n is odd and \sqrt{(n + 1)/2} ∉ 𝔽. \end{matrix}  (6)

To establish lower bounds we start the constructive part of our proof. We define a system σ of n points x^{(1)}, ..., x^{(n)}, if n is even, and of n − 1 points x^{(1)}, ..., x^{(n−1)}, if n is odd. If we take the vectors of σ as the rows of a matrix, this matrix has the following shape:

( \begin{matrix}\frac{1}{2} & & & & & & & & & \frac{1}{2} \\ \frac{1}{2} & & & & & & & & & −\frac{1}{2} \\ & \frac{1}{2} & & & & & & & \frac{1}{2} \\ & \frac{1}{2} & & & & & & & −\frac{1}{2} \\ & & · & & & & & · \\ & & · & & & & & · \\ & & & · & & & · \\ & & & · & & & · \\ & & & & \frac{1}{2} & \frac{1}{2} \\ & & & & \frac{1}{2} & −\frac{1}{2} \end{matrix} ) .

Positions left empty have to be filled with zeros. If n is odd, a last column consisting of zeros only has to be added. Clearly, the points in σ are mutually at distance 1. Thus we have ω(𝔽^{n}) ≥ n, if n is even and ω(𝔽^{n}) ≥ n − 1, if n is odd.

We try to extend the system σ equidistantly by a point y = (y_{1}, …, y_{n}) ∈ 𝔽^{n}.

First we suppose that n is even.

The additional point y must have quadratic distance 1 to all points x^{(1)}, …, x^{(n)} of σ, which for m = 1, …, \frac{n}{2} implies

Δ(y, x^{(2m−1)}) = (y_{m} − \frac{1}{2})^{2} + (y_{n−m+1} − \frac{1}{2})^{2} + ∑_{i≠m,n−m+1}(y_{i})^{2} = 1,

Δ(y, x^{(2m)}) = (y_{m} − \frac{1}{2})^{2} + (y_{n−m+1} + \frac{1}{2})^{2} + ∑_{i≠m,n−m+1}(y_{i})^{2} = 1.

Taking the difference of these equations yields

y_{n−m+1} = 0 for m = 1, ..., \frac{n}{2}.

Now we have for 1 ≤ m ≤ \frac{n}{2} − 1:

Δ(y, x^{(2m−1)}) = (y_{m} − \frac{1}{2})^{2} + \frac{1}{4} + ∑_{i≠m}(y_{i})^{2} = 1,

Δ(y, x^{(2m+1)}) = (y_{m+1} − \frac{1}{2})^{2} + \frac{1}{4} + ∑_{i≠m+1}(y_{i})^{2} = 1.

Again subtracting equations leads to

y_{m+1} = y_{m} for m = 1, ..., \frac{n}{2} − 1.

Thus we see that y must have the form

y = y(s) = (\underbrace{s, ... , s}_{\frac{n}{2} entries}, \underbrace{0, ... , 0}_{\frac{n}{2} entries}), s ∈ 𝔽.

Indeed, in this shape y has the same distance to all points x^{(j)}, j ≤ n.

Δ(y, x^{(j)}) = (s − \frac{1}{2})^{2} + (\frac{n}{2} − 1)s^{2} + \frac{1}{4} = 1,

\frac{n}{2}s^{2} − s − \frac{1}{2} = 0.  (7)

If n = 0 in 𝔽, then σ can be extended equidistantly by y(−\frac{1}{2}) to a system of n + 1 points. According to (4) this is optimal, hence ω(𝔽^{n}) = n + 1. Notice that \sqrt{n + 1} = 1 ∈ 𝔽 in this case, which corresponds to part B) 2) of Theorem 1.

If n ≠ 0 in 𝔽, then we solve equation (7) for s.

s = \frac{1}{n}(1 ± \sqrt{n + 1}).

An equidistant extension of σ exists, if and only if \sqrt{n + 1} ∈ 𝔽. If \sqrt{n + 1} ∈ 𝔽 and n ≠ −2 in 𝔽, then ω(𝔽^{n}) = n + 1 according to (4).

To finish the case of even n, suppose now n = −2 in 𝔽 and \sqrt{n + 1} = \sqrt{−1} ∈ 𝔽. The only candidates for an equidistant extension of σ are

y^{(1)} = y(s_{1}) with s_{1} = \frac{1}{n}(1 + \sqrt{n + 1}) = −\frac{1}{2}(1 + \sqrt{−1}),

y^{(2)} = y(s_{2}) with s_{2} = \frac{1}{n}(1 − \sqrt{n + 1}) = −\frac{1}{2}(1 − \sqrt{−1}).

The quadratic distance of y^{(1)} and y^{(2)} is

Δ(y^{(1)}, y^{(2)}) = \frac{n}{2}(s_{1} − s_{2})^{2} = − (\sqrt{−1})^{2} = 1,

which means that in this case the system σ can be extended equidistantly to a system of n + 2 points. According to (5) no further extension is possible, ω(𝔽^{n}) = n + 2.

We now consider the case of odd n.

In this case the system σ consists of n−1 points x^{(1)}, …, x^{(n−1)}. Again we try to extend σ equidistantly by a point y = (y_{1}, …, y_{n}). As above the distance conditions

Δ(y, x^{(j)}) = 1 for j = 1, …, n − 1

force y to take the following form:

y = y(s, v) = ( \underbrace{s, ... , s}_{\frac{n−1}{2} entries}, \underbrace{0, ... , 0,}_{\frac{n−1}{2} entries} v), s ∈ 𝔽, v ∈ 𝔽.

Indeed, in this shape y has the same distance to all points x^{(j)}, j < n.

Δ(y, x^{(j)}) = (s − \frac{1}{2})^{2} + (\frac{n − 1}{2} − 1)s^{2} + \frac{1}{4} + v^{2} = 1,

\frac{n − 1}{2}s^{2} − s + v^{2} − \frac{1}{2} = 0.  (8)

An equidistant extension of σ exists, if and only if (8) has a solution with s ∈ 𝔽 and v ∈ 𝔽.

If n = 1 in 𝔽, then (8) reduces to

s = v^{2} − \frac{1}{2}.

For v = ±\frac{1}{2}, s = −\frac{1}{4} we get two points, which extend σ equidistantly to a system of n + 1 points. If n ≠ −2 in 𝔽, this leads to ω(𝔽^{n}) = n + 1 according to (4). Notice that in this case \sqrt{(n + 1)/2} = 1 ∈ 𝔽, which supports part C)

1) of Theorem 1. If simultaneously n = 1 and n = −2 in 𝔽, then char(𝔽) = 3. In this case we can find 3 points for an equidistant extension of σ:

y^{(1)} = y(\frac{1}{2}, 1), y^{(2)} = y(\frac{1}{2}, −1), y^{(3)} = y(−\frac{1}{2}, 0).

According to (5) no further extension is possible. So in this case ω(𝔽^{n}) = n + 2, which again corresponds to part C) 1) of Theorem 1.

Suppose now n ≠ 1 in 𝔽. We solve (8) for s:

s = \frac{1}{n − 1} (1 ± \sqrt{1 − 2(n − 1)(v^{2} − \frac{1}{2})}) .  (9)

There is an equidistant extension of σ, if and only if the equation

1 − 2(n − 1)(v^{2} − \frac{1}{2}) = u^{2} or equivalently

u^{2} + 2(n − 1)v^{2} = n  (10)

has a solution with u ∈ 𝔽 and v ∈ 𝔽. We try to find a solution of (10) for v = ±\frac{1}{2}.

u^{2} + 2(n − 1)\frac{1}{4} = n, u = ± \sqrt{(n + 1)/2}.

If \sqrt{(n + 1)/2} ∈ 𝔽, then we determine s ∈ 𝔽 for v = ±\frac{1}{2} by (9). The points y^{(1)} = y(s, \frac{1}{2}), y^{(2)} = y(s, −\frac{1}{2}) extend σ equidistantly to a system of n + 1 points. If n ≠ −2 in 𝔽, then by (4) we conclude ω(𝔽^{n}) = n + 1. If n = −2 in 𝔽, then we take a closer look at the common element s in y^{(1)} and y^{(2)}, which we get from (9):

s = − \frac{1}{3}(1 + \sqrt{−\frac{1}{2}}) = − \frac{1}{3}(1 + \frac{1}{2} \sqrt{−2}).

Notice that char(𝔽) ≠ 3 and \sqrt{−2} ∈ 𝔽 in this case. Now (10) has a further solution in 𝔽: v = 0, u = \sqrt{−2}. For v = 0 we determine s_{0} by (9):

s_{0} = − \frac{1}{3}(1 − \sqrt{−2}).

It is easily checked that σ can be extended equidistantly by the following 3 points:

y^{(1)} = y(s, \frac{1}{2}), y^{(2)} = y(s, −\frac{1}{2}), y^{(3)} = y(s_{0}, 0).

This shows ω(𝔽^{n}) = n + 2 in this case and completes the proof of part C) 1) in Theorem 1.

To finish the proof of part C) 2) of Theorem 1 we may assume that n is odd and \sqrt{(n + 1)/2} ∉ 𝔽. In this case the possible values of ω(𝔽^{n}) are n − 1 and n. We show that it is no loss of generality, if we start with the special points studied above. For the points x^{(1)}, …, x^{(n−1)} of σ we set

w^{(j)} = x^{(j+1)} − x^{(1)}, j = 1, …, n − 2.

Then we have (w^{(j)})^{2} = 1 and w^{(j)}w^{(k)} = 1/2 for j ≠ k. If there is any system of n points in 𝔽^{n} mutually at quadratic distance 1, then we could analogously find vectors z^{(1)}, …, z^{(n−1)} satisfying (z^{(j)})^{2} = 1 and z^{(j)}z^{(k)} = 1/2 for j ≠ k. Now a theorem from linear algebra (Proposition 2 of the Appendix) guarantees the existence of an isometry f of 𝔽^{n} with

f(z^{(j)}) = w^{(j)} for j = 1, ..., n − 2.

For this proposition we need char(𝔽) ≠ 2 and the assumption that the standard inner product of 𝔽^{n} is nonisotropic. Now

y = x^{(1)} + f(z^{(n−1)})

would have quadratic distance 1 to every point x^{(j)}, j < n. This means that ω(𝔽^{n}) = n, if and only if the system σ of points x^{(1)}, ..., x^{(n−1)} has an equidistant extension by an additional point y. We have already shown that such an extension exists, if and only if equation (10) is solvable in 𝔽. This completes the proof of Theorem 1.

3 Proof of Theorem 2

Parts A) and B)1) immediately follow from Theorem 1. Let n be odd and (n + 1)/2 not the square of an integer. From Theorem 1, C) 2) we conclude ω(ℚ^{n}) = n, if the equation

u^{2} + 2(n − 1)v^{2} = n

has a solution with u, v ∈ ℚ and ω(ℚ^{n}) = n−1, if this equation is unsolvable in ℚ. We may set

u = \frac{z}{x} , v = \frac{y}{x} with integers x, y, z, x ≠ 0

and so arrive at the diophantine equation of Chilakamarri [4]:

nx^{2} − 2(n − 1)y^{2} = z^{2}.

If this equation has a solution in integers x, y, z with x ≠ 0, then ω(ℚ^{n}) = n, otherwise ω(ℚ^{n}) = n − 1. So the proof of Theorem 2 will be accomplished, if the following proposition is shown to be true.

Proposition 1. Let n be an integer ≠ 0 and n = n_{1}n_{2}^{2} the factorization of n with unique squarefree divisor n_{1}. The diophantine equation

nx^{2} − 2(n − 1)y^{2} = z^{2}  (11)

has a solution in integers x, y, z, x ≠ 0 if and only if n_{1} has no prime divisor p ≡ ±3 modulo 8.

To prove Proposition 1 we take advantage of the following result from number theory.

Lemma 1. Let n be an integer ≠ 0 and n = n_{1}n_{2}^{2} the factorization of n with unique squarefree divisor n_{1}. The diophantine equation

x^{2} − 2y^{2} = n

has a solution in integers x, y, z, x ≠ 0 if and only if n_{1} has no prime divisor p ≡ ±3 modulo 8.

The proof of Lemma 1 is analogous to the well known classification of those integers that can be written as the sum of two squares. A full proof of Lemma 1 can be found as Theorem 35.3 in Bolker [2].

Proof of Proposition 1. Equation (11) can be transformed to

n(x^{2} − 2y^{2}) = z^{2} − 2y^{2}.  (12)

Suppose x, y, z, x ≠ 0, are integers satisfying (11). As n ≠ 0, x ≠ 0 and as \sqrt{2} is irrational, the integers x^{2} − 2y^{2}, z^{2} − 2y^{2} are nonzero and according to Lemma 1 have prime divisors p ≡ ±3 modulo 8 only with even multiplicity ≥ 0. Equation (12) implies that the same must be true for n.

Now let n have prime divisors p ≡ ±3 modulo 8 only with even multiplicity ≥ 0. By Lemma 1 we can find integers a, b with a^{2}−2b^{2} = n. We may assume that a ≠ 1. It is easily checked that

x = a − 1, y = b, z = a(a − 1) − 2b^{2}

solves (11).

4 Problems and Remarks

The above investigation can no doubt be extended in various directions.

1. Find a complete evaluation of ω(𝔽^{n}) for special fields such as finite fields or ℚ[\sqrt{p}], p a prime number.

2. Try to extend Corollary 2 to finite extensions of ℚ.

3. If 𝔽 is not a real field, then another distance function may be more appropriate.

5 Appendix

To make this paper more selfcontained we outline the result from linear algebra used for the proof of the last case in Theorem 1.

Assume char(𝔽) ≠ 2 and let the standard inner product of 𝔽^{n} be nonisotropic. An isometry f of 𝔽^{n} is a length preserving endomorphism of 𝔽^{n}.

f(x) · f(x) = x · x for every x ∈ 𝔽^{n} ⟺ f(x) · f(y) = x · y for all x, y ∈ 𝔽^{n}.

For ν ∈ 𝔽^{n}, ν ≠ 0 let H(ν) = {x ∈ 𝔽^{n} : ν · x = 0} be the hyperplane with normal vector ν. Every x ∈ 𝔽^{n} can be uniquely written as

x = x_{H} + λν, x_{H} ∈ H(ν), λ ∈ 𝔽.

The reflection S_{ν} at the hyperplane H(ν) is defined by S_{ν}(x) = x_{H} − λν. Clearly, S_{ν} is an isometry.

Proposition 2. Assume that the standard inner product of 𝔽^{n} is nonisotropic and char(𝔽) ≠ 2. Let a_{1}, ..., a_{m}, b_{1}, ..., b_{m} be vectors in 𝔽^{n} satisfying

a_{i} · a_{j} = b_{i} · b_{j} for all i, j = 1, ..., m.

Then there is an isometry f of 𝔽^{n} with f(a_{i}) = b_{i} for every i = 1, ..., m. Either f = id or f is the product of at most m hyperplane reflections.

Proof. We may start the induction on m formally with m = 0 and f = id. For the inductive step suppose that m ≥ 1 and that the assertion is true for m − 1. If a_{1}, ..., a_{m}, b_{1}, ..., b_{m} satisfy the conditions of the proposition, then there is an isometry φ with φ(a_{i}) = b_{i} for i = 1, .., m−1, where φ = id or φ is the product of at most m − 1 hyperplane reflections. If φ(a_{m}) = b_{m}, then we may take f = φ. Let ν = φ(a_{m}) − b_{m} ≠ 0, f = S_{ν}φ. For i < m we have

ν · φ(a_{i}) = φ(a_{m}) · φ(a_{i}) − b_{m} · φ(a_{i}) = a_{m} · a_{i} − b_{m} · b_{i} = 0.

Therefore φ(a_{i}) ∈ H(ν) and

f(a_{i}) = S_{ν}(φ(a_{i})) = φ(a_{i}) = b_{i} for every i, 1 ≤ i < m.

Now (φ(a_{m}))^{2} − b_{m}^{2} = a_{m}^{2} − b_{m}^{2} = 0 implies (φ(a_{m}) − b_{m}) · (φ(a_{m}) + b_{m}) = 0. From ν = φ(a_{m}) − b_{m} and (φ(a_{m}) + b_{m}) ∈ H(ν) we conclude

\begin{matrix}S_{ν}(φ(a_{m}) + b_{m}) & = & φ(a_{m}) + b_{m} \\ S_{ν}(φ(a_{m}) − b_{m}) & = & −φ(a_{m}) + b_{m} \end{matrix} \} ⟹ S_{ν}(φ(a_{m})) = f(a_{m}) = b_{m}.

References

[1] M. Benda and M. Perles, Colorings of metric spaces, Geombinatorics 9 (3) (2000), 113-126.

[2] E.D. Bolker, Elementary Number Theory, W.A. Benjamin, Inc., 1970.

[3] R.H. Bruck and H.J. Ryser, The nonexistence of certain finite projective planes, Canadian J. of Math. 1 (1949), 88-93.

[4] K.B. Chilakamarri, Unit-distance graphs in rational n-spaces, Discrete Mathematics 69 (1988), 213-218.

[5] K.B. Chilakamarri, The unit-distance graph problem: a brief survey and some new results, Bull. Inst. Combin. Appl. 8 (1993), 39-60.

[6] P. Frankl, R.M. Wilson, Intersection theorems with geometric consequences. Combinatorica 1 (1981), no. 4, 357–368.

[7] E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea reprint, New York, 1953.

[8] M. Mann, A new bound for the chromatic number of the rational fivespace, Geombinatorics 11 (2) (2001), 49-54.

[9] A. M. Raigorodskij, Borsuk’s problem and the chromatic numbers of some metric spaces, Russian Math. Surveys 56 (2001), 103-139.

[10] S. Shelah, A. Soifer, Axiom of choice and chromatic number of the plane, J. of Combinatorial Theory A 103 (2003), 387-391.

[11] A. Soifer, Chromatic number of the plane: its past and future, Congress. Numerantium 160 (2003), 69-82.

[12] J. Zaks, On four-colourings of the rational four-space, Aequationes Mathematicae 37 (1989), 259-266.

[13] J. Zaks, On the chromatic number of some rational spaces. Ars Combin. 33 (1992), 253–256.