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 ${\displaystyle \textstyle C}$ be a closed simplicial cone in Euclidean space ${\displaystyle \textstyle \mathbb {R} ^{n))$. The Klein polyhedron of ${\displaystyle \textstyle C}$ is the convex hull of the non-zero points of ${\displaystyle \textstyle C\cap \mathbb {Z} ^{n))$.

Relation to continued fractions

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

Graphs associated with the Klein polyhedron

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

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

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

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

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

${\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)}$

(with ${\displaystyle \textstyle c_{i}\in \mathbb {Q} }$, ${\displaystyle \textstyle c_{n}\neq 0}$) and ${\displaystyle \textstyle W}$ is a permutation matrix. Assuming that ${\displaystyle \textstyle V}$ has been triangulated, the vertices of each of the graphs ${\displaystyle \textstyle \Gamma _{\mathrm {e} }(V)}$ and ${\displaystyle \textstyle \Gamma _{\mathrm {f} }(V)}$ can be described in terms of the graph ${\displaystyle \textstyle \Upsilon _{n))$:

• Given any path ${\displaystyle \textstyle (x_{0},x_{1},\ldots )}$ in ${\displaystyle \textstyle \Gamma _{\mathrm {e} }(V)}$, one can find a path ${\displaystyle \textstyle (A_{0},A_{1},\ldots )}$ in ${\displaystyle \textstyle \Upsilon _{n))$ such that ${\displaystyle \textstyle x_{k}=A_{k}(e)}$, where ${\displaystyle \textstyle e}$ is the vector ${\displaystyle \textstyle (1,\ldots ,1)\in \mathbb {R} ^{n))$.
• Given any path ${\displaystyle \textstyle (\sigma _{0},\sigma _{1},\ldots )}$ in ${\displaystyle \textstyle \Gamma _{\mathrm {f} }(V)}$, one can find a path ${\displaystyle \textstyle (A_{0},A_{1},\ldots )}$ in ${\displaystyle \textstyle \Upsilon _{n))$ such that ${\displaystyle \textstyle \sigma _{k}=A_{k}(\Delta )}$, where ${\displaystyle \textstyle \Delta }$ is the ${\displaystyle \textstyle (n-1)}$-dimensional standard simplex in ${\displaystyle \textstyle \mathbb {R} ^{n))$.

Generalization of Lagrange's theorem

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

Let ${\displaystyle \textstyle K\subseteq \mathbb {R} }$ be a totally real algebraic number field of degree ${\displaystyle \textstyle n}$, and let ${\displaystyle \textstyle \alpha _{i}:K\to \mathbb {R} }$ be the ${\displaystyle \textstyle n}$ real embeddings of ${\displaystyle \textstyle K}$. The simplicial cone ${\displaystyle \textstyle C}$ is said to be split over ${\displaystyle \textstyle K}$ if ${\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\))$ where ${\displaystyle \textstyle \omega _{1},\ldots ,\omega _{n))$ is a basis for ${\displaystyle \textstyle K}$ over ${\displaystyle \textstyle \mathbb {Q} }$.

