non-cox_e.tex
\documentclass{article}
\usepackage{latexsym,amsthm,amsfonts,epsfig,psfrag }
\topmargin = 30pt
%\headheight = 0.0 in
%\headsep = 0.0 in
%\textheight = 49\baselineskip
%\textwidth = 170 mm
%\topskip = 0.0 in
%\oddsidemargin = 0.0 in
%\footheight = 0.0 in
%\footskip = 4 ex
%\leftmargin = 0 mm


\begin{document}

\newtheorem{cor}{Corollary}%[theorem]
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{prop}{Proposition}
\renewcommand{\proofname}{Proof}

\def \Z{{\mathbb Z}}
\def \S{{\mathbb S}}
\def \H{{\mathbb H}}
\def \E{{\mathbb E}}

%\noindent
%��� 512.817.72+514.174.5


\begin{center}
{\Large \bf
Euclidean simplices generating \\
discrete reflection groups}

\vspace{7pt}
{\large A.~Felikson, P.~Tumarkin }
\end{center}


\section*{Introduction}

\noindent
%{\bf 1. }

Let $P$ be a convex polytope in  the spherical space $\S^n$,
in the Euclidean space $\E^n$, or in the hyperbolic space $\H^n$.
 Consider the group $G_P$ generated by
 reflections in the facets of $P$.
We call $G_P$  a {\it reflection group generated by $P$}.
The problem we consider in this paper
is to list polytopes generating discrete reflection groups.


The answer is known only for
some  combinatorial types of polytopes.
Already in 1873, Schwarz \cite{Shwarz}  listed spherical triangles
generating discrete groups.
In  1998, E.~Klimenko and M.~Sakuma \cite{Pink}
solved the problem
for hyperbolic triangles.
In \cite{polygons}, \cite{pyrprism}, \cite{simplex},
\cite{lambert} 
the problem was solved for hyperbolic quadrilaterals,
compact hyperbolic pyramids and triangular prisms, hyperbolic simplices,
and Lambert cubes in $\S^3$, $\E^3$, $\H^3$.
In~\cite{sph} the problem was solved for spherical simplices. 

\vspace{5pt}
\noindent

In this paper, we use the method of~\cite{sph} to classify Euclidean
simplices generating discrete reflection groups.

\vspace{5pt}
\noindent

The authors are grateful to the Max-Planck Institute for Mathematics
in Bonn for hospitality.


\vspace{20pt}



\section{Preliminaries}

A convex polytope in $\S^n$, $\E^n$ or $\H^n$ is called a 
{\it Coxeter polytope} if all its dihedral angles are  submultiples 
of $\pi$. The group $G_F$ generated by  reflections in the facets of 
any Coxeter polytope $F$ is discrete, and $F$ is a fundamental domain 
of $G_F$.

On the other hand, any discrete group $G$ generated by reflections 
coincides with $G_F$ for some Coxeter polytope $F$. If $G=G_P$ for 
some non-Coxeter polytope $P$, then $P$ consists of several copies of 
$F$, and any two copies containing a facet in common are 
symmetric to each other with respect to this facet.\\  

\noindent
{\bf Spherical reflection groups}.
Let  $G$ be a reflection group acting on $\S^n$. 
Suppose that $G$ acts on $\S^n$ discretely, i.e. $G$ is a finite 
group.
Then  $G$ is generated by reflections 
in the facets of some spherical Coxeter polytope. 
It is shown by H.~S.~M.~Coxeter \cite{Coxeter} that 
any spherical Coxeter polytope containing no pair of antipodal points
of $\S^n$ is a simplex. 

To describe Coxeter polytopes we  use {\it Coxeter diagrams}.
A Coxeter diagram of a Coxeter polytope $F$
is a graph whose nodes $v_i$ correspond to the facets $\Pi_i$ of $F$.
Nodes $v_i$ and $v_j$ are joined by a $(k-2)$-fold edge 
if the dihedral angle
formed up by $\Pi_i$ and $\Pi_j$ equals $\frac{\pi}{k}$
(if $\Pi_i$ is orthogonal to $\Pi_j$, $v_i$ and $v_j$ are disjoint).
Indecomposable spherical and Euclidean Coxeter simplices
were classified by Coxeter~\cite{Coxeter}. The list of their 
Coxeter diagrams is represented  in Table~\ref{cox}.
\\

%?????

%Any spherical indecomposable Coxeter simplex
%is one of the simplices   $A_n$, $B_n=C_n$, $D_n$,
%$E_6$, $E_7$, $E_8$, $F_4$, $H_3$, $H_4$ and $G_2^{(m)}$
%(a simplex is called indecomposable if it is not a direct product of
%some other simplices).

%?????

\noindent
{\bf Euclidean reflection groups}. 
Let  $G$ be a discrete reflection group acting on $\E^n$.
Let $F$ be a fundamental chamber of $G$.
As it is shown in~\cite{Coxeter}, $F$ is a direct product of several
simplices and simplicial cones. 

Suppose that $G$ is generated by a simplex (the simplex may
not be a Coxeter simplex). Then $G$ is an indecomposable group
and the fundamental chamber of $G$ is compact.
In this case the fundamental chamber of $G$ is one of the simplices 
 $\widetilde A_n$, $\widetilde B_n$, $\widetilde C_n$, $\widetilde D_n$,
$\widetilde E_6$, $\widetilde E_7$, $\widetilde E_8$, $\widetilde F_4$
and  $\widetilde G_2$ (see Table~\ref{cox}).


See~\cite{29}
for more information about discrete reflection groups.

We use the notation $A_n$, $\widetilde A_n$, $B_n$ and so on for Coxeter
simplices as well as for the groups generated by these simplices.
Finite root systems are denoted by $\mathrm A_n$,
$\mathrm B_n$ and so on. See~\cite{Kac} for background on root systems.    

