text: ENTROPY AND DRIFT IN WORD HYPERBOLIC GROUPS 2 that the methods always diﬀer. Our main result conﬁrms this intuition in a special class of groups: In hyperbolic groups which are not virtually free (i.e., there is no ﬁnite index free subgroup), if d is a word distance, the two methods are always diﬀerent, in a precise quantitative way. Remark 1.1. We emphasize that the question really depends on the choice of the distance d, since the shape of the balls B depends on d. For instance, for any symmetric probability n measure µ on Γ whose support is ﬁnite and generates Γ, there exists a distance d (called ∗ the Green distance, see [BHM11]) for which the measures ρ and µ n behave in the same n way. A famous open problem (to which our methods do not apply) is to understand what H happens when Γ acts cocompactly on the hyperbolic space k, and the distance d is given · H by d(e, γ) = dH (O, γ O) where O is a base point in k. In this case, it is also expected k that the two methods are always diﬀerent. Here are the main partial results in this context: (1) The two methods are diﬀerent for some symmetric measures with ﬁnite support ([LP07], see also Theorem 5.9 below). (2) If, instead of a cocompact lattice, one considers a lattice with cusps, the two methods are always diﬀerent [GLJ93]. (3) If, instead of a lattice, one considers a nice dense subgroup, there exist symmetric measures with ﬁnite support for which the two methods are equivalent [Bou12]. This question also makes sense in continuous time, for negatively curved manifolds. A conjecture of Sullivan asserts that, in this setting, the two methods coincide if and only if the manifold is locally symmetric, see [Led95]. One can give several meanings to the question “are the two methods equivalent?” Let us ∗ ﬁrst discuss an interpretation in terms of behavior at inﬁnity. The measures µ n converge in ∪ the geometric compactiﬁcation Γ ∂Γ to a measure µ∞, supported on the boundary, called the exit measure of the random walk, or its stationary measure. Geometrically, the random walk (X ) (cid:62) converges almost surely to a random point on the boundary ∂Γ, the measure n n 1 µ∞ is its distribution. On the other hand, let ρ∞ be the Patterson-Sullivan measure on ∂Γ associated to the distance d, constructed in [Coo93] in this context. One should think of it as the uniform measure on the boundary (it is equivalent to the Hausdorﬀ measure of maximal dimension on the boundary, for any visual distance coming from d). The measures ρ do not always converge to ρ∞, but all their limit points are equivalent to ρ∞, with a n density bounded from above and from below (this follows from the arguments of [Coo93], see Lemma 2.13 below). A version of the question is then to ask if the measures µ∞ and ρ∞ are mutually singular: in this case, the random walk mainly visits parts of the groups that are not important from the point of view of the uniform measure. Another version of the same question is quantitative: Does the random walk visit parts of the groups that are exponentially negligible from the point of view of the uniform measure? This is made precise through(cid:88)the notions of drift a(cid:88)nd entropy. Deﬁne | | − (1.1) L(µ) = µ(g) g , H(µ) = µ(g)( log µ(g)), ∈ ∈ g Γ g Γ | | where g = d(e, g). The quantity L(µ) is the average distance of an element to the identity. The quantity H(µ), called the time one entropy of µ, is the average logarithmic

text: ENTROPY

text: AND

text: DRIFT

text: IN

text: WORD

text: HYPERBOLIC

text: GROUPS

text: that

text: the

text: methods

text: always

text: diﬀer.

text: Our

text: main

text: result

text: conﬁrms

text: this

text: intuition

text: in

text: a

text: special

text: class

text: of

text: groups:

text: In

text: hyperbolic

text: groups

text: which

text: are

text: not

text: virtually

text: free

text: (i.e.,

text: there

text: is

text: no

text: ﬁnite

text: index

text: free

text: subgroup),

text: if

text: d

text: is

text: a

text: word

text: distance,

text: the

text: two

text: methods

text: are

text: always

text: diﬀerent,

text: in

text: a

text: precise

text: quantitative

text: way.

text: Remark

text: We

text: emphasize

text: that

text: the

text: question

text: really

text: depends

text: on

text: the

text: choice

text: of

text: the

text: distance

text: d,

text: since

text: the

text: shape

text: of

text: the

text: balls

text: B

text: depends

text: on

text: d.

text: For

text: instance,

text: for

text: any

text: symmetric

text: probability

text: n

text: measure

text: µ

text: on

text: Γ

text: whose

text: support

text: is

text: ﬁnite

text: and

text: generates

text: Γ,

text: there

text: exists

text: a

text: distance

text: d

text: (called

text: the

text: Green

text: distance,

text: see

text: for

text: which

text: the

text: measures

text: ρ

text: and

text: µ

text: n

text: behave

text: in

text: the

text: same

text: n

text: way.

text: A

text: famous

text: open

text: problem

text: (to

text: which

text: our

text: methods

text: do

text: not

text: apply)

text: is

text: to

text: understand

text: what

text: H

text: happens

text: when

text: Γ

text: acts

text: cocompactly

text: on

text: the

text: hyperbolic

text: space

text: k,

text: and

text: the

text: distance

text: d

text: is

text: given

text: H

text: by

text: d(e,

text: γ)

text: dH

text: (O,

text: γ

text: O)

text: where

text: O

text: is

text: a

text: base

text: point

text: in

text: k.

text: In

text: this

text: case,

text: it

text: is

text: also

text: expected

text: k

text: that

text: the

text: two

text: methods

text: are

text: always

text: diﬀerent.

text: Here

text: are

text: the

text: main

text: partial

text: results

text: in

text: this

text: context:

text: The

text: two

text: methods

text: are

text: diﬀerent

text: for

text: some

text: symmetric

text: measures

text: with

text: ﬁnite

text: support

text: see

text: also

text: Theorem

text: below).

text: If,

text: instead

text: of

text: a

text: cocompact

text: lattice,

text: one

text: considers

text: a

text: lattice

text: with

text: cusps,

text: the

text: two

text: methods

text: are

text: always

text: diﬀerent

text: If,

text: instead

text: of

text: a

text: lattice,

text: one

text: considers

text: a

text: nice

text: dense

text: subgroup,

text: there

text: exist

text: symmetric

text: measures

text: with

text: ﬁnite

text: support

text: for

text: which

text: the

text: two

text: methods

text: are

text: equivalent

text: This

text: question

text: also

text: makes

text: sense

text: in

text: continuous

text: time,

text: for

text: negatively

text: curved

text: manifolds.

text: A

text: conjecture

text: of

text: Sullivan

text: asserts

text: that,

text: in

text: this

text: setting,

text: the

text: two

text: methods

text: coincide

text: if

text: and

text: only

text: if

text: the

text: manifold

text: is

text: locally

text: symmetric,

text: see

text: One

text: can

text: give

text: several

text: meanings

text: to

text: the

text: question

text: “are

text: the

text: two

text: methods

text: equivalent?”

text: Let

text: us

text: ﬁrst

text: discuss

text: an

text: interpretation

text: in

text: terms

text: of

text: behavior

text: at

text: inﬁnity.

text: The

text: measures

text: µ

text: n

text: converge

text: in

text: the

text: geometric

text: compactiﬁcation

text: Γ

text: ∂Γ

text: to

text: a

text: measure

text: µ∞,

text: supported

text: on

text: the

text: boundary,

text: called

text: the

text: exit

text: measure

text: of

text: the

text: random

text: walk,

text: or

text: its

text: stationary

text: measure.

text: Geometrically,

text: the

text: random

text: walk

