A Bound on the Distance from Approximation Vectors to the Plane

T. Cheslack-Postava, A. Diesl, M. Lepinski, A. Schuyler

August 12, 1999

Abstract In this paper, we will begin by reviewing triangle sequences. One interpretation of these sequences is as a sequence of approximation vectors approaching the plane x + αy + βz = 0. This paper establishes an upper bound on the distance from the n^{th} approximation vector to the plane x + αy + βz = 0.

1 Introduction

This paper will start with an overview of triangle sequences as outlined in work by Garrity [2]. We begin with a geometrical interpretation of triangle sequences. We define an iteration T on the triangle:

△ = (x, y) : 1 ≥ x ≥ y > 0.

This triangle is partitioned into an infinite set of disjoint subtriangles

△_{k} = (x, y) ∈ △ : 1 − x − ky ≥ 0 > 1 − x − (k + 1)y,

where k is any nonnegative integer.

Define the map T : △ → △ ∪ (x, 0) : 0 ≤ x ≤ 1 by

T (α, β) = (\frac{β}{α}, \frac{1 − α − kβ}{α} ) ,

where (α, β) ∈ △_{k}.

The triangle sequence is recovered from this iteration by keeping track of the number of the triangle that the point is mapped into at each step. In other words, if T^{k−1}(α, β) ∈ △_{a_{k}}, then the point (α, β) will have the triangle sequence (a_{1}, a_{2}, a_{3}, …).

We will recursively define a sequence of vectors as follows: SetC_{−2} = (1, 0, 0), C_{−1} = (0, 1, 0), C_{0} = (0, 0, 1) and

C_{n} = C_{n−3} − C_{n−2} − a_{n}C_{n−1}

Let the components of C_{n} be denoted by C_{n} = (p_{n}, q_{n}, r_{n}). These vectors C_{n} can be thought of as integer vectors approximating the plane x + αy + βz = 0. We thus refer to the C_{n} vectors as approximation vectors. We define positive numbers d_{n} in the following manner:

d_{n} = (1, α, β) · C_{n}

These numbers are an indication of close the approximation vectors are to the plane x+αy+βz = 0. (In fact, these numbers differ from the Euclidean distance to the plane by a constant factor). The rest of the paper concerns itself with bounding d_{n} from above. Let X_{n} = C_{n} × C_{n+1} as defined in [1]. We shall denote the components of X_{n} as (x_{n}, y_{n}, z_{n}). In the next section we establish the bound of:

d_{n} < \frac{1}{x_{n+1}}

2 A Bound on d_{n}

Let N_{n} be the matrix,

(\begin{matrix}x_{n−1} & y_{n−1} & z_{n−1} \\ x_{n} − x_{n−1} & y_{n} − y_{n−1} & z_{n} − z_{n−1} \\ x_{n−2} & y_{n−2} & z_{n−2} \end{matrix})

We set M_{n} = (C_{n−2}, C_{n−1}, C_{n}). Recall from [2] that det(M_{n}) = C_{n−2} · (C_{n−1} × C_{n}) = 1.

Lemma 1 M_{n}^{−1} = N_{n}

Proof: We know that

N_{n}M_{n} = (\begin{matrix}x_{n−1} & y_{n−1} & z_{n−1} \\ x_{n} − x_{n−1} & y_{n} − y_{n−1} & z_{n} − z_{n−1} \\ x_{n−2} & y_{n−2} & z_{n−2} \end{matrix}) (\begin{matrix}p_{n−2} & p_{n−1} & p_{n} \\ q_{n−2} & q_{n−1} & q_{n} \\ r_{n−2} & r_{n−1} & r_{n} \end{matrix})

By performing the above multiplication, we get

N_{n}M_{n} = (\begin{matrix}C_{n−2} · X_{n−1} & C_{n−1} · X_{n−1} & C_{n} · X_{n−1} \\ C_{n−2} · X_{n} − C_{n−2} · X_{n−1} & C_{n−1} · X_{n} − C_{n−1} · X_{n−1} & C_{n} · X_{n} − C_{n} · X_{n−1} \\ C_{n−2} · X_{n−2} & C_{n−1} · X_{n−2} & C_{n} · X_{n−2} \end{matrix})

Since for all k, we know that X_{k} = C_{k} × C_{k+1}, then

C_{k} · X_{k} = 0
C_{k} · X_{k−1} = 0
C_{k} · X_{k+1} = 1

Additionally,

C_{n−2} · X_{n} = C_{n−2} · (X_{n−3} + a_{n}X_{n−2} + X_{n−1})
C_{n−2} · X_{n} = C_{n−2} · X_{n−3} + a_{n}C_{n−2} · X_{n−2} + C_{n−2} · X_{n−1}
C_{n−2} · X_{n} = 1

and