Let $P$ be a simplex generating discrete reflection group
($P$ may not be a Coxeter simplex).
Clearly, in this case all the dihedral angles of $P$ are of the type $\frac{\pi m}{k}$.
Hence, for any simplex generating discrete reflection group
we can construct the following {\it generalized Coxeter diagram}:
the nodes $v_i$ of the diagram correspond to the facets $\Pi_i$ of $P$;
the nodes $v_i$ and $v_j$ are joined by a $(k-2)$-fold edge that is 
decomposed into $m$ parts
if the dihedral angle
formed up by $\Pi_i$ and $\Pi_j$ equals to $\frac{\pi m}{k}$.



\input{cox.txt}


\section{Families of simplices}

\noindent
{\bf Spherical simplices generating discrete reflection groups}.
Let $\E^{n}$ be the $n$-dimensional Euclidean  space,
and let $S^{n-1}$ be the unit sphere centered at the origin.
Any hyperplane of  $S^{n-1}$ is a section of $S^{n-1}$
by some  hyperplane of $\E^{n}$ containing the origin.
Hence, any $(n-1)$-dimensional simplex in  $S^{n-1}$ is an intersection 
of $S^{n-1}$ with an interior of some 
cone with $n$ facets in $\E^{n}$ centered at the origin. 

So, suppose that $P$ is a spherical $(n-1)$-dimensional simplex. 
Then we can define $P$ by unit outward normal vectors $f_1,...,f_n$ 
to the facets of the corresponding cone. 

Denote by $\Pi_1,...,\Pi_{n}$ the facets of $P$.
The hyperplanes containing $\Pi_1,...,\Pi_{n}$ decompose
 $S^{n-1}$ into $2^{n}$ simplices $P_1$, ..., $P_{2^n}$
encoded by $n$-tuples of vectors $\{\pm f_1,...,\pm f_{n}\}$. 
In this paper the set of simplices $P_1$,...,$P_{2^{n}}$
is called  a {\it family}.
Each of the simplices $P_1$,...,$P_{2^{n}}$ 
generates the same reflection group as $P$ does.
Thus, we can study the families instead of studying of simplices
 themselves. (In fact, any family contains at most $2^{n-1}$ simplices 
up to isometry: the simplex $\{f_1,...,f_{n}\}$ is always congruent to 
 $\{-f_1,...,-f_{n}\}$).


Let $P$ be a simplex generating a discrete reflection group $G_P$. 
Clearly, the dihedral angles of $P$ are rational 
numbers multiplied by $\pi$. Moreover, if $G$ is an indecomposable
spherical reflection group different from  $G_2^{(m)}$, $H_3$ and $H_4$, 
then any dihedral angle of $P$
is either $\frac{\pi}{k}$ or  $\frac{\pi(k-1)}{k}$, where $k=2,3$ or $4$ 
(cf. Table~\ref{cox}).

Analogously to Coxeter simplices, any simplex  
whose dihedral angles equal  either 
 $\frac{\pi}{k}$ or  $\frac{\pi(k-1)}{k}$
can be represented by the following {\it family diagram}:
the nodes $v_i$ correspond to the facets of $P$;
the nodes $v_i$ and $v_j$ are joined by a $(k-2)$-fold edge 
if the angle
formed up by $\Pi_i$ and $\Pi_j$ is either $\frac{\pi}{k}$
or  $\frac{\pi(k-1)}{k}$
(if $\Pi_i$ is orthogonal to $\Pi_j$, $v_i$ and $v_j$ are disjoint).

Note, that if $P$ is a Coxeter simplex then the  diagram corresponding
 to $P$ is a Coxeter diagram of $P$. 


Any two simplices in one family
have the same family diagram. 
So, we can assign to a family the diagram of any simplex contained 
in the family. We call this diagram a {\it family
diagram}. It is proved in~\cite{sph} (Lemma 2) that any graph having 
no edge of
multiplicity greater than two is a family diagram for at most one
family of simplices. The same statement for the dihedral group 
$G_2=G_2^{(6)}$ is evident.


\vspace{8pt}
\noindent
{\bf Euclidean simplices generating discrete reflection groups}.
Let $P$ be a simplex in $\E^n$
generating discrete reflection group $G_P$.
Let $\Pi_0,...,\Pi_{n}$ be the facets of $P$,
and $f_0,...,f_n$ be the outward unit normal vectors to 
$\Pi_0,...,\Pi_{n}$.
The hyperplanes containing $\Pi_0,...,\Pi_{n}$ decompose
$\E^{n}$ into $2^{n+1}-1$ domains $P_1$,...,$P_{2^{n+1}-1}$
encoded by the vectors $\{\pm f_0,...,\pm f_{n}\}$. 
All these domains except the initial simplex $P$ are non-compact.
Simplex $P$ is encoded by the vectors $\{f_0,..., f_{n}\}$.
Each  of the domains $P_i$ generates the same reflection group as $P$ does.

By a {\it family of Euclidean simplices} we call a set of simplices
having the same set of vectors $\{\pm f_0,...,\pm f_{n}\}$.
Note, that in the Euclidean case any two simplices contained in one
family are mutually similar (moreover, any two of these simplices are 
homothetic).

We classify Euclidean simplices generating discrete reflection
groups up to similarity.

Furthermore, note that any dihedral angle of $P$ is either
$\frac{\pi}{k}$ or  $\frac{\pi(k-1)}{k}$,
where $k=2,3,4$ or $6$ (see Table~\ref{cox}).
Hence, we can define {\it family diagrams} for Euclidean simplices 
in the same way as for  the spherical ones.

\begin{lemma}
\label{unique}
Let $\Phi$ and $\Psi$ be two different families of Euclidean simplices
generating discrete reflection groups. Then their family 
diagrams are distinct.

\end{lemma}

The proof of the lemma follows the proof of Lemma~2 from
paper~\cite{sph}. 

\section{Special vertices}
In this section we prove several auxiliary facts.


A hyperplane $\alpha$ is called a {\it mirror} of the group $G$  
if $G$ contains a reflection with respect to $\alpha$.

 
\begin{lemma}
\label{parallel}
Let $P$ be a simplex in $\E^n$ generating discrete reflection
group $G_P$.
Then no mirror of $G_P$ decomposing $P$ is
 parallel to a facet of $P$.
 
