arXiv:1607.00753v1 [math.PR] 4 Jul 2016

MINIMAL GROWTH HARMONIC FUNCTIONS ON LAMPLIGHTER
GROUPS
ITAI BENJAMINI, HUGO DUMINIL-COPIN, GADY KOZMA, AND ARIEL YADIN
Abstract. We study the minimal possible growth of harmonic functions on lamplighters. We find that (Z/2) ≀ Z has no sublinear harmonic functions, (Z/2) ≀ Z2 has
no sublogarithmic harmonic functions, and neither has the repeated wreath product
(· · · (Z/2 ≀ Z2 ) ≀ Z2 ) ≀ · · · ≀ Z2 . These results have implications on attempts to quantify
the Derriennic-Kaimanovich-Vershik theorem.

1. Introduction
The celebrated Derriennic-Kaimanovich-Vershik theorem [6, 11] states that for any
finitely generated group G and any set of generators S, the Cayley graph of G with
respect to S has bounded non-constant harmonic functions if and only if the entropy of
the position of a random walk on the same Cayley graph at time n grows linearly with
n. This result was a landmark in the understanding of the Poisson boundary of a group
i.e. the space of bounded harmonic functions.
The “if” and the “only if” directions of the theorem are quite different in nature. The
first direction states that once the entropy is sublinear the graph is Liouville i.e. does
not admit a non-constant bounded harmonic function (this direction was proved earlier
e.g. one may show that there are no harmonic
[2]). This direction may be quantified,
p
functions growing faster than n/H(Xn ) where H(Xn ) is the entropy of the random
walk. This is a known fact [7, 3] but for completeness we give the proof
p in the appendix.
In this paper we study the question “how tight is the bound n/Hn (X)?” As a
simple example let us take the lamplighter group (Z/2) ≀ Z (precise definitions will be
given later, see §1.3). We show
Theorem 1. The lamplighter group (Z/2) ≀ Z with the standard generators does not
support any non-constant harmonic function h with h(x) = o(|x|) where | · | is the word
metric.
p
Thus on the lamplighter group the
bound
n/Hn (X) is not tight. It is well-known
√
and easy to see that the entropy is n and hence the bound gives only that harmonic
functions growing slower than n1/4 are constant. As Theorem 1 is quite simple but still
instructive, let us sketch its proof.
Proof sketch. Let us use the generators “move or switch” i.e. if we write any element
of (Z/2) ≀ Z as a couple (ω, n) with ω : Z → Z/2 and n ∈ Z then the generators are
{(10 , 0), (~0, 1), (~0, −1)}. Examine two elements g1 , g2 ∈ (Z/2) ≀ Z which differ only in the
configuration at 0, i.e. if gi = (ωi , ni ), then n1 = n2 and ω1 (k) = ω2 (k) for all k 6= 0.
1

2

BENJAMINI, DUMINIL-COPIN, KOZMA, AND YADIN

Let Xni be two lazy random walks (with laziness probability 41 ) starting from gi , and
couple them as follows. Changes to the Z component are done identically so that the Z
components of Xn1 and Xn2 are always identical. Changes to the configuration are also
done identically except when the walkers “are at 0” (i.e. their Z component is 0) and
their configurations are still different. In this case, if one walker switches (i.e. goes in
the (10 , 0) direction) then the other walker stays lazily at its place, and vice versa.
It is now clear that each time both walkers are at 0 they have a probability 21 to
“glue” i.e. to have Xn1 = Xn2 , and when this happens this is preserved forever. Define
Tr to be the first time the walkers are at ±r. Because h(g) is bounded for all time up
to Tr we may use the optional stopping theorem to claim that
h(gi ) = E(h(XTi r )).
Let E be the gluing time. Then we can write
h(g1 ) − h(g2 ) = E(h(XT1r ) − h(XT2r )) =


= E (h(XT1r ) − h(XT2r ))1{E < Tr } +

E (h(XT1r ) − h(XT2r ))1{E ≥ Tr } .

The first term is simply 0 because if the walkers glued before Tr then XT1r = XT2r . The
second term is bounded by
P(E ≥ T ) · 2 max{h(g) : g can be the value of XTr }.

The probability is ≤ C/r from known properties of random walk on Z. On the other
hand, for r > max{|supp ωi |, |ni |} the only g that can be values of XTr have distance
≤ 5r from the identity of (Z/2) ≀ Z and by the sublinearity of h we get h(g) = o(r). We
get that
C
r→∞
h(g1 ) − h(g2 ) = 0 + o(r) −−−→ 0
r
and that h((ω, n)) does not depend on the value of ω(0). Translating we get that it
does not depend on the value of any lamp i.e. on any ω(i). This means that it is a
function of n only, which is harmonic, implying that it is a harmonic function on Z. But
a harmonic function on Z (with the generators ±1) is linear, which can be proved by a
simple induction. Thus, h is constant.

The result is sharp since for the lamplighter there is an obvious linear growth harmonic
function: the Z component. We remark also that, in general, every finitely-generated
group supports a non-constant linear growth harmonic function. See e.g. [12, 15]. It is
also instructive at this point to compare the lamplighter to nilpotent groups. Similarly
to the lamplighter, nilpotent groups do not support any non-constant sublinear growth
harmonic functions (see √e.g. remark 19 below). However nilpotent groups have much
lower entropy: log n vs. n for the lamplighter.
The next result concerns wreath products with Z2 , or more generally any recurrent
group.
Theorem 2. Let L be a finitely generated group and µ a symmetric measure over a
finite set of generators such that L supports no µ-harmonic sublogarithmic non-constant
function. Let G be a recurrent group with respect to a measure ν. Let ν ≀ µ be the “move

MINIMAL HARMONIC FUNCTIONS

3

or switch” (each with probability 21 ) measure on L ≀ G. Then L ≀ G does not support any
ν ≀ µ-harmonic sublogarithmic non-constant function.
In particular, this means that repeated wreath products with Z2 i.e.
(· · · (Z/2 ≀ Z2 ) ≀ Z2 ) ≀ · · · ≀ Z2
|
{z
}
k times

do not support any sublogarithmic non-constant harmonic functions (with respect to
the natural set of generators). As we will see below (Proposition 13 on page 15), this
group has entropy n/ log(k) n. This is another obstacle for quantifying the DerriennicKaimanovich-Vershik theorem. We remark that constructing non-constant harmonic
functions growing logarithmically (which shows that Theorem 2 is sharp) is easy, and
we do it in §2.3.
One may consider a similar statement for wreath products with Z. This case is much
harder, and we plan to tackle it in a future paper. Our methods can be used for some of
the analysis, but these methods require information regarding the speed of the random
walk on the lamp group, and thus the analysis is more delicate.
It is not known whether the Liouville property depends on the choice of generators
and this is a major open problem. Similarly, we do not know whether claims such as “G
does not support a non-constant sublinear harmonic function” are group properties. As
this is not the focus of the paper, we will always work with the most convenient system of
generators. Theorem 1 can be strengthened to hold for any symmetric finitely-supported
generating measure, and Theorem 2 may be strengthened so that the conclusion on
iterated wreath products would hold for any set of generators, but we will not do it
here.
1.1. Notation. For a graph G, we write x ∼G y to denote two adjacent vertices in G.
The graph metric will be denoted by distG (·, ·). If G is a group, 1G denotes the unit
element in G.
Suppose G = hSi is generated by a finite set S such that S = S −1 (i.e. S is symmetric).
In this case it is natural to consider the Cayley graph of G with respect to S, and the
graph distance in this graph as the metric on G (this is also known as the word metric on
G with respect to S). For every g ∈ G we denote |g| = distG (1G , g). Let µ be a symmetric
probability measure on S; that is, µ(s−1 ) = µ(s) for all s ∈ S. Then µ induces a Markov
chain on G, namely the process with transition probabilities P (x, y) = µ(x−1 y). We call
this process the random walk on G. The law of the random walk on G started from
x ∈ G is denoted by PG
x . When we refer to the walk started at 1G , we omit the reference
to the starting point, i.e. PG = PG
1G .
In all these notations we will omit the notation ‘G’ when the underlying graph (or
group) is clear from the context.
For a function h : G → R, let
Mh (x, r) = max {|h(y) − h(x)| : dist(x, y) ≤ r} .
Let Mh (r) = Mh (1G , r). We use f ≪ g as a short notation for f = o(g) and f ≈ g if
f /g is bounded between two constants.

