Klein polyhedron

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

Relation to continued fractions

The Klein continued fraction for $\alpha =\phi$ (Golden Ratio) with the Klein polyhedra encoding the odd terms in blue and the Klein polyhedra encoding the even terms in red.

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

Graphs associated with the Klein polyhedron

Suppose $C$ is generated by a basis $(a_i)$ of ${ℝ}^n$ (so that $C=\{{\sum }_i{\lambda }_i{a}_i:(\mathrm{\forall }i){\lambda }_i\ge 0\}$), and let $(w_i)$ be the dual basis (so that $C=\{x:(\mathrm{\forall }i)⟨w_i,x⟩\ge 0\}$). Write $D(x)$ for the line generated by the vector $x$, and $H(x)$ for the hyperplane orthogonal to $x$.

Call the vector $x\in {ℝ}^n$ irrational if $H(x)\cap {\mathbb{Q}}^n=\{0\}$; and call the cone $C$ irrational if all the vectors $a_i$ and $w_i$ are irrational.

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

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

Both of these graphs are structurally related to the directed graph ${\mathrm{{\rm Y}}}_n$ whose set of vertices is ${\mathrm{G}\mathrm{L}}_n(\mathbb{Q})$, where vertex $A$ is joined to vertex $B$ if and only if $A^{-1}B$ is of the form $UW$ where

$U=\left(\begin{array}{cccc}1& \cdots & 0& c_1\\ ⋮& \ddots & ⋮& ⋮\\ 0& \cdots & 1& c_{n-1}\\ 0& \cdots & 0& c_n\end{array}\right)$

(with $c_i\in \mathbb{Q}$, $c_n\ne 0$) and $W$ is a permutation matrix. Assuming that $V$ has been triangulated, the vertices of each of the graphs ${\mathrm{\Gamma }}_{\mathrm{e}}(V)$ and ${\mathrm{\Gamma }}_{\mathrm{f}}(V)$ can be described in terms of the graph ${\mathrm{{\rm Y}}}_n$:

• Given any path $(x_0,x_1,\dots )$ in ${\mathrm{\Gamma }}_{\mathrm{e}}(V)$, one can find a path $(A_0,A_1,\dots )$ in ${\mathrm{{\rm Y}}}_n$ such that $x_k=A_k(e)$, where $e$ is the vector $(1,\dots ,1)\in {ℝ}^n$.
• Given any path $({\sigma }_0,{\sigma }_1,\dots )$ in ${\mathrm{\Gamma }}_{\mathrm{f}}(V)$, one can find a path $(A_0,A_1,\dots )$ in ${\mathrm{{\rm Y}}}_n$ such that ${\sigma }_k=A_k(\mathrm{\Delta })$, where $\mathrm{\Delta }$ is the $(n-1)$-dimensional standard simplex in ${ℝ}^n$.

Generalization of Lagrange's theorem

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

Let $K\subseteq ℝ$ be a totally real algebraic number field of degree $n$, and let ${\alpha }_i:K\to ℝ$ be the $n$ real embeddings of $K$. The simplicial cone $C$ is said to be split over $K$ if $C=\{x\in {ℝ}^n:(\mathrm{\forall }i){\alpha }_i({\omega }_1)x_1+\dots +{\alpha }_i({\omega }_n)x_n\ge 0\}$ where ${\omega }_1,\dots ,{\omega }_n$ is a basis for $K$ over $\mathbb{Q}$.