\end{lemma}

\begin{proof}
Let $\Pi_0,...,\Pi_n$ be the facets of $P$ and let $V_0$ be the vertex 
opposite to $\Pi_0$.
Suppose that there exists a mirror of $G_P$ that is parallel to $\Pi_0$ and
decomposes $P$. Since $G_P$ is discrete, there exist only finitely
many of such mirrors. Let $m$ be one of them closest to $V_0$.

Denote by $h$ the homothety with center $V_0$ taking  $\Pi_0$ to $m$.
Denote by $r_i$ the reflection with respect to $\Pi_i$ ($i=0,...,n$), 
and by $r$ the reflection with respect to $m$.
Since $r\in G_P$,  $r=r_{i_1}...r_{i_l}$ for some $l$.
From the other hand, $r=hr_0h^{-1}$.

Consider the reflection
$hrh^{-1}=(hr_{i_1}h^{-1})...(hr_{i_l}h^{-1})$.
Since $hr_{i}h^{-1}\in G_P$ for any $i=0,...,n$,  
we have $hrh^{-1}\in G_P$. Furthermore,  $hrh^{-1}$ is a reflection
with respect to some hyperplane $m'$ parallel to $m$.
Moreover, $m'$ decomposes $P$ and goes closer to $V_0$ than $m$. 
This contradicts to the choice of $m$.

\end{proof}


\begin{lemma}
\label{Fix}
Let $P$ be a simplex generating  discrete group $G_P$.
Let $V$ be a vertex of $P$ and  $\Pi_1,...,\Pi_n$ be the facets of
$P$ containing $V$.
Then the stabilizer $Fix(V,G_P)$ of $V$ in  $G_P$ coincides with
the group $G$
generated by the reflections with respect to $\Pi_1,...,\Pi_n$.
 
\end{lemma}

\begin{proof}

Suppose that the lemma is false. 
Then there exists a non-empty set $M$ of  simplices 
for which the statement of the lemma is broken.
We may assume that $P\in M$ is a simplex minimal by the inclusion.
Let $V$ be a vertex of $P$ for which the statement of the lemma is false.
Then among the dihedral angles formed up by $\Pi_1,...,\Pi_n$ 
 there exists a dihedral angle $\pi \frac{k}{m}$, where $1<k<m$
are mutually co-prime integers. Suppose that this angle is 
formed up by $\Pi_1$ and $\Pi_n$.

Consider a mirror $\Pi$ of $G$ such that $\Pi$ contains 
$\Pi_1\cap \Pi_n$, and
the angle formed up by $\Pi$ and $\Pi_1$ is equal to $\frac{\pi}{m}$.
This mirror decomposes $P$ into two simplices $P_1$ and $P_2$.
Let $P_1$ be the simplex having a facet $\Pi_1$. 
Denote by $G_{P_1}$ the group generated by $P_1$. Clearly, $G_{P_1}=G_P$.
Furthermore, the group generated by the reflections with respect to the
facets $\Pi,\Pi_1,...,\Pi_{n-1}$ coincides with 
the group generated by the reflections with respect to the
facets $\Pi_1,...,\Pi_n$. From the other hand, the stabilizer
 $Fix(V,G_{P_1})$ of $V$ in $G_{P_1}$ coincides with $Fix(V,G_{P})$.
By the assumption, $Fix(V,G_{P})$ does not coincide with the group generated by
the reflections with respect to $\Pi_1,...,\Pi_n$.
Hence,   $Fix(V,G_{P_1})$ differs from the group generated by the
reflections with respect to $\Pi,\Pi_1,...,\Pi_{n-1}$.
Thus, the statement of the lemma is broken for $P_1$.
This contradicts to the assumption that $P\in M$ is the minimal
simplex, and the lemma is proved.

\end{proof}

Let $P$ be any Euclidean polytope generating discrete reflection group. 
Suppose that
there exists a vertex $V$ of $P$ such that the stabilizer of
$V$ contains a linear part of any element of $G_P$.
We call such a vertex a {\it special vertex } of $P$.
It is known  (see~\cite{Kac}, Ch.~6) that any Euclidean Coxeter
simplex has at least one special vertex. 

\begin{lemma}
\label{spec}
Let $P$ be a simplex generating  discrete reflection group $G_P$. 
Then $P$ has at list one special vertex.

\end{lemma}

\begin{proof}
Let $F$ be a fundamental polytope of $G_P$ contained in $P$.
Since $G_P$ is indecomposable, $F$ is a simplex. Any fundamental
polytope of discrete reflection group is Coxeter polytope, thus $F$ is
a Coxeter simplex. Let $V$ be a special vertex of $F$.


Suppose that $F$ is either an inner point of $P$ or an inner point of
some face of $P$. Let $\Pi$ be any facet of $P$ not containing $V$.
Let $m$ be the mirror of $G_P$ parallel to $\Pi$ and containing $V$.
Then $m$ cuts $P$, that contradicts to Lemma~\ref{parallel}.

Thus, $V$ is a vertex of $P$. Let $\Pi_1,...,\Pi_n$ be the facets of $P$
containing $V$.  
By Lemma~\ref{Fix}, the reflections with respect to  $\Pi_1,...,\Pi_n$
generate the stabilizer $Fix(V,G_P)$ of $V$ in $G_P$.
Thus, $V$ is a special vertex of $P$.

\end{proof}

 




\section{Simplices generating given reflection group}
\label{algorithm}

Let $G$ be an indecomposable Euclidean reflection group.  
Let $P$ be a simplex generating $G$, and $f_0,f_1,...,f_n$ 
be the vectors orthogonal to the facets of $P$.
By Lemma~\ref{spec}, there exists a special vertex $V$ of $P$.
Let  $\Pi_0,...,\Pi_n$ be facets of $P$, such that $\Pi_i$ is orthogonal
 to $f_i$ for $i=0,\dots,n$. We may assume that $V$ is contained in  
$\Pi_1,...,\Pi_n$. 

