\magnification=1200 \input amssym.def \long\def\ppp #1. #2\par{\medbreak \noindent{ #1.\enspace}{\sl#2}\par \ifdim\lastskip<\medskipamount \removelastskip\penalty55\medskip\fi} \baselineskip=18pt \def \rank {\hbox {rank} } \def \supp {\hbox {supp} } \def \nl {\par} \newcount\pno \pno=0 \newcount\sno \sno=1 \font\Bbb=msbm10 %\input /za/hebisch/my.mor \def \Cal { \Bbb } \long\def \p #1 #2 {\advpnr {\edef \pnrp {\hbox{ \pnr } } \global \let #1=\pnrp } \ppp {\pnr. {\bf Lemma}}. {#2} \par} \def \t #1 #2 {\advpnr {\edef \pnrp {\hbox{ \pnr } } \global \let #1=\pnrp } \ppp {\pnr . {\bf Theorem}}. {#2} \par} \def \nr #1 {\advpnr { \edef \pnrp {\hbox{ \pnr } } \global \let #1=\pnrp } \pnr} \def \advpnr {\global\advance\pno by 1} \def \pnr {(\the \sno.\the \pno)} %***************************** \newcount\refno \refno=1 \def \rf #1 #2 {\setbox3=\box2 \global\edef #1{\the \refno} \setbox2=\vbox{\unvbox3 \vskip 0pt plus2pt \hbox { \hbox to 2em{[\the \refno \global\advance\refno by1]\hfil} \vtop {\advance\hsize by-5em \noindent \strut #2 \hfil \strut } } } } \global \def \diam {\mathop{\hbox{ diam } }} \def \supp {\mathop{\hbox{ supp }} } \edef \int {\int\limits} \long\def\nic#1{} \rf {\A} {G. Alexopoulos, Fonctions harmoniques born\'{e}es sur les groupes r\'{e}solubles. C. R. Acad. Sci. Paris, t. 305, s\'{e}rie I, 1987, p.777-779.} \rf {\DV} {M. D. Donsker, S. R. S. Varadhan, On the number of distinct sites visited by a random walk, Comm. Pure Appl. Math 32 (1979), 721--747.} \rf {\Hht} {W. Hebisch, On the heat kernel, {\it Math. Z. } 210 (1992), 593-605.} \rf {\HSf} {W. Hebisch, L. Saloff-Coste, Gaussian estimates for Markov chains and random walks on groups, {\it Annals of Prob}. 21 (1993), 673--709. } %\rf {\Vl} { N. Th. Varopoulos, Small time Gaussian estimates %for the heat kernel: part2, J. Funct. %Anal. 83, 3--41 (1990).} \rf {\PS} {Ch. Pittet, L. Saloff-Coste, Amenable groups. isoperimetric profiles and random walks, preprint.} \rf {\Vda} { N. Th. Varopoulos, Diffusion on Lie groups (I), Can. J. Math. 46 (1994), 438-448.} \rf {\Vdb} { N. Th. Varopoulos, Diffusion on Lie groups (II), Can. J. Math. 46 (1994), 1073-1093.} \rf {\Vh} { N. Th. Varopoulos, The heat kernel on Lie groups, Rev. Math. Ib. 12(1996), 141-186. } {\bf On random walks on discrete solvable groups} by Waldemar Hebisch {\bf Introduction} This paper is concerned with the decay of $p_n(e)$ for symmetric random walk on discrete solvable group $G$ of exponential growth. Previous results in [\A], [\Hht], [\HSf], [\Vda], [\Vdb], [\Vh] shows that on Lie groups one has polynomial decay or decay of type $\exp(-n^{1/3})$ and that this remains true for polycyclic groups. Morover there is rather general estimate from above of the similar type. So one may conjecture that such a type of decay is correct for all solvable groups of exponential growth. We are going to show that in fact on discrete solvable groups much faster decay is possible. One may also notice that our groups have no finite presentation. As only groups with finite presentations can occur in geometric problems it would be nice to handle those, however we leave this problem open. {\bf Note} Our results seem to be a particular case of results from [\PS]. While [\PS] covers more topics and the technical details are different the idea for getting both lower and upper bound is the same. Morover, in [\PS] it is pointed out that one may modify the example to get finitely presented solvable groups with ''fast'' decay of $p_n(e)$. {\bf Results} Let $G_d$ be the semidirect product of ${\Bbb Z}^{d}$ and ${\Bbb Z}^{{\Bbb Z}^d}$ and $p_n$ be the simple random walk on $G_d$. We will call the ${\Bbb Z}^d$ part $H$. Then an element of $G$ is a pair $(h,f)$ with $h\in H$ and $f$ beeing integer valued function on $H$ taking only finitely many values different from $0$. In the sequel we will denote by $F$ the set of all such $f$. $H$ acts on $F$ %such functions by translations (we define translations by the formula $(T(h)f)(x)=f(xh)$). Multiplication on $G$ is given by the formula $$(h_1,f_1)(h_2,f_2)=(h_1h_2,T(h_2^{-1})f_1+f_2).$$ Let $A_h$ be a subgroup of $G$ consisting of pairs $(0,f)$ with $f(x)=0$ for $x\ne h$. Of course $A_h$ is isomorphic to ${\Bbb Z}$. Note that $T(h)^{-1}A_e=A_h$. We choose $(\delta_k,0)$, $k=1,\dots,d$ and $(0,\delta_0)$ as generators of $G_d$. Then, the probability distribution $p_1$ is given by $$p_1((\pm\delta_k,0))=p_1((0,\pm\delta_0))={1\over 2(d+1)}.$$ As usual, $p_n$ is the $n$-th convolution power of $p_1$. \t {\a} { For every $d$ there exist $C$ and $c>0$ such that for all $n$ $$ c\exp(-Cn^{d/(d+2)}\log n)\leq p_{2n}(e)\leq C\exp(-cn^{d/(d+2)}).$$ There exist $G$ and $p_1$ such that for every $\epsilon>0$ $p_{n}(e)$ decays faster then $\exp(-n^{1-\epsilon})$.} \t {\b} { Let $Z$ and $Y$ be random variables with values in $A_e$ and $H$ respectively. Assume that $Z$ and $Y$ are symmetric, have finite second moment, $P(Z=0)>0$, and that the values of $Z$ ($Y$ resp.) generate $A_e$ ($H$ resp.). Let $Z_j$ and $Y_j$ be independent random variables, $Z_j$ have the same distribution as $Z$ and $Y_j$ have the same distribution as $Y$. Then there is $c>0$ such that $$c\exp(-c^{-1}\log(n)n^{d/d+2}) \leq \sup_{g\in G}P(\prod_{j=1}^{n}(Y_jZ_j)=g)\leq \exp(-cn^{d/d+2}).$$} P. Note that $Y_jZ_j=(Y_j,Z_j)$ and $$ \prod_{j=1}^{n}(Y_j,Z_j)= (\prod_{j=1}^{n}Y_j,\prod_{j=1}^{n}T^{-1}(\prod_{l=j+1}^{n}Y_j)Z_j)$$ $$ \sup_{g\in G}P(\prod_{j=1}^{n}(Y_jZ_j)=g)\leq \sup_{f\in F}P(\prod_{j=1}^{n}T^{-1}(\prod_{l=j+1}^{n}Y_l)Z_j=f).$$ Since $F$ is commutative $$ \prod_{j=1}^{n}T^{-1}(\prod_{l=j+1}^{n}Y_l)Z_j= \prod_{h\in H}T^{-1}(h)\prod_{h=\prod_{l=j+1}^{n}Y_l}Z_j\leqno (1)$$ Since $T^{-1}(h)Z_j$ takes values in $A_h$, the first product above is simply a cartesian produkt (of independent variables). Morover, %$Z_j$ have the same distribution so on each axis we may apply to $Z_j$ the central limit theorem, so $$ P(\prod_{j=1}^{n}T^{-1}(\prod_{l=j+1}^{n}Y_l)Z_j=f)= E(\prod_{h\in H}P(\prod_{j=1}^{n_h}Z_j=f(h)))$$ $$ \leq E( \prod_{h\in H} (1+cn_h)^{-1/2}) \leq E(\exp(-\tilde c|\{h\in H : n_h>0\}|))$$ where $n_h$ is the number of $j$ such that $h=\prod_{l=j+1}^{n}Y_l$. By [\DV] $$ E(\exp(-\tilde c|\{h\in H : n_h>0\}|)) \leq \exp(-c n^{d/(d+2)}).$$ Similarly $$ P(\prod_{j=1}^{n}(Y_j,Z_j)\in H)=P(\prod_{j=1}^{n}T^{-1}(\prod_{l=j+1}^{n}Y_l)Z_j=0)\geq E( \prod_{h\in H} (1+cn_h)^{-1/2})$$ $$ \geq E( \exp(-c_0\log(2+n)|\{h\in H : n_h>0\}|))$$ $$ \geq E( \exp(-c_0|\{h\in H : n_h>0\}|))^{\log(2+n)}$$ $$ \geq c\exp(-c_1 n^{d/(d+2)})^{\log(2+n)}$$ where the last inequality follows from [\DV]. Next, since $Y$ is symmetric $E(Y)=0$ and $E(|\prod_{j=1}^{n}Y_j|^2)\leq Cn$. Put $$\phi(x)=c\exp(-c_1 x^{d/(d+2)})^{\log(2+x)}$$ nad let $r$ be the smallest such that $Cnr^{-2}\leq 1/2\phi(n)$. Then $r\leq {C_3\over \phi(n)}$ and $$P(|\prod_{j=1}^{n}Y_j|>r)\leq 1/2\phi(n)$$ so with probability at least $1/2\phi(n)$ the product $\prod_{j=1}^{n}(Y_j,Z_j)$ takes a value in the ball centered at $0$ and of radius $r$ in $H$. This ball has $C_4r^{d}$ elements, so the maximal probability is at least $$1/2\phi(n)/(C_4r^{d})\geq C_5\phi(n)^{d+1}$$ which differs from $\phi$ only because of constants. P. of \a : Let $X$ be a random variable with distributon $p_1$ and let $Y$ nad $Z$ be (independent) random variables such that $$P(Z=(0,\pm\delta_0))=1/2 \qquad P(Y=(\pm\delta_k,0)=1/2d\quad k=1,\dots,d.$$ We consider $X$ as a mixture of random variables $Y$ and $Z$, that is $X$ equals $Y$ with probability $d/(d+1)$, otherwise $X$ equals $Z$. Next, let $X_i$ (or $Y_i$ or $Z_i$) be independent random variables with the same distribution as $X$ (resp. $Y$ or $Z$). Consequently, we treat $\prod_{i=1}^nX_i$ as a product of $Y_i$ and $Z_i$ (with random choice between $Y_i$ and $Z_i$). We group $Y$-s and $Z$-s into series. More precisely, consider sequence of independent (also from $Y$-s and $Z$-s) random variables $\omega$ such that $P(\omega(i)=0)=d/(d+1)$ and $P(\omega(i)=1)=1/(d+1)$. We have $X_i=Y_i$ iff $\omega(i)=0$ (and $X_i=Z_i$ iff $\omega(i)=1$). Let $A=\{\omega(1)=0\}$ and $B=\{\omega(1)=1\}$. Let $m_i$ and $l_i$ be defined inductively: $m_0=l_0=1$, $m_{i+1}= \min\{k:k>m_i,\omega(k-1)=0,\omega(k)=1\}$, $l_{i+1}= \min\{k:k>l_i,\omega(k-1)=1,\omega(k)=0\}$. The differences $m_i-m_{i-1}$ are independent, and except for $i=1$ have a common distribution (which is convolution of two geometric distrbutions). There exists $c_1>0$ such that $P(l_{[c_1n]}>n)<\exp(-c_1n)$. On $A$ put $\tilde Y_i=\prod_{k=l_{i-1}}^{m_i-1}Y_k$ and $\tilde Z_i=\prod_{k=m_i}^{l_i-1}Z_k$, on $B$ put $\tilde Y_i=\prod_{k=l_i}^{m_i-1}Y_k$ and $\tilde Z_i=\prod_{k=m_i}^{l_{i+1}-1}$. Let $A_n=A\cap\{l_{[c_1n]}\leq n\}$. Then, on $A_n$ $$ \prod_{i=1}^{n}X_i=\prod_{i=1}^{[c_1n]}(\tilde Y_i\tilde Z_i) \prod_{i=l_{[c_1n]}}^{n}X_i.$$ Let us note that $\tilde Y_i$ and $\tilde Z_i$ are independent, and $\tilde Y_i$ have common distribution with values in $H$ and that $\tilde Z_i$ have common distribution with values in $A_e$ and that $P(\tilde Z_1=0)>0$. Next $$\sup_{g\in G} P((\prod_{i=1}^{n}X_i=g)\cap A)\leq P(l_{[c_1n]}>n)+\sup_{g\in G} P(\prod_{i=1}^{[c_1n]}(\tilde Y_i\tilde Z_i)=g)$$ %$$\leq \sum_{i=0}^{n}\exp(-cj^{d/(d+2)})P(j_n=i|A) \leq %P(j_n=c_1n)+\exp(-c_2n^{d/(d+2)}) $$\leq \exp(-c_3n)+\exp(-c_2n^{d/(d+2)})$$ where the estimate for the second term follows from \b. Estimate on $B$ is similar, thus giving the upper estimate. To get the lower bound, we first note, that as in \b, it is enough to estimate $$P(\prod_{j=1}^{n}X_j\in H).$$ Morover, we may add to $p_1$ atom in $0$. Indeed, if $q=ap+(1-p)\delta_0$ then $$ q^n=\sum c_{n,k}p^k$$ where $c_{n,k}$ are binomial coefficients. %By the central limit theorem There exists $b>0$ such that for large $n$ $$\sum_{2k1/4.$$ Since $p^{2k}(0)$ decreases and $p^{2k+1}(0)=0$ $$ q^{n}(0)\leq \sum_{k\geq bn}c_{n,2k}p^{2k}(0)+\exp(-bn)\leq$$ $$ p^{2[bn]}(0)+\exp(-bn)$$ so any subexponential lower bound for $q^{n}(0)$ will give corresponding lower bound for $p^{n}(0)$. We put $$ \tilde p_1(x)={2d+2\over 2d+3}p_1+{1\over 2d+3}\delta_{(0,0)}$$ Then $P(Z=(0,\pm\delta_0))=P(Z=(0,0))=1/3$. Next, we restrict our attention to $A$. We are going to lenghten the product to get fixed number of series, and then to apply \b. Since $\prod_{i=1}^{n}X_i$ and $\omega$ seem to be dependent, we consider conditional distribution and then take expectation in $\omega$. %So, we %would like to have %$$ %P((\prod_{i=1}^{n}X_i=(0,0))\cap A | \omega) \geq %P((\prod_{i=1}^{l_{n+1}-1}X_i=(0,0))\cap A | \omega) $$ %but we can get only %$$ %P((\prod_{i=1}^{n}X_i\in H)\cap A | \omega) \geq %P((\prod_{i=1}^{l_{n+1}-1}X_i\in H)\cap A | \omega).$$ As in the proof of \b, we note that the second (in $F$) coordinate of $\prod X_i$ has a (conditional in $\omega$ and $Y_j$, $j=1,\dots$) distribution which is a cartesian product of one dimensional distributions. Each of those one dimensional distributions is a convolution power of distribution of $Z$. Since the distribution $q$ of $Z$ is unimodal (thanks to the added atom at 0), its convolution powers have maximum at $0$ for any $k\geq 0$. Hence $q^{\star k}(0)$ is decreasing in $k$. Consequently $$ P((\prod_{i=1}^{n}X_i\in H)\cap A | \omega,Y_1,Y_2,\dots) \geq P((\prod_{i=1}^{l_{n+1}-1}X_i\in H)\cap A | \omega,Y_1,Y_2,\dots).$$ %Integrating, we get ineqality for unconditional pob Next, with the notation as in the proof of upper bound $$ P((\prod_{i=1}^{n}X_i\in H)\cap A ) \geq P((\prod_{i=1}^{l_{n+1}-1}X_i\in H)\cap A ) = P((\prod_{i=1}^{n}(\tilde Y_i\tilde Z_i)\in H)\cap A )$$ and we end the proof applying \b. To get the last claim of \a we consider $H=G_1$. One easily checks that the number of sites visited by the random walk on $G_1$ is larger then th corresponding number on ${\Bbb Z}^d$, for any $d$, so in the final estimate we can take $d$ as large as we wish. {\bf References} \vskip 0.3cm \unvbox 2 \end