C_{n} · X_{n−2} = (C_{n−3} − C_{n−2} − a_{n}C_{n−1}) · X_{n−2}
C_{n} · X_{n−2} = C_{n−3} · X_{n−2} − C_{n−2} · X_{n−2} + a_{n}C_{n−1} · X_{n−2}
C_{n} · X_{n−2} = 1

Therefore,

N_{n}M_{n} = (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})

Hence, N_{n} = M_{n}^{−1}

□

Lemma 2 The following three equalities are true:

1 = d_{n}x_{n−2} + d_{n−2}x_{n−1} + d_{n−1}x_{n} − d_{n−1}x_{n−1}
α = d_{n}y_{n−2} + d_{n−2}y_{n−1} + d_{n−1}y_{n} − d_{n−1}y_{n−1}
β = d_{n}z_{n−2} + d_{n−2}z_{n−1} + d_{n−1}z_{n} − d_{n−1}z_{n−1}

Proof: We know that

(1, α, β)M_{n} = (d_{n−2}, d_{n−1}, d_{n})

Therefore, since M_{n}^{−1} = N_{n},

(1, α, β) = (d_{n−2}, d_{n−1}, d_{n})N_{n}

Therefore,

1 = d_{n}x_{n−2} + d_{n−2}x_{n−1} + d_{n−1}x_{n} − d_{n−1}x_{n−1}
α = d_{n}y_{n−2} + d_{n−2}y_{n−1} + d_{n−1}y_{n} − d_{n−1}y_{n−1}
β = d_{n}z_{n−2} + d_{n−2}z_{n−1} + d_{n−1}z_{n} − d_{n−1}z_{n−1}
□

Lemma 3

α = \frac{y_{n−1} + β_{n}y_{n−2} + α_{n}y_{n} − α_{n}y_{n−1}}{x_{n−1} + β_{n}x_{n−2} + α_{n}x_{n} − α_{n}x_{n−1}}
β = \frac{z_{n−1} + β_{n}z_{n−2} + α_{n}z_{n} − α_{n}z_{n−1}}{x_{n−1} + β_{n}x_{n−2} + α_{n}x_{n} − α_{n}x_{n−1}}

Proof: From Lemma 2, we know that

1 = d_{n−2}x_{n−1} + d_{n}x_{n−2} + d_{n−1}x_{n} − d_{n−1}x_{n−1}

By recalling that α_{n} = \frac{d_{n−1}}{d_{n−2}} and β_{n} = \frac{d_{n}}{d_{n−2}} , we can divide through by d_{n−2} to get

\frac{1}{d_{n−2}} = x_{n−1} + β_{n}x_{n−2} + α_{n}x_{n} − α_{n}x_{n−1}

Or equivalently,

d_{n−2} = \frac{1}{x_{n−1} + β_{n}x_{n−2} + α_{n}x_{n} − α_{n}x_{n−1}}  (1)

Also from Lemma 2, we have that

α = d_{n−2}y_{n−1} + d_{n}y_{n−2} + d_{n−1}y_{n} − d_{n−1}y_{n−1}
β = d_{n−2}z_{n−1} + d_{n}z_{n−2} + d_{n−1}z_{n} − d_{n−1}z_{n−1}

Factoring out a d_{n−2} from the right hand sides yields

α = d_{n−2}(y_{n−1} + β_{n}y_{n−2} + α_{n}y_{n} − α_{n}y_{n−1})
β = d_{n−2}(z_{n−1} + β_{n}z_{n−2} + α_{n}z_{n} − α_{n}z_{n−1})

Substituting in for d_{n−2} from Equation (1), we get

α = \frac{y_{n−1} + β_{n}y_{n−2} + α_{n}y_{n} − α_{n}y_{n−1}}{x_{n−1} + β_{n}x_{n−2} + α_{n}x_{n} − α_{n}x_{n−1}}
β = \frac{z_{n−1} + β_{n}z_{n−2} + α_{n}z_{n} − α_{n}z_{n−1}}{x_{n−1} + β_{n}x_{n−2} + α_{n}x_{n} − α_{n}x_{n−1}}
□

Theorem 1 d_{n} < \frac{1}{x_{n+1}}

Proof: From Lemma 2, we know that

d_{n+1}x_{n−1} + d_{n−1}x_{n} + d_{n}x_{n+1} − d_{n}x_{n} = 1

Since d_{n+1} > 0 and x_{n−1} > 0, we can write the inequality:

d_{n−1}x_{n} + d_{n}x_{n+1} − d_{n}x_{n} < 1

Since the d_{n} terms are decreasing, we can substitute d_{n} for d_{n−1} and maintain the inequality:

d_{n}x_{n} + d_{n}x_{n+1} − d_{n}x_{n} < 1

This implies that

d_{n} < \frac{1}{x_{n+1}}

□

References

[1] T. Cheslack-Postava, A. Diesl, M. Lepinski, and A. Schuyler. Some results concerning uniqueness of triangle sequences. 1999.

[2] Thomas Garrity. On periodic sequences for algebraic numbers. 1999.