Klein polyhedron

Short description: Concept in the geometry of numbers

In the geometry of numbers, the Klein polyhedron, named after Felix Klein, is used to generalize the concept of continued fractions to higher dimensions.

Definition

Let [math]\displaystyle{ \textstyle C }[/math] be a closed simplicial cone in Euclidean space [math]\displaystyle{ \textstyle \mathbb{R}^n }[/math]. The Klein polyhedron of [math]\displaystyle{ \textstyle C }[/math] is the convex hull of the non-zero points of [math]\displaystyle{ \textstyle C \cap \mathbb{Z}^n }[/math].

Relation to continued fractions

Suppose [math]\displaystyle{ \textstyle \alpha \gt 0 }[/math] is an irrational number. In [math]\displaystyle{ \textstyle \mathbb{R}^2 }[/math], the cones generated by [math]\displaystyle{ \textstyle \{(1, \alpha), (1, 0)\} }[/math] and by [math]\displaystyle{ \textstyle \{(1, \alpha), (0, 1)\} }[/math] give rise to two Klein polyhedra, each of which is bounded by a sequence of adjoining line segments. Define the integer length of a line segment to be one less than the size of its intersection with [math]\displaystyle{ \textstyle \mathbb{Z}^n. }[/math] Then the integer lengths of the edges of these two Klein polyhedra encode the continued-fraction expansion of [math]\displaystyle{ \textstyle \alpha }[/math], one matching the even terms and the other matching the odd terms.

Graphs associated with the Klein polyhedron

Suppose [math]\displaystyle{ \textstyle C }[/math] is generated by a basis [math]\displaystyle{ \textstyle (a_i) }[/math] of [math]\displaystyle{ \textstyle \mathbb{R}^n }[/math] (so that [math]\displaystyle{ \textstyle C = \{ \sum_i \lambda_i a_i : (\forall i) \; \lambda_i \geq 0 \} }[/math]), and let [math]\displaystyle{ \textstyle (w_i) }[/math] be the dual basis (so that [math]\displaystyle{ \textstyle C = \{ x : (\forall i) \; \langle w_i, x \rangle \geq 0\} }[/math]). Write [math]\displaystyle{ \textstyle D(x) }[/math] for the line generated by the vector [math]\displaystyle{ \textstyle x }[/math], and [math]\displaystyle{ \textstyle H(x) }[/math] for the hyperplane orthogonal to [math]\displaystyle{ \textstyle x }[/math].

Call the vector [math]\displaystyle{ \textstyle x \in \mathbb{R}^n }[/math] irrational if [math]\displaystyle{ \textstyle H(x) \cap \mathbb{Q}^n = \{0\} }[/math]; and call the cone [math]\displaystyle{ \textstyle C }[/math] irrational if all the vectors [math]\displaystyle{ \textstyle a_i }[/math] and [math]\displaystyle{ \textstyle w_i }[/math] are irrational.

The boundary [math]\displaystyle{ \textstyle V }[/math] of a Klein polyhedron is called a sail. Associated with the sail [math]\displaystyle{ \textstyle V }[/math] of an irrational cone are two graphs:

• the graph [math]\displaystyle{ \textstyle \Gamma_{\mathrm e}(V) }[/math] whose vertices are vertices of [math]\displaystyle{ \textstyle V }[/math], two vertices being joined if they are endpoints of a (one-dimensional) edge of [math]\displaystyle{ \textstyle V }[/math];
• the graph [math]\displaystyle{ \textstyle \Gamma_{\mathrm f}(V) }[/math] whose vertices are [math]\displaystyle{ \textstyle (n-1) }[/math]-dimensional faces (chambers) of [math]\displaystyle{ \textstyle V }[/math], two chambers being joined if they share an [math]\displaystyle{ \textstyle (n-2) }[/math]-dimensional face.