The stabilizer $Fix(V,G)$ of $V$ in $G$ is a Weyl 
group of some finite root system $\Delta$. Suitably normalizing the 
vectors $f_0,f_1,...,f_n$,
we may assume that these vectors belong to $\Delta$. Since $V$ is a 
special vertex of $P$, there exists a mirror of $G$ through $V$ 
parallel to $\Pi_0$. By Lemma~\ref{Fix}, suitably normalizing $f_0$ 
we may assume that $f_0$ is contained in $\Delta$.    
Note, that $f_0,f_1,...,f_n$ are linearly dependent vectors,
however any $n$ of these vectors are linearly independent.


Now we are able to find all families of simplices generating 
given group $G$.

Let $F$ be a fundamental simplex of $G$,
and let $U$ be a special vertex of $F$.
Denote by $W$ the stabilizer $Fix(U,G)$, and let $\Delta$ be the 
corresponding root system.    
Let $v_0,...,v_n$ be any set containing $n+1$ vectors of
$\Delta$, such that any $n$ of these vectors are linearly independent.
Let  $\Pi_1,...,\Pi_n$ be the mirrors of $G$ containing $U$ and
orthogonal to $v_1,...,v_n$.
Let $\Pi_0$ be a mirror of $G$ closest to $U$, orthogonal to $v_0$ and
not containing  $U$.
Then the mirrors $\Pi_0,\Pi_1,...,\Pi_n$ are the facets of some 
simplex $P$
generating a finite index subgroup of $G$.
If, in addition, the reflections with respect to 
 $\Pi_1,...,\Pi_n$ generate $W$, 
then some simplex similar to $P$ generates $G$ 
(the only exception is the group $W=B_n=C_n$; in this case
we can obtain either $\widetilde B_n$ or $\widetilde C_n$
depending on the vector $v_0$, see Section~\ref{SectionBC}).

In other word, to classify families generating $G$ 
it is sufficient to follow the algorithm:

\begin{itemize}
\item[1)] Find all linearly independent systems
$f_1,...,f_n$ in $\Delta$, generating $W$
(we say that $f_1,...,f_n$ generate  $W$,
if the reflections with respect to the hyperplanes through the origin
orthogonal  to these vectors generate $W$).

\item[2)]
For each system $f_1,...,f_n$ obtained on the previous step, add a vector
$f_0\in \Delta$ in such a way that any $n$ of vectors 
 $f_0,f_1,...,f_n$ are linearly independent.
This vector $f_0$ should be chosen by all possible ways.

\item[3)] If $W=B_n=C_n$, examine which of the groups
$\widetilde B_n$ and  $\widetilde C_n$ is generated by
$f_0,f_1,...,f_n$. 

\item[4)] Among the obtained systems  
one should find the systems corresponding to different families,
i.e.  families having different family diagrams.

\end{itemize}

The order of vectors in the systems is not important for us.
The Weyl group acts on  $\E^n$,
hence, it acts on $(n+1)$-tuples of vectors.
We do not differ   $(n+1)$-tuples equivalent with respect to
this action. 

\subsection{Simplices generating $\widetilde A_n$}
\label{SecA}

Let $P$ be a simplex generating the group $\widetilde A_n$.
We may assume that the vectors $f_0,f_1,...,f_n$ belong to the root 
system 
$\mathrm A_n=\{\pm(h_i-h_j)\}, 0\le i<j\le n$, where
$h_0,...,h_n$ is a standard basis of $\E^{n+1}$).

For any simplex $P=\{f_0,f_1,...f_n\}$ generating $\widetilde A_n$
we construct the following {\it graph} $\,\Gamma(P)$:
the nodes $v_0,...,v_n$ of  $\Sigma$ correspond to the vectors 
$h_0,...h_n$; the nodes $v_i$ and $v_j$ are joined by an edge
if one of vectors $(h_i-h_j)$ and $-(h_i-h_j)$ belongs to the set 
$\{f_0,...,f_n\}$. 
Clearly, two simplices from one family have the same 
graph. 

\begin{theorem}
\label{sectionA}
There exists a unique family of simplices generating 
$\widetilde A_n$.
This  family consists of Coxeter simplices $\widetilde A_n$.
\end{theorem}


\begin{proof}
Let $P=\{f_0,f_1,...f_n\}$ be a simplex generating  $\widetilde A_n$
and  $\Gamma(P)$ be the corresponding graph.
Then $\Gamma(P)$ contains exactly $n+1$ nodes and the same number
of edges.
Since any $n$ vectors contained in the set  $\{f_0,...,f_n\}$ are
linearly independent, 
 $\Gamma(P)$ has no cycles containing less than $n+1$ nodes.
Hence,  $\Gamma(P)$ is a cycle with $n+1$ nodes.

Note, that the graph  $\Gamma(P)$ determines the family diagram 
of  $P$. In more details, the nodes of the family diagram
correspond to the edges of   
$\Gamma(P)$, two nodes are joined if the corresponding edges
of  $\Gamma(P)$  have a common node.
Hence, in case of $\widetilde A_n$ the family diagram is a cycle,
too. By Lemma~\ref{unique},   
the family of simplices is completely determined by a family diagram.
Thus, $P$ is a Coxeter simplex  $\widetilde A_n$.

\end{proof}




\subsection{Simplices generating $\widetilde B_n$ and $\widetilde C_n$} 
\label{SectionBC}

Let $P$ be a simplex generating the group $\widetilde B_n$ or 
$\widetilde C_n$.
We may assume that the vectors $f_0,f_1,...,f_n$ belong to the root 
system 
$\mathrm B_n=\{\pm h_i,\ \pm h_i \pm h_j\}, 1\le i<j\le n$, where
$h_1,...,h_n$ is a standard basis of $\E^{n}$).

