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