Both of these graphs are structurally related to the directed graph [math]\displaystyle{ \textstyle \Upsilon_n }[/math] whose set of vertices is [math]\displaystyle{ \textstyle \mathrm{GL}_n(\mathbb{Q}) }[/math], where vertex [math]\displaystyle{ \textstyle A }[/math] is joined to vertex [math]\displaystyle{ \textstyle B }[/math] if and only if [math]\displaystyle{ \textstyle A^{-1}B }[/math] is of the form [math]\displaystyle{ \textstyle UW }[/math] where

[math]\displaystyle{ U = \left( \begin{array}{cccc} 1 & \cdots & 0 & c_1 \\ \vdots & \ddots & \vdots & \vdots \\ 0 & \cdots & 1 & c_{n-1} \\ 0 & \cdots & 0 & c_n \end{array} \right) }[/math]

(with [math]\displaystyle{ \textstyle c_i \in \mathbb{Q} }[/math], [math]\displaystyle{ \textstyle c_n \neq 0 }[/math]) and [math]\displaystyle{ \textstyle W }[/math] is a permutation matrix. Assuming that [math]\displaystyle{ \textstyle V }[/math] has been triangulated, the vertices of each of the graphs [math]\displaystyle{ \textstyle \Gamma_{\mathrm e}(V) }[/math] and [math]\displaystyle{ \textstyle \Gamma_{\mathrm f}(V) }[/math] can be described in terms of the graph [math]\displaystyle{ \textstyle \Upsilon_n }[/math]:

• Given any path [math]\displaystyle{ \textstyle (x_0, x_1, \ldots) }[/math] in [math]\displaystyle{ \textstyle \Gamma_{\mathrm e}(V) }[/math], one can find a path [math]\displaystyle{ \textstyle (A_0, A_1, \ldots) }[/math] in [math]\displaystyle{ \textstyle \Upsilon_n }[/math] such that [math]\displaystyle{ \textstyle x_k = A_k (e) }[/math], where [math]\displaystyle{ \textstyle e }[/math] is the vector [math]\displaystyle{ \textstyle (1, \ldots, 1) \in \mathbb{R}^n }[/math].
• Given any path [math]\displaystyle{ \textstyle (\sigma_0, \sigma_1, \ldots) }[/math] in [math]\displaystyle{ \textstyle \Gamma_{\mathrm f}(V) }[/math], one can find a path [math]\displaystyle{ \textstyle (A_0, A_1, \ldots) }[/math] in [math]\displaystyle{ \textstyle \Upsilon_n }[/math] such that [math]\displaystyle{ \textstyle \sigma_k = A_k (\Delta) }[/math], where [math]\displaystyle{ \textstyle \Delta }[/math] is the [math]\displaystyle{ \textstyle (n-1) }[/math]-dimensional standard simplex in [math]\displaystyle{ \textstyle \mathbb{R}^n }[/math].

Generalization of Lagrange's theorem

Lagrange proved that for an irrational real number [math]\displaystyle{ \textstyle \alpha }[/math], the continued-fraction expansion of [math]\displaystyle{ \textstyle \alpha }[/math] is periodic if and only if [math]\displaystyle{ \textstyle \alpha }[/math] is a quadratic irrational. Klein polyhedra allow us to generalize this result.

Let [math]\displaystyle{ \textstyle K \subseteq \mathbb{R} }[/math] be a totally real algebraic number field of degree [math]\displaystyle{ \textstyle n }[/math], and let [math]\displaystyle{ \textstyle \alpha_i : K \to \mathbb{R} }[/math] be the [math]\displaystyle{ \textstyle n }[/math] real embeddings of [math]\displaystyle{ \textstyle K }[/math]. The simplicial cone [math]\displaystyle{ \textstyle C }[/math] is said to be split over [math]\displaystyle{ \textstyle K }[/math] if [math]\displaystyle{ \textstyle C = \{ x \in \mathbb{R}^n : (\forall i) \; \alpha_i(\omega_1) x_1 + \ldots + \alpha_i(\omega_n) x_n \geq 0 \} }[/math] where [math]\displaystyle{ \textstyle \omega_1, \ldots, \omega_n }[/math] is a basis for [math]\displaystyle{ \textstyle K }[/math] over [math]\displaystyle{ \textstyle \mathbb{Q} }[/math].

