%Partially filled out abstract Coxeter diagram?
%realized order types in dimension 5


%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2023}
\articlenumber{26}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{thmtools}
\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}

\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}

%custom commands
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Hy}{\mathbb{H}}
\newcommand{\calH}{\mathcal{H}}
\renewcommand{\phi}{\varphi}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\cut} { \setminus}

%% define your title in the usual way
\title{\texorpdfstring{Compact Hyperbolic Coxeter $d$-Polytopes with $d+4$ Facets and Related Dimension Bounds}{Compact Hyperbolic Coxeter d-Polytopes with d+4 Facets and Related Dimension Bounds}}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Amanda Burcroff\thanks{\href{mailto:aburcroff@math.harvard.edu}{aburcroff@math.harvard.edu}. Amanda Burcroff was supported by the NSF GRFP and the Marshall Commission.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Harvard University, Cambridge, MA, USA}

%% put the date of submission here
\received{November 12, 2022}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We complete the classification of compact hyperbolic Coxeter $d$-polytopes with $d+4$ facets for $d=4$ and $5$. By previous work of Felikson and Tumarkin, the only remaining dimension where new polytopes may arise is $d=6$. We derive a new method for generating the combinatorial types of these polytopes via the classification of point set order types. In dimensions $4$ and $5$, there are $348$ and $51$ polytopes, respectively, yielding many new examples for further study.  
    
