\documentclass[12pt]{article}
\usepackage{amsfonts}

\newcommand{\Aut}{\mathop{\mathrm{Aut}}}
\newcommand{\BA}{\mathop{\mathrm{BAut}}}
\newcommand{\bU}{\mathbb{U}}
\newtheorem{theorem}{Theorem}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{unnumber}{}
\renewcommand{\theunnumber}{\relax}
\newtheorem{prepf}[unnumber]{Proof}
\newenvironment{pf}{\prepf\rm}{\endprepf}
\newcommand{\qed}{\qquad$\Box$}

\begin{document}
\title{Some isometry groups of Urysohn space}
\author{P. J. Cameron and A. M. Vershik\\[10mm]
\small School of Mathematical Sciences, Queen Mary, University of London,\\
\small Mile End Road, London E1 4NS, U.K.\\[5mm]
\small St.~Petersburg Department of Steklov Institute of Russian Academy of
Sciences,\\
\small Fontanka 27, St Petersburg 191011, Russia}
\date{}
\maketitle

\begin{abstract}
We construct various isometry groups of Urysohn space (the unique complete
separable metric space which is universal and homogeneous), including
abelian groups which act transitively, and free groups which are dense in
the full isometry group.
\end{abstract}

\section{Introduction}

In a posthumously-published paper, P.~S.~Urysohn~\cite{urysohn} constructed
a remarkable complete separable metric space $\bU$ which is both
\emph{homogeneous} (any isometry between finite subsets of $\bU$ can be
extended to an isometry of $\bU$) and \emph{universal} (every complete
separable metric space can be embedded in $\bU$). This space is unique up
to isometry.

The second author~\cite{vershik}, ~\cite{vershik1} showed that
$\bU$ is both the generic complete metric space with distinguished
countable dense subset (in the sense of Baire category) and the
random such space (with respect to any of a wide class of
measures).

In this paper, we investigate the isometry group $\Aut(\bU)$ of $\bU$, and
construct a few interesting subgroups of this group.

Our main tool is an analogous countable metric space $Q\bU$, the
unique universal countable homogeneous metric space with rational
distances which was also have been considered in ~\cite{urysohn}.
The existence of and uniqueness of $Q\bU$ follows from the
arguments used to establish the existence and uniqueness of $\bU$
(see~\cite{vershik1}). Alternatively, this can be deduced from the
fact that the class of finite metric spaces with rational
distances has the amalgamation property, from which
Fra\"{\i}ss\'e's Theorem~\cite{fraisse} gives the result. Now
$\bU$ is the completion of $Q\bU$ (see~\cite{vershik}). In
particular, any isometry of $Q\bU$ extends uniquely to~$\bU$. Our
notation suggests that $Q\bU$ is ``rational Urysohn space''.

Let $\Aut(Q\bU)$ and $\Aut(\bU)$ be the isometry groups of $Q\bU$ and $\bU$.
We show that $\Aut(Q\bU)$ is dense in $\Aut(\bU)$ (in the natural
topology, induced by the product topology on $\bU^\bU$). We also show that
$Q\bU$ has an isometry which permutes all its points in a single cycle (indeed,
it has $2^{\aleph_0}$ conjugacy classes of such isometries). The closure of
the cyclic group generated by such an isometry is an abelian group which acts
transitively on $\bU$, so that $\bU$ carries an abelian group structure
(indeed, many such structures). Moreover,
the free group of countable rank acts as a group of isometries of $Q\bU$ which
is dense in the full isometry group (and hence also is dense in $\Aut(\bU)$).


The space $Q\bU$ is characterised by the following property: If $A,B$ are
finite metric spaces with rational distances (we say \emph{rational metric
spaces}, for short) with $A\subseteq B$, then any embedding of $A$ in $Q\bU$
can be extended to an embedding of $B$. It is enough to assume this in
the case where $|B|=|A|+1$, in which case it take the more convenient form:
\begin{description}
\item{($*$)} If $A$ is a finite subset of $Q\bU$ and $g$ a function from $A$ to
the rationals satisfying
  \begin{itemize}
  \item $g(a)\ge 0$ for all $a\in A$,
  \item $|g(a)-g(b)|\le d(a,b)\le g(a)+g(b)$ for all $a,b\in A$,
  \end{itemize}
then there is a point $z\in Q\bU$ such that $d(z,a)=g(a)$ for all $a\in A$.
\end{description}