For any simplex $P=\{f_0,f_1,...f_n\}$ generating $\widetilde B_n$ or 
$\widetilde C_n$ 
we construct the following {\it graph} $\,\Gamma(P)$:
the nodes $v_1,...,v_n$ of  $\Sigma$ correspond to the vectors 
$h_1,...h_n$; the nodes $v_i$ and $v_j$ are joined by an edge
if one of  vectors $\pm (h_i-h_j)$ and $\pm (h_i+h_j)$ belongs to 
the set 
$\{f_0,...,f_n\}$; the node $v_i$ is {\it marked} if   
$\{f_0,f_1,...,f_n\}$ contains  $\pm h_i$.
If $\{f_0,f_1,...,f_n\}$ contains both
 $\pm(h_i+h_j)$ and $\pm(h_i-h_j)$,   
the nodes $v_i$ and $v_j$ are joined by two edges. 

Since the system of vectors $f_0,f_1,...,f_n$  is indecomposable, 
 $\Gamma(P)$ is connected.
Clearly, $\Gamma(P)$ contains at least one marked node
(otherwise $f_i$ belongs to $\mathrm D_n$ for any $i$,
where  $\mathrm D_n$ is embedded in $\mathrm B_n$ 
as a set of long roots).

\begin{lemma}
\label{marked}
Let $P$ be a simplex generating $\widetilde B_n$ or 
$\widetilde C_n$. \\
1) If $\Gamma(P)$ contains more than one marked node 
then $P$ is a Coxeter simplex $\widetilde C_n$.\\
2) If $\Gamma(P)$ contains a unique
marked node then $\Gamma(P)$ is one of the  graphs shown in 
the left column of Table~\ref{beat}.

\end{lemma}

\begin{proof}
Suppose that $\Gamma(P)$ contains more than one marked node.
Then $\Gamma(P)$ contains a path from one marked node to another.
Consider such a path that does not intersect itself.
The vectors corresponding to the edges and marked nodes of this
path are linearly dependent. Hence, the path contains all edges of
 $\Gamma(P)$, and  $\Gamma(P)$ is the graph shown in
Fig.~\ref{Sigma(C_n)}.
In  this case $P=\widetilde C_n$. 

Now suppose that $\Gamma(P)$ contains a unique marked node.
Since the number of edges of $\Gamma(P)$ equals $n$
and the number of nodes equals $(n+1)-1=n$,  
$\Gamma(P)$ contains a unique cycle
(it may consist of two nodes).
Since any $n$ vectors are linearly independent, if the cycle contains
less than $n$ edges then it does not contain the marked node.
Hence, $\Gamma(P)$ have a subgraph shown in the left column of
Table~\ref{beat}.
From the other hand, this subgraph corresponds to linearly
dependent system of vectors.
Hence, this subgraph coincides with $\Gamma(P)$.

\end{proof}




\begin{figure}[!h]
\begin{center}
\epsfig{file=c_n.eps,width=0.4\linewidth}
\vspace{-10pt}
\end{center}
\caption{Graph $\Gamma(\widetilde C_n)$.}
\label{Sigma(C_n)}
\end{figure}






\begin{theorem}
\label{B}
There exists exactly $n-1$ families of simplices generating
the group $\widetilde B_n$. Family diagrams and  generalized 
Coxeter diagrams of these simplices are shown in Table~\ref{beat}.
 

\end{theorem}

\begin{proof}
By the second statement of Lemma~\ref{marked},
any simplex $P$ generating $\widetilde B_n$ 
corresponds to a graph $\Gamma(P)$ shown in the left column of
Table~\ref{beat}. 

Let us show that any graph $\Gamma$  shown in the left column of
Table~\ref{beat} corresponds to a simplex generating $\widetilde B_n$.
It is easy to see that any $n$ of vectors  $f_0,f_1,...,f_n$ 
are linearly independent and all these vectors are linearly dependent.
Hence,  $\Gamma$ corresponds to some simplex $P$ in $\E^n$.
The group generated by $P$ is a maximal rank indecomposable subgroup of
$\widetilde B_n$, and the fundamental simplex of this subgroup has a
dihedral angle equal to $\frac{\pi}{4}$. 
By~\cite{eucl}, $P$ generates either $\widetilde B_n$ or 
$\widetilde C_n$. 

Let $\varphi$ and $\psi$ be two dihedral angles equal to $\frac{\pi}{4}$
formed up by mirrors of $G_P$.
Then there exists an element $\gamma$ of $G_P$ such that 
$\gamma(\varphi)=\psi$.
The group  $\widetilde C_n$ contains two equivalency classes of such
dihedral angles. Hence, $G_P\ne \widetilde C_n$ and
$P$ generates $\widetilde B_n$.

Furthermore, let us show that each graph shown in the left column
of the Table~\ref{beat} corresponds to a unique family of simplices
generating $\widetilde B_n$.
Indeed, the family diagram of the family containing $P$ can be
easily recovered from  $\Gamma(P)$:
all but one nodes of the diagram correspond to the edges  
of $\Gamma(P)$,
two nodes are adjacent if the corresponding edges 
have a common point;
the rest node corresponds to the marked node  
of $\Gamma(P)$, this node is joined  by a 2-fold
edge with all the nodes that correspond to edges of $\Gamma(P)$
incident to the marked node. 
Thus, any graph shown in the left column of Table~\ref{beat}
corresponds to a unique family diagram, and, by Lemma~\ref{unique}, 
it corresponds to a unique family.
An explicit calculation shows that the generalized Coxeter diagram
of simplex generating $\widetilde B_n$ is one of the diagrams shown
in the right column of Table~\ref{beat}.

Thus,  families of  simplices generating $\widetilde B_n$
are in one-to-one correspondence with  graphs shown in the left
column of Table~\ref{beat}.
To find the number of these families note, that 
$\Gamma(P)$ is uniquely determined by the number of edges in the
cycle. The latter is any integer number $N$ satisfying $2\le N \le n$.

\end{proof}