Given a path ${\displaystyle \textstyle (A_{0},A_{1},\ldots )}$ in ${\displaystyle \textstyle \Upsilon _{n))$, let ${\displaystyle \textstyle R_{k}=A_{k+1}A_{k}^{-1))$. The path is called periodic, with period ${\displaystyle \textstyle m}$, if ${\displaystyle \textstyle R_{k+qm}=R_{k))$ for all ${\displaystyle \textstyle k,q\geq 0}$. The period matrix of such a path is defined to be ${\displaystyle \textstyle A_{m}A_{0}^{-1))$. A path in ${\displaystyle \textstyle \Gamma _{\mathrm {e} }(V)}$ or ${\displaystyle \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 ${\displaystyle \textstyle C\subseteq \mathbb {R} ^{n))$, with generators ${\displaystyle \textstyle (a_{i})}$ and ${\displaystyle \textstyle (w_{i})}$ as above and with sail ${\displaystyle \textstyle V}$, the following three conditions are equivalent:

• ${\displaystyle \textstyle C}$ is split over some totally real algebraic number field of degree ${\displaystyle \textstyle n}$.
• For each of the ${\displaystyle \textstyle a_{i))$ there is periodic path of vertices ${\displaystyle \textstyle x_{0},x_{1},\ldots }$ in ${\displaystyle \textstyle \Gamma _{\mathrm {e} }(V)}$ such that the ${\displaystyle \textstyle x_{k))$ asymptotically approach the line ${\displaystyle \textstyle D(a_{i})}$; and the period matrices of these paths all commute.
• For each of the ${\displaystyle \textstyle w_{i))$ there is periodic path of chambers ${\displaystyle \textstyle \sigma _{0},\sigma _{1},\ldots }$ in ${\displaystyle \textstyle \Gamma _{\mathrm {f} }(V)}$ such that the ${\displaystyle \textstyle \sigma _{k))$ asymptotically approach the hyperplane ${\displaystyle \textstyle H(w_{i})}$; and the period matrices of these paths all commute.

Example

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

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

• The paths ${\displaystyle \textstyle (M_{\mathrm {e} }R^{k})}$ and ${\displaystyle \textstyle ({\bar {M))_{\mathrm {e} }R^{k})}$ are periodic (with period one) in ${\displaystyle \textstyle \Upsilon _{2))$, with period matrices ${\displaystyle \textstyle M_{\mathrm {e} }RM_{\mathrm {e} }^{-1}=T}$ and ${\displaystyle \textstyle {\bar {M))_{\mathrm {e} }R{\bar {M))_{\mathrm {e} }^{-1}=T^{-1))$. We have ${\displaystyle \textstyle x_{k}=M_{\mathrm {e} }R^{k}(e)}$ and ${\displaystyle \textstyle {\bar {x))_{k}={\bar {M))_{\mathrm {e} }R^{k}(e)}$.
• The paths ${\displaystyle \textstyle (M_{\mathrm {f} }R^{k})}$ and ${\displaystyle \textstyle ({\bar {M))_{\mathrm {f} }R^{k})}$ are periodic (with period one) in ${\displaystyle \textstyle \Upsilon _{2))$, with period matrices ${\displaystyle \textstyle M_{\mathrm {f} }RM_{\mathrm {f} }^{-1}=T}$ and ${\displaystyle \textstyle {\bar {M))_{\mathrm {f} }R{\bar {M))_{\mathrm {f} }^{-1}=T^{-1))$. We have ${\displaystyle \textstyle \sigma _{k}=M_{\mathrm {f} }R^{k}(\Delta )}$ and ${\displaystyle \textstyle {\bar {\sigma ))_{k}={\bar {M))_{\mathrm {f} }R^{k}(\Delta )}$.

Generalization of approximability

A real number ${\displaystyle \textstyle \alpha >0}$ is called badly approximable if ${\displaystyle \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 ${\displaystyle \textstyle C=\{x:(\forall i)\;\langle w_{i},x\rangle \geq 0\))$ in ${\displaystyle \textstyle \mathbb {R} ^{n))$, where ${\displaystyle \textstyle \langle w_{i},w_{i}\rangle =1}$, define the norm minimum of ${\displaystyle \textstyle C}$ as ${\displaystyle \textstyle N(C)=\inf\{\prod _{i}\langle w_{i},x\rangle :x\in \mathbb {Z} ^{n}\cap C\setminus \{0\}\))$.

Given vectors ${\displaystyle \textstyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{m}\in \mathbb {Z} ^{n))$, let ${\displaystyle \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 ${\displaystyle \textstyle \{\sum _{i}\lambda _{i}\mathbf {v} _{i}:(\forall i)\;0\leq \lambda _{i}\leq 1\))$.

Let ${\displaystyle \textstyle V}$ be the sail of an irrational simplicial cone ${\displaystyle \textstyle C}$.

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

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

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