4

BENJAMINI, DUMINIL-COPIN, KOZMA, AND YADIN

1.2. Harmonic Growth. For a group G and a finitely-supported measure µ on G, a
function h : G → R is called µ-harmonic if for every x ∈ G, h(x) = Ex [h(X1 )], where
(Xn )n≥0 is a µ-random walk on G. In other words, h(Xn ) is a martingale. If µ is clear
from the context we will just call such functions harmonic.
The harmonic growth of a graph G is the smallest rate of growth of a non-constant
harmonic function on G. (In this paper we only work with Cayley graphs, so we will
consider growth around 1G .) For a monotone non-decreasing function f : N → [0, ∞),
we say that G has harmonic growth at least f (this is denoted by har(G)  f — note
that we do not claim har(G) is some well-defined function, this is just a shorthand
notation), if for all non-constant harmonic h : G → R, there exists a constant c > 0
such that Mh ≥ cf . The graph G is said to have harmonic growth at most f if there
exists a harmonic function h : G → R such that Mh ≤ Cf for some constant C > 0 (this
is denoted by har(G)  f ). If the harmonic growth of G is at least f and at most f
then we say that G has harmonic growth f , and denote this har(G) ≈ f . Note that the
harmonic growth of a graph is an asymptotic notion. In particular, it depends only on
the behavior of f at infinity. Let us mention a few properties of the harmonic growth:
(1) The harmonic growth of a Cayley graph is always at most linear since every such
graph possesses a linearly growing harmonic function [12, 15].
(2) The harmonic growth of Zd is linear (the function h(x1 , . . . , xd ) = x1 is harmonic,
and there are no non-constant sublinear growth harmonic functions).
1.3. Lamplighters. We now define the groups that are of interest to us, as well as their
natural set of generators. These are called wreath products or generalized lamplighters,
with the lamplighter group being the simplest example (Z/2) ≀ Z.
Let L, G be groups. The wreath product L ≀ G is the semi-direct product LG ⋊ G,
where LG is the group of all functions from G to L which are 1L for all but finitely
many elements of G (such functions are called function with finite support) and where
G acts on LG by translations. We will denote elements of L ≀ G by (ω, g) with ω ∈ LG
and g ∈ G so the product is
(ω, g)(ξ, k) = (ω(·)ξ(g−1 ·), gk).

