% LaTeX Article Template - customizing page format
%
% LaTeX document uses 10-point fonts by default. To use
% 11-point or 12-point fonts, use \documentclass[11pt]{article}
% or \documentclass[12pt]{article}.
\documentclass{article}
\usepackage{amssymb}
\usepackage{latexsym}
% Set left margin - The default is 1 inch, so the following
% command sets a 1.25-inch left margin.
\setlength{\oddsidemargin}{0.25in}
% Set width of the text - What is left will be the right margin.
% In this case, right margin is 8.5in - 1.25in - 6in = 1.25in.
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.25in}
% Set height of the text - What is left will be the bottom margin.
% In this case, bottom margin is 11in - 0.75in - 9.5in = 0.75in
\setlength{\textheight}{8in}
% Set the beginning of a LaTeX document
\begin{document}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newenvironment{proof}[1][Proof]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\hfill$\Box$\end{trivlist}}
\newenvironment{definition}[1][Definition]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{example}[1][Example]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remark]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{notation}[1][Notation]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{question}[1][Question]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}
\def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}
\def\R{{\Bbb R}}
\def\V{{\Bbb V}}
\def\N{{\Bbb N}}
\def\Z{{\Bbb Z}}
\def\Q{{\Bbb Q}}
\def\F{{\mathbb F}}
\def\p{{\mathcal P}}
\def\f{{\mathcal F}}
\def\g{{\mathcal G}}
\def\t{{\mathcal T}}
\def\m{{\mathcal M}}
\def\n{{\mathcal N}}
\def\b{{\mathcal B}}
\def\h{{\mathcal H}}
\def\l{{\mathcal L}}
\def\j{{\mathcal J}}
\def\no{\noindent}
\def\to{{\mathcal T}(\Omega)}
\def\fx{{\mathcal F}(X)}
\def\nh{|\!|}
\title{An oscillation theorem for groups of isometries\footnote{Key words
and phrases: Distortion; oscillation; Ramsey theory; groups of isometries;
Polish groups. 2000 Mathematics Subject Classification: Primary
03E15, 03C15, 05D10, 22F50; Secondary: 37F20, 46B03, 54C25,
54D80, 54E40.}}
% Enter your title between curly braces
\author{Greg Hjorth\footnote{Partially supported by NSF grant DMS
0140503}} % Enter your name between curly braces
\date{\today} % Enter your date or \today between curly braces
\maketitle
\abstract{This paper answers a question raised by
Vladimir Pestov.
Let $G$ be a non-trivial group of isometries
of a complete, separable metric space. Let $\hat{G}$ be the
semi-group arising from its completion with respect to the left
uniformity. Then there is a uniformly continuous function from
$\hat{G}$ to the unit interval which assumes both extreme points
on any non-empty right ideal.}
\bigskip
\bigskip
This paper has one main theorem.
If $G$ is a group of isometries of a space $X$,
$\hat{G}$ the
semi-group that arises as its completion in a certain natural sense,
then we can find uniformly continuous functions on $X^2$ that
display high oscillation on the image of any $\rho\in \hat{G}$.
There are some details to be added to make this statement precise,
but they are unsurprising, and can be postponed.
There are some further issues about when $X^2$ can be
replaced by $X$, and what one can say for specific classes of
$X$ and $G$, and these need also to be eventually addressed.
Before any of these
housekeeping chores, I want to give an
extended aside on
two
seemingly
unrelated results in combinatorics,
which can actually be
viewed as lying at the heart of this theorem.
Although these results are
well known, the proofs are sufficiently short to
be included, and the proof of the second of these
will be needed at a later point.
\begin{theorem} (Ramsey's theorem) \label{ramsey}
Let
\[f: \N^2\rightarrow \{0, 1\}.\]
Then there is an infinite
\[A\subset \N\]
and $i\in \{0, 1\}$
such that for any $a**2$.
There are various proofs for this theorem.
The specific proof given below will be important.
\begin{theorem} (Folklore) \label{devlin}
There is a function
\[f: \Q\rightarrow \{0, 1\}\]
such that for any order preserving injection
\[\rho: \Q\rightarrow \Q\]
there exist
\[q_1< q_2, r_1k(n)$ and then $n''$ with $k(n'')>\ell(n')$
to obtain
\[f(x_{k(n)}, x_{\ell(n')})=0,\]
\[f(x_{k(n'')}, x_{\ell(n')})=1.\]
\end{proof}
The conclusions of Ramsey's and Devlin's theorem
contrast one another. We obtain one kind of behavior for
the ordering of $(\N, <)$ and the total opposite for
$(\Q, <)$.
A distinctive property of $(\Q, <)$ is that for any two
finite increasing sequences of the same size
\[q_10$, of arity $1$ with
\[R_i=\{i+1\}.\]
In this way distinct points have distinct quantifier free types,
and thus the only way for q.f.type$_\m(\vec a)$ to equal
q.f.type$_\m(\vec b)$ is for the sequences to be equal and then the
identity map is the required automorphism.
\end{example}
\begin{example} A non-example is provided by $(\N; <)$. Clearly the
quantifier free
type of the sequence $(2, 3)$ is the same as $(5, 10)$, since all we can
say is that the
first point
is smaller than another and these two sequences have that much in common.
However there is no automorphism of $(\N; <)$ other than the trivial one
which fixes every point.
\end{example}
\begin{definition} For $\m$ a countable relational structure and
$\vec a$ a finite sequence from $\m$, we say that $b$ is
{\it in the algebraic closure of $\vec a$,} written
\[b\in{\rm acl}_{\m}(\vec a),\]
if the image of $b$ under Aut$(\m, \vec a)$, the group of automorphisms of
$\m$ fixing $\vec a$ pointwise, is finite.
\end{definition}
Note that in the case that $\m$ is ultrahomogeneous, q.f.type$_\m(\vec
a^\smallfrown b)$
determines orbit in the automorphism group, and thus $b\in {\rm
acl}_\m(\vec a)$
if and only there are just finitely many $c$ with
\[{\rm q.f.type}_\m(\vec a^\smallfrown b) =
{\rm q.f.type}_\m(\vec a^\smallfrown c).\]
\begin{theorem} \label{ultra}
Let $\m$ be an ultrahomogeneous structure with $|{\rm Aut}(\m)|>1$. Then
there is a
pair $\vec a =(a_0, a_1)$ from $\m$ and
\[f: \m^2\rightarrow \{0, 1\}\]
such that for any monomorphism
\[\rho : \m\rightarrow \m\]
we can find $\vec b, \vec c$ in the image of $\rho$, both having the same
quantifier free type
as $\vec a$, but with
\[f(\vec b)=0, \]
\[f(\vec c)=1.\]
\end{theorem}
\begin{proof}
We split the proof into cases, the first being the simplest.
\medskip
\noindent{\bf Case(I):} Every element of $\m$ is in acl$(\emptyset)$, the
algebraic closure
of the empty sequence.
\medskip
Fix some $\pi\in {\rm Aut}(\m)$ not equal to the identity.
Fix $a\in \m$ with $\pi(a)\neq a$ and let $b=\pi(a)$.
Our case assumptions imply that every point has only finitely many other
points with
the same quantifier free type. Since every monomorphism is injective and
preserves
quantifier free type, it follows that all monomorphisms are onto, and so
we have $a$ and $b$ in the image of any such $\rho$. Thus if we simply define
\[f(a, x) =0\]
\[f(b, x)=1\]
for any $x\in\m$, and $f$ arbitrary in all other cases, then $f$ along
with the
quantifier free type of $(a, a)$ is as required.
\medskip
\noindent{\bf Case(II):} Some $a\in\m$ is not in the algebraic closure
of the empty sequence.
\medskip
Let $A$ be the collection of all points in $\m$ with the same
quantifier free type as $a$. There is a further split into subcases.
\medskip
\noindent{\bf Subcase(IIa):} ${\rm acl}_\m(a)\cap A$ is infinite.
\medskip
This implies that for any $b\in A$ we again have ${\rm acl}_\m(b)\cap A$
infinite,
since the automorphism group of $\m$ acts transitively on $A$.
Let $(c_i)_{i\in\N}$ enumerate $A$ and choose successively points
$d_i\neq e_i\in A$ such that
\[d_i, e_i\in {\rm acl}_\m(c_i)\cap A\]
and
\[d_i, e_i\notin\{d_j, e_j: j***j$. $f$ is again arbitrary off of
the type of $(a_0, a_1)$.
The claim is that $f$ and the type of $(a_0, a_1)$ is as required, and
so suppose $\rho:\m\rightarrow\m$ is a monomorphism. We let
\[x_i =\rho(a_0),\]
\[x_j =\rho(a_1).\]
There are two possibilities, the first being $ij$ and
\[f(\rho(d), \rho(a_1))=1\]
as required.
The other possibility is $i>j$, but then, similarly,
since $a_1\notin {\rm acl}_\m(a_0)$ we
can replace $a_1$ with some suitable $d$ to make
$f(\rho(a_0), \rho(d))=0$.
\end{proof}
\subsection{Examples and counterexamples
for first order logic and beyond}
\label{firstorder}
This section differs from the other parts of the paper in
having considerable prerequisites from logic which are
not always made explicit.
This section can be bypassed. None of the results
resurface later in the paper.
We consider various ways in which \ref{ultra}
might be modified.
From the point of view of a logician it is natural to consider the situation
of elementary embeddings between first order structure. While there are two
theorems which follow directly from \ref{ultra}, there is a counterexample to
the most naive formulations.
\begin{example} We build a structure $\m$ admitting many pairs with the
same first order type and
such that for any
set of tuples with the same type
\[S\subset \m^2\]
and
\[f: S\rightarrow \{0, 1\}\]
we can find an elementary embedding of
$\m$ into itself with the image homogeneous for
$f$.
We first let $\{Q_n:n\in \N\}$ be mutually dense co-dense subsets
of the half open interval $(0, 1]$ such that any two
distinct rationals are separated by some $Q_n$; we do this so
that for any distinct non-overlapping finite sets $I_0, I_1\subset \N$ the
intersection
\[\bigcup_{n\in I_0} Q_n \setminus (\bigcup_{n\in I_1} Q_n)\]
is dense in the interval $(0, 1)$.
(The required $Q_n$'s can be produced by a routine
diagonalization argument, which we omit.)
We then extend these subsets to $P_n\subset \R$ by setting
$\ell + r\in P_n$ if and only if $r\in Q_n$, where $\ell\in \Z$,
$r\in (0, 1]$.
We let $\m$ be the
structure whose underlying set is $\Q^+$, the positive
rationals, equipped with the usual ordering $<$ of the
rationals, but also the countably many unary predicates,
$\{P_n: n\in \N\}$,
with the interpretation given above.
Note then that for each $q\in \m$ and semi-open interval
$(\ell, \ell +1]$, $\ell \in \N$,
there is exactly one $q'\in(\ell, \ell +1]$
with the same type as $q$.
Now given $S\subset \m^2$ consisting of
pairs of the same type, we can find some $q, q'\in \Q$ such that
$S(a,b)$ implies $a\equiv q$ mod $\Z$ and $b\equiv q'$ mod $\Z$.
After possibly
replacing $S$ by its reflection we can assume
$S(x_0, x_1)\Rightarrow x_0 < x_1$. Then let
\[f: S\rightarrow \{0, 1\}.\]
Thus the domain of $f$ consists of all pairs
\[(\ell + q, k + q')\]
which have $\ell + q < k + q'$.
From $f$ we define a new function
\[f_\N: [\N]^2\rightarrow \{0, 1\}\]
with
\[f_\N(\ell, k)=f(\ell + q, k + q').\]
Applying Ramsey's theorem we find a
\[A\subset \N\]
and a single $i\in \{0, 1\}$
such that whenever $k<\ell $ are both in $A$
\[f_\N(k, \ell)=i.\]
%We can assume $0\notin A$.
We let
\[k_00$ we let
\[{\cal O}(z_0,..., z_m, y_0,..., y_m, \epsilon)\]
be the set of
$\rho\in{\rm In}(X)$ with
\[d(\rho(z_i), y_i)<\epsilon\]
at each $i\leq m$, and we give In($X$) the topology
with the basis all open sets of this form.
Isom($X$) is then given the induced subspace topology.
\end{definition}
\begin{lemma}
If $X$ is separable and completely metrizable, then
both {\rm In}($X$) and {\rm Isom}($X$) are Polish in the indicated topology.
\end{lemma}
\begin{proof} Let
$\{x_i: i\in \N\}$ be some arbitrary dense subset of
$X$. We define $D$ on Isom($X$) with
\[D(\pi_1, \pi_2) =
\sum_{n\in \N} 2^{-n} {\rm max}(1, d (\pi_1(x_n), \pi_2 (x_n)) +
d(\pi_1^{-1}(x_n), \pi_2^{-1} (x_n)))\]
and $\hat{D}$ on In($X$) by
\[\hat{D}(\rho_1, \rho_2)=
\sum_{n\in \N} 2^{-n}{\rm max}( 1,d(\rho_1(x_n), \rho_2(x_n))).\]
It is routine to verify that these metrics have the required
properties of completeness and separability.
\end{proof}
\begin{definition}
For $G\leq {\rm Isom}(X)$ a subgroup, we let
$\hat{G}$ be its closure in In($X$).
\end{definition}
Even when $G$ is a group, there is no necessity for
its closure in the semi-group In($X$) to form a group.
For instance, if $X=\N$ and $d$ is the complete metric,
then for $G=S_\infty$ the group of all permutations of
$\N$ we have $\hat{G}$ equal to all injections from
$\N$ to $\N$. In general we also have
$\hat{G}$ much smaller than
In($X$) even when $G$ equals Isom($X$). For instance
if $X$ equals $\N$ with $d(m, n)=|m-n|$, then the
isometry group is trivial, whilst In($X$) consists
of infinitely many possible shifts.
For the rest of this section fix some complete
separable metric space $(X, d)$ and let $G$ be some
group of isometries.
\begin{definition} For $\rho_0\in \hat{G}$ we let
$\j(\rho_0)$ be the $\hat{D}$ closure of the set
\[\{\rho_0\cdot \pi: \pi\in G\}.\]
\end{definition}
\begin{lemma} \label{I}
$\rho$ is in $\j(\rho_0)$ if and only if for every
$\epsilon >0$ and $x_1, ..., x_m\in X$ there exists
$\pi\in G$ such that
\[d(\rho_0(\pi(x_i)), \rho(x_i))<\epsilon\]
at every $i\leq m$.
\end{lemma}
\begin{proof}
At once from the definition of the topology.
\end{proof}
\begin{lemma} \label{II}
Let $\rho_0\in \hat{G}$ and use
$X_0$ to denote $\rho_0[X]$.
Let $x_1, ..., x_m\in X, y_1, ..., y_m\in X_0$.
Then the following three things are equivalent:
\leftskip 0.4in
\noindent(i) There exists $\rho\in \{\rho_0\cdot \pi:
\pi\in G\}$ with
\[d(\rho(x_i), y_i)<\epsilon\]
all $i\leq m$.
\noindent (ii) There there exists $\rho\in \j(\rho_0)$ with
\[d(\rho(x_i), y_i)<\epsilon\]
all $i\leq m$.
\noindent (iii) There exists
$\pi\in G$ with
\[d(\pi(x_i), y_i)<\epsilon\]
all $i\leq m$.
\leftskip 0in
\end{lemma}
\begin{proof}
(i) and (ii) are clearly equivalent in virtue of the
definition of $\j(\rho_0)$, thus it suffices to show
(ii) if and only if (iii).
The only if direction is immediate from
$\rho_0$ being in the $\hat{D}$-closure of
$G$, and so let us assume instead that $\pi\in G$ and
$d(\pi(x_i), y_i)<\epsilon$
all $i\leq m$.
Let $z_i$ be such that $\rho_0(z_i)=y_i$ all $i\leq m$.
Choose $\sigma_n\in G$ with $\sigma_n\rightarrow \rho_0$ in
$\hat{G}$; this gives in particular that at each $i$
\[\sigma_n(z_i)\rightarrow y_i\]
at each $i$, and then since $G$ acts by isometries
\[\sigma_n^{-1}(y_i)\rightarrow z_i,\]
and then at large enough $n$
\[d(\sigma_n^{-1}(\pi(x_i)), z_i)\leq
d(\sigma_n^{-1}(\pi(x_i)), \sigma_n^{-1}(y_i)) +
d(\sigma_n^{-1}(y_i), z_i)\]
\[= d(\pi(x_i), y_i) +
d(\sigma_n^{-1}(y_i), z_i)<\epsilon.\]
Then since $\rho_0$ is an isometry, at large
enough $n$
\[ d(\rho_0(\sigma_n^{-1}(\pi(x_i))), \rho_0(z_i))
=d(\rho_0(\sigma_n^{-1}(\pi(x_i))),y_i)<\epsilon,\]
as required for
$\rho=\rho_0\circ \sigma_n^{-1}$ to
verify the lemma.
\end{proof}
\begin{corollary}
\label{corollaryI}
$\j(\rho_0)$ is closed under multiplication.
\end{corollary}
\begin{proof}
Let $\gamma_0, \gamma_1\in \j(\rho_0)$.
Since $\rho_0$ is a limit of elements in
$G$ we can find sequences $(\sigma_n^0)_n, (\sigma_n^1)_n$
from $G$ with
\[\sigma_n^0\rightarrow \gamma_0,\]
\[\sigma_n^1\rightarrow \gamma_1.\]
Appealing to \ref{I}
we need only show that for all $x_1, ..., x_m\in X$,
$\epsilon>0$,
if we set $y_i=\gamma_0(\gamma_1(x_i)))$, then
we can produce $\pi\in G$ with
\[d(\rho_0(\pi(x_i)), y_i)<\epsilon\]
at each $i\leq m$. By appealing to
\ref{II}, it suffices to show that there is
some $\hat{\pi}\in G$ with
\[d(\hat{\pi}(x_i), y_i)<\epsilon\]
all $i\leq m$.
But if $z_i=\gamma_1(x_i)$, then we obtain
\[\sigma^1_n(x_i)\rightarrow \gamma_1(x_i)\]
and then
\[\sigma^2_n(z_i)\rightarrow \gamma_2(z_i)=y_i\]
by the definition of $\hat{D}$ convergence. From this
and the assumption that each $\sigma_n^1$ is an isometry we
obtain
\[\sigma^1_n\circ \sigma^2_n(x_i)\rightarrow y_i\]
as $n\rightarrow \infty$, and so we take $\hat{\pi}$
to be $\sigma^1_n\circ \sigma^2_n$ for $n$ sufficiently
large.
\end{proof}
\begin{definition} $\j\subset \hat{G}$ is a
{\it right ideal} if it is closed under multiplication on
the right by $G$ and it is closed under composition.
\end{definition}
Thus \ref{corollaryI} shows that any $\j(\rho_0)$ is a
right ideal.
\subsection{The theorem}
\label{biglentil}
%Recall from
%$\S$\ref{lemmas} that we view the semi-group of isometries
%of a space as coming equipped with a canonical topology.
%This also induces a topology on Isom($X$), the group of
%isometries of $X$.
%The new idea in the proof of this theorem is given by the
%following definition.
\begin{definition} Let $G$ be a group of isometries of
$(X, d)$ and $\epsilon, \delta>0$.
For $x,y\in X$ we say that $x$ {\it $\epsilon,\delta$-captures}
$y$ relative to $G$ if there is some $N\in \N$ such that we
cannot find $N$ disjoint balls of the form
\[B_{\epsilon} (\pi(y))\]
for $\pi\in G$ with
\[d(\pi(x), x)<\delta.\]
\end{definition}
Here $B_\epsilon(\pi(y))$ denotes the ball of all points
$z$ with $d(\pi(y), z)<\epsilon$. Thus in loose terms
we could say that $x\:$ $\epsilon,\delta$-captures $y$ if it
not possible to keep $x$ very still while simultaneously moving
$y$ around to many different places.
\begin{theorem}
\label{maintheorem}
Let $(X, d)$ be a complete
metric space. Let $G\leq {\rm Isom}(X, d)$ be a group
of isometries and let $\hat{G}\subset {\rm In}(X, d)$ be
its closure.
Assume $G$ has size bigger than one.
Then there exists $x_0, x_1\in X$ and uniformly continuous
\[f: \overline{\{(\pi\cdot x_0, \pi \cdot x_1):
\pi \in G\}}\rightarrow [0, 1]\]
such that for any $\rho_0\in \hat{G}$ there exist
\[(y_0, y_1), (z_0, z_1)\in \{(\rho_0(\pi(x_0)), \rho_0(\pi(x_1))):
\pi \in G\}\]
with
\[f(y_0, y_1)=0,\]
\[f(z_0, z_1)=1.\]
\end{theorem}
\begin{proof}
It suffices to show
that there is a uniformly continuous
$f: X\times X\rightarrow [0, 3]$ and $x_0, x_1\in X$
such that for any $\rho_0\in \hat{G}$ there are
$\pi_1, \pi_2 \in G$
with
\[f(\rho_0(\pi_1(x_0)), \rho_0(\pi_1(x_1)))<1,\]
\[f(\rho_0(\pi_2(x_0)), \rho_0(\pi_2(x_1)))>2.\]
Given an $f$ with
this property, we can obtained the $f$ as above by truncating to
the interval $[1, 2]$ and subtracting 1.
Thus we head towards constructing
$f: X\times X\rightarrow [0, 3]$.
Once the problem has been put in this form we can always
assume that $G$ is a closed subgroup of Isom($X$), since
this present form of the statement of the theorem will
pass downwards from the closure of $G$ to $G$ itself.
\medskip
{\bf Case(I):} Every $x\in X$ has precompact orbit under
$G$.
\medskip
That means we can write
\[X=\bigcup_{x\in X} C_x,\]
each $C_x\subset X$ with $C_x\supset [x]_G$, compact and
\[\pi[C_x]\subset C_x\]
all $\pi\in G$, and hence
\[\rho[C_x]\subset C_x\]
all $\rho\in \hat{G}$. But since any isometry of a
compact metric space into itself will be onto, it follows that
any $\rho\in \hat{G}$ will actually be an isometry, and
we are done once we choose some $(x_0, x_1)\in X\times X$ with
non-trivial orbit under $G$ and an {\it onto}
uniformly continuous $f: \overline{(\pi(x_0), \pi(x_1)): \pi\in G\}}\rightarrow [0,3].$
\medskip
{\bf Case(II):} Some $x\in X$ does not have precompact orbit
in $X$.
\medskip
Fix such an $x_0$ without precompact orbit. Fix $\epsilon$
such that there are infinitely many disjoint balls of the form
\[B_\epsilon(\pi(x_0))\]
for $\pi\in G$. The rest of the argument involves rather messy
approximations, but in general terms we want to replace the notion
of algebraic closure by the notion of being
$\frac{\epsilon}{20},\frac{\epsilon}{100}$-captured. To avoid
constantly needing to mention these unpleasant constants, from now
on we use the following completely ad hoc definition.
\begin{definition} We say that $x$ {\it $\epsilon$-captures}
$y$ if it $\frac{\epsilon}{20},\frac{\epsilon}{100}$-captures
$y$ in the original sense given prior to the statement of the
theorem.
\end{definition}
{\bf Subcase(IIa):} There exists $x_1\in G\cdot x_0$ such that
$x_1$ does not $\epsilon$-capture $x_0$ and
$x_0$ does not $\epsilon$-capture $x_1$.
\medskip
Note that since $G$ acts by isometries, for any $x\in G\cdot x_0$
there exists $x'\in G\cdot x=G\cdot x_0$ with neither of
$x, x'$ $\epsilon$-capturing the other.
Fix such an $x_1$ as in subcase hypothesis.
Let $\{z_n: n\in \N\}$ be dense in $G_\cdot x_0$.
At each $n\in \N$ we define continuous
\[g_n: X\rightarrow [0, 3]\]
by
\[g_n(y)={\rm max}\{0, 3-\frac{150}{\epsilon}
(d(y, B_{\frac{\epsilon}{50}}(z_n)))\}.\]
(Here $d(y, B_{\frac{\epsilon}{50}}(z_n))$ denotes
the infimum over $d(y, z)$ for $z$ chosen with
$d(z, z_n)<\frac{\epsilon}{50}$.)
Thus $g_n$ is uniformly continuous uniformly in
$n$, and constantly assumes the value 3 on
$ B_{\frac{\epsilon}{50}}(z_n)$ and the value
zero outside
$ B_{\frac{\epsilon}{25}}(z_n)$.
We then define $f: X\times X\rightarrow [0,3]$ by
\[f(y, y')=
{\rm max}(0, {\rm sup}\{g_n(y)-{\rm max}_{m\leq n}g_m(y'): n\in \N\}.\]
Given the uniformity of the continuity of the $g_n's$ we obtain
that $f$ is uniformly continuous. Unwrapping the definitions
we have that $f$ constantly assume 3 on
\[ B_{\frac{\epsilon}{50}}(z_n)\times (X\setminus\bigcup_{m\leq n}
B_{\frac{\epsilon}{25}}(z_m))\]
and zero on
\[ (X\setminus\bigcup_{m 0$ with
\[\rho_0(x_0)\in
B_{(\frac{\epsilon}{100}-2\delta)} (z_{m(x_0)}),\]
\[\rho_0(x_1)\in
B_{(\frac{\epsilon}{100}-2\delta)} (z_{m(x_1)}),\]
and $\delta<\frac{\epsilon}{200}$.
Choose $n$ large enough that at each $i\leq k$
\[d(\sigma_n(\pi_i(x_0)), \rho_0(\pi_i(x_0))),\:\:
d(\sigma_n(\pi_i(x_1)), \rho_0(\pi_i(x_1)))<\frac{\epsilon}{200},\]
\[d(\sigma_n(x_0), \rho_0(x_0)), \: \: d(\sigma_n(x_1), \rho_0(x_1))
<\delta.\]
Let $\hp_i=\sigma_n \pi_i \sigma_n^{-1}$,
$\hp_i'=\sigma_n \pi_i' \sigma_n^{-1}$.
Then at each $i\leq k$ we have
\[d(\hp_i(\rho_0(x_0)), \rho_0(x_0))\leq
d(\hp_i(\rho_0(x_0)), \hp_i(\sigma_n(x_0)))
+ d(\hp_i(\sigma_n(x_0)), \sigma_n(x_0))
+ d(\sigma_n(x_0), \rho_0(x_0)),\]
which in virtue of $\hp_i$ being an isometry equals
\[d(\rho_0(x_0), \sigma_n(x_0))
+ d(\hp_i(\sigma_n(x_0)), \sigma_n(x_0))
+ d(\sigma_n(x_0), \rho_0(x_0)),\]
which in turn by the definition of $\hp_i$ equals
\[d(\rho_0(x_0), \sigma_n(x_0))
+ d(\sigma_n(\pi_i(x_0)), \sigma_n(x_0))
+ d(\sigma_n(x_0), \rho_0(x_0)).\]
Then since $\sigma_n$ is an isometry this equals
\[d(\rho_0(x_0), \sigma_n(x_0))
+ d(\pi_i(x_0), x_0)
+ d(\sigma_n(x_0), \rho_0(x_0))\]
\[<\delta + \frac{\epsilon}{100} + \delta
=2\delta + \frac{\epsilon}{100}.\]
A similar calculation gives
\[d(\hp_i(\rho_0(x_1)), \rho_0(\pi_i(x_1)))\leq
d(\hp_i(\rho_0(x_1)), \hp_i(\sigma_n(x_1))) +
d(\hp_i(\sigma_n(x_1)), \rho_0(\pi_i(x_1)))\]
\[=d(\rho_0(x_1), \sigma_n(x_1)) +
d(\hp_i(\sigma_n(x_1)), \rho_0(\pi_i(x_1)))<
\frac{\epsilon}{200} + \frac{\epsilon}{200}
=\frac{\epsilon}{100}.\]
And of course we have the same calculations on the
other side, replacing $\hp_i$ by $\hp_i'$, $x_0$ by
$x_1$, and $x_1$ by $x_0$.
Thus at some high enough $m$ we have
\[d(\hp_i(\sigma_m(x_0)), \rho_0(x_0))<2\delta + \frac{\epsilon}{100},\]
\[d(\hp_i(\sigma_m(x_1)), \rho_0(\pi_i(x_1)))< \frac{\epsilon}{100},\]
\[d(\hp_i'(\sigma_m(x_1)), \rho_0(x_1))<2\delta + \frac{\epsilon}{100},\]
\[d(\hp_i'(\sigma_m(x_0)), \rho_0(\pi_i(x_0)))< \frac{\epsilon}{100}.\]
At this point we can appeal to lemma \ref{II} and find
$\rho_1, ..., \rho_k, \rho_1', ...,\rho_k'\in
\{\rho_0\circ \pi: \pi\in G\}$ such that at each $i$
\[d(\rho_i(x_0), \rho_0(x_0))<2\delta + \frac{\epsilon}{100},\]
\[d(\rho_i(x_1), \rho_0(\pi_i(x_1)))< \frac{\epsilon}{100},\]
\[d(\rho_i'(x_1), \rho_0(x_1))<2\delta + \frac{\epsilon}{100},\]
\[d(\rho_i'(x_0)), \rho_0(\pi_i(x_0)))< \frac{\epsilon}{100}.\]
Then
\[B_{\frac{\epsilon}{25}}(\rho_i(x_1))\subset
B_{(\frac{\epsilon}{25}+\frac{\epsilon}{100})}(\rho_0(\pi_i(x_1)))
=B_{\frac{\epsilon}{20}}(\rho_0(\pi_i(x_1))),\]
and hence
\[B_{\frac{\epsilon}{25}}(\rho_i(x_1))\cap
B_{\frac{\epsilon}{25}}(\rho_j(x_1))=0\]
for $i\neq j$. On the other hand
\[d(\rho_i(x_0), z_{m(x_0)}) \leq d(\rho_i(x_0), \rho_0(x_0))
+ d(\rho_0(x_0), z_{m(x_0)}) \]
\[<
(2\delta + \frac{\epsilon}{100})
+ (\frac{\epsilon}{100}-2\delta)
=\frac{\epsilon}{50}\]
\[\therefore \rho_i(x_0)\in B_{\frac{\epsilon}{50}}(z_{m(x_0)}).\]
Similarly at each $i\neq j$
\[B_{\frac{\epsilon}{25}}(\rho_i'(x_0))\cap
B_{\frac{\epsilon}{25}}(\rho_j'(x_0))=0\]
whilst
\[\rho_i'(x_1)\in B_{\frac{\epsilon}{50}}(z_{m(x_1)}).\]
Since each $z_m$ can be in at most one of the
balls $B_{\frac{\epsilon}{25}}(\rho_i(x_1))$,
$i\leq k$, and since $k>m(x_0)$,
we may find specific $i_0$ with
\[\rho_{i_0}(x_1)\notin B_{\frac{\epsilon}{25}}(z_m)\]
all $m\leq m(x_0)$. Similarly we can fix a $j_0$ with
\[\rho_{j_0}'(x_0)\notin B_{\frac{\epsilon}{25}}(z_m)\]
all $m\leq m(x_1)$. We then let
\[(y_0, y_1)=(\rho_{i_0}(x_0), \rho_{i_0}(x_1)), \]
\[(z_0, z_1)= (\rho_{j_0}'(x_1), \rho_{j_0}'(x_1)).\]
Since $y_1\notin\bigcup_{m\leq m(x_0)} B_{\frac{\epsilon}{25}} (z_m)$
whilst $y_0\in B_{\frac{\epsilon}{50}}(z_{m(x_0)})$ we get
\[f(y_0, y_1)=3,\]
whilst since
$z_0\notin\bigcup_{m\leq m(x_1)} B_{\frac{\epsilon}{25}} (z_m)$
whilst $z_1\in B_{\frac{\epsilon}{50}}(z_{m(x_1)})$ we
alternatively obtain
\[f(z_0, z_1)=0.\]
\medskip
{\bf Subcase(IIb):} There does
{\it not}
exist $x_1\in G\cdot x_0$ with
neither $x_0, x_1$ $\epsilon$-capturing the other.
\medskip
{\bf Subsubcase(IIbi):} The set of $y\in G\cdot x_0$ such that
$x_0$ $\epsilon$-captures $y$ can be covered by finitely many balls of
radius $\frac{\epsilon}{4}$.
\medskip
Fix $N$ such that the $y$'s in $G\cdot x_0$ that are $\epsilon$-captured
by $x_0$ can be covered by $N$ balls of radius $\frac{\epsilon}{4}$. Since
$G$ is acting by isometries we have that for every
$x\in G\cdot x_0$ the set of $y$'s $\epsilon$-captured by
$x$ can be covered by $N$ many balls of radius
$\frac{\epsilon}{4}$.
\medskip
{\bf Claim:} For any $\rho\in \hat{G}$ and $x'\in G\cdot x_0$
there exists $y\in \rho[X]$ with $d(y, x')<\frac{\epsilon}{10}$.
\medskip
{\bf Proof of Claim:} Fix $\sigma_n\rightarrow \rho$ in $G$.
Fix $y_1, ..., y_N, y_{N+1}$ in $G\cdot x_0$ with
\[B_\epsilon(y_i)\cap B_\epsilon(y_j)=0\]
for $i\neq j$.
We then pass to a large enough $M$ that
\[d(\sigma_n(y_i), \sigma_m(y_i))<\frac{\epsilon}{100}\]
all $m, n\geq M$, $i\leq N+1$ and let
\[z=\sigma^{-1}_M(x').\]
By the subsubcase assumptions at (IIbi)
there will be some $i_0\leq N+1$
with $x'$ not $\epsilon$-capturing $\sigma_M(y_{i_0})$. But then
the subcase assumptions at (IIb) we have $\sigma_M(y_{i_0})$
$\epsilon$-capturing $x'=\sigma_M(z)$.
Then for all $n\geq M$
\[
d((\sigma_n\circ \sigma_M^{-1})(\sigma_M(y_{i_0})),
\sigma_M(y_{i_0}))
=d(\sigma_n(y_{i_0}), \sigma_M(y_{i_0}))
<\frac{\epsilon}{100},\]
and thus by $\sigma_M(y_{i_0})$ $\epsilon$-capturing
$x'=\sigma_M(z)$ we have
\[d(\sigma_n(z), x')=d(\sigma_n(\sigma_M^{-1}(x')),
x')<\frac{\epsilon}{20}.\]
Since this happens at all $n$ sufficiently large,
\[d(\rho_{i_0}(z), x')\leq \frac{\epsilon}{20},\]
and we may complete the claim by taking $y=\rho(z)$.
\hfill (Claim$\square$)
\medskip
But now we simply choose $q_0, q_1\in G\cdot x_0$ with
\[B_\epsilon(q_0)\cap B_\epsilon(q_1)=0\]
and define
\[f_0: X\rightarrow [0,3]\]
\[w\mapsto {\rm min}(0, {\rm max}(3, \frac{6}{\epsilon}
d(w, B_{\frac{\epsilon}{2}}(q_1)).\]
We let $x_1$ be arbitrary and define
\[f: \overline{(\pi(x_0), \pi(x_1)): \pi \in G\}}
\rightarrow [0, 3]\]
with $f(w_0, w_1)=f_0(w_0)$.
For any $\rho_0\in \hat{G}$ we can appeal to the claim and
lemma \ref{II} to find $\pi_0, \pi_1\in G$ with
\[\rho_0(\pi_0(x_0))\in B_{\frac{\epsilon}{2}}(q_0), \]
\[\rho_0(\pi_1(x_0))\in B_{\frac{\epsilon}{2}}(q_1),\]
and take
$(y_0, y_1)= (\rho_0(\pi_0(x_0)), \rho_0(\pi_0(x_1))),
(z_0, z_1)= (\rho_0(\pi_1(x_0)), \rho_0(\pi_1(x_1)))$.
\medskip
{\bf Subsubcase(IIbii):} The set of $y\in G\cdot x_0$
that are $\epsilon$-captured by $x_0$ {\it cannot} be
covered by finitely many balls of radius $\frac{\epsilon}{4}$.
\medskip
Let $\{x_n: n\in \N\}$ enumerate a dense subset of $G\cdot x_0$.
\medskip
{\bf Claim:} There exists sequences $(k'_n)_{n\in \N}$, $(k_n'')_{n\in \N},
(\ell'_n)_{n\in \N}, (\ell_n'')_{n\in \N}$ and arrays
\[(y'_{j, i, m})_{m\in \N, i \sum_{m \sum_{m\leq n}\ell_m'\cdot k_m'+\sum_{m1$.
Then there exists uniformly continuous
\[f: \overline{\{(\pi\cdot x_0, \pi \cdot x_1):
\pi \in G\}}\rightarrow [0, 1]\]
such that for any non-empty right ideal
${\mathcal I}\subset\hat{G}$ there are
\[\rho, \gamma\in {\mathcal I}\]
with
\[f(\rho(x_0), \rho(x_1))=0,\]
\[f(\gamma(x_0), \gamma(x_1))=1.\]
\end{corollary}
\begin{proof}
We can assume that the ideal has the form
${\mathcal I}=\j(\rho_0)$ for some $\rho_0\in \hat{G}$,
and then \ref{cor1} follows directly from the definitions and
the theorem.
\end{proof}
\begin{corollary} \label{cor2}
Let $(X, d), G, \hat{G}$ be as above,
again with $|G|>1$. Define $\hat{D}$ to be the usual
metric
on $\hat{G}$, with
\[\hat{D}(\rho_0, \rho_1)=
\sum_{n\in \N} 2^{-n}{\rm max}(1, d(\rho_0(z_n), \rho_1(z_n)))\]
for some dense set $\{z_n: n\in \N\}\subset X$.
Then there exists uniformly continuous
\[\hat{f}: \hat{G}\rightarrow [0, 1]\]
such that for any non-empty right ideal
${\mathcal I}\subset\hat{G}$ there are
\[\rho, \gamma\in {\mathcal I}\]
with
\[\hat{f}(\rho)=0,\]
\[\hat{f}(\gamma)=1.\]
\end{corollary}
\begin{proof} Take $f$ and $x_0, x_1$
as in \ref{cor1} and let
\[\hat{f}(\rho)= f(\rho(x_0), \rho(x_1)).\]
It is immediate from the assumptions on $f$ that
$\hat{f}$ has high oscillation on any non-trivial
ideal and
the definition of $\hat{D}$ implies that $\hat{f}$ is uniformly
continuous.
\end{proof}
\begin{remark}
In each of \ref{maintheorem}, \ref{cor1}, \ref{cor2} we
can ask that $f$ not just be uniformly continuous but in fact
Lipschitz. For instance in \ref{maintheorem} we
can replace $f$ by
\[f^*: X^2\rightarrow [0, 1]\]
with
\[f^*(z_0, z_1)={\rm min}(1, {\rm inf}\{d(z_0, y_0)+ d(z_1, y_1):
f(y_0, y_1)=0)\}).\]
$f^*$ is clearly Lipschitz and
there will be some positive
$\epsilon\leq 1$, depending on the
uniformity of continuity of $f$, and
fixed $x_0, x_1\in X$
such that $f^*$ will assume
the value 0 and at least the value $\epsilon$
on
\[\{(\rho_0(\pi(x_0)), \rho_0(\pi(x_1))): \pi\in G\}\]
for any $\rho_0\in \hat{G}$.
Then we can simply rescale and truncate $f^*$,
replacing it by
\[(z_0, z_1)\mapsto
{\rm min}(1, \frac{f^*(z_0, z_1)}{\epsilon}).\]
\end{remark}
\subsection{Oscillation for Polish groups}
\label{polishgroups}
Theorem \ref{maintheorem} allows us to conclude with a kind of
distortion theorem for Polish groups.
If $G$ is a Polish group and $d_L$ is a left invariant metric,
and $\hat{G}$ is the Cauchy completion of $G$ with respect to
$d_L$, then there is a uniformly continuous
\[f: \hat{G}\rightarrow [0,1]\]
such that for any non-empty ideal ${\mathcal I}\subset \hat{G}$ we
have $f$ attaining both 0 and 1 on ${\mathcal I}$.
There are a couple of remarks and definitions before we can give the
proof.
\begin{theorem} (Birkhoff-Kakutani)
Every Polish group has a compatible left invariant
metric.
\end{theorem}
\begin{proof} See \cite{beckerkechris}.
\end{proof}
This is {\it not} to say that every Polish group admits a
{\it complete} left invariant metric.
$S_\infty$ for instance, the group of all permutations of
the natural numbers with
the topology of pointwise convergence, does not.
\begin{lemma} \label{invariance}
Any two compatible left invariant metrics have the same Cauchy sequences.
\end{lemma}
\begin{proof} Note that a sequence $(g_n)_{n\in \N}$ is Cauchy with respect to one
compatible left invariant metric (and hence all compatible left invariant metrics)
if and only if for every open neighborhood $U$ of the identity there is an $N$ such that
for all $m, n>N$
\[g^{-1}_mg_n\in U.\]
\end{proof}
Thus the {\it left completion} of a Polish group does not depend on the choice of
a left invariant metric. This gives a way of exactly matching up the notions from
$\S$\ref{biglentil} with the present situation.
%Let $G$ be a Polish group, and $d_L$ a compatible left invariant metric, which,
%after possibly truncating, we can assume is bounded by one. Let $\{x_n: n\in \N\}$ be a
%dense subset of $G$ and define the left invariant metric $\hat{D}$ on
%In$(G, d_L)$ as in $\S$\ref{lemmas} by
%\[\hat{D}(\rho_0, \rho_1)=\sum_{n\in \N} 2^{-n}(d(\rho_0(x_n), \rho_0(x_n))).\]
%Each $g\in G$ induces an element of Isom$(G, d_L)$ by considering the left
%translation
%\[\pi_g: h\mapsto gh,\]
%and thus $\hat{D}$ provides a compatible left invariant metric on $G$, and thus, since
%all left invariant metrics give the same notion of Cauchy completion,
%we may identify the left completion of $G$ with the closure of
%\[\{\pi_g: g\in G\}\]
%in In$(G, d_L)$.
\begin{notation}
For $G$ a Polish group, let $\hat{G}$ be the Cauchy completion of $G$ with respect to
some (equivalently, any) choice of a compatible left invariant
metric $d_L$ on $G$.
\end{notation}
\begin{lemma} \label{cauchy}
If $(g_n)_{n\in \N}, (h_n)_{n\in \N}$ are Cauchy with respect to a left invariant metric
on a Polish group $G$ then
$(g_n h_n)_{n\in \N}$ is Cauchy with respect to the left invariant metric.
\end{lemma}
\begin{proof} Nodding back to the proof of the last lemma, note that for any open neighborhood
$U$ of the identity we can find an $N_10$ there exist $\delta_1, \delta_2$ such that
\[\hat{D}(\rho_0, \rho_1)<\delta_1\Rightarrow d_L(\rho_0, \rho_1)<\epsilon,\]
\[d_L(\rho_0, \rho_1)<\delta_2\Rightarrow \hat{D}(\rho_0, \rho_1)<\epsilon.\]
\end{lemma}
\begin{proof} $\hat{D}$ provides a left invariant metric
on $G$, and hence gives rise to the same completion by
lemma \ref{invariance}.
For checking the compositionality, note that the
composition of the isometries associated
to Cauchy $(g_n)_n, (h_n)_n$ sends each
${h}\in{G}$ to the limit of $(g_nh_nh)_n$.
It remains to show the equivalence of the two metrics defined on
$\hat{G}$, as either the Cauchy completion of $G$ or the closure
of $\{\pi_g: g\in G\}$ in In$(\hat{G}, d_L)$.
We fix a dense subset $\{z_i: i\in \N\}$ of
$\hat{G}$ and define the metric $\hat{D}$ as usual. We can assume
that this dense subset lies inside $G$, since $G$ is dense in its
Cauchy completion, and we can also assume that $z_1=e$, the identity
in $G$.
It is clear that the topology obtained by viewing $\hat{G}$ as
a subset of In$(\hat{G}, d_L)$ is at least as strong the topology
given by viewing as the Cauchy completion,
since for any $\epsilon >0$ we have that if
\[\hat{D}(\rho_0, \rho_1)<\frac{\epsilon}{2}\]
then
\[d_L(\rho_0(z_1), \rho_1(z_1))=d_L(\rho_0z_1, \rho_1z_1) =d_L(\rho_0, \rho_1)
<\epsilon.\]
For the converse, consider $\epsilon>0$. We can
find $\delta>0$ and
an initial segment $z_1,..., z_N$ of our enumerated
dense subset,
such that for any $\rho_0, \rho_1\in \hat{G}$ with
\[d_L(\rho_0(z_i), \rho_1(z_i))< \delta\]
all $i\leq N$ we have
\[\hat{D}(\rho_0, \rho_1)<\epsilon.\]
Then we can find some $\delta_1$ such that
\[d_L(g, e)<\delta_1\Rightarrow \forall i\leq N
(d_L(z_i^{-1}g z_i, e)<\delta,\]
\[\therefore \forall g_0, g_1\in G\forall i\leq N
(d_L(g_0, g_1)<\delta_1\Rightarrow d_L(z_i^{-1}(g_1^{-1} g_0) z_i, e)
=d_L(g_0z_i, g_1z_i)<\delta,\]
\[\therefore\forall \rho_0, \rho_1\in \hat{G} \forall i\leq N
(d_L(\rho_0, \rho_1)<\delta_1\Rightarrow d_L(\rho_0 z_i, \rho z_i)
<\delta),\]
as required.
\end{proof}
Thus in particular
the definition of {\it closed right ideal} in $\hat{G}$ given above
agrees with the definition presented in $\S$\ref{lemmas}.
\begin{theorem} \label{polishdistort}
Let $G$ be a Polish group of size bigger than one, and
$\hat{G}$ its left completion with respect to some left invariant metric
$d_L$. Then there is a uniformly continuous
\[f: (\hat{G}, d_L)\rightarrow [0, 1]\]
such that on any non-empty ideal ${\mathcal I}\subset \hat{G}$ we have
$f$ obtaining both zero and one.
\end{theorem}
\begin{proof} As in the proof of theorem \ref{maintheorem} it suffices to
show that we can obtain $f: \hat{G}\rightarrow [0, 3]$ such that on any non-empty
ideal it hits values less than one and greater than 2.
Following \ref{maintheorem} we can choose uniformly continuous
$(\gamma_0, \gamma_1)\in \hat{G}$ and uniformly continuous
\[f_0: \overline{\{(g\cdot \gamma_0, g\cdot \gamma_1):
g\in G\}}\rightarrow [0, 3]\]
such that for any $\rho_0\in \hat{G}$ and
induced ideal $\j(\rho_0)\subset {\rm In}(\hat{G}, d_L)$
we attain values in both $[0, 1)$ and $(2, 3]$ on the set
\[\{(\rho\cdot \gamma_0, \rho\cdot \gamma_1): \rho \in \j(\rho_0)\}.\]
This induces a function
\[f:\hat{G}\rightarrow [0,3]\]
with the specification that
\[f(\rho)=f_0(\rho\cdot \gamma_0, \rho\cdot \gamma_1).\]
It follows immediately from \ref{careful} that
$f$ is uniformly left continuous as a function on
$(\hat{G}, d_L)$ and that $f$ obtains the required oscillation on
any non-empty ideal.
\end{proof}
This theorem is in the form posed as a problem in
\cite{kepeto}.
\subsection{Connecting \ref{ultra} to the oscillation theorem}
\label{derive}
\begin{definition} $S_\infty$ is the group of all permutations
of $\N$ with the topology of pointwise convergence.
\end{definition}
We specifically include permutations
with infinite support in $S_\infty$.
A basic open set in this topological group
consists in all
$\pi\in S_\infty$ such that
\[\pi(i)=k_i\]
all $i\leq N$, some choice of $k_1,..., k_N$.
\begin{theorem} (Folklore) \label{closed}
Any closed subgroup of
$S_\infty$ equals Aut$(\m)$ for some ultrahomogeneous
structure whose underlying set is $\N$.
\end{theorem}
\begin{proof} See \cite{beckerkechris}.
\end{proof}
\begin{notation} Given a countable
ultrahomogeneous
structure $\m$,
let ${\rm In}(\m)$ be the set of all monomorphisms
\[\rho: \m\hookrightarrow \m.\]
We place a complete
metric on ${\rm In}(\m)$ as follows. We first
assume without loss that the underlying set of $\m$ is the
set of natural numbers. Then for $\rho_0\neq \rho_1$ we
let $\Delta(\rho_0, \rho_1)$ be the first $n$ with
$\rho_0(n)\neq \rho_1(n)$, and then define
\[d(\rho_0, \rho_1)=2^{-\Delta(\rho_0, \rho_1)}.\]
\end{notation}
Recall that in $\S$\ref{polishgroups} we defined
$\hat{G}$ for $G$ a Polish group to be the Cauchy completion
with respect to any compatible left invariant metric.
We now have that $d$ provides a left invariant metric on
${\rm In}(\m)$ and hence Aut$(\m)$, and so for $G={\rm Aut}(\m)$
we can identify $\hat{G}$ with the closure of
Aut$(\m)$ with respect to $d$.
Using ultrahomogeneity
this $\hat{G}$ actually turns out to be the full
semi-group of monomorphisms from $\m$ to itself.
\begin{lemma} \label{derive1}
For $\m$ ultrahomogeneous, $G={\rm Aut}(\m)$,
we have that $\hat{G}$ equals ${\rm In}(\m)$.
\end{lemma}
\begin{proof}
Immediately from the definition of ultrahomogeneous we have that
for any $\rho\in {\rm In}(\m)$ and $\vec a, \vec b\in \m^{<\infty}$,
if $\rho(\vec a)=\vec b$ then there is an automorphism
$\pi$ with $\pi(\vec a)=\vec b$. Since this holds for all
$\vec a, \vec b$ we have $\rho\in \hat{G}$.
\end{proof}
\begin{lemma} \label{derive2}
Let $\rho_0\in {\rm In}(\m)$. Then the ideal
\[\j(\rho_0)=
\overline{\{\rho_0\circ \pi: \pi \in {\rm Aut}(\m)\}}\]
equals
all $\gamma\in {\rm In}(\m)$ with
{\rm range}($\gamma)\subset$ {\rm range}$(\rho_0)$.
\end{lemma}
\begin{proof} It is clear
from the definitions
that if $\gamma\in \j(\rho_0))$ then
its image is included in that of $\rho_0$. Conversely,
if the range($\gamma)\subset$ range$(\rho_0)$ then at each
$\vec a\in \m^{<\infty}$ we can first find $\vec c$ with
$\rho_0(\vec c)=\gamma(\vec a)$ and then, since $\vec a, \vec c$
have the
same type, we can find $\pi\in {\rm Aut}(\m)$ with
$\pi(\vec a)=\vec c$ to obtain
\[\rho_0\circ \pi(\vec a) =\gamma(\vec a).\]
Since this holds for all such $\vec a$ we have that
$\gamma$ is in the closure of $\{\rho_0 \circ \pi:
\pi\in {\rm Aut}(\m)\}$.
\end{proof}
With all this background out of the way,
we can obtain theorem \ref{polishdistort} for $G$ a
closed subgroup of $S_\infty$ as follows.
Applying \ref{closed} we can assume $G={\rm Aut}(\m)$
for some ultrahomogeneous $\m$.
We use \ref{ultra} to find some $(a_0, a_1)\in \m^2$
and
\[f:\m^2\rightarrow \{0, 1\}\] such that for
$S$ the set of all pairs with the same type as $(a_0, a_1)$,
we have $f$ obtaining both possible values on
$S\cap \rho_0[\m]\times \rho_0[\m]$ for any monomorphism
$\rho_0:\m\rightarrow \m$.
Then we can define
\[\hat{f}:\hat{G}\rightarrow \{0, 1\}\]
by $\hat{f}(\gamma)=f(\gamma(a_0), \gamma(a_1)).$
It is trivial to verify that this
is left uniformly continuous
Given
any $\rho_0\in \hat{G}$
we choose $\vec b=(b_0, b_1), \vec c=(c_0, c_1)$ in
range$(\rho)\cap S$ with $f(\vec b)=0, f(\vec c)=1$.
We let $b_0', b_1', c_0', c_1'$ be the preimages under
$\rho$ of $b_0, b_1, c_0, c_1$ respectively.
Appealing to ultrahomogeneity we can find $\pi, \sigma\in
{\rm Aut}(\m)$ with
\[\pi(a_0)=b_0', \: \: \pi(a_1)=b_1',\]
\[\sigma(a_0)=c_0', \: \: \sigma(a_1)=c_1',\]
and hence $\rho\circ \pi(\vec a)=\vec b$,
$\rho\circ\sigma(\vec a)=\vec b$, and thus
\[\hat{f}(\rho\circ \pi)=f(\vec b)=0,\]
\[\hat{f}(\rho\circ \sigma)=f(\vec c)=1,\]
as required.
%This section is just to point out that theorem
%\ref{maintheorem} really does subsume
%theorem \ref{ultra}.
%\begin{definition} Given a countable ultrahomogeneous
%structure $\m$ we associate a complete
%{\it countable} metric space $(X_\m, d_\m)$ as
%follows.
%First we choose a one-to-one assignment of real numbers in the
%open unit from $\frac{1}{4}$ to $\frac{1}{2}$ to quantifier
%free types. This can be thought of as a function
%\[\alpha: \m^{<\infty}\rightarrow (\frac{1}{4}, \frac{1}{2})\]
%such that $\alpha(\vec a)=\alpha(\vec b)$ if and only if
%they have the same quantifier free type.
%We then take as the underlying set of $X_\m$ the
%{\it disjoint} union of $\m$, $\m^1$, $\m^2$, $\m^3$,...
%Then given any $\vec a=(a_0,..., a_n)\in \m^n$ we
%set the distance in $X_\m$ of $\vec a$ to any $a_i$ to
%be exactly $c(\vec a)$. For $a, b\in \m$, we let
%$d_\m(a, b)=1$. For all other points in $X_\m$ we take the
%induced path metric. Thus for
%$\vec a\notequal \vec b\in \m^{<\infty}$ we let
%\[d_\m(\vec a, \vec b)= c(\vec a) + c(\vec b)\]
%if the sequences overlap and
%\[d_\m(\vec a, \vec b)=c(\vec a) + c(\vec b) +1\]
%if they are disjoint.
%\end{definition}
%\begin{lemma} \label{func1}
%Any onto isometry of $(X_\m, d_\m)$ fixes
%$\m$ set wise and moves finite
%sequences inside $\m$ to other finite sequences with the same
%quantifier free type.
%\end{lemma}
%\begin{proof} $\m$ is recognizable inside $X_\m$ as the set of
%points which are distance exactly one away from some other point,
%and hence this set is preserved by any invertible
%isometry. Inside $\m$ we similarly recognize the finite sequences
%with the same type as some given $\vec a$, since these are exactly
%the sequences of the same length as $\vec a$ for which there exists a
%point sitting simultaneously
%exactly distance $c(\vec a)$ away from them all.
%\end{proof}
%\begin{lemma} \label{func2}
%Any automorphism of $\m$ extends uniquely to
%an onto isometry of $X_\m$.
%\end{lemma}
%\begin{proof} The {\it existence} of an extension
%follows directly from the invariant manner in which
%$X_\m$ was defined. Uniqueness follows from
%\ref{funct1}.
%\end{proof}
%\begin{lemma} \label{func3}
%If $G$ is the isometry group of $X_\m$ and
%$\rho\in \hat{G}$, then $\vec a$ is in the image of
%$\rho$ if and only if each $a_i$ in the sequence is
%in the image of $a$.
%\end{lemma}
%\begin{proof} Let $\sigma_n\rightarrow \rho$.
%$\vec a$ is in the image of $\rho$ if and only if there
%is single $\vec b$ such that for all sufficiently large
%$n$ we have $\sigma_n(b_i)=a_i$ at each suitable $i$. This
%in turn is equivalent to saying that each $a_i$ is in the
%image of $\rho$.
%\end{lemma}
\subsection{$n=1$ and $n=2$ spaces}
\label{tomandjerry}
\begin{definition} Let $(X, d)$ be a complete separable metric
space and let $G$ be the isometry group of all onto isometries
from $X$ to $X$. As previously defined, let $\hat{G}$ be its closure
in the space of all isometries from $X$ into $X$.
We say that $X$ is an {\it $n=1$ space} if there is a single point
$x_0\in X$ and
uniformly continuous
\[f: \overline{\{\pi(x_0): \pi\in G\} }\rightarrow [0,1]\]
such that for any $\rho_0\in \hat{G}$ we
have $f$ achieving both
extreme values on
\[ \overline{\{\rho_0(\pi(x_0)): \pi\in G\} }.\]
Otherwise we say that $X$ is an {\it $n=2$ space}.
\end{definition}
Thus this terminology is motivated by
\ref{maintheorem} which says that $X$ is either an $n=1$ space
or there is an
\[f: \overline{\{(\pi(x_0), \pi(x_1)):
\pi\in G\} }\rightarrow [0,1]\]
which picks up both extreme values on
any
\[\overline{\{(\rho_0(\pi(x_0)), \rho_0(\pi(x_1))): \pi\in G\} }.\]
While there are some $n=2$ spaces, most of the
examples I know are trivial.
\begin{example} Let $(X, d)$ be a countably infinite set equipped with
the discrete metric. This is an $n=2$ space.
\end{example}
\begin{example} Recall from say \cite{gaokechris} that the
{\it Urysohn space} ${\mathbb U}$
is the complete, separable, universal metric
space which is ultrahomogeneous, in the
sense that any isometry between finite subsets extends to an
isometry of the whole space onto itself.
The Urysohn space is an $n=1$ space:
Fix some arbitrary $z_0$ in the space.
We choose rapidly increasing $(k_n)_{n\in \N}$ with
\[k_n >\sum_{m0$ there is an isometric copy of $c_0$ appearing
as a subspace on which $|f(x)-f(x')|$ is bounded by
$\epsilon$.
\end{theorem}
However in contrast to $\ell^2$ there are isometric embeddings of
$c_0$ into itself which do not appear in $\hat{G}$, the closure of the
{\it onto} isometries. It is not hard to see that any onto isometry of
$c_0$ must move take the canonical basis back to itself with possible
multiplications by $-1$, and thus for $c_0$ we actually have that
the onto isometries are {\it already} closed in the space of
isometries, and thus, for almost trivial reasons,
$c_0$ is an $n=1$ Banach space.
It is therefore natural to ask:
\begin{question} Does there exist a separable Banach space which is
not an $n=1$ Banach space?
\end{question}
\begin{thebibliography}{99}
\bibitem{beckerkechris} H. Becker, A.S. Kechris,
{\bf The descriptive set theory of Polish group actions,}
London Mathematical Society Lecture Note Series,
232, Cambridge University Press, Cambridge, 1996
\bibitem{delaposa} C. Delhomme, C. Laflamme, M. Pouzet, N. Sauer,
{\it The indivisiability of countable metric spaces,}
preprint, http://arxiv.org/abs/math.CO/0510254.
\bibitem{gaokechris} S. Gao, A.S. Kechris,
{\bf On the classification of Polish metric spaces up to isometry, }
Memoirs of the American Mathematical Society, vol. 766, 2003.
\bibitem{gowers} T. Gowers, {\it Lipschitz functions on classical spaces,}
{\bf European Journal of Combinatorics,} vol 13 (1992), pp. 141--151.
\bibitem{hodges} W. Hodges, {\bf Model theory,}
Encyclopedia of Mathematics and its Applications, vol 42,
Cambridge University Press, Cambridge, 1993.
%\bibitem{classical} A.S. Kechris, {\bf Classical descriptive set
%theory,} Graduate Texts in Mathematics 156, Springer-Verlag,
%New York, 1995.
\bibitem{kepeto}A.S. Kechris,
V.G. Pestov, S. T{o}dorcevic,
{\it Fraiss\"{e} li\"{m}its, Ramsey theory and
topological dynamics of automorphism groups},
to appear in {\bf Geometric and Functional Analysis}.
\bibitem{keisler} H.J. Keisler,
{\bf Model theory for infinitary logic,}
Studies in Logic and the Foundations of Mathematics, Vol. 62,
North-Holland Publishing Co., Amsterdam-London, 1971.
\bibitem{odellschlumprecht} E. Odell, T. Schlumprecht,
{\it The distortion problem,}
{\bf Acta Mathematica}, vol. 173 (1994), pp. 259--281.
\end{thebibliography}
\leftskip 0.4in
\noindent {\texttt greg@math.ucla.edu}
\medskip
\noindent http://www.math.ucla.edu/\~{}greg/
\medskip
\noindent 7340 MSB
\noindent Mathematics
\noindent UCLA
\noindent 405 Hilgard Avenue
\noindent Los Angeles
\noindent CA 90095-1555
% Set the ending of a LaTeX document
\end{document}
*