Furthermore, $Q\bU$ is homogeneous (any isometry between finite
subsets of~$Q\bU$ extends to an isometry of $Q\bU$), and every
countable rational metric space can be embedded isometrically in
$Q\bU$.

There is an evident parallel between the theory of universal
metric space and universal graph as well as theory of other
universal objects.

\section{$\Aut(Q\bU)$ is dense in $\Aut(\bU)$}

The topology on the group $\Aut(\bU)$ of isometries of $\bU$ is that induced
by the product topology on $\bU^\bU$. In particular, $g_n\to g$ if and only if,
for any finite sequence $(u_1,\ldots,u_m)$ of points and any $\epsilon>0$,
there exists $n_0$ such that $d(g_n(u_i),g(u_i))<\epsilon$ for $1\le i\le m$
and $n\ge n_0$.

With this topology, $\Aut(Q\bU)$ is a dense subgroup of $\Aut(\bU)$.
Here is a proof. It suffices to show the following property of $Q\bU$:

\begin{prop}
Given $\epsilon>0$ and $v_1,\ldots,v_n,v_1',\ldots,v_{n-1}',v_n''\in Q\bU$
such that $(v_1,\ldots, v_{n-1})$ and $(v_1',\ldots,v_{n-1}')$ are isometric
and
\[|d(v_i',v_n'')-d(v_i,v_n)|<\epsilon,\]
there exists $v_n'\in Q\bU$ such that $(v_1,\ldots,v_n)$ and
$(v_1',\ldots,v_n')$ are isometric and  $d(v_n',v_n'')<\epsilon$.
\end{prop}

Assuming this for a moment, we complete the proof as follows. We are given
an isometry $g$ of $\bU$ and points $u_1,\ldots,u_m\in \bU$.
Choose points $v_1,\ldots,v_m\in Q\bU$ with $d(v_i,u_i)<\epsilon/4m$. Now
using  the above proposition, we inductively choose points $v_1',\ldots,v_m'$
so that $(v_1,\ldots,v_m)$ and $(v_1',\ldots,v_m')$ are isometric and
$d(v_i',g(u_i))<i\epsilon/m$. For suppose that $v_1',\ldots, v_{n-1}'$ have
been  chosen. Choose any point $v_n''\in Q\bU$ with
$d(g(u_n),v_n'')<\epsilon/4m$. Then
\[d(u_i,u_n)-\epsilon/2m<d(v_i,v_n)<d(u_i,u_n)+\epsilon/2m,\]
and
\[d(g(u_i),g(u_n))-(4i+1)\epsilon/4m<d(v_i',v_n'')
<d(g(u_i),g(u_n))+(4i+1)\epsilon/4m,\]
so
\[|d(v_i',v_n'')-d(v_i,v_n)|<(4i+3)\epsilon/4m\le(4n-1)\epsilon/4m.\]
So we may apply the Proposition to choose $v_n'$ with
$d(v_n',v_n'')<(4n-1)\epsilon/4m$. Then $d(v_n',g(u_n))<n\epsilon/m$, and
we have finished the inductive step. At the conclusion, we have
$d(v_n',g(u_n))<n\epsilon/m\le\epsilon$ for $1\le n\le m$.

Now we find an isometry of $Q\bU$ mapping $v_i$ to $v_i'$ for $1\le i\le m$
(by the homogeneity of~$Q\bU$), and the proof is complete.\qed

\paragraph{Proof of the Proposition} We have to extend the set
$\{v_1',\ldots,v_{n-1}',v_n''\}$ by adding a point $v_n'$ with prescribed
distances to $v_1',\ldots,v_{n-1}'$ and distance less than $\epsilon$ to
$v_n''$. So it is enough to show that these requirements don't conflict,
that is, that
\[|d(v_n',x)-d(v_n',y)|\le d(x,y)\le d(v_n\,x)+d(v_n\,y)\]
for $x,y\in\{v_1',\ldots,v_{n-1}',v_n''\}$. There are no conflicts if
$x,y\ne v_n''$: this follows from the fact that the points $v_1,\ldots,v_n$
exist having the required distances. So we may assume that $x=v_i'$ and
$y=v_n''$, in which case the consistency follows from the hypothesis.\qed

\section{$\BA(\bU)$ is dense in $\Aut(\bU)$}

For a metric space $M$, we define $\BA(M)$ to be the group of all
\emph{bounded} isometries of $M$ (those satisfying $d(x,g(x))\le k$ for all
$x\in M$, where $k$ is a constant). Clearly it is a normal subgroup of
$\Aut(M)$, though in general it may be trivial, or it may be the whole
of $\Aut(M)$.

We show that $\BA(Q\bU)$ is a dense proper subgroup of
$\Aut(Q\bU)$: in other words, any isometry between finite subsets
of $Q\bU$ can be extended to a bounded isometry of $Q\bU$. This is
immediate from the following lemma.

\begin{lemma}
Let $f$ be an isometry between finite subsets $A$ and $B$ of $Q\bU$, satisfying
$d(a,f(a))\le k$ for all $a\in A$. Then $f$ can be extended to an isometry
$g$ of $Q\bU$ satisfying $d(x,g(x))\le k$ for all $x\in Q\bU$.
\label{bddense}
\end{lemma}

\begin{pf}
Suppose that $f:a_i\mapsto b_i$ for $i=1,\ldots,n$, with $d(a_i,b_i)\le k$.
It is enough to show that, for any point $u\in Q\bU$, there exists $v\in Q\bU$
such that $d(b_i,v)=d(a_i,u)$ for all $i$ and $d(u,v)\le k$. For then we can
extend $f$ to any further point; the same result in reverse shows that we can
extend $f^{-1}$, and then we can construct $g$ by a back-and-forth argument.

The point $v$ must satisfy $d(b_i,v)=d(a_i,u)$ and $d(u,v)\le k$.
We must show that these requirements are consistent; then the
existence of $v$ follows from the extension property of $Q\bU$.
Clearly the consistency conditions for the values $d(b_i,v)$ are
satisfied. So the only possible conflict can arise from the
inequality
\[|d(v,u)-d(v,b_i)|\le d(u,b_i)\le d(v,u)+d(v,b_i).\]
We wish to impose an upper bound on $d(v,u)$, so a conflict could arise only
if a lower bound arising from the displayed equation were greater than $k$,
that is, $|d(v,b_i)-d(u,b_i)|>k$, or equivalently, $|d(u,a_i)-d(u,b_i)|>k$.
But this is not the case, since
\[|d(u,a_i)-d(u,b_i)|\le d(a_i,b_i)\le k.\]
\end{pf}

\section{A cyclic isometry of $Q\bU$}

The following theorem is true:

\begin{theorem}
There is an isometry $g$ of $Q\bU$ such that $\langle g\rangle$ is transitive
on~$Q\bU$. The induced isometry of $\bU$ has the property that every orbit of
$\langle g\rangle$ is dense in $\bU$.
\end{theorem}

\begin{pf} The second statement follows trivially from the first.
So it is enough to show that there is an isometry $\sigma$ of $Q\bU$ such that
$\langle\sigma\rangle$ is transitive on $Q\bU$. The analogous statement for the
universal homogeneous integral metric space was proved in~\cite{hco},
and we require this in the proof.

If a metric space has a cyclic automorphism, we can identify its points with
the integers so that the automorphism is the shift. Then the metric is
completely determined by the function $f(i)=d(i,0)$ on the non-negative
integers; for $d(i,j)=f(|j-i|)$. The function should satisfy the constraints
\begin{description}
\item{(a)} $f(i)\ge0$, with equality if and only if $i=0$.
\item{(b)} $|f(i)-f(j)|\le f(i+j)\le f(i)+f(j)$ for all $i,j$.
\end{description}
Now the cyclic metric space given by such a function is isometric to $Q\bU$ if
and only if $f$ has the following property:
\begin{description}
\item{(c)} given any function $h$ from $\{1,\ldots,k\}$ to the positive
rationals satisfying
\[|h(i)-h(j)|\le f(|i-j|)\le h(i)+h(j)\]
for $i,j\in\{1,\ldots,k\}$, there exists a natural number $N$ such that
$h(i)=f(N-i)$ for all $i\in\{1,\ldots,k\}$.
\end{description}

Under those conditions a distance matrix (see ~\cite{vershik1})
$\{d(i,j)\}, i,j \in \Bbb Z$ is \emph{Toeplitz matrix} (e.g.
commutes with the shift on $\Bbb Z$). So, we will call a function
satisfying (a) and (b) a \emph{Toeplitz function} (from the form
of the metric, $d(i,j)=f(|i-j|)$, and say that it is
\emph{universal} if it also satisfies (b).

It is worth mentioning that condition (c) is a special case of
necessary and sufficient condition for universality of the
arbitrary distance matrix over real numbers which was given in
~\cite{vershik1}; here universality of matix means that completion
of the set $\Bbb Z$ under the metric defined by given distance
matrix is universal Urysohn space.

We denote by $RT_n$ the space of non-negative rational $n$-tuples satisfying
condition (b) for $i,j\in\{1,\ldots,n\}$. Given $f\in RT_n$, we say that
the $m$-tuple $(h(1),\ldots,h(m))$ is \emph{$f$-admissible} if
\[|h(i)-h(i+k)|\le f(k)\le h(i)+h(i+k)\]
for $1\le i< i+k\le m$ and $k\le n$. We note that if $h$ is $f$-admissible,
then it is admissible with respect to the restriction of $f$ to
$\{1,\ldots,n'\}$ for any $n'\le n$.

We need to show that, if $h$ is $f$-admissible, then there is some
prolongation $f^*$ of $f$ such that $h$ is $f^*$-admissible and $(f,h)$
is an initial segment of a Toeplitz function. This is proved for integral
metric spaces in~\cite{hco}. For the rational case, multiply everything by
the least common multiple of the denominators, apply the integral result,
and divide by $d$.
\qed
\end{pf}

The proof shows that, in the sense of Baire category, almost all rational
Toeplitz functions are universal, so that almost all rational
metric spaces which admit cyclic transitive isometry groups are isometric
to~$Q\bU$. It gives further information too:

\begin{cor}
The group $\Aut(Q\bU)$ contains $2^{\aleph_0}$ conjugacy classes of isometries
which permute the points in a single cycle. Moreover, representatives of
these classes remain non-conjugate in $\Aut(\bU)$.
\end{cor}

\begin{pf} It is clear that, if cyclic isometries $g$ and $h$ are
conjugate, then the functions $f_g$ and $f_h$ describing them as in the
above proof are equal. For, if $h=k^{-1}gk$, then
\[f_h(n)=d(x,h^n(x))=d(x,k^{-1}g^nk(x))=d(k(x),g^nk(x))=f_g(n).\]
But the set of functions describing cyclic isometries of $Q\bU$ is residual,
hence of cardinality~$2^{\aleph_0}$.\qed
\end{pf}

The cyclic isometries constructed in this section have the property that
$d(x,g(x))$ is constant for $x\in Q\bU$, and hence this holds for all
$x\in \bU$. In particular, these isometries are bounded.



\section{An abelian group of exponent~$2$}

To extend this argument to produce other groups acting regularly
 (=freely and transitively) on~$Q\bU$,
it is necessary to change the definition of a Toeplitz function so that
the metric is defined by translation in the given group. We give here one
simple example.

\begin{prop}
The countable abelian group of exponent~$2$ can act regularly as
an isometry group of $Q\bU$.
\end{prop}

\begin{pf}
This group $G$ has a chain of subgroups $H_0\le H_1\le H_2\le\cdots$ whose
union is $G$, with $|H_i|=2^i$. We show that, given any $H_i$-invariant
rational metric on $H_i$ and any $h\in H_{i+1}\setminus H_i$, we can
prescribe the distances from $h$ to $H_i$ arbitrarily (subject to the
consistency condition) and extend the result to an $H_{i+1}$-invariant
metric on $H_{i+1}$. The extension of the metric is done by translation
in $H_{i+1}$: note that $H_{i+1}\setminus H_i$ is isometric to $H_i$,
since $d(h+h',h+h'')=d(h',h'')$ for $h',h''\in H_i$. Now the resulting
function is a metric. All that has to be verified is the triangle
inequality. Now triangles with all vertices in $H_i$, or all vertices in
$H_{i+1}\setminus H_i$, clearly satisfy the triangle inequality. Any
other triangle can be translated to a triangle containing $h$ and two
points of $H_i$, for which the triangle inequality is equivalent to the
consistency condition for extending the metric to $H_i\cup\{h\}$.\qed
\end{pf}

As before, for such a group $G$ almost all $G$-invariant metrics
(in the sense of Baire category) are isometric to $Q\bU$.

\section{Transitive abelian subgroups of the group $Iso(\bU)$}

The constructions of the last two sections have the following consequence:

\begin{prop}
There are transitive abelian groups of isometries of $\bU$ of infinite
exponent, and transitive groups of exponent~$2$.
\end{prop}

\begin{pf} Let $G$ be one of the abelian groups previously constructed,
and $\overline{G}$ its closure in $\Aut(\bU)$. Since the orbits of $G$ are
dense, it is clear that $\overline{G}$ is transitive. Moreover, as the closure
of an abelian group, it is itself abelian. For, if $h,k\in\overline{G}$,
say $h_i\to h$ and $k_i\to k$; then $h_ik_i=k_ih_i\to hk=kh$.
Similarly, if $G$ has exponent~$2$, then so does $\overline{G}$.\qed
\end{pf}

What is the structure of the closure of action of the
 infinite cyclic group $\Bbb Z$?
Since there are many choices for action of $\Bbb Z$, we must
expect that their closures will not all be alike. In particular,
there should be some choices of $\Bbb Z$ such that $\overline{\Bbb
Z}$ is torsion-free, and others for which it is not.

\section{Regular actions of other groups on $\bU$ and on the universal graph $R$}

The universal graph $R$ (see definition f.e. \cite{Ca}) could be
considered as a universal homogeneous metric space in the class of
metric spaces with the distances which takes values $\{0,1,2\}$;
graph $R$ could be isometrically imbed to $\bU$. But there is a
natural more deeper parallelism between theory of universal metric
space and theory of universal graph. There is one-way relation
between transitive group actions on $Q\bU$ (or, more generally,
group actions on $\bU$ with a dense orbit) and transitive actions
on the random (universal) graph $R$, as given in the following
result.

\begin{prop}
Let $G$ be a group acting on Urysohn space $\bU$ and $X$ is a
countable dense orbit. Then $G$ preserves the structure of the
random graph $R$ on~$X$ (which is definied below).
\end{prop}

\begin{pf}
Partition the positive real numbers into two subsets $E$ and $N$
such that, for any $C,\epsilon>0$, there are consecutive intervals
of length at most $\epsilon$ to the right of $C$ with one
contained in $E$ and the other in $N$. (For example, take a
divergent series $(a_n)$ whose terms tend to zero, and put
half-open intervals of length $a_n$ alternately in $E$ and $N$.)

We define a graph on $X$ by letting $\{x,y\}$ be an edge if $d(x,y)\in E$,
and a non-edge if $d(x,y)\in N$. Clearly this graph is $G$-invariant; we must
show that it is isomorphic to the random graph $R$.

Let $U$ and $V$ be finite disjoint sets of points of $X$, and let
the diameter of $U\cup V$ be $h$ and the minimum distance between
two of its points be $m$. Choose $C>h/2$ and $\epsilon<m/2$, and
find consecutive intervals $I_E$ and $I_N$ as above. Let $U\cup
V=\{w_1,\ldots,w_n\}$. For all values $a_i \in I_E\cup I_n, i=1
\ldots n $, the consistency condition
\[|a_i-a_j|\le d(w_i,w_j)\le a_i+a_j\]
is always satisfied. So choose the values such that $a_i$ is in
the interior of $I_E$ if $w_i\in U$, and in the interior of $I_n$
if $w_i\in V$. Let $z$ be a point of $U$ with $d(z,w_i)=a_i, i=1
\ldots n $. Since $X$ is dense, we can find $x\in X$ such that
$d(x,z)$ is arbitrarily small; in particular, so that $d(x,w_i)$
is in $I_E$ (resp. $I_N$) if and only if $d(z,w_i)$ is. Thus $x$
is joined to all verties in $U$ and to none in $V$. This condition
characterises $R$ as a countable graph.
\end{pf}

\begin{cor}
If a countable group $G$ can act on Urysohn space $\bU$ with dense
orbits then this group can act transitively on the universal graph
$R$.
\end{cor}

The converse is not true. A special case of the result of Cameron
and Johnson~\cite{cj} shows that a sufficient condition for a
group $G$ to act regularly on the universal graph $R$ is that any
element has only finitely many square roots. In a group with odd
exponent, each element has a unique square root. So any such group
acts regularly on $R$. But we have the following:

\begin{prop}
The countable abelian group of exponent~$3$ cannot act on $\bU$ with a dense
orbit, and in particular cannot act transitively on $Q\bU$.
\end{prop}

\begin{pf} Suppose that we have such an action of this group $A$. Since the
stabiliser of a point in the dense orbit is trivial, we can identify the
points of the orbit with elements of $A$ (which we write additively).

Choose $x\ne 0$ and let $d(0,x)=\alpha$. Then $\{0,x,-x\}$ is an equilateral
triangle with side~$\alpha$. Since $\bU$ is universal and $A$ is dense, there
is an element $y$ such that $d(x,y),d(-x,y)\approx\frac{1}{2}\alpha$ and
$d(0,y)\approx\frac{3}{2}\alpha$. (The approximation is to within a given
$\epsilon$ chosen smaller than $\frac{1}{6}$. Then the three points $0,y,x-y$
form a triangle with sides approximately $\frac{3}{2}\alpha$,
$\frac{1}{2}\alpha$, $\frac{1}{2}\alpha$, contradicting the triangle
inequality.
\end{pf}

\section{Unbounded isometries of $\bU$}

The subgroup $\BA(\bU)$ is not the whole isometry group, because
unbounded isometries exist. The simplest way to see this is to
mention thatf.e. euclidean space $R^n$ can be imbedded to $\bU$ in
such a way that the group of motions $Iso(R^n$ is monomorphically
imbedded to $Iso(\bU)$ and the group of rotations of $R^n$
extended to the unbounded isometry. But we will give a direct
construction of such isometry. We are grateful to Jaroslav
Ne\v{s}et\v{r}il for the following argument.

\begin{prop}
There exist unbounded isometries of~$Q\bU$ (and hence of $\bU$).
\end{prop}

The proof depends on a lemma.

\begin{lemma}
Let $A$ be a finite subset of $Q\bU$ and let $g$ be a function on $A$
satisfying  the consistency conditions ($*$). Then the diameter of the set
\[\{z\in Q\bU: d(z,a)=g(a)\hbox{ for all }a\in A\}\]
is twice the minimum value of $g$.
\end{lemma}

\begin{pf} Let $z_1$ and $z_2$ be two points realising $g$. Consider
the problem of adding $z_2$ to the set $A\cup\{z_1\}$. The consistency
conditions for $z_2$ are precisely those for $z_1$ together with the
conditions
\[|d(z_2,z_1)-d(z_2,a)|\le d(z_1,a)\le d(z_2,z_1)+d(z_2,a)\]
for all $a\in A$. Since $d(z_1,a)=d(z_2,a)=g(a)$, the only non-trivial
restriction is $d(z_1,z_2)\le 2d(z_1,a)=2g(a)$, which must hold for all
$a\in A$.\qed
\end{pf}

\paragraph{Proof of the Proposition} We construct an isometry $f$ of $Q\bU$ by
the standard back-and-forth method, starting with any enumeration of $Q\bU$.
At odd-numbered stages we choose the first point not in the range of $f$
and select a suitable pre-image. At stages divisible by~$4$ we choose the
first point not in the domain of $f$ and select a suitable image. This
guarantees that the isometry we construct is a bijection from $Q\bU$ to
itself.

At stage $4n+2$, let $\bU$ be the domain of $f$. Choose an unused point $z$
whose least distance from~$\bU$ is $n$. Now the diameter
of the set of possible images of $z$ is $2n$; so we can choose a
possible image $f(z)$ whose distance from~$z$ is at least $n$. Then the
constructed isometry is not bounded.\qed

\bigbreak

We can improve this argument to construct an isometry $g$ such that all
powers of $g$ except the identity are unbounded. In fact, even more is true:

\begin{lemma}
There are two isometries $a,b$ of $Q\bU$ which generate a free group, all of
whose non-identity elements are unbounded isometries.
\end{lemma}

\begin{pf}
We begin by enumerating $Q\bU=(x_0,x_1,\ldots)$. We follow the argument we used
to show that unbounded isometries exist. We construct $a$ and $b$
simultaneously, using the even-numbered stages for a back-and-forth argument
to ensure that both are bijections, and the odd-numbered stages to ensure
that any word in $a$ and $b$ is unbounded. The first requirement is done as
we have seen before.

Enumerate the words $w(a,b)$ in $a$ and $b$ and their inverses. (It suffices
to deal with the cyclically reduced words, since all others are conjugates of
these.) We show first how to ensure that $w(a,b)\ne1$. At a given stage,
suppose we are considering a word $w(a,b)$. Choose a point $x_i$ such that
neither $a$ nor $b$, nor their inverses, has been defined on $x_j$ for $j\ge
i$. Suppose that $w$ ends with the letter $a$. Since there are infinitely
many choices for the image of $x_i$ under $a$, we may choose an image $x_j$
with $j>i$. Now define the action of the second-last letter of the word on
$x_j$ so that the image is $x_k$ with $k>j$. Continuing in this way, we end
up with a situation where $w(a,b)x_i=x_m$ with $m>i$. So $w(a,b)\ne1$.

To ensure that $w(a,b)$ is unbounded, we must do more. Enumerate the words so
that each occurs infinitely often in the list. Now, the $k$th time we revisit
the word $w$, we can ensure (as in our construction of an unbounded isometry)
that $d(x_i,w(a,b)x_i)\ge k$. Thus $w(a,b)$ is unbounded.
\end{pf}

\section{A dense free subgroup of $\Aut(\bU)$}

We can now use a trick due to Tits~\cite{bldgs} to show that there is a dense
subgroup of $\Aut(\bU)$ which is a free group of countable rank.

\begin{theorem}
There is a subgroup $F$ of $\Aut(Q\bU)$ which acts faithfully and homogeneously
on $Q\bU$ and is isomorphic to the free group of countable rank.
\end{theorem}

\begin{pf}
Since the free group $F_2$ contains a subgroup isomorphic to $F_\omega$,
choose a group $H$ with free generators $h_i$ for $i\in\mathbb{N}$, such that
$H\cap\BA(Q\bU)=1$. Enumerate the pairs of isometric $n$-tuples of elements of
$Q\bU$, for all $n$, as $(\alpha_0,\beta_0)$, $(\alpha_1,\beta_1)$, \dots~.
Now, for each $i$, Lemma~\ref{bddense} shows that we can choose
$n_i\in\BA(Q\bU)$ such that $n_ih_i(\alpha_i)=\beta_i$. Let $F$ be the group
generated by the elements $n_1h_1, n_2h_2, \ldots$~. Clearly $F$ acts
homogeneously on $Q\bU$. We claim that $F$ is free with the given generators.
Suppose that $w(n_ih_i)=1$ for some word $w$. Since $\BA(Q\bU)$ is a normal
subgroup, we have $nw(h_i)=1$ for some $n\in\BA(Q\bU)$. Since $n$ is bounded
and $w(h_i)$ unbounded, this is impossible. In fact this argument shows that
all the non-identity elements of $F$ are unbounded isometries.
\end{pf}

\begin{thebibliography}{9}

\bibitem{hco}
P. J. Cameron, Homogeneous Cayley objects,
\textit{Europ. J. Combinatorics} \textbf{21} (2000), 831--838.

\bibitem{cj}
P. J. Cameron and K. W. Johnson,
An essay on countable B-groups,
\textit{Math. Proc. Cambridge Philos. Soc.} \textbf{102} (1987), 223--232.

\bibitem{Ca}
P. J. Cameron, The random graph,
 \textit{The mathematics of Paul Erdos II}
ed. R.L.Graham and J.Nesetril. Berlin Springer-Verlag, (1997),
333-351.

\bibitem{fraisse}
R. Fra\"{\i}ss\'e,
Sur certains relations qui g\'en\'eralisent
l'ordre des nombres rationnels,
\textit{C. R. Acad. Sci. Paris} \textbf{237} (1953), 540--542.

\bibitem{bldgs}
J. Tits,
\textit{Buildings of Spherical Type and Finite BN-Pairs},
Lecture Notes in Math. \textbf{382}, Springer--Verlag, Berlin, 1974.

\bibitem{urysohn}
P. S. Urysohn,
Sur un espace metrique universel,
\textit{Bull. Sci. Math.} \textbf{51} (1927), 1--38.

\bibitem{vershik}
A. M. Vershik,
A random metric space is a Uryson space (Russian),
\textit{Dokl. Akad. Nauk} \textbf{387} (2002), 733--736.

\bibitem{vershik1}
A. M. Vershik, The Universal and Random Metric spaces,
\textit{Russian Math. Surv.} \textbf{356} (2004), No.2, 65--104.
\end{thebibliography}

\end{document}