Groups with Tarski number $5$
Gili Golan
The Tarski number of a non-amenable group $G$ is the minimal number of pieces in a paradoxical decomposition of $G$. Until now the only numbers which were known to be Tarski numbers of some groups were $4$ and $6$. We construct a group with Tarski number $5$ and mention a related result for Tarski numbers of group actions.
1406.2097.tex
 % Latex file

\documentclass[11pt]{amsart}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amscd}
\usepackage[all]{xy}

\textheight 8.7in
\textwidth=15cm \hoffset=-1.8cm

\newcounter{tmp}
\numberwithin{equation}{section}

\newcounter{AbcT}
\renewcommand{\theAbcT}{\Alph{AbcT}}

\newtheorem {AbcTheorem} [AbcT]{Theorem}

\newtheorem {Theoremintro}    {Theorem}
\newtheorem {Corollaryintro}[Theoremintro]    {Corollary}

\newtheorem {Theorem}    {Theorem}[section]
\newtheorem* {Theorem2}    {Theorem 2}
\newtheorem* {Theorem3}    {Theorem 3}
\newtheorem* {Theorem5}    {Theorem 1(a)}
\newtheorem* {Theorem6}    {Theorem 1(b)}
\newtheorem* {Theorem7}    {Theorem 1(b)}
\newtheorem* {Theorem8}    {Theorem 1(c)}
\newtheorem* {Theorem9}    {Theorem 1(d)}
\newtheorem* {Theorem10}    {Theorem 4}

%\newtheorem* {Definition} {Definition} %[section]
\newtheorem {Problem}    [Theorem]{Problem}
\newtheorem {Question}    [Theorem]{Question}

\newtheorem {Lemma}      [Theorem]    {Lemma}
\newtheorem {Corollary}   [Theorem] {Corollary}
\newtheorem {Proposition}[Theorem]    {Proposition}
\newtheorem {Claim}      [Theorem]    {Claim}
\newtheorem {Observation}[Theorem]    {Observation}
\theoremstyle{remark}
\newtheorem {Remark}		 [Theorem]    {\bf{Remark}}
\newtheorem {Remarks}		 [Theorem]    {\bf{Remarks}}
\newtheorem {Definition} [Theorem]    {\bf{Definition}}
\def\acts{\curvearrowright}


\newtheorem {Conjecture}[Theorem]    {Conjecture}


