\documentclass{beamer}
\usepackage{beamerthemesplit}

\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage[all]{xy}



%\usepackage{eepic}
\usepackage{xcolor}
%\usepackage{comment}
%\usepackage{tikz}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{caption}
\usepackage{tikz}
%\usepackage{subcaption}


\theoremstyle{theorem}
\newtheorem*{thm}{Theorem}
\newtheorem*{lem}{Lemma}


\theoremstyle{definition}
%\newtheorem*{fact}{Fact}
\newtheorem*{defn}{Definition}
\newtheorem*{ques}{Question}
\newtheorem*{cor}{Corollary}
\newtheorem*{conj}{Conjecture}
\newtheorem*{rem}{Remark}
\newtheorem*{ex}{Example}









\newcommand{\ww}{{\omega^\omega}}
\newcommand{\bas}{\bar{s}}
\newcommand{\bag}{\bar{g}}
\newcommand{\std}{\text{std}}
\newcommand{\iso}{\text{ISO}}
\newcommand{\bU}{\mathbb{U}}
\newcommand{\ave}{\text{Ave}}


\newcommand{\res}{\restriction}
\newcommand{\bg}{\boldsymbol{\Gamma}}
\newcommand{\bgd}{\check{\boldsymbol{\Gamma}}}
\newcommand{\bd}{\boldsymbol{\Delta}}
\newcommand{\bs}{\boldsymbol{\Sigma}}
\newcommand{\bp}{\boldsymbol{\Pi}}



