Klein polyhedron

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

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

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

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