\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
Growing Apollonian Packings
}
\vskip 1cm
\large
Colin Mallows\\
Avaya Labs \\
Basking Ridge, NJ 07920 \\
USA \\
\href{mailto:colinm@avaya.com}{\tt colinm@avaya.com}\\
\end{center}
\vskip .2 in
\begin{abstract}
In two dimensions, start with three mutually tangent circles, with disjoint
interiors (a circle with negative radius has the point at infinity in its
interior). We can draw two new circles that touch these three, and then
six more in the gaps that are formed, and so on. This procedure generates
an (infinite) Apollonian packing of circles. We show that the sum of the
bends (curvatures) of the circles that appear in successive generations
is an integer multiple of the sum of the bends of the original
three circles. The same is true if we start with four mutually tangent
circles (a Descartes configuration) instead of three. Also the integrality
holds in three (resp., five) dimensions, if we start with four or five (resp.
six or seven) mutually tangent spheres. (In four and higher dimensions the
spheres in successive generations are not disjoint.) The analysis in the
three-dimensional case is difficult. There is an ambiguity in how
the successive generations are defined. We are unable to give general
results for this case.
\end{abstract}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}
\newcommand{\mb}{{\mathbf b}}
\newcommand{\mc}{{\mathbf c}}
\newcommand{\me}{{\mathbf e}}
\newcommand{\mh}{{\mathbf h}}
\newcommand{\mx}{{\mathbf x}}
%\newcommand{\m1}{{\mathbf 1}} Doesn't work
\newcommand{\mC}{{\mathbf C}}
\newcommand{\mI}{{\mathbf I}}
\newcommand{\mJ}{{\mathbf J}}
\newcommand{\mR}{{\mathbf R}}
\newcommand{\mS}{{\mathbf S}}
\newcommand{\mT}{{\mathbf T}}
\newcommand{\mV}{{\mathbf V}}
\newcommand{\mW}{{\mathbf W}}
\newcommand{\mX}{{\mathbf X}}
\section{Reflection and the Apollonian group}
We draw on the definitions and analysis in \cite{G1,G3}.
The ``bend" of a circle
or sphere is its curvature, = 1/radius. In $n$ dimensions, a
``Descartes configuration" consists of $n+2$ mutually tangent spheres
with disjoint interiors. The bends $b_i$
of these spheres satisfy the Soddy-Gosset relation (see \cite{G3})
$$
n(\sum b_i^2) = (\sum b_i )^2 .
$$
Thus we can form $n+2$ new Descartes configurations by deleting one of the
spheres, say the $i$-th, and adding a new sphere tangent to the remaining
$n+1$ spheres, whose bend is the other
root of the quadratic equation that is satisfied by $b_i$. We call
this operation ``Descartes reflection". If the bends of the original set of
$n+2$ spheres are contained in the column vector $\mb$, the bends of the $i$-th
new set are in the vector $\mR_i \mb$ where
\begin{equation}
\mR_i = \mI + \frac{2}{n-1} \me_i 1^T - \frac{2n}{n-1}\me_i \me_i^T , \label{eq:Ri}
\end{equation}
where $\mI$ is the unit $(n+2) \times (n+2)$ matrix, the column vector $\me_i$ has $1$ in the $i$-th
position and zeroes elsewhere, and $1$ is a column of 1's. Thus $\mR_i$
is the identity matrix except for the %i%th row, which has
-1 on the diagonal and $2/(n-1)$ elsewhere. (See \cite[Eq.\ 4.1]{G3}.)
Each of these $n+2$ matrices is an involution, and they generate an infinite
Coxeter group which we name ${\cal G}_n$. In all dimensions except 3, there
are no relations
among them except the involutory ones: $\mR_i^2 = \mI$. (See
\cite[Thm.\ 5.2]{G3}). However, in 3 dimensions
there are extra relations $(\mR_i \mR_j)^3 = \mI$ which will cause us
difficulty below. Until further notice, we consider only dimensions
$n =2$ and $n \ge 4$.
A word of length $k$,
$\mW = \mR_{i_1} \mR_{i_2} \cdots \mR_{i_k}$,
in the generators of ${\cal G}_n$ is called {\em reduced} if
$i_j \ne i_{j+1}$ for
$j = 1, \ldots, k-1$. (So all squares have been cancelled). The number of
reduced words of length $k \ge 1$ is clearly $(n+2)(n+1)^{k-1}$.
We will derive the quantities $s_k/s_0$ where
$s_k$ is the sum of the bends of the spheres that are generated in the
$k$th generation of the Apollonian construction.
\section{Starting with a Descartes configuration}
We start with $n+2$ spheres in an $n$-dimensional Descartes configuration,
$n \ne 3$. Since every application of a generator (in a reduced word)
produces exactly one new sphere, the following lemma is clear.
\begin{lemma}
The spheres in the $k$-th generation ($k \ge 1$) are in 1--1 correspondence with reduced
words of length $k$ in the generators of ${\cal G}_n$.
\end{lemma}
\begin{theorem}
In $n$ dimensions ($n \ne 3$) the generating function of the sum of the
bends in the $k$th generation is
$$
G(x) = (1-x)(1-nx)s_0/(1-\theta x + (n+1)x^2)
$$
where $\theta = (n^2 + n + 2)/(n-1)$.
\label{thm1}
\end{theorem}
\begin{proof}
The sum of the bends in the $k$th generation is
\begin{equation}
s_k = \sum \me_{i_1}^T \mR_{i_1} \cdots \mR_{i_k} \mb \label{eq:sk}
\end{equation}
where $\mb$ is the vector containing the bends of the initial configuration,
and the sum is over all sequences $i_1,i_2, \ldots, i_k$ with
$i_j \ne i_{j+1},~~~ j = 1, \ldots, k-1$. We define
$$
\mT = \sum_j \mR_j
$$
Then $\mT = a\mI + b\mJ $
where $\mJ$ is the matrix of all ones, $a = (n^2 - n - 2)/(n-1)$, and
$b = 2/(n-1)$. Let $\mX_k$ be the row vector
$\sum \me_{i_1} \mR_{i_1} \cdots \mR_{i_k}$
where the sum is as in (\ref{eq:sk}).
Then $\mX_0 = 1^T$, $\mX_1 = ((n+3)/(n-1)) 1^T$, and
$$
\mX_{k+1} = \mX_k \mT - (n+1)\mX_{k-1}
$$
By induction, $\mX_k = c_k 1^T$ for some numbers $c_k$ and a little work shows that
$$
c_0 = 1, ~~~~~c_1 = (n+3)/(n-1), ~~~~~ c_{k+1} = \theta c_k - (n+1)c_{k-1}
$$
The theorem follows.
\end{proof}
The coefficients in $G(x)$ are integer multiples of $s_0$ only for
$n = 2, 5$ (our analysis does not relate to $n=3$). We find them to be
\medskip
\begin{tabular}{lrrrrrrrrrr}
& $k=$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
$n=2$ & $s_k/s_0 = $ & 1 & 5 & 39 & 297 & 2259 & 17181 & 130671 & 993825 & 7558587\\
$n=5$ & $s_k/s_0 = $ & 1 & 2 & 15 & 108 & 774 & 5544 & 39708 & 284400 & 2036952
\end{tabular}
\medskip
We remark, without giving details, that in all dimensions (except 3)
a similar (but more tedious) computation shows that the sum of the squares
of the bends in the $k$-th
generation, $t_k$ say, is a multiple of the sum of the squares of the
bends in the zeroth generation, which is $t_0 =(1/n) s_0^2$.
The generating function is
$$
(1-x)(1-nx)t_0/(1-\phi(n)x+(n+1)x^2)
$$
where $\phi(n) = (n^3 + 5n + 2)/(n-1)^2$. In two dimensions the multiples are integers:
\medskip
\begin{tabular}{lrrrrrrrr}
$k=$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
$t_k/t_0 =$ & 1 & 17 & 339 & 6729 & 133563 & 2651073 & 52620771 & 1044462201
\end{tabular}
\medskip
In two dimensions the average bend in the $k$th generation, $\bar{s_k}$, is
asymptotically $C_1 \mu ^k$ where $\mu = (4+\sqrt 13 )/3$, and the average
squared bend $\bar{t_k}$ is asymptotically $C_2 \nu ^k$ where
$\nu = (10+\sqrt 97 )/3$. Thus the
coefficient of variation of the bends in the $k$th generation is asymptotically
$C \lambda ^k -1$ where $\lambda = 3\nu/\mu^2 = 1.029427$. One can conjecture
that some transformation (such as taking logs) would give a limiting
distribution. But since the
higher moments are not independent of the starting configuration, it is not
clear whether such a limit can exist independent of the initial configuration.
For all $n \ge 4$ as $k \rightarrow \infty$ the coefficient of variation of the
bends in the $k$th generation is of the form $C(1+\epsilon)^k -1$ where
$\epsilon$ is a small fraction.
\section{Starting with $n+1$ spheres}
Now suppose we start with only $n+1$ mutually tangent spheres,
$S_1, \ldots, S_{n+1}$, with
bends summing to $s_0^-$, and with the sum of squares of the bends being
$t_0^-$. By the Soddy-Gosset result, the two spheres
that each touch all of these $n+1$ spheres have bends
$a, a' = (s_0^- \pm q)/(n-1)$ where $ q^2 = n(s_0^-)^2 - (n-1)t_0^-$.
Pick one of
these two spheres and call it $S_{n+2}$, with bend $b_{n+2} = a$.
Then $S_1, \ldots, S_{n+1}, S_{n+2}$ form
a Descartes configuration, and the sum of the bends of this configuration
is $s_0 = s_0^- + a$. The first derived generation of spheres
consists of $S_{n+2}$ and the sphere obtained by reflecting this sphere in the
original $n+1$ spheres.
The sum of these two bends is thus $s_1^- = a + a' = 2s_0^-/(n-1)$.
Again, the following lemma is clear.
\begin{lemma} For $k \ge 1$ the spheres in the $(k+1)$st generation,
starting from $n+1$ spheres, are in 1--1 correspondence with reduced words
in the generators of the group ${\cal G}_n$
of these two forms: (i) words of length $k$ whose right-most element is
not $\mR_{n+2}$ (ii) words of length $k+1$ whose right-most element is
$\mR_{n+2}$.
\end{lemma}
The number of such words is $2(n+1)^k$.
\begin{theorem}
The generating function of the sum of the bends in the $k$th generation, starting from $n+1$ spheres in $n$ dimensions, is
$$
G^-(x) = (1-x)(1-((n^2+1)/(n-1))x)s_0^-/(1-\theta x + (n+1)x^2)
$$
\label{thm2}
\end{theorem}
\begin{proof}
Computations using the explicit form of $\mR_i$ show that
$s_2^- = 2((n+1)/(n-1))^2 s_0^-$. For
$k \ge 2$ we have
$$
s_{k+1}^- = \sum \me_{i_1}^T \mR_{i_1} ... \mR_{i_k} (\mb + \mR_{n+2} \mb)
$$
where the sum is over $i_j \ne i_{j+1} ,~~~ i_k \ne n+2$. Adding and
subtracting the words that have $i_k = n+2$, we get
\begin{equation}
s_{k+1}^- = s_k + s_k' - \sum \me_{i_1}^T \mR_{i_1} ... \mR_{i_k-1} (\mR_{n+2} \mb + \mb) \label{eq:sk-}
\end{equation}
where $s_k'$ is the sum of the bends in the $k$th generation, starting
from the full Descartes configuration with $b_{n+2} = a'$. In the
summation in (\ref{eq:sk-}), we have $i_{k-1} \ne n+2$, so this sum is just
$s_k^-$. Also, using the Soddy-Gosset equation,
$s_0 + s_0' = (2n/(n-1))s_0^-$,
so that for $k \ge 1$
$$
(s_{k+1}^- + s_k^-)/s_0^- = (2n/(n-1))s_k/s_0 = (2n/(n-1))c_k
$$
in the notation of Theorem~\ref{thm1}. Hence the required generating function satisfies
$$
(1+x)\frac{G^-(x)}{s_0^-} = 1 + \frac{n+1}{n-1}x + \frac{2nx}{n-1}\left(\frac{G(x)}{s_0} -1 \right)
$$
and the theorem follows.
\end{proof}
For $n=2$ we find
\medskip
\begin{tabular}{lrrrrrrrrr}
$k=$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
$s_k^-/s_0^- = $ & 1 & 2 & 18 & 138 & 1050 & 7986 & 60738 & 461946 & 3513354
\end{tabular}
\medskip
\noindent and for $k \ge 3$ these numbers satisfy the same recurrence as in the
$(n+2)$-sphere-start case. The generating function is $(1-x)(1-5x)/(1-8x+3x^2)$.
Again, for $k \ge 3$ the sum of the squares of the bends in the $k$th
generation, $t_k^-$, satisfies the same recurrence as in the
$(n+2)$-start case; for $n=2$ we find
\medskip
\begin{tabular}{lrrrrrrrr}
$k=$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
$t_k^-/t_0^- =$ & 1 & 2 & 66 & 1314 & 26082 & 517698 & 10275714 & 203961186
\end{tabular}
\medskip
\noindent and the generating function is $(1-18x+29x^2)/(1-20x+3x^2)$.
\section{Three dimensions}
The analogous problems for the 3-dimensional case, starting with either
four or five tangent spheres, are much more difficult. Counting reduced
words is challenging, and there is an
indeterminacy in how the spheres are counted.
The reflection operators are $5\times 5$ matrices as in Eq.~(\ref{eq:Ri}), with all elements
in $\{ -1,0,1\}$.
They satisfy
\begin{equation}
\mR_i^2 = \mI,~~~ (\mR_i \mR_j)^3 = \mI \label{eq:ident}
\end{equation}
In \cite{G3} {\em reduced} words were defined as those that
\begin{verse}
(i) contain no subwords of the form $\mR_j \mR_j$, \\
(ii) contain no subwords of the form $\mV_1 \mV_2 \cdots \mV_{2m}$ in which
$\mV_1 = \mV_3, \mV_{2j} = \mV_{2j+3}$ for $1 \le j \le m-2$, and $\mV_{2m-2} = \mV_{2m}$.
\end{verse}
Thus all possible cancellations using the identities in (\ref{eq:ident})
have been performed.
The definition implies that every subword of a reduced word is also reduced.
It is not the case that spheres correspond to reduced words.
To see this, assume the zeroth generation is a five-sphere Descartes
configuration in which the bends are $0,0,1,1,1$. This consists of two
parallel planes, distant 2 apart, with three unit spheres between them,
touching each other and both planes. The first derived generation,
obtained by Descartes reflection of each of these spheres, using
single-letter words $\mR_i$,
consists of five spheres, with bends $1,1,1,3,3$. The second derived
generation, obtained from words $\mR_i \mR_j$ with $i \ne j$,
has 20 spheres, with bends $1^6 3^6 4^6 6^2$. In this
generation the 20 spheres form 10 pairs, with the spheres in a pair
($\mR_i \mR_j$ and $\mR_j \mR_i$)
touching each other. The bends of the touching pairs are
$(1,1)^3, (3,4)^6, (6,6)^1$. Thus we have formed an additional 10 Descartes
quintuples, each containing three spheres of generation zero and two spheres
of generation 2. These quintuples will be obtained (in two ways, each)
in generation 3, (e.g., as $\mR_i \mR_j \mR_i = \mR_j \mR_i \mR_j$) but
these generation-3 quintuples will not contain any new spheres. Also,
applying ``reflection" to one of these ``extra" quintuples we find only
three new spheres, not four. It is unclear
to which generation the spheres that are obtained by reflection from these
``extra" quintuples belong. There are two arguments:
(a) They belong to the fourth generation because they are obtained by
reflection using the quintuples that are obtained from words in the third
generation.
(b) They belong in the third generation because they can be obtained
by reflection using the ``extra" quintuples that are formed at the second
generation.
Similar ambiguities arise in succeeding generations.
Thus we are faced with four distinct problems:
\begin{verse}
(1) count reduced words of length $k$.\\
(2) count spheres, using strategy (a).\\
(3) count quintuples, assuming ``extra" quints belong in
the generation in which they first appear (i.e. strategy (b).\\
(4) count spheres, using strategy (b).
\end{verse}
There are similar problems when we start with only four touching spheres
instead of five.
We have been unable to make much progress on these problems. We have the
following results for small values of k, starting with five spheres.
\medskip
\begin{tabular}{lrrrrrrr}
generation & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\\
reduced words & 1 & 5 & 20 & 80 & 300 & 1140 & 4260\\
unique words & 1 & 5 & 20 & 70 & 240 & 780 & 2730\\
\\
no. spheres (a) & 5 & 5 & 20 & 60 & 210 & 690 & 3330\\
$s_k/s_0$ (a) & 1 & 3 & 20 & 108 & 630 & 3570 & 20460\\
$t_k/t_0$ (a) & 1 & 6 & 77 & 732 & 7278 & 71634 & 707076\\
\\
quintuples (b) & 1 & 5 & 30 & 120 & 480 & 2070 & \\
no. spheres (b) & 5 & 5 & 20 & 90 & 330 & 1290 & \\
$s_k/s_0$ (b) & 1 & 3 & 20 & 174 & 1170 & 8454 & \\
$t_k/t_0$ (b) & 1 & 6 & 77 & 1278 & 15978 & 216366 &
\end{tabular}
\section{How these results were computed}
We remind the reader that we are in three dimensions.
We use the ``curvature-center coordinates" defined in \cite[Defn.\ 3.2]{G3}.
A sphere with bend $b$ and center $\mx = (x_1, x_2, x_3)$ is described
by the vector $(b, b\mx)$. The plane $\mh^T \mx = p$ has c-c coordinates
$(0,\mh)$, and does not uniquely define the plane; we could avoid this
by using the ``augmented c-c coordinates" defined in \cite{G3} but this is not
necessary since in our calculations there will never be more than two
planes. The spheres in a Descartes configuration are
described by a $5 \times 3$ matrix $\mC$ whose rows are the c-c coordinates
of the various spheres. The operation of reflection of the $i$th sphere
in this configuration replaces $\mC$ by $\mR_i\mC$.
We start with the special Descartes configuration described by the matrix
$$
\mC = \left(\begin{array}{cccc}
1 & 2r & 0 & 0 \\
1 & -r & 1 & 0 \\
1 & -r & -1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & -1
\end{array}
\right)
$$
where $r$ is $1/\sqrt 3$. To save space and computational effort (using
the statistical language Splus)
we encode a row $(b,bx,by,bz)$ as the integer
$10^7b + 10^4bx/r +10^2by +bz$. Thus the
starting configuration is described by the column vector
$\mc = (10020000,9990100,9989900,1,-1)^T$. After reflection
by $\mR_i$ the configuration is $\mR_i \mc$.
For $k = 1,...,7$ we formed a list of the types of reduced
words of length $k$. Thus for $k=3$ we have
121 and 123; for $k=4$ we have 1213, 1231, 1232, 1234. For
$k=5,6,7$ we find 12,39,139 types, respectively. For
each type, we consider the words that are formed when each of 1, 2, etc.
are replaced by generators $\mR_i, \mR_j, \cdots$ in all possible ways. To get
the number of unique words, duplicates
are eliminated using the identities (4). Thus
$\mR_1\mR_2\mR_1$ and $\mR_2\mR_1\mR_2$
are counted as distinct reduced words, but as the same unique word.
Now we compute the coded coordinates of the last sphere that is added when each
of these products of generators is applied to the base configuration. The
list of coded spheres is then culled to eliminate duplicates. This gives the
coded coordinates of spheres formed using strategy (a).
To compute the number of spheres in the $k$th generation using
strategy (b), we need to count spheres that are added by reflection from
the ``extra" quintuples. Each (reduced) word of length $k$ that contains $j$
sub-words of type 121 (=212) will be an ``extra" word in generation $k-j$.
These words do not provide extra spheres in generation $k-j$, but have
progeny in succeeding generations.
Computation finds the numbers of types in the following table. Note
that the type 12131 is counted as having just one 121 substring, not two,
because the word ABACA equals BABCA and ABCAC, and appears as a single ``extra"
word (in two ways) in generation 4.
\medskip
\begin{tabular}{lrrrrrrrr}
generation & 0& 1& 2& 3& 4& 5& 6& 7\\
\\
total no. types & 1& 1& 1& 2& 4& 12& 39& 139\\
\\
types with no 121s & 1& 1& 1& 1& 2& 5& 14& 43\\
with one 121 substring & & & & 1& 2& 7& 24& 83\\
with two 121 substrings & & & & & & & 1& 13\\
\\
``extra" types & & & 1& 2& 8& 37 & & \\
total no. types (b) & 1& 1& 2& 3& 10& 42 & &
\end{tabular}
\section{Open problems}
In all dimensions we do not know how the higher moments behave
(they do not depend only on $s_0$). It is possible that
for each starting configuration, some transformation of the bends might have
a limiting distribution, which possibly might be independent of the
starting configuration, but our numerical results are not extensive enough
to allow us to make any conjectures. In three dimensions, all four of the
problems listed above remain open. We have not done any computations
for a four-sphere starting configuration, but expect that the method we used
in section 3 will work here.
\section{Acknowledgement}
Thanks to a referee for simplifying my proofs of Theorems~\ref{thm1}
and \ref{thm2}, and for a very careful reading of my manuscript.
\begin{thebibliography}{9}
\bibitem{G1} R. L. Graham, J. C. Lagarias, C. L. Mallows, A. R. Wilks,
and C. Yan. Apollonian circle packings: Geometry and Group theory I.
The Apollonian Group. {\em Discrete Comput. Geom.} {\bf 34} (2005),
547--585.
\bibitem{G3} R. L. Graham, J. C. Lagarias, C. L. Mallows, A. R. Wilks,
and C. Yan. Apollonian circle packings: Geometry and Group theory
III. Higher Dimensions. {\em Discrete Comput. Geom.} {\bf 35} (2006),
37--72.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15.
\noindent \emph{Keywords: } circle-packing.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received September 26 2008;
revised version received January 2 2009.
Published in {\it Journal of Integer Sequences}, January 3 2009.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}