For an element (ω, g) ∈ L ≀ G, and k ∈ G, we call g the lamplighter (position), and ω(k)
is the (status of the) lamp at k. The group G is sometimes called the base group and
the group L the group of lamps.
For ℓ ∈ L, define the delta function δℓ ∈ LG by
(
ℓ
if g = 1G
δℓ (g) =
1L otherwise.
and 1 = δ1L . Let S be a generating set of L and U a generating set of G. Consider the
set
Γ = {(δs , 1) : s ∈ S} ∪ {(1, u) : u ∈ U } .

It is not difficult to see that Γ generates L≀G. Right multiplication by (1, u) corresponds
to moving the lamplighter in G while right-multiplying by (δs , 1) corresponds to changing
the status of the current lamp by right-multiplying it by s. Given symmetric probability

MINIMAL HARMONIC FUNCTIONS

5

measures, µ supported on S and ν supported on U , we can define the move or switch
measure, which is a symmetric probability measure µ ≀ ν supported on Γ, by
1
1
and
(µ ≀ ν)(δs , 1) := · µ(s).
(µ ≀ ν)(1, u) := · ν(u)
2
2
That is, under the measure µ ≀ ν, the walk on L ≀ G has the following behavior: with
probability 1/2 the lamplighter moves in G according to the distribution given by ν;
with the remaining probability 1/2 the lamplighter does not move but rather changes
the status of the current lamp according to the distribution given by µ.
If the base group G is transient, then L ≀ G admits bounded non-constant harmonic
functions (i.e. is not Liouville). For instance, one may consider the function h(ω) to be
the probability that the status of the lamp at 1G differs eventually from 1L .
As a consequence, (Z/2Z) ≀ Z3 is an example of an amenable non-Liouville group [11,
§6.2]. See also [8] for a proof that these groups nevertheless do not support non-constant
harmonic functions of bounded energy.
2. Proof of Theorem 2
Recall the statement of Theorem 2: if G is recurrent and if L does not support any
non-constant sublogarithmic functions, then neither does L ≀ G. Before starting the
proof, let us remark that the difficulty lies in the case that L is infinite. If L is finite,
then the theorem may be proved quite similarly to the proof of Theorem 1 (see page 1).
Let us recall quickly the argument:
Sketch of the finite L case. Let x1 , x2 ∈ L ≀ G differ only in the configuration at 1H .
Examine two lazy random walkers starting from the gi and coupled to walk together
except when they are both at 1H , where they have positive probability to glue for all
time. We define E to be the gluing time and Tr to be the first time that the walker reaches
distance r from 1G . Known estimate for return probabilities on recurrent groups (which,
by Gromov’s theorem are finite extensions of Z or Z2 ) show that P(E ≥ T ) ≤ C/ log r.
The sublogarithmicity of h shows that the contribution of this event decays as r → ∞
and the coupling shows that h does not depend on the lamp at 1G . Translating we get
that h does not depend on the state of the lamps at all, and hence may be considered as a
harmonic function on G. But any sublinear harmonic functions on a virtually nilpotent

group is constant (remark 19).
Where changes for L infinite is that one can no longer claim that the probability
that E occurred before k returns to 1G increases to 1 exponentially fast in k. Even
in
√
the simplest case that the lamp group is Z, this probability decays only like 1/ k√and
had we translated the proof literally we would only get that Z ≀ Z2 has no sub- 3 log
non-constant harmonic functions.
To solve this problem we replace our x1 , x2 with infinitely many x, which differ only
at the lamp at 1G . This gives a function ψ : L → R with ψ(ℓ) = h(xℓ ), where xℓ ∈ L ≀ G
is x with the status of the lamp at 1G set to ℓ. Now, ψ is sublogarithmic on L but is
not necessarily harmonic on it. However, the harmonicity and sublogarithmic growth
of h on L ≀ G allows to use the strong Markov property to represent ψ(ℓ) as the value
of h at the kth return of a random walker to 1G . This means that ψ may be written

6

BENJAMINI, DUMINIL-COPIN, KOZMA, AND YADIN

as P k fk , where fk is the value of h had the lamp at 1H never moved (and P is the
transition kernel of the lazy random walk on L). The sublogarithmic growth of h allows
to show that fk (ℓ) ≤ Ck 3 log |ℓ| (the polynomial growth in k is the important fact here),
see Proposition 11. We will show (Proposition 5) that such estimates imply that ψ is
constant. The laziness of the walk plays an important role in this step.
The approach is significantly complicated by the fact that we do not know a-priori
that the value of h at the kth return to 1G is integrable. This complicates the definition
of fk and some parts of the argument. The details are provided in the next sections.
2.1. Preliminaries. We begin with some preliminary results.

Lemma 3. Fix p ∈ (0, 1) and n ∈ N. Let b(k) = nk pk (1 − p)n−k and b(k) = 0 for
k ∈ Z \ {0, . . . , n}.Then for the difference operator defined by ∂ψ(k) = ψ(k) − ψ(k + 1)
we have that, for any k,

m/2
m
m
|∂ b(k)| ≤
.
(1)
p(1 − p)n

Proof. From the binomial formula,

1 − p + peit
which leads to
1
b(k) =
2π

Z

π

itSn

E[e

−itk

]e

−π

n

=

X

b(k)eitk

k

1
dt =
2π

Z

π

−π

1 − p + peit

eit

n

· e−itk dt.

Applying ∂ is the same as multiplying by 1 −
in the Fourier domain hence
Z π

1
n
∂ m b(k) =
1 − p + peit · (1 − eit )m · e−itk dt.
2π −π
We estimate the integral by the maximum of the absolute value of the integrand. The
expression for the maximum would be shorter if we use the quantity u = 2p(1 − p)(1 −
cos(t)) ∈ [0, 1]. We get
|∂ m b(k)| ≤ sup (1 − u)n/2 · um/2 · p−m/2 (1 − p)−m/2 ,
u∈[0,1]

which is maximized at u =

m
m+n .
m

Hence,

|∂ b(k)| ≤



m
p(1 − p)n

m/2

.



Lemma 4. Let G be a group and let P be the transition matrix of some random walk on
G. Let ψ : G → R be a function with sub-linear growth. Then if (I − P )ψ is constant,
then this constant must be zero (and then ψ is harmonic).
Remark. In this lemma the random walk need not be symmetric.
Proof. Let (Xt ) be the random walk on G with transitions given by P and let K be the
constant from the statement of the lemma, i.e. (P − I)ψ ≡ K. Then Mt := ψ(Xt ) − tK
is a martingale and hence for all t,
ψ(x) = M0 = Ex [Mt ] = Ex [ψ(Xt )] − tK.

MINIMAL HARMONIC FUNCTIONS

7

But since ψ has sub-linear growth,
1
1
K = Ex [ψ(Xt )] − ψ(x) −→ 0 as t tends to ∞.
t
t
So K = 0 and ψ is harmonic with respect to P .



Proposition 5. Let G be a group and let P be the transition matrix of some random
walk on G, let α ∈ (0, 1) and let Q = αI + (1 − α)P be the transition matrix of the
corresponding lazy random walk. Let ψ : G → R be a function with sub-linear growth.
Suppose that for infinitely many k there exists functions fk : G → R with fk (g) ≤
CkC |g|C such that ψ = Qk fk . Then, there exists m such that (I − P )m ψ ≡ 0.
Moreover, if ψ grows slower than the harmonic growth of G (with respect to P ), then
ψ is constant.
Proof. Observe that
k

k

Q = (αI + (1 − α)P ) =

k  
X
k
j=0

j

αk−j (1 − α)j P j =

X

b(j)P j ,

j∈N

for b(j) as in Lemma 3, with p, n in Lemma 3 given by p = 1 − α and n = k. Thus we
may write ψ = Qk fk as
X
ψ=
b(j)P j fk .
(2)
j∈N

Thus, for every k for which (2) holds we may write
X
(2) X m
∂ b(j)P j fk ≤
|∂ m b(j)| · |P j f (g)|
|(I − P )m ψ(g)| =
j∈N

(∗)

≤ (k + 1) ·

≤



m
α(1−α)



m
α(1 − α)k

m/2

j∈N

m/2

· sup {|f (h)| : distG (g, h) ≤ k}

· (|g| + k)C · k1−m/2 .

(3)

The inequality marked by (∗) has three parts. First, we use the fact that the sum
has only k + 1 non-zero terms to bound it by k + 1 times the maximal term. Second,
we estimate the term ∂ m b(j) using Lemma 3. Third, for the term P j fk we note that
because the generator P is finitely supported P j f (g) contains only terms with distance
≤ j ≤ k from g, and the coefficients sum to 1, so P j fk can be bounded by the maximum
of fk in the given ball.
Provided that m > 2(C + 1), the last term in (3) converges to 0 as k → ∞. This
implies the first part of the claim.
Let us now assume that ψ grows slower than har(G). Then, (I − P )m−1 ψ also grows
slower than har(G), as it is a finite combination of translates of ψ. Since (I − P )m−1 ψ
is harmonic (via the first part of the claim), this implies that it is constant. However,
because every group has harmonic growth at most linear, we have that (I − P )m−2 ψ is a
sub-linear function with constant Laplacian. By Lemma 4, we get that (I − P )m−2 ψ is
harmonic. Iterating this reasoning, we obtain that ψ is harmonic and thus constant. 

8

BENJAMINI, DUMINIL-COPIN, KOZMA, AND YADIN

Lemma 6. Let (Xt )t = (ωt , gt )t be a random walk on L ≀ G with step measure µ ≀ ν and
define
t
X

1{gt =1G } ≥ k ,
Tk := inf t ≥ 0 :
(4)
j=0

E(r) := inf t ≥ 0 : distG (gt , 1G ) > r .
Then, the random variable ωTk (1G ) is independent of {ωTk (g)}g6=1G and of the event
{Tk < E(r)}. Furthermore, its law is the law of a lazy µ-random walk on L with laziness
probability 1/2, at time k.
The proof of this statement is elementary and will be omitted.
We finish this section with a few standard facts on recurrent groups. Most readers
would want to skip to §2.2.
Lemma 7. Let G be a recurrent group, let g ∈ G and let r > |g|. Let E be the event
that the random walk on G starting from g reaches distance r from 1G before reaching
1G itself. Then, P(E) ≤ C log |g|/ log r.

Proof. Any recurrent group contains as a subgroup of finite index one of 0, Z or Z2 , see
e.g. [20, Theorem 3.24]. The proof uses deep results by Varopoulos, Gromov, Bass, and
Guivarc’h, see [20] for details and references. The theorem of Gromov has had a new
proof recently, see [12, 15].
Let us start with the case that G = Z2 . In this case it is known [16, §4.4] that
there is a function a : Z2 → R harmonic everywhere except at (0, 0) and satisfying
a(x) = c log |x| + O(1). Let b be the harmonic extension of the values of a on the
boundary of the ball of radius r to its interior (so b(x) = c log r + O(1)). We see that
h = 1 − (b − a)/(b(0, 0) − a(0, 0)) is harmonic on the ball except at (0, 0), is 0 at (0, 0), 1
on the boundary and (log |g| + O(1))/ log r at g. By the strong Markov property, h(g)
is exactly the probability sought, and the claim is proved in this case.
The case that the group is a finite extension of Z2 (i.e. that it contains a subgroup
of finite index isomorphic to Z2 ) may be done similarly: the function a on G can be
defined, as in [16], by
∞
X
(pn (1G ) − pn (h)),
a(h) =
n=0

where pn is the heat kernel on G. Since G satisfies a local central limit theorem (see
e.g. [1]), a would still satisfy a(x) = c log(|x|) + O(1). If G is a finite extension of Z a
similar argument holds except this time a(g) = O(|g|) and we get P(E) ≤ C/r. If G is
finite, then P(E) = 0 for r sufficiently large.


Lemma 8. Let G be a recurrent group and let E(r) be the exit time from a ball of radius
r. Then
P(E(r) > M ) ≤ 2 exp(−cr −2 M ).
Proof. Random walk on any group satisfies the weak Poincaré inequality, see [14, 4.1.1]
for the statement of the inequality and the proof. Since, as in the proof of the previous
lemma, it is a finite extension of {0}, Z or Z2 , it also satisfies volume doubling√i.e.
|B(2r)| ≤ C|B(r)|. This means, by Delmotte’s theorem [5] that pt (x, y) ≤ C/|B( t)|.

MINIMAL HARMONIC FUNCTIONS

9

Summing this inequality we see that after time C1 r 2 for some C1 sufficiently large the
probability to stay in a ball of radius 2r is ≤ 12 . This means that if in time t you
are at some g ∈ B(1G , r) then by time t + C1 r 2 you have probability ≥ 21 to exit
B(g, 2r) ⊃ B(1G , r). In the language of E(r) this means that
1
P(E(r) > t + C1 r 2 | E(r) > t) ≤ .
2
The lemma follows readily.



Lemma 9. Recall the definition of Tk and E(r) from (4). For every k ≥ 1, every M ≥ 0
and every starting point x = (ω, g) ∈ L ≀ G, we have that log(E(r) + M ) is integrable
and
log(r + M ) log(|g|)
Ex [log(E(r) + M )1{E(r)≤Tk } ] < Ck
.
(5)
log r
Proof. The integrability clause is an immediate corollary of Lemma 8 so we move to
prove (5). Write
E[·] = E[·1{E(r)<r3 } ] +

∞
X

E[·1{E(r)∈[r3 2i ,r3 2i+1 )} ].

(6)

i=0

In the first term, the integrand log(E(r) + M )1{E(r)<r3 } is bounded by log(M + r 3 ) ≤
3 log(M + r) and the probability of the event {E(r) ≤ Tk } is at most Ck log(|g|)/ log r
by Lemma 7. For the second term in (6), we drop the condition E(r) ≤ Tk and write
h
i
E log(E(r) + M ) · 1{E(r)≤Tk } · 1{E(r)∈[r3 2i ,r3 2i+1 )} ≤
≤ log(r 3 2i+1 + M ) · P[E(r) ≥ r 3 2i ] ≤ log(r 3 2i+1 + M ) exp(−cr2i ),

which may be readily summed over i and the sum is bounded by C log(r + M )/ log r.
The lemma is thus proved.

2.2. The main step. We proceed with the proof of Theorem 2. Throughout this
section, we fix a group L with har(L)  log, and a recurrent group G. We fix x ∈ L ≀ G
for the rest of the proof.
For ℓ ∈ L, let φℓ : L ≀ G → L ≀ G be the function that changes the status of the lamp
at 1G to ℓ, leaving all other lamps unchanged. Formally,
(
σ(k) if k 6= 1G
φℓ (σ, g) = (τ, g) with τ (k) =
ℓ
otherwise.
We note immediately that φ does not change distances by much:
|φℓ (g)| ≤ |g| + |ℓ|,

(7)

which holds for our specific choice of generators.
Definition 10. Let h : L ≀ G → R be a harmonic function of sub-logarithmic growth.
For k ≥ 1 and ℓ ∈ L define
fk (ℓ) = lim EL≀G
x [h(φℓ (XT (k)∧E(r) ))].
r→∞

(8)

10

BENJAMINI, DUMINIL-COPIN, KOZMA, AND YADIN

where T (k) and E(r) are defined by (4). Note that fk depends also on h and x, but
these will be suppressed in the notation.
It is not clear a-priori that fk is well-defined as we have not shown that h(φℓ (XT (k)∧E(r) ))
is integrable, nor that the limit exists. We will show this in Proposition 11 below, and,
more importantly, give a useful estimate on fk .
Proposition 11. For every k ≥ 1, fk is well-defined and satisfies
|fk (ℓ)| ≤ C log(|x| + |ℓ|) · k3 ,

for some constant C > 0 (which may depend on h).
Proof. Denote




|h(x)|
M (r) = sup
: |x| ≥ r
log(|x|)
and note that M is decreasing in r and M (r) → 0 as r → ∞. We first reduce the
problem by noting that
lim Ex [h(φℓ (XE(r) )) · 1{E(r)<Tk } ] = 0.

(9)

r→∞

To see (9), first note that
(7)

and hence

r ≤ |φℓ (XE(r) )| ≤ |XE(r) | + |ℓ| ≤ E(r) + |x| + |ℓ|
h(φℓ (XE(r) )) ≤ M (|φℓ (XE(r) )|) log(|φℓ (XE(r) )|)
≤ M (r) log(E(r) + |x| + |ℓ|).

Taking expectation (and assuming r > |x|), we get
Ex [h(φℓ (XE(r) )) · 1{E(r) < Tk }]

≤ M (r) Ex [log(E(r) + |x| + |ℓ|) · 1{E(r) < Tk }]
(5)

≤ M (r) · Ck

log(r + |x| + |ℓ|) log(|x|)
→0
log r

as r → ∞

(10)

proving (9). A similar calculation shows that the variables integrated over in the definition of fk (8) are indeed integrable. All similar quantities (i.e. that involve only the
walk in the ball of radius r in G) are proved to be integrable using the same argument
so we will not return to this point later on.
At some point during the proof, it will be convenient to assume that the walk is not
degenerate i.e. does not spend all its time at 1G (in particular the degenerate case can
happen only if the G-component of the starting point x is 1G ). Since the contribution
of this event is clearly bounded by Ce−ck log(|x| + |ℓ|) and is independent of r, we will
remove it now. Define therefore
A := {the walk spends all its time at 1G }
B := {Tk < E(r)} \ A

f (r) := Ex [h(φℓ (XTk )) · 1B ].

(11)

MINIMAL HARMONIC FUNCTIONS

11

Due to the previous discussion, the proposition will be proved once we show that f (r)
converges, and that lim f (r) ≤ Ck 3 log(|x| + |ℓ|).
Define now gt to be the position of the lighter at time t (or the G-component of Xt if
you want) and define
Λj = max{|gt | : t ∈ [Tj , Tj+1 ]},

where Tj are still defined by (4). We call Λj the height of the j th excursion. We need to
single out the excursion with the largest height (denote it by i — if there are ties take
the last longest walk). Define therefore the following two random elements of L ≀ G,
XTi+1
V = XT−1
i

XTk .
W = XTi XT−1
i+1

In words, V is the excursion of largest height and W are all the rest. We note the
following
Lemma 12. Under B the variables XTk and W V have the same distribution.
Proof. Since the G component of all XTi is 1G then we need only consider the lamps.
However, whether we take the steps of the random walk in the original order (XTk )
or with the largest excursion taken out and performed in the end (W V ), each lamp
is visited exactly the same number of times. So conditioning on the steps in the G
direction, each lamp does a simple random walk on L of equal length (we use here that
the event B depends only on the G component). This shows that XTk and W V have the
same distribution after conditioning on the walk in the G direction. Integrating gives
the lemma.

In particular,
f (r) = E[h(φℓ (W V )) · 1B ].
Condition on W and examine V . It is the value of simple random walk on L ≀ G,
conditioned to have larger height that all other excursions, at the time when it first
returns to 1G . Examine the time τ when the walker “knows” this excursion is the
longest (this could be either the time when it reaches the same height as the highest
excursion in W , or when it surpasses it, depending on how one resolves ties, but in all
cases it is a stopping time). We also modify τ in the degenerate case that all excursions
in W stay in 1G and require from τ to be at least XTi + 1 even if the walker knows it
was the largest already at time XTi , so that the walker also knows it did not spend all
time in 1G . After τ , the walk is a simple random walk, unconditioned. Write V = V1 V2
with
Xτ
V2 = Xτ−1 XTi+1
V1 = XT−1
i
and condition also on V1 . Write
f (r) = Ex [E[h(φℓ (W V1 V2 )) · 1B | i, W, V1 ]].

We notice two facts. First, the condition ¬A (recall that A is our degenerate event, see
(11)) affects only W and V1 , and can be taken from the inner expectation to the outer.
Second, we can write φℓ (W V1 V2 ) = φℓ (W )V1 V2 because the value of the lamp at 1G is
changed only in excursions of height 0 (here we use ¬A ). Denote y = φℓ (W )V1 . We get


 
(12)
f (r) = Ex E h(yV2 ) · 1{E(r)>Tk } | i, W, V1 1¬A .

12

BENJAMINI, DUMINIL-COPIN, KOZMA, AND YADIN

We now apply the strong Markov property at the stopping time τ . The event E(r) > Tk
for the “external” random walk becomes E(r) > T1 for the random walk after τ , and V2
becomes XT1 . Hence
E[h(yV2 ) · 1{E(r)>Tk } ] = Ey [h(XT1 ) · 1{E(r)>T1 } ].
It is time to use the fact that h is harmonic on L ≀ G. We write
Ey [h(XT1 )1{E(r)>T1 } ]

=

Ey [h(XE(r)∧T1 )]

−

Ey [h(XE(r) )1{T1 >E(r)} ]

(of course E(r) and T1 cannot be equal). Since h is harmonic, the process (h(Xt∧T1 ∧E(r) ))t
is a martingale. Further, we may use the bounded convergence theorem because
sup |h(Xt∧T1 ∧E(r) )| ≤ max |h(Xt )| ≤
t

t≤E(r)

≤ max C log(|Xt |) ≤ C log(|y| + E(r))
t≤E(r)

which is integrable, by Lemma 9. We get
Ey [h(XT1 ∧E(r) )] = h(y).
Inserting this into (12) gives
f (r) = Ex

h

i
h(y) − Ey [h(XE(r) )1{T1 >E(r)} ] 1¬A .

It will be convenient to add the condition that the height of the second-highest excursion
is ≤ r. We may do so because otherwise |y| > r, in the inner expectation the walker
is stopped immediately (E(r) = 0) and the inner expectation itself is exactly h(y) and
the term contributes zero. Denote C = {the second-highest excursion is ≤ r} \ A . We
write
II = f (r) − I
I = Ex [h(y) · 1C ]
II = the rest

and bound these terms individually.
Let us start with the second term, which can be reasonably considered to be the error
term. We reverse the use of the Markov property and get
Ey [h(XE(r) )1{T1 >E(r)} ] = E[h(yV3 )1{E(r)<Tk } | i, W, V1 ],

where V3 is the part of V2 until the first time it exits the ball of radius r in G (recall
that i denotes the excursion of largest height). Recall that y = φℓ (W )V1 and that V1 is
a random walk on L ≀ G conditioned to be longer than all excursions in W and stopped
when it knows it is. Hence V1 V3 is simply a random walk conditioned to be longer than
all excursions in W . Returning the integration over W and V1 , we get
II = − Ex [h(φℓ (W )V1 V3 )1D ]

(13)

where D is the event that all excursions except for the longest did not exit the ball of
radius r (this part was C ), while the longest did exit it (this is E(r) < Tk ). Now, write
(7)

|φℓ (W )V1 V3 | ≤ |ℓ| + |W | + |V1 V3 |.
The expression |W |+ |V1 V3 | allows us to get rid of the conditioning in V1 V3 . We can now
claim that |W | + |V1 V3 | is bounded by the sum of lengths of k excursions exactly one of

MINIMAL HARMONIC FUNCTIONS

13

which exits the ball of radius r in G. Denoting by Di the event that the ith excursion is
the one that exits the ball of radius r, we may write, under Di ,
|W | + |V1 V3 | ≤ |x| + E(r) + |Tk | − |Ti+1 |

and then

E[log(|φℓ (W )V1 V3 |) · 1Di ]

≤ E[log(|x| + |ℓ| + E(r)) · 1Di ] + E[log(Tk − Ti+1 ) · 1Di ]

The first term may be estimated by Lemma 9 to be at most

Ci log(r + |x| + |ℓ|) log(|x|)/ log r.

For the second term we note that the effect of Di on the random walk after Ti+1 is just
to prohibit exiting the ball of radius r and then
E[log(Tk − Ti+1 ) · 1Di ]

≤ E[log(Tk−i−1 ) · 1{Tk−i−1 < E(r)}] · P[E(r) < Ti+1 ] ≤ Ci.

where the last inequality estimates E[·] ≤ C log r using Lemma 8 and P[·] ≤ Ci/ log r by
Lemma 7.
Combining both parts we may write
(13)

II = − Ex [h(φℓ (W )V1 V3 )1D ]

≤ M (r) Ex [log(|φℓ (W )V1 V3 |)1D ]

≤ M (r)
(∗)

k
X

≤ M (r)

Ex [log(|φℓ (W )V1 V3 |)1Di ]
i=1
k 
X
i=1


Ci log(r + |x| + |ℓ|) log(|x|)
+ Ci
log r

≤ C(x, ℓ, k)M (r)

where in (∗) we applied the previous discussion. In particular II → 0 as r → ∞.
We now move to the estimate of I. For this, we denote by Es , s > 2 the event that
the height of the second-heighest excursion is in [s, s2 ) and for s = 2, replace [2, 4] with
[0, 4]. Denote
Is := Ex [h(y) · 1{C , Es }]
Now, the event Es has probability ≤ Ck 2 / log2 s since it requires two of the k excursions
to reach height s. On the other hand,
|y| ≤ |x| + |ℓ| + the total time of the process .

Define U to be the sum of the lengths of the first two excursions to s2 i.e.
U1 = E(s2 )
U3 = min{t > U2 : |gt | > r}

U2 = min{t > U1 : gt = 1G }
U = U3 − U2 + U1 .

Then, under Es , the total time of the process is bounded by U , and we may write
|y| ≤ |x| + |ℓ| + U.

14

BENJAMINI, DUMINIL-COPIN, KOZMA, AND YADIN

By Lemma 8 E(U ) ≤ s4 and U has exponential concentration. Any positive variable
with exponential concentration, when conditioned over an event of probability p, can
“gain” no more than | log p| by the conditioning. Hence, we get
Is ≤ Ex [C log(|x| + |ℓ| + U ) · 1{C , Es }]


Ck2
Ck 2
4
· log(|x| + |ℓ| + s ) log
≤
log2 s
log2 s
log log s
≤ Ck3 log(|x| + |ℓ|)
.
log s

This shows that
I=

∞
X

n=0

(14)

I22n ≤

∞
X

Ck3 log(|x| + |ℓ|)

n=0
Ck3 log(|x|+|ℓ|)

(14)

n
2n

and in particular that I is bounded by
independently of r. Furthermore,
n+1
it is clear that I22n is independent of r as long as r > 22 , since the event that the
n+1
implies that neither y nor C depend on
second-highest excursion is not larger than 22
r. So we get that I converges as r → ∞, and its limit is bounded by Ck3 log(|x| + |ℓ|).
As II → 0 as r → ∞, the proposition is proved.

We now complete the proof of Theorem 2.
Proof of Theorem 2. Fix x = (ω, g) ∈ L ≀ G and define a function ψ : L → R by
ψ(ℓ) = h(φℓ (x)). We wish to relate ψ and fk (from Definition 10 with the same x and
h). Let therefore k ≥ 1 and r sufficiently large and examine h(XTk ) under the event
Tk < E(r). At every visit to 1G , the lamp there has probability 12 to move. Hence, at Tk
the distribution of the lamp is exactly that of the lazy random walk on L after k steps.
This means that, conditioning on everything that the walk does outside 1G ,
h(XTk ) ∼ Qk (h(φω(1G ) (XTk ))),

where Q = 12 (I + P ) is the transition matrix of the lazy P -random walk on L, with
laziness probability 21 (the operand of Q above, i.e. h(φω(1G ) (XTk )), is considered as a
function of ω(1G ) i.e. of the status of the lamp at 1G of the starting point). Taking
expectations (still under Tk < E(r)), we get
Ex [h(XTk )1{Tk < E(r)}] = Qk (Ex [h(φω(1G ) (XTk ))1{Tk < E(r)}]).
Because h is sub-logarithmic in growth, we know that h(XE(r) ) · 1{E(r) < Tk } goes to 0
as r → ∞ (see the beginning of the proof of Proposition 11). So we get for the left-hand
side,
lim Ex [h(XTk )1{Tk < E(r)}] = lim Ex [h(XE(r)∧Tk )] = h(x)
r→∞

r→∞

where in the last equality we used that h is harmonic on L ≀ G. For the right-hand side,
we get
lim Ex [h(φℓ (XTk ))1{Tk

r→∞

<

E(r)}]

=

lim Ex [h(φℓ (XTk ∧E(r) ))]

r→∞

This gives the sought-after relation,
ψ = Qk f k .

=

fk (ℓ).

MINIMAL HARMONIC FUNCTIONS

15

Using Proposition 5 and the facts that ψ grows sub-logarithmically and har(G)  log(·),
we obtain that ψ is constant. Therefore, h(φℓ (x)) = h(x) for all ℓ and all x; that is, h
does not depend on the status of the lamp at 1G .
We may repeat this argument for the lamps at other elements of G by translating
h. We conclude that h is a function depending only on the position of the lamplighter,
and not on the lamp configuration. Thus, h can be viewed as a sub-linear (in fact
sub-logarithmic) harmonic function on G. Since G is recurrent, it implies that h is
constant.

2.3. Harmonic growth with Z2 base. Complementing Theorem 2, we show that
when the base group is Z2 then the harmonic growth is logarithmic. For simplicity of
the presentation, we show this for the group G := (Z/2Z) ≀ Z2 , other cases are similar.
Due to Theorem 2, it suffices to construct a logarithmically growing non-constant
harmonic function on (Z/2Z) ≀ Z2 .
Let a : Z2 → R be
P the potential kernel, as defined in [16, §4.4]. That is, a is harmonic
on Z2 \ {0} and 41 w∼0 a(w) = a(0) + 1. The standard normalization is a(0) = 0, but
we will normalize it instead by a(0) = 21 . Further, a(x) = c log |x| + O(1) as |x| → ∞
for some constant c > 0.
We may now define our harmonic function. We define h(σ, z) = (−1)σ(0) · a(z) for
any (σ, z) ∈ G. The logarithmic growth is clear from the growth of a so we only need
to show that h is indeed harmonic.
Recall that the neighbors of (σ, z) in L are (σ, z±ej ) and (σ z , z) where e1 = (1, 0), e2 =
(0, 1) and σ z is the configuration σ with the state of the lamp at z flipped. Assume that
the random walk goes to σ z with probability 12 and to each of the neighbors in Z2 with
probability 18 .
We have that if z 6= 0,
!
X
X
z
σ(0)
1
1
1
1
· a(z) + 4
h(σ, w) = 2 (−1)
a(w) = (−1)σ(0) a(z) = h(σ, z),
2 h(σ , z)+ 8
w∼z

w∼z

and if z = 0,
0
1
2 h(σ , 0)

+

1
8

X

w∼0

h(σ, w) = 21 (−1)σ(0) ·

So h is harmonic on L.

− 21 +

1
4

X

w∼0

!

a(w)

= 12 (−1)σ(0) = h(σ, 0).

3. Iterated wreath products
Proposition 13. For any k ≥ 1, there exists a group G such that har(G)  log and
H(Xn ) ≥ c(k)n/ log(k) n, where (Xn )n is a random walk on G.
Proof. Define G1 = (Z/2Z) ≀ Z2 and Gk+1 = Gk ≀ Z2 . On the one hand, Theorem 2 tells
us that har(Gk )  log for all k ≥ 1.
On the other hand, let L be a group and G = L ≀ Z2 . Let HG (n) be the entropy of
the nth step of a random walk on L. Then, for some constant C > 0 (which depends

16

BENJAMINI, DUMINIL-COPIN, KOZMA, AND YADIN

only on the degree of the Cayley graph chosen for L),
n
HL (log n).
HG (n) ≥ c
log n

(15)

Indeed, let (Xn = (σn , zn ))n be a random walk on G. For z ∈ Z2 , let Kn (z) be the
number of times the lamplighter was at z up to time n. For each z ∈ Z2 , σn (z) is a
lazy random walk on L that has taken Kn (z) steps. Thus, if Y denotes the lazy random
walk on L,
hX
i
HL (n) = H((σn , zn )) ≥ H((σn , Kn )) ≥ H(σn |Kn ) = E
H(YKn (z) )
z∈Z2




≥ E |{z ∈ Z2 : Kn (z) ≥ log n}| · HG (log n).


2 . Known estimates [16] give that E |{z ∈
The walk (zn ) is a lazy
random
walk
on
Z

Z2 : Kn (z) ≥ log n}| > cn/ log n for some universal constant c > 0 small enough.
Equation (15) follows readily.
The estimate above enables us to relate Gk to Gk−1 . Iterating until G1 , we find that
n
HGk (n) > ck (k) ,
log n
where as usual log(k) is iteration of log k times.



We remark that in fact HGk (n) < Cn/ log(k) n as well, which can be proved using the
same calculation, bounding the error terms.
The contrapositive of the above is that if f is some monotone function such that for
all groups har(G)  f (n/H(Xn )), then f must grow faster than exp exp · · · exp n for any
number of iterations of exponentials.
4. Open Questions
Let us list some of the many natural open problems that arise in the context of
unbounded harmonic functions on Cayley graphs (discrete groups).
(1) A major open question is whether the Liouville property is a group property
or not, or in other words, if it is independent of the choice of generators. A
generalization of this question is: Does the harmonic growth of the group depend
on the finite generating set? That is, given a group G with G = hSi = hS ′ i for
finite symmetric sets S, S ′ , is it true that the harmonic growth is the same for
both Cayley graphs?
(2) This paper only focuses on the smallest growing non-constant harmonic functions. One may also consider larger growth harmonic functions. It is well known
that on Zd the smallest non-constant harmonic functions are linear, and the
second-smallest are quadratic (see e.g. [13]). Do other groups (of non-polynomial
volume growth) admit such a “forbidden gap” in the growth of non-constant
harmonic functions? See [1, 10, 18] for precise results in the case of polynomial
growth.

MINIMAL HARMONIC FUNCTIONS

17

(3) Gromov’s theorem [9] states that a group with polynomial growth is virtually
nilpotent. A key ingredient in Kleiner’s new proof of Gromov’s theorem [12, 15]
is the fact that on a group of polynomial volume growth, the space of Lipschitz
harmonic functions is finite dimensional. The following question is therefore
natural:
Let G be a finitely generated group, and consider the space of Lipschitz harmonic functions on G. Suppose this space is finite dimensional. Does it follow
that G is virtually nilpotent?
We remark that this cannot be deduced directly from Kleiner’s proof. Kleiner’s
proof contains an inductive step where one reduces the question to a subgroup.
The property of having polynomial growth can be carried from a group to a
subgroup, but for the property of having a finite-dimensional space of harmonic
functions, we do not know a-priori if this carries over to a subgroup.
See [17] for a treatment of this question in the solvable case. Also related is
Tointon’s result characterizing virtually Z groups as those with the space of all
harmonic functions being finite dimensional, see [19].
Even if we cannot deduce that G is virtually nilpotent, we might still be able
to deduce some properties of random walk on it. A perhaps more tractable
question would be:
Suppose G has a finite-dimensional space of Lipschitz harmonic functions.
Does it follow that the random walk on G is diffusive?
(4) Another interesting question is to characterize those groups for which there do
not exist sub-linear non-constant harmonic functions. As noted above, all groups
with polynomial volume growth are such, but also (Z/2Z) ≀ Z.
Appendix A. Entropy Bound
A.1. Entropy. For background on entropy see e.g. [4].
Let µ, ν be probability measures supported on a finite set Ω. Define
X
H(µ) =
µ(ω) log µ(ω),
ω

D(µ||ν) =

X

µ(ω) log( µ(ω)
ν(ω) ),

ω

x
0

where x log is interpreted as ∞ (so D(µ||ν) is finite only if µ is absolutely continuous
with respect to ν). Let P be a probability measure on Ω × Ω′ , (where Ω, Ω′ are finite)
with marginal probability measures µ and ν on Ω and Ω′ respectively. Define


X
P (ω,ω ′ )
I(µ, ν) =
.
P (ω, ω ′ ) log µ(ω)ν(ω
′)
(ω,ω ′ )∈Ω×Ω′

(I depends on P but we omit it in the notation). If X, Y are random variables in
some probability space taking finitely many values, then we define H(X), D(X||Y ) and
I(X, Y ) using the corresponding induced measures on the value space.
For two random variables X and Y , the conditional entropy of X conditioned on Y is
defined as H(X|Y ) = H(X, Y ) − H(Y ). If p(x, y) is the probability that (X, Y ) = (x, y)

18

BENJAMINI, DUMINIL-COPIN, KOZMA, AND YADIN

and p(x|y) = p(x, y)/p(y), then
H(X|Y ) = E[− log p(X|Y )]
X
=−
p(y)
y : p(y)>0

X

p(x|y) log p(x|y).

x : p(x|y)>0

It may also be easily checked that
I(X, Y ) = H(X) − H(X|Y ) = H(X) + H(Y ) − H(X, Y ).
Lemma 14. Let X and Y be two random variables on some probability space, taking
finitely many values. Let f be some real valued function defined on the range of X and
Y . Then,
(E[f (X)] − E[f (Y )])2 ≤ 2D(X||Y ) · (E[f (X)2 ] + E[f (Y )2 ]).
Proof. Define the following distance between variables
X (P[X = z] − P[Y = z])2
.
dBTV (X, Y ) =
P[X = z] + P[Y = z]
z

If there exists z such that P[X = z] > P[Y = z] = 0, then D(X||Y ) = ∞ and there is
nothing to prove. Let us now assume that for all z, P[Y = z] = 0 implies P[X = z] = 0.
Hence, we can always write p(z) := P[X = z]/ P[Y = z] and
X
(1 − p(z))2
.
dBTV (X, Y ) =
P[Y = z] ·
1 + p(z)
z

Consider the function f (ξ) = ξ log ξ (with f (0) = 0). We have that f ′ (ξ) = log ξ +
1, f ′′ (ξ) = 1/ξ. Thus, expanding around 1, we find that for all ξ > 0, ξ log ξ − ξ + 1 ≥
(ξ−1)2
2(1+ξ) . This implies
X
dBTV (X, Y ) ≤ 2
P[Y = z](1 − p(z)) + 2D(X||Y ) = 2D(X||Y ).
z

Using Cauchy-Schwartz, one obtains
X
| E[f (X)] − E[f (Y )]| =
| P[X = z] − P[Y = z]| · |f (z)|
z

p

p
dBTV (X, Y ) · E[f (X)2 ] + E[f (Y )2 ]
p
p
≤ 2D(X||Y ) · E[f (X)2 ] + E[f (Y )2 ].
≤



Corollary 15. Let X, Y be random variables on some probability space, taking finitely
many values. Let f be some real valued function on the range of X. Then,
i
h
p
p
E E[f (X)|Y ] − E[f (X)] ≤ 2 I(X, Y ) E[f (X)2 ].

Proof. Define X|y to be the random variable whose density is P[X|y = x] = P[X =
x|Y = y]. By Lemma 14 applied to X and (X|y),


2
E[f (X|y)] − E[f (X)] ≤ 2D X|y X · (E[(f (X|y)2 ] + E[f (X)2 ])

MINIMAL HARMONIC FUNCTIONS

19



≤ 2D X|y X · (E[f (X|y)2 ] + E[f (X)2 ]).

Summing (after weighting by P[Y = y]) the previous equation for every y, and observing
that
X
I(X, Y ) =
P[Y = y]D(X|y||X)
and

P

y

P[Y =

y] E[f (X|y)2 ]

=

y
E[f (X)2 ],

E E[f (X)|Y ] − E[f (X)] =
≤

X
y

X
y

the Cauchy-Schwarz inequality implies
P[Y = y] · E[f (X|y)] − E[f (X)]

q

P[Y = y] 2D X|y X · (E[f (X|y)2 ] + E[f (X)2 ])

p
√ p
≤ 2 I(X, Y ) · 2 E[f (X)2 ].



The next proposition is our main tool, relating harmonic functions and the incremental
entropy of a random walk.
Proposition 16. Let G be a group. Let (Xn )n≥0 be a random walk on G. Let h : G → R
be a harmonic function. Then,
(Ez |h(X1 ) − h(z)|)2 ≤ 4 Ez [|h(Xn ) − h(z)|2 ] · (H(Xn ) − H(Xn−1 )).
Proof. Since h is harmonic we have that |h(X1 ) − h(z)| = | Ez [h(Xn )|X1 ] − Ez [h(Xn )]|.
Using Corollary 15 (with X being Xn , Y being X1 and f (x) = h(x) − h(z)), we find
that
p
p
Ez |h(X1 ) − h(z)| ≤ 2 · I(Xn , X1 ) · Ez [(h(Xn ) − h(z))2 ].
Since G is transitive, we have that H(Xn |X1 ) = H(Xn−1 ). Thus,
I(Xn , X1 ) = H(Xn ) + H(X1 ) − H(Xn , X1 )

= H(Xn ) − H(Xn |X1 ) = H(Xn ) − H(Xn−1 ),

which implies the claim readily.



Our inequality actually provides a quantitative estimate on the growth of harmonic
functions, which quantifies the above direction of the Kaimanovich-Vershik criterion.
Theorem 17. Let G be a group. Let (Xn )n≥0 be a random walk on G. Then,
p
har(G)  n/H(Xn ).
Proof. Note that by the Markov property, for any k,

Thus,

H(X1 |Xk ) = H(X1 |Xk , Xk+1 , . . .).

H(Xk ) − H(Xk−1 ) = H(Xk ) − H(Xk |X1 ) = H(X1 ) − H(X1 |Xk )
is a decreasing sequence in k. Thus,
n
X

H(Xk ) − H(Xk−1 ) ≥ n · H(Xn ) − H(Xn−1 ) .
H(Xn ) =
k=1

20

BENJAMINI, DUMINIL-COPIN, KOZMA, AND YADIN

Let h : G → R be a non-constant harmonic function. Let x ∼ y be vertices such that
h(x) 6= h(y). By Lemma 16

(Ex |h(X1 ) − h(x)|)2 ≤ 4 Ex [h(Xn )2 ]H(Xn )/n ≤ 4Mh (x, n)2 H(Xn )/n.
p
Since Ex |h(X1 ) − h(x)| is a positive constant, we have that Mh (x, n)  n/H(Xn ). 

Corollary 18 (Avez, Kaimanovich-Vershik [11]). Let G be a group. Let (Xn )n≥0 be
a random walk on G. If H(Xn )/n tends to 0, then G is Liouville (meaning that any
bounded harmonic function is constant).
Remark 19. One can also use Proposition 16 to show that for groups with polynomial
growth, the harmonic growth is linear. This is done (in a slightly different context) in
[3]. Since it is so short, let us repeat the argument here.
The only required fact is that for a group of polynomial growth the random walk is
diffusive. So if h is a sub-linear harmonic function then Ex [h(Xn )2 ] = o(n) as n → ∞.
Since the group is of polynomial growth, H(Xn ) = O(log n), and so there are infinitely
many n for which H(Xn ) − H(Xn−1 ) = O(n−1 ). Along this infinite sequence of n, we
have by Lemma 16
(Ex |h(X1 ) − h(x)|)2 ≤ o(n) · O(n−1 ) = o(1),

so h(X1 ) = h(x) a.s. Since this holds for all x, it must be that h is constant.
References
[1] Alexopoulos, G. K., Random walks on discrete groups of polynomial volume growth. Ann. Probab.
30:2 (2002), 723–801. Available at: projecteuclid.org
[2] Avez, A., Harmonic functions on groups. Differential geometry and relativity, 27–32. in: Mathematical
Phys. and Appl. Math., Vol. 3, Reidel, Dordrecht, (1976).
[3] Benjamini, I., Duminil-Copin, H., Kozma, G., and Yadin, A. Disorder, entropy and harmonic
functions. Ann. Probab. 43:5 (2015), 2332–2373. Available at: arXiv:1111.4853
[4] Cover, T. M., and Thomas, J. A. Elements of Information Theory. John Wiley & Sons, Inc.,
(1991).
[5] Thierry Delmotte, Parabolic Harnack inequality and estimates of Markov chains on graphs, Rev.
Mat. Iberoamericana 15:1 (1999), 181–232. Available at: rsme.es
[6] Derriennic, Y., Quelques applications du théoréme ergodique sous-additif [French: Some applications
of the sub-additive ergodic theorem]. Conference on Random Walks (Kleebach, 1979), Astérisque 74
(1980), 183–201.
[7] Erschler, A. and Karlsson, A., Homomorphisms to R constructed from random walks. Ann. Inst.
Fourier 60(6) (2010), 2095–2113. Available: aif.cedram.org, math.kth.se/~ akarl
[8] Georgakopoulos, A., Lamplighter graphs do not admit harmonic functions of finite energy. Proc.
Amer. Math. Soc. 138(9) (2010), 3057–3061. Available at: ams.org, arXiv:0907.1398
[9] Gromov, M., Groups of polynomial growth and expanding maps. Inst. Hautes Études Sci. Publ.
Math. 53 (1981), 53–73. Available at: numdam.org
[10] Hua, B. and Jost, J., Polynomial growth harmonic functions on groups of polynomial volume
growth. Preprint (2012). Available at: arXiv:1201.5238
[11] Kaimanovich, V. A., and Vershik, A. M., Random walks on discrete groups: boundary and entropy.
Ann. Probab. 11 (1983), 457–490. projecteuclid
[12] Kleiner, B., A new proof of Gromov’s theorem on groups of polynomial growth. J. Amer. Math.
Soc. 23(3) (2010), 815–829. ams.org, arXiv:0710.4593
[13] Lippner, G. and Mangoubi, D., Harmonic functions on the lattice: Absolute monotonicity, propagation of smallness, construction. Preprint (2013), available at: arXiv:1312.4550

MINIMAL HARMONIC FUNCTIONS

21

[14] Pittet, C. and Saloff-Coste, L., A survey on the relationships between volume growth, isoperimetry,
and the behavior of simple random walk on Cayley graphs, with examples. Preprint (2001). Available
at: cornell.edu/~ lsc
[15] Tao, T., A proof of Gromov’s theorem. Blog (2010), terrytao.wordpress.com
[16] Lawler, G. F., and Limic, V. Random Walk: A Modern Introduction. Cambridge University
Press, 2010.
[17] Meyerovitch, T., and Yadin, A. Harmonic functions of linear growth on solvable groups. Israel J.
of Math. to appear. arXiv:1408.6243
[18] Meyerovitch, T., Perl, I., Tointon, M., and Yadin, A. Polynomials and harmonic functions on
discrete groups. arXiv:1505.01175
[19] Tointon, M. Characterisations of algebraic properties of groups in terms of harmonic functions.
arXiv:1409.6326
[20] Woess, W., Random walks on infinite graphs and groups. Cambridge Tracts in Mathematics, 138.
Cambridge University Press, Cambridge, 2000.

IB, GK: Department of mathematics, the Weizmann institute of science.
E-mail address: itai.benjamini@weizmann.ac.il, gady.kozma@weizmann.ac.il
HDC: Université de Genève, Genève, Switzerland
E-mail address: hugo.duminil@unige.ch
AY: Ben-Gurion University of the Negev, Beer Sheva, Israel
E-mail address: yadina@bgu.ac.il