\begin{table}[!h]
\caption{Simplices generating $\widetilde B_n$. }
\label{beat}
\vspace{5pt}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
\ $\Gamma(P)$\ &\  Family diagram\ 
& 
\begin{tabular}{c}
\raisebox{0pt}[15pt][10pt]{Generalized} \\
\raisebox{5pt}[5pt][5pt]{Coxeter diagram}
\end{tabular}
\\
\hline
&&\\
\epsfig{file=beat1.eps,width=0.092\linewidth}&
\epsfig{file=beat2.eps,width=0.098\linewidth}&
\epsfig{file=beat3.eps,width=0.098\linewidth}\\
&&\\
\hline
&&\\
\raisebox{10pt}[0pt][0pt]{\epsfig{file=cycle1.eps,width=0.101\linewidth}}&
\raisebox{6pt}{\epsfig{file=cycle2.eps,width=0.095\linewidth}}&
\raisebox{6pt}{\epsfig{file=cycle3.eps,width=0.095\linewidth}}\\
\hline
\end{tabular}
\end{center}
\end{table}

\noindent
As a corollary of Theorem~\ref{B} and the first statement of 
Lemma~\ref{marked} we obtain the following theorem:

 
\begin{theorem}
\label{C}
There exists a unique family of simplices generating 
$\widetilde C_n$.
This  family consists of Coxeter simplices $\widetilde C_n$.

\end{theorem}





\subsection{Simplices generating $\widetilde D_n$}
\label{sectionD}

Let $P$ be a simplex generating the group $\widetilde D_n$.
We may assume that the vectors $f_0,f_1,...,f_n$ belong to the 
root system 
$\mathrm D_n=\{\pm h_i \pm h_j)\}, 1\le i<j\le n$, where
$h_1,...,h_n$ is a standard basis of $\E^{n}$).

For any simplex $P=\{f_0,f_1,...f_n\}$ generating $\widetilde D_n$
we construct the following {\it graph} $\,\Gamma(P)$:
the nodes $v_1,...,v_n$ of  $\Sigma$ correspond to the vectors 
$h_1,...h_n$; the nodes $v_i$ and $v_j$ are joined by an edge
if one of vectors $\pm (h_i-h_j)$ and $\pm (h_i+h_j)$ belongs to the set 
$\{f_0,...,f_n\}$; if $\{f_0,f_1,...,f_n\}$ contains both $\pm(h_i+h_j)$ and  
$\pm(h_i-h_j)$ then $v_i$ and $v_j$ are joined by two edges.

The system of vectors $f_0,f_1,...,f_n$  is indecomposable,
hence, $\Gamma(P)$ is connected.
Since  $\Gamma(P)$ has $n$ nodes and $n+1$ edges,   
 $\Gamma(P)$ contains at least two cycles $C_1$ and $C_2$.

Suppose that  $C_1$ and $C_2$ have no common nodes.
Since the graph containing two disjoint cycles corresponds to 
a linearly dependent system of vectors, 
$\Gamma(P)$ is one of the graphs shown in the left column 
of Table~\ref{veslo}. 
If $C_1$ and $C_2$ have a unique common node then
$\Gamma(P)$ is the graph shown at the bottom of left column
of Table~\ref{veslo}. 

\begin{lemma}
\label{2cycles}
Suppose that $\Gamma(P)$ contains two cycles having at least two
common nodes. Then the system of vectors  $f_0,f_1,...,f_n$
contains $n$ linearly dependent vectors.

\end{lemma}

\begin{proof}
Consider the graph $\Gamma(P)$ colored by the following way: edges
corresponding to vectors 
$\pm(h_i+h_j)$ are red, and the rest edges, i.e. the edges
corresponding to $\pm(h_i-h_j)$, are black. 
Note that substituting the vector $h_i$  by $-h_i$ we change the 
color of all edges incident to  $v_i$.
Thus, preserving the vectors  $f_0,f_1,...,f_n$,
we can make all but one edge of a given cycle black
(the rest edge is either red or black). 
Vectors $h_1-h_2,h_2-h_3,...,h_k-h_1$ are linearly dependent.
Hence, each cycle containing an even number of  red edges
corresponds to a system of linearly dependent vectors.

Consider common nodes of two cycles contained in $\Gamma(P)$.
There are at least three paths  $L_1,L_2$ and $L_3$ joining these
nodes in $\Gamma(P)$.
Denote by $c(L_i)$ the number of red edges in $L_i$.
Then $c(L_i)+c(L_j)$ is even for some $i\ne j$, $i,j=1,2,3$.
We assume that $c(L_1)+c(L_2)$ is even. Then the cycle $C=L_1\cup L_2$
contains even number of  red edges, so, it corresponds
to some linearly dependent vectors. 
Since some edges of $\Gamma(P)$ do not belong to $C$,
the number of these linearly dependent vectors is less than $n+1$.
The contradiction  proves the lemma.


\end{proof}

\begin{cor}
\label{d}
$\Gamma(P)$ contains exactly two cycles and coincides with one of 
graphs shown in the left column of Table~\ref{veslo}.

\end{cor}

Thus, we obtain the following theorem:

\begin{theorem}
The group $\widetilde D_n$ is generated by exactly  
 $\frac{1}{4}n(n-2)$ families of simplices if $n$ is even,
and by exactly $\frac{1}{4}(n-1)^2$ families if $n$ is odd.
Family diagrams and generalized Coxeter diagrams 
of these simplices are presented in Table~\ref{veslo}. 
 


\end{theorem}

\begin{table}[!h]
\caption{Simplices generating $\widetilde D_n$. }
\label{veslo}
\vspace{5pt}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
\ $\Gamma(P)$\ &\  Family diagram\ 
& 
\begin{tabular}{c}
\raisebox{0pt}[15pt][10pt]{Generalized} \\
\raisebox{5pt}[5pt][5pt]{Coxeter diagram}
\end{tabular}
\\
\hline
&&\\
\epsfig{file=veslo1.eps,width=0.0939\linewidth}&
\epsfig{file=veslo2.eps,width=0.098\linewidth}&
\epsfig{file=veslo3.eps,width=0.098\linewidth}\\
&&\\
\hline
&&\\
\raisebox{7pt}[0pt][0pt]{\epsfig{file=veslo4.eps,width=0.097\linewidth}}&
\raisebox{6pt}{\epsfig{file=veslo5.eps,width=0.095\linewidth}}&
\raisebox{6pt}{\epsfig{file=veslo6.eps,width=0.095\linewidth}}\\
\hline
\end{tabular}
\end{center}
\end{table}




