Klein polyhedron

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

Definition

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

The Klein continued fraction for

\textstyle \alpha =\varphi

(Golden Ratio) with the Klein polyhedra encoding the odd terms in blue and the Klein polyhedra encoding the even terms in red.

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} ^{2}.$ 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

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

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

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}=Tx_{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}{\frac {1}{2}}&{\frac {1}{2}}\\{\frac {1}{4}}&-{\frac {1}{4}}\end{array}}\right)$ , $\textstyle {\bar {M}}_{\mathrm {e} }=\left({\begin{array}{cc}{\frac {1}{2}}&{\frac {1}{2}}\\-{\frac {1}{4}}&{\frac {1}{4}}\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} }RM_{\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} }RM_{\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

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$ .

References

^ Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics. Vol. 193. Cambridge: Cambridge University Press. p. 245. ISBN 978-0-521-11169-0. Zbl 1260.11001.

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.

[Bug245-1] Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics. Vol. 193. Cambridge: Cambridge University Press. p. 245. ISBN 978-0-521-11169-0. Zbl 1260.11001.

[1]