text: guarantees in the process. III. TERMINOLOGY We collect measurements zR , z1 , . . . , znt of the robot R 1:t 1:t 1:t trajectory fR : t ∈ → X, where X is the joint action sRpace and nt human trajectories f = [f1, . . . , fnt]: t ∈ → X, which are governed by p(fR | zR ) and p(f1 | 1:t zf1 ), . . . , p(fnt | zfnt). We do not assume that every 1:t 1:t measurement of zR and zf in 1 : t is present. We 1:t 1:t use the shorthand zf = [zf1 , . . . , zfnt]; similarly, we let (cid:81) 1:t 1:t 1:t p(f | zf ) = nt p(fi | zfi ). We model both fi and fR 1:t i=1 1:t as stochastic processes. Our robot and pedestrian models are represented in a GP basis (Figure 4): N | N | Fig. 4: Human ambiguity: (fi µfi,Σfi), (fi µfi,Σfi) model R R L L (cid:88)NtR intention to go direction µfRi,µfLi (with preferences wRfi and wLfi). Within p(fR | zR1:t) = w(cid:96)RN(fR | µR(cid:96) , ΣR(cid:96) ), a mode, human has ﬂexibility ΣfRi,L about µfRi,L. Data from [62] (cid:96)=1 (cid:88)Ntfi thewnhoerrme awliz(cid:96),aktio=n co(2efπﬁ)c−ieTn/t2|rΣesR(cid:96)ult+ingΣffkrio|m−1/m2ulatinpdlyiZn(cid:96)g−,k1twios p(fi | zfi ) = wfiN(fi | µfi, Σfi). (III.1) (cid:2) (cid:3) 1:t k k k Gaussians. We note max P(κ) = w . (cid:96),k k=1 In crowd navigation we are interested in the probability of The mixture weights are the likelihood of the data: wR = not colliding P(¬κ) = w − P(κ) = w (1 − Z−1/w ). (cid:96) (cid:96),k (cid:96),k (cid:96),k (cid:96),k N(fR = zR | µR, Σ ) and wfi = N(fi = zfi | µfi, Σfi). To mitigate symbol proliferation, we introduce a shorthand. Although th1:et GPs(cid:96) evo(cid:96)lve at eackh time step, we1:stupprkess tikme Deﬁnition 4: Let N = N(fχ | µχ, Σχ); χ ∈ fχ,σ σ σ in the mean and covariance functions: µ ≡ µ(t) and Σ ≡ {R, 1, . . . , n }, σ ∈ {(cid:96), k}. Thus N = N(f3 | µf3, Σf3). t f3,k k k Σ(t). As an illustration of the GP basis, consider Figure 4 Deﬁnition 5: The operator P is deﬁned as (cid:80) ¬κ and the distribution p(fi | zfi ) = wfiN(fi | (cid:104) (cid:105) µfi, Σfi). If wfi > wfi then a1r:tg max p(kf=iL|,Rzfik) = µfi. P¬κ : NfR,(cid:96)Nfi,k → w(cid:96),k(1 − Z(cid:96)−,k1/w(cid:96),k)NfR,(cid:96)Nfi,k. k k L R h 1:t L Optimization over µfLi can be misleading since µRfi is ig- We deﬁne ΛR,fi ≡ w (1 − Z−1/w ) = P(¬κ). nored. What if the human is debating whether to visit Lenny (cid:96),k (cid:96),k (cid:96),k (cid:96),k Deﬁnition 6: Independent agent planning optimizes a or Rhonda? What if the human is “ﬂexible” in how they decoupled cost function C(fR, f) = C (fR)C (f). intend to travel to Lenny or Rhonda? For crowd navigation to R f Deﬁnition 7: Sampling based motion planning (SBMP) be successful, we must reason over ambiguity and ﬂexibility. draws fR ∼ p(fR | zR ) and f ∼ p(f | We make this precise. k 1:t k Deﬁnition 1: We call µfi, µR human and robot inten- zf1:t), and then computes the optimal joint trajectory k j arg min C({fR, f }N ), where C({fR, f }N ) is some tions. If Ntfi, NtR > 1, intention ambiguity is present. We joint cosftRf,ufnctionk. Ifkwek=c1an sample unifokrmlky fkr=o1m the cost measure intention preference with the weights wfi, wR. E.g, function, then SBMP is a sampling based approximation of k (cid:96) if one weight is large, intention ambiguity is small. the joint distribution Deﬁnition 2: Flexibility is the willingness of an agent to compromise about intention µfi or µR. Mathematically, the (cid:88)N k j p(fR, f | zR , zf ) = δ([fR, f] − [fR, f] ). ﬂexibility of intent µR or µfi is ΣR or Σfi. 1:t 1:t k Flexibility is motivatejd by tkhe follojwing: skuppose an agent Deﬁnition 8 (Convex laneka=p1proach [36]): Convex is unimodal with model N(x | µ, Σ). If the agent intends µ lanes are regions through the crowd with a single strongly (by providing data supporting µ) then Σ is small; optima. The convex lane approach creates a convex lane the agent is Σ unwilling to compromise on µ. If the agent {ψi}mi=1 ∈ X partition, with weights wψi = P(ψi), based has not provided a strong signal supporting µ then Σ is on current pedestrian positions. Inference samples lanes smDalelﬁ. nition 3: The probability of collision of N(fR | ψj ∼ {wψi}mi=1 and then(cid:88)trajectories [fR, f]k ∼ pψj(fR, f): µR(cid:96) , ΣR(cid:96) ) and N(fi | µfki, Σfki) is (see Section 5.2 of [60]) p(fR, f | zR1:t, zf1:t) = wψipψi(fR, f | zR1:t, zf1:t) ψ(cid:88)i∈X (cid:88) (cid:90) P(κ) = N(x | µR, ΣR)N(x | µfi, Σfi)dx = wψiδ([fR, f] − [fR, f]k). (cid:96) (cid:96) k k ψi∈X k∈ψi (cid:104) (cid:105) = w exp − 1(µR − µfi)(cid:62)(ΣR + Σfi)−1(µR − µfi) IV. STATISTICAL PRINCIPLES OF CROWD NAVIGATION (cid:96),k 2 (cid:96) k (cid:96) k (cid:96) k In [61], robot navigation in dense human crowds was ex- = Z−1, (III.2) (cid:96),k plored as a probabilistic inference problem, rather than as a cost minimization problem. This enabled the perspective ##LTFigure## ##LTLine##

text: guarantees

text: in

text: the

text: process.

text: III.

text: TERMINOLOGY

text: We

text: collect

text: measurements

text: zR

text: znt

text: of

text: the

text: robot

text: R

text: trajectory

text: fR

text: t

text: X,

text: where

text: X

text: is

text: the

text: joint

text: action

text: sRpace

text: and

text: nt

text: human

text: trajectories

text: f

text: fnt]:

text: t

text: X,

text: which

text: are

text: governed

text: by

text: p(fR

text: zR

text: and

text: p(fnt

text: zfnt).

text: We

text: do

text: not

text: assume

text: that

text: every

text: measurement

text: of

text: zR

text: and

text: zf

text: in

text: t

text: is

text: present.

text: We

text: use

text: the

text: shorthand

text: zf

text: zfnt];

text: similarly,

text: we

text: let