\begin{proof}

By Cor.~\ref{d}, a simplex $P$ generating $\widetilde D_n$ 
corresponds to a graph $\Gamma(P)$ shown in the left column of
Table~\ref{veslo}. 

Let us show that any graph $\Gamma$  shown in the left column of
Table~\ref{veslo} corresponds to a simplex generating $\widetilde
D_n$.
For each cycle of $\Gamma$ choose an edge $v_iv_j$ and put the vector
 $h_i-h_j$ in correspondence with this edge (in other words, suppose
these edges to be red). For all other edges $v_kv_l$  take  vectors $h_k+h_l$.
It is easy to see that any $n$ of these vectors   
are linearly independent and all these vectors are linearly dependent.
Hence,  $\Gamma$ corresponds to some simplex $P$ in $\E^n$.
By~\cite{eucl}, the group  $\widetilde D_n$ has no finite index
indecomposable subgroups different from $\widetilde D_n$. 
Therefore, $P$ generates  $\widetilde D_n$. 

Now, show that each graph $\Gamma$ shown in the left column of
Table~\ref{veslo} corresponds to a unique family of simplices generating
 $\widetilde D_n$.
Indeed, a family diagram  of the family containing $P$ 
can be recovered from $\Gamma(P)$: nodes of diagram 
correspond to  edges of  $\Gamma$, two nodes are adjacent if the
corresponding edges have a common point.
Therefore,  the family does not depend on the choice of initial edges. 
Moreover, in the beginning of the procedure we could make red not one but
several edges: the family diagram would not be changed.  
Hence, family diagram of simplices generating $\widetilde D_n$
are in one-to-one correspondence with  graphs shown in the left
column of Table~\ref{veslo}.
By Lemma~\ref{unique}, each family diagram corresponds to a unique 
family.
Thus, families of simplices generating  $\widetilde D_n$
are in one-to-one correspondence with graphs shown in the left
column of Table~\ref{veslo}. 
An explicit calculation shows that generalized Coxeter diagram
of simplex generating $\widetilde D_n$ is one of diagrams shown
in the right column of Table~\ref{veslo}.


To find the number of families note, that 
$\Gamma(P)$ is uniquely determined by the numbers $N_1$ and $N_2$ of
edges in two cycles. 
Numbers $N_1$ and $N_2$ are 
any two integers satisfying $N_1+N_2\le n+1$ and
$2\le N_1\le N_2 \le n$. The number of such pairs $(N_1,N_2)$
equals either $\frac{1}{4}n(n-2)$  
or $\frac{1}{4}(n-1)^2$ if $n$ is even or odd respectively.



\end{proof}




\subsection{Simplices generating other groups}

In Sections~\ref{SecA}--\ref{sectionD} we have described all 
families generating the groups
$\widetilde A_n$, $\widetilde B_n$,
$\widetilde C_n$  and $\widetilde D_n$.
Now, we are left to classify  families generating finitely many of
other indecomposable Euclidean reflection groups.
Namely, we a left with the groups 
$\widetilde E_6$, $\widetilde E_7$,
$\widetilde E_8$, $\widetilde F_4$,  
and $\widetilde G_2$. 
We can find the complete answer following the algorithm
contained in the beginning of Section~\ref{algorithm}.
As the result we obtain the lists which are rather large:
there exist \\
\phantom{aaaaaaaa} 17 families of simplices generating
  $\widetilde E_6$,\\ 
\phantom{aaaaaaaa} 142 families of simplices generating $\widetilde E_7$, \\
\phantom{aaaaaaaa} 1736 families of simplices generating $\widetilde E_8$,\\
\phantom{aaaaaaaa} 11 families of simplices generating $\widetilde F_4$, \\
\phantom{aaaaaaaa} and 2 families of simplices generating $\widetilde G_2$. \\
Appendix contains the complete list of these families.


\section*{Appendix}

Appendix contains the list of families generating
$\widetilde E_6$, $\widetilde E_7$,
$\widetilde E_8$, $\widetilde F_4$,  
and $\widetilde G_2$.
Families generating $E_6$, $E_7$ and $E_8$ are encoded
in the following way. For a family $\pm f_0,\pm f_1,...,\pm f_n$
construct a symmetrical matrix $G^+=\{g_{i,j}\}$, where
$g_{i,j}=2|(f_i,f_j)|$.
This is a doubled unsigned Gram matrix of the system
$f_0, f_1,..., f_n$.
The upper triangle of $G^+$ is filled up by $0$ and $1$.
Let $p$ be a decimal number which is equal to
the binary number
$\overline{
g_{1,2}g_{1,3}...g_{1,n}g_{2,3}...g_{2,n}...g_{i,i+1}...g_{i,n}...g_{n-1,n}}\!$.
The number $p$ depends on the ordering of vectors $f_0,f_1,...f_n$.
We choose $p$ the smallest possible.

\subsection*{Families generating $\widetilde E_6$}
\input{res_e6.txt}


\subsection*{Families generating $\widetilde E_7$}
\input{res_e7.txt}

\subsection*{Families generating $\widetilde E_8$}
\input{res_e8.txt}

\subsection*{Families generating $\widetilde F_4$}

 Families generating $F_4$ are encoded
in the following way. For a family determined by 
$\pm f_0,\pm f_1,...,\pm f_4$
construct a symmetric matrix $G^+=\{g_{i,j}\}$,
where $g_{i,j}=0$ if $f_i$ is orthogonal to $f_j$,
 $g_{i,j}=1$ if $\angle f_if_j=\frac{\pi}{3}$ or
$\frac{2\pi}{3}$,
 $g_{i,j}=2$ if $\angle f_if_j=\frac{\pi}{4}$ or
