%%%%%%
%
% Last changed: 30 November, 2003 (by Waldek)
%
%%%%%

\documentclass[a4paper,12pt]{amsart}
%\documentclass[a4paper,12pt]{article}
\usepackage{doublespace}
\usepackage{amsfonts,amssymb}
\usepackage{amsmath}
%\usepackage{showkeys}
\usepackage[T1]{fontenc}
\fontencoding{T1}
\usepackage[latin1]{inputenc}

\setstretch{1.5}

\theoremstyle{plain}
\newtheorem{theo}{Theorem}[section]
\newtheorem{pro}[theo]{Proposition}
\newtheorem{lem}[theo]{Lemma}

\theoremstyle{definition}
\newtheorem{defn}[theo]{Definition}

\theoremstyle{remark}
\newtheorem{remark}[theo]{Remark}
\newtheorem{notation}[theo]{Notation}

\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\arc}{arc}

\newcommand{\eps}{\varepsilon}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\elL}{L}

\newcommand{\period}{\;.}
\newcommand{\comma}{\;,}
\newcommand{\dilate}{\mathcal{D}}

\newcommand{\norm}[1]{\Vert#1\Vert}

\begin{document}

\title[Multipliers and singular integrals]{Multipliers and singular
integrals on exponential growth groups}
\author{Waldemar Hebisch}
\address{Institute of Mathematics, Wroc{\l}aw University, and 
Institute of Mathematics, PAN}
\email{hebisch@math.uni.wroc.pl}
\author{Tim Steger}
\address{Istituto Di Matematica e Fisica, Universit\`a degli Studi di
Sassari, Via Vienna 2, 07100 Sassari, Italia}
\email{steger@ssmain.uniss.it}
\thanks{Both authors are part of the European TMR network entitled
``Harmonic Analysis''.  The first author was partially supported by
KBN grant {\tt 5 P03A 050 20} and by the TMR network.  The second
author was partially supported by his university and by the
Italian M.U.R.S.T}


\begin{abstract}
We propose a simple abstract version of Calder\'on--Zygmund theory,
which is applicable to spaces with exponential volume growth, and then
show that important specific operators can be treated within this
framework.
\end{abstract}
 
%\cite{CGGM:weak}

\maketitle

\section{Abstract Calder\'on--Zygmund theory}
Throughout we use the usual convention that $C$~stands for a positive
constant, usually a large positive constant, whose precise value
varies from occurrence to occurrence. 
%, even from line to line.  
However,
to avoid writing such curiosities as ``$C+C+3C\leq C$'' we sometimes
use $C',C'',\dots$ instead of~$C$.  The precise values of
$C',C'',\dots$ also change from occurrence to occurrence.

\begin{defn}\label{CZ}
We say that the space~$M$ with metric~$d$ and Borel measure~$\mu$ has
the \emph{Calder\'on--Zygmund property} if there exists a constant~$C$
such that for every~$f$ in~$L^1$ and for every
$\lambda>C\frac{\|f\|_{L^1}}{\mu(M)}$ ($\lambda>0$ if $\mu(M)=\infty$)
we have a decomposition $f=\sum f_i+g$, such that there exist sets
$Q_i$, numbers $r_i$, and points $x_i$ satisfying:
\begin{itemize}
\item $f_i=0$ outside $Q_i$,
\item $\int f_i\,d\mu=0$,
\item $Q_i\subset B(x_i,Cr_i)$,
\item $\sum \mu(Q^{*}_i) \leq C\frac{\|f\|_{L^1}}{\lambda}$, where
$Q^{*}_i=\{x: d(x,Q_i)< r_i\}$, 
\item $\sum \|f_i\|_{L^1}\leq C\|f\|_{L^1}$,
\item $|g|\leq C\lambda$.
\end{itemize}
Since $g=f-\sum f_i$, we have $\norm{g}_{L^1}\leq C'\norm{f}_{L^1}$,
hence $\norm{g}_{L^2}^2\leq C''\lambda\norm{f}_{L^1}$.
\end{defn}

If $K(x,y)$ is any measurable kernel defined on $M\times M$, then
let~$K$ also denote the associated integral operator:
\begin{equation*}
(Kf)(x)=\int_M K(x,y)f(y)\,dy \period
\end{equation*}

\begin{theo}\label{singi}
If $M$ has the Calder\'on--Zygmund property, if $T=\sum_{n\in\mathbb{Z}}
K_n$ is bounded on~$L^2$, and if for constants $C$, $0<c<1$, $a>0$, $b>0$
\begin{gather*}
\int |K_n(x,y)|(1+c^nd(x,y))^a\,dx\leq C
\comma \\
\int |K_n(x,y)-K_n(x,z)|\,dx\leq C(c^nd(y,z))^{b}
\comma
\end{gather*}
then $T$ is of weak type $(1,1)$ and bounded on $L^p$, $1<p\leq 2$.
\end{theo}
\begin{remark} If $\sum K_n$ is strongly convergent 
on $L^2$, then easy extensions to our arguments show that the sum is
also strongly convergent on $L^p$, $1<p\leq 2$ and is convergent in
measure for arguments in $L^1$.  Similarly, almost everywhere
convergence on $L^2$ implies almost everywhere convergence on $L^p$,
$1\leq p \leq 2$.
\end{remark}
\begin{remark}
We find the given formulation very convenient. However, the assumption about 
$K_n$ may be replaced by the weaker condition
$$\int_{d(x,y),d(x,z)>\varepsilon d(y,x)} |K(x,y)-K(x,z)|d\mu(x)
\leq C_\varepsilon$$
with $\varepsilon>0$ small enough.
\end{remark}
\begin{lem}\label{inta}
Let $f_i$, $Q_i$, $r_i$, $x_i$, and $Q_i^*$ be as in \ref{CZ}.
Then there exists~$C$ such that for all $i$
\begin{equation*}
\sum_{n:c^nr_i\geq
1}\int_{(Q_{i}^{*})^{c}} |K_{n}f_{i}|(x)\,dx \leq C \|f_{i}\|_{L^{1}}
\period 
\end{equation*}
\end{lem}
\begin{proof}
\begin{multline*}
\int_{(Q_{i}^{*})^{c}}
|K_{n} f_{i}|(x)\,dx \\
\leq \|f_{i}\|_{L^{1}}\sup_{y \in Q_{i}}
\int_{(Q_{i}^{*})^{c}}|K_{n}(x,y)|\,dx
\leq \|f_{i}\|_{L^{1}}\sup_{y}
\int_{ d(x,y)\geq r_i}|K_{n}(x,y)|\,dx \\
\leq (c^nr_i)^{-a}\|f_{i}\|_{L^{1}}\sup_{y}
\int_{ d(x,y)\geq r_i}|K_{n}(x,y)|(1+c^{n}d(x,y))^{a}\,dx \\
\leq C(c^nr_i)^{-a}\|f_{i}\|_{L^{1}}
  \period
\end{multline*}
Hence,
\begin{equation*}
\sum_{n:c^nr_i\geq 1}\int_{(Q_{i}^{*})^{c}}
|K_{n}f_{i}|(x)\,dx 
\leq C \|f_{i}\|_{L^{1}} \sum_{n:c^nr_i\geq 1}(c^nr_i)^{-a}
\leq C' \|f_{i}\|_{L^{1}}
\period\qed
\end{equation*}
\renewcommand{\qed}{}
\end{proof}

\begin{lem}\label{intb}
Let $f_i$, $Q_i$, $r_i$, $x_i$, and $Q_i^*$ be as in \ref{CZ}.
Then there exists~$C$ such that for all $i$
\begin{equation*}
\sum_{n:c^nr_i< 1}\int
|K_{n}f_{i}|(x)\,dx \leq C \|f_{i}\|_{L^{1}}
\period
\end{equation*}
\end{lem}
\begin{proof} Since $\int f_{i}(y)dy=0$,
\begin{align*}
\int|K_{n}f_{i}|(x)\,dx
&=\int\left|\int_{Q_{i}} K_{n}(x,y)f_{i}(y)dy\right|\,dx \\
&=\int\left|\int_{Q_{i}}
  (K_{n}(x,y)-K_{n}(x,x_i))f_{i}(y)dy\right|\,dx \\
&\leq \int \int_{Q_{i}} |K_{n}(x,y)-K_{n}(x,x_i)||f_{i}(y)|dy \,dx \\
&\leq \|f_{i}\|_{L^{1}} \sup_{y\in Q_{i}}\int
  |K_{n}(x,y)-K_{n}(x,x_i)|\,dx \\
&\leq C\|f_{i}\|_{L^{1}}\sup_{y\in Q_{i}} (c^nd(y,x_i))^{b}
\leq C'(c^nr_i)^{b}\|f_{i}\|_{L^{1}}
\period
\end{align*}
Hence,
\begin{equation*}
\sum_{n:c^nr_i<1}\int|K_{n}f_{i}|(x)\,dx 
\leq \sum_{n:c^nr_i<1}C'(c^nr_i)^{b}\|f_{i}\|_{L^{1}}
\leq C''\|f_{i}\|_{L^{1}}
\period\qed
\end{equation*}

\renewcommand{\qed}{}
\end{proof}

\begin{proof}[Proof of \ref{singi}]
By the Marcinkiewicz interpolation theorem 
it is enough to show that $T$ is of weak type $(1,1)$. 
Fix $\lambda>0$. 
If $\lambda\leq C\frac{\|f\|_{L^1}}{\mu(M)}$, then
\begin{equation*}
\mu(\{x:|Tf|>\lambda\})\leq\mu(M)\leq C\frac{\|f\|_{L^1}}{\lambda}
\end{equation*}
and we are done.
So assume that $\lambda>C\frac{\|f\|_{L^1}}{\mu(M)}$ and fix a Calder\'on--Zygmund 
decomposition of $f$. Put $E=\{x:\sum_{n,i}|K_{n}f_i|>\frac{\lambda}{2}\}$, 
$E_1=\bigcup_{i}Q_i^{*}$. By \ref{inta} and \ref{intb},
\begin{multline*}
\int_{E_1^c}\sum_{n,i}|K_{n}f_i|\leq \sum_i\int_{(Q_i^{*})^c}
\sum_{n}|K_{n}f_i|
\leq C\sum_i\|f_i\|_{L^1}\leq C'\|f\|_{L^1}
\end{multline*}
so
\begin{equation*}
|E-E_1|\leq \frac{2C'\|f\|_{L^1}}{\lambda}
\period
\end{equation*}
Now
\begin{multline*}
|\{x:|Tf(x)|>\lambda\}|\leq |\{x:|Tg(x)|>\frac{\lambda}{2}\}|
+|E| \\
\leq \frac{4\|Tg\|^2_{L^2}}{\lambda^2}
+|E_1|+|E-E_1|
\leq \frac{C''\lambda\|f\|_{L^1}}{\lambda^2}+C\frac{\|f\|_{L^1}}{\lambda}
+\frac{2C'\|f\|_{L^1}}{\lambda} \\
\leq C'''\frac{\|f\|_{L^1}}{\lambda}
\period\qed
\end{multline*}
\renewcommand{\qed}{}
\end{proof}

\begin{remark}
The above proof of~\ref{singi} remains valid using the weaker
hypotheses of sublinearity, namely
\begin{gather*}
|(Tf)(x)|\leq\sum_n|(K_nf)(x)|
  \comma \\
|(K_n(f_1+f_2))(x)|\leq|(K_nf_1)(x)|+|(K_nf_2)(x)|
  \period
\end{gather*}
\end{remark}

\section{Main theorems}\label{intro}

Let~$T$ be a homogeneous tree of order~$q+1$ (so each vertex has
$q+1$~neighbours). On~$T$ we consider the natural distance~$d$ (length
of the shortest path between two vertices). We fix an infinite
geodesic~$g$ in~$T$. We fix a numeration of the vertices in~$g$ (so we
get a mapping $N:g\mapsto \mathbb{Z}$ such that $|N(x)-N(y)|=d(x,y)$
for $x,y\in g$).  

Think of the tree as hanging down from the point at infinity defined
by the ray of~$g$ where $N\to +\infty$.  With that picture in mind we
define the level function, $l(x)$, by the formula
$l(x)=N(x')-d(x,x')$, where $x'$ is the unique vertex of~$g$ closest
to~$x$.  Let $(Af)(x)=\frac{1}{2\sqrt
q}\sum_{d(x,y)=1}q^{(l(y)-l(x))/2}f(y)$.  For a complex function $f$
on the tree we define the gradient $\nabla f$ by the formula
\begin{equation*}
(\nabla f)(x)=\sum_{y:d(x,y)=1}|f(y)-f(x)|
\period
\end{equation*}
We define the measure $\mu$ on $T$ by the formula
\begin{equation*}
\int f \,d\mu = \sum f(x)q^{l(x)}
\period
\end{equation*}

Note that $A$~is self-adjoint on $\elL^2(d\mu)$.  Also note that
$\norm{A}_{\elL^1(d\mu)\to\elL^1(d\mu)}\leq 1$, hence that
$\norm{A}_{\elL^p(d\mu)\to\elL^p(d\mu)}\leq 1$ for $1\leq
p\leq\infty$.  Thus the $\elL^2$-spectrum of~$A$ lies in~$[-1,1]$.
For any $\theta\in\RR$ the function $q^{i\theta l(x)}$ is
``almost'' in $\elL^2(d\mu)$.  More precisely $q^{i\theta
l(x)}e^{-\eps d(x,x_0)}\in\elL^2(d\mu)$ for any $\eps>0$ 
and $x_0\in T$.  One
calculates that $A(q^{i\theta l(x)})=\cos\theta\,q^{i\theta l(x)}$ and
a slightly more involved calculation using $q^{i\theta
l(x)}e^{-\eps d(x,x_0)}$ shows that $\cos\theta$ is in the
$\elL^2$-spectrum of~$A$.  Hence:
\begin{remark}
The $\elL^2$-spectrum of~$A$ is precisely~$[-1,1]$.
\end{remark}
\begin{notation}
If $t>0$ and if $H(\lambda)$ is any function defined for real~$\lambda$,
\begin{equation*}
(\dilate_t H)(\lambda)=H(t\lambda)
  \period 
\end{equation*}
\end{notation}
\begin{theo}\label{multtree} Fix any nonzero~$\phi\geq 0$ in
$C_c^\infty([1/4,2])$.  Suppose that $F(\lambda)=H(1+\lambda)$ 
(or $F(\lambda)=H(1-\lambda)$) where
$\supp H\subset[0,2)$.  If for some $s>3/2$
\begin{equation*}
\sup_{t>0} \|(\dilate_t H)\phi\|_{H(s)}<\infty \comma
\end{equation*}
then $F(A)$ is of weak type $(1,1)$ and bounded on $L^p(d\mu)$, 
$1<p<\infty$.   Moreover $\nabla (I-A)^{-1/2}$ is 
of weak type $(1,1)$ and bounded on $L^p$, $1<p\leq 2$.
\end{theo}

Let $G=\RR\ltimes\RR^{Q}$ with $s\in\RR$ acting on~$\RR^Q$ by
$n\mapsto e^{-s}n$.  Multiplication is given by
\begin{equation*}
(s_1,n_1)(s_2,n_2)=(s_1+s_2,e^{s_2}n_1+n_2)
\period
\end{equation*}
This $G$ is the Iwasawa (or $AN$) group corresponding to the real
rank~$1$ symmetric space $SO_+(Q+1,1)/SO(Q)$.  There is a
distinguished Laplacian on~$G$, which is up to a first order term (or
up to conjugation) equal to the Laplace--Beltrami operator on the
symmetric space.  \emph{Right-invariant} vector fields are
\begin{equation*}
X_0=\partial_a
\comma\qquad\qquad
% \\
X_i=e^{a}\partial_{n_i}
  \qquad\text{for $i=1,\dots,Q$.}
\end{equation*}
Then we put
\begin{equation*}
L=-\sum_{0\leq i \leq Q}X_i^2
\period
\end{equation*}
We consider $L$ on $L^{p}(G)$ with respect to \emph{left-invariant}
Haar measure $dx$ (which is equal to Lebesgue measure in our
coordinates).

\begin{theo}\label{multan}
Fix any nonzero~$\phi\geq 0$ in $C_c^\infty([1/2,2])$.  
If $s_0,s_1>\frac{3}{2}$, $s_1>\frac{Q+1}{2}$,
\begin{align*}
\sup_{t\geq 1}
\|(\dilate_t F)\phi\|_{H(s_0)} &<\infty
\comma \\
\sup_{0<t\leq 1}
\|(\dilate_t F)\phi\|_{H(s_1)} &<\infty
\comma
\end{align*}
then $F(L)$ is of weak type $(1,1)$ and bounded on $L^p$,
$1<p<\infty$. Moreover $\nabla L^{-1/2}$ is 
of weak type $(1,1)$ and bounded on $L^p$, $1<p\leq 2$.
\end{theo}

\section{Covering lemma on the weighted tree}

We defined the measure~$\mu$ on~$T$ by the formula
\begin{equation*}
\int f \,d\mu = \sum f(x)q^{l(x)}
\period
\end{equation*}
We will write $|R|$ as a shorthand for the measure~$\mu(R)$.
Say that $x$~lies \emph{below}~$y$ (and that $y$ lies
\emph{above}~$x$) if $l(x)=l(y)-d(x,y)$.  Say that $R\subset T$ is an
\emph{admissible trapezoid} iff $R$ consists of a single point~$x_R$,
or if there is $x_R\in T$ and an integer $h>0$, such that $R$ consists
of all $x$ below $x_R$ such that $h \leq l(x_R)-l(x) < 2h$.  Put
$h(R)=h$ in this second case and $h(R)=1$ in the one point case.  In
either case one finds $|R|=h(R)q^{l(x_R)}$.  We call $w(R)=q^{l(x_R)}$ the
\emph{width} of~$R$.  
%\\ ??? FIGURE HERE ???

For an admissible trapezoid $R$ we define its \emph{envelope} $\tilde
R$ as follows: if $R$ consists of one point, then $\tilde R=R$,
otherwise $\tilde R$ consists of all $x$ below $x_R$ such that $h/2
\leq l(x_R)-l(x) < 4h$.  Note that if $R_1\cap R_2\ne \emptyset$ and
$w(R_1)\geq w(R_2)$, then $R_2\subset \tilde R_1$. It is also easy to
check that $|\tilde R|\leq 4|R|$. We define a maximal function $M$ by
the formula
\begin{equation*}
(Mf)(x)
=\sum_{x\in R}|R|^{-1}\int |f(y)|\,d\mu(y)
=\sup_{x\in R}|R|^{-1}\sum_{y\in R}|f(y)|q^{l(y)}
\end{equation*}
where the $\sup$ is taken over admissible trapezoids~$R$.

\begin{theo}\label{covt}$T$ with measure $\mu$ and distance $d$ 
has the Calder\'on--Zygmund property.  Furthermore $M$ is of 
weak type $(1,1)$.
\end{theo}

\begin{proof}
Let $f\in\elL^1(d\mu)$.  Let $S_0$~be the family of all admissible
trapezoids~$R$ such that
\begin{equation*}
\sum_{x\in R} |f(x)|q^{l(x)}\geq \lambda |R|
\period
\end{equation*}
Start by listing~$S_0$ in some arbitrarily chosen order.  Choose $R_0$
to be an admissible trapezoid in $S_0$ of largest width (possible
since the width is bounded by $|R|$, and
$|R|\leq\norm{f}_{\elL^1}/\lambda$).  In case of ties, choose that
trapezoid of largest width which occurs earliest in the listing
of~$S_0$.  Now we proceed inductively: $S_{i+1}$ consists of all $R\in
S_i$ disjoint from $R_0,\dots,R_i$ and $R_{i+1}$ is an admissible
trapezoid in $S_{i+1}$ of largest width.  Since the~$R_i$ are
disjoint, and since each $R_i\in S$ we have
\begin{equation*}
\sum_i |R_i| \leq
\frac{1}{\lambda}\sum_i \sum_{x\in R_i} |f(x)|q^{l(x)}
\leq \frac{\|f\|_{L^1}}{\lambda}
\period
\end{equation*}
Consequently
\begin{equation*}
\sum_i |\tilde R_i| \leq 4\sum_i |R_i| 
\leq \frac{4\|f\|_{L^1}}{\lambda}
\period
\end{equation*}
If $\sum_{x\in R} |f(x)|q^{l(x)}\geq \lambda |R|$, then by
construction $R$~intersects some~$R_i$ with width not smaller then the
width of~$R$, hence with $R\subset \tilde R_i$.  So, putting $E=\bigcup
\tilde R_i$, we have $Mf\leq \lambda$ outside $E$, and $|E|\leq
\frac{4\|f\|_{L^1}}{\lambda}$, so the second claim is proved.

To get the~$f_i$ in the Calder\'on--Zygmund decomposition, we first define 
auxiliary sets $U_i$ and functions $h_i$ as follows:
\begin{equation*}
U_i=\tilde R_i-\bigcup_{j<i}\tilde R_j
\comma
\end{equation*}
$h_i(x)=f(x)$ for $x\in U_i$ and $h_i(x)=0$ for $x\not\in U_i$.
We claim that
\begin{equation*}
\sum_x |h_i(x)|q^{l(x)}\leq 6q\lambda |\tilde R_i|
\period
\end{equation*}
Indeed it is easy to find three admissible trapezoids $P_1$, $P_2$,
$P_3$, such that $w(P_k)>w(R_i)$ ($k=1,2,3$), $|P_k|\leq 2q
|\tilde R_i|$, and $\tilde R_i\subset P_1\cup P_2 \cup P_3$.  If
\begin{equation*}
\sum_{x\in P_k} |f(x)|q^{l(x)}\geq \lambda |P_k|
\comma
\end{equation*}
then there is~$j<i$ such that $P_k\cap R_j\neq\emptyset$, hence
$P_k\subset \tilde R_j$, hence $h_i$~is zero on~$P_k$.  One way or the
other $\sum_{x\in P_k} |h_i(x)|q^{l(x)}\leq \lambda |P_k|$, which
means that
\begin{equation*}
\sum_x |h_i(x)|q^{l(x)}
\leq \sum_{k=1}^3\sum_{x\in P_k} |h_i(x)|q^{l(x)}
\leq \sum_{k=1}^3 \lambda|P_k|
\leq 6q\lambda|\tilde R_i|
\end{equation*}
as claimed.  We put
\begin{gather*}
f_i=h_i-\biggl(\sum_{x}h_i(x)q^{l(x)}\biggr)\frac{\chi_{R_i}}{|R_i|}
  \comma \qquad\qquad
g=f-\sum f_i
  \period
\end{gather*}
Now we put $Q_i=\tilde R_i$, $r_i=h(R_i)/4$ and we choose 
arbitrary $x_i\in R_i$. The conditions $f=g+\sum f_i$, 
$f_i=0$ outside $Q_i$, and $\int f_i \,d\mu=0$ hold by definition. 
It is easy to check that $Q_i\subset B(x_i,32r_i)$. It is also easy 
to check that $|Q_i^{*}|\leq 2|Q_i|$ so
\begin{equation*}
\sum |Q_i^{*}|\leq 2|\tilde R_i|\leq \frac{8\|f\|_{L^1}}{\lambda}
\period
\end{equation*}
Clearly
\begin{equation*}
\sum_{i}\int |f_i|\leq 2 \sum_{i}\int |h_i| \leq 2\int |f|=2\|f\|_{L^1}
\period
\end{equation*}
%Also, 
%$$\left|\frac{\sum_{x}h_i(x)q^{l(x)}}{|R_i|}\right|
%\leq \frac{9q\lambda |\tilde R_i|}{|R_i|}
%\leq 45q\lambda$$
Now, $g$~is equal to~$f$ outside $E=\bigcup \tilde R_i$, and 
\begin{equation*}
g=\sum_i \left( \sum_{x}h_i(x)q^{l(x)}\right)\frac{\chi_{R_i}}{|R_i|}
\end{equation*}
on $E$. 
Since $(Mf)(x)\leq \lambda$ outside~$E$, a fortiori
$g(x)=f(x)\leq\lambda$ 
outside~$E$. On~$E$ we observe that the~$R_i$ 
are disjoint so 
\begin{equation*}
\sup_{x\in E} |g|(x)\leq \sup_{i}
\left|\frac{\sum_{x}h_i(x)q^{l(x)}}{|R_i|}\right|
\leq \sup_{i} \frac{6q\lambda |\tilde R_i|}{|R_i|}
\leq 24q\lambda
\end{equation*}
which ends the proof.
\end{proof}

\section{Integral kernels on the weighted tree}

%Consider homogeneous tree $T$ of order $q+1$ (each vertex has $q+1$ 
%neighbours). On $T$ we consider natural distance $d$ (length of the 
%shortest path between two points). We choose an infinite geodesic 
%$g$ in $T$. We fix a numeration 
%of vertices in $g$ (so we get mapping $N:g\mapsto Z$). For every 
%vertex $x$ in $T$ there is a unique closest vertex $x'$ on $g$. 
%We define level function by the formula $l(x)=N(x')-d(x,x')$.

% such that on $g$ it agrees 
% with the fixed numeration, and in general  of $g$ 
Let $(Lf)(x)=\sum_{d(x,y)=1}f(y)$. The spectral resolution of $L$ is 
given by the formula:
\begin{equation*}
(F(L)f)(x)=\frac{q}{2\pi(q+1)}
  \int_{0}^{\pi} F(2\sqrt{q}\cos\theta)
\sum_y\frac{\phi_\theta(x,y)}{|c_\theta|^2}f(y)\,d\theta
\end{equation*}
where
\begin{equation*}
\phi_\theta(x,y)=q^{-d(x,y)/2}\left(c_{s}e^{i\theta d(x,y)}+
                        \bar{c}_{s}e^{-i\theta d(x,y)}\right)
        =q^{-d(x,y)/2}2\Re(c_{s}e^{i\theta d(x,y)})
\end{equation*}
and
\begin{equation*}
c_{s}=\frac{-qi}{q+1}\frac{1}{2\sin\theta}\left(e^{i\theta}-\frac{1}{q}e^{-i\theta}\right)
\period
\end{equation*}
When $q$ is odd (so the tree may by identified with a free group)
the formula is given in \cite{FTP:haf} as Theorem 4.1 
(one must change notation: $q\mapsto 2r-1$, $\theta\mapsto \log(2r-1)t$). 
For even $q$ the formula (and the proof) in \cite{FTP:haf} still works.
%Let $Af(x)=\sum_{d(x,y)=1}q^{(l(y)-l(x))/2}f(y)$. 
Let~$q^{l/2}$ stand for the operator $f(x)\mapsto q^{l(x)/2}f(x)$.  We
have $2\sqrt{q}q^{l/2}A=Lq^{l/2}$ so
\begin{multline*}
(F(A)f)(x)=
\frac{q}{2\pi(q+1)}\int_{0}^{\pi} F(\cos\theta)q^{-l(x)/2} \\
  \times
\sum_y q^{l(y)/2}q^{-d(x,y)/2}2\Re(c_{s}e^{i\theta d(x,y)})
  \frac{1}{|c_\theta|^2}f(y)\,d\theta
\period
\end{multline*}
%Note that if we forget about the real part above the operator 
%gets bigger for real $F$. For our purpose smooth factors of $F$ 
%are harmless, so we write
To simplify the sequel we put $\tilde A=I-A$. 
For our purpose we may treat the real and imaginary parts of~$F$ 
separately, so we may assume that $F$ is real. Then
\begin{multline*}
F(\tilde A)(x,y)=\Re\left(K(x,y)\int_0^{\pi} F(1-\cos\theta)
e^{i\theta d(x,y)}\eta(\theta)\sin\theta\,d\theta\right)
 \\
=\Re(K(x,y)E_F(d(x,y)))
\end{multline*}
where
\begin{gather*}
K(x,y)=q^{(-l(y)-l(x)-d(x,y))/2}
\comma
 \\
\eta(\theta)=\frac{q}{2\pi(q+1)}\frac{2}{{\bar c}_s\sin\theta}=
\frac{q}{2\pi(q+1)}\frac{4(q+1)}{qi\left(e^{-i\theta}-\frac{1}{q}e^{i\theta}\right)}
  \\=\frac{2}{\pi i\left(e^{-i\theta}-\frac{1}{q}e^{i\theta}\right)}
\end{gather*}
and
\begin{equation}\label{eq:EF}
E_F(k)=\int_0^{\pi}
   F(1-\cos\theta)e^{i\theta k}\eta(\theta)\sin\theta\,d\theta
\period
\end{equation}

% ??? DELETE THIS LEMMA ???
\begin{lem}\label{sobv} Let $s\geq 0$ and let~$m$ be the integer
satisfying $s\leq m$.  Let $a<b$, $c<d$ be fixed constants.  Suppose
$\phi:\RR\to\RR$~is $C(m)$ and
increasing with $\phi(c)<a$, $\phi(d)>b$, $\phi'>0$. Then there is~$C$
depending only on $a$, $b$, $c$, $d$, $s$, $\|1/(\phi')\|_{L^{\infty}}$ 
and~$\|\phi\|_{C(m)}$ such
that
\begin{equation*}
\|F\circ\phi\|_{H(s)}\leq C\|F\|_{H(s)}
\period
\end{equation*}
whenever $\supp F\subset[a,b]$.
\end{lem}

\begin{proof} 
This lemma only formulates a well-known fact.
\end{proof}

\begin{lem}\label{sumf}
Fix $\eps$, $0<\eps\leq 1$.  If $s>\frac{3}{2}+\eps$, then there
exists~$C>0$ such that if for any nonnegative integer~$n$ we have 
\begin{equation*}
\supp F\subset[2^{-2n-1},2^{-2n+2}]\cap[0,3/2],
\end{equation*}
 then
\begin{gather*}
\sum_{k=0}^{\infty}|E_F(k)|(1+k)(1+2^{-n}k)^\eps\leq
C\|\dilate_{2^{-2n}}F\|_{H(s)}
\comma
 \\
\sum_{k=0}^{\infty}|E_F(k)|(1+2^{-n}k)^\eps\leq
C2^{-n}\|\dilate_{2^{-2n}}F\|_{H(s)}
\comma
 \\
\sum_{k=0}^{\infty}|E_F(k+1)-E_F(k)| \, (1+k)(1+2^{-n}k)^\eps
\leq C2^{-n}\|\dilate_{2^{-2n}}F\|_{H(s)}
\period
\end{gather*}
\end{lem}
\begin{proof} Put
\begin{equation*}
F(x)=(\dilate_{2^{2n}} G)(x)=G(2^{2n}x)
\period
\end{equation*}
Changing variables in equation~\ref{eq:EF} to $t=2^{n}\theta$ we get
\begin{multline*}
E_F(k)=2^{-n}\int_{1}^{\pi}G(2^{2n+1}\sin^2(2^{-n-1}t))
\eta(2^{-n}t)\sin(2^{-n}t)e^{i2^{-n}tk}\,dt
 \\
=2^{-2n}\int_{1}^{\pi} H(t)\psi_l(t)e^{itm}\,dt
=2^{-2n}\int_{1}^{\pi} \tilde H_l(t)e^{itm}\,dt
\end{multline*}
where $k=2^{n}m+l$, $0\leq l< 2^n$
\begin{gather*}
\tilde H_l(t)=H(t)\psi_l(t)
\comma
 \\
H(t)=G(2^{2n+1}\sin^2(2^{-n-1}t))
\comma
 \\
\psi_l(t)=e^{i2^{-n}tl}2^{n}\sin(2^{-n}t)\eta(2^{-n}t)
\period
\end{gather*}
One easily sees that $\psi_l(t)$ and its derivatives are bounded
uniformly in $n$, $l$ and $t\in[0,\pi]$. Also, 
each of the derivatives
of $\phi_n=2^{2n+1}\sin^2(2^{-n-1}t)$ is uniformly bounded in~$n$ and
$\phi_n'$ is uniformly bouded from below on counterimage of $\supp G_n$,
so by \ref{sobv}
\begin{equation*}
\|\tilde H_l\|_{H(s)}\leq C\|H\|_{H(s)}\|\psi_l\|_{C(s)}
\leq C'\|G\|_{H(s)}
\period
\end{equation*}
Hence 
\begin{multline*}
\sum_{k=0}^{\infty} |E_F(k)|\,(1+k)(1+2^{-n}k)^\eps
 \\
\leq 2^{n+1}\sum_{l=0}^{2^{n}-1}\sum_{m=0}^{\infty}
|E_F(2^{n}m+l)|\,(1+m)^{1+\eps}
 \\
\leq 2^{n+1}\sum_{l=0}^{2^{n}-1}\left(\sum_{m=0}^{\infty}
(|E_F(2^{n}m+l)|\,(1+m)^{s})^2\right)^{1/2}
\left(\sum_{m=0}^{\infty}(1+m)^{2(1+\eps-s)}\right)^{1/2}
 \\
\leq C2^{n+1}2^{-2n}\sum_{l=0}^{2^{n}-1}\|\tilde H_l\|_{H(s)}
\leq C''\|G\|_{H(s)}=C''\|\dilate_{2^{-2n}}F\|_{H(s)}
\period
\end{multline*}
The second estimate follows similarly. For the third estimate one
should note that
$e^{i(k+1)\theta}-e^{ik\theta}=(1-e^{i\theta})e^{ik\theta}$ and then
the first factor contributes $2^{-n}$ to the final result.
\end{proof}

Recall that for a complex function $f$ on the tree we define the
gradient~$\nabla f$ by the formula
\begin{equation*}
(\nabla f)(x)=\sum_{w:d(x,w)=1}|f(w)-f(x)|
\period
\end{equation*}
The gradient so defined is a sublinear operator. 

\begin{lem}\label{suml} 
Suppose $d(y,z)=1$ and $l(z)=l(y)-1$.  Then
\begin{gather*}
\sum_{x:d(x,y)=k}K(x,y)q^{l(x)}=
  \begin{cases}
    1 &\text{for $k=0$} \\
    2+\frac{q-1}{q}(k-1) &\text{for $k>0$}
  \end{cases}
\comma
 \\
\sum_{x:d(x,y)=k}|K(x,y)-K(x,z)|q^{l(x)}\leq 2
\comma
 \\
\sum_{x:d(x,y)=k}|\nabla_x K(x,y)|q^{l(x)}=1-\frac{1}{q}\leq 2
\period
\end{gather*}
\end{lem}
\begin{proof}
Every vertex at distance~$k$ from~$y$ is reached starting from~$y$
making $p$~steps up and then $k-p$~steps down. There is only one
possibility for each step up, while we have $q$ choices when making a
step down. However, we should not go back on our steps, so if $p,k-p>0$, then we have
only $q-1$ possibilities for the first step down.  Also, note that
$l(x)-l(y)=2p-k$.  Hence
\begin{multline*}
\sum_{x:d(x,y)=k}q^{(-l(y)-l(x)-d(x,y))/2}q^{l(x)}=
\sum_{x:d(x,y)=k}q^{(-l(y)+l(x)-k)/2}
 \\
=q^{k}q^{(-k-k)/2}
  +\biggl(\sum_{p=1}^k (q-1)q^{k-p-1}q^{(2p-k-k)/2}\biggr)
  +q^{(2k-k-k)/2}
 \\
=1+\frac{q-1}{q}\biggl(\sum_{p=1}^{k-1} 1\biggr) +1
\period
\end{multline*}
In the second sum, values of $K(x,y)$ and $K(x,z)$ are equal, unless
$x$~lies below~$z$, so we get only the $p=0$~term in the sum over $p$.

Similarly, in the third sum only the $p=k$~term gives a nonzero
contribution.  Moreover, for the unique~$x$ contributing to the
$p=k$~term, the contribution $|K(w,y)-K(x,y)|$ to $\nabla_x K(x,y)$ is
zero for all but one~$w$.  For that one~$w$, which is the unique
vertex at distance one to~$x$ which lies above~$x$, we have
$l(w)=l(x)+1$, $d(w,y)=d(x,y)+1$, and $K(w,y)=\frac{1}{q}K(x,y)$.
%\\ ??? INSERT FIGURE HERE ???
\end{proof}

\begin{lem}\label{sumb}
Fix $\eps$, $0<\eps\leq 1$. 
If $s>\frac{3}{2}+\eps$,
then there is~$C$ such that if $n$ is a nonnegative integer and 
$\supp F\subset[2^{-2n-1},2^{-2n+2}]\cap[0,3/2]$, then 
\begin{gather*}
\sum_x |F(\tilde A)(x,y)|\,(1+2^{-n}d(x,y))^\eps q^{l(x)}\leq
C\|\dilate_{2^{-2n}}F\|_{H(s)}
\comma
 \\
\sum_x |F(\tilde A)(x,y)-F(\tilde A)(x,z)|q^{l(x)}\leq C2^{-n}d(y,z)
\|\dilate_{2^{-n}}F\|_{H(s)}
\comma
 \\
\sum_x |\nabla_x F(\tilde A)|(x,y)\,
  (1+2^{-n}d(x,y))^\eps q^{l(x)}\leq C2^{-n}
    \|\dilate_{2^{-n}}F\|_{H(s)}
\period
\end{gather*}
\end{lem}
\begin{proof} We will prove only the second inequality 
(the first is easier, the third is similar to the second). 
It is enough to prove the lemma for real~$F$.
We may assume that $d(y,z)=1$ and that $l(z)=l(y)-1$. 
Then
\begin{multline*}
\sum_x |F(\tilde A)(x,y)-F(\tilde A)(x,z)|q^{l(x)}
 \\
=
\sum_x |\Re(K(x,y)E_F(d(x,y))-K(x,z)E_F(d(x,z)))|q^{l(x)}
 \\
\leq \sum_x |K(x,y)-K(x,z)||E_F(d(x,y))|q^{l(x)}
 \\
+
\sum_x K(x,z)|E_F(d(x,y))-E_F(d(x,z))|q^{l(x)}=S_1+S_2
\period
\end{multline*}
Now, by \ref{sumf} and \ref{suml}
\begin{multline*}
S_1=\sum_k |E_F(k)|\sum_{x:d(x,y)=k}|K(x,y)-K(x,z)|q^{l(x)}
 \\
\leq 2\sum_k |E_F(k)| \leq C 2^{-n}\|\dilate_{2^{-n}}F\|_{H(s)}
\period
\end{multline*}
To estimate the second sum note that if $d(x,z)=k$ then $d(x,y)=k\pm
1$, so $|E_F(d(x,y))-E_F(d(x,z))|\leq
|E_F(k+1)-E_F(k)|+|E_F(k)-E_F(k-1)|$ (formally putting
$E_F(-1)=E_F(0)$).  Then (again using \ref{sumf} and \ref{suml})
\begin{multline*}
S_2\leq\sum_k (|E_F(k+1)-E_F(k)|+|E_F(k)-E_F(k-1)|)
    \sum_{x:d(x,z)=k}K(x,z)q^{l(x)}
 \\
\leq 4\sum_k|E_F(k+1)-E_F(k)|\,(1+k)
 \\
\leq C 2^{-n}\|\dilate_{2^{-n}}F\|_{H(s)}
\period\qed
\end{multline*}
\renewcommand{\qed}{}
\end{proof}

\begin{proof}[Proof of \ref{multtree}] Let $(-1)^l$ represent the
operator $f(x)\mapsto (-1)^{l(x)}f(x)$.  Observe that
$-(-1)^lAf=A((-1)^lf)$.  That is, $A$ is conjugated to~$-A$ by an
operator which preserves all $\elL^p(d\mu)$-norms as well as the
weak-$\elL^1(d\mu)$ measure of the size of a function.  Consequently,
it is sufficient to prove the first claim of the theorem in the case
$F(\lambda)=H(1-\lambda)$.

By standard estimates, the principal hypothesis on~$H$ is independent
of the choice of~$\phi$.  Now fix nonnegative $\phi,\psi\in
C_c^{\infty}([1/2,4])$ such that $\phi=\psi^2$, and for all $x>0$
$\sum_{n=-\infty}^{\infty}\phi(2^{2n}x)=1$. We have
\begin{equation*}
H(x)=\sum_{n=-\infty}^{\infty} G_n(x) = \sum_{n=0}^{\infty} G_n(x)
  \qquad\text{where}\qquad
G_n(x)=\phi(2^{2n}x)H(x)
\period
\end{equation*}
Of course 
\begin{equation*}
H(\tilde A)= \sum_{n=0}^{\infty} G_n(\tilde A)
\period
\end{equation*}
We are going to show that the $G_n(\tilde A)$ satisfy the assumptions
of \ref{singi}.  By hypothesis, there is $s>\frac{3}{2}$ and $C$
independent of~$n$ such that
\begin{equation*}
\|\dilate_{2^{-2n}}G_n\|_{H(s)}\leq C
\period
\end{equation*}
Fix~$\eps$, $0<\eps\leq 1$, such that $s>\frac{3}{
2}+\eps$.  By \ref{sumb}
\begin{multline*}
\int |G_n(\tilde A)|(x,y)\,(1+2^{-n}d(x,y))^\eps \,d\mu(x)
 \\
=
\sum_x |G_n(\tilde A)(x,y)|\,(1+2^{-n}d(x,y))^\eps q^{l(x)}\leq
C\|\dilate_{2^{-2n}}G_n\|_{H(s)}\leq C'
\end{multline*}
so the first assumption of \ref{singi} is satisfied. 
Similarly the second assumption of \ref{singi} follows directly 
from \ref{sumb} so we get first claim of \ref{multtree}.

To get the second claim write
\begin{multline*}
\frac{1}{\sqrt{t}}=\sum_n \frac{\phi(2^{2n}t)}{\sqrt{t}}=\sum_n U_n(t)
% \\
=\sum_n \frac{\psi(2^{2n}t)}{\sqrt{t}}\psi(2^{2n}t)=
\sum_n V_n(t)W_n(t)
\period
\end{multline*}
It is easy to see that (for any $s>0$) 
\begin{gather*}
\|\dilate_{2^{-2n}}U_n\|_{H(s)}=\|2^n U_0\|_{H(s)}=C2^n
\comma
 \\
\|\dilate_{2^{-2n}}V_n\|_{H(s)}=\|2^n V_0\|_{H(s)}=C2^n
\comma
\end{gather*}
and
\begin{equation*}
\|\dilate_{2^{-2n}}W_n\|_{H(s)}=\|W_0\|_{H(s)}=C
\period
\end{equation*}
Using the third part of \ref{sumb} we have for some $C=C(s)$
\begin{equation*}
\int |\nabla_x V_n(\tilde A)(x,y)|\,d\mu(x)\leq C
\end{equation*}
so using the second part of \ref{sumb} we get
\begin{multline*}
\int |\nabla U_n(\tilde A)(x,y) - \nabla U_n(\tilde A)(x,z)|\,d\mu(x)
  \\
\leq\left(\sup_w \int |\nabla V_n(\tilde A)(x,w)|\,d\mu(x)\right)
\\ \times 
 \left(\int |W_n(\tilde A)(w,y) - W_n(\tilde A)(w,z)|\,d\mu(w)\right)
\leq C'2^{-n}d(y,z)
  \period
\end{multline*}
In this way we have checked that
\begin{equation*}
\nabla U_n(\tilde A)
\end{equation*}
satisfies the second assumption of \ref{singi}. 
%\\ ??? NOT REALLY ??? \\
We verify the first
assumption of \ref{singi} by direct application of \ref{sumb}
to~$U_n(t)$.  This ends the proof.
\end{proof}

\section{A covering lemma on certain AN groups}

Let $G=\RR\ltimes N$, $N=\RR^n$. 
We assume that the multiplication is given by the formula
\begin{multline*}
(t,x_1,\dots,x_n)(s,y_1,\dots,y_n)
  \\
=(t+s,\exp(a_1s)x_1+y_1,\dots,\exp(a_ns)x_n+y_n)
\end{multline*}
where the $a_i\ne 0$ are real numbers. In the sequel we will pretend that
$a_i$ are positive, negative $a_i$ are easy but tedious to handle. 
One easily checks that Lebesgue
measure on $\RR^{n+1}$ is left invariant, so we may take it as Haar
measure. On~$G$ we consider the natural right-invariant riemanianian
distance given by $ds^{2}=dt^2+\sum \exp(-2ta_i)\,dx^2_i$.  Put
$M=2\max(1,a_1,\dots,a_n)$.  Note that for large balls (say $r>1$) we
have
\begin{equation*}
\{(t,x):|x|<ce^cr,|t|<cr\}
\subset B(0,r)\subset \{(t,x):|x|<e^{Mr},|t|<r\}
\end{equation*}

\begin{lem}\label{stim}
$G$~has the Calder\'on--Zygmund property.
\end{lem}

We need some preparation before the proof. We say that a 
parallelopiped $R$ is admissible iff $(t,x)\in R$ if and only if 
%$$(t,x)\in R \equiv 
\begin{equation*}
t\in [m_02^{k_0},(m_0+1)2^{k_0})
\comma
\end{equation*}
%\qquad 
\begin{equation*}
x_i\in[m_i2^{k_i},(m_i+1)2^{k_i})\text{\qquad for $i=1,\dots,n$}
\end{equation*}
where $m_i$, $k_i$ for $i=0,\dots,n$ are integers and for $k_0<0$ we have 
\begin{equation*}
e^{2M}2^{k_0}\leq\exp(-a_i(m_0+\frac{1}{2})2^{k_0}) 2^{k_i}
\leq 4e^{8M}2^{k_0}
\end{equation*}
$i=1,\dots,n$ and for $k_0\geq 0$ we have 
\begin{equation*}
\exp(M2^{k_0+1})\leq\exp(-a_i(m_0+\frac{1}{2})2^{k_0})2^{k_i}
\leq 4\exp(M2^{k_0+3})
\period
\end{equation*}
We will write $R=R(k_0,\dots,k_n,m_0,\dots,m_n)$.

Note that there is $C$ such that if $R=R(k_0,\dots,k_n,m_0,\dots,m_n)$ is 
an admissible 
parallelopiped, $x_R$ is the centerpoint of $R$ and $r_R=2^{k_0}$, 
then $R\subset B(x_R,Cr_R)$ and $|R^{*}|=|\{x: d(x,R)<r_R\}|\leq 3 2^Q$.


\begin{lem}\label{part}
If $Q$ is an admissible parallelopiped, then there exists 
a sequence of partitions $\mathcal{P}_j$ of $Q$ such that
\begin{itemize}
\item each $\mathcal{ P}_j$ consists of admissible parallelopipeds,  
\item for each $j$ all $R\in\mathcal{ P}_j$ have a common $k_0$
\item for each $R\in\mathcal{ P}_j$ either $R\in\mathcal{ P}_{j+1}$ or $R$ is 
a sum of two members of $\mathcal{ P}_{j+1}$ (of equal volumes).
\item the parallelopipeds in $\mathcal{ P}_j$ are arbitrarily small for 
large $j$.
\end{itemize}
\end{lem}
\begin{proof} 
We write
\begin{multline*}
\mathcal{ P}_j=\{R(k_0,\dots,k_n,m_0,\dots,m_n)\subset Q: 
k_0=f_0(j)
\comma
 \\
k_i=f_i(j,m_0), i=1,\dots,n\}
\end{multline*}
where $f_i$ are to be specified. 
Now, the second condition 
is satisfied by definition. 
To satisfy the third condition we require that either 
$f_0(j+1)=f_0(j)$ and $f_i(j,m_0)-1\leq f_i(j+1,m_0)\leq f_i(j,m_0)$ 
or $f_0(j+1)=f_0(j)-1$ and $f_i(j+1,2m_0)=f_i(j+1,2m_0+1)=f_i(j,m_0)$. 
The first case correspond to splitting (some of) parallelopipeds in 
$x$ coordinates, the second corresponds to splitting all parallelopipeds 
into half in $t$ coordinate. 
As a normalization we also require that $f_0(0)=k_0$, that when 
splitting in $x$ we perform as many splittings as allowed by admissibility 
condition, and that $\mathcal{ P}_j\ne\mathcal{ P}_{j+1}$. 
 
%To prove the lemma it is enough to show that given (a candidate for) 
%$\mathcal{ P}_j$ we can divide it (define $\mathcal{ P}_{j+1}, \mathcal{ P}_{j+2},\dots$) 
%so that eventually $f_0$ gets arbitrarily small. Namely, $\mathcal{ P}_j$ is 
%fully determined by $f_i$, and for finite set $A$ of $j$ and 
%$B$ of $m_0$ our 
%rules allow only finite number of restrictions of $f_0$ to $A$ 
%and restrictions of $f_i$ to $A\times B$. So 
%at least one of those possibilities allows extension to to arbitrarily 
%large $A$ and $B$. Now axiom of choice allows as to choose consistent 
%set of extensions, giving $\mathcal{ P}_j$ as required.

To finish the proof we should show how to divide $\mathcal{ P}_j$. 
If $f_0(j)\leq 0$, then in each step we just substract one from $f_i$ 
(cycling over $i$, $i=0,\dots,n$). So in the sequel we need only 
to handle $f_0(j)>0$. 
Our rules make as keep $f_0(j)$ unchanged and decrease 
$f_i(j,m_0)$, $i=1,\dots,n$ as long as admissibility allows. So, 
we may assume that splitting in $x$ coordinates is forbidden.
Hence, we have
%$f_0(k+k)=f_0(j)$ and 
\begin{equation*}
\exp(M2^{f_0(j)+1})
\leq\exp(-a_i(m_0+\frac{1}{2})2^{f_0(j)})2^{f_i(j,m_0)}
\leq 2\exp(M2^{f_0(j)+1})
\end{equation*}
Now according to our rules, we make $f_0(j+1)=f_0(j)-1$,  
$f_i(j+1,2m_0)=f_i(j+1,2m_0+1)=f_i(j,m_0)$
and we should check 
that the result is admissible. However
\begin{multline*}
\exp(-a_i(2m_0+\frac{1}{2})2^{f_0(j+1)})=
\exp(-a_i(m_0+\frac{1}{4})2^{f_0(j)})
 \\
\geq\exp(-a_i(m_0+\frac{1}{2})2^{f_0(j)})
\exp(-M2^{f_0(j)})
\end{multline*}
so
\begin{multline*}
\exp(-a_i(2m_0+\frac{1}{2})2^{f_0(j+1)})2^{f_i(j+1,2m_0)}
 \\
\geq\exp(-M2^{f_0(j)})\exp(-a_i(m_0+\frac{1}{2})2^{f_0(j)})2^{f_i(j,m_0)}
 \\
\geq\exp(-M2^{f_0(j)})\exp(M2^{f_0(j)+1})
 \\
=\exp(M2^{f_0(j)})=\exp(M2^{f_0(j+1)+1})
\end{multline*}
which gives one of admissibility conditions (lower bound for $2m_0$). 
Similar, computation gives upper bound for $2m_0+1$, and 
two other bounds (upper bound for $2m_0$ and lower bound for $2m_0+1$). 
%are immediate.
\end{proof}

\begin{proof}[Proof of \ref{stim}] Fix $f$ and $\lambda>0$. We should
decompose $f$.  First, note that there is a partition $\mathcal{ P}$
of $G$ into dyadic parallelopipeds such that for each $Q\in\mathcal{
P}$ we have $|Q|>\|f\|_{L^1}/\lambda$. 
Namely, let $\psi_i(l,m_0)$ be the largest integers so that 
$R(l,\psi_1(l,m_0),\dots,\psi_n(l,m_0),m_0,m_1,\dots,m_n)$
is admissible. We take $l$ large enough and
enough and write 
\begin{multline*}
%\mathcal{ P}
G=\bigcup_{m_i\in\mathbb{Z},m_0\in\{0,-1\}}
R(l,\psi_1(l,m_0),\dots,\psi_n(l,m_0),\dots,m_0,m_1,\dots,m_n)
 \\
\cup\bigcup_{k\geq l,m_i\in{\Bbb Z},m_0\in\{1,-2\}}
R(k,\psi_1(k,m_0),\dots,\psi_n(k,m_0),m_0,m_1,\dots,m_n)
\period
\end{multline*}
Next, on each $Q\in\mathcal{ P}$ we apply \ref{part} and use standard
stopping time argument.
\end{proof}

%parallelopiped $Q$, and that 
%$$\int_{Q}|f| \leq \lambda |Q|\period$$
%Indeed, we may take $m=2^{n+1}$ dyadic parallelopipeds $Q_i$ 
%having $0$ as a vertex, and make them big enough, so that 
%$$\int_{G} |f| \leq 2\sum\int_{Q_i}|f|$$
%and
%$$\int_{Q_i} |f| \leq \lambda |Q_i|\period$$

%Consider sequence of operators $P_j$ given by the formula 
%$$(P_jf)(x)=|R|^{-1}\int_R f
%\text{\qquad for $x\in R$, where $R\in\mathcal{ P}_j$}$$
%(so $P_j$ is the conditional expectation with respect to $\mathcal{ P}_j$).
%One easily sees that $\|P_j\|_{L^1}=1$, moreover if $R\in \mathcal{ P}_j$, 
%$\chi_R$ is the indicator function of $R$, then for $i\geq j$ we have 
%$P_i\chi_R=\chi_R$. So the sequence $P_j$ is strongly convergent on $L^1$ 
%to identity when $j\rightarrow\infty$.

\section{Integral kernels on Lie groups}

On a Lie group with right-invariant distance
function~$d(\cdot,\cdot)$, let $d(x)=d(x,e)$, so $d(x,y)=d(xy^{-1})$.

\begin{theo}\label{keri} Assume $G$ and $L$ are as in \cite{H:ed}. 
If $\eps>0$, if $s_0,s_1>\frac{3}{2}+\eps$, if $s_1>\frac{Q+1}{2}+\eps$,
then there is $C$ such that for $\supp F\subset[1/2,2]$ and $t\geq 1$
\begin{equation*}
\int |F(tL)|(x)\,(1+t^{-1/2}d(x))^{\eps}\leq C \|F\|_{H(s_0)}
\end{equation*}
while for $0<t\leq 1$
\begin{equation*}
\int |F(tL)|(x)\,(1+t^{-1/2}d(x))^{\eps}\leq C \|F\|_{H(s_1)}
\period
\end{equation*}
%Moreover, for $t>1$ 
%
\begin{equation*}
%\int p_t^2w \leq  Ct^{-1}
\end{equation*}
%and 
%
\begin{equation*}
%\int p_t^2w^\frac{Q-1}{Q}\leq C t^{-3/2}\period
\end{equation*}
\end{theo}

\begin{proof} This follows using the methods of \cite{H:ed}.
\end{proof}

In particular, \ref{keri} applies to the group in the statement of
Theorem~\ref{multan}, namely $G=\RR\ltimes\RR^Q$ where $s\in\RR$~acts
on $\RR^Q$ via $n\mapsto e^{-s}n$.  For our next result, \ref{gradi},
our attention will be exclusively on that group.

We recall several conventions relative to convolution and the modular
function.  As always, convolution of measures is defined by
\begin{equation*}
\int_G f(x)\,d(\mu_1*\mu_2)(x)
=\int_{G\times G} f(yz)\,d\mu_1(y)\,d\mu_2(z)\period
\end{equation*}
The $*$-operation on measures is $d\mu^*(x)=d\bar\mu(x^{-1})$.  One
has $(\mu_1*\mu_2)^*=\mu_2^* * \mu_1^*$.  For Dirac measures
$\delta_x*\delta_y=\delta_{xy}$ and $(\delta_x)^*=\delta_{x^{-1}}$.
If $\norm{\mu}$ stands for the total variation, then
$\norm{\mu_1*\mu_2}\leq\norm{\mu_1}\,\norm{\mu_2}$,
$\norm{\mu^*}=\norm{\mu}$.

The base measure on~$G$, denoted simply by $dx$, is taken as
\emph{left-invariant} Haar measure, and thus $d^*x$ is
right-invariant Haar measure.  The modular function is defined by
$d^*x=\delta(x)\,dx$.  It follows that
\begin{multline*}
d(xx_0)=d^*(x_0^{-1}x^{-1})
  =\delta(x_0^{-1}x^{-1})\,d(x_0^{-1}x^{-1}) \\
  =\delta(x_0^{-1}x^{-1})\,d(x^{-1})
  =\delta(x_0^{-1}x^{-1})\,d^*(x)
  =\delta(x_0^{-1})\,d(x)
\period 
\end{multline*}
For the group under consideration, $\RR\ltimes\RR^Q$, one finds that
$dx$~is ordinary Lebesgue measure and $\delta(s,n)=e^{-Qs}$.

For the purposes of convolution and the $*$-operation, we identify the 
function~$f(x)$ with the measure~$f(x)\,dx$.  One then finds:
\begin{align*}
(f_1*f_2)(x)&=\int_G f_1(y)f_2(y^{-1}x)\,dy\comma
  &
(\delta_x*f)(z)&=f(x^{-1}z)\comma
  \\
f^*(x)&=\delta(x)\bar f(x^{-1})\comma
  &
(f*\delta_x)(z)&=\delta(x)f(zx^{-1})
  \period
\end{align*}
Having fixed this identification it is automatic that
$(f_1*f_2)^*=f_2^* * f_1^*$, $(f*\delta_x)^*=\delta_{x^{-1}}*f^*$,
etc.  Since $L^1$-norm (relative to $dx$) corresponds to total
variation, one has
$\norm{f_1*f_2}_{L^1}\leq\norm{f_1}_{L^1}\norm{f_2}_{L^1}$,
$\norm{f^*}_{L^1}=\norm{f}_{L^1}$.  The inner product for $L^2(dx)$  may
be written as $\langle f_1,f_2\rangle=(f_2^* * f_1)(e)$.

As explained in Section~\ref{intro} we work with the
\emph{right-invariant} vector fields $X_i$, and the right-invariant
Laplacian~$L$ given by
\begin{gather*}
X_0=\partial_s
  \comma
  \qquad\ \ 
X_i=e^{s}\partial_{n_i},\text{\ $i=1,\dots,Q$}
  \comma
  \qquad\ \ 
L=-\sum_{0\leq i\leq Q} X_i^2 
\period
\end{gather*}
On $L^2(dx)$ this Laplacian is symmetric and may be extended to a
positive self-adjoint operator.  Let $p_t$ be the \emph{heat kernel}
for $(G,L)$, meaning that $\exp(-tL)(f)=p_t*f$.  Since $\exp(-tL)$ is
self-adjoint, one has $p_t=p_t^*$.

We use the (right-invariant) distance function adapted to the
vector fields $X_i$, $0\leq i\leq Q$.  Here follows the usual
definition.  For fixed $x,y\in G$ consider all smooth curves
$\gamma:[0,1]\to G$ such that $\gamma(0)=x$, $\gamma(1)=y$.  For
such a curve write $\gamma'(t)=\sum_i a_i(t)X_i$.  Then
\begin{equation*}
d(x,y)=\inf_{\gamma}
  \biggl(\int_0^1 \sum_i |a_i(s)|^2 \,ds\biggr)^{1/2}\period
\end{equation*}
It follows that $|(X_i d)(x)|\leq 1$ in the Lipschitz sense.  For the
group under consideration~$d(x)$ is smooth (except at~$x=e$), so this
inequality is valid in the naive sense (except at~$x=e$).

\begin{theo}\label{gradi} Assume $G=\RR\ltimes\RR^Q$ and $L$ are as in
\ref{multan}. There exist~$C$ and $\eps>0$ such that uniformly in $t>0$
\begin{equation*}
\sum_i \int |X_ip_t(x)|\exp(\eps t^{-1/2}d(x))\,dx \leq Ct^{-1/2}
\period
\end{equation*}
\end{theo} 

\begin{proof}  As long as $t$ is bounded from above the 
estimate follows easily from well-known pointwise bounds on the 
heat kernel, see for example \cite{H:est} (in fact \cite{H:est} is an 
overkill, since for elliptic operators the estimates we need where already 
known in the sixties).
%\\ ??? REFERENCE ??? \\
So it is enough to prove our claim for $t>1$.

We may assume that $Q=2l$ is even.  Indeed $G_Q$ is a quotient of
$G_{Q+1}$, the heat kernel on~$G_Q$ is the push-forward of the heat
kernel on~$G_{Q+1}$, and for $0\leq i\leq Q$ the vector fields~$(X_i)$
on~$G_Q$ and~$G_{Q+1}$ respectively match up under the quotient map.
Consequently our estimate on $G_{Q+1}$ implies the same estimate
on~$G_Q$.

With $Q=2l$ one gets
\begin{equation*}
\delta(s,n)=e^{-2ls}\comma \qquad\qquad \delta(s,n)^{1/2}=e^{-ls}
  \period
\end{equation*}
The distance on~$G$ is given by the formula
\begin{equation}\label{eq:dist}
d((s,n),e)=\arc\cosh\bigl(\tfrac{1}{2}(e^{s}+e^{-s}(1+|n|^2)\bigr)
  \period
\end{equation}
The following explicit formula for~$p_t(s,n)$ is taken from~\cite{CGGM:weak}.
\begin{align*}
p_t(x)&=e^{ct}\delta^{1/2}q_t(d(x,e))
\comma
 \\
q_t(r)&=Ce^{-ct}t^{-1/2}D_r^l\exp(-r^2/(4t))
\intertext{where}
D_r&=\frac{-1}{\sinh(r)}\partial_r
  \period
\end{align*}
The reduction to even~$Q$ avoids the use of fractional derivatives in
the above formula.

The first stage of our proof follows along the lines
of~\cite{CGGM:weak}.  Put
\begin{equation*}
\Phi_1(r)=\frac{r}{\sinh(r)}
  \comma\qquad\qquad
\Phi_{j+1}=D_r\Phi_j
\period
\end{equation*}
Easy induction shows that one can write
\begin{gather*}
CD_r^l\exp(-r^2/(4t))=\exp(-r^2/(4t))\sum_{k=1}^lt^{-k}\psi_{l,k}(r)\comma
 \\
\psi_{l,k}=\sum_{|\alpha|=l}c_\alpha\prod_{i=1}^{k}\Phi_{\alpha_i}
\end{gather*}
where the $c_\alpha$ are positive.

One then checks that when $r\rightarrow\infty$
\begin{align*}
\Phi_j(r)&=re^{-jr}+O(e^{-jr})\comma
 \\
\partial_r\Phi_j(r)&=\partial_r(re^{-jr})+O(e^{-jr})
\intertext{so}
\psi_{l,k}(r)&=r^ke^{-lr}+O((r+1)^{k-1}e^{-lr})\comma
 \\
\partial_r\psi_{l,k}(r)&=\partial_r(r^ke^{-lr})+O((r+1)^{k-1}e^{-lr})
\period
\end{align*}
It is known that the $\Phi_j$~are all positive.  So, likewise, all the
$\psi_{l,k}$~are positive.  Now the formula for the heat kernel reads
\begin{equation}\label{eq:pt}
p_t=\sum_{k=1}^{l}t^{-(2k+1)/2}\exp(-d^2/(4t))\delta^{1/2}\psi_{l,k}(d)
\period
\end{equation}
Hence
\begin{multline}\label{eq:Xipt}
X_ip_t=t^{-3/2}\exp(-d^2/(4t))X_i(\delta^{1/2}\psi_{l,1}(d))
 \\
+(X_id/2)t^{-5/2}d\exp(-d^2/(4t))\delta^{1/2}\psi_{l,1}(d)
 \\
+X_i\left(\sum_{k=2}^{l}t^{-(2k+1)/2}\exp(-d^2/(4t))
\delta^{1/2}\psi_{l,k}(d)\right)
\period
\end{multline}
We will deal with these three terms separately.  The first term (which
we will deal with last) is the really delicate one.  To bound the second
term, we use the inequality $|X_id|\leq1$:
\begin{multline*}
|(X_id/2)t^{-5/2}d\exp(-d^2/(4t))\delta^{1/2}\psi_{l,1}(d)|
 \\
\leq Ct^{-2}(d^2/(4t))^{1/2}\exp(-d^2/(4t))\delta^{1/2}\psi_{l,1}(d)
 \\
\leq C't^{-2}\exp(-d^2/(8t))\delta^{1/2}\psi_{l,1}(d)
 \\
\leq C''t^{-1/2}p_{2t}
  \period
\end{multline*}
Now use the fact that $\norm{p_{2t}}_{L^1}=1$.

Although the third term of~\eqref{eq:Xipt} is given by a complicated
formula, it is really of lower order (in~$t$) than the others, and can
be bounded quite directly.  Consider the term for some $k\geq 2$.
\begin{multline*}
|X_i\left(t^{-(2k+1)/2}\exp(-d^2/(4t))\delta^{1/2}\psi_{l,k}(d)\right)|
 \\
=|t^{-(2k+1)/2}\big((X_i\exp(-d^2/(4t)))\delta^{1/2}\psi_{l,k}(d)
 \\
+\exp(-d^2/(4t))(X_i\delta^{1/2})\psi_{l,k}(d)
 \\
+\exp(-d^2/(4t))\delta^{1/2}(X_i\psi_{l,k}(d)\big)|
 \\
=|t^{-(2k+3)/2}(X_i d/2)d\exp(-d^2/(4t))\delta^{1/2}\psi_{l,k}(d)
 \\
+t^{-(2k+1)/2}\big(\exp(-d^2/(4t))(X_i\delta(e))\delta^{1/2}\psi_{l,k}(d)
 \\
+\exp(-d^2/(4t))\delta^{1/2}(X_id)\partial_r\psi_{l,k}(d)\big)|
 \\
\leq Ct^{-(2k+3)/2}d\exp(-d^2/(4t))\delta^{1/2}(d+1)^ke^{-ld}
 \\
+Ct^{-(2k+1)/2}\exp(-d^2/(4t))\delta^{1/2}(d+1)^ke^{-ld}
 \\
\leq C't^{-2}(1+d^kt^{-k/2}+d^{k-1}t^{-(k-1)/2})
    \exp(-d^2/(4t))\delta^{1/2}(d+1)e^{-ld}
 \\
\leq C''t^{-2}\exp(-d^2/(8t))\delta^{1/2}(d+1)e^{-ld}
\leq C'''t^{-1/2}p_{2t}
\period
\end{multline*}
At the next to the last line, we use $k\geq 2$ to get~$t^{-2}$.

For the first term of~\eqref{eq:Xipt}, where $k=1$, we must give a more
detailed argument.  In that term occurs the factor
$X_i(\delta^{1/2}\psi_{l,1}(d))$ where $\delta^{1/2}=\exp(-ls)$ and
$\psi_{l,1}(d)\approx cd\exp(-ld)$.  Except for a relatively small piece
of~$G$, the two exponentials, $\exp(-ls)$ and $\exp(-ld)$, almost
cancel one another out, and so the
derivative~$X_i(\delta^{1/2}\psi_{l,1}(d))$ is very much smaller than one
would naively expect.

A comparison with the analogous calculation on a tree is striking.
\begin{alignat*}{3}
{}&\delta^{1/2}\exp(-d) &&\qquad\longleftrightarrow\qquad &&K(x,y)\comma\\
{}&\delta^{1/2} && \qquad\longleftrightarrow\qquad && q^{(-l(x)-l(y))/2}
\comma\\
{}& \exp(-d) &&\qquad\longleftrightarrow\qquad && q^{-d(x,y)/2}
  \period
\end{alignat*}
In the case of the tree the two exponential factors cancel each other
out perfectly (and consequently $\nabla_x K(x,y)=0$) unless $x$~lies
directly above~$y$.  In the present case, things are fuzzier, but
essentially the same phenomenon controls the situation.

For $T>1$, $\arc\cosh(T)=\log(2T)+(1/4)T^{-2}+\dots$, the expansion
continuing as a convergent power series in $T^{-2}$.  Applying this
to~\eqref{eq:dist}, that is to the exact formula for
$d(s,n)=d((s,n),e)$ gives
\begin{gather*}
d(s,n)=\log(e^{s}+e^{-s}(1+|n|^2))+O((e^{s}+e^{-s}(1+|n|^2))^{-2})\comma
  \\
\partial_s d(s,n)=\partial_s \log(e^{s}+e^{-s}(1+|n|^2)) + 
  O((e^{s}+e^{-s}(1+|n|^2))^{-2})\comma
  \\
e^{s}\partial_{n_i} d(s,n)= 
e^{s}\partial_{n_i}\log(e^{s}+e^{-s}(1+|n|^2)) 
+O((e^{s}+e^{-s}(1+|n|^2))^{-2})
  \period
\end{gather*}
Next, since $\delta^{1/2}(s,n)=e^{-ls}$, since
$\psi_{l,1}(r)=cre^{-lr}+O(e^{-lr})$, and since
$\partial_r\psi_{l,1}(r)=-clre^{-lr}+O(e^{-lr})$:
\begin{align*}
(\delta^{1/2}\psi_{l,1})(s,n)&=cd(s,n)(e^{2s}+1+|n|^2)^{-l}+
O(\delta^{1/2}e^{-ld})\comma
  \\
\partial_s (\delta^{1/2}\psi_{l,1})(s,n)&= 
cd\partial_s(e^{2s}+1+|n|^2)^{-l}+O(\delta^{1/2}e^{-ld})
  \\
&=cd\frac{-2le^{2s}}{(e^{2s}+1+|n|^2)^{l+1}} + O(\delta^{1/2}e^{-ld})\comma
\intertext{and}
e^{s}\partial_{n_i} (\delta^{1/2}\psi_{l,1})(s,n)&=
cd\partial_{n_i}(e^{2s}+1+|n|^2)^{-l}+O(\delta^{1/2}e^{-ld})
  \\
&=cd\frac{-2le^{s}n_i}{(e^{2s}+1+|n|^2)^{l+1}}+ O(\delta^{1/2}e^{-ld})
  \period
\end{align*}
Now
\begin{multline*}
\int |\partial_sp_t|(x)\exp(\eps t^{-1/2}d(x))\,dx
 \\
%\leq\int |t^{-3/2}\exp(-d^2/(4t))\partial_s((\delta^{1/2})\psi_{l,1}(d))|
\leq C\int |t^{-3/2}\exp(-d^2/(4t))d\partial_s((e^{2s}+1+|n|^2)^{-l})|
\exp(\eps t^{-1/2}d(x))\,dx
 \\
+Ct^{-1/2}\int p_{2t}\exp(\eps t^{-1/2}d(x))\,dx
 \\
+t^{-3/2}\int \exp(-d^2/(4t))O(\delta^{1/2}e^{-ld})
\exp(\eps t^{-1/2}d(x))\,dx
 \\
=C(I_1+I_2)+I_3
\period
\end{multline*}
Similarly
\begin{equation*}
\int |e^{s}\partial_{n_i}p_t|(x)\exp(\eps t^{-1/2}d(x))\,dx\leq
C(I_4+I_2)+I_3
\end{equation*}
where
\begin{equation*}
I_4=\int |t^{-3/2}\exp(-d^2/(4t))de^{s}
\partial_{n_i}(%(\delta^{1/2})\psi_{l,1}(d))|
(e^{2s}+1+|n|^2)^{-l})|
\exp(\eps t^{-1/2}d(x))\,dx
  \period
\end{equation*}
So to finish the proof we need to estimate $I_i$, $i=1,2,3,4$. 
We can absorb $\exp(\eps t^{-1/2}d(x))$ into the Gaussian factor, so
\begin{equation*}
I_2\leq Ct^{-1/2}\int p_{3t}=Ct^{-1/2}
\period
\end{equation*}
We can compare $I_3$ with a linear combination of the $p_t$, using the 
bound
\begin{equation*}
O(\delta^{1/2}e^{-ld})\leq C2^{2k}p_{2^{2k}}
  \qquad\qquad\text{for $2^k\leq d(x)<2^{k+1}$.}
\end{equation*}
This follows from~\eqref{eq:pt}, the
formula for~$p_t$, recalling that all the terms there are positive.
Hence
\begin{multline*}
t^{-3/2}\int\exp(-d^2/(4t))O(\delta^{1/2}e^{-ld})\exp(\eps t^{-1/2}d(x))\,dx
 \\
=t^{-3/2}\int_{d(x)\geq t^{1/2}}+t^{-3/2}\int_{d(x)<t^{1/2}}
 \\
\leq Ct^{-1/2}\int p_{2t}
+t^{-3/2}\int_{d(x)<t^{1/2}}O(\delta^{1/2}e^{-ld})
 \\
\begin{aligned}
\leq Ct^{-1/2}&+t^{-3/2}\int_{d(x)<1}O(\delta^{1/2}e^{-ld})
 \\
 &+t^{-3/2}\sum_{k\geq 0,2^k<t^{1/2}}
    \int_{2^k\leq d(x)<2^{k+1}}O(\delta^{1/2}e^{-ld})
\end{aligned}
 \\
\leq C't^{-1/2}+\sum_{k\geq 0,2^k<t^{1/2}}C''t^{-3/2}2^{2k}
\leq C't^{-1/2} +C'''t^{-1/2}
  \period
\end{multline*}
To estimate $I_1$ note that 
\begin{equation*}
\int_{\RR^{2l}} \frac{2le^{2s}}{(e^{2s}+1+|n|^2)^{l+1}} \,dn 
=\int_{\RR^{2l}} \frac{2l}{(1+e^{-2s}+|n|^2)^{l+1}} \,dn 
\leq C
\end{equation*}
with constant $C$ independent of $s$. Hence
\begin{multline*}
I_1=\int |t^{-3/2}\exp(-d^2/(4t))d\partial_s((e^{2s}+1+|n|^2)^{-l})|
\exp(\eps t^{-1/2}d(x))\,dx
 \\
\leq Ct^{-1}\int |\exp(-d^2/(8t))\partial_s((e^{2s}+1+|n|^2)^{-l})|\,dx
 \\
\leq Ct^{-1}\int \exp(-s^2/(8t))
\int_{\RR^{2l}} \frac{2le^{2s}}{(e^{2s}+1+|n|^2)^{l+1}} \,dn \,ds
 \\
\leq  C't^{-1}\int \exp(-s^2/(8t))\,ds = C''t^{-1/2}
  \period
\end{multline*}
The argument for $I_4$ is similar, and that ends the proof.
\end{proof}

The key estimate~\ref{gradi} has now been proved for the case
of~$G=\RR\ltimes\RR^Q$, as needed for the proof of~\ref{multan}.  We
will state our next two results in greater generality, using that key
estimate as one of the hypotheses.

We recall the general set-up.  Let $G$~be a Lie group.  On~$G$ use
left-invariant Haar measure as the basic measure.  Work always with
right-invariant vector fields and differential operators.  Assume that
on~$G$ there are given vector fields~$X_i$ and that the distance
$d(\cdot,\cdot)$ on~$G$ is the distance adapted to those vector
fields.  Assume also that there is a given self-adjoint
Laplacian~$L\geq 0$ on~$G$, and that its heat kernel is~$p_t(\cdot)$.

\begin{lem} \label{dife} Let $G$, $X_i$, $d$, $L$, and $p_t$ be as
above.  If, as in~\ref{gradi}, we have $\norm{X_i p_t}_{L^1}\leq
Ct^{-1/2}$ for each~$i$, then there is $C'$ such that
\begin{equation*}
\|p_t*(\delta_x-\delta_y)\|_{L^{1}}\leq C't^{-1/2}d(x,y)\period
\end{equation*}
%where $C$ is independent of $t$.
\end{lem}

\begin{proof} First, we need an auxiliary formula. 
Let $\gamma:[0,1]\mapsto G$ be a smooth curve. Fix $s$.
Assume that $\gamma'(s)=Y(\gamma(s))$, where $Y$ is 
a right-invariant vector field. We have
\begin{equation*}
\partial_u(p_t*\delta_{\gamma(s+u)})|_{u=0}=
\partial_u(p_t*\delta_{\exp(uY)}*\delta_{\gamma(s)})|_{u=0}
\end{equation*}
so, applying the $*$-operation and using the fact that $p_t^*=p_t$,
\begin{multline*}
\|\partial_u(p_t*\delta_{\gamma(s+u)})|_{u=0}\|_{L^1}=
\|\partial_u(\delta_{(\gamma(s))^{-1}}*\delta_{\exp(-uY)}*p_t)|_{u=0}
\|_{L^1}
% \\
=\|Yp_t\|_{L^1}
\period
\end{multline*}
If $\gamma'(s)=\sum_i a_i(s)X_i$, then since $s$ was arbitrary,
\begin{equation*}
\|\partial_s(p_t*\delta_{\gamma(s)})\|_{L^1}
\leq \sum_i |a_i(s)|\,\|X_ip_t\|_{L^1}
\period
\end{equation*}
Now, assume that $\gamma$ joins
$x$ and $y$.  Then
%, since $s$ was arbitrary,
\begin{multline*}
\|p_t*(\delta_x-\delta_y)\|_{L^{1}}
 \\
\leq \int_0^1 \|\partial_s(p_t*\delta_{\gamma(s)})\|_{L^{1}}\,ds
\leq \int_0^1 \sum_{i} |a_i(s)|\|X_ip_t\|_{L^{1}}\,ds
 \\
\leq Ct^{-1/2}\biggl(\int_0^1 \sum_i |a_i(s)|^2\,ds\biggr)^{1/2}
  \period
\end{multline*}
Since $d(x,y)=\inf_{\gamma}(\int_0^1 \sum_i |a_i(s)|^2 \,ds)^{1/2}$
we get the claim. 
\end{proof}


\begin{theo}\label{riesz} Let $G$, $X_i$, $d$, $L$, and $p_t$ be as
above.  Suppose that
\begin{itemize}
\item $G$~satisfies the Calder\'on--Zygmund condition,
\item the conlusion of~\ref{gradi} holds.
\end{itemize}
Then the Riesz transforms $X_iL^{-1/2}$ are of weak type~$(1,1)$ and
bounded on $L^p$, $1<p\leq 2$.
\end{theo}

\begin{proof} We are going to use \ref{singi}. We write
\begin{equation*}
\Gamma(\tfrac{1}{2})X_iL^{-1/2}=\int_0^{\infty} t^{-1/2}X_ip_t \,dt=
\sum_{n}\int_{2^n}^{2^{n+1}}t^{-1/2}X_ip_t \,dt = \sum_{n}K_n
\period
\end{equation*}

For our next calculation we use the following natural convention.  Suppose
$K$~is the operator given by the kernel $K(x,y)$, namely $(Kf)(x)=\int
K(x,y)f(y)\,dy$. Then for any measure~$\mu$ we define 
\begin{equation*}
(K\mu)(x)=\int K(x,y)\,d\mu(y).
\end{equation*} 
%Since $(p_t*f)(x)=\int p_t(xy)f(y^{-1})\,dy=\int
%p_t(xy^{-1})\delta(y)f(y)\,dy$, the kernel associated to
%left-convolution by~$p_t$ is $p_t(x,y)=p_t(xy^{-1})\delta(y)$.
%Differentiating shows that the kernel associated to $X_ip_t$ is
%$(X_ip_t)(x,y)=(X_ip_t)(xy^{-1})\delta(y)$. 
%Now, putting $a=1$ and $c=2^{-1/2}$
%\begin{multline*}
%\int |K_n(x,y)(1+c^{-n}d(x,y))|\,dx 
%\leq C\int |K_n(x,y)\exp(\eps 2^{-(n+1)/2}d(x,y))|\,dx \,dt
% \\
%\leq C\int_{2^n}^{2^{n+1}} 
%\int |t^{-1/2}(X_ip_t)(xy^{-1})\delta(y)\exp(\eps t^{-1/2}d(xy^{-1})|\,dx \,dt
% \\
%\int |t^{-1/2}(X_ip_t)(x)\exp(\eps t^{-1/2}d(x)|\,dx \,dt
% \\
%\leq C'\int _{2^n}^{2^{n+1}}t^{-1}\,dt\leq C'
%\end{multline*}
Note, that $((f\cdot g)*\delta_y)(x)=(f*\delta_y)(x)g(xy^{-1})$. 
Now, putting $a=1$ and $c=2^{-1/2}$
\begin{multline*}
\int |K_n(x,y)(1+c^{-n}d(x,y))|\,dx
\\
\leq\int_{2^n}^{2^{n+1}}
\int |(t^{-1/2}(X_ip_t)*\delta_y)(x)(1+c^{-n}d(xy^{-1}))|\,dx
\\
=\int_{2^n}^{2^{n+1}}
\|(t^{-1/2}(X_ip_t)(1+c^{-n}d))*\delta_y\|_{L^1}\,dt
\\
\leq C\int_{2^n}^{2^{n+1}}
\|t^{-1/2}(X_ip_t)\exp(\eps t^{-1/2}d)\|_{L^1}\,dt
 \\
\leq C'\int _{2^n}^{2^{n+1}}t^{-1}\,dt\leq C'
\end{multline*}
so the first assumption about $K_n$ in \ref{singi} holds. 

\begin{multline*}
\int |K_n(x,y)-K_n(x,z)|\,dx=\|K_n(\delta_y-\delta_z)\|_{L^{1}}
 \\
\leq \int_{2^n}^{2^{n+1}} 
\| t^{-1/2}(X_ip_t)(\delta_y-\delta_z)\|_{L^{1}}\,dt
 \\
\leq  \int_{2^n}^{2^{n+1}} t^{-1/2}\|X_ip_{t/2}\|_{L^{1}}\,
  \|p_{t/2}*(\delta_y-\delta_z)\|_{L^{1}}\,dt
 \\
\leq C \int_{2^n}^{2^{n+1}} t^{-3/2}d(y,z)\,dt 
\leq C'2^{-n/2}d(y,z)= C' c^nd(y,z)
\end{multline*}
so the second assumption of~\ref{singi} is also satisfied, ending the
proof.
\end{proof}

\begin{proof}[Proof of \ref{multan}] The result will follow 
from \ref{singi}.  Indeed, by \ref{stim}, $G$~has the
Calder\'on--Zygmund property. Fix $\phi\in C^{\infty}_c(\RR_+)$ such
that $\supp \phi \subset [1/2,2]$ and $\sum_n \phi(2^nx)=1$ for all
$x>0$. Put $F_n(x)=F(2^{-n}x)\phi$ and $G_n(x)=F_n(x)\exp(x)$.  We
write
\begin{equation*}
F(L)=\sum F_n(2^nL)=\sum G_n(2^nL)\exp(-2^{n}L)
\end{equation*}
Now the first assumption of~\ref{singi} follow from~\ref{keri}
(applied directly to $F_n$) and the second from~\ref{keri} (applied
to~$G_n$) and~\ref{dife}, which ends the proof.
\end{proof}

This proof of the spectral multiplier part of~\ref{multan} is also
applicable to any~$G$, $X_i$, $d$, $L$, and $p_t$ as above such that
\begin{itemize}
\item $G$~satisfies the Calder\'on--Zygmund condition,
\item the conclusion of~\ref{keri} holds,
\item the conclusion of~\ref{dife} holds.
\end{itemize}

\section{Final remarks}

The method used to obtain the Calder\'on--Zygmund decomposition on the
tree is inspired by \cite{Z:ts} (p. 309, Lemma XVII.3.2) and uses the
same ideas as \cite{GiS:max}. Working on trees made ideas simpler, and 
made clear which maximal function is relevant for singular integrals 
(on Lie groups there are many natural maximal functions, some bounded, 
some unbounded \cite{GGHM:max},\cite{GGM:assy}). 
We use a somewhat different method on
Lie groups, which allows us to handle the case where the roots are of
both signs (for instance, unimodular groups).  Both proofs are related
to the construction of F\"olner sequences.

For simplicity, we restricted ourselves to rank $1$ case. However, 
our arguments works the same in a product setting.

The first author can prove that if a (locally compact) group $G$ with
left-invariant Haar measure and right-invariant distance satisfies the
Calder\'on--Zygmund property, then $G$ is amenable.

In~\cite{S:est} Sj\"ogren proves that $X_1L^{-1/2}$ is of weak
type~$(1,1)$ in the $Q=1$~case, $G=\RR\ltimes\RR$.  The result in our
Theorem~\ref{multan} is stronger than that because it deals also
with~$X_0$.  In~\cite{Wn:rig} Wängeforos extends Sj\"ogren's results
to $AN$ groups associated to arbitrary rank~$1$ symmetric spaces.
In~\cite{GS:haar} Gaudry and Sj\"ogren prove, again for
$G=\RR\ltimes\RR$, that $L^{-1/2}X_1$ is of weak type~$(1,1)$.  That
operator is $-(X_1L^{-1/2})^*$, so their result gives $p>2$ estimates
for $X_1L^{-1/2}$.  Although Gaudry and Sj\"ogren do not mention
trees explicitly, Theorem~3 in~\cite{GS:haar} does have a strong
tree-like flavor.

\begin{thebibliography}{00}

\bibitem{A:st} {F. Astengo, Multipliers for a distinguished Laplacean
on solvable extensions of H-type groups,
Monatsh. Math. 120 (1995), 179--188.}


\bibitem{CM:sp} {M. Christ, D. M\"uller, On $L^{p}$ spectral
multipliers
 for a solvable Lie group, Geom. Funct. Anal. 6 (1996), 860--876.}

\bibitem{CS:mul}
 J. L. Clerc, E. M. Stein, 
\newblock $L\sp{p}$-multipliers for noncompact symmetric spaces. 
\newblock {\em Proc. Nat. Acad. Sci. U.S.A.} 71 (1974), 3911--3912. 


\bibitem{C:m} {M. Cowling, Harmonic analysis on semigroups, Ann. of
Math. 117 (1983), 267--283. }

\bibitem{CGGM:weak}
{M. Cowling, G. Gaudry, S. Giulini, G. Mauceri,}
\newblock Weak type $(1,1)$ estimates for heat kernel maximal functions on Lie
  groups.
\newblock {\em Trans. Amer. Math. Soc.} 323, (1991), 637--649.

\bibitem{CGHM:m} {M. Cowling, S. Giulini, A. Hulanicki, G. Mauceri,
Spectral
multipliers for a distinguished Laplacian on certain groups of
exponential growth, {\it Studia Math.} 111 (1994), 103--121.}

\bibitem{DHZ:est}
E. Damek, A. Hulanicki, J. Zienkiewicz,
\newblock Estimates for the Poisson kernels and their derivatives on
rank one $NA$ groups. 
\newblock {\em Studia Math.} 126 (1997), no. 2, 115--148. 

\bibitem{FTP:haf} 
A. Figa-Talamanca, M. Picardello, 
Harmonic analysis on free groups,
Dekker, New York 1983. 


\bibitem{GGHM:max}
G. Gaudry, S. Giulini, A. Hulanicki, A. M. Mantero,
\newblock Hardy-Littlewood maximal functions on some solvable Lie
groups. 
\newblock {\em J. Austral. Math. Soc. Ser. A} 45 (1988), no. 1, 78--82. 

\bibitem{GGM:assy}
{G. Gaudry, S. Giulini, and A. M. Mantero,}
\newblock Asymmetry of maximal functions on the affine group of the line.
\newblock {\em Tôhoku Math. J.} 42 (1990), 195--203.

\bibitem{GQS:sing}
G. Gaudry, T. Qian,  P. Sjögren, 
\newblock Singular integrals associated to the Laplacian on the affine group $ax+b$. 
\newblock {\em Ark. Mat.} 30 (1992), no. 2, 259--281. 

\bibitem{GS:sing}
G. Gaudry, P. Sjögren, 
\newblock Singular integrals on Iwasawa $NA$ groups of rank $1$. 
\newblock {\em J. Reine Angew. Math.} 479 (1996), 39--66. 

\bibitem{GS:sinc}
G. Gaudry, P. Sjögren, 
\newblock Singular integrals on the complex affine group. 
\newblock {\em Colloq. Math.} 75 (1998), no. 1, 133--148. 

\bibitem{GS:haar}
G. Gaudry, P. Sjögren, 
\newblock Haar-like expansions and boundedness of a Riesz operator on a solvable Lie group. 
\newblock {\em Math. Z.} 232 (1999), no. 2, 241--256. 

\bibitem{GM:disti}
{S. Giulini, G. Mauceri,}
\newblock Analysis of a distinguished Laplacian on solvable Lie groups.
\newblock {\em Math. Nachr.} 163 (1993), 151--162.

\bibitem{GMM:nonc} 
{S. Giulini,  G. Mauceri, S. Meda,}
\newblock $L\sp p$ multipliers on noncompact symmetric spaces.
\newblock {\em J. Reine Angew. Math.} 482, (1997), 151--175.

\bibitem{GiS:max}
S. Giulini, P. Sjögren, 
\newblock A note on maximal functions on a solvable Lie group. 
\newblock {\em Arch. Math. (Basel)} 55 (1990), no. 2, 156--160.

\bibitem{H:est} {W. Hebisch, Estimate on the semigroups generated
by left invariant operators on Lie groups,
J. reine angew. Math. 423 (1992), 1--45.}

\bibitem{H:s} {W. Hebisch, 
The subalgebra of \hbox{$L^{1}(AN)$} generated by
the laplacean, Proc. AMS 117 (1993), 547--549.}

\bibitem{H:bo} {W. Hebisch, Boundedness of $L^{1}$ spectral multipliers for an
exponential solvable Lie group, {\it Coll. Math. } 73 (1997), 155--164.}

\bibitem{H:me} {W. Hebisch, Spectral multipliers on exponential growth solvable
Lie groups, {\it Math. Z. } 229 (1998), 435--441.}

\bibitem{H:ed} {W. Hebisch,Analysis of Laplacians on solvable
Lie groups, Notes for ICMS conference Edinburg 1998.}

\bibitem{LoM:rta} {N, Lohoué, S. Mustapha, Sur les transformées de Riesz 
sur les groupes de Lie moyennables et sur certains espaces homogènes, 
Canad. J. Math. 50 (1998), 1090--1104.} 

\bibitem{LM:hol} {J. Ludwig, D. M\"uller, Sub-Laplacians of
holomorphic $L^p$-type on rank one $AN$-groups
and related solvable groups, J. of Funct. Anal. 170 (2000), 366-427.}

\bibitem{M:uh} {S. Mustapha, Multiplicateurs spectraux sur certains
groupes non-unimodulaires, Harmonic Analysis and Number Theory,
CMS Conf. Proceedings, Vol 21, 1997.}

\bibitem{M:u} {S. Mustapha, Multiplicateurs de Mikhlin pour une
classe particuli\`ere de groupes non-unimodulaires,
Ann. Inst. Fourier 48 (1998), 957--966.}

\bibitem{S:est}
P. Sjögren,
\newblock An estimate for a first-order Riesz operator on the affine group. 
\newblock{\em  Trans. Amer. Math. Soc.} 351 (1999), no. 8, 3301--3314. 

\bibitem{S:weak}
J.-O. Strömberg,
\newblock Weak type $L\sp{1}$ estimates for maximal functions on noncompact symmetric spaces. 
\newblock {\em Ann. of Math.} (2) 114 (1981), no. 1, 115--126. 


\bibitem{S:t} {E. M. Stein, Topics in harmonic analysis related to
the
    Littlewood-Paley theory, Ann. of Math. Stud. 63, Princeton
Univ.
    Press, Princeton 1970.}


\bibitem{T:e} {M. Taylor, $L^{p}$ -Estimate on functions of the
Laplace
operator, {\it Duke Math. J.} 58 (1989), 773-793. }

\bibitem{Wn:rig} {M. Wängeforos, An estimate for some first-order 
Riesz operators on Iwasawa NA groups of rank $1$, preprint 1997}

\bibitem{Z:ts} {A. Zygmund, Trigonomeric series, Cambridge University 
Press 1968.}

\end{thebibliography}

\end{document}