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

See also

• Building (mathematics)

References

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