Given a path [math]\displaystyle{ \textstyle (A_0, A_1, \ldots) }[/math] in [math]\displaystyle{ \textstyle \Upsilon_n }[/math], let [math]\displaystyle{ \textstyle R_k = A_{k+1} A_k^{-1} }[/math]. The path is called periodic, with period [math]\displaystyle{ \textstyle m }[/math], if [math]\displaystyle{ \textstyle R_{k+qm} = R_k }[/math] for all [math]\displaystyle{ \textstyle k, q \geq 0 }[/math]. The period matrix of such a path is defined to be [math]\displaystyle{ \textstyle A_m A_0^{-1} }[/math]. A path in [math]\displaystyle{ \textstyle \Gamma_{\mathrm e}(V) }[/math] or [math]\displaystyle{ \textstyle \Gamma_{\mathrm f}(V) }[/math] associated with such a path is also said to be periodic, with the same period matrix.

The generalized Lagrange theorem states that for an irrational simplicial cone [math]\displaystyle{ \textstyle C \subseteq \mathbb{R}^n }[/math], with generators [math]\displaystyle{ \textstyle (a_i) }[/math] and [math]\displaystyle{ \textstyle (w_i) }[/math] as above and with sail [math]\displaystyle{ \textstyle V }[/math], the following three conditions are equivalent:

• [math]\displaystyle{ \textstyle C }[/math] is split over some totally real algebraic number field of degree [math]\displaystyle{ \textstyle n }[/math].
• For each of the [math]\displaystyle{ \textstyle a_i }[/math] there is periodic path of vertices [math]\displaystyle{ \textstyle x_0, x_1, \ldots }[/math] in [math]\displaystyle{ \textstyle \Gamma_{\mathrm e}(V) }[/math] such that the [math]\displaystyle{ \textstyle x_k }[/math] asymptotically approach the line [math]\displaystyle{ \textstyle D(a_i) }[/math]; and the period matrices of these paths all commute.
• For each of the [math]\displaystyle{ \textstyle w_i }[/math] there is periodic path of chambers [math]\displaystyle{ \textstyle \sigma_0, \sigma_1, \ldots }[/math] in [math]\displaystyle{ \textstyle \Gamma_{\mathrm f}(V) }[/math] such that the [math]\displaystyle{ \textstyle \sigma_k }[/math] asymptotically approach the hyperplane [math]\displaystyle{ \textstyle H(w_i) }[/math]; and the period matrices of these paths all commute.

Example

Take [math]\displaystyle{ \textstyle n = 2 }[/math] and [math]\displaystyle{ \textstyle K = \mathbb{Q}(\sqrt{2}) }[/math]. Then the simplicial cone [math]\displaystyle{ \textstyle \{(x,y) : x \geq 0, \vert y \vert \leq x / \sqrt{2}\} }[/math] is split over [math]\displaystyle{ \textstyle K }[/math]. The vertices of the sail are the points [math]\displaystyle{ \textstyle (p_k, \pm q_k) }[/math] corresponding to the even convergents [math]\displaystyle{ \textstyle p_k / q_k }[/math] of the continued fraction for [math]\displaystyle{ \textstyle \sqrt{2} }[/math]. The path of vertices [math]\displaystyle{ \textstyle (x_k) }[/math] in the positive quadrant starting at [math]\displaystyle{ \textstyle (1, 0) }[/math] and proceeding in a positive direction is [math]\displaystyle{ \textstyle ((1,0), (3,2), (17,12), (99,70), \ldots) }[/math]. Let [math]\displaystyle{ \textstyle \sigma_k }[/math] be the line segment joining [math]\displaystyle{ \textstyle x_k }[/math] to [math]\displaystyle{ \textstyle x_{k+1} }[/math]. Write [math]\displaystyle{ \textstyle \bar{x}_k }[/math] and [math]\displaystyle{ \textstyle \bar{\sigma}_k }[/math] for the reflections of [math]\displaystyle{ \textstyle x_k }[/math] and [math]\displaystyle{ \textstyle \sigma_k }[/math] in the [math]\displaystyle{ \textstyle x }[/math]-axis. Let [math]\displaystyle{ \textstyle T = \left( \begin{array}{cc} 3 & 4 \\ 2 & 3 \end{array} \right) }[/math], so that [math]\displaystyle{ \textstyle x_{k+1} = T x_k }[/math], and let [math]\displaystyle{ \textstyle R = \left( \begin{array}{cc} 6 & 1 \\ -1 & 0 \end{array} \right) = \left( \begin{array}{cc} 1 & 6 \\ 0 & -1 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right) }[/math].