\newcommand {\Heads}[1]   {\smallskip\pagebreak[1]\noindent{\bf #1{\hskip 0.2cm}}}
\newcommand {\Head}[1]    {\Heads{#1:}}
%\newcommand {\Remark}     {\Head{Remark}}
\newcommand {\Note}       {\Head{Note}}
\newcommand {\equ}[1]     {\eqref{#1}}
\newcommand {\cmod}[1]    {\;\; (\bmod \; #1)}

\newcommand {\defemph}[1] {{\textbf{\textsf{#1}}}}
\newcommand{\Amen}{\mathrm{Amen}}
\newcommand{\Fin}{\mathrm{Fin}}
\newcommand{\Cay}{\mathit{Cay}}

%  ========================
%  COUNTER FOR BIBLIOGRAPHY
%  ========================

\newcounter{DM@bibnum}
\newcommand {\bibnum}     {\stepcounter{DM@bibnum}\parbox[l]{8mm}{[\arabic{DM@bibnum}]}}

%  =========
%  QED SIGNS
%  =========



\newcommand  {\QED}    {\def\qedsymbol{$\square$}\qed}

\newcommand  {\rem}[1] {\underline{\it #1}\marginpar{{\it to do}}}






\newcommand {\F} {{\mathbb F}}
\newcommand {\K} {{\mathbb K}}

\newcommand {\Prob}{{\mathbb P}
}
\newcommand {\Q} {{\mathcal Q}}
\newcommand {\QQ}{{{\mathcal Q}^{1}}}
\newcommand {\A} {{\mathcal A}}
\newcommand {\B} {{\mathcal B}}
\newcommand {\C} {{\mathcal C}}
\newcommand {\bor} {{\mathfrak b}}
\newcommand {\mm} {{\mathfrak {m}}}
\newcommand {\q} {{\mathfrak q}}
\newcommand {\U} {{\mathcal U}}
\newcommand {\T} {{\mathcal T}}
\newcommand {\N} {{\mathcal N}}


\newcommand {\R} {{\mathbb R}}
\newcommand {\BS}{{\mathbb S}}
\newcommand {\Z} {{\mathbb Z}}


\def\vk{{\vskip .3cm}}
\def\hk{{\hskip .3cm}}

\newcommand{\cho}{{x}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\newcommand{\ooplus}{\bigoplus\limits}
\newcommand{\pprod}{\prod\limits}
\newcommand{\frc}{\displaystyle\frac}
\newcommand{\ddt}{\partial_{t}}


\def\KMS{{\rm KMS}}
\def\Lie{{\rm Lie}}
\def\Cent{{\rm Cent}}
\def\Norm{{\rm Norm}}
\def\Stab{{\rm Stab\,}}
\def\Hdim{{\rm Hdim\,}}
\def\Hdiminf{{\rm Hdiminf\,}}
\def\Hdimsup{{\rm Hdimsup\,}}
\def\dimup{\overline{\rm dim}}
\def\dimlow{\underline{\rm dim}}
\def\ad{{\rm ad\,}}
\def\log{{\rm log\,}}
\def\deg{{\rm deg\,}}
\def\dep{{\rm dep\,}}
\def\Der{{\rm Der\,}}
\def\gr{{\rm gr\,}}
\def\Aut{{\rm Aut\,}}
\def\VAut{{\rm VAut\,}}
\def\TAut{{\rm TAut\,}}
\def\Gal{{\rm Gal\,}}
\def\Ker{{\rm Ker\,}}
\def\Im{{\rm Im\,}}
\def\im{{\rm Im\,}}
\def\Tr{{\rm Tr\,}}
\def\tr{{\rm tr\,}}
\def\Tred{{\rm T_{\rm red}\,}}
\def\Nred{{\rm N_{\rm red}\,}}
\def\Norm{{\rm N}}
\def\LT{{\rm LT\,}}
\def\End{{\rm End\,}}
\def\Ind{{\rm Ind\,}}
\def\rk{\rm{rk\,}}
\def\card{{\rm card\,}}
\def\diag{{\rm diag\,}}
\def\height{{\rm ht}}
\def\length{{\rm length}}
\def\Limset{{\rm Limset\,}}

\def\NFp{{\mathcal N(\Fp)}}
\def\NFq{{\mathcal N(\Fq)}}
\def\NSL_2{{\mathcal N SL_2}}
\def\GaF{{\dbG_{\rm a,\dbF}}}


\def\sl{{\mathfrak{sl}}}
\def\gl{{\mathfrak{gl}}}
\def\hd{{\dim_{\rm{H}}}}
\def\Comm{{\rm Comm}}

\def\Spec{{\rm Spec}}
\def\inspec{{\rm Inspec}(J_p)}
\def\dens{{\rm Dense}}
\def\ldens{{\rm LDense}}

\def\Gp{{\rm Gr}}
\def\depth{{\rm depth}}

%Greek letters
\def\alp{\alpha}                \def\Alp{\Alpha}
\def\bet{\beta}
\def\gam{\gamma}                \def\Gam{\Gamma}
\def\del{\delta}                \def\Del{\Delta}
\def\eps{\varepsilon}
\def\veps{\epsilon}
\def\zet{\zeta}
\def\tet{\theta}                \def\Th{\Theta}
\def\th{\theta}
\def\iot{\iota}
\def\kap{\kappa}
\def\lam{\lambda}            \def\Lam{\Lambda}
\def\sig{\sigma}                \def\Sig{\Sigma}
\def\phi{\varphi}
\def\ome{\omega}                \def\Ome{\Omega}

%Calligraphic roman letters
\def\calA{{\mathcal A}}
\def\calB{{\mathcal B}}
\def\calC{{\mathcal C}}
\def\calD{{\mathcal D}}
\def\calE{{\mathcal E}}
\def\calF{{\mathcal F}}
\def\calG{{\mathcal G}}
\def\calH{{\mathcal H}}
\def\calI{{\mathcal I}}
\def\calJ{{\mathcal J}}
\def\calK{{\mathcal K}}
\def\calL{{\mathcal L}}
\def\calM{{\mathcal M}}
\def\calN{{\mathcal N}}
\def\calO{{\mathcal O}}
\def\calP{{\mathcal P}}
\def\calQ{{\mathcal Q}}
\def\calR{{\mathcal R}}
\def\calS{{\mathcal S}}
\def\calT{{\mathcal T}}
\def\calU{{\mathcal U}}
\def\calV{{\mathcal V}}
\def\calW{{\mathcal W}}
\def\calX{{\mathcal X}}
\def\calY{{\mathcal Y}}
\def\calZ{{\mathcal Z}}


%roman letters with a tilde
\def\agal{\tilde a}             \def\Agal{{\widetilde A}}
\def\bgal{\widetilde b}             \def\Bgal{{\widetilde B}}
\def\cgal{\tilde c}             \def\Cgal{{\widetilde C}}
\def\dgal{\tilde d}             \def\Dgal{{\widetilde D}}
\def\egal{\tilde e}             \def\Egal{{\widetilde E}}
\def\fgal{\tilde f}             \def\Fgal{{\widetilde F}}
\def\ggal{\tilde g}             \def\Ggal{{\widetilde G}}
\def\hgal{\tilde h}             \def\Hgal{{\widetilde H}}
\def\igal{\tilde i}             \def\Igal{{\widetilde I}}
\def\jgal{\tilde j}             \def\Jgal{{\widetilde J}}
\def\kgal{\tilde k}             \def\Kgal{{\widetilde K}}
\def\lgal{\tilde l}             \def\Lgal{{\widetilde L}}
\def\mgal{\tilde m}             \def\Mgal{{\widetilde M}}
\def\ngal{\tilde n}             \def\Ngal{{\widetilde N}}
\def\ogal{\tilde o}             \def\Ogal{{\widetilde O}}
\def\pgal{\tilde p}             \def\Pgal{{\widetilde P}}
\def\qgal{\tilde q}             \def\Qgal{{\widetilde Q}}
\def\rgal{\widetilde r}             \def\Rgal{{\widetilde R}}
\def\sgal{\tilde s}             \def\Sgal{{\widetilde S}}
\def\tgal{\tilde t}             \def\Tgal{{\widetilde T}}
\def\ugal{\tilde u}             \def\Ugal{{\widetilde U}}
\def\vgal{\tilde v}             \def\Vgal{{\widetilde V}}
\def\wgal{\widetilde w}             \def\Wgal{{\widetilde W}}
\def\xgal{\tilde x}             \def\Xgal{{\widetilde X}}
\def\ygal{\tilde y}             \def\Ygal{{\widetilde Y}}
\def\zgal{\tilde z}             \def\Zgal{{\widetilde Z}}

%roman letters with a bar
\def\abar{\bar a}               \def\Agag{\overline{\strut A}}
\def\bbar{\bar b}               \def\Bgag{\overline{\strut B}}
\def\cbar{\bar c}               \def\Cgag{\overline{\strut C}}
\def\dbar{\bar d}               \def\Dgag{\overline{\strut D}}
\def\ebar{\bar e}               \def\Egag{\overline{\strut E}}
\def\fbar{\bar f}               \def\Fgag{\overline{\strut F}}
\def\gbar{\bar g}               \def\Gbar{\overline{ G}}
\def\hbar{\bar h}               \def\Hgag{\overline{\strut H}}
\def\ibar{\bar i}               \def\Igag{\overline{\strut I}}
\def\jbar{\bar j}               \def\Jgag{\overline{\strut J}}
\def\kbar{\bar k}               \def\Kgag{\overline{\strut K}}
\def\lbar{\bar l}               \def\Lgag{\overline{\strut L}}
\def\mbar{\bar m}               \def\Mgag{\overline{\strut M}}
\def\nbar{\bar n}               \def\Ngag{\overline{\strut N}}
\def\obar{\bar o}               \def\Ogag{\overline{\strut O}}
\def\pbar{\bar p}               \def\Pgag{\overline{\strut P}}
\def\qbar{\bar q}               \def\Qgag{\overline{\strut Q}}
\def\rbar{\bar r}               \def\Rgag{\overline{\strut R}}
\def\sbar{\bar s}               \def\Sgag{\overline{\strut S}}
\def\tbar{\bar t}               \def\Tgag{\overline{\strut T}}
\def\ubar{\bar u}               \def\Ugag{\overline{\strut U}}
\def\vbar{\bar v}               \def\Vgag{\overline{\strut V}}
\def\wbar{\bar w}               \def\Wgag{\overline{\strut W}}
\def\xbar{\bar x}               \def\Xgag{\overline{\strut X}}
\def\ybar{\bar y}               \def\Ygag{\overline{\strut Y}}
\def\zbar{\bar z}               \def\Zgag{\overline{\strut Z}}

%roman letters with a hat
\def\ahat{\hat a}               \def\Ahat{\widehat {\mathstrut A}}
\def\bhat{\hat b}               \def\Bhat{\widehat {\mathstrut B}}
\def\chat{\hat c}               \def\Chat{\widehat {\mathstrut C}}
\def\dhat{\hat d}               \def\Dhat{\widehat {\mathstrut D}}
\def\ehat{\hat e}               \def\Ehat{\widehat {\mathstrut E}}
\def\fhat{\hat f}               \def\Fhat{\widehat {\mathstrut F}}
\def\ghat{\hat g}               \def\Ghat{\widehat {\mathstrut G}}
\def\hhat{\hat h}               \def\Hhat{\widehat {\mathstrut H}}
\def\ihat{\hat i}               \def\Ihat{\widehat {\mathstrut I}}
\def\jhat{\hat j}               \def\Jhat{\widehat {\mathstrut J}}
\def\khat{\hat k}               \def\Khat{\widehat {\mathstrut K}}
\def\lhat{\hat l}               \def\Lhat{\widehat {\mathstrut L}}
\def\mhat{\hat m}               \def\Mhat{\widehat {\mathstrut M}}
\def\nhat{\hat n}               \def\Nhat{\widehat {\mathstrut N}}
\def\ohat{\hat o}               \def\Ohat{\widehat {\mathstrut O}}
\def\phat{\widehat p}               \def\Phat{\widehat {\mathstrut P}}
\def\qhat{\hat q}               \def\Qhat{\widehat {\mathstrut Q}}
\def\rhat{\hat r}               \def\Rhat{\widehat {\mathstrut R}}
\def\shat{\hat s}               \def\Shat{\widehat {\mathstrut S}}
\def\that{\hat t}               \def\That{\widehat {\mathstrut T}}
\def\uhat{\hat u}               \def\Uhat{\widehat {\mathstrut U}}
\def\vhat{\hat v}               \def\Vhat{\widehat {\mathstrut V}}
\def\what{\hat w}               \def\What{\widehat {\mathstrut W}}
\def\xhat{\hat x}               \def\Xhat{\widehat {\mathstrut X}}
\def\yhat{\hat y}               \def\Yhat{\widehat {\mathstrut Y}}
\def\zhat{\hat z}               \def\Zhat{\widehat {\mathstrut Z}}



%Euler Fracture letters
\def\grA{{\mathfrak A}} \def\gra{{\mathfrak a}}
\def\grB{{\mathfrak B}} \def\grb{{\mathfrak b}}
\def\grC{{\mathfrak C}} \def\grc{{\mathfrak c}}
\def\grD{{\mathfrak D}} \def\grd{{\mathfrak d}}
\def\grE{{\mathfrak E}} \def\gre{{\mathfrak e}}
\def\grF{{\mathfrak F}} \def\grf{{\mathfrak f}}
\def\grG{{\mathfrak G}} \def\grg{{\mathfrak g}}
\def\grH{{\mathfrak H}} \def\grh{{\mathfrak h}}
\def\grI{{\mathfrak I}} \def\gri{{\mathfrak i}}
\def\grJ{{\mathfrak J}} \def\grj{{\mathfrak j}}
\def\grK{{\mathfrak K}} \def\grk{{\mathfrak k}}
\def\grL{{\mathfrak L}} \def\grl{{\mathfrak l}}
\def\grM{{\mathfrak M}} \def\grm{{\mathfrak m}}
\def\grN{{\mathfrak N}} \def\grn{{\mathfrak n}}
\def\grO{{\mathfrak O}} \def\gro{{\mathfrak o}}
\def\grP{{\mathfrak P}} \def\grp{{\mathfrak p}}
\def\grQ{{\mathfrak Q}} \def\grq{{\mathfrak q}}
\def\grR{{\mathfrak R}} \def\grr{{\mathfrak r}}
\def\grS{{\mathfrak S}} \def\grs{{\mathfrak s}}
\def\grT{{\mathfrak T}} \def\grt{{\mathfrak t}}
\def\grU{{\mathfrak U}} \def\gru{{\mathfrak u}}
\def\grV{{\mathfrak V}} \def\grv{{\mathfrak v}}
\def\grW{{\mathfrak W}} \def\grw{{\mathfrak w}}
\def\grX{{\mathfrak X}} \def\grx{{\mathfrak x}}
\def\grY{{\mathfrak Y}} \def\gry{{\mathfrak y}}
\def\grZ{{\mathfrak Z}} \def\grz{{\mathfrak z}}

%Capital roman double letters
\def\dbA{{\mathbb A}}
\def\dbB{{\mathbb B}}
\def\dbC{{\mathbb C}}
\def\dbD{{\mathbb D}}
\def\dbE{{\mathbb E}}
\def\dbF{{\mathbb F}}
\def\dbG{{\mathbb G}}
\def\dbH{{\mathbb H}}
\def\dbI{{\mathbb I}}
\def\dbJ{{\mathbb J}}
\def\dbK{{\mathbb K}}
\def\dbL{{\mathbb L}}
\def\dbM{{\mathbb M}}
\def\dbN{{\mathbb N}}
\def\dbO{{\mathbb O}}
\def\dbP{{\mathbb P}}
\def\dbQ{{\mathbb Q}}
\def\dbR{{\mathbb R}}
\def\dbS{{\mathbb S}}
\def\dbT{{\mathbb T}}
\def\dbU{{\mathbb U}}
\def\dbV{{\mathbb V}}
\def\dbW{{\mathbb W}}
\def\dbX{{\mathbb X}}
\def\dbY{{\mathbb Y}}
\def\dbZ{{\mathbb Z}}

\def\Fp{{\dbF_p}}
\def\Fpt{{\dbF_p[[t]]}}
\def\Fq{{\dbF_q}}
\def\Fqt{{\dbF_q[[t]]}}
\newcommand{\cost}{\text{cost}}
\newcommand{\lb}{\left[}
\newcommand{\rb}{\right]}
\newcommand{\sub}{\subseteq}
\newcommand{\iv}{^{-1}}
\newcommand{\lla}{\la\!\la}
\newcommand{\rra}{\ra\!\ra}
\def\skv{{\vskip .12cm}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\title{Groups with Tarski number $5$}
\author{Gili Golan}
\address{Bar-Ilan University}
\email{gili.golan@math.biu.ac.il}

\subjclass[2000]{Primary 43A07, 20F65
Secondary 20E18, 20F05, 20F50}
\keywords{Tarski number, paradoxical decomposition, random spanning forest}


\begin{abstract}
The Tarski number of a non-amenable group $G$ is the minimal number of pieces
in a paradoxical decomposition of $G$. Until now the only numbers which were known to be Tarski numbers of some groups were $4$ and $6$. We construct a group with Tarski number $5$ and mention a related result for Tarski numbers of group actions.
\end{abstract}
\maketitle

\section{Introduction}
Recall the definition of a \emph{paradoxical decomposition} of a group.

\begin{Definition}\rm
\label{d1}

A group $G$ admits a \emph{paradoxical decomposition}
if there exist positive integers $m$ and $n$, disjoint subsets $P_1,\ldots, P_m,Q_1,\ldots, Q_n$ of $G$
and subsets $S_1=\{g_1,\ldots, g_m\}$, $S_2=\{h_1,\ldots, h_n\}$ of $G$ such that
\begin{equation}\label{eq1}G=\bigcup_{i=1}^m g_i P_i=\bigcup_{j=1}^n h_j Q_j.\end{equation}
The sets $S_1,S_2$ are called the \emph{translating sets} of the paradoxical decomposition.
\end{Definition}
It is well known \cite{Wa} that $G$ admits a paradoxical decomposition if and only if it is non-amenable.
The minimal possible value of $m+n$ in a paradoxical decomposition of $G$
is called the \emph{Tarski number} of $G$ and denoted by $\mathcal T(G)$.
 
It is clear that for any paradoxical decomposition we must have $m\geq 2$ and $n\geq 2$,
so the minimal possible value of Tarski number is $4$. By a theorem of J\'onsson and Dekker (see, for example, \cite[Theorem~5.8.38]{Sa}),  $\calT(G)=4$ if and only if $G$ contains a non-abelian free subgroup. 

Recently it was proved that the set of Tarski numbers is infinite \cite{OS}. At the time, no specific number other than $4$ was known to be a Tarski number. The first and only result of the kind appeared shortly afterwards in \cite{EGS}, where a group with Tarski number $6$ was constructed. The main feature of the proof was the use of random spanning forests on Cayley graphs. We shall use similar techniques to construct a group with Tarski number $5$. 

The notion of paradoxical decompositions and Tarski numbers naturally extends to group actions (see, for example, \cite{Wa}). In this more general setting the problem of determining whether a given number is a Tarski number can be completely resolved. Indeed, for every $n\ge 4$ it is possible to construct a faithful transitive group action with Tarski number $n$. The proof and related results about Tarski numbers of group actions will appear at a future paper %IYH.

\vskip .12cm
{\bf Acknowledgments.} The author would like to thank Mikhail Ershov and Andrei Jaikin Zapirain for useful discussions and Mark Sapir for useful discussions and comments on the text. Part of the research was done during the author's stay at the University of Virginia. She wishes to express her gratitude for the accommodations and hospitality.

\section{Groups with Tarski number $5$}

In what follows we shall make use of the following criterion which follows from Lemma 2.5 and Theorem 2.6 in \cite{EGS}.

\begin{Lemma}\label{lemma}
Let $G$ be a group and $S_1,S_2$ finite subsets of $G$. The following are equivalent.
\begin{enumerate}
\item $G$ has a paradoxical decomposition with translating sets $S_1,S_2$.
\item For any pair of finite subsets $A_1,A_2\in G$, $|A_1S_1\cup A_2S_2|\ge |A_1|+|A_2|.$
\end{enumerate}
\end{Lemma}

\begin{Proposition}
\label{prop:Betti}
Let $G$ be a group generated by $S=\{a,b,c\}$ and assume that $a$ is an element of infinite order. If $\cost(G)\ge 2.5$ then $G$ has a paradoxical decomposition with translating sets $S_1=\{1,a\},S_2=\{1,b,c\}$. 
\end{Proposition}

\begin{proof}
Fix a pair of finite subsets $A_1,A_2$ of $G$. By Lemma \ref{lemma} it suffices to prove that $|A_1S_1\cup A_2S_2|\ge |A_1|+|A_2|$.
Let $\Gamma=\Cay(G, S\cup S^{-1})$ be the right Cayley graph of $G$ with respect to $S\cup S^{-1}$ considered as an unoriented graph
without multiple edges. The key result we shall use is the theorem of Thom \cite[Theorem~3]{Thom} which asserts that there exists a $G$-invariant random spanning forest $\mu$ of $\Gamma$ such that $\mu$-a.s the forest contains all edges labeled by $a^{\pm 1}$ and the expected degree of a vertex in $\mu$ is at least $2 \cost(G\acts [0,1]^E)$ where $E$ is the set of edges of $\Gamma$ and the action $G\acts [0,1]^E$ is the natural action.


An immediate corollary is that there exists an ordinary
 forest $\mathcal F$ on $\Gamma$ (depending on $A_2$) such that all edges labeled by $a^{\pm 1}$ belong to $F$ and
\begin{equation}
\label{eq:forest}
\sum_{g\in A_2}\deg_{\mathcal F}(g)\geq 2 \cost(G\acts [0,1]^E)|A_2| \ge 2\cost(G)|A_2|\ge 5|A_2|.
\end{equation}
\vskip .12cm

Let $E$ be the set of all directed edges  $(g,gs)$ such that $g\in A_2$, $s\in S\cup S^{-1}$ and the unoriented edge
$\{g,gs\}$ lies in $\mathcal F$. Let $E_1$ be the subset of $E$ consisting of all edges $(g,gs)\in E$ with $s\in S\setminus S^{-1}$. Note that $|E|\geq 5|A_2|$ by \eqref{eq:forest}, and it is clear that $|E_1|\geq |E|-|S||A_2|$,
so that $|E_1|\geq 2|A_2|$.

Since the sets $S\setminus S^{-1}$ and $(S\setminus S^{-1})^{-1}$ are disjoint, $E_1$ does not contain
a pair of opposite edges. Also, the label of every edge in $E_1$ belongs to $\{a,b,c\}$. 
Thus, if $E_2$ denotes the set of edges $(g,gs)\in E_1$ such that $g\in A_2$ and $s\in \{b,c\}$, $|E_2|\ge  |E_1|-|A_2|\ge |A_2|$. 

Let $E_3$ be the set of directed edges $(g,ga)$ for $g\in A_1$. Clearly, $E_2$ and $E_3$ are disjoint sets and $E_2\cup E_3$ does not contain a pair of opposite edges.
The endpoints of edges in $E_2\cup E_3$ lie in the set $A_1S_1\cup A_2S_2$.
Let $\Lambda$ be the unoriented graph with vertex set $A_1S_1\cup A_2S_2$
and edge set $E_2\cup E_3$ (with forgotten orientation). Then $\Lambda$ is a subgraph of $\mathcal F$;
in particular $\Lambda$ is a (finite) forest. Hence
$$|A_1S_1\cup A_2S_2|=|V(\Lambda)|>|E(\Lambda)|= |E_3|+|E_2|\ge |A_1|+|A_2|,$$ as desired.
\end{proof}

\begin{Theorem}\label{Cor}
Let $F=\la a,b,c\ra$ be a free group of rank $3$. Let $r_1,r_2,\dots\in \gamma_2F$ be an enumeration of the elements of the derived subgroup of $F$. Let $R=\{r_i^{p^{n_i}}\}$ for some integer sequence $n_1,n_2,\ldots$ such that $\sum_{i}\frac{1}{p^{n_i}}\le\frac{1}{2}$. Then for $G=\la X| R\ra$, $\mathcal T(G)=5$.
\end{Theorem}

\begin{proof}
By \cite[Theorem B.1]{EGS} $G$ has a quotient $Q$ such that $\beta_1(Q)\ge 1.5$ where $\beta_1(Q)$ is the first $L^2$-Betti number of $Q$. In addition, $Q$ can be chosen so that the image of $a$ in $Q$ has infinite order. Indeed, as in the proof of \cite[Theorem B.1]{EGS}, let $R_m=\{r_i^{p^{n_i}}\}_{i=1}^m$, $G(m)=\la X|R_m\ra$ and $G(m)_p$ be the image of $G(m)$ in its pro-$p$ completion. Then, if $G(m)_p=F/N_m$, by the argument in \cite{EGS}, for $Q=F/\bigcup_{m\in\mathbb{N}}N_m$, $\beta_1(Q)\ge 1.5$. Assume by contradiction that the image of $a$ in $Q$ has finite order. Then, for some $m\in\mathbb{N}$, the image of $a$ in $G(m)_p$ is also of finite order. Let $Ab\colon F\to \mathbb{Z}^3$ be the abelianization homomorphism. Since $R_m\sub \gamma_2F$, $Ab$ induces a homomorphism $Ab\colon G(m)\to \mathbb{Z}^3$. Let $i_{\mathbb{Z}^3}\colon \mathbb{Z}^3\to\widehat{\mathbb{Z}^3}_p$ and $i_{G(m)}\colon G(m)\to \widehat {G(m)}_p$ be the natural homomorphisms from $\mathbb{Z}^3$ and $G(m)$ to their pro-$p$ completions. Then, $\phi=i_{\mathbb{Z}^3}\circ Ab\colon G(m)\to \widehat{Z^3}_p$ is a homomorphism from $G(m)$ to a pro-$p$ group. Clearly, $\phi$ is continuous when $G(m)$ is equipped with the pro-$p$ topology. Thus, it can be extended in a unique way to a homomorphism $\psi \colon \widehat{G(m)}_p\to \widehat{Z^3}_p$ for which $\psi \circ i_{G(m)}=\phi$. Since the image of $a$ under $\phi$ has infinite order in $\widehat{Z^3}_p$, $i_{G(m)}(a)$ must have an infinite order in $G(m)_p\sub\widehat{G(m)}_p$, a contradiction.  

Now we are ready to prove the theorem. For a quotient $Q$ with the properties mentioned above, $\cost(Q)\ge \beta_1(Q)+1\ge 2.5$. Thus, Proposition \ref{prop:Betti} applied to $Q$ implies that $\mathcal T(Q)\le 5$. Since $Q$ is a quotient of $G$, $\mathcal T(G)\le \mathcal T(Q)\le 5$ (see, for example, \cite[Theorem 5.8.16]{Sa}). Since $G$ is torsion-by-abelian it doesn't contain any free non abelian subgroup. Hence, by the theorem of J\'onsson and Dekker mentioned above $\mathcal T(G)\neq 4$. Therefore $\mathcal T(G)=5$ as required. 
\end{proof}


\begin{thebibliography}{AAA}

\bibitem{CSGH}
T.~Ceccherini-Silberstein, R.~Grigorchuk and P.~de~la~Harpe,
\textit{Amenability and paradoxical decompositions for pseudogroups and discrete metric spaces}, Proc. Steklov Inst. Math. 224 (1999), no. 1, 57 --97.


\bibitem{EGS} M. Ershov, G. Golan and M. Sapir,
\it The Tarski numbers of groups, 
\rm http://arxiv.org/abs/1401.2202 


\bibitem{OS}
 N.~Ozawa and M.~Sapir,
\textit{Non-amenable groups with arbitrarily large Tarski number?},
mathoverflow question 137678.

\bibitem{Sa} M.~Sapir,
\emph{Combinatorial algebra: syntax and semantics},\\ http://www.math.vanderbilt.edu/$\sim$msapir/book/b2.pdf.

\bibitem{Thom} A.~Thom,
\it The expected degree of minimal spanning forests,
\rm http://arxiv.org/abs/1306.0303


\bibitem{Wa} S.~Wagon,
\it The Banach-Tarski paradox,
\rm Cambridge University Press, (1985).

\end{thebibliography}

\end{document}



1406.2097.extracted_bib
{CSGH T.~Ceccherini-Silberstein, R.~Grigorchuk and P.~de~la~Harpe, Amenability and paradoxical decompositions for pseudogroups and discrete metric spaces, Proc. Steklov Inst. Math. 224 (1999), no. 1, 57 --97.
1406.2097.extracted_bib
{EGS M. Ershov, G. Golan and M. Sapir, The Tarski numbers of groups, \rm http://arxiv.org/abs/1401.2202
1406.2097.extracted_bib
{OS N.~Ozawa and M.~Sapir, Non-amenable groups with arbitrarily large Tarski number?, mathoverflow question 137678.
1406.2097.extracted_bib
{Sa M.~Sapir, Combinatorial algebra: syntax and semantics,\\ http://www.math.vanderbilt.edu/$\sim$msapir/book/b2.pdf.
1406.2097.extracted_bib
{Thom A.~Thom, The expected degree of minimal spanning forests, \rm http://arxiv.org/abs/1306.0303
1406.2097.extracted_bib
{Wa S.~Wagon, The Banach-Tarski paradox, \rm Cambridge University Press, (1985).