Given a path $(A_0,A_1,\dots )$ in ${\mathrm{{\rm Y}}}_n$, let $R_k=A_{k+1}{A}_k^{-1}$. The path is called periodic, with period $m$, if $R_{k+qm}=R_k$ for all $k,q\ge 0$. The period matrix of such a path is defined to be $A_m{A}_0^{-1}$. A path in ${\mathrm{\Gamma }}_{\mathrm{e}}(V)$ or ${\mathrm{\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 $C\subseteq {ℝ}^n$, with generators $(a_i)$ and $(w_i)$ as above and with sail $V$, the following three conditions are equivalent:

• $C$ is split over some totally real algebraic number field of degree $n$.
• For each of the $a_i$ there is periodic path of vertices $x_0,x_1,\dots$ in ${\mathrm{\Gamma }}_{\mathrm{e}}(V)$ such that the $x_k$ asymptotically approach the line $D(a_i)$; and the period matrices of these paths all commute.
• For each of the $w_i$ there is periodic path of chambers ${\sigma }_0,{\sigma }_1,\dots$ in ${\mathrm{\Gamma }}_{\mathrm{f}}(V)$ such that the ${\sigma }_k$ asymptotically approach the hyperplane $H(w_i)$; and the period matrices of these paths all commute.

Example

Take $n=2$ and $K=\mathbb{Q}(\sqrt{2})$. Then the simplicial cone $\{(x,y):x\ge 0,|y|\le x/\sqrt{2}\}$ is split over $K$. The vertices of the sail are the points $(p_k,\pm q_k)$ corresponding to the even convergents $p_k/q_k$ of the continued fraction for $\sqrt{2}$. The path of vertices $(x_k)$ in the positive quadrant starting at $(1,0)$ and proceeding in a positive direction is $((1,0),(3,2),(17,12),(99,70),\dots )$. Let ${\sigma }_k$ be the line segment joining $x_k$ to $x_{k+1}$. Write ${\overline{x}}_k$ and ${\overline{\sigma }}_k$ for the reflections of $x_k$ and ${\sigma }_k$ in the $x$-axis. Let $T=\left(\begin{array}{cc}3& 4\\ 2& 3\end{array}\right)$, so that $x_{k+1}=T{x}_k$, and let $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 $M_{\mathrm{e}}=\left(\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ \frac{1}{4}& -\frac{1}{4}\end{array}\right)$, ${\overline{M}}_{\mathrm{e}}=\left(\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ -\frac{1}{4}& \frac{1}{4}\end{array}\right)$, $M_{\mathrm{f}}=\left(\begin{array}{cc}3& 1\\ 2& 0\end{array}\right)$, and ${\overline{M}}_{\mathrm{f}}=\left(\begin{array}{cc}3& 1\\ -2& 0\end{array}\right)$.

• The paths $(M_{\mathrm{e}}{R}^k)$ and $({\overline{M}}_{\mathrm{e}}{R}^k)$ are periodic (with period one) in ${\mathrm{{\rm Y}}}_2$, with period matrices $M_{\mathrm{e}}R{M}_{\mathrm{e}}^{-1}=T$ and ${\overline{M}}_{\mathrm{e}}R{\overline{M}}_{\mathrm{e}}^{-1}=T^{-1}$. We have $x_k=M_{\mathrm{e}}{R}^k(e)$ and ${\overline{x}}_k={\overline{M}}_{\mathrm{e}}{R}^k(e)$.
• The paths $(M_{\mathrm{f}}{R}^k)$ and $({\overline{M}}_{\mathrm{f}}{R}^k)$ are periodic (with period one) in ${\mathrm{{\rm Y}}}_2$, with period matrices $M_{\mathrm{f}}R{M}_{\mathrm{f}}^{-1}=T$ and ${\overline{M}}_{\mathrm{f}}R{\overline{M}}_{\mathrm{f}}^{-1}=T^{-1}$. We have ${\sigma }_k=M_{\mathrm{f}}{R}^k(\mathrm{\Delta })$ and ${\overline{\sigma }}_k={\overline{M}}_{\mathrm{f}}{R}^k(\mathrm{\Delta })$.

Generalization of approximability

A real number $\alpha >0$ is called badly approximable if $\{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 $C=\{x:(\mathrm{\forall }i)⟨w_i,x⟩\ge 0\}$ in ${ℝ}^n$, where $⟨w_i,w_i⟩=1$, define the norm minimum of $C$ as $N(C)=inf\{{\prod }_i⟨w_i,x⟩:x\in {\mathbb{Z}}^n\cap C\setminus \{0\}\}$.

Given vectors ${𝐯}_1,\dots ,{𝐯}_m\in {\mathbb{Z}}^n$, let $[{𝐯}_1,\dots ,{𝐯}_m]={\sum }_{i_1<\cdots <i_n}|det({𝐯}_{i_1}\cdots {𝐯}_{i_n})|$. This is the Euclidean volume of $\{{\sum }_i{\lambda }_i{𝐯}_i:(\mathrm{\forall }i)0\le {\lambda }_i\le 1\}$.

Let $V$ be the sail of an irrational simplicial cone $C$.

• For a vertex $x$ of ${\mathrm{\Gamma }}_{\mathrm{e}}(V)$, define $[x]=[{𝐯}_1,\dots ,{𝐯}_m]$ where ${𝐯}_1,\dots ,{𝐯}_m$ are primitive vectors in ${\mathbb{Z}}^n$ generating the edges emanating from $x$.
• For a vertex $\sigma$ of ${\mathrm{\Gamma }}_{\mathrm{f}}(V)$, define $[\sigma ]=[{𝐯}_1,\dots ,{𝐯}_m]$ where ${𝐯}_1,\dots ,{𝐯}_m$ are the extreme points of $\sigma$.

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

The quantities $[x]$ and $[\sigma ]$ are called determinants. In two dimensions, with the cone generated by $\{(1,\alpha ),(1,0)\}$, they are just the partial quotients of the continued fraction of $\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.