Let [math]\displaystyle{ \textstyle M_{\mathrm e} = \left( \begin{array}{cc} \frac12 & \frac12 \\ \frac14 & -\frac14 \end{array} \right) }[/math], [math]\displaystyle{ \textstyle \bar{M}_{\mathrm e} = \left( \begin{array}{cc} \frac12 & \frac12 \\ -\frac14 & \frac14 \end{array} \right) }[/math], [math]\displaystyle{ \textstyle M_{\mathrm f} = \left( \begin{array}{cc} 3 & 1 \\ 2 & 0 \end{array} \right) }[/math], and [math]\displaystyle{ \textstyle \bar{M}_{\mathrm f} = \left( \begin{array}{cc} 3 & 1 \\ -2 & 0 \end{array} \right) }[/math].

• The paths [math]\displaystyle{ \textstyle (M_{\mathrm e} R^k) }[/math] and [math]\displaystyle{ \textstyle (\bar{M}_{\mathrm e} R^k) }[/math] are periodic (with period one) in [math]\displaystyle{ \textstyle \Upsilon_2 }[/math], with period matrices [math]\displaystyle{ \textstyle M_{\mathrm e} R M_{\mathrm e}^{-1} = T }[/math] and [math]\displaystyle{ \textstyle \bar{M}_{\mathrm e} R \bar{M}_{\mathrm e}^{-1} = T^{-1} }[/math]. We have [math]\displaystyle{ \textstyle x_k = M_{\mathrm e} R^k (e) }[/math] and [math]\displaystyle{ \textstyle \bar{x}_k = \bar{M}_{\mathrm e} R^k (e) }[/math].
• The paths [math]\displaystyle{ \textstyle (M_{\mathrm f} R^k) }[/math] and [math]\displaystyle{ \textstyle (\bar{M}_{\mathrm f} R^k) }[/math] are periodic (with period one) in [math]\displaystyle{ \textstyle \Upsilon_2 }[/math], with period matrices [math]\displaystyle{ \textstyle M_{\mathrm f} R M_{\mathrm f}^{-1} = T }[/math] and [math]\displaystyle{ \textstyle \bar{M}_{\mathrm f} R \bar{M}_{\mathrm f}^{-1} = T^{-1} }[/math]. We have [math]\displaystyle{ \textstyle \sigma_k = M_{\mathrm f} R^k (\Delta) }[/math] and [math]\displaystyle{ \textstyle \bar{\sigma}_k = \bar{M}_{\mathrm f} R^k (\Delta) }[/math].

Generalization of approximability

A real number [math]\displaystyle{ \textstyle \alpha \gt 0 }[/math] is called badly approximable if [math]\displaystyle{ \textstyle \{ q (p \alpha - q) : p,q \in \mathbb{Z}, q \gt 0\} }[/math] is bounded away from zero. An irrational number is badly approximable if and only if the partial quotients of its continued fraction are bounded. This fact admits of a generalization in terms of Klein polyhedra.