We furthermore provide new upper bounds on the dimension $d$ of compact hyperbolic Coxeter polytopes with $d+k$ facets for $k \leq 10$.  It was shown by Vinberg in $1985$ that there are no compact hyperbolic Coxeter polytopes in dimensions higher than $29$, and no better dimension bounds have previously been published for $k \geq 5$.  As a consequence of our bounds, we prove that a compact hyperbolic Coxeter $29$-polytope has at least $40$ facets.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Coxeter polytope, hyperbolic reflection group, affine Gale diagram}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{main.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
Let $\Hy^d$ be the $d$-dimensional real hyperbolic space.  A \emph{hyperbolic Coxeter polytope} is a domain in $\Hy^d$ bounded by a collection of geodesic hyperplanes, such that each intersecting pair of hyperplanes meets at dihedral angle $\frac{\pi}{m}$ for some integer $m \geq 2$.  Hyperbolic Coxeter polytopes are precisely the fundamental domains of discrete hyperbolic reflection groups.  These polytopes also have relevance to the construction of orbifolds and manifolds, in particular some of minimal volume \cite{kellerhals2014hyperbolic}.  

We classify the compact hyperbolic Coxeter $d$-polytopes with $d+4$ facets for $d = 4$ and $5$, as well as improve some bounds on the dimension of compact Coxeter polytopes with few facets. While Euclidean and spherical Coxeter polytopes were classified by Coxeter in 1934 \cite{coxeter1934discrete}, no complete classification is known in the hyperbolic case.  Henceforth, all polytopes are assumed to be hyperbolic unless otherwise specified.  

Many of the classification results for compact Coxeter polytopes have been obtained by restricting either the dimension, combinatorial type, or number of facets.  A dynamic summary of this progress is maintained on Anna Felikson's webpage \cite{felikson_tumarkin}. 

\subsection{\texorpdfstring{Classifying compact Coxeter $d$-polytopes with $d+4$ facets for $d \neq 6$}{Classification of compact Coxeter d-polytopes with d+4 facets for d not equal to 6}}
We first focus on restricting the number of facets with respect to the dimension.  Compact Coxeter simplices, i.e., $d$-polytopes with $d+1$ facets, were classified by Lann{\'e}r in 1950 \cite{lanner1950complexes}.  These arise only in dimensions $2$, $3$, and $4$.  The compact Coxeter $d$-polytopes with $d+2$ facets are classified in \cite{kaplinskaya1974discrete} and \cite{esselmann1996classification}; these arise in dimensions $3$ through $5$ and are simplicial prisms except in dimension $4$.  Esselmann \cite{esselmann1994kompakte} showed in 1994 that a compact Coxeter $d$-polytope with $d+3$ facets must satisfy $d \leq 8$, and that there is a unique polytope of dimension $8$ (first constructed by Bugaenko \cite{bugaenko1984groups}).  In 2007, Tumarkin \cite{tumarkin2007compact} completed the classification of compact Coxeter $d$-polytopes with $d+3$ facets, which arise in dimensions $2$ through $6$ and $8$.  

The first portion of this work is dedicated to furthering the classification of compact Coxeter $d$-polytopes with $d+4$ facets.   In 2008, Felikson and Tumarkin \cite{felikson2008d} showed that such polytopes arise only in dimension at most $7$, and furthermore that there is a unique compact Coxeter $7$-polytope with $11$ facets (originally constructed by Bugaenko \cite{bugaenko1984groups}).  We complete this classification in dimensions $4$ and $5$, leaving dimension $6$ as the only remaining dimension where new polytopes can arise.

\begin{thm}\label{thm: polytope classification}
The are $348$ hyperbolic Coxeter $4$-polytopes with $8$ facets, and $51$ hyperbolic Coxeter $5$-polytopes with $9$ facets.  For the full list, see the appendices of \cite{burcroff2022near}.  
\end{thm}  

\begin{rem}
The classification above includes
\begin{itemize}
    \item the first known hyperbolic Coxeter polytope in dimension higher than $3$ with a dihedral angle of less than $\frac{\pi}{10}$,
    \item the first and only known hyperbolic Coxeter polytope in dimension higher than $3$ with a dihedral angle of $\frac{\pi}{7}$, and
    \item the first known compact Coxeter polytope in dimension $5$ with a dihedral angle of less than $\frac{\pi}{6}$,
\end{itemize} 
along with many new \emph{essential} polytopes.  

A polytope is \emph{essential} if it is minimal with respect to the operations of taking the fundamental domain of a finite index reflection subgroup of the corresponding reflection group or gluing two Coxeter polytopes along congruent facets (see \cite{felikson2014essential} for further details).  See the Coxeter diagrams in \autoref{fig: interesting polytopes} for examples of polytopes having these properties.
\end{rem}

  The work in the paper on which this extended abstract is based combined with that of Felikson and Tumarkin yields a classification in all dimensions except $6$.  There is only one known compact Coxeter $6$-polytope with $10$ facets, which was constructed by Bugaenko \cite{bugaenko1984groups}. 
  
\begin{figure}
\begin{center}
\includegraphics[width=.9\linewidth]{interesting_polytopes.pdf}
\caption{The Coxeter diagrams of three new polytopes from the classification in \autoref{thm: polytope classification}, all of which are essential.  See \autoref{subsec: gale diagrams} for details on how to interpret Coxeter diagrams.\vspace{-1cm}}
\label{fig: interesting polytopes}
\end{center}  
\end{figure}

In order to obtain this classification, we develop a new method for restricting the possible combinatorial types of these polytopes.  The Gale diagram of a $d$-dimensional polytope with $n$ facets is an $n - d - 1$ arrangement of points in Euclidean space that encodes the combinatorial type of the polytope.  Hence the combinatorial types of $d$-polytopes with $d+4$ facets can be studied in terms of a $3$-dimensional point arrangement.  Moreover, each Gale diagram can be transformed into an affine Gale diagram, an arrangement of signed points, to further reduce the dimension by $1$ \cite{vinberg1985hyperbolic}.  We show that the (affine) Gale diagrams of compact $d$-dimensional hyperbolic polytopes with $d+4$ facets can be generated by bipartitioning the points in all simple point set order types with $d+4$ points (see \cref{thm: affine properties} for further details).  The point set order types of sizes up to $10$ have been enumerated and made available through the Point Set Order Type Database \cite{aichholzer2002enumerating}.  Using this database, we produce a reasonably short list of possible combinatorial types for the polytopes of interest in dimensions $4$ and $5$.  In dimension $6$, the same methods can be applied, but the number of point set order types makes the process rather computationally demanding.

Having greatly restricted the possible combinatorial types in dimensions $4$ and $5$, we then determine whether each combinatorial type can be realised as one or more polytopes.  This involves enumerating weighted graphs with restrictions on certain subgraphs and the spectral properties of their adjacency matrices.  Though the search space is infinite, combinatorial and linear algebraic techniques (see, e.g., \cite{vinberg1985hyperbolic}) have previously been successful in reducing this to a computational problem.  In particular, Tumarkin handled the analogous task for polytopes with $d + 3$ facets by inspecting local determinants, face structures, and gluings of Lann{\'e}r diagrams \cite{tumarkin2007compact}.  These methods are only partially effective for the polytopes with $d + 4$ facets, due to the greater complexity of the polytopes and less restrictive combinatorial types.  We then utilise {\tt Mathematica} to check a finite number of cases in order to list all polytopes of a given combinatorial type, a technique which was recently used in classifying the compact Coxeter cubes \cite{jacquemet2018all}.

Ma and Zheng independently and via different methods classified the compact hyperbolic Coxeter $4$-polytopes with $8$ facets \cite{ma2022compact4} and $5$-polytopes with $9$ facets \cite{ma2022compact5}. Their work became publicly available within a few months after the release of the author's master's thesis on this topic. The author is very grateful to Ma and Zheng for their communication about this classification, as it helped to correct several minor errors.  Due to the sheer volume of data handling required by both our methods and those of Ma and Zheng, there were a few errors in the polytope lists initially announced by both groups, though the methods seem sound.  Ma, Zheng, and the current author now agree on the published lists.  The existence of two independent methods for obtaining these polytopes may lend some confidence to the accuracy of this rather delicate classification.


\subsection{Bounding the dimension of polytopes with few facets}
We then shift our focus to bounding the dimension of certain compact Coxeter polytopes.  It was shown in 1984 by Vinberg \cite{vinberg1981absence} that compact Coxeter polytopes do not arise in dimensions higher than $29$.  Vinberg proceeded by constructing certain weightings on the edges of the polytopes and utilised a result of Nikulin \cite{nikulin1982classification} on the average number of vertices along a $2$-dimensional face.  A \emph{missing face} of a polytope is a minimal set of facets whose intersection is empty.  We show that a slight modification of Vinberg's argument yields a stronger bound for \emph{$3$-free polytopes}, that is, polytopes having missing faces only of order $2$.  

\begin{thm}\footnote{Since the release of this work, our upper bound of $13$ has been improved using similar methods (which, in turn, were inspired by those of Vinberg \cite{vinberg1981absence}) to $12$ by Alexandrov \cite{alexandrov2022lann}.} Compact hyperbolic Coxeter $3$-free polytopes do not arise in dimensions higher than $13$.
\end{thm}  

Using this property of $3$-free polytopes along with the classification results, we improve the bounds on the dimension of compact Coxeter $d$-polytopes with $d+k$ facets for $5 \leq k \leq 10$.  In order to obtain an initial bound, we examine certain faces which must themselves be compact Coxeter polytopes, similar to the methods used by Felikson and Tumarkin \cite{felikson2008d} to bound the dimension when $k = 4$.  We are able to improve these bounds in certain cases, frequently referring to the classification of polytopes with fewer facets.  A corollary of our improved bounds is that any compact Coxeter polytopes of dimension $29$, i.e., the threshold of Vinberg's bound, must have at least $29 + 11 = 40$ facets.  


\section{\texorpdfstring{Combinatorial Types of $d$-Polytopes with $d+4$ Facets}{Combinatorial Types of d-Polytopes with d + 4 Facets}}\label{sec: comb types d+4}
\subsection{ Gale and Coxeter diagrams}\label{subsec: gale diagrams}
An important technique in classifying convex polytopes is representing a polytope by a diagram from which one can read off the face structure.  We will work with \emph{affine Gale diagrams}, which are a projection of the more classical \emph{Gale diagrams}, introduced in a $1956$ paper by David Gale \cite{gale201615}.  Note that while (affine) Gale diagrams are often defined using the vertices of a polytope, we look at the dual construction defined on the facets.  

Given a simple $d$-polytope $P$ with $d + k$ facets, a Gale diagram of $P$ consists of a set of $d + k$ points on the sphere $S^{k-2} \subset \R^{k-1}$ corresponding to the facets of $P$.  In the case $k = 4$, Gale diagrams consist of point configurations on $S^2 \subseteq \R^3$.  These seem rather difficult to classify, and thus a crucial step in our analysis is passing to the affine Gale diagrams.  These affine variants encode the same information as Gale diagrams but use partitioned sets of points in $\R^{k-2}$. 

An \emph{affine Gale diagram} of a $d$-polytope with $d+k$ facets consists of two (not necessarily disjoint) point sets, called ``positive'' and ``negative'', in $\R^{k-2}$ containing $d+k$ points in total (counted with multiplicity).  An affine Gale diagram is obtained from a Gale diagram $G$ by taking a hyperplane $H$ through the origin not containing any points of $G$, and projecting the points orthogonally onto $H$, with the projections of points from the open half space $H^+$ being labelled ``positive'' and those from $H^-$ labelled ``negative''.  The face structure of $P$ is determined in the following way: a set of facets $\{f_i : i \in I\}$ of $P$ has a non-trivial intersection if and only if the convex hull of the positive points in $\{f_j : j \notin I\}$ non-trivially intersects the convex hull of the negative points in $\{f_j : j \notin I\}$.


We now define another type of diagram that not only encodes the combinatorial type of a polytope, but also its dihedral angles.  

\begin{defn}
An \emph{abstract Coxeter diagram} is a finite simple graph with weighted ordinary and dashed edges.  The weights $w_{ij}$ must be positive and satisfy the following condition: if $w_{ij} < 1$, then $w_{ij} = \cos\left( \frac{\pi}{m_{ij}}\right)$ for some integer $m_{ij} \geq 3$. 
\end{defn}

The word ``abstract'' highlights that the diagrams we consider do not always correspond to polytopes.  When such a diagram does correspond to a polytope, then the edges of weight $\cos\left(\frac{\pi}{m_{ij}}\right)$ encode that the dihedral angle between facets $f_i$ and $f_j$ is $\frac{\pi}{m_{ij}}$ and non-intersecting facets at distance $x$ are encoded by an edge of weight $\cosh(x)$.  

We often denote an abstract Coxeter diagram by the letter $\Sigma$.  The order $|\Sigma|$ of the diagram $\Sigma$ is the number of vertices of $\Sigma$.  A \emph{subdiagram} $\Sigma'$ of $\Sigma$ is a vertex-induced subgraph of $\Sigma$, where the edge weights are preserved; this relation is written as $\Sigma' \subset \Sigma$.  Since we are considering only compact polytopes, there are no edges of weight $1$ in our setting.  When drawing abstract Coxeter diagrams, we adhere to the following conventions:
\begin{enumerate}[label={(\roman*)}]
    \item If $w_{ij} < 1$, hence $w_{ij} = \cos\left( \frac{\pi}{m_{ij}}\right)$ for some integer $m_{i,j} \geq 2$, then the corresponding edge is drawn as a straight line labelled by $m_{ij}$.  In the special cases where $m_{ij}$ is equal to $3$, $4$, or $5$, we draw the corresponding edge as an unlabelled single, double, or triple line, respectively. If $m_{ij} = 2$, we leave the edge empty.
    \item If $w_{ij} > 1$, the corresponding edge is drawn as a dashed line with label $w_{ij}$.  We often omit these weights, since they can be determined from rest via rank conditions.
\end{enumerate}

\begin{figure}[ht]
\begin{center}
\includegraphics[height=4.5cm]{affine_G1_with_Gale.pdf}
\caption{On the left is an affine Gale diagram of a $4$-polytope with $8$ facets, with the positive points depicted in red and the negative points in black.  The line segments between negative points are included to aid in identifying the convex hull of each subset.  On the right, we have a Coxeter diagram of polytope realising this combinatorial type.\vspace{-1cm}}
\label{fig: affine G6}
\end{center}  
\end{figure}

\subsection{\texorpdfstring{Affine Gale diagrams of simple $d$-polytopes with $d+4$ facets}{Affine Gale diagrams of compact polytopes with d + 4 facets}}\label{sec: affine Gale d+4}
In order to determine the compact hyperbolic $d$-polytopes with $d+4$ facets in dimension $4$ and $5$, our methods involve first limiting their possible combinatorial types.  This was accomplished for compact hyperbolic $d$-polytopes with $d+3$ facets by Tumarkin \cite{tumarkin2007compact}, using \emph{standard Gale diagrams} described by Esselmann \cite{esselmann1994kompakte}.  However, Tumarkin's methods do not seem immediately generalisable to Gale diagrams of higher dimension. We develop a new method for generating affine Gale diagrams using a classification of point set order types by Aichholzer, Aurenhammer, and Krasser \cite{aichholzer2002enumerating}.  These are reduced to a representative list of Gale diagrams, from which one can easily determine the set of missing faces. Later sections are devoted to determining which of these combinatorial types are realisable. 

%\begin{rem}\label{rem: disj pos neg}Let $P$ be a simple $d$-polytope with $d + k$ facets for $k \geq 2$.  Observe that the positive and negative points of an affine Gale diagram for $P$ are necessarily disjoint.  If not, let $v \in \R^2$ be a point which is both positive and negative.  The facets not corresponding to this point then intersect non-trivially in a face of codimension $d + k - 2 \geq d$, which is not possible.\end{rem}

A set of points in $\R^d$ is said to be in \emph{general position} if no $m$ points lie in a subspace of dimension $m -2$ for $m = 2,\dots,d+1$.  We show that we can slightly perturb the points of the affine Gale diagram so that the points are in general position without changing the combinatorial structure.

Furthermore, it has been shown by Tumarkin and Felikson \cite{felikson2008hyperbolic,felikson2009coxeter} that for $k \geq 4$, every compact $d$-polytope with $d+k$ facets has at least two pairs of non-intersecting facets.  Given a polytope $P$ with $d+4$ facets, let $f$ and $f'$ be a non-intersecting pair of facets.  In any Gale diagram associated to $P$, the points corresponding to $f$ and $f'$ can be separated from the remaining points by a hyperplane through the origin.  Take the affine Gale diagram obtained by orthogonal projection onto this hyperplane and choosing the half-space containing $f$ and $f'$ to be positive.  Thus, we can obtain an affine Gale diagram associated to $P$ where all points are in general position and with exactly two positive points.  In summary, we have the following result.

\begin{thm}\label{thm: affine properties}
Every simple $d$-polytope with $d+4$ facets admits an affine Gale diagram \\${A = A_+ \cup A_-}$, where $A_+$ and $A_-$ are finite sets of points in $\R^2$ such that
\begin{enumerate}[label={(\roman*)}]
    \item all points of $A$ are in general position,
    \item $|A_+| = 2$, and
    \item $A_+$ is contained in the interior of the convex hull of $A_-$.
\end{enumerate}
\end{thm}

An example of such an affine Gale diagram and a polytope realising its combinatorial type are depicted in \cref{fig: affine G6}.  We use these restrictions to show that all affine Gale diagrams of compact $d$-polytopes with $d+4$ facets can be obtained by bipartitioning the $d + k$ points of a point set order type.


\subsection{Point set order types}\label{subsec: point set}
In order to enumerate the possible Gale diagrams of compact $d$-polytopes with $d+4$ facets, we utilise a classification of the point set order types of size at most $10$ \cite{aichholzer2002enumerating}.  The \emph{order type} of a set of points $\{p_1,\dots,p_n\} \subset \R^2$ in general position is a mapping that assigns to each ordered triple $(i,j,k)$ of distinct elements in $\{1,\dots,n\}$ the orientation of the point triple $(p_i,p_j,p_k)$.  Two finite subsets $P,Q \subset \R^2$ are said to be \emph{combinatorially equivalent} if they have  the  same  order  type, i.e., if there exists a bijection $f:P\to Q$ that preserves orientations.  

We now obtain our method for generating the desired affine Gale diagrams using the point set order types.  Namely, taking a representative of each simple order type and iterating over all choices of two positive points from the interior of the convex hull yields all possible affine Gale diagrams.  

Using the order type database for up to $10$ points \cite{aichholzer2002enumerating}, one can classify the combinatorial types of all polytopes with $d + 4$ facets in dimension at most $6$.  There are $3{,}315$ order types on $8$ points, which yield $34$ possible combinatorial types of simple $4$-polytopes with $8$ facets having at least one pair of disjoint facets, listed in \cite[Appendix A]{burcroff2022near}.  The classification in dimension $4$ was also completed by Gr{\" u}nbaum and Sreedharan \cite{grunbaum1967enumeration} via different methods, though they also considered polytopes with no pairs of disjoint facets.  There are $158{,}817$ order types on $9$ points, which yield $186$ possible combinatorial types of $5$-polytopes with $9$ facets; the $111$ combinatorial types with at least two pairs of disjoint facets are listed in \cite[Appendix A]{burcroff2022near}.  Over $14$ million order types on $10$ points yield a list of $265$ possible combinatorial types of $6$-polytopes with $10$ facets.  Note that not all of these combinatorial types are realized; this is merely a short list of possible types from which we determine those that are realized as compact Coxeter polytopes.  


\subsection{Computational methods}\label{subsec: computation}

We now roughly outline the computational steps used to classify compact Coxeter polytopes of a given combinatorial type $G$.  We begin with a complete graph on $d + k$ vertices with unknown edge weights, and describe the process by which we assign edge weights such that every possible Coxeter diagram of a $d$-polytope with $d+4$ facets is constructed.\hfill\vspace{0.2cm}
{\bf 1. Select a set of dihedral angles taking values at most $\frac{\pi}{6}$\vspace{0.2cm}}

For each combinatorial type, we begin by restricting the dihedral angles which can be at most $\frac{\pi}{6}$ using the combinatorial structure and local determinants.  In practice, each combinatorial type generated by the methods in the previous section can be limited to having at most five such dihedral angles.  We then iterate over all subsets of these angles, and examine the Coxeter diagrams for which this set is precisely the set of dihedral angles of size at most $\frac{\pi}{6}$.  Though at this stage we have not fixed the exact size of these angles, knowing that they have size at most $\frac{\pi}{6}$ yields restrictions on the remaining dihedral angles.\hfill\vspace{0.2cm}\\
{\bf 2. Assign edge weights within Lann{\'e}r diagrams of size $4$ and $5$\vspace{0.2cm}}

The subdiagrams of a Coxeter diagram corresponding to a missing face were classified by Lann{\'e}r \cite{lanner1950complexes} and are known as Lann{\'e}r diagrams.  The maximum size of a  Lann{\'e}r diagram is $5$, and there are finitely many Lann{\'e}r diagrams of size $4$ or $5$.  In particular, if we restrict to only those vertices in the Coxeter diagram contained in Lann{\'e}r diagrams of size $4$ or $5$, the resulting subdiagram is obtained by gluing Lann{\'e}r diagrams from this list.  We can thus iterate over the possible Lann{\'e}r diagrams to assign weightings to edges within such a subdiagram. \hfill\vspace{0.2cm}\\
{\bf 3. Assign the dihedral angles of size at least $\frac{\pi}{5}$\vspace{0.2cm}}

There are finitely many assignments of the remaining dihedral angles, i.e., those not contained within a Lann{\'e}r diagram of size $4$ or $5$.  We iterate over all these possibilities, with the additional restriction that all subdiagrams not containing a missing face must be elliptic.  We furthermore require that subdiagram induced by any two Lann{\'e}r diagrams is connected, lest this subdiagram be superhyperbolic.\hfill\vspace{0.2cm}\\
{\bf 4. Solve for the remaining Coxeter diagram edge weights\vspace{0.2cm}}

At this stage, the only quantities which have not been assigned are the dihedral angles of size less than $\frac{\pi}{6}$ and distance between divergent facets.  For the former, the weight of the corresponding edge in the Coxeter diagram must be a real numbers in the range $\left[\cos\left(\frac{\pi}{6}\right), 1\right) = \left[\frac{\sqrt{3}}{2}, 1\right)$.   The weight of each edge corresponding to two divergent facets must be a real number in the range $(1,\infty)$.  Restricting to these ranges, we find all solutions to an appropriately chosen system of equations, which encodes certain rank conditions.  We do so using the computer algebra system {\tt Mathematica}.\hfill\\
{\bf 5. Check the signs of the eigenvalues of the resulting Gram matrix.\vspace{0.2cm}}

For each of the solutions to the system of equations, we obtain an associated \emph{Gram matrix}.  It follows from the theory of hyperbolic polytopes that it is sufficient to check that the resulting matrix has exactly $1$ negative eigenvalue and that its rank is $d + 1$. If these conditions are met, we can conclude that this Coxeter diagram corresponds to Coxeter $d$-polytope with $d+k$ facets of combinatorial type $G$.  

The code implementing the process described above is publicly available at \\\url{https://github.com/agburcroff/Cox_d-Polytopes_with_dplus4_Facets.git}. 


\section{Coxeter Polytope Dimension Bounds}

We first present a bound on compact Coxeter $3$-free polytopes, i.e., polytopes where every missing face is of size $2$.  We utilise this bound along with the classification of compact Coxeter $d$-polytopes with few facets to place upper bounds on the dimensions of polytopes with $d+k$ facets for $5 \leq k \leq 10$.  To our knowledge, the best previous bound on the dimension for each of these classes of polytopes was Vinberg's bound $d \leq 29$ for all compact Coxeter polytopes.


The proof of our dimension bound for $3$-free polytopes is refinement of Vinberg's proof that simple Coxeter polytopes have dimension at most $29$.  This involves studying weightings of the planar angles of such polytopes.  A \emph{planar angle} of a polytope is a pair of a vertex and a two-dimensional face containing the vertex.  Based on such a weighting, it is possible to derive the following dimension bound.

\begin{prop}[\protect{\hspace{1sp}\cite[Prop. 6.2]{vinberg1985hyperbolic}}]\label{prop: planar angle bound}
Let $P$ be a $d$-dimensional compact Coxeter polytope and $c > 0$.  We assume that the planar angles of $P$ can be endowed with weights such that the sum of the weights of the planar angles at the vertex is at most $cd$ and that the sum of the weights of the planar angles of any $2$-dimensional face with $k$ vertices is at least $5 - k$. Then $d < 8c + 6$.
\end{prop}

We construct a weighting on the planar angles of a compact Coxeter $3$-free polytope such that the unique nonzero planar angle for each vertex has weight $1$ and that each $2$-dimensional face with $4$ vertices has a nonzero planar angle.  Thus we can derive the following dimension bound from \autoref{prop: planar angle bound} with $c = 1$.


\begin{thm}\label{thm: 3-free bound}
There are no compact $3$-free Coxeter hyperbolic polytopes of dimension $14$ or higher.
\end{thm}



While this result may be of interest in its own right, we presently make use of this result to bound the dimension of polytopes with few facets.  

\begin{defn}
Let $D(k)$ denote the maximum positive integer for which a compact Coxeter $D(k)$-polytope with $D(k) + k$ facets exists.
\end{defn}

By Vinberg's result \cite[Theorem 4]{vinberg1981absence}, we have $D(k) \leq 29$ for all $k$.  For $k \leq 4$, the exact value of $D(k)$ is known.

\begin{thm}\label{thm: low k bounds}\hspace{-0.5em}\footnote{Anna Felikson and Pavel Tumarkin have shown in unpublished notes that $D(5) \leq 8$ using a fairly involved argument [Tumarkin, personal communication (2021)].}
We have 
\begin{itemize}
    \item $D(1) = 4$, due to Lann{\'e}r \emph{\cite{lanner1950complexes}};
    \item $D(2) = 5$, due to Kaplinskaja \emph{\cite{kaplinskaya1974discrete}} and Esselmann \emph{\cite{esselmann1994kompakte}};
    \item $D(3) = 8$, due to Esselmann \emph{\cite{esselmann1994kompakte}};
    \item $D(4) = 7$, due to Felikson and Tumarkin \emph{\cite{felikson2008d}}.
\end{itemize}
\end{thm}

 Thus, we begin our investigation with $k = 5$, and proceed until the bounds obtained by our methods are no stronger than the general bound of Vinberg.  We derive the following improved bounds.
 
 \begin{thm}\label{thm: polytope dim bounds}
 We have $D(5) \leq 9$, $D(6) \leq 12$, $D(7) \leq 15$, $D(8) \leq 18$, $D(9) \leq 22$, and $D(10) \leq 26$.
 \end{thm}
 
 The argument proceeds by first proving a linear bound on $d$ having slope $4$ (with respect to $k$), then applying the classification of polytopes with fewer facets to slightly improve these bounds in particular cases.  The initial linear bound is obtained by first iterating part of the argument used by Felikson and Tumarkin to bound $D(4)$ \cite{felikson2008d}, which yields \autoref{lem: face bound}.

 \begin{lem}\label{lem: face bound}
If $P$ contains a missing face of size $\ell > 2$, then
$$D(k) \leq \max_{1 \leq i \leq k - 1} D(i) + \ell - 1\,.$$
\end{lem}
 
Combining these results with our dimension bound of $13$ on $3$-free polytopes, we obtain the following dimension bound.

\begin{thm}\label{thm: partial dim bound}
For $k \geq 5$, we have
$$D(k) \leq  \max\left\{\max\{ D(i) + 4: i < k\}, \min\{k-1,13\}\right\}\,.$$
\end{thm}
\begin{proof}
Fix a Coxeter $d$-polytope $P$ with $d+k$ facets.  If $P$ is not $3$-free, then it contains a missing face of order $3$, $4$, or $5$.  The first bound then follows from \cref{lem: face bound}.
\end{proof}

In order to improve the bounds given by \autoref{thm: partial dim bound} to those in \autoref{thm: polytope dim bounds}, we rely heavily on the classification of compact hyperbolic Coxeter $d$-polytopes with at most $d+4$ facets.  The general form of these fairly technical arguments is as follows:
\begin{itemize}
\item Suppose that a compact hyperbolic Coxeter $d$-polytope $P$ has $d+k$ facets and a missing face of size $\ell$. We consider proper subsets $\Sigma_i$ of the facets corresponding to this missing face.
\item  Let $P(\Sigma_i)$ be the face of the polytope formed by intersecting the facets in $\Sigma_i$.  Under certain easily-checked conditions, a face of a Coxeter polytope is itself a Coxeter polytope. We then choose $\Sigma_1$ such that $P(\Sigma_1)$ is a Coxeter polytope, and hence it must be a $(d-|\Sigma_1|)$-polytope with at most $d+k-\ell$ facets.
\item Using the classification of polytopes with few facets, we can determine some properties of the polytope $P(\Sigma_i)$.  Using a result of Felikson and Tumarkin \cite[Corollary 1.1]{felikson2008d}, this yields some restrictions on the dihedral angles between facets not contained in $\Sigma_i$. We can then use these restrictions to choose a new subset of facets $\Sigma_{i+1}$ and again look at the face $P(\Sigma_{i+1})$.
\item We repeat the previous step until we have sufficiently many restrictions on the dihedral angles of $P$ to deduce that no such polytope $P$ exists.
\end{itemize}





\acknowledgements{The author would like to sincerely thank her  master's thesis advisor, Pavel Tumarkin, for his expert support throughout the course of this research. She is also grateful to Anna Felikson, Ruth Kellerhals, Norbert Peyerimhoff, Jiming Ma, and Fangting Zheng for their helpful comments and suggestions.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