\newcommand{\on}{\text{On}}
\newcommand{\sP}{\mathcal{P}}
\newcommand{\sC}{\mathcal{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}



\newcommand{\lh}{\text{lh}}
\newcommand{\mys}{\medskip}
\newcommand{\id}{\mathsf{id}}
\newcommand{\lecc}{\text{lecc}}


\newcommand{\ncl}[2]{\overline{#2}^{#1}}
\newcommand{\conc}{{}^\smallfrown}
\newcommand{\supp}{\text{supp}}
\newcommand{\fp}{\otimes}

\newcommand{\sB}{\mathcal{B}}


\newcommand{\ifs}{{IFS}}
\newcommand{\iifs}{I_{\text{ifs}}}
\newcommand{\irr}{\text{Irr}}
\newcommand{\lo}{\text{LO}}
\newcommand{\sI}{\mathcal{I}}





\begin{document}


%\setbeamercovered{dynamic}

\title{Applications of Descriptive Set Theory to Functional Analysis and Dynamics}



\author{S.\ Jackson}



\institute{
Department of Mathematics\\
University of North Texas\\
%jackson@unt.edu
}






\date{
August, 2013\\
{\color{red}SUMIRFAS}, College Station}


\begin{frame}
\titlepage
\end{frame}



\begin{frame}
\frametitle{Overview}
We discuss to applications of descriptive set theory to classifying complexity,
one in functional analysis, and one in dynamics. 
\mys


The first result concerns the complexity of the uniform homeomorphism relation between 
separable Banach spaces. It is joint with {\color{red} Su Gao} and {\color{red} Bunyamin Sari}.
\mys

The second result concerns the complexity of a natural ideal associated to attractors from
iterated function systems. 
\end{frame}



\section{Introduction}



\begin{frame}
Basic objects of study in analysis are the Polish spaces $X$, 
the complete separable metric spaces. 
\mys


Recall $(X,\sB)$ is a standard Borel space if $\sB$ is a $\sigma$-algebra on 
$X$ such that $(X,\sB)$ is isomorphic to the algebra of Borel sets in some Polish space. 
\mys

Any Borel subset of a Polish space is a standard Borel space.
\mys

Examples: $\R^n_\std$, $\ww$, $2^\omega$, probability measures on a Polish space, 
separable Banach spaces, $F(X)$. 
\end{frame}



\begin{frame}
Any two uncountable Polish spaces are Borel isomorphic, so among the standard Borel spaces 
the only invariants are the cardinalities $1,2,\dots$, $\omega$, $c$. 
\mys


In Polish spaces, one classifies the complexities of sets through the notion of a {\color{blue}reduction}.
\mys


Let $X$, $Y$ be Polish spaces and $A \subseteq X$, $B \subseteq Y$. We say $A$ is Wadge reducible to $B$,
$A \leq_w B$ if there is a continuous function $f \colon X \to Y$ such that $A=f^{-1}(B)$, that is,

\[
x \in A \Leftrightarrow f(x) \in B
\]

[
This definition is reasonable if $X$, $Y$ are $0$-dimensional, otherwise can use coarser
notion of Borel reduction].
\end{frame}


\begin{frame}
For sets in $\ww$ complexity classes fall into a wellorderded hierarchy via Wadge's lemma
and the Martin-Monk theorems. 
\mys





{\color{red}Wadge's} Lemma: Assume sufficient determinacy. Then for $A,B \subseteq \ww$ either 
$A \leq_w B$ or $B \leq_w A$. 
\mys


So, if we identify the degree of $A$ with $A^c$, then the degrees are linearly orderded. 
\mys



{\color{red}Martin-Monk}: Assume sufficient determinacy. Then the Wadge degrees are wellorderded. 
\mys




So, the Wadge hierarcy gives a complete classification of the complexity degrees for
sets in Polish space. 
\end{frame}


\begin{frame}
We wish a notion of complexity to classify objects more general than subsets of a Polish space. 
\mys



Let $E$ be an equivalence relation on a Polish space $X$. The corresponding quotient space is $X/E$. 
\mys


Objects of the form $X/E$ represent all objects for which there is a surjection of $\R$
onto the object. We usually restrict to Borel equivalence relations $E$ (though the results 
usually apply to arbitrary $E$ given determinacy). 
\mys


In general, there is no reasonable (definable) way to regard $X/E$ as a subset of a standard Borel space. 
\mys


We generalize the notion of reduction to introduce notion of complexity for equivalence relations
on standard Borel spaces.
\end{frame}


\begin{frame}
Let $E$, $F$ be Borel equivalence relations on standard Borel spaces $X$, $Y$. 
\mys


\begin{defn}
\begin{itemize}
\item
We say $E$ is {\color{blue}reducible} to $F$, $E \leq F$,  if there is a Borel function $f \colon X\to Y$
such that $x E\ y \Leftrightarrow f(x) F\ f(y)$.


\item
We say $E$ is bi-reducible with $F$, $E \sim F$,  if $E \leq F$ and $F \leq E$. 

\item
We say $E$ is emdeddable into $F$, $E \sqsubseteq F$, if in addition $f$ is one-to-one.
\end{itemize}

\end{defn}


Note that a reduction gives a definable injection from $X/E$ to $Y/F$ so reduction can be viewed 
as a notion of definable cardinality for these quotient spaces. 
\end{frame}



\begin{frame}

We say $E$ is a countable (Borel) equivalence relation if all classes of $E$ are countable.
\mys


If $G$ is a Polish group and $G$ acts on $X$, then the {\color{blue}orbit equivalence relation}
$E_G$ is defined by
\[
x E_G\, y \Leftrightarrow \exists g \in G\ (g \cdot x =y).
\]


The {\color{red}Feldman-Moore} theorem says that every countable Borel equivalence 
relation is given by the Borel action of a countable group $G$. The case $G=\Z$ 
is the classical case of discrete-time dynamics. 
\mys

So, we can study the equivalence relations $E_G$ group by group.
\end{frame}


\begin{frame}
The simplest equivalence relations are the {\color{blue}smooth} or {\color{blue}tame} ones.

\begin{defn}
$E$ is smooth if there is a Borel reduction of $E$ to equality relation on a Polish space.
\end{defn}


So, for a smooth $E$, $X/E$ can be regarded as  a subset of a standard Borel space.
\mys

For countable Borel $E$, smooth is the same as saying there is a Borel selector for $E$.
\end{frame}



\begin{frame}

\begin{defn}
$E_0$ is the equivalence relation on $2^\omega$ given by 
\[
x E_0\, y \Leftrightarrow \exists n\ \forall m \geq n\ (x(m)=y(m)).
\]
\end{defn}


The {\color{red}Harrington-Kechris-Louveau} theorem says that if $E$ is a Borel equivalence
relation then either $E$ is smooth or $E_0 \sqsubseteq E$.
\mys


So, there is no complexity class of equivalence relation strictly between 
the smooth relation $E_{=}$ and $E_0$. 


\end{frame}


\begin{frame}
If $G$ is a Polish group, $G$ acts of $F(G)$ by the shift action
\[
g\cdot F=\{gf \colon f \in F\}
\]


We can view this action as being on $2^G$ by

\[
g \cdot x (h)= x(g^{-1}h)
\]

We call this the {\color{blue}Bernoulli} (left) shift action of $G$ on $2^G$. When $G$
is countable, $2^G$ is a compact Polish space in the natural product topology.
\end{frame}


\begin{frame}
The Bernoulli shift is more or less universal for 

\begin{fact}
Let $E$ the the orbit equivalence relation for a Borel action of the countable group $G$
on a Polish space $X$. Then 
\[
E \leq E((2^\omega)^G) \leq E(2^{G\times \Z}).\]
\end{fact}
\mys


A theorem of {\color{red}Becker-Kechris} says that for general Polish $G$ the $\omega$-product of the shift 
action of $G$ on $F(G)$ is universal for Borel $G$-actions. 
\mys


There is also a universal Polish group (e.g., $\iso(\bU)$), so that there is a universal Polish group action.
\end{frame}









\begin{frame}
\frametitle{Countable Equivalence Relations}

\begin{thm}[Dougherty-J-Kechris]
The shift action of $F_2$ on $2^{F_2}$ is a universal countable Borel equivalence relation,
that is, $E\leq E_{F_2}$ for any countable Borel $E$.
\end{thm}
\mys





\begin{defn}
A countable Borel equivalence relation $E$ is {\color{blue}hyperfinite}
if $E$ is the increasing union of relations $E_n$ with finite classes. 
\end{defn}


\begin{thm}[Slaman-Steel]
The following are equivalent:

\begin{itemize}
\item
$E$ is hyperfinite.
\item
$E=E_G$ where $G=\Z$.
\item
The classes of $E$ can be uniformly Borel ordered in type $\Z$ (or are finite).
\end{itemize}
\end{thm}
\end{frame}





\begin{frame}


\begin{thm}[Weiss] Every Borel action by $\Z^n$ is hyperfinite.
\end{thm}
\mys


\begin{thm}[Gao-J] Every Borel action by a countable abelian group is hyperfinite.
\end{thm}
\mys


Hyperfiniteness problem (Kechris): Is every equivalence relation generated by a Borel action
of an amenable group hyperfinite?
\mys



{\color{red}Adams-Kechris} showed that the structure of the countable Borel equivalence relations 
above $E_0$ is complicated.
\end{frame}



\begin{frame}
\frametitle{Some Non-countable Relations}


\begin{itemize}
\item
$E_0^\omega$: Does not embed into any $\bs^0_3$ equivalence relation. 
\item
$\ell_p$, $1 \leq p \leq \infty$. Given by action of Polish group. 
By {\color{red}Dougherty-Hjorth} $\ell_p \leq \ell_q$ for $p \leq q$.
\item
$\ell_\infty$ by {\color{red}Rosendal} is universal for $K_\sigma$ equivalence relations.
\item
$E_1$: Defined as $E_0$ except on $\R$. 
\item
$=^+$: Equality on countable sets of reals. Embeds any countable equivalence relations,
given by $S_\infty$ action.
\end{itemize}
\end{frame}



\section{Application to functional analysis}



\begin{frame}
The collection $\sB$ of separable Banach spaces can be viewed as a Polish space by 
identifying separable Banach spaces with closed subspaces of $C[0,1]$. The 
subset of $F(C[0,1])$ corresponding to linear subspaces is a $G_\delta$.
\mys


The collection $\sB_b$ of separable Banach spaces with basis $(X,B)$ 
can also be viewed as a Polish space. 
\begin{itemize}
\item
One way is to use a universal basis, so we identify $(X,B)$ with an $x \in 2^\omega$. 
\item
Or can identify $(X, (b_i))$ with the sequence $\| \sum_{i=1}^k a_i^n b_i\|_X$,
where $(a^n_1,\dots,a^n_k)$ enumerates $\Q^{<\omega}$. This identifies $\sB_b$ 
with a closed subset of $\R^\omega$. 
\end{itemize}


There are Borel functions taking codes for members of $\sB_b$
in one coding to codes in the other coding. 








\end{frame}




\begin{frame}

\frametitle{Some known classifications}

({\color{red}Ferenczi, Louveau, Rosendal}) Isomorphism on separable Banach spaces is
bireducible with $\bs^1_1$-complete equivalence relation.
\mys



({\color{red}Rosendal}) Equivalence of bases is complete $K_\sigma$ equivalence relation ($\ell_\infty$).
\mys



({\color{red}Melleray}) Isometry between separable Banach spaces is universal orbit equivalence relation.
\mys

({\color{red}Gao-J-Sari}) Uniform homeomorphism between separable Banach spaces is at least 
$\ell_\infty$.

\end{frame}







\begin{frame}

\begin{figure}[h]
%\begin{center}
%\centering
\setlength{\unitlength}{.25cm}

\begin{subfigure}
\centering
\begin{picture}(20,25)(15,5.5)

\put(12.25,0.2){\makebox(0,0)[b]{$\id(2^\omega)$}}
\put(10,1){\circle*{.3}}
\put(10,1){\line(0,1){3}}
\put(10,4){\circle*{.3}}
\put(11,3.5){\makebox(0,0)[b]{$E_0$}}
\put(10,4){\line(0,1){5}}
\put(10,9){\circle*{.3}}
\put(10.25,7.5){$E_G$, $G$ amenable}
\put(2,6){hyperfinite?}
\put(10,15){\oval(6,12)}
\put(10,21){\circle*{.3}}
\put(10,21){\line(0,1){3}}
\put(10,24){\circle*{.3}}
\put(10.5,23.5){$E_\infty$}
\end{picture}
\end{subfigure}




\begin{subfigure}
\centering
\begin{picture}(20,25)(-8,-20)

\put(10,1){\circle*{.3}}
\put(12.25,0.2){\makebox(0,0)[b]{$\id(2^\omega)$}}
\put(10,1){\line(0,1){3}}
\put(10,4){\circle*{.3}}
\put(11,2.8){\makebox(0,0)[b]{$E_0$}}

\put(10,4){\line(-3,2){6}}
\put(4,8){\circle*{.3}}
\put(3,6.5){\makebox(0,0)[b]{$E_0^\omega$}}
\put(10,4){\line(-1,2){2}}
\put(8,8){\circle*{.3}}
\put(7.5,6.5){\makebox(0,0)[b]{$E_\infty$}}
\put(10,4){\line(1,2){2}}
\put(12,8){\circle*{.3}}
\put(12.5,6.5){\makebox(0,0)[b]{$\ell_1$}}
\put(10,4){\line(3,2){6}}
\put(16,8){\circle*{.3}}
\put(16.2,6.5){\makebox(0,0)[b]{$E_1$}}

\put(4,8){\line(0,1){6}}
\put(4,14){\circle*{.3}}
\put(3,13.8){\makebox(0,0)[b]{$=^+$}}
\put(4,14){\line(2,-3){4}}
\put(16,8){\line(0,1){6}}
\put(16,14){\circle*{.3}}
\put(17.25,13.2){\makebox(0,0)[b]{$\ell_\infty$}}
\put(22.2,13.2){\makebox(0,0)[b]{(equivalence}}
\put(22,12){\makebox(0,0){of bases)}}
\put(16,14){\line(-2,-3){4}}
\put(16,14){\line(-4,-3){8}}

\put(10,23){\line(2,-3){6}}
\put(10,23){\line(-2,-3){6}}
\put(10,23){\circle*{.3}}
\put(10.2,23){\makebox(0,0)[b]{$E_{{\bf\Sigma}^1_1}$}}
\put(16.5,23){\makebox(0,0)[b]{(isomorphism)}}

\put(12,8){\line(-2,3){6}}
\put(6,17){\circle*{.3}}
\put(5,17){\makebox(0,0)[b]{$E_G^\infty$}}
\put(10,17){\makebox(0,0)[b]{(isometry)}}
\end{picture}
\end{subfigure}
%\caption{\label{fig:ers}Equivalence relations characterizing the
%complexity of
%classification problems for Banach spaces.}%\vspace*{-12pt}
%\end{center}
\end{figure}



\end{frame}

\begin{frame}
Recall that for linearly isomorphic Banach spaces $X$, $Y$, the Banch-Mazur 
distance is defined by 

\[
d(X,Y)= \inf \{ \| T\| \| T^{-1}\| \colon T\colon X \to Y \text{ is an isomorphism } \}
\]
\mys


\begin{defn}
$X$, $Y$ are {\color{blue} locally equivalent} if there is a $C>0$ such that for every finite
dimensional subspace $E$ of $X$ there is a subspace $F$ of $Y$ with $d(E,F) \leq C$ and 
vice-versa. We write $X\equiv_L Y$. 
\end{defn}



\begin{thm}[Ribe]
If $X$, $Y$ are uniformly homeomorphic then $X \equiv_L Y$. 
\end{thm}


\end{frame}



\begin{frame}
\begin{fact}
Local equivalence is a $\bs_0^3$ equivalence relation on $\sB$ or on $\sB_b$. 
\end{fact}
\mys


\begin{cor}
$E_0^\omega$, and hence $=^+$ is not reducible to $\equiv_L$ on either $\sB$ or $\sB_b$.
\end{cor}
\mys


In fact we have:
\mys


\begin{thm}[Gao-J-Sari]
$\equiv_L$ (on either $\sB$ or $\sB_b$) is bi-reducible with $\ell_\infty$.
\end{thm}


On the other hand, local equivalence differs from uniform homeomorphism:

\begin{thm} [GJS]
There is a single Borel class $\sC$ of separable Banach spaces under uniform homeomorphism
such that $=^+$ is reducible to the isomorphism relation on $\sC$.
\end{thm}

\end{frame}



\section{sketch of proof}


\begin{frame}
\frametitle{Sketch of proof of reducibility}

Let $I_i=[l_i,r_i] \subseteq (1,2)$ with $| I_i |= \frac{1}{2^{i+1}}$, and let $n_i \in \Z^+$. 
\mys

Let $\vec p= (p_i)$ with $p_i \in I_i$.
\mys


Let 
\[S_{\vec p}= \left( \sum_{i=1}^\infty \ell_{p_i}^{n_i} \right)_2
\]


Fix a sequence $b_i \in \Z^+$ with $\limsup b_i=\infty$.
\mys


Let $\sigma_i \colon [0,b_i] \to I_i$ be an affine bijection. 
\end{frame}

\begin{frame}


\begin{figure}[h]
\centering
%\setlength{\unitlength}{0.4mm}
\begin{tikzpicture}[scale=0.04]

\draw (-100,0) to (100,0);
\draw (-100, -5) to (-100, 5);
\draw (100, -5) to (100, 5);
\node at (-100, -10) {$1$};
\node at (100, -10) {$2$};


\draw (-90, -3) to (-90, 3);
\draw (-40, -3) to (-40, 3);
\draw[color=red] (-90,0) to (-40,0);


\draw (-20, -3) to (-20, 3);
\draw (20, -3) to (20, 3);
\draw[color=red] (-20,0) to (20,0);
\node at (0,7) {$I_i$};
\node at (-20, -7) {$l_i$};
\node at (20, -7) {$r_i$};
\draw (-20,50) to (50,50);
\draw (-20,47) to (-20,53);
\draw (50,47) to (50,53);
\node at (-20, 57) {$0$};
\node at (50, 57) {$b_i$};
\draw[->, dashed] (-20,45) to (-20,5);
\draw[->, dashed] (47,47) to (20,5);
\node at (-30, 25) {$\sigma_i$};



\draw (-20, -3) to (-20, 3);
\draw (20, -3) to (20, 3);
\draw[color=red] (-20,0) to (20,0);


\draw (30, -3) to (30, 3);
\draw (60, -3) to (60, 3);
\draw[color=red] (30,0) to (60,0);


\draw (65, -3) to (65, 3);
\draw (80, -3) to (80, 3);
\draw[color=red] (65,0) to (80,0);

\node at (90,2) {$\cdots$};



\end{tikzpicture}
\caption{Basic setup for the embedding}
\end{figure}

\begin{itemize}
\item
$I_i=[l_i,r_i]$, $| I_i| =2^{-(i+1)}$
\item
$\sigma_i \colon [0,b_i] \to I_i$
\end{itemize}
\end{frame}




\begin{frame}
We choose the $n_i$ carefully, they must grow fast, but not too fast.
\mys


Let 
\[
n_i=2^{b_i 2^i}
\]


We can easily reduce $\ell_\infty(\R)$ to $\ell_\infty([0,b_i])$, so we use the latter. 
\mys



Given $x \in \prod [0,b_i]$, we define $\pi(x)$ to be the separable Banach space 
$\pi(x)=S_{\vec p, \vec n}$ where $\vec p \in \prod I_i$ is given by

\[
p_i=\sigma_i(x(i))
\]
\mys




We check that $\pi$ is a reduction from $\ell_\infty([0,b_i])$ to 
the uniform homeomorphism relation on $\sB$. 
\end{frame}



\begin{frame}

Note that  (we assume the $b_i$ are increasing)

\[ 
n_{i+1}^{1/r_{i+1}} \geq n_{i+1}^{1/2} =2^{b_{i+1} 2^i} \geq n_i \geq n_i^{1/l_i}
\]
\mys



\begin{lem}
$S_{\vec p}$, $S_{\vec q}$ are uniformly homeomorphic 
iff 
$\sup_i n_i^{|\frac{1}{p_i}-\frac{1}{q_i}|} <\infty$.
\end{lem}


{\color{blue}Proof.}
If $n_i^{|\frac{1}{p_i}-\frac{1}{q_i}|}<C$ for all $i$, then 
$d(\ell_{p_i}^{n_i},\ell_{q_i}^{n_i}) \leq C$, just take the identity map.
\mys


Let $p=p_{i_0}$, $q=q_{i_0}$, $n=n_{i_0}$, and assume $p<q$.
\end{frame}





\begin{frame}
Let $T \colon \ell_p^n \to S_{\vec q}$ be a linear embedding. We show that 
$\| T\|  \| T^{-1} \| \geq C (n^{1/p-1/q})$ for some absolute constant $C$.
\mys


To do this we consider the type $2,n$ constants of $\ell_p^n$ and $S_{\vec q}$.
\mys

Recall the {\color{blue}type $p,n$ constant} $T_{p,n}(X)$ of a Banach space $X$ is the smallest 
constant such that for all $n$ vectors $x_1,\dots , x_n \in X$ we have: 

\[
\left( \underset{\epsilon_i=\pm 1}{\ave} \| \sum_{i=1}^n \epsilon_i x_i \|^2  \right)^{1/2}
\leq T_{p,n}(X) \left( \sum_{i=1}^n \| x_i\|^p \right)^{1/p}
\]


$X$ is of type $p$ if $T_p(X)=\sup_n T_{p,n}(X) <\infty$.
\end{frame}




\begin{frame}

If $T \colon X \to Y$ is a linear embedding then \[ T_{p,n}(X)\leq \| T\| \| T^{-1}\| T_{p,n}(Y).\]
\mys





We have (c.f. {\color{red}Tomczak-Jaegermann}):
\mys


\begin{itemize}
\item
$T_p(\ell_q^n) \geq n^{\max(0, 1/q-1/p)}$ 
\item
$T_p(\ell_q^n) \leq c q^{1/2}  n^{\max(0, 1/q-1/p)}$ \ ($1 \leq q <\infty$)
\item
For $n \leq k$, $T_{p,n}(\ell_q^k) \leq c q^{1/2}  n^{\max(0, 1/q-1/p)}$
\end{itemize}
\end{frame}


\begin{frame}
Fix $T\colon \ell_p^n \to S_{\vec q}$. We estimate $T_{2,n}(\ell_p^n)$. 
\mys

On the one hand it is at least $n^{1/p-1/2}$.
\mys


On the other hand, it is $\leq \|T\| \| T^{-1}\| T_{2,n}(S_{\vec q})$.
\mys


A computation using the previous facts and $n_i^{2/q_i}<n^{2/q}$ for $i <i_0$ gives that 
\mys

$T_{2,n}(S_{\vec q}) \leq \sqrt{2} c n^{1/q-1/p}$
\mys


and so $\|T\| \|T^{-1} \| \geq \frac{1}{\sqrt{2}c} n^{1/p-1/q}$.
\mys

This proves the lemma.
\end{frame}


\begin{frame}
Suppose $\vec x$, $\vec y \in \prod [0,b_i]$.
\mys

$\pi(\vec x)=S_{\sigma_i(x(i)),\vec n}$ is uniformly homeomorphic to 
$\pi(\vec y)=S_{\sigma_i(y(i)),\vec n}$
\mys

$\Leftrightarrow  \sup_i\  n_i^{| \frac{1}{\sigma_i(x(i))}-\frac{1}{\sigma_i(y(i))}|} <\infty$
\mys

$\Leftrightarrow \sup_i\  \log(n_i) |\sigma_i(x(i))-\sigma_i(y(i))| <\infty$
\mys

$\Leftrightarrow \sup_i\  (b_i 2^i) (\frac{ |x(i)-y(i)|}{b_i 2^{i+1}}) = 
\frac{1}{2} \sup_i |x(i)-y(i)|<\infty$
\mys


$\Leftrightarrow \vec x \ \ell_\infty\ \vec y$.

\end{frame}





\begin{frame}

This shows $\ell_\infty=\ell_\infty(\R)$ reduces to uniform homeomorphism on separable Banach spaces.
\mys


We also get that $\ell_\infty$ is bi-reducible with $\equiv_L$. 
\mys

For this we need the reverse reduction from $\equiv_L$ to $\ell_\infty$. 
\mys


This follows from the following fact. 
\mys


For any Polish $(X,d)$ let 
$\vec x F_X \, \vec y$ iff the $d$-Hausdorff distance between $\{ x(i)\}$ and $\{ y(i)\}$
is finite.
\mys

\begin{fact}
For any Polish $(X,d)$, $F_X \leq \ell_\infty$.
\end{fact}
\end{frame}


\section{Application to Dynamics}


\begin{frame}
\frametitle{Dynamics}
Let $f_i \colon \R^n \to \R^n$, $i=1,\dots,k$,  be contraction mappings, that is 
$\| f_i(x)-f_i(y)\| \leq c\| x-y\|$  where $c<1$. 
\mys

There is a unique compact set $K=K(f_1,\dots,f_n)$ such that 
$K=f_1(K)\cup \cdots \cup f_k(K)$. 
\mys

We say $\vec f$ satisfies the {\color{blue}porosity condition} if there is a $p>0$ such that for all 
balls $B$ of radius $r$ there is a sub-ball $B' \subseteq B$ of radius $pr$
such that $B' \cap K= \emptyset$.  
\mys



If we fix a ball $B(r)$ and a $c<1$, then the set of $\vec f$ which are contractions
of $B(r)$ with constant $c$ and is a Polish space $F(r,c)$, and the set of $\vec f$ 
satisfying the porosity condition is a closed subset of $F(r,c)$. 
\end{frame}



\begin{frame}

We let $\ifs$ denote the $K\in F(\R^n)$ of the form $K=K(\vec f)$ for some
iterated function system $\vec f$ satisfying the porosity condition. 
\mys

We let $\iifs$ denote the $\sigma$-ideal generated by the sets in $\ifs$. 
So, $\iifs \subseteq X$ is a $\sigma$-ideal of closed subsets of $\R^n$. 
\mys


We recall the following dichotomy theorem of {\color{red}Kechris} and {\color{red}Woodin}:

\begin{thm}[Kechris,Woodin]
Let $\sI$ be a $\bp^1_1$ $\sigma$-ideal of closed sets in a compact metric space.
Then either $\sI$ is $\bp^0_2$ or $\sI$ is $\bp^1_1$-complete.
\end{thm}
\end{frame}



\begin{frame}
Every $F \in \iifs$ is meager. However the meager ideal is $\bp^0_2$. 
A straightforward computation shows that $\iifs$ is $\bs^1_2$.

\begin{thm}
$\iifs$ is $\bp^1_1$-complete.
\end{thm}
\mys

More generally, Let $\sP=\{ p_\alpha\}_{\alpha<\lambda}$ be a family of 
porosity functions,  $p_\alpha \colon \omega \to \omega$.
\mys

Let $\iifs^{\sP}$ be the $\sigma$-ideal generated by the $K(\vec f)$ which have
a porosity function dominated by a $p_\alpha \in \sP$. 
\mys

\end{frame}




\begin{frame}



\begin{thm}
Let $\sP$ be be given and assume there is a $g \colon \omega\to \omega$ 
such that 
\[\forall p \in \sP\ \exists^\infty n\ (\frac{p(n+1)}{p(n)} <g(n)).\]
Then $\iifs^\sP$ is $\bp^1_1$-hard.
\end{thm}


\begin{cor}
There is an uncountable Borel $\sP$ such that $\iifs^\sP$ is 
$\bp^1_1$-hard.
\end{cor}
\mys


When $\sP$ is countable we get the upper bound: $\iifs^\sP$ is $\bp^1_1$.
\end{frame}


\begin{frame}

So we have:
\mys

\begin{itemize}
\item
If $|\sP|<\mathfrak b$, then $\iifs^{\sP}$ is $\bp^1_1$ hard.
\item
If $\sP$ is countable then $\iifs^{\sP}$ is $\bp^1_1$-complete.
\item
If $\sP=\omega^\omega$ then $\iifs^{\sP}$ is $\bp^0_2$. 
\item
There are uncountable Borel $\sP$ for which $\iifs^\sP$ is $\bp^1_1$ hard.
\end{itemize}
\mys


\begin{cor}
The ideal $\iifs^C$ of all $K(\vec f)$ which have a computable porosity function 
is $\bp^1_1$-complete.
\end{cor}


\end{frame}






\begin{frame}
\frametitle{Some questions}

\begin{ques} 
Are there any $\Delta^1_1$ $\sP$ for which $\iifs^{\sP}$ is 
$\bs^1_2$-complete?
\end{ques}
\mys

\begin{ques}
For which $\Delta^1_1$ $\sP$ is $\iifs^{\sP}$ $\bp^0_2$, $\bp^1_1$, 
$\bs^1_2$-complete?
\end{ques}

\end{frame}



\subsection{Sketch of proof of lower bound}
\begin{frame}
Enough to consider $n=1$, in fact work in $[0,1]$.
\mys

Fix a reasonable homeomorphism $h$ between $\ww$ and $\irr \subseteq [0,1]$.
\mys


Let $Tr$ be the Polish space of trees on $\omega$ and $W \subseteq Tr$ the set of wellfounded
trees. So, $W$ is $\bp^1_1$-complete.
\mys

We define a continuous
map $\pi \colon T\to K([0,1])$ reducing $W$ to $\iifs$.
\mys


If $T \in W$ then $\pi(T)$ will be countable, and hence in 
$\iifs$. If $T \notin W$ then we will have $\pi(T)\subseteq  \pi_0(T) \cup \Q$
where $\pi_0(T)\subseteq \irr \cap [0,1]$ is a closed subset of $\irr$.  

\end{frame}




\begin{frame}
We actually define $\pi_0 \colon Tr \to Tr$.
\mys







Fix a function $b\colon \Q \times \omega^{<\omega} \to \omega$ such that for rational 
porosity number $p$ and $s \in \omega^{< \omega}$, we have that for any iterated function system
$\vec f$ with porosity $\geq p$ there is a sequence $t \in \omega^{<\omega}$ of length 
$\leq b(p,s)$ such that $h(s\conc t) \cap K(\vec f)=\emptyset$. 
\mys


This uses the fact that $h$ is reasonable. Actually, $b(p,s)$ depends only on $p$ and $|s|$.
\mys


For each $n$ fix a continuous surjection $h_{1/n}$ from $\ww$ to the Polish space of 
iterated function systems on $[0,1]$ with porosity $p \geq \frac{1}{n}$
and $c \leq 1-\frac{1}{n}$.
\end{frame}






\begin{frame}

\setlength{\unitlength}{1mm}
\begin{centering}
\begin{picture}(200,40)(0,20)
\put(0,50){\line(1,0){25}}
\put(0,45){\line(1,0){25}}
\put(27,47.5){\line(1,0){25}}
\put(27,44){$0$}

\put(55,50){\line(1,0){25}}
\put(55,45){\line(1,0){25}}
\put(82,47.5){\line(1,0){25}}
\put(82,44){$0$}

\put(12.5, 52){$s_0$}
\put(12.5, 41){$t_0$}
\put(39.5,43.5){$v_0$}
\put(-1,44){$\bullet$}
\put(-1,41){$p_0$}




\put(67.5, 52){$s_1$}
\put(67.5, 41){$t_1$}
\put(94.5,43.5){$v_1$}
\put(54,44){$\bullet$}
\put(54,41){$p_1$}


\end{picture}
\end{centering}
\vspace{-30pt}



\begin{itemize}
\item
$s_i$ build a branch through $T$.
\item
$t_i$ build an $\ifs$. Let $\bar{t}=\bar{t}_0\conc \bar{t}_1\conc \cdots$ (drop first digits)
and let $t'_i= (\bar{t})_i= \bar{t}_{\langle i,0\rangle}\conc \bar{t}_{\langle i,1\rangle}\cdots$.
\item
$v_i$ get out of $K(\vec f)$.
\item
$h_{1/t_i(0)}(t'_i)$ is consistent
with being an iterated function system $\vec f$ such that 
$K(\vec f) \cap N_{u_0\conc v_0\conc \cdots \conc v_i} =\emptyset$.
\item
$|v_{i+1}|=b(p, u_0\conc v_0\conc  \cdots  \conc u_{i+1})$ 
where $p=\frac{1}{t_{i+1}(0)}$.
\end{itemize}
\end{frame}

























\end{document}