$\frac{3\pi}{4}$.
Let $p$ be a decimal number which is equal to
the base three number
$\overline{
g_{1,2}g_{1,3}...g_{1,n}g_{2,3}...g_{2,n}...g_{i,i+1}...g_{i,n}...g_{n-1,n}}$.
The number $p$ depends on the numbering of vectors $f_1,...f_n$.
We choose $p$ the smallest possible.
Then $p$ depends only on the family of simplices.

\input{res_f4.txt}

\subsection*{Families generating $\widetilde G_2$}

The group $G_2$ can be generated either by triangle with angles
$(\frac{\pi}{2},\frac{\pi}{3},\frac{\pi}{6})$ or
by triangle with angles
$(\frac{2\pi}{3},\frac{\pi}{6},\frac{\pi}{6})$.


\begin{thebibliography}{11}

\bibitem{Coxeter}
H.~S.~M.~Coxeter. {\em Discrete groups generated by reflections.}
Ann. Math. 35 (1934), no. 3, 588--621.  

%\bibitem{Dyn}
%E.~B.~Dynkin. {\em Semisimple subalgebras of semisimple Lie algebras.}
%Amer. Math. Soc. Trans. (2), 6 (1957) 111--244. 


\bibitem{polygons}
 A.~Felikson. {\em Coxeter decompositions of hyperbolic polygons.}
Europ. J. Combinatorics 19 (1998), 801--817.




\bibitem{simplex}
A.~Felikson. {\em Coxeter decompositions of hyperbolic simplices.}
Sbornik: Mathematics 193 (2002), no. 12, 1867--1888. 
arXiv:math.MG/0210067.


\bibitem{pyrprism}
A.~Felikson. {\em Coxeter decompositions of bounded hyperbolic pyramids 
and triangular prisms.} Math. Notes  75 (2004), no. 3-4, 583--593. 
arXiv:math.MG/0212195.


\bibitem{lambert}
 A.~Felikson. {\em Lambert Cube generating discrete reflection group.}
 Math. Notes 75 (2004), no. 1-2, 250--258.


\bibitem{sph}
 A.~Felikson. {\em Spherical simplices  generating discrete 
reflection groups.} Sbornik: Mathematics 195 (2004), no. 3-4, 585--598.  
 arXiv:math.MG/0212244.

\bibitem{eucl}
 A.~Felikson, P.~Tumarkin. 
{\em Reflection subgroups of Euclidean reflection groups.}
 arXiv:math.MG/0402403.

\bibitem{Kac}
V.~Kac. {\em Infinite dimensional Lie algebras.} 
Cambridge Univ. Press, 1990. 



\bibitem{Pink} E.~Klimenko, M.~Sakuma. 
{\em Two-generator discrete subgroups of
$Isom(\H^2)$ containing orientation-reversing elements.}
Geom. Dedicata 72 (1998), 247--282.



\bibitem{Shwarz} H.~A.~Schwarz. {\em \"Uber diejenige F\"alle
in welchen die Gaussische
 Reihe eine algeraische Function ihres elementes destellt.} Crelle's J. 1873,
v 75, 292--335.


\bibitem{29} 
E.~B.~Vinberg (Ed.). {\em Geometry II, 
Encyclopedia of Mathematical Sciences, Vol. 29.} Springer-Verlag
Berlin Heidelberg, 1993. 





\end{thebibliography}




\vspace{25pt}
\noindent
Independent University of Moscow, Russia \\
Max-Planck Institut f\"ur Mathematik Bonn, Germany\\
e-mail: \phantom{ow} felikson@mccme.ru\qquad pasha@mccme.ru








\end{document}

math0502108.extracted_bib
\begin{thebibliography}{11}

\bibitem{Coxeter}
H.~S.~M.~Coxeter. {\em Discrete groups generated by reflections.}
Ann. Math. 35 (1934), no. 3, 588--621.  

%\bibitem{Dyn}
%E.~B.~Dynkin. {\em Semisimple subalgebras of semisimple Lie algebras.}
%Amer. Math. Soc. Trans. (2), 6 (1957) 111--244. 


\bibitem{polygons}
 A.~Felikson. {\em Coxeter decompositions of hyperbolic polygons.}
Europ. J. Combinatorics 19 (1998), 801--817.




\bibitem{simplex}
A.~Felikson. {\em Coxeter decompositions of hyperbolic simplices.}
Sbornik: Mathematics 193 (2002), no. 12, 1867--1888. 
arXiv:math.MG/0210067.


\bibitem{pyrprism}
A.~Felikson. {\em Coxeter decompositions of bounded hyperbolic pyramids 
and triangular prisms.} Math. Notes  75 (2004), no. 3-4, 583--593. 
arXiv:math.MG/0212195.


\bibitem{lambert}
 A.~Felikson. {\em Lambert Cube generating discrete reflection group.}
 Math. Notes 75 (2004), no. 1-2, 250--258.


\bibitem{sph}
 A.~Felikson. {\em Spherical simplices  generating discrete 
reflection groups.} Sbornik: Mathematics 195 (2004), no. 3-4, 585--598.  
 arXiv:math.MG/0212244.

\bibitem{eucl}
 A.~Felikson, P.~Tumarkin. 
{\em Reflection subgroups of Euclidean reflection groups.}
 arXiv:math.MG/0402403.

\bibitem{Kac}
V.~Kac. {\em Infinite dimensional Lie algebras.} 
Cambridge Univ. Press, 1990. 



\bibitem{Pink} E.~Klimenko, M.~Sakuma. 
{\em Two-generator discrete subgroups of
$Isom(\H^2)$ containing orientation-reversing elements.}
Geom. Dedicata 72 (1998), 247--282.



\bibitem{Shwarz} H.~A.~Schwarz. {\em \"Uber diejenige F\"alle
in welchen die Gaussische
 Reihe eine algeraische Function ihres elementes destellt.} Crelle's J. 1873,
v 75, 292--335.


\bibitem{29} 
E.~B.~Vinberg (Ed.). {\em Geometry II, 
Encyclopedia of Mathematical Sciences, Vol. 29.} Springer-Verlag
Berlin Heidelberg, 1993. 





\end{thebibliography}