text: (X

text: converges

text: almost

text: surely

text: to

text: a

text: random

text: point

text: on

text: the

text: boundary

text: ∂Γ,

text: the

text: measure

text: n

text: n

text: µ∞

text: is

text: its

text: distribution.

text: On

text: the

text: other

text: hand,

text: let

text: ρ∞

text: be

text: the

text: Patterson-Sullivan

text: measure

text: on

text: ∂Γ

text: associated

text: to

text: the

text: distance

text: d,

text: constructed

text: in

text: in

text: this

text: context.

text: One

text: should

text: think

text: of

text: it

text: as

text: the

text: uniform

text: measure

text: on

text: the

text: boundary

text: (it

text: is

text: equivalent

text: to

text: the

text: Hausdorﬀ

text: measure

text: of

text: maximal

text: dimension

text: on

text: the

text: boundary,

text: for

text: any

text: visual

text: distance

text: coming

text: from

text: d).

text: The

text: measures

text: ρ

text: do

text: not

text: always

text: converge

text: to

text: ρ∞,

text: but

text: all

text: their

text: limit

text: points

text: are

text: equivalent

text: to

text: ρ∞,

text: with

text: a

text: n

text: density

text: bounded

text: from

text: above

text: and

text: from

text: below

text: (this

text: follows

text: from

text: the

text: arguments

text: of

text: see

text: Lemma

text: below).

text: A

text: version

text: of

text: the

text: question

text: is

text: then

text: to

text: ask

text: if

text: the

text: measures

text: µ∞

text: and

text: ρ∞

text: are

text: mutually

text: singular:

text: in

text: this

text: case,

text: the

text: random

text: walk

text: mainly

text: visits

text: parts

text: of

text: the

text: groups

text: that

text: are

text: not

text: important

text: from

text: the

text: point

text: of

text: view

text: of

text: the

text: uniform

text: measure.

text: Another

text: version

text: of

text: the

text: same

text: question

text: is

text: quantitative:

text: Does

text: the

text: random

text: walk

text: visit

text: parts

text: of

text: the

text: groups

text: that

text: are

text: exponentially

text: negligible

text: from

text: the

text: point

text: of

text: view

text: of

text: the

text: uniform

text: measure?

text: This

text: is

text: made

text: precise

text: notions

text: of

text: drift

text: entropy.

text: Deﬁne

text: L(µ)

text: µ(g)

text: g

text: H(µ)

text: µ(g)(

text: log

text: µ(g)),

text: g

text: Γ

text: g

text: Γ

text: where

text: g

text: d(e,

text: g).

text: The

text: quantity

text: L(µ)

text: is

text: the

text: average

text: distance

text: of

text: an

text: element

text: to

text: the

text: identity.

text: The

text: quantity

text: H(µ),

text: called

text: the

text: time

text: one

text: entropy

text: of

text: µ,

text: is

text: the

text: average

text: logarithmic


text: ENTROPY AND DRIFT IN WORD HYPERBOLIC GROUPS 30 Proof. The example is the same as in [Pei03], but his geometric proofs are replaced by combinatorial arguments based on generating series. Let G be a ﬁnitely generated non-quasi-convex subgroup of a hyperbolic group G˜ (take for instance for G˜ the fundamental group of a hyperbolic 3-manifold which ﬁbers over the F circle, and for G the fundamental group of the ﬁber of this ﬁbration). Let H = , with k (cid:62) ∗ ⊂ ∗ k large enough so that v v . We take Λ = G H Γ = G˜ H. It is not quasi-convex, H G because of the factor G. Writing v for its growth, we claim that, for some c > 0, Λ |S ∩ | ∼ (4.6) n Λ cenvΛ. (cid:80) We compute with generating series. Let F (z) be the growth series for G, given by |S ∩ | G F (z) = (cid:62) n G zn. Likewise, we deﬁne F and F . Since any word in Λ has a G n 0 H Λ canonical decomposition in terms of words in G and H, a classical computation (see [dlH00, Prop. VI.A.4]) gives F F (4.7) F = − −G H − . Λ 1 (F 1)(F 1) G H − (cid:62) − Let zG = ∞e vG zH = e vH be the convergence radii of FG and FH. At zH, we have F (z ) = + , since the cardinality of spheres in the free group is exactly of the order of H H − − envH. When z increases to zH, the function (FG(z) 1)(FH(z) 1) tak−es the value 1, at a number z = zΛ. Since this is the ﬁrst singularity of FΛ, we have zΛ = e vΛ. M−oreover,−the function F is meromorphic at z , with a pole of order 1 (since the function (F 1)(F 1) Λ Λ G H has positive derivative, being a power series with nonnegative coeﬃcients). It follows from a simple tauberian theorem (see, for instance, [FS09, Theorem IV.10]) that the coeﬃcients − of F behave like cz n, proving (4.6). Λ Λ ∈ Let us estimate the number of non-quasi-convex points in Λ. Consider a word w Λ of length n, for instance starting with a factor in G and ending with a factor in H. It can be · · · (cid:80) written as g h g h h . Along a geodesic from e to w, all the words g h (with h preﬁx 1 1 2 2 s (cid:80) (cid:80) 1 of h ) belong to Λ. So do all the words g h g h with h preﬁx of h , and so on. Therefore, 1 1 1 2 2 | | the pr(cid:80)oport\ion of ti(cid:80)me that the |geo| d(cid:62)esic −spends outsid|e o|f(cid:54)Λ is at(cid:80)most (cid:80)gi (cid:54)/n. Such a point in Λ Λ satisﬁes g (1 ε)n and h εn. Assuming ε 1/2, this QC(ε,0) i i | | (cid:54) | | | |− − | | (cid:62) gives |S h∩i \(ε/2) |gi . In particular, for any α > 0, we have eα( gi 2ε 1 hi ) 1. Let u = n Λ Λ , its generating series satisﬁes the following equation (where we only n QC(ε,0) wr(cid:88)ite in details(cid:88)the word(cid:88)s starting with G and ending in H, the other ones being completely (cid:80) (cid:80) analogous): u zn (cid:54) (cid:88)(cid:2) eα( ai−2ε−1 bi)|S(cid:3)a1 ∩ G||Sb1 ∩ H| · · · |Sb(cid:96) ∩ H|zn + . . . n (cid:62) ··· (cid:96) 1 a1+b1+a2+ +b(cid:96)=n − − − − = (F (eαz) 1)(F (e 2αε 1z) 1) (cid:96) + . . . G H (cid:62) (cid:96) 1 − − F (eαz)F (e 2αε 1z) G H = − − − − − . 1 (F (eαz) 1)(F (e 2αε 1z) 1) G H ##LTLine## ##LTLine##

text: ENTROPY

label: paragraph

text: AND

text: DRIFT

text: IN

text: WORD

text: HYPERBOLIC

text: GROUPS

text: Proof.

text: The

text: example

text: is

text: the

text: same

text: as

text: in

text: but

text: his

text: geometric

text: proofs

text: are

text: replaced

text: by

text: combinatorial

text: arguments

text: based

text: on

text: generating

text: series.

text: Let

text: G

text: be

text: a

text: ﬁnitely

text: generated

text: non-quasi-convex

text: subgroup

text: of

text: a

text: hyperbolic

text: group

text: G˜

text: (take

text: for

text: instance

text: for

text: G˜

text: the

text: fundamental

text: group

text: of

text: a

text: hyperbolic

text: which

text: ﬁbers

text: over

text: the

text: F

text: circle,

text: and

text: for

text: G

text: the

text: fundamental

text: group

text: of

text: the

text: ﬁber

text: of

text: this

text: ﬁbration).

text: Let

text: H

text: with

text: k

text: k

text: large

text: enough

text: so

text: that

text: v

text: v

text: We

text: take

text: Λ

text: G

text: H

text: Γ

text: G˜

text: H.

text: It

text: is

text: not

text: quasi-convex,

text: H

text: G

text: because

text: of

text: the

text: factor

text: G.

text: Writing

text: v

text: for

text: its

text: growth,

text: we

text: claim

text: that,

text: for

text: some

text: c

text: Λ

text: |S

text: n

text: Λ

text: cenvΛ.

text: We

text: compute

text: with

text: generating

text: series.

text: Let

text: F

text: (z)

text: be

text: the

text: growth

text: series

text: for

text: G,

text: given

text: by

text: |S

text: G

text: F

text: (z)

text: n

text: G

text: zn.

text: Likewise,

text: we

text: deﬁne

text: F

text: and

text: F

text: Since

text: any

text: word

text: in

text: Λ

text: has

text: a

text: G

text: n

text: H

text: Λ

text: canonical

text: decomposition

text: in

text: terms

text: of

text: words

text: in

text: G

text: and

text: H,

text: a

text: classical

text: computation

text: (see

text: Prop.

text: gives

text: F

text: F

text: F

text: −G

text: H

text: Λ

text: (F

text: G

text: H

text: Let

text: zG

text: ∞e

text: vG

text: zH

text: e

text: vH

text: be

text: the

text: convergence

text: radii

text: of

text: FG

text: and

text: FH.

text: At

text: zH,

text: we

text: have

text: F

text: (z

text: since

text: the

text: cardinality

text: of

text: spheres

text: in

text: the

text: free

text: group

text: is

text: exactly

text: of

text: the

text: order

text: of

text: H

text: H

text: envH.

text: When

text: z

text: increases

text: to

text: zH,

text: the

text: function

text: (FG(z)

text: tak−es

text: the

text: value

text: at

text: a

text: number

text: z

text: zΛ.

text: Since

text: this

text: is

text: the

text: ﬁrst

text: singularity

text: of

text: FΛ,

text: we

text: have

text: zΛ

text: e

text: vΛ.

text: M−oreover,−the

text: function

text: F

text: is

text: meromorphic

text: at

text: z

text: with

text: a

text: pole

text: of

text: order

text: (since

text: the

text: function

text: (F

text: Λ

text: Λ

text: G

text: H

text: has

text: positive

text: derivative,

text: being

text: a

text: power

text: series

text: with

text: nonnegative

text: coeﬃcients).

text: It

text: follows

text: from

text: a

text: simple

text: tauberian

text: theorem

text: (see,

text: for

text: instance,

text: Theorem

text: that

text: the

text: coeﬃcients

text: of

text: F

text: behave

text: like

text: cz

text: n,

text: proving

text: Λ

text: Λ

text: Let

text: us

text: estimate

text: the

text: number

text: of

text: non-quasi-convex

text: points

text: in

text: Λ.

text: Consider

text: a

text: word

text: w

text: Λ

text: of

text: length

text: n,

text: for

text: instance

text: starting

text: with

text: a

text: factor

text: in

text: G

text: and

text: ending

text: with

text: a

text: factor

text: in

text: H.

text: It

text: can

text: be

text: written

text: as

text: g

text: h

text: g

text: h

text: h

text: Along

text: a

text: geodesic

text: from

text: e

text: to

text: w,

text: all

text: the

text: words

text: g

text: h

text: (with

text: h

text: preﬁx

text: s

text: of

text: h

text: belong

text: to

text: Λ.

text: So

text: do

text: all

text: the

text: words

text: g

text: h

text: g

text: h

text: with

text: h

text: preﬁx

text: of

text: h

text: and

text: so

text: on.

text: Therefore,

text: the

text: of

text: that

text: the

text: |geo|

text: −spends

text: outsid|e

text: is

text: Such

text: a

text: point

text: in

text: Λ

text: Λ

text: satisﬁes

text: g

text: ε)n

text: and

text: h

text: εn.

text: Assuming

text: ε

text: this

text: i

text: i

text: gives

text: |S

text: h∩i

text: |gi

text: In

text: particular,

text: for

text: any

text: α

text: we

text: have

text: eα(

text: gi

text: 2ε

text: hi

text: Let

text: u

text: n

text: Λ

text: Λ

text: its

text: generating

text: series

text: satisﬁes

text: the

text: following

text: equation

text: (where

text: we

text: only

text: n

text: in

text: starting

text: with

text: G

text: and

text: ending

text: in

text: H,

text: the

text: other

text: ones

text: being

text: completely

text: analogous):

text: u

text: zn

text: eα(

text: H|

text: H|zn

text: n

text: (F

text: (eαz)

text: (e

text: 2αε

text: G

text: H

text: F

text: (eαz)F

text: (e

text: 2αε

text: G

text: H

text: (F

text: (eαz)

text: (e

text: 2αε

text: G

text: H

text: ##LTLine##

text: ##LTLine##


text: ENTROPY AND DRIFT IN WORD HYPERBOLIC GROUPS 32 · · · The random walk at time n is given by X = g g , where g are independent and n 1 · · ·n i distributed like µ. We will show that most products g g (which belong to Λ) are within 1 i distance M of a geodesic from e to X (this amounts to the classical fact that trajectories n of the random walk follow geodesics in the group), and moreover that they approximate a ∈ proportion at least ε of the points on this geodesic. This will give X Λ as desired. n QC(ε,M) The second point is more delicate: we should for instance exclude the situation where, given a geodesic γ, one has X = γ(a(n)) where a(n) is the smallest square larger than n. In this n case, X follows the geodesic γ at linear speed, but nevertheless the proportion of γ it visits n tends to 0. This behavior will be excluded thanks to the fact that, with high probability, the jumps of the random walk are bounded. The argument is probabilistic and formulated in terms of the bilateral version of the Z P ⊗Z random walk. On Ω = Γ with the product measure = µ , let g be the n-th coordinate. n The g are independent, identically distributed, and correspond to the increments of a n − random walk (X ) ∈Z with X = e and X 1X = g . Almost surely, X converges → ±∞ n n 0 n n±+∈1 n+1 (cid:54) − n when n towards two random variables ξ ∂Γ, with ξ+ = ξ almost surely since these random variables are independent and atomless. Following Kaimanovich [Kai00], − − denote by S(ξ , ξ+) the union of all the geodesics from ξ to ξ+. Let π be the projection − − on S(ξ , ξ+), i.e., π(g) is the closest point to g on S(ξ , ξ+). It is not uniquely deﬁned, but two possible choices are within distance C , for some C only depending on Γ. 0 0 Let us choose L > 0 large enough (how large will only depend on the hyperbolicity constant of the space). Any measurable function is bounded on sets with arbitrarily large measure. Hence, there exists K > 0 such that, with probability at least 9/10, | | (cid:62) (1) For every k K, the projections π(X ) are distant from π(X ) by at least L (and −k 0 they are closer to ξ+ if k > 0, and to ξ if k < 0). − (cid:54) (2) We have d(e, S(ξ , ξ+)) K. ∈ Z As everything is equivariant, we deduce that, for all i , the point X satisﬁes the same i properties with probability at least 9/10, i.e., − (cid:54) | | (cid:62) (cid:62) (4.8) d(X , S(ξ , ξ+)) K and, for all k K, d(π(X ), π(X )) L. i i i+k (cid:98) (cid:99) (cid:54) Let n be a large integer. Write m = n/K . Among the integers K, 2K, . . . , mK n, we E | | (cid:62) · consider the set I (ω) of those i such that X satisﬁes (4.8). We have ( I ) m 9/10. | | (cid:54) n i n As I m, we get n 9m (cid:54) E | | (cid:54) m P | | P | | (cid:62) m 9mP | | (cid:62) ( I ) ( I < m/10) + m ( I m/10) = + ( I m/10). n n n n 10 10 10 10 P | | (cid:62) (cid:62) This gives ( I m/10) 8/9. Let η = 1/(20K). Let Ω be the set of ω such that | | (cid:62) n (cid:54) n I (ω) ηn + 1, and X and X satisfy (4.8), and d(X , e) 2(cid:96)n (where (cid:96) is the drift of µ). n P (cid:62) 0 n n It satisﬁes (Ω ) 1/2 if n is large enough. This is the set of good trajectories for which n we can control the position of many of the X . ∈ i Let ω Ω . We write Y for a projection of X on a geodesic γ from e to X . Let \ { n} i i n I˜ = I mK , so that the elements of I˜ are at distance at least K of 0 and n. As X and n n n ∈ 0 X satisfy (4.8), the projections π(X ) for i I˜ are located between π(X ) and π(X ), and n i n 0 n are at a distance at least L of these points (see Figure 1). If L is large enough, we obtain ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: ENTROPY

text: AND

text: DRIFT

text: IN

text: WORD

text: HYPERBOLIC

text: GROUPS

text: The

text: random

text: walk

text: at

text: time

text: n

text: is

text: given

text: by

text: X

text: g

text: g

text: where

text: g

text: are

text: independent

text: and

text: n

text: ·n

text: i

text: distributed

text: like

text: µ.

text: We

text: will

text: show

text: that

text: most

text: products

text: g

text: g

text: (which

text: belong

text: to

text: Λ)

text: are

text: within

text: i

text: distance

text: M

text: of

text: a

text: geodesic

text: from

text: e

text: to

text: X

text: (this

text: amounts

text: to

text: the

text: classical

text: fact

text: that

text: trajectories

text: n

text: of

text: the

text: random

text: walk

text: follow

text: geodesics

text: in

text: the

text: group),

text: and

text: moreover

text: that

text: they

text: approximate

text: a

text: proportion

text: at

text: least

text: ε

text: of

text: the

text: points

text: on

text: this

text: geodesic.

text: This

text: will

text: give

text: X

text: Λ

text: as

text: desired.

text: n

text: QC(ε,M)

text: The

text: second

text: point

text: is

text: more

text: delicate:

text: we

text: should

text: for

text: instance

text: exclude

text: the

text: situation

text: where,

text: given

text: a

text: geodesic

text: γ,

text: one

text: has

text: X

text: γ(a(n))

text: where

text: a(n)

text: is

text: the

text: smallest

text: square

text: larger

text: than

text: n.

text: In

text: this

text: n

text: case,

text: X

text: follows

text: the

text: geodesic

text: γ

text: at

text: linear

text: speed,

text: but

text: nevertheless

text: the

text: proportion

text: of

text: γ

text: it

text: visits

text: n

text: tends

text: to

text: This

text: behavior

text: will

text: be

text: excluded

text: thanks

text: to

text: the

text: fact

text: that,

text: with

text: high

text: probability,

text: the

text: jumps

text: of

text: the

text: random

text: walk

text: are

text: bounded.

text: The

text: argument

text: is

text: probabilistic

text: and

text: formulated

text: in

text: terms

text: of

text: the

text: bilateral

text: version

text: of

text: the

text: Z

text: P

text: ⊗Z

text: random

text: walk.

text: On

text: Ω

text: Γ

text: with

text: the

text: product

text: measure

text: µ

text: let

text: g

text: be

text: the

text: n-th

text: coordinate.

text: n

text: The

text: g

text: are

text: independent,

text: identically

text: distributed,

text: and

text: correspond

text: to

text: the

text: increments

text: of

text: a

text: n

text: random

text: walk

text: (X

text: ∈Z

text: with

text: X

text: e

text: and

text: X

text: g

text: Almost

text: surely,

text: X

text: converges

text: n

text: n

text: n

text: n

text: when

text: n

text: towards

text: two

text: random

text: variables

text: ξ

text: ∂Γ,

text: with

text: ξ+

text: ξ

text: almost

text: surely

text: since

text: these

text: random

text: variables

text: are

text: independent

text: and

text: atomless.

text: Following

text: Kaimanovich

text: denote

text: by

text: S(ξ

text: ξ+)

text: the

text: union

text: of

text: all

text: the

text: geodesics

text: from

text: ξ

text: to

text: ξ+.

text: Let

text: π

text: be

text: the

text: projection

text: on

text: S(ξ

text: ξ+),

text: i.e.,

text: π(g)

text: is

text: the

text: closest

text: point

text: to

text: g

text: on

text: S(ξ

text: ξ+).

text: It

text: is

text: not

text: uniquely

text: deﬁned,

text: but

text: two

text: possible

text: choices

text: are

text: within

text: distance

text: C

text: for

text: some

text: C

text: only

text: depending

text: on

text: Γ.

text: Let

text: us

text: choose

text: L

text: large

text: enough

text: (how

text: large

text: will

text: only

text: depend

text: on

text: the

text: hyperbolicity

text: constant

text: of

text: the

text: space).

text: Any

text: measurable

text: function

text: is

text: bounded

text: on

text: sets

text: with

text: arbitrarily

text: large

text: measure.

text: Hence,

text: there

text: exists

text: K

text: such

text: that,

text: with

text: probability

text: at

text: least

text: For

text: every

text: k

text: K,

text: the

text: projections

text: π(X

text: are

text: distant

text: from

text: π(X

text: by

text: at

text: least

text: L

text: (and

text: −k

text: they

text: are

text: closer

text: to

text: ξ+

text: if

text: k

text: and

text: to

text: ξ

text: if

text: k

text: We

text: have

text: d(e,

text: S(ξ

text: ξ+))

text: K.

text: Z

text: As

text: everything

text: is

text: equivariant,

text: we

text: deduce

text: that,

text: for

text: all

text: i

text: the

text: point

text: X

text: satisﬁes

text: the

text: same

text: i

text: properties

text: with

text: probability

text: at

text: least

text: i.e.,

text: d(X

text: S(ξ

text: ξ+))

text: K

text: and,

text: for

text: all

text: k

text: K,

text: d(π(X

text: π(X

text: L.

text: i

text: i

text: i+k

text: Let

text: n

text: be

text: a

text: large

text: integer.

text: Write

text: m

text: n/K

text: Among

text: the

text: integers

text: K,

text: mK

text: n,

text: we

text: E

text: consider

text: the

text: set

text: I

text: (ω)

text: of

text: those

text: i

text: such

text: that

text: X

text: satisﬁes

text: We

text: have

text: I

text: m

text: n

text: i

text: n

text: As

text: I

text: m,

text: we

text: get

text: n

text: E

text: m

text: P

text: P

text: m

text: I

text: I

text: m

text: I

text: I

text: n

text: n

text: n

text: n

text: P

text: This

text: gives

text: I

text: Let

text: η

text: Let

text: Ω

text: be

text: the

text: set

text: of

text: ω

text: such

text: that

text: n

text: n

text: I

text: (ω)

text: ηn

text: and

text: X

text: and

text: X

text: satisfy

text: and

text: d(X

text: e)

text: (where

text: is

text: the

text: drift

text: of

text: µ).

text: n

text: P

text: n

text: n

text: It

text: satisﬁes

text: (Ω

text: if

text: n

text: is

text: large

text: enough.

text: This

text: is

text: the

text: set

text: of

text: good

text: trajectories

text: for

text: which

text: n

text: we

text: can

text: control

text: the

text: position

text: of

text: many

text: of

text: the

text: X

text: i

text: Let

text: ω

text: Ω

text: We

text: write

text: Y

text: for

text: a

text: projection

text: of

text: X

text: on

text: a

text: geodesic

text: γ

text: from

text: e

text: to

text: X

text: Let

text: n}

text: i

text: i

text: n

text: I˜

text: I

text: mK

text: so

text: that

text: the

text: elements

text: of

text: I˜

text: are

text: at

text: distance

text: at

text: least

text: K

text: of

text: and

text: n.

text: As

text: X

text: and

text: n

text: n

text: n

text: X

text: satisfy

text: the

text: projections

text: π(X

text: for

text: i

text: I˜

text: are

text: located

text: between

text: π(X

text: and

text: π(X

text: and

text: n

text: i

text: n

text: n

text: are

text: at

text: a

text: distance

text: at

text: least

text: L

text: of

text: these

text: points

text: (see

text: Figure

text: If

text: L

text: is

text: large

text: enough,

text: we

text: obtain

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ENTROPY AND DRIFT IN WORD HYPERBOLIC GROUPS 36 The previous lemma shows that we should understand λ . We deﬁne an auxiliary proba- ∗ ε bility measure α˜ so that λ = α˜ β , by ε ε ε ε (cid:88) ∞ − ∗ (5.1) α˜ = (1 ε)nεα n. ε ε n=0 In this formula, most weight is concentrated around those n of the order of 1/ε. Hence, we have to understand the iterates of α in time 1/ε. When Γ is ﬁnite, we will see that it ε s has enough time to equidistribute on Γ (even though α may give a very small weight to s ε some elements, this weight is by construction much larger than ε, so that 1/ε iterates are enough to equidistribute). When Γ is virtually cyclic, we will see that the random walk s has enough time to drift away signiﬁcantly from the identity. In both cases, we will need quantitative results on basic groups, but in weakly elliptic cases (i.e., the transition probabilities are not bounded from below). There are techniques to get quantitative estimates in such settings, especially comparison techniques (due for instance to Varopoulos, Diaconis, Saloﬀ-Coste): one can compare weakly elliptic walks to elliptic ones (which we understand well) thanks to Dirichlet forms arguments: these arguments make it possible to transfer results from the latter to the former (modulo some loss in the constants, due to the lack of ellipticity). We will rely on such results when Γ is inﬁnite. When it is s ﬁnite, such techniques can also be used, but we will rather give a more elementary argument. We start with the case where Γ is ﬁnite. We need to quantify the speed of convergence s to the stationary measure in ﬁnite groups, with the following lemma. Lemma 5.2. Let Λ be a ﬁnite group. Let Σ(cid:0)(cid:80)⊂ Λ be a generat(cid:1)ing subset (it does not have Λ to be symmetric). Let π be the uniform measure on Λ, and let d(µ, π ) be the euclidean Λ Λ − distance between a measure µ and π (i.e., (µ(g) π (g))2 1/2). For any δ > 0, there Λ Λ exists K > 0 with the following property. Let η > 0. Consider a probability measure µ on Λ (cid:62) ∈ ∪ { } with µ(σ) η for any σ Σ e . Then, for all n > K/η, Λ ∗ (cid:54) d(µ n, π ) δ. Λ In other words, the time to see the equidistribution towards the stationary measure is bounded by 1/η, where η is the minimum of the transition probabilities on Σ . Λ (cid:80) (cid:80) M Proof. Endow the space (Λ) of signed measures on Λ with the scalar product corresponding | | { } ⊥ to the quadratic form ν 2 = ν(g)2. Denote by H = ν : ν(g) = 0 the hyperplane π (cid:80) Λ of zero mass measures. For any probability ρ, denote by M the left-convolution operator on M ∗ ρ (Λ), that is M (ν) = ρ ν. Since convolution preserves mass, H is M -invariant. Let us ρ ρ prove that the operator norm of M is bounded by 1. Indeed, put u (g) = ∈ ρ(h)ρ(hg), ρ ρ h Λ

text: ENTROPY

text: AND

text: DRIFT

text: IN

text: WORD

text: HYPERBOLIC

text: GROUPS

text: The

text: previous

text: lemma

text: shows

text: that

text: we

text: should

text: understand

text: λ

text: We

text: deﬁne

text: an

text: auxiliary

text: proba-

text: ε

text: bility

text: measure

text: α˜

text: so

text: that

text: λ

text: α˜

text: β

text: by

text: ε

text: ε

text: ε

text: ε

label: equation

text: α˜

text: ε)nεα

text: n.

text: ε

text: ε

text: In

text: this

text: formula,

text: most

text: weight

text: is

text: concentrated

text: around

text: those

text: n

text: of

text: the

text: order

text: of

text: Hence,

text: we

text: have

text: to

text: understand

text: the

text: iterates

text: of

text: α

text: in

text: time

text: When

text: Γ

text: is

text: ﬁnite,

text: we

text: will

text: see

text: that

text: it

text: ε

text: s

text: has

text: enough

text: time

text: to

text: equidistribute

text: on

text: Γ

text: (even

text: though

text: α

text: may

text: give

text: a

text: very

text: small

text: weight

text: to

text: s

text: ε

text: some

text: elements,

text: this

text: weight

text: is

text: by

text: construction

text: much

text: larger

text: than

text: ε,

text: so

text: that

text: iterates

text: are

text: enough

text: to

text: equidistribute).

text: When

text: Γ

text: is

text: virtually

text: cyclic,

text: we

text: will

text: see

text: that

text: the

text: random

text: walk

text: s

text: has

text: enough

text: time

text: to

text: drift

text: away

text: signiﬁcantly

text: from

text: the

text: identity.

text: In

text: both

text: cases,

text: we

text: will

text: need

text: quantitative

text: results

text: on

text: basic

text: groups,

text: but

text: in

text: weakly

text: elliptic

text: cases

text: (i.e.,

text: the

text: transition

text: probabilities

text: are

text: not

text: bounded

text: from

text: below).

text: There

text: are

text: techniques

text: to

text: get

text: quantitative

text: estimates

text: in

text: such

text: settings,

text: especially

text: comparison

text: techniques

text: (due

text: for

text: instance

text: to

text: Varopoulos,

text: Diaconis,

text: Saloﬀ-Coste):

text: one

text: can

text: compare

text: weakly

text: elliptic

text: walks

text: to

text: elliptic

text: ones

text: (which

text: we

text: understand

text: well)

text: thanks

text: to

text: Dirichlet

text: forms

text: arguments:

text: these

text: arguments

text: make

text: it

text: possible

text: to

text: transfer

text: results

text: from

text: the

text: latter

text: to

text: the

text: former

text: (modulo

text: some

text: loss

text: in

text: the

text: constants,

text: due

text: to

text: the

text: lack

text: of

text: ellipticity).

text: We

text: will

text: rely

text: on

text: such

text: results

text: when

text: Γ

text: is

text: inﬁnite.

text: When

text: it

text: is

text: s

text: ﬁnite,

text: such

text: techniques

text: can

text: also

text: be

text: used,

text: but

text: we

text: will

text: rather

text: give

text: a

text: more

text: elementary

text: argument.

text: We

text: start

text: with

text: the

text: case

text: where

text: Γ

text: is

text: ﬁnite.

text: We

text: need

text: to

text: quantify

text: the

text: speed

text: of

text: convergence

text: s

text: to

text: the

text: stationary

text: measure

text: in

text: ﬁnite

text: groups,

text: with

text: the

text: following

text: lemma.

text: Lemma

text: Let

text: Λ

text: be

text: a

text: ﬁnite

text: group.

text: Let

text: Λ

text: be

text: a

text: subset

text: (it

text: does

text: not

text: have

text: Λ

text: to

text: be

text: symmetric).

text: Let

text: π

text: be

text: the

text: uniform

text: measure

text: on

text: Λ,

text: and

text: let

text: d(µ,

text: π

text: be

text: the

text: euclidean

text: Λ

text: Λ

text: distance

text: between

text: a

text: measure

text: µ

text: and

text: π

text: (i.e.,

text: (µ(g)

text: π

text: For

text: any

text: δ

text: there

text: Λ

text: Λ

text: exists

text: K

text: with

text: the

text: following

text: property.

text: Let

text: η

text: Consider

text: a

text: probability

text: measure

text: µ

text: on

text: Λ

text: with

text: µ(σ)

text: η

text: for

text: any

text: σ

text: Σ

text: e

text: Then,

text: for

text: all

text: n

text: K/η,

text: Λ

text: d(µ

text: n,

text: π

text: δ.

text: Λ

text: In

text: other

text: words,

text: the

text: time

text: to

text: see

text: the

text: equidistribution

text: towards

text: the

text: stationary

text: measure

text: is

text: bounded

text: by

text: where

text: η

text: is

text: the

text: minimum

text: of

text: the

text: transition

text: probabilities

text: on

text: Σ

text: Λ

text: M

text: Proof.

text: Endow

text: the

text: space

text: (Λ)

text: of

text: signed

text: measures

text: on

text: Λ

text: with

text: the

text: scalar

text: product

text: corresponding

text: to

text: the

text: quadratic

text: form

text: ν

text: Denote

text: by

text: H

text: ν

text: ν(g)

text: the

text: hyperplane

text: π

text: Λ

text: of

text: zero

text: mass

text: measures.

text: For

text: any

text: probability

text: ρ,

text: denote

text: by

text: M

text: the

text: left-convolution

text: operator

text: on

text: M

text: ρ

text: (Λ),

text: that

text: is

text: M

text: (ν)

text: ρ

text: ν.

text: Since

text: convolution

text: preserves

text: mass,

text: H

text: is

text: M

text: -invariant.

text: Let

text: us

text: ρ

text: ρ

text: prove

text: that

text: the

text: operator

text: norm

text: of

text: M

text: is

text: bounded

text: by

text: Indeed,

text: put

text: u

text: (g)

text: ρ(h)ρ(hg),

text: ρ

text: ρ

text: h

text: Λ


text: ENTROPY AND DRIFT IN WORD HYPERBOLIC GROUPS 37 (cid:88) (cid:88) this is a probability on Λ. We have | | − − M ν 2 = (cid:88)(M ν(g))2 = ρ(gh 1)(cid:88)ρ(gh 1)ν(h )ν(h ) ρ ρ 1 2 1 2 ∈ ∈ g Λ (g,h1,h2) Λ3 − − = (cid:88) ν(h )ν(h )u (h h 1) = ν(h)ν(g 1h)u (g) 1 2 ρ 1 2 ρ ∈ ∈ (h1,h2) Λ2 (g,h) Λ2 (cid:54) | | | | ν 2u (g) = ν 2. ρ ∈ g Λ (cid:107) (cid:107) (cid:54) ∪ { } This proves that M 1. Now ﬁx ρ to be the uniform probability on the set Σ e . ρ ∈ ∪o { } Λ Notice that u (g) > 0 for any g Σ e , since ρ (e) > 0. We claim that M restricted ρo Λ o ρo∈ − { } to H has an operator norm c < 1. Would it be not the case, there would exist ν H 0 such that the previous inequalities would be equalities. Thanks to the equality case in the ∈ (cid:55)→ Cauchy-Schwarz inequality, this implies that, for any g Σ , the two measures h ν(h) (cid:55)→ − Λ and h ν(g 1h) are positively proportional. Since their norm are equal, they must be equal. Since Σ generates Λ, ν is Λ-invariant and belongs to H, so it must be zero. Λ By assumption, the probability µ can be decomposed as − µ = ηρ + (1 η)ν, o where ν is some probability. This implies that M restricted to H has operator norm at − µ most ηc + (1 η). Therefore, ∗ | ∗ − | | − | (cid:54) − − d(µ n, π ) = µ n π = Mn(δ π ) 2(1 (1 c)η)n. Λ Λ µ e Λ (cid:3) This inequality implies the result. We can now describe the asymptotic behavior of µ when the group Γ is ﬁnite. ε s ∗ Lemma 5.3. Assume that Γ is ﬁnite. Deﬁne a new probability measure λ = π β (it s ∼ Γs generates a non-elementary subgroup). When ε tends to 0, we have h(µ ) εh(λ) and ∼ ε (cid:96)(µ ) ε(cid:96)(λ). ε Proof. The random variable t , being geometric of parameter ε, is of the order of 1/ε with 1 P (cid:62) − high probability (i.e., for any δ > 0, there exists u > 0 such that (t > u/ε) 1 δ). { } 1 − − Writing Σ = a , . . . , a for the support of α , we have min ∈ α (σ) = (1 ε) 1µ (a ), s 1 s ε σ Σs ε ε s∗ which is much bigger than ε by deﬁnition of s. Lemma 5.2 shows that the measures α n (cid:62) ε are close to π for n u/ε. This implies that α˜ (deﬁned in (5.1)) converges to π when → Γs ε Γs ε 0. As β converges to β, this shows that λ converges to λ. ε ε The support of the measure λ contains Γ and a , . . . , a (as the support of β contains { } s s+1 r e, a , . . . , a by construction). Hence, Γ contains the non-elementary subgroup Γ . It s+1 r λ r follows that the entropy and the drift are continuous at λ, by Proposition 2.3 and Theorem 2.9. → → (cid:3) We get h(λ ) h(λ) and (cid:96)(λ ) (cid:96)(λ). With Lemma 5.1, this completes the proof. ε ε We deduce from the lemma that h(µ )/(cid:96)(µ ) tends to h(λ)/(cid:96)(λ). Hence, the measure ε ε µ = λ satisﬁes the conclusion of the theorem, at least in the non-symmetric case. In the Σ ∗ symmetric case, where we are looking for a symmetric measure µ , the measure λ = π β Σ Γs

text: ENTROPY

text: AND

text: DRIFT

text: IN

text: WORD

text: HYPERBOLIC

text: GROUPS

text: this

text: is

text: a

text: probability

text: on

text: Λ.

text: We

text: have

text: M

text: ν

text: ρ(gh

text: )ν(h

text: ρ

text: ρ

text: g

text: Λ

text: Λ3

text: ν(h

text: )ν(h

text: )u

text: (h

text: h

text: ν(h)ν(g

text: (g)

text: ρ

text: ρ

text: Λ2

text: (g,h)

text: Λ2

text: ν

text: (g)

text: ν

text: ρ

text: g

text: Λ

text: This

text: proves

text: that

text: M

text: Now

text: ﬁx

text: ρ

text: to

text: be

text: the

text: uniform

text: probability

text: on

text: the

text: set

text: Σ

text: e

text: ρ

text: ∪o

text: Λ

text: Notice

text: that

text: u

text: (g)

text: for

text: any

text: g

text: Σ

text: e

text: since

text: ρ

text: (e)

text: We

text: claim

text: that

text: M

text: restricted

text: ρo

text: Λ

text: o

text: ρo∈

text: to

text: H

text: has

text: an

text: operator

text: norm

text: c

text: Would

text: it

text: be

text: not

text: the

text: case,

text: there

text: would

text: exist

text: ν

text: H

text: such

text: that

text: the

text: previous

text: inequalities

text: would

text: be

text: equalities.

text: Thanks

text: to

text: the

text: equality

text: case

text: in

text: the

text: Cauchy-Schwarz

text: inequality,

text: this

text: implies

text: that,

text: for

text: any

text: g

text: Σ

text: the

text: two

text: measures

text: h

text: ν(h)

text: Λ

text: and

text: h

text: ν(g

text: are

text: positively

text: proportional.

text: Since

text: their

text: norm

text: are

text: equal,

text: they

text: must

text: be

text: equal.

text: Since

text: Σ

text: generates

text: Λ,

text: ν

text: is

text: Λ-invariant

text: and

text: belongs

text: to

text: H,

text: so

text: it

text: must

text: be

text: zero.

text: Λ

text: By

text: assumption,

text: the

text: probability

text: µ

text: can

text: be

text: decomposed

text: as

text: µ

text: ηρ

text: η)ν,

text: o

text: where

text: ν

text: is

text: some

text: probability.

text: This

text: implies

text: that

text: M

text: restricted

text: to

text: H

text: has

text: operator

text: norm

text: at

text: µ

text: most

text: ηc

text: η).

text: Therefore,

text: d(µ

text: n,

text: π

text: µ

text: n

text: π

text: Mn(δ

text: π

text: c)η)n.

text: Λ

text: Λ

text: µ

text: e

text: Λ

text: This

text: inequality

text: implies

text: the

text: result.

text: We

text: can

text: now

text: describe

text: the

text: asymptotic

text: behavior

text: of

text: µ

text: when

text: the

text: group

text: Γ

text: is

text: ﬁnite.

text: ε

text: s

text: Lemma

text: Assume

text: that

text: Γ

text: is

text: ﬁnite.

text: Deﬁne

text: a

text: new

text: probability

text: measure

text: λ

text: π

text: β

text: (it

text: s

text: Γs

text: generates

text: a

text: non-elementary

text: subgroup).

text: When

text: ε

text: tends

text: to

text: we

text: have

text: h(µ

text: εh(λ)

text: and

text: ε

text: ε

text: Proof.

text: The

text: random

text: variable

text: t

text: being

text: geometric

text: of

text: parameter

text: ε,

text: is

text: of

text: the

text: order

text: of

text: with

text: P

text: high

text: probability

text: (i.e.,

text: for

text: any

text: δ

text: there

text: exists

text: u

text: such

text: that

text: (t

text: u/ε)

text: δ).

text: Writing

text: Σ

text: a

text: a

text: for

text: the

text: support

text: of

text: α

text: we

text: have

text: min

text: α

text: (σ)

text: ε)

text: 1µ

text: (a

text: s

text: s

text: ε

text: σ

text: Σs

text: ε

text: ε

text: s∗

text: which

text: is

text: much

text: bigger

text: than

text: ε

text: by

text: deﬁnition

text: of

text: s.

text: Lemma

text: shows

text: that

text: the

text: measures

text: α

text: n

text: ε

text: are

text: close

text: to

text: π

text: for

text: n

text: u/ε.

text: This

text: implies

text: that

text: α˜

text: (deﬁned

text: in

text: converges

text: to

text: π

text: when

text: Γs

text: ε

text: Γs

text: ε

text: As

text: β

text: converges

text: to

text: β,

text: this

text: shows

text: that

text: λ

text: converges

text: to

text: λ.

text: ε

text: ε

text: The

text: support

text: of

text: the

text: measure

text: λ

text: contains

text: Γ

text: and

text: a

text: a

text: (as

text: the

text: support

text: of

text: β

text: contains

text: s

text: r

text: e,

text: a

text: a

text: by

text: construction).

text: Hence,

text: Γ

text: contains

text: the

text: non-elementary

text: subgroup

text: Γ

text: It

text: r

text: λ

text: r

text: follows

text: that

text: the

text: entropy

text: and

text: the

text: drift

text: are

text: continuous

text: at

text: λ,

text: by

text: Proposition

text: and

text: Theorem

text: We

text: get

text: h(λ

text: h(λ)

text: and

text: With

text: Lemma

text: this

text: completes

text: the

text: proof.

text: ε

text: ε

text: We

text: deduce

text: from

text: the

text: lemma

text: that

text: h(µ

text: tends

text: to

text: Hence,

text: the

text: measure

text: ε

text: ε

text: µ

text: λ

text: satisﬁes

text: the

text: conclusion

text: of

text: the

text: theorem,

text: at

text: least

text: in

text: the

text: non-symmetric

text: case.

text: In

text: the

text: Σ

text: symmetric

text: case,

text: where

text: we

text: are

text: looking

text: for

text: a

text: symmetric

text: measure

text: µ

text: the

text: measure

text: λ

text: π

text: β

text: Σ

text: Γs


text: ENTROPY AND DRIFT IN WORD HYPERBOLIC GROUPS 40 → C for any f : Λ . As Λ has linear growth, the following Nash inequality holds (see, for instance, [Woe00, Proposition 14.1]). (cid:107) (cid:107) (cid:54) (cid:107) (cid:107) E f 6 C f 4 (f, f), L2 L1 ρ where all norms are deﬁned with respect to the measure m on Λ. Let P be the Markov µ operator associated to µ. It satisﬁes (cid:107) (cid:107) − (cid:107) (cid:107) (cid:104) (cid:105) − (cid:104) (cid:105) (cid:104) − ∗ (cid:105) f 2 P f 2 = f, f P f, P f = (I P P )f, f . L2 µ L2 µ µ µ µ ∗ The operator P P is the Markov operator associated to the symmetric probability measure ∗ µ µ (cid:62) ∈ ∪ − (cid:62) (cid:62) ν = µˇ µ, which(cid:54)satis−ﬁes (cid:88)ν(σ) η/2 for σ ΣΛ ΣΛ1 and(cid:88)ν(e) 1/4 (since µ(e) 1/2). Therefore, ρ(g) Cη 1ν(g) for all g. We deduce (cid:88) (cid:107) (cid:107) − (cid:107) (cid:107) − − 1 | − | − f 2 P f 2 = f(x)(f(x) f(y))ν(x 1y) = f(x) f(y) 2ν(x 1y) L2 µ L2 2 (cid:62) η | − | − η E f(x) f(y) 2ρ(x 1y) = (f, f). ρ 2C C Combining this inequality with Nash inequality, we obtain (cid:107) (cid:107) (cid:54) − (cid:107) (cid:107) (cid:107) (cid:107) − (cid:107) (cid:107) f 6 Cη 1 f 4 ( f 2 P f 2 ). L2 L1 L2 µ L2 ∗ The operator P satisﬁes the same inequality, for the same reason. Composing these µ ∞ inequalities, we obtain an estimate for the norm of P n from L1 to L (this is [VSCC92, µ Lemma VII.2.6]), of the form (cid:107) (cid:107) (cid:54) (cid:48) − P n → ∞ (C η 1/n)1/2. µ L1 L (cid:3) Applying this inequality to the function δ , we get the desired result. e (cid:48) (cid:48) The previous lemma implies that, if C is large enough, a neighborhood of size (ηn)1/2/C ∗ of the identity has probability for µ n at most 1/2. Hence, the average distance to the origin is at least of the order of (ηn)1/2. ∗ Now, we study the stationary measure for β α˜ on ∂Γ. We recall that g is a hyperbolic ε ε 0 element in Γ , ﬁxed once and for all. s { − } Lemma 5.7. There exists a neighborhood U of g , g+ in ∂Γ such that the stationary ∗ → 0 0 measure ν of β α˜ satisﬁes ν (U) 0. ε ε ε ε { − } ∗ Proof. Let us ﬁrst show that, for any neighborhood U of g , g+ , then (α˜ δ )(Uc) tends ∈ 0 0 ε z to 0, uniformly in z ∂Γ. This is not surprising since a typical element for α˜ is large in the ε virtually cyclic group Γ˜ , and sends most points into U. To make this argument rigorous, we s ∗ ∗ will use Lemma 5.6. The deﬁnition (5.1) shows that it suﬃces to prove that (α n δ )(Uc) (cid:62) (cid:80) ε z is small for n u/ε. The subgroup generated by g has ﬁnite index in Γ˜ . Hence, any element in Γ˜ can be 0 s ∗ s written as gkγ , for γ in a ﬁnite set. Thus, the measure α n can be written as c (k, i)δ , 0 i i ε { n} g0kγi for some coeﬃcients c (k, i). Lemma 5.6 (applied to Λ = Γ˜ with Σ = a , . . . , a ) ensures n s Λ 1 t ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: ENTROPY

text: AND

text: DRIFT

text: IN

text: WORD

text: HYPERBOLIC

text: GROUPS

text: C

text: for

text: any

text: f

text: Λ

text: As

text: Λ

text: has

text: linear

text: growth,

text: the

text: following

text: Nash

text: inequality

text: holds

text: (see,

text: for

text: instance,

text: Proposition

text: E

text: f

text: C

text: f

text: (f,

text: f),

text: ρ

text: where

text: all

text: norms

text: are

text: deﬁned

text: with

text: respect

text: to

text: the

text: measure

text: m

text: on

text: Λ.

text: Let

text: P

text: be

text: the

text: Markov

text: µ

text: operator

text: associated

text: to

text: µ.

text: It

text: satisﬁes

text: f

text: P

text: f

text: f,

text: f

text: P

text: f,

text: P

text: f

text: (I

text: P

text: P

text: )f,

text: f

text: µ

text: µ

text: µ

text: µ

text: µ

text: The

text: operator

text: P

text: P

text: is

text: the

text: Markov

text: operator

text: associated

text: to

text: the

text: symmetric

text: probability

text: measure

text: µ

text: µ

text: ν

text: µˇ

text: µ,

text: for

text: σ

text: ΣΛ

text: ΣΛ1

text: (since

text: µ(e)

text: Therefore,

text: ρ(g)

text: Cη

text: for

text: all

text: g.

text: We

text: deduce

text: f

text: P

text: f

text: f(x)(f(x)

text: f(y))ν(x

text: f(x)

text: f(y)

text: µ

text: η

text: η

text: E

text: f(x)

text: f(y)

text: (f,

text: f).

text: ρ

text: C

text: Combining

text: this

text: inequality

text: with

text: Nash

text: inequality,

text: we

text: obtain

text: f

text: Cη

text: f

text: f

text: P

text: f

text: µ

text: The

text: operator

text: P

text: satisﬁes

text: the

text: same

text: inequality,

text: for

text: the

text: same

text: reason.

text: Composing

text: these

text: µ

text: inequalities,

text: we

text: obtain

text: an

text: estimate

text: for

text: the

text: norm

text: of

text: P

text: n

text: from

text: to

text: L

text: (this

text: is

text: µ

text: Lemma

text: of

text: the

text: form

text: P

text: n

text: (C

text: η

text: µ

text: L

text: Applying

text: this

text: inequality

text: to

text: the

text: function

text: δ

text: we

text: get

text: the

text: desired

text: result.

text: e

text: The

text: previous

text: lemma

text: implies

text: that,

text: if

text: C

text: is

text: large

text: enough,

text: a

text: neighborhood

text: of

text: size

text: of

text: the

text: identity

text: has

text: probability

text: for

text: µ

text: n

text: at

text: most

text: Hence,

text: the

text: average

text: distance

text: to

text: the

text: origin

text: is

text: at

text: least

text: of

text: the

text: order

text: of

text: Now,

text: we

text: study

text: the

text: stationary

text: measure

text: for

text: β

text: α˜

text: on

text: ∂Γ.

text: We

text: recall

text: that

text: g

text: is

text: a

text: hyperbolic

text: ε

text: ε

text: element

text: in

text: Γ

text: ﬁxed

text: once

text: and

text: for

text: all.

text: s

text: Lemma

text: There

text: exists

text: a

text: neighborhood

text: U

text: of

text: g

text: g+

text: in

text: ∂Γ

text: such

text: that

text: the

text: stationary

text: measure

text: ν

text: of

text: β

text: α˜

text: satisﬁes

text: ν

text: (U)

text: ε

text: ε

text: ε

text: ε

text: Proof.

text: Let

text: us

text: ﬁrst

text: show

text: that,

text: for

text: any

text: neighborhood

text: U

text: of

text: g

text: g+

text: then

text: (α˜

text: δ

text: )(Uc)

text: tends

text: ε

text: z

text: to

text: uniformly

text: in

text: z

text: ∂Γ.

text: This

text: is

text: not

text: surprising

text: since

text: a

text: typical

text: element

text: for

text: α˜

text: is

text: large

text: in

text: the

text: ε

text: virtually

text: cyclic

text: group

text: Γ˜

text: and

text: sends

text: most

text: points

text: into

text: U.

text: To

text: make

text: this

text: argument

text: rigorous,

text: we

text: s

text: will

text: use

text: Lemma

text: The

text: deﬁnition

text: shows

text: that

text: it

text: suﬃces

text: to

text: prove

text: that

text: (α

text: n

text: δ

text: )(Uc)

text: ε

text: z

text: is

text: small

text: for

text: n

text: u/ε.

text: The

text: subgroup

text: generated

text: by

text: g

text: has

text: ﬁnite

text: index

text: in

text: Γ˜

text: Hence,

text: any

text: element

text: in

text: Γ˜

text: can

text: be

text: s

text: s

text: written

text: as

text: gkγ

text: for

text: γ

text: in

text: a

text: ﬁnite

text: set.

text: Thus,

text: the

text: measure

text: α

text: n

text: can

text: be

text: written

text: as

text: c

text: (k,

text: i)δ

text: i

text: i

text: ε

text: n}

text: for

text: some

text: coeﬃcients

text: c

text: (k,

text: i).

text: Lemma

text: (applied

text: to

text: Λ

text: Γ˜

text: with

text: Σ

text: a

text: a

text: ensures

text: n

text: s

text: Λ

text: t

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ENTROPY AND DRIFT IN WORD HYPERBOLIC GROUPS 41 (cid:54) (cid:62)(cid:88) that sup c (k, i) C/(ηn)1/2. When n u/ε, this quantity tends to 0 since ε = o(η). We k,i n have ∗ ∗ ∈ (α n δ )(Uc) = c (k, i)1(gkγ z / U). ε z n 0 i k,i ∈ As the element g is hyperbolic, there exists C such that, for any w ∂Γ, 0 |{ ∈ Z ∈ }| (cid:54) k : gkw / U C. (cid:0) (cid:1) (cid:88) 0 \ { − } (cid:104) (cid:105) The uniformity in w follows from the compactness of (∂Γ g , g+ )/ g . We obtain 0 0 0 ∗ ∗ (cid:54) |{ ∈ Z ∈ }| (cid:54) (cid:54) (α n δ )(Uc) sup c (k, i) k : gkγ z / U C sup c (k, i) C/(ηn)1/2. ε z n 0 i n k,i k,i i ∗ ∗ This shows that (α n δ )(Uc) is small, as desired. ∗ ε z ∗ As α˜ δ (Uc) tends to 0 uniformly in z, we deduce that (α˜ ν )(Uc) also tends to 0, ε z ∗ ε ε and therefore that (α˜ ν )(U) tends to 1. { − } ε ε ∩ (cid:54) ∅ Let A = g , g+ . We claim that, for all g such that gA A = , then gA = A. Indeed, if − ∈ 0 0 − − g(g ) A for instance, then g 1g g is a hyperbolic element stabilizing g . It also stabilizes 0 0 0 g+, by [GdlH90, Théorème 30 page 154], i.e., g g(g+) = g(g+). Hence, g(g+) is a ﬁxed point 0 ∈ 0 0 0 0 of g , i.e., g(g+) A. 0 0 By deﬁnition of β , the ﬁnitely many elements of its support do not ﬁx A. They even ∩ ∅ ε satisfy gA A = for all g in this support, by the previous argument. If U is small enough, ∩ ∅ ⊂ we get gU U = , i.e., g(U) Uc. Finally, ∗ ∗ (cid:62) ∗ ν (Uc) = (β α˜ ν )(Uc) (α˜ ν )(U), ε ε ε ε ε ε (cid:3) which tends to 1 when ε tends to 0. (cid:62) · Lemma 5.8. The drift (cid:96)(λ ) satisﬁes (cid:96)(λ ) c (η/ε)1/2. ε ε (cid:90) Proof. Let ρ be a stationary measure for λ , on the Busemann boundary ∂ Γ. By Proposi- ε ε B tion 2.2, (cid:96)(λ ) = c (g, ξ) dρ (ξ) dλ (g), ε(cid:90) B ε ε − ∗ where c (g, ξ) = h (g 1) is the Busemann cocycle. As λ = α˜ β , this gives B ξ ε ε ε (cid:96)(λ ) = c (Lb, ξ) dρ (ξ) dα˜ (L) dβ (b). ε B ε ε ε (cid:90) (cid:90) With the cocycle relation (2.2), this becomes (cid:96)(λ ) = c (L, bξ) dρ (ξ) dα˜ (L) dβ (b) + c (b, ξ) dρ (ξ) dα˜ (L) dβ (b). ε B ε ε ε B ε ε ε The second integral is bounded independently of ε since the support of β is ﬁnite. In the (cid:48) ∗ ε ﬁrst integral, ξ = bξ is distributed according to the measure ρ˜ := β ρ , which is stationary ∗ ε ε ε for β α˜ . Lemma 5.7 implies that its projection (π )∗ρ˜ on the geometric boundary, which ε ε ∗ B ε { − } is again stationary for β α˜ , gives a small measure to a neighborhood U of g , g+ . ε ε 0 0

text: ENTROPY

text: AND

text: DRIFT

text: IN

text: WORD

text: HYPERBOLIC

text: GROUPS

text: that

text: sup

text: c

text: (k,

text: i)

text: When

text: n

text: u/ε,

text: this

text: quantity

text: tends

text: to

text: since

text: ε

text: o(η).

text: We

text: k,i

text: n

text: have

text: (α

text: n

text: δ

text: )(Uc)

text: c

text: (k,

text: z

text: U).

text: ε

text: z

text: n

text: i

text: k,i

text: As

text: the

text: element

text: g

text: is

text: hyperbolic,

text: there

text: exists

text: C

text: such

text: that,

text: for

text: any

text: w

text: ∂Γ,

text: Z

text: k

text: gkw

text: U

text: C.

text: The

text: uniformity

text: in

text: w

text: follows

text: from

text: the

text: compactness

text: of

text: (∂Γ

text: g

text: g+

text: g

text: We

text: obtain

text: Z

text: (α

text: n

text: δ

text: )(Uc)

text: sup

text: c

text: (k,

text: i)

text: k

text: gkγ

text: z

text: U

text: C

text: sup

text: c

text: (k,

text: i)

text: ε

text: z

text: n

text: i

text: n

text: k,i

text: k,i

text: i

text: This

text: shows

text: that

text: (α

text: n

text: δ

text: )(Uc)

text: is

text: small,

text: as

text: desired.

text: ε

text: z

text: As

text: α˜

text: δ

text: (Uc)

text: tends

text: to

text: uniformly

text: in

text: z,

text: we

text: deduce

text: that

text: (α˜

text: ν

text: )(Uc)

text: also

text: tends

text: to

text: ε

text: z

text: ε

text: ε

text: and

text: therefore

text: that

text: (α˜

text: ν

text: )(U)

text: tends

text: to

text: ε

text: ε

text: Let

text: A

text: g

text: g+

text: We

text: claim

text: that,

text: for

text: all

text: g

text: such

text: that

text: gA

text: A

text: then

text: gA

text: A.

text: Indeed,

text: if

text: g(g

text: A

text: for

text: instance,

text: then

text: g

text: g

text: is

text: a

text: hyperbolic

text: element

text: stabilizing

text: g

text: It

text: also

text: stabilizes

text: g+,

text: by

text: Théorème

text: page

text: i.e.,

text: g

text: g(g+)

text: g(g+).

text: Hence,

text: g(g+)

text: is

text: a

text: ﬁxed

text: point

text: of

text: g

text: i.e.,

text: g(g+)

text: A.

text: By

text: deﬁnition

text: of

text: β

text: the

text: ﬁnitely

text: many

text: elements

text: of

text: its

text: support

text: do

text: not

text: ﬁx

text: A.

text: They

text: even

text: ε

text: satisfy

text: gA

text: A

text: for

text: all

text: g

text: in

text: this

text: support,

text: by

text: the

text: previous

text: argument.

text: If

text: U

text: is

text: small

text: enough,

text: we

text: get

text: gU

text: U

text: i.e.,

text: g(U)

text: Uc.

text: Finally,

text: ν

text: (Uc)

text: (β

text: α˜

text: ν

text: )(Uc)

text: (α˜

text: ν

text: )(U),

text: ε

text: ε

text: ε

text: ε

text: ε

text: ε

text: which

text: tends

text: to

text: when

text: ε

text: tends

text: to

text: Lemma

text: The

text: drift

text: satisﬁes

text: c

text: ε

text: ε

text: Proof.

text: Let

text: ρ

text: be

text: a

text: stationary

text: measure

text: for

text: λ

text: on

text: the

text: Busemann

text: boundary

text: Γ.

text: By

text: Proposi-

text: ε

text: ε

text: B

text: tion

text: c

text: (g,

text: ξ)

text: dρ

text: (ξ)

text: dλ

text: (g),

text: B

text: ε

text: ε

text: where

text: c

text: (g,

text: ξ)

text: h

text: (g

text: is

text: the

text: Busemann

text: cocycle.

text: As

text: λ

text: α˜

text: β

text: this

text: gives

text: B

text: ξ

text: ε

text: ε

text: ε

text: c

text: (Lb,

text: ξ)

text: dρ

text: (ξ)

text: dα˜

text: (L)

text: dβ

text: (b).

text: ε

text: B

text: ε

text: ε

text: ε

text: With

text: the

text: cocycle

text: relation

text: this

text: becomes

text: c

text: (L,

text: bξ)

text: dρ

text: (ξ)

text: dα˜

text: (L)

text: dβ

text: (b)

text: c

text: (b,

text: ξ)

text: dρ

text: (ξ)

text: dα˜

text: (L)

text: dβ

text: (b).

text: ε

text: B

text: ε

text: ε

text: ε

text: B

text: ε

text: ε

text: ε

text: The

text: second

text: integral

text: is

text: bounded

text: independently

text: of

text: ε

text: since

text: the

text: support

text: of

text: β

text: is

text: ﬁnite.

text: In

text: the

text: ε

text: ﬁrst

text: integral,

text: ξ

text: bξ

text: is

text: distributed

text: according

text: to

text: the

text: measure

text: ρ˜

text: β

text: ρ

text: which

text: is

text: stationary

text: ε

text: ε

text: ε

text: for

text: β

text: α˜

text: Lemma

text: implies

text: that

text: its

text: projection

text: (π

text: )∗ρ˜

text: on

text: the

text: geometric

text: boundary,

text: which

text: ε

text: ε

text: B

text: ε

text: is

text: again

text: stationary

text: for

text: β

text: α˜

text: gives

text: a

text: small

text: measure

text: to

text: a

text: neighborhood

text: U

text: of

text: g

text: g+

text: ε

text: ε


text: ENTROPY AND DRIFT IN WORD HYPERBOLIC GROUPS 9 hyperbolicity is not automatic. Hence, one should postulate its hyperbolicity if it is needed, as in the statement of Theorem 1.2. We say that the pair (Γ, d) is a metric hyperbolic group if the group Γ is hyperbolic for one (or, equivalently, for any) word distance, and if the distance d is left-invariant, hyperbolic, and quasi-isometric to one (or equivalently, any) word distance. Such a distance d does not have to be geodesic, but it is quasi-geodesic since geodesics for a given word distance form a system of quasi-geodesics for d, going from any point to any point. Let (Γ, d) be a metric hyperbolic group. The left-multiplication by elements of Γ is ∪ ∪ isometric. Hence, Γ acts by homeomorphisms on its compactiﬁcations Γ ∂Γ and Γ ∂ Γ. ∈ ∪ B Moreover, any inﬁnite order element g Γ acts hyperbolically on Γ ∂Γ: it has two ﬁxed − ∪ \ { −} points at inﬁnity g and g+, the points in Γ ∂Γ g are attracted to g+ by forward ∪ \ { } − iteration of g, and the points in Γ ∂Γ g+ are attracted to g by backward iteration of g. × → R Deﬁnition 2.1. Consider an action of a group Γ on a space Z. A function c : Γ Z ∈ ∈ is a cocycle if, for any g, h Γ and any ξ Z, (2.2) c(gh, ξ) = c(g, hξ) + c(h, ξ). (cid:55)→ The cocycle is Hölder-continuous if Z is a metric space and each function ξ c(g, ξ) is Hölder-continuous. There is a choice to be made in the deﬁnition of cocycles, since one may compose with g or − × → R g 1. Our deﬁnition is the most customary. With this deﬁnition, the map c : Γ ∂ Γ − B B given by c (g, ξ) = h (g 1) is a cocycle, called the Busemann cocycle. B ξ A subgroup H of Γ is nonelementary if its action on ∂Γ does not ﬁx a ﬁnite set. Equiva- Z lently, H is not virtually the trivial group or . We say that a probability measure µ on Γ is nonelementary if the subgroup Γ generated by its support is itself nonelementary. (cid:80) µ Let µ be a probability measure on Γ. Since Γ acts by homeomorphisms on the compact space ∂Γ, it admits a stationary measure: there exists a probability measure ν on ∂Γ such ∗ that µ ν = ν, i.e., ∈ µ(g)g∗ν = ν. If µ is nonelementary, this measure is unique, g Γ and has no atom (see [Kai00]). It is also the exit measure of the corresponding random · · · ∈ walk X = g g : almost every trajectory X (ω) converges to a point X∞(ω) ∂Γ, and n 1 n n moreover the distribution of X∞ is precisely ν. In the same way, since Γ acts on ∂ Γ, it admits a stationary measure ν there. This B B measure is not unique in general, even if µ is nonelementary. However, all such measures project under π to the unique stationary measure on ∂Γ. B Let (Γ, d) be a metric hyperbolic group. Consider a probability measure µ on Γ, with ﬁnite ﬁrst moment L(µ) (deﬁned in (1.1)). The drift of the random walk has been deﬁned ∗ · · · in (1.2) as (cid:96)(µ) = lim L(µ n)/n. Let X = g g be the position at time n of the random n 1 n walk generated by µ (where the g are independent and distributed according to µ). Then, | | i almost surely, (cid:96)(µ) = lim X /n. n

text: ENTROPY

text: AND

text: DRIFT

text: IN

text: WORD

text: HYPERBOLIC

text: GROUPS

text: hyperbolicity

text: is

text: not

text: automatic.

text: Hence,

text: one

text: should

text: postulate

text: its

text: hyperbolicity

text: if

text: it

text: is

text: needed,

text: as

text: in

text: the

text: statement

text: of

text: Theorem

text: We

text: say

text: that

text: the

text: pair

text: (Γ,

text: d)

text: is

text: a

text: metric

text: hyperbolic

text: group

text: if

text: the

text: group

text: Γ

text: is

text: hyperbolic

text: for

text: one

text: (or,

text: equivalently,

text: for

text: any)

text: word

text: distance,

text: and

text: if

text: the

text: distance

text: d

text: is

text: left-invariant,

text: hyperbolic,

text: and

text: quasi-isometric

text: to

text: one

text: (or

text: equivalently,

text: any)

text: word

text: distance.

text: Such

text: a

text: distance

text: d

text: does

text: not

text: have

text: to

text: be

text: geodesic,

text: but

text: it

text: is

text: quasi-geodesic

text: since

text: geodesics

text: for

text: a

text: given

text: word

text: distance

text: form

text: a

text: system

text: of

text: quasi-geodesics

text: for

text: d,

text: going

text: from

text: any

text: point

text: to

text: any

text: point.

text: Let

text: (Γ,

text: d)

text: be

text: a

text: metric

text: hyperbolic

text: group.

text: The

text: left-multiplication

text: by

text: elements

text: of

text: Γ

text: is

text: isometric.

text: Hence,

text: Γ

text: acts

text: by

text: homeomorphisms

text: on

text: its

text: compactiﬁcations

text: Γ

text: ∂Γ

text: and

text: Γ

text: Γ.

text: B

text: Moreover,

text: any

text: inﬁnite

text: order

text: element

text: g

text: Γ

text: acts

text: hyperbolically

text: on

text: Γ

text: ∂Γ:

text: it

text: has

text: two

text: ﬁxed

text: points

text: at

text: inﬁnity

text: g

text: and

text: g+,

text: the

text: points

text: in

text: Γ

text: ∂Γ

text: g

text: are

text: attracted

text: to

text: g+

text: by

text: forward

text: iteration

text: of

text: g,

text: and

text: the

text: points

text: in

text: Γ

text: ∂Γ

text: g+

text: are

text: attracted

text: to

text: g

text: by

text: backward

text: iteration

text: of

text: g.

text: R

text: Deﬁnition

text: Consider

text: an

text: action

text: of

text: a

text: group

text: Γ

text: on

text: a

text: space

text: Z.

text: A

text: function

text: c

text: Γ

text: Z

text: is

text: a

text: cocycle

text: if,

text: for

text: any

text: g,

text: h

text: Γ

text: and

text: any

text: ξ

text: Z,

text: c(gh,

text: ξ)

text: c(g,

text: hξ)

text: c(h,

text: ξ).

text: The

text: cocycle

text: is

text: Hölder-continuous

text: if

text: Z

text: is

text: a

text: metric

text: space

text: and

text: each

text: function

text: ξ

text: c(g,

text: ξ)

text: is

text: Hölder-continuous.

text: There

text: is

text: a

text: choice

text: to

text: be

text: made

text: in

text: the

text: deﬁnition

text: of

text: cocycles,

text: since

text: one

text: may

text: compose

text: with

text: g

text: or

text: R

text: g

text: Our

text: deﬁnition

text: is

text: the

text: most

text: customary.

text: With

text: this

text: deﬁnition,

text: the

text: map

text: c

text: Γ

text: Γ

text: B

text: B

text: given

text: by

text: c

text: (g,

text: ξ)

text: h

text: (g

text: is

text: a

text: cocycle,

text: called

text: the

text: Busemann

text: cocycle.

text: B

text: ξ

text: A

text: subgroup

text: H

text: of

text: Γ

text: is

text: nonelementary

text: if

text: its

text: action

text: on

text: ∂Γ

text: does

text: not

text: ﬁx

text: a

text: ﬁnite

text: set.

text: Equiva-

text: Z

text: lently,

text: H

text: is

text: not

text: virtually

text: the

text: trivial

text: group

text: or

text: We

text: say

text: that

text: a

text: probability

text: measure

text: µ

text: on

text: Γ

text: is

text: nonelementary

text: if

text: the

text: subgroup

text: Γ

text: generated

text: by

text: its

text: support

text: is

text: itself

text: nonelementary.

text: µ

text: Let

text: µ

text: be

text: a

text: probability

text: measure

text: on

text: Γ.

text: Since

text: Γ

text: acts

text: by

text: homeomorphisms

text: on

text: the

text: compact

text: space

text: ∂Γ,

text: it

text: admits

text: a

text: stationary

text: measure:

text: there

text: exists

text: a

text: probability

text: measure

text: ν

text: on

text: ∂Γ

text: such

text: that

text: µ

text: ν

text: ν,

text: i.e.,

text: µ(g)g∗ν

text: ν.

text: If

text: µ

text: is

text: nonelementary,

text: this

text: measure

text: is

text: unique,

text: g

text: Γ

text: and

text: has

text: no

text: atom

text: (see

text: It

text: is

text: also

text: the

text: exit

text: measure

text: of

text: the

text: corresponding

text: random

text: walk

text: X

text: g

text: g

text: almost

text: every

text: trajectory

text: X

text: (ω)

text: converges

text: to

text: a

text: point

text: X∞(ω)

text: ∂Γ,

text: and

text: n

text: n

text: n

text: moreover

text: the

text: distribution

text: of

text: X∞

text: is

text: precisely

text: ν.

text: In

text: the

text: same

text: way,

text: since

text: Γ

text: acts

text: on

text: Γ,

text: it

text: admits

text: a

text: stationary

text: measure

text: ν

text: there.

text: This

text: B

text: B

text: measure

text: is

text: not

text: unique

text: in

text: general,

text: even

text: if

text: µ

text: is

text: nonelementary.

text: However,

text: all

text: such

text: measures

text: project

text: under

text: π

text: to

text: the

text: unique

text: stationary

text: measure

text: on

text: ∂Γ.

text: B

text: Let

text: (Γ,

text: d)

text: be

text: a

text: metric

text: hyperbolic

text: group.

text: Consider

text: a

text: probability

text: measure

text: µ

text: on

text: Γ,

text: with

text: ﬁnite

text: ﬁrst

text: moment

text: L(µ)

text: (deﬁned

text: in

text: The

text: drift

text: of

text: the

text: random

text: walk

text: has

text: been

text: deﬁned

text: in

text: as

text: lim

text: L(µ

text: n)/n.

text: Let

text: X

text: g

text: g

text: be

text: the

text: position

text: at

text: time

text: n

text: of

text: the

text: random

text: n

text: n

text: walk

text: generated

text: by

text: µ

text: (where

text: the

text: g

text: are

text: independent

text: and

text: distributed

text: according

text: to

text: µ).

text: Then,

text: i

text: almost

text: surely,

text: lim

text: X

text: /n.

text: n


text: In [EG80], Erd˝os and Graham ask whether the equation x2+y2 = z2 is 2-regular. In [Gra08], Graham notes that it is not clear which answer is correct. In [FH13] it is proved that 9x2 + 16y2 = n2 (along with a family of similar quadratic equations) is 2-regular, but only x and y are supposed to be monochromatic (note n). We oﬀer(cid:0)the following three(cid:1)results, which have been a part of ongoing work to settle the question: (cid:0) (cid:1) Theorem 1. R x2 + y2 + z2 = w2 = 105. 2 (cid:0) (cid:1) Theorem 2. R x2 + x2 + x2 + x2 = y2 + y2 + y2 = 32. 3 1 2 3 4 1 2 3 Theorem 3. R x2 + y2 = z2 > 6500. 2 In the third of these results, we do not exclude the possibility that it is inﬁnite. These results are all obtained computationally and will be detailed in [MP]. The ﬁrst result also inspires a new sequence representing the Rado number for · · · the equation x2 + x2 + + x2 = z2, which is tabulated as follows: 1 2 k k = 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 N = ? 105 37 23 18 20 20 15 16 20 23 17 21 26 17 23 This is now entry A250026 in the Online Encyclopedia of Integer Sequences. References [BB82] Albrecht Beutelspacher and Walter Brestovansky, Generalized Schur Numbers, Lecture Notes in Mathematics 696 (1982), 30–38. [EG80] Paul Erd˝os and Ron Graham, Old and New Problems and Results in Combinatorial Number Theory, Universit´e de Gen`eve, L’Enseignement Math´ematique 28 (1980). [FH13] Nikos Frantzikinakis and Bernard Host, Uniformity of Multiplica- tive Functions and Partition Regularity of Some Quadratic Equations, ArXiv e-prints (2013). [Gra08] Ron Graham, Old and New Problems in Ramsey Theory, Bolyai Soc. math. Stud. 17 (2008), 105–118. [MP] Kellen Myers and Joseph Parrish, Some Nonlinear Rado Numbers, (in preparation). [Rad33] Richard Rado, Studien zur Kombinatorik, Math. Zeit. 36 (1933), 242– 280. ≡ [Sch16] Issai Schur, Uber die Kongruenz xm + ym zm(mod p), Jahresber. Deutsche Math.-Verein. 25 (1916), 114–116. 2 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: In

text: Erd˝os

text: and

text: Graham

text: ask

text: whether

text: the

text: equation

text: is

text: In

text: Graham

text: notes

text: that

text: it

text: is

text: not

text: clear

text: which

text: answer

text: is

text: correct.

text: In

text: it

text: is

text: proved

text: that

text: (along

text: with

text: a

text: family

text: of

text: similar

text: quadratic

text: equations)

text: is

text: but

text: only

text: x

text: and

text: y

text: are

text: supposed

text: to

text: be

text: monochromatic

text: (note

text: n).

text: We

text: following

text: which

text: have

text: been

text: a

text: part

text: of

text: ongoing

text: work

text: to

text: settle

text: the

text: question:

text: Theorem

text: R

text: Theorem

text: R

text: Theorem

text: R

text: In

text: the

text: third

text: of

text: these

text: results,

text: we

text: do

text: not

text: exclude

text: the

text: possibility

text: that

text: it

text: is

text: inﬁnite.

text: These

text: results

text: are

text: all

text: obtained

text: computationally

text: and

text: will

text: be

text: detailed

text: in

text: [MP].

text: The

text: ﬁrst

text: result

text: also

text: inspires

text: a

text: new

text: sequence

text: representing

text: the

text: Rado

text: number

text: for

text: the

text: equation

text: which

text: is

text: tabulated

text: as

text: follows:

text: k

text: k

text: N

text: This

text: is

text: now

text: entry

text: in

text: the

text: Online

text: Encyclopedia

text: of

text: Integer

text: Sequences.

text: References

text: Albrecht

text: Beutelspacher

text: and

text: Walter

text: Brestovansky,

text: Generalized

text: Schur

text: Numbers,

text: Lecture

text: Notes

text: in

text: Mathematics

text: Paul

text: Erd˝os

text: and

text: Ron

text: Graham,

text: Old

text: and

text: New

text: Problems

text: and

text: Results

text: in

text: Combinatorial

text: Number

text: Theory,

text: Universit´e

text: de

text: Gen`eve,

text: L’Enseignement

text: Math´ematique

text: Nikos

text: Frantzikinakis

text: and

text: Bernard

text: Host,

text: Uniformity

text: of

text: Multiplica-

text: tive

text: Functions

text: and

text: Partition

text: Regularity

text: of

text: Some

text: Quadratic

text: Equations,

text: ArXiv

text: e-prints

text: Ron

text: Graham,

text: Old

text: and

text: New

text: Problems

text: in

text: Ramsey

text: Theory,

text: Bolyai

text: Soc.

text: math.

text: Stud.

text: [MP]

text: Kellen

text: Myers

text: and

text: Joseph

text: Parrish,

text: Some

text: Nonlinear

text: Rado

text: Numbers,

text: (in

text: preparation).

text: Richard

text: Rado,

text: Studien

text: zur

text: Kombinatorik,

text: Math.

text: Zeit.

text: Issai

text: Schur,

text: Uber

text: die

text: Kongruenz

text: xm

text: ym

text: zm(mod

text: p),

text: Jahresber.

text: Deutsche

text: Math.-Verein.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Walk-powers and homomorphism bound of planar graphs ∗ Reza Naserasr a, Sagnik Sen b, Qiang Sun a (a) LRI, CNRS and Universit´e Paris Sud, F-91405 Orsay Cedex, France (b) Indian Statistical Institute, Kolkata, India May 27, 2020 Abstract As an extension of the Four-Color Theorem it is conjectured that every planar graph Z { · · · } of odd-girth at least 2k + 1 admits a homomorphism to PC = ( 2k, e , e , , e , J ) 2k 2 1 2 2k where e ’s are standard basis and J is all 1 vector. Noting that PC itself is of odd-girth i 2k 2k + 1, in this work we show that if the conjecture is true, then PC is an optimal such a 2k graph both with respect to number of vertices and number of edges. The result is obtained using the notion of walk-power of graphs and their clique numbers. An analogous result is proved for bipartite signed planar graphs of unbalanced-girth 2k. The work is presented on a uniform frame work of planar consistent signed graphs. 1 Introudction 1.1 Signed graphs, notation − Given a graph G, a signature on G is an assignment of signs, + or , to the edges. The set of negative edges is normally denoted by Σ and will normally be referred to as the signature. A re- signing is to change the signs of all edges incident to a given set of vertices or, equivalently, edges of an edge-cut. Two signatures are said to be equivalent if one can be obtained from the other by a re-signing. A graph G together with a set of signatures equivalent to Σ is called a signed graph and is denoted by [G, Σ] where Σ is any member of the class of equivalent signatures. A signed cycle with an even (odd) number of negative edges is called balanced (unbalanced). It is easily observed that the balance of a cycle is invariant of re-signing. The unbalanced-girth of a signed graph is the shortest length of its unbalanced cycles. A consistent signed graph is a signed graph in which every balanced cycle is of even length and all unbalanced cycles are of a same parity. Thus there are two types of consistent signed graphs: i. when all unbalanced cycles are of odd length, it can be shown that this is the case if and ≡ only if Σ E(G), such a signed graph will be called an odd signed graph; ii. when all unbalanced cycles are of even length, which will be the case if and only if G is bipartite, such a signed graph thus will be referred to as a singed bipartite graph. ∗ Corresponding author, supported by CSC. E-mail address: sun@lri.fr(Q. Sun). 1 ##LTLine##

text: Walk-powers

label: title

text: and

text: homomorphism

text: bound

text: of

text: planar

text: graphs

label: author

text: Reza

text: Naserasr

text: a,

text: Sagnik

text: Sen

text: b,

text: Qiang

text: Sun

text: a

text: (a)

text: LRI,

text: CNRS

text: and

text: Universit´e

text: Paris

text: Sud,

text: Orsay

text: Cedex,

text: France

text: (b)

text: Indian

text: Statistical

text: Institute,

text: Kolkata,

text: India

text: May

label: date

text: Abstract

text: As

label: abstract

text: an

text: extension

text: of

text: the

text: Four-Color

text: Theorem

text: it

text: is

text: conjectured

text: that

text: every

text: planar

text: graph

text: Z

text: of

text: odd-girth

text: at

text: least

text: admits

text: a

text: homomorphism

text: to

text: PC

text: e

text: e

text: e

text: J

text: where

text: e

text: ’s

text: are

text: standard

text: basis

text: and

text: J

text: is

text: all

text: vector.

text: Noting

text: that

text: PC

text: itself

text: is

text: of

text: odd-girth

text: i

text: in

text: this

text: work

text: we

text: show

text: that

text: if

text: the

text: conjecture

text: is

text: true,

text: then

text: PC

text: is

text: an

text: optimal

text: such

text: a

text: graph

text: both

text: with

text: respect

text: to

text: number

text: of

text: vertices

text: and

text: number

text: of

text: edges.

text: The

text: result

text: is

text: obtained

text: using

text: the

text: notion

text: of

text: walk-power

text: of

text: graphs

text: and

text: their

text: clique

text: numbers.

text: An

text: analogous

text: result

text: is

text: proved

text: for

text: bipartite

text: signed

text: planar

text: graphs

text: of

text: unbalanced-girth

text: The

text: work

text: is

text: presented

text: on

text: a

text: uniform

text: frame

text: work

text: of

text: planar

text: consistent

text: signed

text: graphs.

text: Introudction

text: Signed

text: graphs,

text: notation

text: Given

text: a

text: graph

text: G,

text: a

text: signature

text: on

text: G

text: is

text: an

text: assignment

text: of

text: signs,

text: or

text: to

text: the

text: edges.

text: The

text: set

text: of

text: negative

text: edges

text: is

text: normally

text: denoted

text: by

text: Σ

text: and

text: will

text: normally

text: be

text: referred

text: to

text: as

text: the

text: signature.

text: A

text: re-

text: signing

text: is

text: to

text: change

text: the

text: signs

text: of

text: all

text: edges

text: incident

text: to

text: a

text: given

text: set

text: of

text: vertices

text: or,

text: equivalently,

text: edges

text: of

text: an

text: edge-cut.

text: Two

text: signatures

text: are

text: said

text: to

text: be

text: equivalent

text: if

text: one

text: can

text: be

text: obtained

text: from

text: the

text: other

text: by

text: a

text: re-signing.

text: A

text: graph

text: G

text: together

text: with

text: a

text: set

text: of

text: signatures

text: equivalent

text: to

text: Σ

text: is

text: called

text: a

text: signed

text: graph

text: and

text: is

text: denoted

text: by

text: [G,

text: Σ]

text: where

text: Σ

text: is

text: any

text: member

text: of

text: the

text: class

text: of

text: equivalent

text: signatures.

text: A

text: signed

text: cycle

text: with

text: an

text: even

text: (odd)

text: number

text: of

text: negative

text: edges

text: is

text: called

text: balanced

text: (unbalanced).

text: It

text: is

text: easily

text: observed

text: that

text: the

text: balance

text: of

text: a

text: cycle

text: is

text: invariant

text: of

text: re-signing.

text: The

text: unbalanced-girth

text: of

text: a

text: signed

text: graph

text: is

text: the

text: shortest

text: length

text: of

text: its

text: unbalanced

text: cycles.

text: A

text: consistent

text: signed

text: graph

text: is

text: a

text: signed

text: graph

text: in

text: which

text: every

text: balanced

text: cycle

text: is

text: of

text: even

text: length

text: and

text: all

text: unbalanced

text: cycles

text: are

text: of

text: a

text: same

text: parity.

text: Thus

text: there

text: are

text: two

text: types

text: of

text: consistent

text: signed

text: graphs:

text: i.

text: when

text: all

text: unbalanced

text: cycles

text: are

text: of

text: odd

text: length,

text: it

text: can

text: be

text: shown

text: that

text: this

text: is

text: the

text: case

text: if

text: and

text: only

text: if

text: Σ

text: E(G),

text: such

text: a

text: signed

text: graph

text: will

text: be

text: called

text: an

text: odd

text: signed

text: graph;

text: ii.

text: when

text: all

text: unbalanced

text: cycles

text: are

text: of

text: even

text: length,

text: which

text: will

text: be

text: the

text: case

text: if

text: and

text: only

text: if

text: G

text: is

text: bipartite,

text: such

text: a

text: signed

text: graph

text: thus

text: will

text: be

text: referred

text: to

text: as

text: a

text: singed

text: bipartite

text: graph.

text: Corresponding

text: author,

text: supported

text: by

text: CSC.

text: E-mail

text: address:

text: sun@lri.fr(Q.

text: Sun).

text: ##LTLine##


text: Proof. We consider a ﬁxed signature Σ of [G, Σ]. We will use the same notations (P , t etc.) xy xy as in Lemma 2.2. Thus as proved in that lemma, parallel edges of K are subdivided same 4 number of times. Furthermore, repeating the same argument modulo 2, we can conclude that the number of negative edges in P and the number of negative edges in P have same parity { } { } xy wz for all x, y, w, z = a, b, c, d . Let u and v be two vertices from same part of G (thus any path connecting u and v have − even length). We would like to prove that they are adjacent in [G, Σ](2k 2). If they belong to a same facial cycle, then the two paths connecting these two vertices in that (unbalanced) cycle ∈ satisfy the conditions and we are done. Hence, assume without loss of generality that u P ∈ ab and v P . cd − Removing the edges of the parallel paths P and P will result in a cycle of length 4k 2t ad bc ad containing u, v. This implies: ≤ − (t + t + t ) + (t + t + t ) 4k 2 ua ac cv ub bd dv ⇒ { } ≤ − min (t + t + t ), (t + t + t ) 2k 2. (4) ua ac cv ub bd dv Similarly by removing P and P we get ac bd { } ≤ − min (t + t + t ), (t + t + t ) 2k 2. (5) ua ad dv ub bc cv It remains to show that the two paths of equation (4) and (5) have diﬀerent number of negative edges modulo 2. To see this note that union of any one of the two paths from (4) with a path from (5) covers a facial cycle exactly once and one a part of P or P twice. Since each ab cd facial cycle is unbalanced, our claim is proved. We are now ready to present our general construction. − Theorem 3.3. There exists a planar signed bipartite graph [G, Σ] such that in [G, Σ](2k 1) each − part of G induces a clique of size at least 22k 2. Proof. Consider a K on four vertices a, b, c and d. Let G be a subdivision of this K where 4 − 1 4 edges ab and cd each are subdivided into 2k 2 edges. Note that G is a connected bipartite (cid:48) 1 graph and let V and V be its partite sets. Let Σ be the signature with the new edge incident to 1 1 1 a (created by the subdivision of ab) and the new edge incedent to c (created by the subdivision of cd) being negative. Thus the signed bipartite graph [G , Σ ] is a subdivision of K in which 1 1 4 all the four faces are unbalanced cycles of length 2k. Hence by Lemma 3.2 we know that each (cid:48) − − of V and V induces a clique of order 2k 1 in [G , Σ ](2k 2). 1 1 1 1 ∈ { · · · − } In the following we will build a sequence of signed graphs [G , Σ ], for i 1, 2, , 2k 1 , ≤ − i i such that each [G , Σ ], i 2k 2, contains [G , Σ ] as a subgraph. Moreover, the signed i+1 i+1 i i (cid:48) graph [G , Σ ] is a bipartite planar graph with unbalanced-girth 2k and partite sets V , V . Let i i (cid:48) − i i us denote the clique number of the graph induced by V (or V ) from [G , Σ ](2k 2) by f(i) (or (cid:48) i i i i f (i)). Note that both the functions are strictly increasing and at the ﬁnal step we will have − (cid:48) − ≥ − f(2k 1), f (2k 1) 22k 2. We start with the following partial construction. Suppose [G , Σ ] is built and let P = · · · i i uv v v w be a maximal thread. Furthermore, assume that P is either part of a path of 1 2 −r − length 2k 2 connecting a and b or part of a path of length 2k 2 connecting c and d. 8 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof.

text: We

text: consider

text: a

text: ﬁxed

text: signature

text: Σ

text: of

text: [G,

text: Σ].

text: We

text: will

text: use

text: the

text: same

text: notations

text: (P

text: t

text: etc.)

text: xy

text: xy

text: as

text: in

text: Lemma

text: Thus

text: as

text: proved

text: in

text: that

text: lemma,

text: parallel

text: edges

text: of

text: K

text: are

text: subdivided

text: same

text: number

text: of

text: times.

text: Furthermore,

text: repeating

text: the

text: same

text: argument

text: modulo

text: we

text: can

text: conclude

text: that

text: the

text: number

text: of

text: negative

text: edges

text: in

text: P

text: and

text: the

text: number

text: of

text: negative

text: edges

text: in

text: P

text: have

text: same

text: parity

text: xy

text: wz

text: for

text: all

text: x,

text: y,

text: w,

text: z

text: a,

text: b,

text: c,

text: d

text: Let

text: u

text: and

text: v

text: be

text: two

text: vertices

text: from

text: same

text: part

text: of

text: G

text: (thus

text: any

text: path

text: connecting

text: u

text: and

text: v

text: have

text: even

text: length).

text: We

text: would

text: like

text: to

text: prove

text: that

text: they

text: are

text: adjacent

text: in

text: [G,

text: If

text: they

text: belong

text: to

text: a

text: same

text: facial

text: cycle,

text: then

text: the

text: two

text: paths

text: connecting

text: these

text: two

text: vertices

text: in

text: that

text: (unbalanced)

text: cycle

text: satisfy

text: the

text: conditions

text: and

text: we

text: are

text: done.

text: Hence,

text: assume

text: without

text: loss

text: of

text: generality

text: that

text: u

text: P

text: ab

text: and

text: v

text: P

text: cd

text: Removing

text: the

text: edges

text: of

text: the

text: parallel

text: paths

text: P

text: and

text: P

text: will

text: result

text: in

text: a

text: cycle

text: of

text: length

text: ad

text: bc

text: ad

text: containing

text: u,

text: v.

text: This

text: implies:

text: (t

text: t

text: t

text: (t

text: t

text: t

text: ua

text: ac

text: cv

text: ub

text: bd

text: dv

text: min

text: (t

text: t

text: t

text: (t

text: t

text: t

text: ua

text: ac

text: cv

text: ub

text: bd

text: dv

text: Similarly

text: by

text: removing

text: P

text: and

text: P

text: we

text: get

text: ac

text: bd

text: min

text: (t

text: t

text: t

text: (t

text: t

text: t

text: ua

text: ad

text: dv

text: ub

text: bc

text: cv

text: It

text: remains

text: to

text: show

text: that

text: the

text: two

text: paths

text: of

text: equation

text: and

text: have

text: diﬀerent

text: number

text: of

text: negative

text: edges

text: modulo

text: To

text: see

text: this

text: note

text: that

text: union

text: of

text: any

text: one

text: of

text: the

text: two

text: paths

text: from

text: with

text: a

text: path

text: from

text: covers

text: a

text: facial

text: cycle

text: exactly

text: once

text: and

text: one

text: a

text: part

text: of

text: P

text: or

text: P

text: twice.

text: Since

text: each

text: ab

text: cd

text: facial

text: cycle

text: is

text: unbalanced,

text: our

text: claim

text: is

text: proved.

text: We

text: are

text: now

text: ready

text: to

text: present

text: our

text: general

text: construction.

text: Theorem

text: There

text: exists

text: a

text: planar

text: signed

text: bipartite

text: graph

text: [G,

text: Σ]

text: such

text: that

text: in

text: [G,

text: each

text: part

text: of

text: G

text: induces

text: a

text: clique

text: of

text: size

text: at

text: least

text: Proof.

text: Consider

text: a

text: K

text: on

text: four

text: vertices

text: a,

text: b,

text: c

text: and

text: d.

text: Let

text: G

text: be

text: a

text: subdivision

text: of

text: this

text: K

text: where

text: edges

text: ab

text: and

text: cd

text: each

text: are

text: subdivided

text: into

text: edges.

text: Note

text: that

text: G

text: is

text: a

text: connected

text: bipartite

text: graph

text: and

text: let

text: V

text: and

text: V

text: be

text: its

text: partite

text: sets.

text: Let

text: Σ

text: be

text: the

text: signature

text: with

text: the

text: new

text: edge

text: incident

text: to

text: a

text: (created

text: by

text: the

text: subdivision

text: of

text: ab)

text: and

text: the

text: new

text: edge

text: incedent

text: to

text: c

text: (created

text: by

text: the

text: subdivision

text: of

text: cd)

text: being

text: negative.

text: Thus

text: the

text: signed

text: bipartite

text: graph

text: [G

text: Σ

text: is

text: a

text: subdivision

text: of

text: K

text: in

text: which

text: all

text: the

text: four

text: faces

text: are

text: unbalanced

text: cycles

text: of

text: length

text: Hence

text: by

text: Lemma

text: we

text: know

text: that

text: each

text: of

text: V

text: and

text: V

text: induces

text: a

text: clique

text: of

text: order

text: in

text: [G

text: Σ

text: In

text: the

text: following

text: we

text: will

text: build

text: a

text: sequence

text: of

text: signed

text: graphs

text: [G

text: Σ

text: for

text: i

text: i

text: i

text: such

text: that

text: each

text: [G

text: Σ

text: i

text: contains

text: [G

text: Σ

text: as

text: a

text: subgraph.

text: Moreover,

text: the

text: signed

text: i

text: i

text: graph

text: [G

text: Σ

text: is

text: a

text: bipartite

text: planar

text: graph

text: with

text: unbalanced-girth

text: and

text: partite

text: sets

text: V

text: V

text: Let

text: i

text: i

text: i

text: i

text: us

text: denote

text: the

text: clique

text: number

text: of

text: the

text: graph

text: induced

text: by

text: V

text: (or

text: V

text: from

text: [G

text: Σ

text: by

text: f(i)

text: (or

text: i

text: i

text: i

text: i

text: f

text: (i)).

text: Note

text: that

text: both

text: the

text: functions

text: are

text: strictly

text: increasing

text: and

text: at

text: the

text: ﬁnal

text: step

text: we

text: will

text: have

text: f

text: We

text: start

text: with

text: the

text: following

text: partial

text: construction.

text: Suppose

text: [G

text: Σ

text: is

text: built

text: and

text: let

text: P

text: i

text: i

text: uv

text: v

text: v

text: w

text: be

text: a

text: maximal

text: thread.

text: Furthermore,

text: assume

text: that

text: P

text: is

text: either

text: part

text: of

text: a

text: path

text: of

text: −r

text: length

text: connecting

text: a

text: and

text: b

text: or

text: part

text: of

text: a

text: path

text: of

text: length

text: connecting

text: c

text: and

text: d.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##