Given a simplicial cone [math]\displaystyle{ \textstyle C = \{ x : (\forall i) \; \langle w_i, x \rangle \geq 0\} }[/math] in [math]\displaystyle{ \textstyle \mathbb{R}^n }[/math], where [math]\displaystyle{ \textstyle \langle w_i, w_i \rangle = 1 }[/math], define the norm minimum of [math]\displaystyle{ \textstyle C }[/math] as [math]\displaystyle{ \textstyle N(C) = \inf \{ \prod_i \langle w_i, x \rangle : x \in \mathbb{Z}^n \cap C \setminus \{0\} \} }[/math].

Given vectors [math]\displaystyle{ \textstyle \mathbf{v}_1, \ldots, \mathbf{v}_m \in \mathbb{Z}^n }[/math], let [math]\displaystyle{ \textstyle [\mathbf{v}_1, \ldots, \mathbf{v}_m] = \sum_{i_1 \lt \cdots \lt i_n} \vert \det(\mathbf{v}_{i_1} \cdots \mathbf{v}_{i_n}) \vert }[/math]. This is the Euclidean volume of [math]\displaystyle{ \textstyle \{ \sum_i \lambda_i \mathbf{v}_i : (\forall i) \; 0 \leq \lambda_i \leq 1 \} }[/math].

Let [math]\displaystyle{ \textstyle V }[/math] be the sail of an irrational simplicial cone [math]\displaystyle{ \textstyle C }[/math].

• For a vertex [math]\displaystyle{ \textstyle x }[/math] of [math]\displaystyle{ \textstyle \Gamma_{\mathrm e}(V) }[/math], define [math]\displaystyle{ \textstyle [x] = [\mathbf{v}_1, \ldots, \mathbf{v}_m] }[/math] where [math]\displaystyle{ \textstyle \mathbf{v}_1, \ldots, \mathbf{v}_m }[/math] are primitive vectors in [math]\displaystyle{ \textstyle \mathbb{Z}^n }[/math] generating the edges emanating from [math]\displaystyle{ \textstyle x }[/math].
• For a vertex [math]\displaystyle{ \textstyle \sigma }[/math] of [math]\displaystyle{ \textstyle \Gamma_{\mathrm f}(V) }[/math], define [math]\displaystyle{ \textstyle [\sigma] = [\mathbf{v}_1, \ldots, \mathbf{v}_m] }[/math] where [math]\displaystyle{ \textstyle \mathbf{v}_1, \ldots, \mathbf{v}_m }[/math] are the extreme points of [math]\displaystyle{ \textstyle \sigma }[/math].

Then [math]\displaystyle{ \textstyle N(C) \gt 0 }[/math] if and only if [math]\displaystyle{ \textstyle \{ [x] : x \in \Gamma_{\mathrm e}(V) \} }[/math] and [math]\displaystyle{ \textstyle \{ [\sigma] : \sigma \in \Gamma_{\mathrm f}(V) \} }[/math] are both bounded.

The quantities [math]\displaystyle{ \textstyle [x] }[/math] and [math]\displaystyle{ \textstyle [\sigma] }[/math] are called determinants. In two dimensions, with the cone generated by [math]\displaystyle{ \textstyle \{(1, \alpha), (1,0)\} }[/math], they are just the partial quotients of the continued fraction of [math]\displaystyle{ \textstyle \alpha }[/math].

See also

• Building (mathematics)

References

• O. N. German, 2007, "Klein polyhedra and lattices with positive norm minima". Journal de théorie des nombres de Bordeaux 19: 175–190.
• E. I. Korkina, 1995, "Two-dimensional continued fractions. The simplest examples". Proc. Steklov Institute of Mathematics 209: 124–144.
• G. Lachaud, 1998, "Sails and Klein polyhedra" in Contemporary Mathematics 210. American Mathematical Society: 373–385.