Klein polyhedron

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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

Relation to continued fractions[edit]

Suppose \textstyle \alpha > 0 is an irrational number. In \textstyle \mathbb{R}^2, the cones generated by \textstyle \{(1, \alpha), (1, 0)\} and by \textstyle \{(1, \alpha), (0, 1)\} 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 \textstyle \mathbb{Z}^n. Then the integer lengths of the edges of these two Klein polyhedra encode the continued-fraction expansion of \textstyle \alpha, one matching the even terms and the other matching the odd terms.

Graphs associated with the Klein polyhedron[edit]

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

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

The boundary \textstyle V of a Klein polyhedron is called a sail. Associated with the sail \textstyle V of an irrational cone are two graphs:

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

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

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)

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

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

Generalization of Lagrange's theorem[edit]

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

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

Given a path \textstyle (A_0, A_1, \ldots) in \textstyle \Upsilon_n, let \textstyle R_k = A_{k+1} A_k^{-1}. The path is called periodic, with period \textstyle m, if \textstyle R_{k+qm} = R_k for all \textstyle k, q \geq 0. The period matrix of such a path is defined to be \textstyle A_m A_0^{-1}. A path in \textstyle \Gamma_{\mathrm e}(V) or \textstyle \Gamma_{\mathrm f}(V) 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 \textstyle C \subseteq \mathbb{R}^n, with generators \textstyle (a_i) and \textstyle (w_i) as above and with sail \textstyle V, the following three conditions are equivalent:

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

Example[edit]

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

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

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

Generalization of approximability[edit]

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

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

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

Let \textstyle V be the sail of an irrational simplicial cone \textstyle C.

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

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

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

See also[edit]

References[edit]

  1. ^ Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics 193. Cambridge: Cambridge University Press. p. 245. ISBN 978-0-521-11169-0. Zbl pre06066616. 
  • 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.