text: p(f

text: zf

text: nt

text: p(fi

text: zfi

text: We

text: model

text: both

text: fi

text: and

text: fR

text: as

text: stochastic

text: processes.

text: Our

text: robot

text: and

text: pedestrian

text: models

text: are

text: represented

text: in

text: a

text: GP

text: basis

text: (Figure

text: N

text: N

text: Fig.

text: Human

text: ambiguity:

text: (fi

text: µfi,Σfi),

text: (fi

text: µfi,Σfi)

text: model

text: R

text: R

text: L

text: L

text: intention

text: to

text: go

text: direction

text: µfRi,µfLi

text: (with

text: preferences

text: wRfi

text: and

text: wLfi).

text: Within

text: p(fR

text: a

text: mode,

text: human

text: has

text: ﬂexibility

text: ΣfRi,L

text: about

text: µfRi,L.

text: Data

text: from

text: thewnhoerrme

text: p(fi

text: zfi

text: wfiN(fi

text: µfi,

text: Σfi).

text: k

text: k

text: k

text: Gaussians.

text: We

text: note

text: max

text: P(κ)

text: w

text: In

text: crowd

text: navigation

text: we

text: are

text: interested

text: in

text: the

text: probability

text: of

text: The

text: mixture

text: weights

text: are

text: the

text: likelihood

text: of

text: the

text: data:

text: wR

text: not

text: colliding

text: P(¬κ)

text: w

text: P(κ)

text: w

text: N(fR

text: zR

text: µR,

text: Σ

text: and

text: wfi

text: N(fi

text: zfi

text: µfi,

text: Σfi).

text: To

text: mitigate

text: symbol

text: proliferation,

text: we

text: introduce

text: a

text: shorthand.

text: Although

text: at

text: eackh

text: time

text: step,

text: tikme

text: Deﬁnition

text: Let

text: N

text: N(fχ

text: µχ,

text: Σχ);

text: χ

text: fχ,σ

text: σ

text: σ

text: in

text: the

text: mean

text: and

text: covariance

text: functions:

text: µ

text: µ(t)

text: and

text: Σ

text: {R,

text: n

text: σ

text: k}.

text: Thus

text: N

text: t

text: k

text: k

text: Σ(t).

text: As

text: an

text: illustration

text: of

text: the

text: GP

text: basis,

text: consider

text: Figure

text: Deﬁnition

text: The

text: operator

text: P

text: is

text: deﬁned

text: as

text: ¬κ

text: and

text: the

text: distribution

text: p(fi

text: zfi

text: wfiN(fi

text: µfi,

text: Σfi).

text: If

text: wfi

text: wfi

text: then

text: max

text: p(kf=iL|,Rzfik)

text: µfi.

text: P¬κ

text: k

text: k

text: L

text: R

text: h

text: L

text: Optimization

text: over

text: µfLi

text: can

text: be

text: misleading

text: since

text: µRfi

text: is

text: ig-

text: We

text: deﬁne

text: ΛR,fi

text: w

text: P(¬κ).

text: nored.

text: What

text: if

text: the

text: human

text: is

text: debating

text: whether

text: to

text: visit

text: Lenny

text: Deﬁnition

text: Independent

text: agent

text: planning

text: optimizes

text: a

text: or

text: Rhonda?

text: What

text: if

text: the

text: human

text: is

text: “ﬂexible”

text: in

text: how

text: they

text: decoupled

text: cost

text: function

text: C(fR,

text: f)

text: C

text: (fR)C

text: (f).

text: intend

text: to

text: travel

text: to

text: Lenny

text: or

text: Rhonda?

text: For

text: crowd

text: navigation

text: to

text: R

text: f

text: Deﬁnition

text: Sampling

text: based

text: motion

text: planning

text: (SBMP)

text: be

text: successful,

text: we

text: must

text: reason

text: over

text: ambiguity

text: and

text: ﬂexibility.

text: draws

text: fR

text: p(fR

text: zR

text: and

text: f

text: p(f

text: We

text: make

text: this

text: precise.

text: k

text: k

text: Deﬁnition

text: We

text: call

text: µfi,

text: µR

text: human

text: and

text: robot

text: inten-

text: and

text: then

text: computes

text: the

text: optimal

text: joint

text: trajectory

text: k

text: j

text: arg

text: min

text: C({fR,

text: f

text: }N

text: where

text: C({fR,

text: f

text: }N

text: is

text: some

text: tions.

text: If

text: Ntfi,

text: NtR

text: intention

text: ambiguity

text: is

text: present.

text: We

text: joint

text: cosftRf,ufnctionk.

text: sample

text: unifokrmlky

text: the

text: cost

text: measure

text: intention

text: preference

text: with

text: the

text: weights

text: wfi,

text: wR.

text: E.g,

text: function,

text: then

text: SBMP

text: is

text: a

text: sampling

text: based

text: approximation

text: of

text: k

text: if

text: one

text: weight

text: is

text: large,

text: intention

text: ambiguity

text: is

text: small.

text: the

text: joint

text: distribution

text: Deﬁnition

text: Flexibility

text: is

text: the

text: willingness

text: of

text: an

text: agent

text: to

text: compromise

text: about

text: intention

text: µfi

text: or

text: µR.

text: Mathematically,

text: the

text: k

text: j

text: p(fR,

text: f

text: zR

text: zf

text: δ([fR,

text: f]

text: [fR,

text: f]

text: ﬂexibility

text: of

text: intent

text: µR

text: or

text: µfi

text: is

text: ΣR

text: or

text: Σfi.

text: k

text: Flexibility

text: is

text: motivatejd

text: by

text: tkhe

text: follojwing:

text: skuppose

text: an

text: agent

text: Deﬁnition

text: (Convex

text: Convex

text: is

text: unimodal

text: with

text: model

text: N(x

text: µ,

text: Σ).

text: If

text: the

text: agent

text: intends

text: µ

text: lanes

text: are

text: regions

text: through

text: the

text: crowd

text: with

text: a

text: single

text: strongly

text: (by

text: providing

text: data

text: supporting

text: µ)

text: then

text: Σ

text: is

text: small;

text: optima.

text: The

text: convex

text: lane

text: approach

text: creates

text: a

text: convex

text: lane

text: the

text: agent

text: is

text: Σ

text: unwilling

text: to

text: compromise

text: on

text: µ.

text: If

text: the

text: agent

text: X

text: partition,

text: with

text: weights

text: wψi

text: P(ψi),

text: based

text: has

text: not

text: provided

text: a

text: strong

text: signal

text: supporting

text: µ

text: then

text: Σ

text: is

text: on

text: current

text: pedestrian

text: positions.

text: Inference

text: samples

text: lanes

text: smDalelﬁ.

text: nition

text: The

text: probability

text: of

text: collision

text: of

text: N(fR

text: ψj

text: and

text: [fR,

text: f]k

text: pψj(fR,

text: f):

text: and

text: N(fi

text: µfki,

text: Σfki)

text: is

text: (see

text: Section

text: of

text: p(fR,

text: f

text: wψipψi(fR,

text: f

text: P(κ)

text: N(x

text: µR,

text: ΣR)N(x

text: µfi,

text: Σfi)dx

text: wψiδ([fR,

text: f]

text: [fR,

text: f]k).

text: k

text: k

text: ψi∈X

text: k∈ψi

text: w

text: exp

text: µfi)

text: IV.

text: STATISTICAL

text: PRINCIPLES

text: OF

text: CROWD

text: NAVIGATION

text: k

text: k

text: k

text: In

text: robot

text: navigation

text: in

text: dense

text: human

text: crowds

text: was

text: ex-

text: plored

text: as

text: a

text: probabilistic

text: inference

text: problem,

text: rather

text: than

text: as

text: a

text: cost

text: minimization

text: problem.

text: This

text: enabled

text: the

text: perspective

text: ##LTFigure##

text: ##LTLine##


text: parcels dubbed “lobes”, which give rise to lobe dynamics [29, 33] as a mechanism for transport across periodically varying invariant manifolds. In the autonomous setting, the concept of almost-invariant sets, introduced in [9] and further developed in [16, 13] uses the transfer (or Perron-Frobenius) operator to ﬁnd regions in phase space which are either invariant, or in the absence of any open invariant sets, as close to invariant as possible. Such sets decompose the phase space into regions which are as dynamically disconnected as possible, and between which transport is minimized. Related approaches to ﬁnding “ergodic partitions” in phase space have also been developed using long orbits [31] or using the Koopman operator [5], the dual of the transfer operator. In the case of nonautonomous, aperiodic dynamics, the notion of almost-invariant sets was generalized to coherent sets [19] and shortly thereafter to ﬁnite-time coherent sets [22, 14]. While almost-invariant sets remain ﬁxed in phase space, when the underlying governing dynamics is time-varying, it is essential to allow sets that are parameterised by time. Nevertheless, the underlying idea, minimising mixing with the surrounding phase space, is common to both almost-invariant and ﬁnite-time coherent sets. As in the case of almost-invariant sets, one numerically constructs a transfer operator for the duration of the dynamics to be considered. This transfer operator will push forward densities over the chosen time interval. After some straightforward normalising procedures, one computes the subdominant singular spectrum and singular vectors of the transfer operator, which indicate the presence and location of ﬁnite-time coherent sets. This construction relies on a small amount of diﬀusion being present in the dynamics; this diﬀusion can be part of the model, or if the underlying dynamics is purely advective it can be easily numerically induced. An equivalent deﬁnition of ﬁnite-time coherent sets was introduced in [15], speciﬁcally aimed at the case of purely advective dynamics. The underlying goal is to determine co-dimension 1 manifolds whose size remains small relative to enclosed1 volume, under evolution by the dynamics. This idea extends the classical (static) isoperimetric problem [4] of determining the co-dimension 1 manifold with least size given a ﬁxed enclosed volume. The idea to deﬁne ﬁnite-time coherent sets as those sets with boundaries that have dynamically minimal size relative to enclosed volume is consistent with the minimal L2-mixing approach of [14] because if small-amplitude diﬀusion is added, L2 mixing can only occur along the boundary interfaces between coherent regions. This fact has been formally established in [15] in the volume-preserving setting and [18] in the non-volume- preserving case. The persistently minimal size of the boundary of ﬁnite-time coherent sets in this sense is also broadly consistent with the approach of [26], although [26] is limited to two-dimensions and closed curves. Related work [27] uses a time-dependent metric (with corresponding time-dependent diﬀusion) induced by the advective ﬂow to deﬁne coherent sets as almost-invariant sets in the material manifold. In approximating the time dependent metric by a single one they end up with a similar operator as the dynamic Laplacian in [15, 18]. Numerical implementation of the method of [15] requires approximation of eigenfunc- 1The boundary of the domain may take part in the enclosing. 2 ##LTLine##

text: parcels

label: paragraph

text: dubbed

text: “lobes”,

text: which

text: give

text: rise

text: to

text: lobe

text: dynamics

text: as

text: a

text: mechanism

text: for

text: transport

text: across

text: periodically

text: varying

text: invariant

text: manifolds.

text: In

text: the

text: autonomous

text: setting,

text: the

text: concept

text: of

text: almost-invariant

text: sets,

text: introduced

text: in

text: and

text: further

text: developed

text: in

text: uses

text: the

text: transfer

text: (or

text: Perron-Frobenius)

text: operator

text: to

text: ﬁnd

text: regions

text: in

text: phase

text: space

text: which

text: are

text: either

text: invariant,

text: or

text: in

text: the

text: absence

text: of

text: any

text: open

text: invariant

text: sets,

text: as

text: close

text: to

text: invariant

text: as

text: possible.

text: Such

text: sets

text: decompose

text: the

text: phase

text: space

text: into

text: regions

text: which

text: are

text: as

text: dynamically

text: disconnected

text: as

text: possible,

text: and

text: between

text: which

text: transport

text: is

text: minimized.

text: Related

text: approaches

text: to

text: ﬁnding

text: “ergodic

text: partitions”

text: in

text: phase

text: space

text: have

text: also

text: been

text: developed

text: using

text: long

text: orbits

text: or

text: using

text: the

text: Koopman

text: operator

text: the

text: dual

text: of

text: the

text: transfer

text: operator.

text: In

text: the

text: case

text: of

text: nonautonomous,

text: aperiodic

text: dynamics,

text: the

text: notion

text: of

text: almost-invariant

text: sets

text: was

text: generalized

text: to

text: coherent

text: sets

text: and

text: shortly

text: thereafter

text: to

text: ﬁnite-time

text: coherent

text: sets

text: While

text: almost-invariant

text: sets

text: remain

text: ﬁxed

text: in

text: phase

text: space,

text: when

text: the

text: underlying

text: governing

text: dynamics

text: is

text: time-varying,

text: it

text: is

text: essential

text: to

text: allow

text: sets

text: that

text: are

text: parameterised

text: by

text: time.

text: Nevertheless,

text: the

text: underlying

text: idea,

text: minimising

text: mixing

text: with

text: the

text: surrounding

text: phase

text: space,

text: is

text: common

text: to

text: both

text: almost-invariant

text: and

text: ﬁnite-time

text: coherent

text: sets.

text: As

text: in

text: the

text: case

text: of

text: almost-invariant

text: sets,

text: one

text: numerically

text: constructs

text: a

text: transfer

text: operator

text: for

text: the

text: duration

text: of

text: the

text: dynamics

text: to

text: be

text: considered.

text: This

text: transfer

text: operator

text: will

text: push

text: forward

text: densities

text: over

text: the

text: chosen

text: time

text: interval.

text: After

text: some

text: straightforward

text: normalising

text: procedures,

text: one

text: computes

text: the

text: subdominant

text: singular

text: spectrum

text: and

text: singular

text: vectors

text: of

text: the

text: transfer

text: operator,

text: which

text: indicate

text: the

text: presence

text: and

text: location

text: of

text: ﬁnite-time

text: coherent

text: sets.

text: This

text: construction

text: relies

text: on

text: a

text: small

text: amount

text: of

text: diﬀusion

text: being

text: present

text: in

text: the

text: dynamics;

text: this

text: diﬀusion

text: can

text: be

text: part

text: of

text: the

text: model,

text: or

text: if

text: the

text: underlying

text: dynamics

text: is

text: purely

text: advective

text: it

text: can

text: be

text: easily

text: numerically

text: induced.

text: An

text: equivalent

text: deﬁnition

text: of

text: ﬁnite-time

text: coherent

text: sets

text: was

text: introduced

text: in

text: speciﬁcally

text: aimed

text: at

text: the

text: case

text: of

text: purely

text: advective

text: dynamics.

text: The

text: underlying

text: goal

text: is

text: to

text: determine

text: co-dimension

text: manifolds

text: whose

text: size

text: remains

text: small

text: relative

text: to

text: volume,

text: under

text: evolution

text: by

text: the

text: dynamics.

text: This

text: idea

text: extends

text: the

text: classical

text: (static)

text: isoperimetric

text: problem

text: of

text: determining

text: the

text: co-dimension

text: manifold

text: with

text: least

text: size

text: given

text: a

text: ﬁxed

text: enclosed

text: volume.

text: The

text: idea

text: to

text: deﬁne

text: ﬁnite-time

text: coherent

text: sets

text: as

text: those

text: sets

text: with

text: boundaries

text: that

text: have

text: dynamically

text: minimal

text: size

text: relative

text: to

text: enclosed

text: volume

text: is

text: consistent

text: with

text: the

text: minimal

text: approach

text: of

text: because

text: if

text: small-amplitude

text: diﬀusion

text: is

text: added,

text: mixing

text: can

text: only

text: occur

text: along

text: the

text: boundary

text: interfaces

text: between

text: coherent

text: regions.

text: This

text: fact

text: has

text: been

text: formally

text: established

text: in

text: in

text: the

text: volume-preserving

text: setting

text: and

text: in

text: the

text: non-volume-

text: preserving

text: case.

text: The

text: persistently

text: minimal

text: size

text: of

text: the

text: boundary

text: of

text: ﬁnite-time

text: coherent

text: sets

text: in

text: this

text: sense

text: is

text: also

text: broadly

text: consistent

text: with

text: the

text: approach

text: of

text: although

text: is

text: limited

text: to

text: two-dimensions

text: and

text: closed

text: curves.

text: Related

text: work

text: uses

text: a

text: time-dependent

text: metric

text: (with

text: corresponding

text: time-dependent

text: diﬀusion)

text: induced

text: by

text: the

text: advective

text: ﬂow

text: to

text: deﬁne

text: coherent

text: sets

text: as

text: almost-invariant

text: sets

text: in

text: the

text: material

text: manifold.

text: In

text: approximating

text: the

text: time

text: dependent

text: metric

text: by

text: a

text: single

text: one

text: they

text: end

text: up

text: with

text: a

text: similar

text: operator

text: as

text: the

text: dynamic

text: Laplacian

text: in

text: Numerical

text: implementation

text: of

text: the

text: method

text: of

text: requires

text: approximation

text: of

text: eigenfunc-

text: boundary

text: of

text: the

text: domain

text: may

text: take

text: part

text: in

text: the

text: enclosing.

text: ##LTLine##


text: becomes strongly distorted and ﬁlamented. In this situation, we are not interested in co- herent sets that intersect this heavily ﬁlamented boundary and so we restrict to coherent sets in the interior of the domain. This can be achieved by replacing the (natural) homo- geneous Neumann boundary conditions with homogeneous Dirichlet boundary conditions. In terms of numerical eigenvector computations, to apply homogeneous Dirichlet bound- ary conditions, one simply sets all rows and columns of Dˆt and M in (13) corresponding to nodes on the boundary of the domain to rows and columns of zeros. × Cauchy-Green approach. As in [23], we use a uniform grid of 250 150 points, the associated Delaunay triangulation, yielding roughly 73000 triangles and Gauss quadrature − of degree 1 (i.e. one quadrature point per element). The evaluation of C 1 takes ca. 46 s, t the assembly of the matrices 0.3 s and the solution of the eigenproblem 3 seconds. T Figure 16 (left) shows the largest 10 eigenvalues of the dynamic Laplacian with = { } t , t + 90 , the results do not change signiﬁcantly when using more intermediate time 0 0 steps. Note that there appears to be a gap after the third eigenvalue. Figure 17 (left column) shows the associated ﬁrst three eigenvectors. The corresponding coherent sets (as identiﬁed by k-means clustering the ﬁrst three eigenvectors, cf. Fig. 18, left) nicely agree with those identiﬁed in [23], Fig. 9 (the rightmost vortex from Fig. 9 in that work appears in a lower eigenfunction which we do not show here). We deliberately chose the same resolution as in [23] here, the results for the leading three eigenvectors do not change signiﬁcantly, however, when decreasing the grid resolu- × tion down to 100 60 points only. Figure 16: Ocean ﬂow: spectrum of the dynamic Laplacian using the Cauchy-Green approach (left) and the adaptive transfer operator approach (right). Adaptive transfer operator approach. The approach from Section yields compa- rable results as shown in the right columns of Fig. 16. The computation times are: time integration: 4 s, assembly: 1.4 s, solution of the eigenproblem: 16 seconds. We can × decrease the resolution down to a 150 90 grid before the results start to deteriorate signiﬁcantly. Missing data. We ﬁnally analyze how well the coherent sets can be recovered in the ocean ﬂow experiment when data is missing. Again, we use the same set of nodes and 27 ##LTFigure## ##LTFigure##

text: becomes

text: strongly

text: distorted

text: and

text: ﬁlamented.

text: In

text: this

text: situation,

text: we

text: are

text: not

text: interested

text: in

text: co-

text: herent

text: sets

text: that

text: intersect

text: this

text: heavily

text: ﬁlamented

text: boundary

text: and

text: so

text: we

text: restrict

text: to

text: coherent

text: sets

text: in

text: the

text: interior

text: of

text: the

text: domain.

text: This

text: can

text: be

text: achieved

text: by

text: replacing

text: the

text: (natural)

text: homo-

text: geneous

text: Neumann

text: boundary

text: conditions

text: with

text: homogeneous

text: Dirichlet

text: boundary

text: conditions.

text: In

text: terms

text: of

text: numerical

text: eigenvector

text: computations,

text: to

text: apply

text: homogeneous

text: Dirichlet

text: bound-

text: ary

text: conditions,

text: one

text: simply

text: sets

text: all

text: rows

text: and

text: columns

text: of

text: Dˆt

text: and

text: M

text: in

text: corresponding

text: to

text: nodes

text: on

text: the

text: boundary

text: of

text: the

text: domain

text: to

text: rows

text: and

text: columns

text: of

text: zeros.

text: Cauchy-Green

text: approach.

text: As

text: in

text: we

text: use

text: a

text: uniform

text: grid

text: of

text: points,

text: the

text: associated

text: Delaunay

text: triangulation,

text: yielding

text: roughly

text: triangles

text: and

text: Gauss

text: quadrature

text: of

text: degree

text: (i.e.

text: one

text: quadrature

text: point

text: per

text: element).

text: The

text: evaluation

text: of

text: C

text: takes

text: ca.

text: s,

text: t

text: the

text: assembly

text: of

text: the

text: matrices

text: s

text: and

text: the

text: solution

text: of

text: the

text: eigenproblem

text: seconds.

text: T

text: Figure

text: (left)

text: shows

text: the

text: largest

text: eigenvalues

text: of

text: the

text: dynamic

text: Laplacian

text: with

text: t

text: t

text: the

text: results

text: do

text: not

text: change

text: signiﬁcantly

text: when

text: using

text: more

text: intermediate

text: time

text: steps.

text: Note

text: that

text: there

text: appears

text: to

text: be

text: a

text: gap

text: after

text: the

text: third

text: eigenvalue.

text: Figure

text: (left

text: column)

text: shows

text: the

text: associated

text: ﬁrst

text: three

text: eigenvectors.

text: The

text: corresponding

text: coherent

text: sets

text: (as

text: identiﬁed

text: by

text: k-means

text: clustering

text: the

text: ﬁrst

text: three

text: eigenvectors,

text: cf.

text: Fig.

text: left)

text: nicely

text: agree

text: with

text: those

text: identiﬁed

text: in

text: Fig.

text: (the

text: rightmost

text: vortex

text: from

text: Fig.

text: in

text: that

text: work

text: appears

text: in

text: a

text: lower

text: eigenfunction

text: which

text: we

text: do

text: not

text: show

text: here).

text: We

text: deliberately

text: chose

text: the

text: same

text: resolution

text: as

text: in

text: here,

text: the

text: results

text: for

text: the

text: leading

text: three

text: eigenvectors

text: do

text: not

text: change

text: signiﬁcantly,

text: however,

text: when

text: decreasing

text: the

text: grid

text: resolu-

text: tion

text: down

text: to

text: points

text: only.

text: Figure

text: Ocean

text: ﬂow:

text: spectrum

text: of

text: the

text: dynamic

text: Laplacian

text: using

text: the

text: Cauchy-Green

text: approach

text: (left)

text: and

text: the

text: adaptive

text: transfer

text: operator

text: approach

text: (right).

text: Adaptive

text: transfer

text: operator

text: approach.

text: The

text: approach

text: from

text: Section

text: yields

text: compa-

text: rable

text: results

text: as

text: shown

text: in

text: the

text: right

text: columns

text: of

text: Fig.

text: The

text: computation

text: times

text: are:

text: time

text: integration:

text: s,

text: assembly:

text: s,

text: solution

text: of

text: the

text: eigenproblem:

text: seconds.

text: We

text: can

text: decrease

text: the

text: resolution

text: down

text: to

text: a

text: grid

text: before

text: the

text: results

text: start

text: to

text: deteriorate

text: signiﬁcantly.

text: Missing

text: data.

text: We

text: ﬁnally

text: analyze

text: how

text: well

text: the

text: coherent

text: sets

text: can

text: be

text: recovered

text: in

text: the

text: ocean

text: ﬂow

text: experiment

text: when

text: data

text: is

text: missing.

text: Again,

text: we

text: use

text: the

text: same

text: set

text: of

text: nodes

text: and

text: ##LTFigure##

text: ##LTFigure##


text: Note that we have completely eliminated any consideration of the boundary. If we want to have a continuous-time version of the above eigenproblem, we simply replace the sum ∈ T over t with an integral. A related discussion for the case of T not volume preserving is given in the appendix. 2.2 The dynamic Laplacian with Dirichlet boundary conditions In some situations, one may wish to restrict coherent sets to the class of submanifolds M that do not intersect the boundary of (which is assumed to be nonempty, otherwise one uses the setting of Section ). We will illustrate one such possibility in Section , where an initial rectangular ocean domain becomes highly distorted. An appropriate isoperimetric ⊂ M problem in this setting is to search for an open submanifold A int( ) with compact closure, an∈d Twith an evolving boundary Φ(cid:80)t(∂A) that remains small relative to the volume of A for t . This can be achieved by modifying the expression (1) to |T1| ∈T (cid:96) − (Φt(∂A)) t d 1 h (A) := , (6) d (cid:96)(A) and deﬁning the dynamic (Dirichlet) Cheeger constant h by d { M ∞ } h := min h(A) : A open, submanifold of int( ), compact closure, C boundary . d (7) ⊂ M We will call the minimising A int( ) t(cid:80)he dominant ﬁnite-time coherent set. The corresponding version of the (Dirichlet) Sobolev constant is: (cid:107)∇ (cid:107) |T1| ∈T (Φt∗f) t 1 s := inf (cid:107) (cid:107) , (8) d f∈Cc∞(M,R) f 1 ∞ M R where C ( , ) denotes the set of non-identically vanishing, compactly supported, ∞ c M C real-valued functions on int( ). One can prove a dynamic (Dirichlet) Federer- Fleming theorem: M R ∞ Theorem 1. Let be a compact subset of d with nonempty C boundary, and h and d s deﬁned as in (7) and (8), respectively. Then h = s . d d d Proof. In the setting of T volume-preserving, this result follows from the obvious modiﬁ- cations to the proof of Theorem 3.1 [15]. The solution of the L2 version of the L1 optimisation problem (8) is given by the (cid:32) (cid:33) eigenfunction of the eigenproblem (9)–(10) corresponding to the largest eigenvalue λ < 0. (cid:88) 1 1 ∗ M |T | (Φt) ∆Φt∗ v = λv on int( ), (9) ∈T t M v = 0 on ∂ (10) 7 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Note

text: that

text: we

text: have

text: completely

text: eliminated

text: any

text: consideration

text: of

text: the

text: boundary.

text: If

text: we

text: want

text: to

text: have

text: a

text: continuous-time

text: version

text: of

text: the

text: above

text: eigenproblem,

text: we

text: simply

text: replace

text: the

text: sum

text: T

text: over

text: t

text: with

text: an

text: integral.

text: A

text: related

text: discussion

text: for

text: the

text: case

text: of

text: T

text: not

text: volume

text: preserving

text: is

text: given

text: in

text: the

text: appendix.

label: section

text: The

text: dynamic

text: Laplacian

text: with

text: Dirichlet

text: boundary

text: conditions

text: In

text: some

text: situations,

text: one

text: may

text: wish

text: to

text: restrict

text: coherent

text: sets

text: to

text: the

text: class

text: of

text: submanifolds

text: M

text: that

text: do

text: not

text: intersect

text: the

text: boundary

text: of

text: (which

text: is

text: assumed

text: to

text: be

text: nonempty,

text: otherwise

text: one

text: uses

text: the

text: setting

text: of

text: Section

text: We

text: will

text: illustrate

text: one

text: such

text: possibility

text: in

text: Section

text: where

text: an

text: initial

text: rectangular

text: ocean

text: domain

text: becomes

text: highly

text: distorted.

text: An

text: appropriate

text: isoperimetric

text: M

text: problem

text: in

text: this

text: setting

text: is

text: to

text: search

text: for

text: an

text: open

text: submanifold

text: A

text: int(

text: with

text: compact

text: closure,

text: an∈d

text: Twith

text: an

text: evolving

text: boundary

text: that

text: remains

text: small

text: relative

text: to

text: the

text: volume

text: of

text: A

text: for

text: t

text: This

text: can

text: be

text: achieved

text: by

text: modifying

text: the

text: expression

text: to

text: ∈T

text: (Φt(∂A))

text: t

text: d

text: h

text: (A)

text: d

text: and

text: deﬁning

text: the

text: dynamic

text: (Dirichlet)

text: Cheeger

text: constant

text: h

text: by

text: d

text: M

text: h

text: min

text: h(A)

text: A

text: open,

text: submanifold

text: of

text: int(

text: compact

text: closure,

text: C

text: boundary

text: d

text: M

text: We

text: will

text: call

text: the

text: minimising

text: A

text: int(

text: dominant

text: ﬁnite-time

text: coherent

text: set.

text: The

text: corresponding

text: version

text: of

text: the

text: (Dirichlet)

text: Sobolev

text: constant

text: is:

text: ∈T

text: (Φt∗f)

text: t

text: s

text: inf

text: d

text: f∈Cc∞(M,R)

text: f

text: M

text: R

text: where

text: C

text: denotes

text: the

text: set

text: of

text: non-identically

text: vanishing,

text: compactly

text: supported,

text: c

text: M

text: C

text: real-valued

text: functions

text: on

text: int(

text: One

text: can

text: prove

text: a

text: dynamic

text: (Dirichlet)

text: Federer-

text: Fleming

text: theorem:

text: M

text: R

text: Theorem

text: Let

text: be

text: a

text: compact

text: subset

text: of

text: d

text: with

text: nonempty

text: C

text: boundary,

text: and

text: h

text: and

text: d

text: s

text: deﬁned

text: as

text: in

text: and

text: respectively.

text: Then

text: h

text: s

text: d

text: d

text: d

text: Proof.

text: In

text: the

text: setting

text: of

text: T

text: volume-preserving,

text: this

text: result

text: follows

text: from

text: the

text: obvious

text: modiﬁ-

text: cations

text: to

text: the

text: proof

text: of

text: Theorem

text: The

text: solution

text: of

text: the

text: version

text: of

text: the

text: optimisation

text: problem

text: is

text: given

text: by

text: the

text: eigenfunction

text: of

text: the

text: eigenproblem

text: corresponding

text: to

text: the

text: largest

text: eigenvalue

text: λ

text: M

text: |T

text: (Φt)

text: ∆Φt∗

text: v

text: λv

text: on

text: int(

text: ∈T

text: t

text: M

text: v

text: on

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Note that in comparison to (4), we have simply added the Dirichlet condition (10), and thus the left-hand-side of (9) is the dynamic Laplace operator acting on a function v, and this operator is elliptic and self-adjoint as in the Neumann boundary condition case. In this Dirichlet case, we also have a dynamic Cheeger inequality relating h to λ . d 1 Theorem 2. Let M be a com√pact subset of Rd with nonempty C∞ boundary, and h be ≤ − d deﬁned as in (7). Then h 2λ , where λ is the largest eigenvalue of (9)–(10). d 1 1 Proof. In the setting of T volume-preserving, this follows from the obvious modiﬁcations to the proof of Theorem 3.2 [15]. The weak form of the eigenproblem (9)–(10) is identical to the weak form (5), except M M that we replace(cid:90)the space of test functions H1( (cid:90) ) with H1( ). (cid:88) 0 − 1 ∇ • ∇ ∈ M |T | (Φt∗v) (Φt∗ψ) d(cid:96) = λ vψ d(cid:96), for all ψ H1( ). (11) M M 0 ∈T Φt( ) t In terms of heat ﬂow (cf. [27]), one interprets the Dirichlet boundary conditions as M “refrigeration” ﬁxed at temperature zero on the boundary of . The eigenfunction φ M 1 corresponding to λ is strictly positive (by convention) in the interior of and φ is 1 ∈ T 1 designed so that on average (over t ) the rate of heat loss through the evolving M ∈ T boundaries Φt( ), t is minimised. This is in contrast to the previous Neumann (no ﬂux) boundary conditions of Section , where the second eigenfunction describes a signed heat distribution that approaches the constant equilibrium heat distribution at the slowest ∈ T average rate (again averaged over t ). 3 Finite Element discretization We are going to use a Ritz-Galerkin discretization of the weak eigenproblem (5) and a ﬁnite element basis for the underlying ansatz and test function spaces. As mentioned in the introduction, one particular advantage of this approach is that if we choose the same basis for the ansatz and the test function space then we end up with symmetric stiﬀness and mass matrices, i.e. we inherit the self-adjointness of the dynamic Laplacian. ⊂ M (cid:80) Let V 0 H1( ) be a ﬁnite-dimensional subspace with basis ϕ0, . . . , ϕ0. For brevity, n 1 n we write ϕi = ϕ0i in∈ tChe following(cid:32). The∈discre(cid:33)te eigenproblem corresponding to (5) is to ﬁnd pairs (λ, v), λ , v = n u ϕ (cid:88)V 0, such that i=1 i i n − 1 |T | Dˆt u = λMu, (12) ∈T t ∈ C where u = (u , . . . , u )T n, 1 n 8 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Note

text: that

text: in

text: comparison

text: to

text: we

text: have

text: simply

text: added

text: the

text: Dirichlet

text: condition

text: and

text: thus

text: the

text: left-hand-side

text: of

text: is

text: the

text: dynamic

text: Laplace

text: operator

text: acting

text: on

text: a

text: function

text: v,

text: and

text: this

text: operator

text: is

text: elliptic

text: and

text: self-adjoint

text: as

text: in

text: the

text: Neumann

text: boundary

text: condition

text: case.

text: In

text: this

text: Dirichlet

text: case,

text: we

text: also

text: have

text: a

text: dynamic

text: Cheeger

text: inequality

text: relating

text: h

text: to

text: λ

text: d

text: Theorem

text: Let

text: M

text: be

text: a

text: com√pact

text: subset

text: of

text: Rd

text: with

text: nonempty

text: C∞

text: boundary,

text: and

text: h

text: be

text: d

text: deﬁned

text: as

text: in

text: Then

text: h

text: 2λ

text: where

text: λ

text: is

text: the

text: largest

text: eigenvalue

text: of

text: d

text: Proof.

text: In

text: the

text: setting

text: of

text: T

text: volume-preserving,

text: this

text: follows

text: from

text: the

text: obvious

text: modiﬁcations

text: to

text: the

text: proof

text: of

text: Theorem

text: The

text: weak

text: form

text: of

text: the

text: eigenproblem

text: is

text: identical

text: to

text: the

text: weak

text: form

text: except

text: M

text: M

text: that

text: we

text: space

text: of

text: test

text: functions

text: with

text: M

text: |T

text: (Φt∗v)

text: (Φt∗ψ)

text: λ

text: vψ

text: for

text: all

text: ψ

text: M

text: M

text: ∈T

text: Φt(

text: t

text: In

text: terms

text: of

text: heat

text: ﬂow

text: (cf.

text: one

text: interprets

text: the

text: Dirichlet

text: boundary

text: conditions

text: as

text: M

text: “refrigeration”

text: ﬁxed

text: at

text: temperature

text: zero

text: on

text: the

text: boundary

text: of

text: The

text: eigenfunction

text: φ

text: M

text: corresponding

text: to

text: λ

text: is

text: strictly

text: positive

text: (by

text: convention)

text: in

text: the

text: interior

text: of

text: and

text: φ

text: is

text: T

text: designed

text: so

text: that

text: on

text: average

text: (over

text: t

text: the

text: rate

text: of

text: heat

text: loss

text: through

text: the

text: evolving

text: M

text: T

text: boundaries

text: Φt(

text: t

text: is

text: minimised.

text: This

text: is

text: in

text: contrast

text: to

text: the

text: previous

text: Neumann

text: (no

text: ﬂux)

text: boundary

text: conditions

text: of

text: Section

text: where

text: the

text: second

text: eigenfunction

text: describes

text: a

text: signed

text: heat

text: distribution

text: that

text: approaches

text: the

text: constant

text: equilibrium

text: heat

text: distribution

text: at

text: the

text: slowest

text: T

text: average

text: rate

text: (again

text: averaged

text: over

text: t

text: Finite

text: Element

text: discretization

text: We

text: are

text: going

text: to

text: use

text: a

text: Ritz-Galerkin

text: discretization

text: of

text: the

text: weak

text: eigenproblem

text: and

text: a

text: ﬁnite

text: element

text: basis

text: for

text: the

text: underlying

text: ansatz

text: and

text: test

text: function

text: spaces.

text: As

text: mentioned

text: in

text: the

text: introduction,

text: one

text: particular

text: advantage

text: of

text: this

text: approach

text: is

text: that

text: if

text: we

text: choose

text: the

text: same

text: basis

text: for

text: the

text: ansatz

text: and

text: the

text: test

text: function

text: space

text: then

text: we

text: end

text: up

text: with

text: symmetric

text: stiﬀness

text: and

text: mass

text: matrices,

text: i.e.

text: we

text: inherit

text: the

text: self-adjointness

text: of

text: the

text: dynamic

text: Laplacian.

text: M

text: Let

text: V

text: be

text: a

text: ﬁnite-dimensional

text: subspace

text: with

text: basis

text: For

text: brevity,

text: n

text: n

text: we

text: write

text: ϕi

text: in∈

text: tChe

text: eigenproblem

text: corresponding

text: to

text: is

text: to

text: ﬁnd

text: pairs

text: (λ,

text: v),

text: λ

text: v

text: n

text: u

text: ϕ

text: such

text: that

text: i

text: i

text: n

text: |T

text: Dˆt

text: u

text: λMu,

text: ∈T

text: t

text: C

text: where

text: u

text: (u

text: u

text: )T

text: n,

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: A QUANTIFIED TAUBERIAN THEOREM AND LOCAL DECAY OF C0-SEMIGROUPS 11 · ∈ · ∈ Therefore w (c )mf Lp for some c > 0 implies that w (cc )mf Lp. (M2)K2 1 1 MK 1 The proof of Theorem 1.1 is complete. Proof of Lemma 3.1. Let us begin with the easier part (a). Hadamard’s formula (cid:13) (cid:13) ⊃ ∈ ssh=(cid:13)(cid:13)(cid:13)ow(cid:61)szt.(cid:13)(cid:13)(cid:13)hTathe((cid:13)(cid:13)(cid:13)(cid:13)n1(cid:88)6) implies that fˆ is a(cid:13)(cid:13)(cid:13)(cid:13)naly(cid:88)tic in ΩM2 ΩM(cid:18)1. Let(cid:19)z ΩM1 and let (cid:13) ∞ (cid:13) ∞ − 1 − ≤ 1 ε j − fˆ(z) = fˆ(j)(is)(z is)j K (s)M (s)j = ε 1K (s). j! 2 2 M (s) 2 2 j=0 j=0 ∈ R | | | | Let us now prove part (b). Let us ﬁx s , let r = 1/M ( s +1/M( s )) and let 1 γ be the positively oriented circle of radius r around is in the complex plane. Note C that γ is indeed included in the closure of the union of Ω and . Let γ and γ− be the intersection of γ(cid:34)w(cid:90)ith C(cid:90) an(cid:35)d C−, respect(cid:18)ively. MB1y Cauc(cid:19)h+y’s formu+la we + have − j! fˆ(z) (z is)2 fˆ(j)(is) = + − 1 + dz 2πi (z is)k+1 r2 γ− γ+ =: j! [I− + I ] . + (cid:13) (cid:13) Let us ﬁrst estimate I−: (cid:13) (cid:13) (cid:13) (cid:13) (cid:107) (cid:107) ≤ 1 (cid:18)· − − (cid:19) ·(cid:18) · (cid:19) I− r j 1 sup fˆ(z) πr 2 2π z∈γ− ≤ | | 1 | | 1 j (17) K s + | | M s + | | . 1 M ( s ) 1 M ( s ) (cid:16) (cid:17) 1 1 (cid:32) (cid:33) (cid:90) (cid:90) (cid:88) Let us now estimate I : + 1 + (z−is)2 m−1 ∞ I+ = 2(cid:88)1πi (z − isr)2j+1 z−j−1f(k)(0) + z−m e−ztf(m)(t)dt dz γ+ k=0 0 − m 1 =: I + I +,k +,m k=0 − ∈ It is an easy exercise to show that the integral of e rtcos(θ) cos(θ) over θ (π/2, π/2) − can be estimated from above (cid:90)by a(cid:90)constant times ((rt)2(cid:13)+ 1) 1.(cid:13) Therefore by | | (cid:13) (cid:13) H¨older’s inequality we get for large s (cid:13) (cid:13) ∞ (cid:107)I (cid:107) ≤ | | C (cid:13)(cid:13) π2 e(cid:13)(cid:13)−rtcos(θ) cos(θ)dθ f(m)(t) dt +,m s m rj+1 (cid:13) − (cid:13) 0 π 2 ≤ (cid:13) C (cid:13) |s|(cid:13)m rj+2(cid:13)−1/p f(m) Lp ≤ C f(m) | | | | − | | Lp M ( s + 1/M ( s ))j+2 1/p. s m 1 1 A similar (and easier) estimate is true for the other summands I . This together +,k (cid:3) with (17) yields the claim. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: A

text: QUANTIFIED

text: TAUBERIAN

text: THEOREM

text: AND

text: LOCAL

text: DECAY

text: OF

text: Therefore

text: w

text: (c

text: )mf

text: Lp

text: for

text: some

text: c

text: implies

text: that

text: w

text: (cc

text: )mf

text: Lp.

text: MK

text: The

text: proof

text: of

text: Theorem

text: is

text: complete.

text: Proof

text: of

text: Lemma

text: Let

text: us

text: begin

text: with

text: the

text: easier

text: part

text: (a).

text: Hadamard’s

text: formula

text: implies

text: that

text: fˆ

text: is

text: in

text: and

text: let

text: ε

text: j

text: fˆ(z)

text: fˆ(j)(is)(z

text: is)j

text: K

text: (s)M

text: (s)j

text: ε

text: (s).

text: j!

text: M

text: (s)

text: R

text: Let

text: us

text: now

text: prove

text: part

text: (b).

text: Let

text: us

text: ﬁx

text: s

text: let

text: r

text: s

text: s

text: and

text: let

text: γ

text: be

text: the

text: positively

text: oriented

text: circle

text: of

text: radius

text: r

text: around

text: is

text: in

text: the

text: complex

text: plane.

text: Note

text: C

text: that

text: γ

text: is

text: indeed

text: included

text: in

text: the

text: closure

text: of

text: the

text: union

text: of

text: Ω

text: and

text: Let

text: γ

text: and

text: γ−

text: be

text: the

text: intersection

text: of

text: C−,

text: formu+la

text: we

text: have

text: j!

text: fˆ(z)

text: (z

text: fˆ(j)(is)

text: dz

text: (z

text: γ−

text: γ+

text: j!

text: [I−

text: I

text: Let

text: us

text: ﬁrst

text: estimate

text: I−:

text: I−

text: r

text: j

text: sup

text: fˆ(z)

text: πr

text: 2π

text: z∈γ−

text: j

text: K

text: s

text: M

text: s

text: M

text: s

text: M

text: s

text: Let

text: us

text: now

text: estimate

text: I

text: I+

text: (z

text: z−m

text: e−ztf(m)(t)dt

text: dz

text: γ+

text: m

text: I

text: I

text: +,k

text: +,m

text: It

text: is

text: an

text: easy

text: exercise

text: to

text: show

text: that

text: the

text: integral

text: of

text: e

text: rtcos(θ)

text: cos(θ)

text: over

text: θ

text: can

text: be

text: estimated

text: from

text: above

text: times

text: Therefore

text: by

text: H¨older’s

text: inequality

text: we

text: get

text: for

text: large

text: s

text: C

text: π2

text: cos(θ)dθ

text: f(m)(t)

text: dt

text: +,m

text: s

text: m

text: π

text: C

text: f(m)

text: Lp

text: C

text: f(m)

text: Lp

text: M

text: s

text: s

text: s

text: m

text: A

text: similar

text: (and

text: easier)

text: estimate

text: is

text: true

text: for

text: the

text: other

text: summands

text: I

text: This

text: together

text: +,k

text: with

text: yields

text: the

text: claim.

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: 14 REINHARD STAHN L ≤ Part 1: Estimation of µ. We distinguish the two cases t A and t > A. ≤ Case 1: t A. We calculate (cid:88) L τ k − µ(t) = qjet(w+A(cid:18) 1q(cid:19)j) (cid:88) (cid:88) R j=0 ∞ τ 1 t m k = etw (cid:88) q(m+1)j (cid:18) (cid:19) R m! A m=0 j=0 ∞ − τ · (k + 1)tk · k! t (n 1)(k+1) = etw − R Akk! (n(k + 1) 1)! A n=1 τ · · =: I II. R Clearly II is bounded from below by 1 and bounded from above by a constant (cid:18) (cid:19) which does not depend on k or A. Thus by Stirling’s formula we get √ L ≥ τ − eδt k µ(t) c ke δt . R δAk As a function in t we can maximize the right-hand side by setting δt = k. If we furthermore deﬁne √1 (24) τ = (δA)k k we see that (23) is proved. Since II is boun(cid:18)ded fro(cid:19)m above we have √ L ≤ τ − eδt k (25) µ(t) C ke δt . R δAk Again we maximize the right-hand side by(cid:16)sett(cid:17)ing δt = k and plugging in (24). This leads to √ L ≤ τ − e k ≤ C µ(t) C ke k R δA R ∈ For t [k/2δ, 2k/δ] this is already what we want to have in (22). ≤ Case 1.1: δt k/2. In this case the maximum in (25) with respect to t is (cid:16) (cid:17) (cid:16) (cid:17) attained for δt = k/2. This yields √ |L | ≤ τ − e k C e k ≤ ε µ(t) C ke k2 = 2 R 2δA R 4 R ≤ The last inequality holds for suﬃciently large k. We proved (22) for δt k/2. ≤ ≤ − ≤ Case 1.2: 2k δt δA. Condition (i) from Theorem 4.1 yields M 1(c t) K 1 eδt/α for any α > 0 as long as t is large enough. Thus, if we multiply (25) by ##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: REINHARD

text: STAHN

text: L

text: Part

text: Estimation

text: of

text: µ.

text: We

text: distinguish

text: the

text: two

text: cases

text: t

text: A

text: and

text: t

text: A.

text: Case

text: t

text: A.

text: We

text: calculate

text: L

text: τ

text: k

text: µ(t)

text: R

text: τ

text: t

text: m

text: k

text: etw

text: R

text: m!

text: A

text: τ

text: (k

text: k!

text: t

text: (n

text: etw

text: R

text: Akk!

text: (n(k

text: A

text: τ

text: I

text: II.

text: R

text: Clearly

text: II

text: is

text: bounded

text: from

text: below

text: by

text: and

text: bounded

text: from

text: above

text: by

text: a

text: constant

text: which

text: does

text: not

text: depend

text: on

text: k

text: or

text: A.

text: Thus

text: by

text: Stirling’s

text: formula

text: we

text: get

text: L

text: τ

text: eδt

text: k

text: µ(t)

text: c

text: ke

text: δt

text: R

text: δAk

text: As

text: a

text: function

text: in

text: t

text: we

text: can

text: maximize

text: the

text: right-hand

text: side

text: by

text: setting

text: δt

text: k.

text: If

text: we

text: furthermore

text: deﬁne

text: √1

text: τ

text: (δA)k

text: k

text: we

text: see

text: that

text: is

text: proved.

text: Since

text: II

text: is

text: above

text: we

text: have

text: L

text: τ

text: eδt

text: k

text: µ(t)

text: C

text: ke

text: δt

text: R

text: δAk

text: Again

text: we

text: maximize

text: the

text: right-hand

text: side

text: δt

text: k

text: and

text: plugging

text: in

text: This

text: leads

text: to

text: L

text: τ

text: e

text: k

text: C

text: µ(t)

text: C

text: ke

text: k

text: R

text: δA

text: R

text: For

text: t

text: this

text: is

text: already

text: what

text: we

text: want

text: to

text: have

text: in

text: Case

text: δt

text: In

text: this

text: case

text: the

text: maximum

text: in

text: with

text: respect

text: to

text: t

text: is

text: attained

text: for

text: δt

text: This

text: yields

text: |L

text: τ

text: e

text: k

text: C

text: e

text: k

text: ε

text: µ(t)

text: C

text: ke

text: R

text: R

text: R

text: The

text: last

text: inequality

text: holds

text: for

text: suﬃciently

text: large

text: k.

text: We

text: proved

text: for

text: δt

text: Case

text: δt

text: δA.

text: Condition

text: (i)

text: from

text: Theorem

text: yields

text: M

text: t)

text: K

text: eδt/α

text: for

text: any

text: α

text: as

text: long

text: as

text: t

text: is

text: large

text: enough.

text: Thus,

text: if

text: we

text: multiply

text: by

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: 16 REINHARD STAHN |(cid:61) − | Now it is not diﬃcult to prove (20) for z R > 2δ. The latter condition | − | |(cid:61) − | implies z w > 2δ. Thus, using (26) we get for z R > 2δ and k large: √ |C | ≤ τ − − ≤ C k − ≤ µ(z) C kA(2δA) k 1 2 k ε. R δR |(cid:61) − | | − | ≥ − (cid:61) If we don’t have z R > 2δ we can merely estimate z w δ 1/M( z). ∈ |(cid:61) − | This yields for z Ω with z R > 2δ and for all γ > 1 M 1 |C | ≤ τ − 1 − − µ(z) C kA(δA(1 (cid:61) )) k 1 R√ δM( z) ≤ C k δ√R eγ1 δMk((cid:61)z) ≤ C (cid:112)k eγ1N(2δ)δMk(R) δR ≤ C γ1N(2δ) δR MK(R)K(R) c1 . − ≥ − From the ﬁrst to the second line we use the inequality 1 x e γ1x which is ≥ valid for small x 0. If M is bounded we choose δ large enough to make use of this inequality. From the second to the third line we used condition (ii) from Theorem 4.1. Choosing γ = γ N(2δ) we get (20). Concerning Remark 4.4 a reverse (cid:61) 1 inequality for z = R can be proved analogously but in an even simpler way by − ≤ − ≥ using the inequality 1 x e x which is valid for all x 0. L(cid:48) L Part 3: Estimation of µ. Finally we want to estimate the derivative of µ. ≥ Case 1: t A. In this case we directly get for large k |L(cid:48) | ≤ τ − − − − µ(t) (k + 1)(R + A 1)e (δ A 1)t R√ ≤ k − ≤ C (δA)kRe δA ε. R (cid:88) L Case 2: t < A. Let us ﬁrst get a diﬀerent representation of µ: L(cid:48) τ k − − µ(t) = qj(w + (cid:18)A 1(cid:19)qj)e(w+A 1qj)t (cid:88) (cid:88) R j=0 ∞ τ 1 t m k − = etw (cid:88) (wq(m+1)j +(cid:18)A (cid:19)1q(m+2)j) (cid:20) (cid:21) R m! A m=0 j=0 ∞ − − w (k + 1)tk k! t (n 1)(k+1) n(k + 1) 1 = τetw − 1 + . R Akk! (n(k + 1) 1)! A wt n=1 Note that if t > t > 0 the sum at the end of the calculation is bounded by a 0 constant which only depends on t . (cid:18) (cid:19) (cid:20) (cid:21) 0 √ |L(cid:48) | ≤ (cid:18)− (cid:19)eδ(cid:20)t k (cid:21) k µ(t) Cτ ke δt 1 + δAk Rt ≤ − eδt k k (27) Ce δt 1 + k Rt ##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: REINHARD

text: STAHN

text: Now

text: it

text: is

text: not

text: diﬃcult

text: to

text: prove

text: for

text: z

text: R

text: The

text: latter

text: condition

text: implies

text: z

text: w

text: Thus,

text: using

text: we

text: get

text: for

text: z

text: R

text: 2δ

text: and

text: k

text: large:

text: |C

text: τ

text: C

text: k

text: µ(z)

text: C

text: k

text: k

text: ε.

text: R

text: δR

text: If

text: we

text: don’t

text: have

text: z

text: R

text: 2δ

text: we

text: can

text: merely

text: estimate

text: z

text: w

text: δ

text: z).

text: This

text: yields

text: for

text: z

text: Ω

text: with

text: z

text: R

text: 2δ

text: and

text: for

text: all

text: γ

text: M

text: |C

text: τ

text: µ(z)

text: C

text: k

text: R√

text: δM(

text: z)

text: C

text: k

text: δ√R

text: C

text: δR

text: C

text: δR

text: MK(R)K(R)

text: From

text: the

text: ﬁrst

text: to

text: the

text: second

text: line

text: we

text: use

text: the

text: inequality

text: x

text: e

text: which

text: is

text: valid

text: for

text: small

text: x

text: If

text: M

text: is

text: bounded

text: we

text: choose

text: δ

text: large

text: enough

text: to

text: make

text: use

text: of

text: this

text: inequality.

text: From

text: the

text: second

text: to

text: the

text: third

text: line

text: we

text: used

text: condition

text: (ii)

text: from

text: Theorem

text: Choosing

text: γ

text: γ

text: we

text: get

text: Concerning

text: Remark

text: a

text: reverse

text: inequality

text: for

text: z

text: R

text: can

text: be

text: proved

text: analogously

text: but

text: in

text: an

text: even

text: simpler

text: way

text: by

text: using

text: the

text: inequality

text: x

text: e

text: x

text: which

text: is

text: valid

text: for

text: all

text: x

text: L

text: Part

text: Estimation

text: of

text: µ.

text: Finally

text: we

text: want

text: to

text: estimate

text: the

text: derivative

text: of

text: µ.

text: Case

text: t

text: A.

text: In

text: this

text: case

text: we

text: directly

text: get

text: for

text: large

text: k

text: τ

text: µ(t)

text: (k

text: A

text: (δ

text: A

text: R√

text: k

text: C

text: (δA)kRe

text: δA

text: ε.

text: R

text: L

text: Case

text: t

text: A.

text: Let

text: us

text: ﬁrst

text: get

text: a

text: diﬀerent

text: representation

text: of

text: µ:

text: τ

text: k

text: µ(t)

text: qj(w

text: R

text: τ

text: t

text: m

text: k

text: etw

text: R

text: m!

text: A

text: w

text: (k

text: k!

text: t

text: (n

text: n(k

text: τetw

text: R

text: Akk!

text: (n(k

text: A

text: wt

text: Note

text: that

text: if

text: t

text: t

text: the

text: sum

text: at

text: the

text: end

text: of

text: the

text: calculation

text: is

text: bounded

text: by

text: a

text: constant

text: which

text: only

text: depends

text: on

text: t

text: k

text: k

text: µ(t)

text: Cτ

text: ke

text: δt

text: δAk

text: Rt

text: eδt

text: k

text: k

text: Ce

text: δt

text: k

text: Rt

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: 2 JULIEN MELLERAY ⊂ Theorem. Let X be a Cantor space. Assume that K P(X) is compact and convex; all elements of K are atomless and have full support; and K satisﬁes the Glasner–Weiss condition. Then K is approximately divisible (hence K is a dynamical simplex). This theorem is obtained as a corollary of the following result, which is of inde- pendent interest. Theorem. Let X be a Cantor space, and G be a group of homeomorphisms of X such that each G-orbit is dense. Then the set of all G-invariant Borel probability measures on X is approximately divisible. The proof of this result is similar in spirit to some of the arguments used in [IM]. A more novel aspect of the work presented here is that we exploit a connec- tion between dynamical simplices and Fra¨ısse´ theory, which enables us to build interesting examples. Along those lines, we obtain a new and rather elementary proof of a well-known theorem of Downarowicz. Theorem (Downarowicz [D]). For any metrizable Choquet simplex K, there exists a minimal homeomorphism ϕ of a Cantor space X such that K is afﬁnely homeomorphic to the set of all ϕ-invariant Borel probability measures on X. An interesting aspect of the construction used to prove this result is its ﬂexibil- ity; we exploit this to prove the following theorem. Theorem. There exist two dynamical simplices K, L of a Cantor space X, and home- ∈ ⊂ ⊂ omorphisms g, h Homeo(X) such that g∗K L and h∗L K, yet there is no ∈ f Homeo(X) such that f∗K = L. This answers a question recently raised by Ash [A] and shows that the relation of speedup equivalence is strictly coarser than the relation of orbit equivalence. The paper is organized as follows: we ﬁrst prove that approximate divisibility is redundant in the characterization of dynamical simplices. Then we outline some basics of Fra¨ısse´ theory and explain why this theory is relevant to the study of dy- namical simplices. We exploit that connection to prove Downarowicz’s theorem on realizability of Choquet simplices as dynamical simplices, and adapt this con- struction to show that there exist minimal homeomorphisms which are speedup equivalent but not orbit equivalent. Acknowledgements. The research presented here was partially supported by ANR project GAMME (ANR-14-CE25-0004). I am grateful to T. Ibarluc´ıa for valu- able corrections, comments and suggestions about the ﬁrst draft of this paper. 2. APPROXIMATE DIVISIBILITY OF SIMPLICES OF INVARIANT MEASURES Throughout this section X stands for a Cantor space, and P(X) denotes the space of Borel probability measures on X, with its usual topology (induced by the (cid:55)→ maps µ µ(A) as A runs over all clopen subsets of X). Our objective in this sec- tion is to prove the following theorem, and then deduce from it that approximate divisibility is redundant in the characterization of a dynamical simplex. Theorem 2.1. Let G be a group of homeomorphisms of a Cantor space X such that each G-orbit is dense. Then the set K of all G-invariant Borel probability measures on X is G approximately divisible. For the remainder of this section, we ﬁx G as above.

font: LCWWRY+URWPalladioL-Roma

text: JULIEN

text: MELLERAY

text: Theorem.

font: YVONQE+URWPalladioL-Bold

text: Let

font: ROVZLS+URWPalladioL-Ital

text: X

text: be

text: a

text: Cantor

text: space.

text: Assume

text: that

text: K

text: P(X)

text: is

text: compact

text: and

text: convex;

text: all

text: elements

text: of

text: K

text: are

text: atomless

text: and

text: have

text: full

text: support;

text: and

text: K

text: satisﬁes

text: the

text: Glasner–Weiss

text: condition.

text: Then

text: K

text: is

text: approximately

text: divisible

text: (hence

text: K

text: is

text: a

text: dynamical

text: simplex).

text: This

text: theorem

text: is

text: obtained

text: as

text: a

text: corollary

text: of

text: the

text: following

text: result,

text: which

text: is

text: of

text: inde-

text: pendent

text: interest.

text: Theorem.

text: Let

text: X

text: be

text: a

text: Cantor

text: space,

text: and

text: G

text: be

text: a

text: group

text: of

text: homeomorphisms

text: of

text: X

text: such

text: that

text: each

text: G-orbit

text: is

text: dense.

text: Then

text: the

text: set

text: of

text: all

text: G-invariant

text: Borel

text: probability

text: measures

text: on

text: X

text: is

text: approximately

text: divisible.

text: The

text: proof

text: of

text: this

text: result

text: is

text: similar

text: in

text: spirit

text: to

text: some

text: of

text: the

text: arguments

text: used

text: in

text: [IM].

text: A

text: more

text: novel

text: aspect

text: of

text: the

text: work

text: presented

text: here

text: is

text: that

text: we

text: exploit

text: a

text: connec-

text: tion

text: between

text: dynamical

text: simplices

text: and

text: Fra¨ısse´

text: theory,

text: which

text: enables

text: us

text: to

text: build

text: interesting

text: examples.

text: Along

text: those

text: lines,

text: we

text: obtain

text: a

text: new

text: and

text: rather

text: elementary

text: proof

text: of

text: a

text: well-known

text: theorem

text: of

text: Downarowicz.

text: Theorem

text: (Downarowicz

text: [D]).

text: For

text: any

text: metrizable

text: Choquet

text: simplex

text: K,

text: there

text: exists

text: a

text: minimal

text: homeomorphism

text: ϕ

text: of

text: a

text: Cantor

text: space

text: X

text: such

text: that

text: K

text: is

text: afﬁnely

text: homeomorphic

text: to

text: the

text: set

text: of

text: all

text: ϕ-invariant

text: Borel

text: probability

text: measures

text: on

text: X.

text: An

text: interesting

text: aspect

text: of

text: the

text: construction

text: used

text: to

text: prove

text: this

text: result

text: is

text: its

text: ﬂexibil-

text: ity;

text: we

text: exploit

text: this

text: to

text: prove

text: the

text: following

text: theorem.

text: Theorem.

text: There

text: exist

text: two

text: dynamical

text: simplices

text: K,

text: L

text: of

text: a

text: Cantor

text: space

text: X,

text: and

text: home-

text: omorphisms

text: g,

text: h

text: Homeo(X)

text: such

text: that

text: g∗K

text: L

text: and

text: h∗L

text: K,

text: yet

text: there

text: is

text: no

text: f

text: Homeo(X)

text: such

text: that

text: f∗K

text: L.

text: This

text: answers

text: a

text: question

text: recently

text: raised

text: by

text: Ash

text: [A]

text: and

text: shows

text: that

text: the

text: relation

text: of

text: speedup

text: equivalence

text: is

text: strictly

text: coarser

text: than

text: the

text: relation

text: of

text: orbit

text: equivalence.

text: The

text: paper

text: is

text: organized

text: as

text: follows:

text: we

text: ﬁrst

text: prove

text: that

text: approximate

text: divisibility

text: is

text: redundant

text: in

text: the

text: characterization

text: of

text: dynamical

text: simplices.

text: Then

text: we

text: outline

text: some

text: basics

text: of

text: Fra¨ısse´

text: theory

text: and

text: explain

text: why

text: this

text: theory

text: is

text: relevant

text: to

text: the

text: study

text: of

text: dy-

text: namical

text: simplices.

text: We

text: exploit

text: that

text: connection

text: to

text: prove

text: Downarowicz’s

text: theorem

text: on

text: realizability

text: of

text: Choquet

text: simplices

text: as

text: dynamical

text: simplices,

text: and

text: adapt

text: this

text: con-

text: struction

text: to

text: show

text: that

text: there

text: exist

text: minimal

text: homeomorphisms

text: which

text: are

text: speedup

text: equivalent

text: but

text: not

text: orbit

text: equivalent.

text: Acknowledgements.

text: The

text: research

text: presented

text: here

text: was

text: partially

text: supported

text: by

text: ANR

text: project

text: GAMME

text: I

text: am

text: grateful

text: to

text: T.

text: Ibarluc´ıa

text: for

text: valu-

text: able

text: corrections,

text: comments

text: and

text: suggestions

text: about

text: the

text: ﬁrst

text: draft

text: of

text: this

text: paper.

text: APPROXIMATE

text: DIVISIBILITY

text: OF

text: SIMPLICES

text: OF

text: INVARIANT

text: MEASURES

text: Throughout

text: this

text: section

text: X

text: stands

text: for

text: a

text: Cantor

text: space,

text: and

text: P(X)

text: denotes

text: the

text: space

text: of

text: Borel

text: probability

text: measures

text: on

text: X,

text: with

text: its

text: usual

text: topology

text: (induced

text: by

text: the

text: maps

text: µ

text: µ(A)

text: as

text: A

text: runs

text: over

text: all

text: clopen

text: subsets

text: of

text: X).

text: Our

text: objective

text: in

text: this

text: sec-

text: tion

text: is

text: to

text: prove

text: the

text: following

text: theorem,

text: and

text: then

text: deduce

text: from

text: it

text: that

text: approximate

text: divisibility

text: is

text: redundant

text: in

text: the

text: characterization

text: of

text: a

text: dynamical

text: simplex.

text: Theorem

text: Let

text: G

text: be

text: a

text: group

text: of

text: homeomorphisms

text: of

text: a

text: Cantor

text: space

text: X

text: such

text: that

text: each

text: G-orbit

text: is

text: dense.

text: Then

text: the

text: set

text: K

text: of

text: all

text: G-invariant

text: Borel

text: probability

text: measures

text: on

text: X

text: is

text: G

text: approximately

text: divisible.

text: For

text: the

text: remainder

text: of

text: this

text: section,

text: we

text: ﬁx

text: G

text: as

text: above.


text: 12 JULIEN MELLERAY We move on towards proving Theorem 5.8. Starting from Q, R as in the state- ment of the theorem, we ﬁrst assume that R is a closed face of Q and pick an afﬁne continuous injection g of Q into itself such that g(Q) is a closed face of R. ∈ ∈ Note that, given any f A(Q)+, we may deﬁne h A(g(Q))+ by setting 1 1 h(g(q)) = f (q). Then, using Proposition 5.9 we can extend h to A(Q)+. We just ∈ ∈ 1 ◦ proved that, for any f A(Q)+, there exists h A(Q)+ such that h g = f. 1 1 ⊂ Granting that, we may again apply a closure argument to ﬁnd F A(Q) such that: • F is a countable dense Q-vector subspace which contains the constant func- tion 1. • F satisﬁes the ﬁnite sum property. • F satisﬁes both the (R, Q)-extension property and the (g(Q), Q)-extension property. • { ◦ ∈ } f g: f F+ = F+. 1 1 We then run the same construction as in the proof of Theorem 4.4, considering L ∈ K ∈ again the class consisting of all A such that for all nonzero a A the map (cid:55)→ Q q µq(a) belongs to F1+. We denote by MQ the Fra¨ısse´ limit of this class, view its underlying Boolean algebra as the clopen algebra of a Cantor space XL and again → L (cid:55)→ denote by Φ: Q S( ) thLe afﬁne hoLmeomorphism q µq. We consider the classes (resp. ) obtained by taking restrictions of ele- L R g(Q) meLnts of to R (resp. g(Q)); that is, whenever AQL= (A, (µq)q∈Q) is an elLement of , we obtain an element AR = (A, (µr))r∈R ofL R, and all elements of R are obtained in this way (and, of course, similarly for ). g(Q) L L Lemma 5.12. The classes and have the amalgamation property. R g(Q) L Proof. We only write down the argument for , the other one is identical. As R in the proof of Proposition 4.3, showing that the amalgamation property holds L ∈ reduces to proving that, whene∈ver (A, (µr))r∈R belongs to R, a A is a nonzero atom and f , . . . , f , g , . . . , g F+ are such that 1 n 1 m 1 ∀ ∈ ∑n ∑m r R µr(a) = fi(r) = gj(r) i=1 j=1 ∈ there exists h F+ such that i,j 1 ∀ ∑m ∀ ∑n i hi,j|R = fi|R and j hi,j|R = gj|R . j=1 i=1 To prove that this is true, ﬁrst apply the (R, Q)-extension property of F to f, f1, . . .(cid:3)fn and f, g , . . . , g , then use the fact that F has the ﬁnite sum property. 1 m Let MR, Mg(Q) denote the structures (Clopen(XL), (µr)r∈R) and (Clopen(XL), (µg(q))q∈Q). L L Lemma 5.13. M (resp. M ) is the Fra¨ısse´ limit of (resp. ). R g(Q) R g(Q) Proof. The (R, Q)-extension property of F and the Fra¨ısse´ property of MQ combine to show that M has the Fra¨ısse´ property. Indeed, let A be a ﬁnite algebra of R → ∈ L clopen subsets of XL, and pick an embedding α: A B R. For each atom a of A, we let (bia)i∈Ia denote the atoms of∈B which are contained in α(a). The measures of each bia correspond to maps fia F1+ such that ∑i∈Ia fia(r) = µa(r) for

text: JULIEN

text: MELLERAY

text: We

text: move

text: on

text: towards

text: proving

text: Theorem

text: Starting

text: from

text: Q,

text: R

text: as

text: in

text: the

text: state-

text: ment

text: of

text: the

text: theorem,

text: we

text: ﬁrst

text: assume

text: that

text: R

text: is

text: a

text: closed

text: face

text: of

text: Q

text: and

text: pick

text: an

text: afﬁne

text: continuous

text: injection

text: g

text: of

text: Q

text: into

text: itself

text: such

text: that

text: g(Q)

text: is

text: a

text: closed

text: face

text: of

text: R.

text: Note

text: that,

text: given

text: any

text: f

text: A(Q)+,

text: we

text: may

text: deﬁne

text: h

text: A(g(Q))+

text: by

text: setting

text: h(g(q))

text: f

text: (q).

text: Then,

text: using

text: Proposition

text: we

text: can

text: extend

text: h

text: to

text: A(Q)+.

text: We

text: just

text: proved

text: that,

text: for

text: any

text: f

text: A(Q)+,

text: there

text: exists

text: h

text: A(Q)+

text: such

text: that

text: h

text: g

text: f.

text: Granting

text: that,

text: we

text: may

text: again

text: apply

text: a

text: closure

text: argument

text: to

text: ﬁnd

text: F

text: A(Q)

text: such

text: that:

text: F

text: is

text: a

text: countable

text: dense

text: Q-vector

text: subspace

text: which

text: contains

text: the

text: constant

text: func-

text: tion

text: F

text: satisﬁes

text: the

text: ﬁnite

text: sum

text: property.

text: F

text: satisﬁes

text: both

text: the

text: (R,

text: Q)-extension

text: property

text: and

text: the

text: (g(Q),

text: Q)-extension

text: property.

text: f

text: g:

text: f

text: F+

text: F+.

text: We

text: then

text: run

text: the

text: same

text: construction

text: as

text: in

text: the

text: proof

text: of

text: Theorem

text: considering

text: L

text: K

text: again

text: the

text: class

text: consisting

text: of

text: all

text: A

text: such

text: that

text: for

text: all

text: nonzero

text: a

text: A

text: the

text: map

text: Q

text: q

text: µq(a)

text: belongs

text: to

text: We

text: denote

text: by

text: MQ

text: the

text: Fra¨ısse´

text: limit

text: of

text: this

text: class,

text: view

text: its

text: underlying

text: Boolean

text: algebra

text: as

text: the

text: clopen

text: algebra

text: of

text: a

text: Cantor

text: space

text: XL

text: and

text: again

text: L

text: denote

text: by

text: Φ:

text: Q

text: S(

text: thLe

text: afﬁne

text: hoLmeomorphism

text: q

text: µq.

text: We

text: consider

text: the

text: classes

text: (resp.

text: obtained

text: by

text: taking

text: restrictions

text: of

text: ele-

text: L

text: R

text: g(Q)

text: meLnts

text: of

text: to

text: R

text: (resp.

text: g(Q));

text: that

text: is,

text: whenever

text: AQL=

text: (A,

text: (µq)q∈Q)

text: is

text: an

text: elLement

text: of

text: we

text: obtain

text: an

text: element

text: AR

text: (A,

text: (µr))r∈R

text: ofL

text: R,

text: and

text: all

text: elements

text: of

text: R

text: are

text: obtained

text: in

text: this

text: way

text: (and,

text: of

text: course,

text: similarly

text: for

text: g(Q)

text: L

text: L

text: Lemma

text: The

text: classes

text: and

text: have

text: the

text: amalgamation

text: property.

text: R

text: g(Q)

text: L

text: Proof.

text: We

text: only

text: write

text: down

text: the

text: argument

text: for

text: the

text: other

text: one

text: is

text: identical.

text: As

text: R

text: in

text: the

text: proof

text: of

text: Proposition

text: showing

text: that

text: the

text: amalgamation

text: property

text: holds

text: L

text: reduces

text: to

text: proving

text: that,

text: whene∈ver

text: (A,

text: (µr))r∈R

text: belongs

text: to

text: R,

text: a

text: A

text: is

text: a

text: nonzero

text: atom

text: and

text: f

text: f

text: g

text: g

text: F+

text: are

text: such

text: that

text: n

text: m

text: ∑n

text: ∑m

text: r

text: R

text: µr(a)

text: fi(r)

text: gj(r)

text: there

text: exists

text: h

text: F+

text: such

text: that

text: i,j

text: ∑m

text: ∑n

text: i

text: hi,j|R

text: fi|R

text: and

text: j

text: hi,j|R

text: gj|R

text: To

text: prove

text: that

text: this

text: is

text: true,

text: ﬁrst

text: apply

text: the

text: (R,

text: Q)-extension

text: property

text: of

text: F

text: to

text: f,

text: and

text: f,

text: g

text: g

text: then

text: use

text: the

text: fact

text: that

text: F

text: has

text: the

text: ﬁnite

text: sum

text: property.

text: m

text: Let

text: MR,

text: Mg(Q)

text: denote

text: the

text: structures

text: (Clopen(XL),

text: (µr)r∈R)

text: and

text: (Clopen(XL),

text: (µg(q))q∈Q).

text: L

text: L

text: Lemma

text: M

text: (resp.

text: M

text: is

text: the

text: Fra¨ısse´

text: limit

text: of

text: (resp.

text: R

text: g(Q)

text: R

text: g(Q)

text: Proof.

text: The

text: (R,

text: Q)-extension

text: property

text: of

text: F

text: and

text: the

text: Fra¨ısse´

text: property

text: of

text: MQ

text: combine

text: to

text: show

text: that

text: M

text: has

text: the

text: Fra¨ısse´

text: property.

text: Indeed,

text: let

text: A

text: be

text: a

text: ﬁnite

text: algebra

text: of

text: R

text: L

text: clopen

text: subsets

text: of

text: XL,

text: and

text: pick

text: an

text: embedding

text: α:

text: A

text: B

text: R.

text: For

text: each

text: atom

text: a

text: of

text: A,

text: we

text: let

text: (bia)i∈Ia

text: denote

text: the

text: atoms

text: of∈B

text: which

text: are

text: contained

text: in

text: α(a).

text: The

text: measures

text: of

text: each

text: bia

text: correspond

text: to

text: maps

text: fia

text: such

text: that

text: ∑i∈Ia

text: fia(r)

text: µa(r)

text: for


text: 4 JULIEN MELLERAY Lemma 2.4. Fix an integer N, and assume that A, B are clopen subsets such that there exists a N-dividing partition of A and a N-dividing partition of B. Then there is a N- ∪ dividing partition of A B. Proof. By induction on the number of columns of the N-dividing partition of B, it is enough to consider the cas≥e where it is of the form (V0, h1(V0), . . . , hm(V0)) for some clopen V and some m N. Using the previous lemma m times, we produce 0 U N-dividing partitions which reﬁne U, and clopen sets W contained in V such i i 0 that • U U ⊆ • For all i <≤ m, i+1 reﬁnes i aUnd Wi+1 Wi; • For all i ≤ m the elementsUof i do not intersect Wi, h1(Wi), . . . , hi(W∪i); For all i m the union of i and (Wi, h1(Wi), . . . , hm(Wi)) covers A B. U In the end, m is disjoint from (Wm, h1(Wm), .U. . , hm(Wm)), so we may just add (Wm, h1(Wm), .∪. . , hm(Wm)) as a new column to m to obtain the desired N-dividin(cid:3)g partition of A B. Proposition 2.5. For any integer N and any clopen A there exists a N-dividing partition of A. ∈ Proof. Since by assumption the G-orbit of any x A is dense, its intersection with (cid:51) A is inﬁnite and we may ﬁnd some clopen subset U x and elements g , . . . , g 0 1 N of G such that U0, g1(U0), . . . , gN(U0) are disjoint and contained in A. Thus there exists a covering of A by clopen sets which can each be covered by a N-dividing partition, and by compactness there exists such a covering which is ﬁnite. Then (cid:3) we obtain the desired N-dividing partition of A from Lemma 2.4. Proof of Theorem 2.1. Fix a nonempty clopen subset A of X, an integer n and ε > 0. Then pick a N-dividing partition of A for some N > n; let us denote it as before by ε ∈ { − } (Ui,j)i∈I,j∈{0,...,ni} .For each∈i{, we write−ni }+ 1 = npi + qi for some qi 0, . . . , n 1 and then deﬁne, for all k 0, . . . , n (cid:71)1(cid:71), − pi 1 Bk = Ui,k+nl . ∈ i I l=0 ∈ By construction, for all µ KG we have µ(B0) = µ(B1) = . .∈. ={ µ(Bn−1−) (b}e- cause there exists an element of G mapping B to B for all i 0, . . . , n 1 ); ≤ 0 i hence nµ(B0) µ(A) s∈ince B0, . . . , Bn−1 are disjoint and contained in A. Also by construction, for any µ (cid:71)KG we have (cid:91) − \ n 1 ≤ ∑ ≤ − µ(A Bk) qiµ(Ui,0) (n 1)µ( U0,i) ∈ ∈ k=0 i I i I In any N-dividing partition of A, the union of the bases of the columns must have ∈ µ-measure less that µ(NA) for all µ KG, so what we just obtained implies that − − ≤ n 1 ≤ µ(A) nµ(B0) N µ(A) ε . − ≤ ≤ Thus, B = B0 is such that µ(A) ε nµ(B) µ(A), proving that KG is approx(cid:3)i- mately divisible. We are now ready to prove that the assumption of approximate divisibility in the deﬁnition of a dynamical simplex is redundant. ##LTLine## ##LTLine## ##LTLine##

text: JULIEN

text: MELLERAY

text: Lemma

text: Fix

text: an

text: integer

text: N,

text: and

text: assume

text: that

text: A,

text: B

text: are

text: clopen

text: subsets

text: such

text: that

text: there

text: exists

text: a

text: N-dividing

text: partition

text: of

text: A

text: and

text: a

text: N-dividing

text: partition

text: of

text: B.

text: Then

text: there

text: is

text: a

text: N-

text: dividing

text: partition

text: of

text: A

text: B.

text: Proof.

text: By

text: induction

text: on

text: the

text: number

text: of

text: columns

text: of

text: the

text: N-dividing

text: partition

text: of

text: B,

text: it

text: is

text: enough

text: to

text: consider

text: the

text: cas≥e

text: where

text: it

text: is

text: of

text: the

text: form

text: for

text: some

text: clopen

text: V

text: and

text: some

text: m

text: N.

text: Using

text: the

text: previous

text: lemma

text: m

text: times,

text: we

text: produce

text: U

text: N-dividing

text: partitions

text: which

text: reﬁne

text: U,

text: and

text: clopen

text: sets

text: W

text: contained

text: in

text: V

text: such

text: i

text: i

text: that

text: U

text: U

text: For

text: all

text: i

text: m,

text: reﬁnes

text: i

text: aUnd

text: Wi;

text: For

text: all

text: i

text: m

text: the

text: elementsUof

text: i

text: do

text: not

text: intersect

text: Wi,

text: hi(W∪i);

text: For

text: all

text: i

text: m

text: the

text: union

text: of

text: i

text: and

text: (Wi,

text: hm(Wi))

text: covers

text: A

text: B.

text: U

text: In

text: the

text: end,

text: m

text: is

text: disjoint

text: from

text: (Wm,

text: .U.

text: hm(Wm)),

text: so

text: we

text: may

text: just

text: add

text: (Wm,

text: hm(Wm))

text: as

text: a

text: new

text: column

text: to

text: m

text: to

text: obtain

text: the

text: desired

text: partition

text: of

text: A

text: B.

text: Proposition

text: For

text: any

text: integer

text: N

text: and

text: any

text: clopen

text: A

text: there

text: exists

text: a

text: N-dividing

text: partition

text: of

text: A.

text: Proof.

text: Since

text: by

text: assumption

text: the

text: G-orbit

text: of

text: any

text: x

text: A

text: is

text: dense,

text: its

text: intersection

text: with

text: A

text: is

text: inﬁnite

text: and

text: we

text: may

text: ﬁnd

text: some

text: clopen

text: subset

text: U

text: x

text: and

text: elements

text: g

text: g

text: N

text: of

text: G

text: such

text: that

text: are

text: disjoint

text: and

text: contained

text: in

text: A.

text: Thus

text: there

text: exists

text: a

text: covering

text: of

text: A

text: by

text: clopen

text: sets

text: which

text: can

text: each

text: be

text: covered

text: by

text: a

text: N-dividing

text: partition,

text: and

text: by

text: compactness

text: there

text: exists

text: such

text: a

text: covering

text: which

text: is

text: ﬁnite.

text: Then

text: we

text: obtain

text: the

text: desired

text: N-dividing

text: partition

text: of

text: A

text: from

text: Lemma

text: Proof

text: of

text: Theorem

text: Fix

text: a

text: nonempty

text: clopen

text: subset

text: A

text: of

text: X,

text: an

text: integer

text: n

text: and

text: ε

text: Then

text: pick

text: a

text: N-dividing

text: partition

text: of

text: A

text: for

text: some

text: N

text: n;

text: let

text: us

text: denote

text: it

text: as

text: before

text: by

text: ε

text: .For

text: each∈i{,

text: we

text: write−ni

text: npi

text: qi

text: for

text: some

text: qi

text: n

text: and

text: then

text: deﬁne,

text: for

text: all

text: k

text: n

text: pi

text: Bk

text: Ui,k+nl

text: i

text: I

text: By

text: construction,

text: for

text: all

text: µ

text: KG

text: we

text: have

text: (b}e-

text: cause

text: there

text: exists

text: an

text: element

text: of

text: G

text: mapping

text: B

text: to

text: B

text: for

text: all

text: i

text: n

text: i

text: hence

text: µ(A)

text: s∈ince

text: are

text: disjoint

text: and

text: contained

text: in

text: A.

text: Also

text: by

text: construction,

text: for

text: any

text: µ

text: we

text: have

text: n

text: µ(A

text: Bk)

text: (n

text: i

text: I

text: i

text: I

text: In

text: any

text: N-dividing

text: partition

text: of

text: A,

text: the

text: union

text: of

text: the

text: bases

text: of

text: the

text: columns

text: must

text: have

text: µ-measure

text: less

text: that

text: µ(NA)

text: for

text: all

text: µ

text: KG,

text: so

text: what

text: we

text: just

text: obtained

text: implies

text: that

text: n

text: µ(A)

text: N

text: µ(A)

text: ε

text: Thus,

text: B

text: is

text: such

text: that

text: µ(A)

text: ε

text: nµ(B)

text: µ(A),

text: proving

text: that

text: KG

text: is

text: mately

text: divisible.

text: We

text: are

text: now

text: ready

text: to

text: prove

text: that

text: the

text: assumption

text: of

text: approximate

text: divisibility

text: in

text: the

text: deﬁnition

text: of

text: a

text: dynamical

text: simplex

text: is

text: redundant.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: DYNAMICAL SIMPLICES AND FRAI¨SSE´ THEORY 5 ⊂ Corollary 2.6. Assume that K P(X) is compact and convex; all elements of K are atomless and have full support; and K satisﬁes the Glasner–Weiss condition. Then K is approximately divisible. { ∈ ∀ ∈ } Proof. We pick K as above, and let H = h Homeo(X): µ K h∗µ = µ . We ﬁrst note that the argument used in the proof Proposition 2.6 in [GW] shows that the action of H on X is transitive. Hence it follows from Theorem 2.1 that the simplex K of all G-invariant Borel probability measures on X is approximately H divisible. Since K is contained in K , K is also approximately divisible (we note H that it then follows from the arguments of [IM] that K = KH but this is not neede(cid:3)d here). 3. DYNAMICAL SIMPLICES AS FRA¨ISSE´ LIMITS In this section, we develop the connection between dynamical simplices and Fra¨ısse´ theory. We introduce the basic concepts of Fra¨ısse´ theory in our speciﬁc context. Since we do not assume familarity with this theory, we give some back- ground details; we refer the reader to [H] for a more thorough discussion. For the moment, we ﬁx a set E (later, E will be a Choquet simplex), and the ob- jects we consider are Boolean algebras endowed with a family of ﬁnitely additive B probabilityBmeasures (µe)e∈E. We let E denote the class of all these objects: an element of E is of the form (A, (µe)e∈E) where A is a Boolean algebra and each µe is a ﬁnitely additive probabi∈lityBmeasure on A. Since there should be no risk of confusion, we simply write A and use the same letter A also to denote the E underlying Boolean algebra of the structure we are considering. Allow us to point out, for those who are used to Fra¨ısse´ theory, that elements B of E really are ﬁrst order structures in disguise, in a language wh↔ere e∈ach µe is coded by unary predicates µre which are interpreted via µe(a) = r a µre; this is for instance done in [KR] (with just one measure in the language but this makes no essential difference). We adopt somewhat unusual conventions in the hope of improving readability in our particular case. B Note that inside we have natural notions of isomorphism, embedding, and E B substructure. Below, we call elements of E-structures. K B E K Deﬁnition 3.1. Let be a subclass of . One says that satisﬁes : E ∈ K (1) the hereditary property if whenever A and B embeds in A then also ∈ K B . ∈ K ∈ K (2) the joint embedding property if for any A, B there exists C such that both A and B embed in C. ∈ K → (3) the amalgamation property if, for any A, B, C and embeddings α: A → ∈ K (cid:48) → (cid:48) → B, β: A C there exists D and embeddings α : B D, β : C D (cid:48) ◦ (cid:48) ◦ such that α α = β β. { } All the classes we will consider contain the trivial boolean algebra 0, 1 , with B µe(0) = 0 and µe(1) = 1 for all e, which is a substructure of all elements of E. Thus the joint embedding property will be implied by the amalgamation property. The hereditary property is usually easy to check; the amalgamation property is typically much trickier, and is intimately related to homogeneity. ∈ B Deﬁnition 3.2. Given A , we say that A is homogeneous if any isomorphism E between ﬁnite substructures of A extends to an isomorphism of A.

text: DYNAMICAL

text: SIMPLICES

text: AND

text: FRAI¨SSE´

text: THEORY

text: Corollary

text: Assume

text: that

text: K

text: P(X)

text: is

text: compact

text: and

text: convex;

text: all

text: elements

text: of

text: K

text: are

text: atomless

text: and

text: have

text: full

text: support;

text: and

text: K

text: satisﬁes

text: the

text: Glasner–Weiss

text: condition.

text: Then

text: K

text: is

text: approximately

text: divisible.

text: Proof.

text: We

text: pick

text: K

text: as

text: above,

text: and

text: let

text: H

text: h

text: Homeo(X):

text: µ

text: K

text: h∗µ

text: µ

text: We

text: ﬁrst

text: note

text: that

text: the

text: argument

text: used

text: in

text: the

text: proof

text: Proposition

text: in

text: [GW]

text: shows

text: that

text: the

text: action

text: of

text: H

text: on

text: X

text: is

text: transitive.

text: Hence

text: it

text: follows

text: from

text: Theorem

text: that

text: the

text: simplex

text: K

text: of

text: all

text: G-invariant

text: Borel

text: probability

text: measures

text: on

text: X

text: is

text: approximately

text: H

text: divisible.

text: Since

text: K

text: is

text: contained

text: in

text: K

text: K

text: is

text: also

text: approximately

text: divisible

text: (we

text: note

text: H

text: that

text: it

text: then

text: follows

text: from

text: the

text: arguments

text: of

text: [IM]

text: that

text: K

text: KH

text: but

text: this

text: is

text: not

text: here).

text: DYNAMICAL

text: SIMPLICES

text: AS

text: FRA¨ISSE´

text: LIMITS

text: In

text: this

text: section,

text: we

text: develop

text: the

text: connection

text: between

text: dynamical

text: simplices

text: and

text: Fra¨ısse´

text: theory.

text: We

text: introduce

text: the

text: basic

text: concepts

text: of

text: Fra¨ısse´

text: theory

text: in

text: our

text: speciﬁc

text: context.

text: Since

text: we

text: do

text: not

text: assume

text: familarity

text: with

text: this

text: theory,

text: we

text: give

text: some

text: back-

text: ground

text: details;

text: we

text: refer

text: the

text: reader

text: to

text: [H]

text: for

text: a

text: more

text: thorough

text: discussion.

text: For

text: the

text: moment,

text: we

text: ﬁx

text: a

text: set

text: E

text: (later,

text: E

text: will

text: be

text: a

text: Choquet

text: simplex),

text: and

text: the

text: ob-

text: jects

text: we

text: consider

text: are

text: Boolean

text: algebras

text: endowed

text: with

text: a

text: family

text: of

text: ﬁnitely

text: additive

text: B

text: probabilityBmeasures

text: (µe)e∈E.

text: We

text: let

text: E

text: denote

text: the

text: class

text: of

text: all

text: these

text: objects:

text: an

text: element

text: of

text: E

text: is

text: of

text: the

text: form

text: (A,

text: (µe)e∈E)

text: where

text: A

text: is

text: a

text: Boolean

text: algebra

text: and

text: each

text: µe

text: is

text: a

text: ﬁnitely

text: additive

text: probabi∈lityBmeasure

text: on

text: A.

text: Since

text: there

text: should

text: be

text: no

text: risk

text: of

text: confusion,

text: we

text: simply

text: write

text: A

text: and

text: use

text: the

text: same

text: letter

text: A

text: also

text: to

text: denote

text: the

text: E

text: underlying

text: Boolean

text: algebra

text: of

text: the

text: structure

text: we

text: are

text: considering.

text: Allow

text: us

text: to

text: point

text: out,

text: for

text: those

text: who

text: are

text: used

text: to

text: Fra¨ısse´

text: theory,

text: that

text: elements

text: B

text: of

text: E

text: really

text: are

text: ﬁrst

text: order

text: structures

text: in

text: disguise,

text: in

text: a

text: language

text: wh↔ere

text: e∈ach

text: µe

text: is

text: coded

text: by

text: unary

text: predicates

text: µre

text: which

text: are

text: interpreted

text: via

text: µe(a)

text: r

text: a

text: µre;

text: this

text: is

text: for

text: instance

text: done

text: in

text: [KR]

text: (with

text: just

text: one

text: measure

text: in

text: the

text: language

text: but

text: this

text: makes

text: no

text: essential

text: difference).

text: We

text: adopt

text: somewhat

text: unusual

text: conventions

text: in

text: the

text: hope

text: of

text: improving

text: readability

text: in

text: our

text: particular

text: case.

text: B

text: Note

text: that

text: inside

text: we

text: have

text: natural

text: notions

text: of

text: isomorphism,

text: embedding,

text: and

text: E

text: B

text: substructure.

text: Below,

text: we

text: call

text: elements

text: of

text: E-structures.

text: K

text: B

text: E

text: K

text: Deﬁnition

text: Let

text: be

text: a

text: subclass

text: of

text: One

text: says

text: that

text: satisﬁes

text: E

text: K

text: the

text: hereditary

text: property

text: if

text: whenever

text: A

text: and

text: B

text: embeds

text: in

text: A

text: then

text: also

text: K

text: B

text: K

text: K

text: the

text: joint

text: embedding

text: property

text: if

text: for

text: any

text: A,

text: B

text: there

text: exists

text: C

text: such

text: that

text: both

text: A

text: and

text: B

text: embed

text: in

text: C.

text: K

text: the

text: amalgamation

text: property

text: if,

text: for

text: any

text: A,

text: B,

text: C

text: and

text: embeddings

text: α:

text: A

text: K

text: B,

text: β:

text: A

text: C

text: there

text: exists

text: D

text: and

text: embeddings

text: α

text: B

text: D,

text: β

text: C

text: D

text: such

text: that

text: α

text: α

text: β

text: β.

text: All

text: the

text: classes

text: we

text: will

text: consider

text: contain

text: the

text: trivial

text: boolean

text: algebra

text: with

text: B

text: and

text: for

text: all

text: e,

text: which

text: is

text: a

text: substructure

text: of

text: all

text: elements

text: of

text: E.

text: Thus

text: the

text: joint

text: embedding

text: property

text: will

text: be

text: implied

text: by

text: the

text: amalgamation

text: property.

text: The

text: hereditary

text: property

text: is

text: usually

text: easy

text: to

text: check;

text: the

text: amalgamation

text: property

text: is

text: typically

text: much

text: trickier,

text: and

text: is

text: intimately

text: related

text: to

text: homogeneity.

text: B

text: Deﬁnition

text: Given

text: A

text: we

text: say

text: that

text: A

text: is

text: homogeneous

text: if

text: any

text: isomorphism

text: E

text: between

text: ﬁnite

text: substructures

text: of

text: A

text: extends

text: to

text: an

text: isomorphism

text: of

text: A.