text: Ultra-light and strong: the massless harmonic oscillator and its singular path integral ∗ G. Modanese 1 1Free University of Bolzano, Faculty of Science and Technology P.za Universit`a 5, Bolzano, Italy (Dated: June 29, 2016) In classical mechanics, a light particle bound by a strong elastic force just oscillates at high frequency in the region allowed by its initial position and velocity. In quantum mechanics, instead, the ground state of the particle becomes completely de-localized → in the limit m 0. The harmonic oscillator thus ceases to be a useful microscopic → physical model in the limit m 0, but its Feynman path integral has interesting singularities which make it a prototype of other systems exhibiting a “quantum runaway” from the classical conﬁgurations near the minimum of the action. The probability density of the coherent runaway modes can be obtained as the solution of a Fokker-Planck equation associated to the condition S = S . This technique min can be applied also to other systems, notably to a dimensional reduction of the Einstein-Hilbert action. I. INTRODUCTION For most dynamical systems, the Feynman path integral admits a continuation to imagi- nary time, and quantum ﬂuctuations with respect to the classical trajectories are bounded. In certain cases, however, the main contributions to the path integral originate from regions of the conﬁguration space which are far from the classical and semiclassical conﬁgurations near the stationary point of the action. Situations of this kind have been previously studied by da Luz et al. [1, 2] for systems with strong constraints or boundary conditions, which lead to a drastic discretization of the conﬁguration space. A remarkable application is to systems, like “quantum paths”, which are of direct practical interest [3]. In this paper we will show that a similar “quantum runaway” occurs in an apparently harmless system (but one for which the conﬁguration space is truly inﬁnite-dimensional): the massless harmonic oscillator. We shall start with some simple physical remarks and then turn to the path integral. II. ELEMENTARY TREATMENT: CLASSICAL, STOCHASTIC, QUANTUM ∗ Email address: giovanni.modanese@unibz.it ##LTLine##

text: Ultra-light

label: title

text: and

text: strong:

text: the

text: massless

text: harmonic

text: oscillator

text: and

text: its

text: singular

text: path

text: integral

label: author

text: G.

text: Modanese

text: University

text: of

text: Bolzano,

text: Faculty

text: of

text: Science

text: and

text: Technology

text: P.za

text: Universit`a

text: Bolzano,

text: Italy

text: (Dated:

text: June

label: date

text: In

label: abstract

text: classical

text: mechanics,

text: a

text: light

text: particle

text: bound

text: by

text: a

text: strong

text: elastic

text: force

text: just

text: oscillates

text: at

text: high

text: frequency

text: in

text: the

text: region

text: allowed

text: by

text: its

text: initial

text: position

text: and

text: velocity.

text: In

text: quantum

text: mechanics,

text: instead,

text: the

text: ground

text: state

text: of

text: the

text: particle

text: becomes

text: completely

text: de-localized

text: in

text: the

text: limit

text: m

text: The

text: harmonic

text: oscillator

text: thus

text: ceases

text: to

text: be

text: a

text: useful

text: microscopic

text: physical

text: model

text: in

text: the

text: limit

text: m

text: but

text: its

text: Feynman

text: path

text: integral

text: has

text: interesting

text: singularities

text: which

text: make

text: it

text: a

text: prototype

text: of

text: other

text: systems

text: exhibiting

text: a

text: “quantum

text: runaway”

text: from

text: the

text: classical

text: conﬁgurations

text: near

text: the

text: minimum

text: of

text: the

text: action.

text: The

text: probability

text: density

text: of

text: the

text: coherent

text: runaway

text: modes

text: can

text: be

text: obtained

text: as

text: the

text: solution

text: of

text: a

text: Fokker-Planck

text: equation

text: associated

text: to

text: the

text: condition

text: S

text: S

text: This

text: technique

text: min

text: can

text: be

text: applied

text: also

text: to

text: other

text: systems,

text: notably

text: to

text: a

text: dimensional

text: reduction

text: of

text: the

text: Einstein-Hilbert

text: action.

text: I.

text: INTRODUCTION

text: For

text: most

text: dynamical

text: systems,

text: the

text: Feynman

text: path

text: integral

text: admits

text: a

text: continuation

text: to

text: imagi-

text: nary

text: time,

text: and

text: quantum

text: ﬂuctuations

text: with

text: respect

text: to

text: the

text: classical

text: trajectories

text: are

text: bounded.

text: In

text: certain

text: cases,

text: however,

text: the

text: main

text: contributions

text: to

text: the

text: path

text: integral

text: originate

text: from

text: regions

text: of

text: the

text: conﬁguration

text: space

text: which

text: are

text: far

text: from

text: the

text: classical

text: and

text: semiclassical

text: conﬁgurations

text: near

text: the

text: stationary

text: point

text: of

text: the

text: action.

text: Situations

text: of

text: this

text: kind

text: have

text: been

text: previously

text: studied

text: by

text: da

text: Luz

text: et

text: al.

text: for

text: systems

text: with

text: strong

text: constraints

text: or

text: boundary

text: conditions,

text: which

text: lead

text: to

text: a

text: drastic

text: discretization

text: of

text: the

text: conﬁguration

text: space.

text: A

text: remarkable

text: application

text: is

text: to

text: systems,

text: like

text: “quantum

text: paths”,

text: which

text: are

text: of

text: direct

text: practical

text: interest

text: In

text: this

text: paper

text: we

text: will

text: show

text: that

text: a

text: similar

text: “quantum

text: runaway”

text: occurs

text: in

text: an

text: apparently

text: harmless

text: system

text: (but

text: one

text: for

text: which

text: the

text: conﬁguration

text: space

text: is

text: truly

text: inﬁnite-dimensional):

text: the

text: massless

text: harmonic

text: oscillator.

text: We

text: shall

text: start

text: with

text: some

text: simple

text: physical

text: remarks

text: and

text: then

text: turn

text: to

text: the

text: path

text: integral.

text: II.

text: ELEMENTARY

text: TREATMENT:

text: CLASSICAL,

text: STOCHASTIC,

text: QUANTUM

text: Email

text: address:

text: giovanni.modanese@unibz.it

text: ##LTLine##


text: 2 Let us consider the behavior of an harmonic oscillator in the limit in which the mass m goes to zero while the elastic constant k remains ﬁnite. We can think of this limit just as a mathematical exercise, or as a way of describing a situation in which a very light particle is → bound by a strong potential. In the classical equation of motion, the limit m 0 does not produce any qualitative change of the dynamics. The frequency of the oscillations tends to inﬁnity, as can be intuitively predicted considering the lack of inertia. The amplitude of the oscillations, however, remains ﬁnite; if the particle starts at rest at some distance from the origin, it remains conﬁned within the same distance, while its velocity at the origin tends to inﬁnity, due to energy conservation. Let us check if the classical limit of zero mass can be described by setting m = 0 in the − action of the particle from the beginning, thus starting with the lagrangian L = kx2/2. The equation of motion obtained by minimizing the action is x(t) = 0, or x(t) = F (t)/k in the presence of an additional external force F (t). This means that the oscillator just follows the external force, or is at rest at the origin if the external force vanishes. Therefore → its behavior is qualitatively diﬀerent from that obtained taking the limit m 0. We can → conclude that the correct procedure is actually the limit m 0, because a classical non- relativistic dynamics where m = 0 from the start is ill-deﬁned (for example, it is impossible to deﬁne kinetic energy and momentum of the particle; in fact the canonical momentum associated to L is trivially constrained, etc.). If we introduce some noise into the classical equations, we still obtain reasonable results in → the limit m 0. In the presence of thermal noise, the equipartition principle suggests that the average displacement of the oscillator is ﬁnite, independently from the mass, because (cid:104) (cid:105) kx2 = k T , where k is the Boltzmann constant; the average velocity tends to inﬁnity as B B → (cid:104) (cid:105) m 0, since mv2 = k T . More in detail, one can write a Langevin stochastic equation B (cid:48)(cid:48) − mx (t) = kx(t) + mΓ(t) (1) where Γ(t) is for instance a white noise such that (cid:104) (cid:105) (cid:104) (cid:48) (cid:105) k T − (cid:48) B Γ(t) = 0, Γ(t)Γ(t ) = 2γ δ(t t ) (2) m ##LTLine##

label: paragraph

text: Let

text: us

text: consider

text: the

text: behavior

text: of

text: an

text: harmonic

text: oscillator

text: in

text: the

text: limit

text: in

text: which

text: the

text: mass

text: m

text: goes

text: to

text: zero

text: while

text: the

text: elastic

text: constant

text: k

text: remains

text: ﬁnite.

text: We

text: can

text: think

text: of

text: this

text: limit

text: just

text: as

text: a

text: mathematical

text: exercise,

text: or

text: as

text: a

text: way

text: of

text: describing

text: a

text: situation

text: in

text: which

text: a

text: very

text: light

text: particle

text: is

text: bound

text: by

text: a

text: strong

text: potential.

text: In

text: the

text: classical

text: equation

text: of

text: motion,

text: the

text: limit

text: m

text: does

text: not

text: produce

text: any

text: qualitative

text: change

text: of

text: the

text: dynamics.

text: The

text: frequency

text: of

text: the

text: oscillations

text: tends

text: to

text: inﬁnity,

text: as

text: can

text: be

text: intuitively

text: predicted

text: considering

text: the

text: lack

text: of

text: inertia.

text: The

text: amplitude

text: of

text: the

text: oscillations,

text: however,

text: remains

text: ﬁnite;

text: if

text: the

text: particle

text: starts

text: at

text: rest

text: at

text: some

text: distance

text: from

text: the

text: origin,

text: it

text: remains

text: conﬁned

text: within

text: the

text: same

text: distance,

text: while

text: its

text: velocity

text: at

text: the

text: origin

text: tends

text: to

text: inﬁnity,

text: due

text: to

text: energy

text: conservation.

text: Let

text: us

text: check

text: if

text: the

text: classical

text: limit

text: of

text: zero

text: mass

text: can

text: be

text: described

text: by

text: setting

text: m

text: in

text: the

text: action

text: of

text: the

text: particle

text: from

text: the

text: beginning,

text: thus

text: starting

text: with

text: the

text: lagrangian

text: L

text: The

text: equation

text: of

text: motion

text: obtained

text: by

text: minimizing

text: the

text: action

text: is

text: x(t)

text: or

text: x(t)

text: F

text: (t)/k

text: in

text: the

text: presence

text: of

text: an

text: additional

text: external

text: force

text: F

text: (t).

text: This

text: means

text: that

text: the

text: oscillator

text: just

text: follows

text: the

text: external

text: force,

text: or

text: is

text: at

text: rest

text: at

text: the

text: origin

text: if

text: the

text: external

text: force

text: vanishes.

text: Therefore

text: its

text: behavior

text: is

text: qualitatively

text: diﬀerent

text: from

text: that

text: obtained

text: taking

text: the

text: limit

text: m

text: We

text: can

text: conclude

text: that

text: the

text: correct

text: procedure

text: is

text: actually

text: the

text: limit

text: m

text: because

text: a

text: classical

text: non-

text: relativistic

text: dynamics

text: where

text: m

text: from

text: the

text: start

text: is

text: ill-deﬁned

text: (for

text: example,

text: it

text: is

text: impossible

text: to

text: deﬁne

text: kinetic

text: energy

text: and

text: momentum

text: of

text: the

text: particle;

text: in

text: fact

text: the

text: canonical

text: momentum

text: associated

text: to

text: L

text: is

text: trivially

text: constrained,

text: etc.).

text: If

text: we

text: introduce

text: some

text: noise

text: into

text: the

text: classical

text: equations,

text: we

text: still

text: obtain

text: reasonable

text: results

text: in

text: the

text: limit

text: m

text: In

text: the

text: presence

text: of

text: thermal

text: noise,

text: the

text: equipartition

text: principle

text: suggests

text: that

text: the

text: average

text: displacement

text: of

text: the

text: oscillator

text: is

text: ﬁnite,

text: independently

text: from

text: the

text: mass,

text: because

text: k

text: T

text: where

text: k

text: is

text: the

text: Boltzmann

text: constant;

text: the

text: average

text: velocity

text: tends

text: to

text: inﬁnity

text: as

text: B

text: B

text: m

text: since

text: k

text: T

text: More

text: in

text: detail,

text: one

text: can

text: write

text: a

text: Langevin

text: stochastic

text: equation

text: B

text: mx

text: (t)

text: kx(t)

text: mΓ(t)

text: where

text: Γ(t)

text: is

text: for

text: instance

text: a

text: white

text: noise

text: such

text: that

text: k

text: T

text: B

text: Γ(t)

text: Γ(t)Γ(t

text: 2γ

text: δ(t

text: t

text: m

text: ##LTLine##


text: 11 action of the conﬁgurations, then for systems with a continuum spectrum the interference (cid:126) factor eiS/ ensures that the only relevant contribution originates from the stationary points of S; if, however, there are δ-like peaks in ρ(S), then the system can in fact run away to non-classical conﬁgurations. We have computed explicitly some of these conﬁgurations for the massless oscillator by solving the equation S = 0, regarded either as a diﬀerential equation depending on a function with null integral, or as a stochastic equation containing a white noise. A possible application of this method to a system far more complex and (cid:82) (cid:112) physically relevant than the massless oscillator concerns the Einstein gravitational action S = (1/8πG) d4x g(x)R(x). Since the scalar curvature R is not positive-deﬁnite, it is possible to ﬁnd ﬁeld conﬁgurations which do not satisfy the Einstein equations in vacuum and still have zero action after the integration, due to a compensation between disjoint regions with positive and negative curvature. Conﬁgurations of this kind have been computed in [7–9]. (See also a related equipotential lines technique in [10].) In order to evaluate their contribution to the Feynman path integral one can follow an approach similar to that described here. [1] Da Luz, M.G.E., and Bin Kang Cheng, Quantum-mechanical results for a free particle inside a box with general boundary conditions, Phys. Rev. A 51 (1995) 1811-1819 [2] Ozorio de Almeida, A.M., and M.G.E. da Luz, Path integrals and edge corrections for torus maps, Physica D 94 (1996) 1-18 [3] Viswanathan, G.M., et al., Optimizing the success of random searches, Nature 401 (1999) 911-914 [4] Risken, H., “The Fokker-Planck equation: methods of solutions and applications”, Springer, Berlin, 1996. [5] Cufaro Petroni, N., De Martino, S. and S. De Siena, Exact solutions of Fokker-Planck equa- tions associated to quantum wave functions, Phys. Lett. A 245 (1998) 1-10 [6] Modanese, G., Functional integral transition elements of a massless oscillator, submitted. arXiv:1408.1635 [7] Modanese, G., The vacuum state of quantum gravity contains large virtual masses, Class. Quant. Grav. 24 (2007) 1899 [8] Modanese, G., Virtual dipoles and large ﬂuctuations in quantum gravity, Phys. Lett. B 460 (1999) 276-280 [9] Modanese, G., The Paradox of Virtual Dipoles in the Einstein Action, Phys. Rev. D 62 (2000) 087502 [10] Bertotti, M.L. and Modanese, G., Microscopic Models for Welfare Measures addressing a Reduction of Economic Inequality, Complexity 21 (2015) 89-98 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: action

text: of

text: the

text: conﬁgurations,

text: then

text: for

text: systems

text: with

text: a

text: continuum

text: spectrum

text: the

text: interference

text: factor

text: eiS/

text: ensures

text: that

text: the

text: only

text: relevant

text: contribution

text: originates

text: from

text: the

text: stationary

text: points

text: of

text: S;

text: if,

text: however,

text: there

text: are

text: δ-like

text: peaks

text: in

text: ρ(S),

text: then

text: the

text: system

text: can

text: in

text: fact

text: run

text: away

text: to

text: non-classical

text: conﬁgurations.

text: We

text: have

text: computed

text: explicitly

text: some

text: of

text: these

text: conﬁgurations

text: for

text: the

text: massless

text: oscillator

text: by

text: solving

text: the

text: equation

text: S

text: regarded

text: either

text: as

text: a

text: diﬀerential

text: equation

text: depending

text: on

text: a

text: function

text: with

text: integral,

text: or

text: as

text: a

text: stochastic

text: equation

text: containing

text: a

text: white

text: noise.

text: A

text: possible

text: application

text: of

text: this

text: method

text: to

text: a

text: system

text: far

text: more

text: complex

text: and

text: physically

text: relevant

text: than

text: the

text: massless

text: oscillator

text: concerns

text: the

text: Einstein

text: gravitational

text: action

text: S

text: g(x)R(x).

text: Since

text: the

text: scalar

text: curvature

text: R

text: is

text: not

text: positive-deﬁnite,

text: it

text: is

text: possible

text: to

text: ﬁnd

text: ﬁeld

text: conﬁgurations

text: which

text: do

text: not

text: satisfy

text: the

text: Einstein

text: equations

text: in

text: vacuum

text: and

text: still

text: have

text: zero

text: action

text: after

text: the

text: integration,

text: due

text: to

text: a

text: compensation

text: between

text: disjoint

text: regions

text: with

text: positive

text: and

text: negative

text: curvature.

text: Conﬁgurations

text: of

text: this

text: kind

text: have

text: been

text: computed

text: in

text: (See

text: also

text: a

text: related

text: equipotential

text: lines

text: technique

text: in

text: In

text: order

text: to

text: evaluate

text: their

text: contribution

text: to

text: the

text: Feynman

text: path

text: integral

text: one

text: can

text: follow

text: an

text: approach

text: similar

text: to

text: that

text: described

text: here.

text: Da

text: Luz,

text: M.G.E.,

text: and

text: Bin

text: Kang

text: Cheng,

text: Quantum-mechanical

text: results

text: for

text: a

text: free

text: particle

text: inside

text: a

text: box

text: with

text: general

text: boundary

text: conditions,

text: Phys.

text: Rev.

text: A

text: Ozorio

text: de

text: Almeida,

text: A.M.,

text: and

text: M.G.E.

text: da

text: Luz,

text: Path

text: integrals

text: and

text: edge

text: corrections

text: for

text: torus

text: maps,

text: Physica

text: D

text: Viswanathan,

text: G.M.,

text: et

text: al.,

text: Optimizing

text: the

text: success

text: of

text: random

text: searches,

text: Nature

text: Risken,

text: H.,

text: “The

text: Fokker-Planck

text: equation:

text: methods

text: of

text: solutions

text: and

text: applications”,

text: Springer,

text: Berlin,

text: Cufaro

text: Petroni,

text: N.,

text: De

text: Martino,

text: S.

text: and

text: S.

text: De

text: Siena,

text: Exact

text: solutions

text: of

text: Fokker-Planck

text: equa-

text: tions

text: associated

text: to

text: quantum

text: wave

text: functions,

text: Phys.

text: Lett.

text: A

text: Modanese,

text: G.,

text: Functional

text: integral

text: transition

text: elements

text: of

text: a

text: massless

text: oscillator,

text: submitted.

text: Modanese,

text: G.,

text: The

text: vacuum

text: state

text: of

text: quantum

text: gravity

text: contains

text: large

text: virtual

text: masses,

text: Class.

text: Quant.

text: Grav.

text: Modanese,

text: G.,

text: Virtual

text: dipoles

text: and

text: large

text: ﬂuctuations

text: in

text: quantum

text: gravity,

text: Phys.

text: Lett.

text: B

text: Modanese,

text: G.,

text: The

text: Paradox

text: of

text: Virtual

text: Dipoles

text: in

text: the

text: Einstein

text: Action,

text: Phys.

text: Rev.

text: D

text: Bertotti,

text: M.L.

text: and

text: Modanese,

text: G.,

text: Microscopic

text: Models

text: for

text: Welfare

text: Measures

text: addressing

text: a

text: Reduction

text: of

text: Economic

text: Inequality,

text: Complexity

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 3 − (Here γ is an amplitude with dimension time 1 [4].) Then one solves the corresponding → Fokker-Planck equation and looks at its limit for m 0 and k ﬁnite. Stochastic mechanics has often been viewed as a bridge between classical and quantum mechanics [5]. The so- lution W of the Fokker-Planck equation gives the probability distribution of the stochastic variables. In this case it is known that the stationary solution is a Boltzmann distribution in phase space, namely (cid:20) (cid:18) (cid:19)(cid:21) − 1 1 1 W (x, v) = N exp mv2 + kx2 (3) k T 2 2 B → where N is a normalization factor. We see from this distribution that in the limit m 0, x is limited and v is not, as anticipated through the equipartition law. → When we consider the limit m 0, k const. in quantum mechanics, we immediately realize that the behavior of the oscillator becomes singular. Since the frequency tends to inﬁnity, the energy of the ground state also tends to inﬁnity, and so does the diﬀerence between the ground state and the ﬁrst excited state. The average value of x2 in the ground state also tends to inﬁnity, thus the oscillator becomes completely de-localized; in fact we have (cid:12) (cid:12) (cid:12) (cid:12) (cid:126) (cid:126) (cid:104) (cid:105) 2 √2 0 xˆ2 0 = = (4) mω km The same conclusion can be reached by considering the expressions of the operators xˆ (cid:114) (cid:114) (cid:114) † and pˆ in terms of the adimensional creation/annihilation operators a and a, namely (cid:0) (cid:1) (cid:0) (cid:1) √ (cid:126) (cid:126) 1 † † − xˆ = 4 a + a ; pˆ = i 4 mk a a (5) 2 mk 2 This also shows that the roles of the kinetic and potential term in the divergence of the → energy are completely analogous, since when m 0 we have pˆ2 ≈ √1 1 ≈ √1 ; kxˆ2 (6) 2m m 2 m ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (Here

text: γ

text: is

text: an

text: amplitude

text: with

text: dimension

text: time

text: Then

text: one

text: solves

text: the

text: corresponding

text: Fokker-Planck

text: equation

text: and

text: looks

text: at

text: its

text: limit

text: for

text: m

text: and

text: k

text: ﬁnite.

text: Stochastic

text: mechanics

text: has

text: often

text: been

text: viewed

text: as

text: a

text: bridge

text: between

text: classical

text: and

text: quantum

text: mechanics

text: The

text: so-

text: lution

text: W

text: of

text: the

text: Fokker-Planck

text: equation

text: gives

text: the

text: probability

text: distribution

text: of

text: the

text: stochastic

text: variables.

text: In

text: this

text: case

text: it

text: is

text: known

text: that

text: the

text: stationary

text: solution

text: is

text: a

text: Boltzmann

text: distribution

text: in

text: phase

text: space,

text: namely

label: equation

text: W

text: (x,

text: v)

text: N

text: exp

text: k

text: T

text: B

text: where

text: N

text: is

text: a

text: normalization

text: factor.

text: We

text: see

text: from

text: this

text: distribution

text: that

text: in

text: the

text: limit

text: m

text: x

text: is

text: limited

text: and

text: v

text: is

text: not,

text: as

text: anticipated

text: through

text: the

text: equipartition

text: law.

text: When

text: we

text: consider

text: the

text: limit

text: m

text: k

text: const.

text: in

text: quantum

text: mechanics,

text: we

text: immediately

text: realize

text: that

text: the

text: behavior

text: of

text: the

text: oscillator

text: becomes

text: singular.

text: Since

text: the

text: frequency

text: tends

text: to

text: inﬁnity,

text: the

text: energy

text: of

text: the

text: ground

text: state

text: also

text: tends

text: to

text: inﬁnity,

text: and

text: so

text: does

text: the

text: diﬀerence

text: between

text: the

text: ground

text: state

text: and

text: the

text: ﬁrst

text: excited

text: state.

text: The

text: average

text: value

text: of

text: in

text: the

text: ground

text: state

text: also

text: tends

text: to

text: inﬁnity,

text: thus

text: the

text: oscillator

text: becomes

text: completely

text: de-localized;

text: in

text: fact

text: we

text: have

text: √2

text: mω

text: km

text: The

text: same

text: conclusion

text: can

text: be

text: reached

text: by

text: considering

text: the

text: expressions

text: of

text: the

text: operators

text: xˆ

text: and

text: pˆ

text: in

text: terms

text: of

text: the

text: adimensional

text: creation/annihilation

text: operators

text: a

text: and

text: a,

text: namely

text: xˆ

text: a

text: a

text: pˆ

text: i

text: mk

text: a

text: a

text: mk

text: This

text: also

text: shows

text: that

text: the

text: roles

text: of

text: the

text: kinetic

text: and

text: potential

text: term

text: in

text: the

text: divergence

text: of

text: the

text: energy

text: are

text: completely

text: analogous,

text: since

text: when

text: m

text: we

text: have

text: √1

text: √1

text: m

text: m

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: 7 Ρ 0.30 0.25 0.20 0.15 0.10 S(cid:144)Ñ 1 2 3 4 5 6 FIG. 2: Conceptual example of a system with a density of states ρ(S) which has a continuum spectrum plus integrable spikes for some action values Sˆ , Sˆ , ... The spikes make coherent contri- 1 2 butions to the Feynman averages, weighted respectively by factors eiSˆ1/(cid:126), eiSˆ2/(cid:126)... The contributions from the continuum spectrum interfere destructively between themselves, except for states near the minimum of the action. (cid:90) (cid:104) (cid:105) − F (E) = N dEρ(E)F (E)e E/kBT (12) where N is a normalization factor. ˆ If the density ρ(E) has a δ-like peak for some value E (Fig. 1), then we expect that the ˆ ˆ conﬁgurations with energy E give a relevant contribution to the averages. If, however, E is large with respect to the ground state energy and the temperature T is not very high, the − contribution of the states with energy Eˆ will be quite suppressed by the factor e Eˆ/kBT ; and − in any case, all values of E contribute to the averages, albeit with the weight e E/kBT . (cid:126) In a Feynman path integral with complex weight eiS/ we can imagine to integrate over a density of states ρ(S) which is a function of the action of the states. The states can be thought of as classical trajectories. We can write the average of a function F (S), similarly to (12), as (cid:90) (cid:104) (cid:105) (cid:126) F (S) = N dSρ(S)F (S)eiS/ (13) ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Ρ

font: default

text: FIG.

text: Conceptual

label: caption

text: example

text: of

text: a

text: system

text: with

text: a

text: density

text: of

text: states

text: ρ(S)

text: which

text: has

text: a

text: continuum

text: spectrum

text: plus

text: integrable

text: spikes

text: for

text: some

text: action

text: values

text: Sˆ

text: Sˆ

text: The

text: spikes

text: make

text: coherent

text: contri-

text: butions

text: to

text: the

text: Feynman

text: averages,

text: weighted

text: respectively

text: by

text: factors

text: The

text: contributions

text: from

text: the

text: continuum

text: spectrum

text: interfere

text: destructively

text: between

text: themselves,

text: except

text: for

text: states

text: near

text: the

text: minimum

text: of

text: the

text: action.

text: F

text: (E)

text: N

text: dEρ(E)F

text: (E)e

text: E/kBT

text: where

text: N

text: is

text: a

text: normalization

text: factor.

text: ˆ

text: If

text: the

text: density

text: ρ(E)

text: has

text: a

text: δ-like

text: peak

text: for

text: some

text: value

text: E

text: (Fig.

text: then

text: we

text: expect

text: that

text: the

text: ˆ

text: ˆ

text: conﬁgurations

text: with

text: energy

text: E

text: give

text: a

text: relevant

text: contribution

text: to

text: the

text: averages.

text: If,

text: however,

text: E

text: is

text: large

text: with

text: respect

text: to

text: the

text: ground

text: state

text: energy

text: and

text: the

text: temperature

text: T

text: is

text: not

text: very

text: high,

text: the

text: contribution

text: of

text: the

text: states

text: with

text: energy

text: Eˆ

text: will

text: be

text: quite

text: suppressed

text: by

text: the

text: factor

text: e

text: Eˆ/kBT

text: and

text: in

text: any

text: case,

text: all

text: values

text: of

text: E

text: contribute

text: to

text: the

text: averages,

text: albeit

text: with

text: the

text: weight

text: e

text: E/kBT

text: In

text: a

text: Feynman

text: path

text: integral

text: with

text: complex

text: weight

text: eiS/

text: we

text: can

text: imagine

text: to

text: integrate

text: over

text: a

text: density

text: of

text: states

text: ρ(S)

text: which

text: is

text: a

text: function

text: of

text: the

text: action

text: of

text: the

text: states.

text: The

text: states

text: can

text: be

text: thought

text: of

text: as

text: classical

text: trajectories.

text: We

text: can

text: write

text: the

text: average

text: of

text: a

text: function

text: F

text: (S),

text: similarly

text: to

text: as

text: F

text: (S)

text: N

text: dSρ(S)F

text: (S)eiS/

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##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: 8 FIG. 3: Conceptual example of a system whose action depends on two variables (x, y), has a minimum at (0, 0) and also stays at its minimum value (but is not diﬀerentiable) along two lines crossing at (0, 0). In an inﬁnite-dimensional analogue, the “lines” of constant action can be a full-dimensional subspace of the conﬁguration space. (cid:126) In this case, however, the interference factor eiS/ leads to a mutual cancellation of all the contributions from the continuous spectrum, except for those near the minimum. The other surviving contributions are those from possible δ-like peaks (Fig. 2), which can also (cid:126) (cid:126) ˆ ˆ interfere between themselves, depending on the phase diﬀerences between S / , S / ... 1 2 In our current example we are considering a system whose density ρ(S) has a minimum and a peak at S = 0 (and can also have other peaks, not computed here). A graphical representation which illustrates the behavior of the action S as a functional of the classical paths is given in Fig. 3. It is impossible, however, to fully represent in a ﬁnite-dimensional image a functional over an inﬁnite-dimensional space. The idea is that the zero-modes are elements of those subspaces where S is zero but not a minimum, like the four lines in the horizontal plane of Fig. 3, where the function of two variables represented is not diﬀerentiable. The smooth minimum of S is at the origin and is surrounded by a full- dimensional region where S is very close to zero; but in the inﬁnite-dimensional analogy also the “lines” of the zero-modes are inﬁnite-dimensional like the full space and do not have zero measure like lines in 2D. V. STOCHASTIC AND FOKKER-PLANCK EQUATION FOR THE ZERO-MODES We would like to oﬀer here an alternative characterization of the zero-modes, based on a ##LTFigure##

text: FIG.

text: Conceptual

text: example

text: of

text: a

text: system

text: whose

text: action

text: depends

text: on

text: two

text: variables

text: (x,

text: y),

text: has

text: a

text: minimum

text: at

text: and

text: also

text: stays

text: at

text: its

text: minimum

text: value

text: (but

text: is

text: not

text: diﬀerentiable)

text: along

text: two

text: lines

text: crossing

text: at

text: In

text: an

text: inﬁnite-dimensional

text: analogue,

text: the

text: “lines”

text: of

text: constant

text: action

text: can

text: be

text: a

text: full-dimensional

text: subspace

text: of

text: the

text: conﬁguration

text: space.

text: In

text: this

text: case,

text: however,

text: the

text: interference

text: factor

text: eiS/

text: leads

text: to

text: a

text: mutual

text: cancellation

text: of

text: all

text: the

text: contributions

text: from

text: the

text: continuous

text: spectrum,

text: except

text: for

text: those

text: near

text: the

text: minimum.

text: The

text: other

text: surviving

text: contributions

text: are

text: those

text: from

text: possible

text: δ-like

text: peaks

text: (Fig.

text: which

text: can

text: also

text: ˆ

text: ˆ

text: interfere

text: between

text: themselves,

text: depending

text: on

text: the

text: phase

text: diﬀerences

text: between

text: S

text: S

text: In

text: our

text: current

text: example

text: we

text: are

text: considering

text: a

text: system

text: whose

text: density

text: ρ(S)

text: has

text: a

text: minimum

text: and

text: a

text: peak

text: at

text: S

text: (and

text: can

text: also

text: have

text: other

text: peaks,

text: not

text: computed

text: here).

text: A

text: graphical

text: representation

text: which

text: illustrates

text: the

text: behavior

text: of

text: the

text: action

text: S

text: as

text: a

text: functional

text: of

text: the

text: classical

text: paths

text: is

text: given

text: in

text: Fig.

text: It

text: is

text: impossible,

text: however,

text: to

text: fully

text: represent

text: in

text: a

text: ﬁnite-dimensional

text: image

text: a

text: functional

text: over

text: an

text: inﬁnite-dimensional

text: space.

text: The

text: idea

text: is

text: that

text: the

text: zero-modes

text: are

text: elements

text: of

text: those

text: subspaces

text: where

text: S

text: is

text: zero

text: but

text: not

text: a

text: minimum,

text: like

text: the

text: four

text: lines

text: in

text: the

text: horizontal

text: plane

text: of

text: Fig.

text: where

text: the

text: function

text: of

text: two

text: variables

text: represented

text: is

text: not

text: diﬀerentiable.

text: The

text: smooth

text: minimum

text: of

text: S

text: is

text: at

text: the

text: origin

text: and

text: is

text: surrounded

text: by

text: a

text: full-

text: dimensional

text: region

text: where

text: S

text: is

text: very

text: close

text: to

text: zero;

text: but

text: in

text: the

text: inﬁnite-dimensional

text: analogy

text: also

text: the

text: “lines”

text: of

text: the

text: zero-modes

text: are

text: inﬁnite-dimensional

text: like

text: the

text: full

text: space

text: and

text: do

text: not

text: have

text: zero

text: measure

text: like

text: lines

text: in

text: V.

text: STOCHASTIC

text: AND

text: FOKKER-PLANCK

text: EQUATION

text: FOR

text: THE

text: ZERO-MODES

text: We

text: would

text: like

text: to

text: oﬀer

text: here

text: an

text: alternative

text: characterization

text: of

text: the

text: zero-modes,

text: based

text: on

text: a

text: ##LTFigure##


text: Draft version May 29, 2020 Preprint typeset using LATEX style AASTeX6 v. 1.0 DEEP-HITS: ROTATION INVARIANT CONVOLUTIONAL NEURAL NETWORK FOR TRANSIENT DETECTION Guillermo Cabrera-Vives1,2,3,5, Ignacio Reyes4,1,5, Francisco Fo¨rster2,1, Pablo A. Este´vez4,1 and Juan-Carlos Maureira2 Email: gcabrera@dim.uchile.cl 1Millennium Institute of Astrophysics, Chile 2Center for Mathematical Modeling, Universidad de Chile, Chile 3AURA Observatory in Chile 4Department of Electrical Engineering, Universidad de Chile, Chile 5These authors contributed equally to this work ABSTRACT We introduce Deep-HiTS, a rotation invariant convolutional neural network (CNN) model for clas- sifying images of transients candidates into artifacts or real sources for the High cadence Transient Survey (HiTS). CNNs have the advantage of learning the features automatically from the data while achieving high performance. We compare our CNN model against a feature engineering approach using random forests (RF). We show that our CNN signiﬁcantly outperforms the RF model reducing the error by almost half. Furthermore, for a ﬁxed number of approximately 2,000 allowed false tran- sient candidates per night we are able to reduce the miss-classiﬁed real transients by approximately 1/5. To the best of our knowledge, this is the ﬁrst time CNNs have been used to detect astronomi- cal transient events. Our approach will be very useful when processing images from next generation instruments such as the Large Synoptic Survey Telescope (LSST). We have made all our code and data available to the community for the sake of allowing further developments and comparisons at https://github.com/guille-c/Deep-HiTSa. Keywords: methods: data analysis — methods: statistical — techniques: image processing — super- novae: general — surveys 1. INTRODUCTION the space domain, but also the time domain opening new opportunities for understanding our universe. As in many other ﬁelds, large scale survey telescopes The High cadence Transient Survey (HiTS, F¨orster et are already generating more data than humans are able al. 2016), is aimed at detecting and following up optical to process, posing the need for new data-processing transients with characteristic timescales from hours to tools. Some examples are the Sloan Digital Sky Sur- days. The primary goal of HiTS is to detect supernovae vey (SDSS, York et al. 2000), the Panoramic Survey (SNe) during their earliest hours of explosion. HiTS Telescope and Rapid Response System (Pan-STARRS, uses the Dark Energy Camera (DECam, Flauguer et al. Hodapp et al. 2004), the All-Sky Automated Survey 2015) mounted at the prime focus of the Victor M. for Supernovae (ASAS-SN, Shappee et al. 2014), and Blanco 4 m telescope on Cerro Tololo near La Serena, the Dark Energy Survey (DES, Dark Energy Survey Chile. The HiTS pipeline detects transients using dif- Collaboration 2016) among others. Furthermore, in ference images: a template image is subtracted from the the near future we expect to have the Large Synoptic science image taken at the time of observation and point Survey Telescope (LSST, LSST Science Collaboration sources are located within this diﬀerence image. A cus- 2009) operative, which will scan the whole southern sky tom made pipeline does the astrometry, PSF matching, every couple of days producing terabytes of data per candidate extraction, and candidate classiﬁcation into night. These instruments allow us to explore not only real or fake transients. Our previous approach uses ran- dom forests (RF, Breiman 2001) over a set of handmade features for candidate classiﬁcation. Similar approaches have been used in the past by diﬀerent groups includ- a Deep-HiTS is licensed under the terms of the GNU General Public License v3.0. ing Romano et al. (2006), Bloom et al. (2012), Brink

text: Draft

label: section

text: version

text: May

text: Preprint

text: typeset

text: using

text: LATEX

text: style

text: v.

text: DEEP-HITS:

text: ROTATION

text: INVARIANT

text: CONVOLUTIONAL

text: NEURAL

text: NETWORK

text: FOR

text: TRANSIENT

text: DETECTION

text: Guillermo

text: Ignacio

text: Francisco

text: Pablo

text: A.

text: and

text: Juan-Carlos

text: Email:

text: gcabrera@dim.uchile.cl

text: Institute

text: of

text: Astrophysics,

text: Chile

text: for

text: Mathematical

text: Modeling,

text: Universidad

text: de

text: Chile,

text: Chile

text: Observatory

text: in

text: Chile

text: of

text: Electrical

text: Engineering,

text: Universidad

text: de

text: Chile,

text: Chile

text: authors

text: contributed

text: equally

text: to

text: this

text: work

text: ABSTRACT

text: We

text: introduce

text: Deep-HiTS,

text: a

text: rotation

text: invariant

text: convolutional

text: neural

text: network

text: (CNN)

text: model

text: for

text: clas-

text: sifying

text: images

text: of

text: transients

text: candidates

text: into

text: artifacts

text: or

text: real

text: sources

text: for

text: the

text: High

text: cadence

text: Transient

text: Survey

text: (HiTS).

text: CNNs

text: have

text: the

text: advantage

text: of

text: learning

text: the

text: features

text: automatically

text: from

text: the

text: data

text: while

text: achieving

text: high

text: performance.

text: We

text: compare

text: our

text: CNN

text: model

text: against

text: a

text: feature

text: engineering

text: approach

text: using

text: random

text: forests

text: (RF).

text: We

text: show

text: that

text: our

text: CNN

text: signiﬁcantly

text: outperforms

text: the

text: RF

text: model

text: reducing

text: the

text: error

text: by

text: almost

text: half.

text: Furthermore,

text: for

text: a

text: ﬁxed

text: number

text: of

text: approximately

text: allowed

text: false

text: tran-

text: sient

text: candidates

text: per

text: night

text: we

text: are

text: able

text: to

text: reduce

text: the

text: miss-classiﬁed

text: real

text: transients

text: by

text: approximately

text: To

text: the

text: best

text: of

text: our

text: knowledge,

text: this

text: is

text: the

text: ﬁrst

text: time

text: CNNs

text: have

text: been

text: used

text: to

text: detect

text: astronomi-

text: cal

text: transient

text: events.

text: Our

text: approach

text: will

text: be

text: very

text: useful

text: when

text: processing

text: images

text: from

text: next

text: generation

text: instruments

text: such

text: as

text: the

text: Large

text: Synoptic

text: Survey

text: Telescope

text: (LSST).

text: We

text: have

text: made

text: all

text: our

text: code

text: and

text: data

text: available

text: to

text: the

text: community

text: for

text: the

text: sake

text: of

text: allowing

text: further

text: developments

text: and

text: comparisons

text: at

text: Keywords:

text: methods:

text: data

text: analysis

text: methods:

text: statistical

text: techniques:

text: image

text: processing

text: super-

text: novae:

text: general

text: surveys

text: INTRODUCTION

text: the

text: space

text: domain,

text: but

text: also

text: the

text: time

text: domain

text: opening

text: new

text: opportunities

text: for

text: understanding

text: our

text: universe.

text: As

text: in

text: many

text: other

text: ﬁelds,

text: large

text: scale

text: survey

text: telescopes

text: The

text: High

text: cadence

text: Transient

text: Survey

text: (HiTS,

text: F¨orster

text: et

text: are

text: already

text: generating

text: more

text: data

text: than

text: humans

text: are

text: able

text: al.

text: is

text: aimed

text: at

text: detecting

text: and

text: following

text: up

text: optical

text: to

text: process,

text: posing

text: the

text: need

text: for

text: new

text: data-processing

text: transients

text: with

text: characteristic

text: timescales

text: from

text: hours

text: to

text: tools.

text: Some

text: examples

text: are

text: the

text: Sloan

text: Digital

text: Sky

text: Sur-

text: days.

text: The

text: primary

text: goal

text: of

text: HiTS

text: is

text: to

text: detect

text: supernovae

text: vey

text: (SDSS,

text: York

text: et

text: al.

text: the

text: Panoramic

text: Survey

text: (SNe)

text: during

text: their

text: earliest

text: hours

text: of

text: explosion.

text: HiTS

text: Telescope

text: and

text: Rapid

text: Response

text: System

text: (Pan-STARRS,

text: uses

text: the

text: Dark

text: Energy

text: Camera

text: (DECam,

text: Flauguer

text: et

text: al.

text: Hodapp

text: et

text: al.

text: the

text: All-Sky

text: Automated

text: Survey

text: mounted

text: at

text: the

text: prime

text: focus

text: of

text: the

text: Victor

text: M.

text: for

text: Supernovae

text: (ASAS-SN,

text: Shappee

text: et

text: al.

text: and

text: Blanco

text: m

text: telescope

text: on

text: Cerro

text: Tololo

text: near

text: La

text: Serena,

text: the

text: Dark

text: Energy

text: Survey

text: (DES,

text: Dark

text: Energy

text: Survey

text: Chile.

text: The

text: HiTS

text: pipeline

text: detects

text: transients

text: using

text: dif-

text: Collaboration

text: among

text: others.

text: Furthermore,

text: in

text: ference

text: images:

text: a

text: template

text: image

text: is

text: subtracted

text: from

text: the

text: the

text: near

text: future

text: we

text: expect

text: to

text: have

text: the

text: Large

text: Synoptic

text: science

text: image

text: taken

text: at

text: the

text: time

text: of

text: observation

text: and

text: point

text: Survey

text: Telescope

text: (LSST,

text: LSST

text: Science

text: Collaboration

text: sources

text: are

text: located

text: within

text: this

text: diﬀerence

text: image.

text: A

text: cus-

text: operative,

text: which

text: will

text: scan

text: the

text: whole

text: southern

text: sky

text: tom

text: made

text: pipeline

text: does

text: the

text: astrometry,

text: PSF

text: matching,

text: every

text: couple

text: of

text: days

text: producing

text: terabytes

text: of

text: data

text: per

text: candidate

text: extraction,

text: and

text: candidate

text: classiﬁcation

text: into

text: night.

text: These

text: instruments

text: allow

text: us

text: to

text: explore

text: not

text: only

text: real

text: or

text: fake

text: transients.

text: Our

text: previous

text: approach

text: uses

text: ran-

text: dom

text: forests

text: (RF,

text: Breiman

text: over

text: a

text: set

text: of

text: handmade

text: features

text: for

text: candidate

text: classiﬁcation.

text: Similar

text: approaches

text: have

text: been

text: used

text: in

text: the

text: past

text: by

text: diﬀerent

text: groups

text: includ-

text: a

text: Deep-HiTS

text: is

text: licensed

text: under

text: the

text: terms

text: of

text: the

text: GNU

text: General

text: Public

text: License

text: ing

text: Romano

text: et

text: al.

text: Bloom

text: et

text: al.

text: Brink


text: 7 Figure 2. Architecture of the proposed rotational invariant CNN model. Blue boxes represent convolutional layers and red boxes represent max-pooling layers. The stacked images of each candidate are presented to the network rotated four times in × order to exploit rotational symmetry. The calculated feature maps of each rotation are ﬂattened and stacked creating a 2, 304 4 vector that is fed to a fully connected network whose outputs are the probabilities of being an artefact and a real transient. ##LTFigure## ##LTFigure##

text: Figure

text: Architecture

text: of

text: the

text: proposed

text: rotational

text: invariant

text: CNN

text: model.

text: Blue

text: boxes

text: represent

text: convolutional

text: layers

text: and

text: red

text: boxes

text: represent

text: max-pooling

text: layers.

text: The

text: stacked

text: images

text: of

text: each

text: candidate

text: are

text: presented

text: to

text: the

text: network

text: rotated

text: four

text: times

text: in

text: order

text: to

text: exploit

text: rotational

text: symmetry.

text: The

text: calculated

text: feature

text: maps

text: of

text: each

text: rotation

text: are

text: ﬂattened

text: and

text: stacked

text: creating

text: a

text: vector

text: that

text: is

text: fed

text: to

text: a

text: fully

text: connected

text: network

text: whose

text: outputs

text: are

text: the

text: probabilities

text: of

text: being

text: an

text: artefact

text: and

text: a

text: real

text: transient.

text: ##LTFigure##

label: figure

text: ##LTFigure##


text: SINGLE RECURRENCE 15 ⊆ Question 2.16. Let S G. • (i) Does (R ) imply that S is density expanding? 5• (ii) Does (R ) imply that S + A is piecewise syndetic whenever ∗ 5 d (A) > 0? For G = G , Theorem 1.6 answers both parts of Question 2.16 in the 2 negative. A positive solution to Problem 4.4 together with the results of [23] would answer both parts of Question 2.16 in the negative for G = G , where p is any prime. p F 3. Vector spaces over p (cid:76) In this section we state some deﬁnitions and conventions needed for the proof of Theorems 1.1, 1.2, 1.4, and 1.6. We identify a useful ∞ Z Z presentation of G := /p and some associated subgroups. We p n=1 use an arbitrary prime p so that we can formulate Problem 4.4, but we specialize to the case p = 2 in our proofs. This material is also presented in Section 2 of [23]. (cid:76)F Z Z If p is a prime number, let (= /p ) denote the ﬁnite ﬁeld with p p F − elements. We write the elements of as 0, 1, . . . , p 1. Consider the ∞ F p countable direct sum G := . { } p n=1 p N Let Ω := 0, 1 , and write elements of Ω as ω = ω ω ω . . . . For ∈ N { }{ } → 1 2 3 each n let Ω = 0, 1 1,...,n and π : Ω Ω be the projection n n n map given by π (ω) = ω . . . ω . Let Γ be the group of functions → F n 1 n p g : Ω with the group operation of pointwise addition. p For each n ∈ N, let G(n) (cid:83)be the subgroup of Γ consisting of functions ◦ p → F p ⊆ of the form f π , where f : Ω . Observing that G(n) G(n+1) n n p p p for each n, we let G˜p := n∈N G(pn). Then G˜p is a countable abelian group isomorphic5 to G . Our constructions are easier to work with p ˜ from the perspective of G rather than the standard presentation of a p ˜ countable direct sum, so from now on we let G denote the group G . p p F We observe that G(pn) is isomorphic to ( p)Ωn, and we will identify F eleme↔nts of G(pn) with elemen◦ts of ( p)Ω∈n. FThe identiﬁcation is given by g g˜ if and only if g = g˜ π for g˜ ( )Ωn. n p 5One can construct the isomorphism by hand, but when p is prime it suﬃces to observe that both G and G˜ are countably inﬁnite vector spaces over the ﬁnite F p p ﬁeld . p ##LTLine##

text: SINGLE

text: RECURRENCE

text: Question

text: Let

text: S

text: G.

label: list

text: (i)

text: Does

text: (R

text: imply

text: that

text: S

text: is

text: density

text: expanding?

text: 5•

text: (ii)

text: Does

text: (R

text: imply

text: that

text: S

text: A

text: is

text: piecewise

text: syndetic

text: whenever

text: d

text: (A)

text: For

text: G

text: G

text: Theorem

text: answers

text: both

text: parts

text: of

text: Question

text: in

text: the

text: negative.

text: A

text: positive

text: solution

text: to

text: Problem

text: together

text: with

text: the

text: results

text: of

text: would

text: answer

text: both

text: parts

text: of

text: Question

text: in

text: the

text: negative

text: for

text: G

text: G

text: where

text: p

text: is

text: any

text: prime.

text: p

text: F

text: Vector

text: spaces

text: over

text: p

text: In

text: this

text: section

text: we

text: state

text: some

text: deﬁnitions

text: and

text: conventions

text: needed

text: for

text: the

text: proof

text: of

text: Theorems

text: and

text: We

text: identify

text: a

text: useful

text: Z

text: Z

text: presentation

text: of

text: G

text: /p

text: and

text: some

text: associated

text: subgroups.

text: We

text: p

text: use

text: an

text: arbitrary

text: prime

text: p

text: so

text: that

text: we

text: can

text: formulate

text: Problem

text: but

text: we

text: specialize

text: to

text: the

text: case

text: p

text: in

text: our

text: proofs.

text: This

text: material

text: is

text: also

text: presented

text: in

text: Section

text: of

text: Z

text: Z

text: If

text: p

text: is

text: a

text: prime

text: number,

text: let

text: /p

text: denote

text: the

text: ﬁnite

text: ﬁeld

text: with

text: p

text: p

text: F

text: elements.

text: We

text: write

text: the

text: elements

text: of

text: as

text: p

text: Consider

text: the

text: F

text: p

text: countable

text: direct

text: sum

text: G

text: p

text: p

text: N

text: Let

text: Ω

text: and

text: write

text: elements

text: of

text: Ω

text: as

text: ω

text: ω

text: ω

text: ω

text: For

text: N

text: each

text: n

text: let

text: Ω

text: and

text: π

text: Ω

text: Ω

text: be

text: the

text: projection

text: n

text: n

text: n

text: map

text: given

text: by

text: π

text: (ω)

text: ω

text: ω

text: Let

text: Γ

text: be

text: the

text: group

text: of

text: functions

text: F

text: n

text: n

text: p

text: g

text: Ω

text: with

text: the

text: group

text: operation

text: of

text: pointwise

text: addition.

text: p

text: For

text: each

text: n

text: N,

text: let

text: G(n)

text: the

text: subgroup

text: of

text: Γ

text: consisting

text: of

text: functions

text: p

text: F

text: p

text: of

text: the

text: form

text: f

text: π

text: where

text: f

text: Ω

text: Observing

text: that

text: G(n)

text: n

text: n

text: p

text: p

text: p

text: for

text: each

text: n,

text: we

text: let

text: G˜p

text: n∈N

text: G(pn).

text: Then

text: G˜p

text: is

text: a

text: countable

text: abelian

text: group

text: to

text: G

text: Our

text: constructions

text: are

text: easier

text: to

text: work

text: with

text: p

text: from

text: the

text: perspective

text: of

text: G

text: rather

text: than

text: the

text: standard

text: presentation

text: of

text: a

text: p

text: countable

text: direct

text: sum,

text: so

text: from

text: now

text: on

text: we

text: let

text: G

text: denote

text: the

text: group

text: G

text: p

text: p

text: F

text: We

text: observe

text: that

text: G(pn)

text: is

text: isomorphic

text: to

text: p)Ωn,

text: and

text: we

text: will

text: identify

text: F

text: eleme↔nts

text: of

text: G(pn)

text: with

text: elemen◦ts

text: of

text: p)Ω∈n.

text: FThe

text: identiﬁcation

text: is

text: given

text: by

text: g

text: g˜

text: if

text: and

text: only

text: if

text: g

text: g˜

text: π

text: for

text: g˜

text: )Ωn.

text: n

text: p

text: can

text: construct

text: the

text: isomorphism

text: by

text: hand,

text: but

text: when

text: p

text: is

text: prime

text: it

text: suﬃces

text: to

text: observe

text: that

text: both

text: G

text: and

text: G˜

text: are

text: countably

text: inﬁnite

text: vector

text: spaces

text: over

text: the

text: ﬁnite

text: F

text: p

text: p

text: ﬁeld

text: p

text: ##LTLine##


text: SINGLE RECURRENCE 23 ⊆ can be iterated to produce sets A G(nl) whose translates by elements ∪ · · · ∪ 2 of V (n , m ) V (n , m ) are easily understood. 1 1 l l The following lemma summarizes the relevant properties of the sets ∈ A (n, m). Recall from Section that 1 denotes the element g G i ∈ Z Z ∈ 2 having g(ω) = 1 /2 for all ω Ω. ∈ N ∈ N ∪ { } ∈ Z Z Lemma 4.8. For all n, m, , k 0 , k < m, and i /2 , we have (i) A (n, m) + 1 = A (n, m), i i+⊆1 − (ii) A (n, m) + U(n, k) A (n, m k), i ⊆i − (iii) A (n, m) + U(n, k) + 1 A (n, m k), i ∩ − i+∅1 (iv) A (n, m) A (n, m k) = , i (cid:48) i+1 ⊆ (cid:48) (v) If m < m, then A (n, m) A (n, m ). i i Proof. Part (i) follows from the deﬁnition of A (n, m) and the fact that − − ∈ i (g + 1) 1(i) = g 1(i + 1) for all g G . 2 ∈ ∈ To prove Part (ii), note that for each g G(n), u U(n, k), we have | | − 2 ∈ g([τ]) = (g + u)([τ]) for at least Ω k values of τ Ω . We then | − | ≥ | − | − n n have (g + u) 1(i) g 1(i) k for every such g, and Part (ii) now n n follows from the deﬁnition of A(n, m). Part (iii) follows directly from parts (i) and (ii). To prove Part (iv) we exploit Observation 3.3. Assume, to get a ∩ − (cid:54) ∅ contradiction, that A (n, m) A (n, m k) = , and let g be an i i+1 | − | ≥ | | element of the intersection. We then have g 1(i) 1 Ω + m and | − | ≥ | | − − ∩ − n 2 n∅ g 1(i + 1) 1 Ω + m k. Since g 1(i) g 1(i + 1) = , we then | | ≥n| 2| n − have Ω Ω + 2m k, a contradiction. n n (cid:3) Part (v) follows immediately from the deﬁnition of A (n, m). i | |− − Remark 4.9. The A (n, m) are Hamming balls of radius 1 Ω m 1 ∈ i 2 n around i1 G(n), so Parts (ii) and (iii) of Lemma 4.8 are consequences 2 (cid:48) (cid:48) of the fact that U(n, k) + U(n, k ) = U(n, k + k ). | In the following deﬁnition we will use the restrictions g , deﬁned in τ Section . ##LTLine## ##LTLine## ##LTLine##

text: SINGLE

text: RECURRENCE

text: can

text: be

text: iterated

text: to

text: produce

text: sets

text: A

text: G(nl)

text: whose

text: translates

text: by

text: elements

text: of

text: V

text: (n

text: m

text: V

text: (n

text: m

text: are

text: easily

text: understood.

text: l

text: l

text: The

text: following

text: lemma

text: summarizes

text: the

text: relevant

text: properties

text: of

text: the

text: sets

text: A

text: (n,

text: m).

text: Recall

text: from

text: Section

text: that

text: denotes

text: the

text: element

text: g

text: G

text: i

text: Z

text: Z

text: having

text: g(ω)

text: for

text: all

text: ω

text: Ω.

text: N

text: N

text: Z

text: Z

text: Lemma

text: For

text: all

text: n,

text: m,

text: k

text: k

text: m,

text: and

text: i

text: we

text: have

text: (i)

text: A

text: (n,

text: m)

text: A

text: (n,

text: m),

text: i

text: (ii)

text: A

text: (n,

text: m)

text: U(n,

text: k)

text: A

text: (n,

text: m

text: k),

text: i

text: ⊆i

text: (iii)

text: A

text: (n,

text: m)

text: U(n,

text: k)

text: A

text: (n,

text: m

text: k),

text: i

text: (iv)

text: A

text: (n,

text: m)

text: A

text: (n,

text: m

text: k)

text: i

text: (v)

text: If

text: m

text: m,

text: then

text: A

text: (n,

text: m)

text: A

text: (n,

text: m

text: i

text: i

text: Proof.

text: Part

text: (i)

text: follows

text: from

text: the

text: deﬁnition

text: of

text: A

text: (n,

text: m)

text: and

text: the

text: fact

text: that

text: i

text: (g

text: g

text: for

text: all

text: g

text: G

text: To

text: prove

text: Part

text: (ii),

text: note

text: that

text: for

text: each

text: g

text: G(n),

text: u

text: U(n,

text: k),

text: we

text: have

text: g([τ])

text: (g

text: u)([τ])

text: for

text: at

text: least

text: Ω

text: k

text: values

text: of

text: τ

text: Ω

text: We

text: then

text: n

text: n

text: have

text: (g

text: u)

text: g

text: k

text: for

text: every

text: such

text: g,

text: and

text: Part

text: (ii)

text: now

text: n

text: n

text: follows

text: from

text: the

text: deﬁnition

text: of

text: A(n,

text: m).

text: Part

text: (iii)

text: follows

text: directly

text: from

text: parts

text: (i)

text: and

text: (ii).

text: To

text: prove

text: Part

text: (iv)

text: we

text: exploit

text: Observation

text: Assume,

text: to

text: get

text: a

text: contradiction,

text: that

text: A

text: (n,

text: m)

text: A

text: (n,

text: m

text: k)

text: and

text: let

text: g

text: be

text: an

text: i

text: element

text: of

text: the

text: intersection.

text: We

text: then

text: have

text: g

text: Ω

text: m

text: and

text: n

text: n∅

text: g

text: Ω

text: m

text: k.

text: Since

text: g

text: g

text: we

text: then

text: ≥n|

text: n

text: have

text: Ω

text: Ω

text: k,

text: a

text: contradiction.

text: n

text: n

text: Part

text: (v)

text: follows

text: immediately

text: from

text: the

text: deﬁnition

text: of

text: A

text: (n,

text: m).

text: i

text: Remark

text: The

text: A

text: (n,

text: m)

text: are

text: Hamming

text: balls

text: of

text: radius

text: Ω

text: m

text: i

text: n

text: around

text: G(n),

text: so

text: Parts

text: (ii)

text: and

text: (iii)

text: of

text: Lemma

text: are

text: consequences

text: of

text: the

text: fact

text: that

text: U(n,

text: k)

text: U(n,

text: k

text: U(n,

text: k

text: k

text: In

text: the

text: following

text: deﬁnition

text: we

text: will

text: use

text: the

text: restrictions

text: g

text: deﬁned

text: in

text: τ

text: Section

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: SINGLE RECURRENCE 33 ⇒ ⇒ ⇒ ⇒ Proof. We prove (iii) = (ii) = (i) = (iii), then (iv) = (i) ⇒ and (iii) = (iv). ⇒ ⊆ (iii) = (ii). Suppose S satisﬁes condition (iii), and let W (cid:84) G be a Bohr neighborhood of 0, so that there are homomorphisms → T ∈ T ρ , . . . , ρ : G and a neighborhood V of 0 such that W con- 1 k − T → tains k ρ 1(V ). Let Z be the group k and ρ : G Z be the homo- i=1 i × · · · × ⊆ morphism given by ρ(g) = (ρ (g), . . . , ρ (g)). Let U = V V 1 ∈k Z, so that U is a neighborhood of 0 Z. Since S satisﬁes condition ∈ ∈ ∈ (iii), there is a g S such that ρ(g) U. Then ρ (g) V for each i, ∈ i and we conclude that g W . ⇒ ∩ (cid:54) ∅ (ii) = (i). Suppose S W = for every Bohr neighborhood of ∈ ⊆ 0 G. Let (Z, R ) be a minimal group rotation, and let U Z be ρ ∈ a nonempty open set. Choose a neighborhood V of 0 Z such that ∩ (cid:54) ∅ ∈ − U (U + v) = for every v V , and let W = ρ 1(V ). Then W is a ∈ ∩ ∈ Bohr neighborhood6 of 0, so there exists g S W , meaning ρ(g) V . ∩ (cid:54) ∅ ∩ (cid:54) ∅ We then have U (U + ρ(g)) = , meaning U (RgU) = . This ρ shows that S satisﬁes (R ). ⇒ 6 → (i) = (iii). Let ρ : G Z be a homomorphism to a compact ⊆ abelian group Z and assume S G satisﬁes (R ). Assume, without ⊆ 6 loss of generality, that ρ(G) = Z. Let U Z be a neighborhood of ∈ ⊆ − ⊆ 0 Z, and let V U be such that V V U. Since S satisﬁes R , ∈ ∩ (cid:54) ∅ ∈ − 6 there is a g S such that V (V + ρ(g)) = , meaning ρ(g) V V , ∈ ∈ so ρ(g) U. Since U is an arbitrary neighborhood of 0 Z, we have ∈ shown that 0 ρ(S). ⇒ (iv) = (i). Suppose S satisﬁes condition (iv) and that (Z, R ) ⊆ ρ is a minimal group rotation. Let U Z be a nonempty open set, so that m(U) > 0, where m is the Haar probability measure on Z. ∩ ∈ Condition (iv) implies m(U (U + ρ(g))) > 0 for some g S, so that ∩ (cid:54) ∅ ⊆ U (U + ρ(g)) = for this g. Since U Z was an arbitrary open set, this shows that S satisﬁes (R ). ⇒ 6 (iii) = (iv). Let (Z, m, R ) be a group rotation G-system. For ⊆ ρ (cid:55)→ ∩ measurable sets D Z, the map z m(D (D + z)) is continuous. If ∩ m(D) > 0, we conclude that m(D (D + z)) > 0 for all z suﬃciently ∩ close to 0, so condition (iii) implies m(D (D + ρ(g))) > 0 for some ∈ (cid:3) g S. See Section for the deﬁnitions of “measure expanding,” “measure transitive,” etc. 6Here we are using the fact that every homomorphism from G to a compact group is continuous in the Bohr topology. ##LTLine## ##LTLine## ##LTLine##

text: SINGLE

text: RECURRENCE

text: Proof.

text: We

text: prove

text: (iii)

text: (ii)

text: (i)

text: (iii),

text: then

text: (iv)

text: (i)

text: and

text: (iii)

text: (iv).

text: (iii)

text: (ii).

text: Suppose

text: S

text: satisﬁes

text: condition

text: (iii),

text: and

text: let

text: W

text: G

text: be

text: a

text: Bohr

text: neighborhood

text: of

text: so

text: that

text: there

text: are

text: homomorphisms

text: T

text: T

text: ρ

text: ρ

text: G

text: and

text: a

text: neighborhood

text: V

text: of

text: such

text: that

text: W

text: con-

text: k

text: T

text: tains

text: k

text: ρ

text: Let

text: Z

text: be

text: the

text: group

text: k

text: and

text: ρ

text: G

text: Z

text: be

text: the

text: homo-

text: i

text: morphism

text: given

text: by

text: ρ(g)

text: (ρ

text: (g),

text: ρ

text: (g)).

text: Let

text: U

text: V

text: V

text: ∈k

text: Z,

text: so

text: that

text: U

text: is

text: a

text: neighborhood

text: of

text: Z.

text: Since

text: S

text: satisﬁes

text: condition

text: (iii),

text: there

text: is

text: a

text: g

text: S

text: such

text: that

text: ρ(g)

text: U.

text: Then

text: ρ

text: (g)

text: V

text: for

text: each

text: i,

text: i

text: and

text: we

text: conclude

text: that

text: g

text: W

text: (ii)

text: (i).

text: Suppose

text: S

text: W

text: for

text: every

text: Bohr

text: neighborhood

text: of

text: G.

text: Let

text: (Z,

text: R

text: be

text: a

text: minimal

text: group

text: rotation,

text: and

text: let

text: U

text: Z

text: be

text: ρ

text: a

text: nonempty

text: open

text: set.

text: Choose

text: a

text: neighborhood

text: V

text: of

text: Z

text: such

text: that

text: U

text: (U

text: v)

text: for

text: every

text: v

text: V

text: and

text: let

text: W

text: ρ

text: Then

text: W

text: is

text: a

text: Bohr

text: of

text: so

text: there

text: exists

text: g

text: S

text: W

text: meaning

text: ρ(g)

text: V

text: We

text: then

text: have

text: U

text: (U

text: ρ(g))

text: meaning

text: U

text: (RgU)

text: This

text: ρ

text: shows

text: that

text: S

text: satisﬁes

text: (R

text: (i)

text: (iii).

text: Let

text: ρ

text: G

text: Z

text: be

text: a

text: homomorphism

text: to

text: a

text: compact

text: abelian

text: group

text: Z

text: and

text: assume

text: S

text: G

text: satisﬁes

text: (R

text: Assume,

text: without

text: loss

text: of

text: generality,

text: that

text: ρ(G)

text: Z.

text: Let

text: U

text: Z

text: be

text: a

text: neighborhood

text: of

text: Z,

text: and

text: let

text: V

text: U

text: be

text: such

text: that

text: V

text: V

text: U.

text: Since

text: S

text: satisﬁes

text: R

text: there

text: is

text: a

text: g

text: S

text: such

text: that

text: V

text: (V

text: ρ(g))

text: meaning

text: ρ(g)

text: V

text: V

text: so

text: ρ(g)

text: U.

text: Since

text: U

text: is

text: an

text: arbitrary

text: neighborhood

text: of

text: Z,

text: we

text: have

text: shown

text: that

text: ρ(S).

text: (iv)

text: (i).

text: Suppose

text: S

text: satisﬁes

text: condition

text: (iv)

text: and

text: that

text: (Z,

text: R

text: ρ

text: is

text: a

text: minimal

text: group

text: rotation.

text: Let

text: U

text: Z

text: be

text: a

text: nonempty

text: open

text: set,

text: so

text: that

text: m(U)

text: where

text: m

text: is

text: the

text: Haar

text: probability

text: measure

text: on

text: Z.

text: Condition

text: (iv)

text: implies

text: m(U

text: (U

text: ρ(g)))

text: for

text: some

text: g

text: S,

text: so

text: that

text: U

text: (U

text: ρ(g))

text: for

text: this

text: g.

text: Since

text: U

text: Z

text: was

text: an

text: arbitrary

text: open

text: set,

text: this

text: shows

text: that

text: S

text: satisﬁes

text: (R

text: (iii)

text: (iv).

text: Let

text: (Z,

text: m,

text: R

text: be

text: a

text: group

text: rotation

text: G-system.

text: For

text: ρ

text: measurable

text: sets

text: D

text: Z,

text: the

text: map

text: z

text: m(D

text: (D

text: z))

text: is

text: continuous.

text: If

text: m(D)

text: we

text: conclude

text: that

text: m(D

text: (D

text: z))

text: for

text: all

text: z

text: suﬃciently

text: close

text: to

text: so

text: condition

text: (iii)

text: implies

text: m(D

text: (D

text: ρ(g)))

text: for

text: some

text: g

text: S.

text: See

text: Section

text: for

text: the

text: deﬁnitions

text: of

text: “measure

text: expanding,”

text: “measure

text: transitive,”

text: etc.

text: we

text: are

text: using

text: the

text: fact

text: that

text: every

text: homomorphism

text: from

text: G

text: to

text: a

text: compact

text: group

text: is

text: continuous

text: in

text: the

text: Bohr

text: topology.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 34 JOHN T. GRIESMER ⊆ Lemma 5.3. Let G be a countable abelian group and S G. The following are equivalent. • (i) S satisﬁes (R ). 6 (ii) S is dense in the Bohr topology of G. (iii) Every translate of S is a set of measurable recurrence for group rotation G-systems. The following are equivalent. (iv) Every translate of S is a set of chromatic recurrence. • (v) S satisﬁes (R ). 5 (vi) S is transitive for minimal G-systems. (vii) S is expanding for minimal G-systems. The following are equivalent. (viii) Every translate of S is a set of density recurrence. • (ix) S satisﬁes (R ). 4 (x) S is measure transitive. (xi) S is measure expanding. Proof. The equivalence of (i), (ii), and (iii) is a consequence of Lemma 5.2 and the deﬁnition of the Bohr topology. The equivalence of (iv) and (v) is due to Part (ii) of Proposition 2.9. ⇒ (v) = (vi). Let (X, T ) be a minimal topological G-system with ⊆ U, V X nonempty open sets. By the minimality of (X, T ) there ∈ ∩ (cid:54) ∅ − exists g G such that W := U T gV = . Since S g is a set of ∈ ∩ − (cid:54) ∅ topological recurrence, there exists h S such that W T h gW = , meaning ∩ ∩ − ∩ (cid:54) ∅ U T gV T h g(U T gV ) = , ∩ (cid:54) ∅ ⊆ which implies U T hV = . Since U, V X are arbitrary nonempty open sets, we have shown that S is transitive for minimal G-systems. ⇒ (vi) = (vii). Let (X, T ) be a minimal topological G-system and ∈ let x X. We will show that for each nonempty open set U, there ∈ is a dense open set of points V such that for all x V , there exists ∈ ∈ U U ⊆ g S such that T gx U. Fix a nonempty open set U X. By ⊆ ∈ condition (vi) for every nonempty open W X there exists g S

text: JOHN

text: T.

text: GRIESMER

text: Lemma

text: Let

text: G

text: be

text: a

text: countable

text: abelian

text: group

text: and

text: S

text: G.

text: The

text: following

text: are

text: equivalent.

text: (i)

text: S

text: satisﬁes

text: (R

text: (ii)

text: S

text: is

text: dense

text: in

text: the

text: Bohr

text: topology

text: of

text: G.

text: (iii)

text: Every

text: translate

text: of

text: S

text: is

text: a

text: set

text: of

text: measurable

text: recurrence

text: for

text: group

text: rotation

text: G-systems.

text: The

text: following

text: are

text: equivalent.

text: (iv)

text: Every

text: translate

text: of

text: S

text: is

text: a

text: set

text: of

text: chromatic

text: recurrence.

text: (v)

text: S

text: satisﬁes

text: (R

text: (vi)

text: S

text: is

text: transitive

text: for

text: minimal

text: G-systems.

text: (vii)

text: S

text: is

text: expanding

text: for

text: minimal

text: G-systems.

text: The

text: following

text: are

text: equivalent.

text: (viii)

text: Every

text: translate

text: of

text: S

text: is

text: a

text: set

text: of

text: density

text: recurrence.

text: (ix)

text: S

text: satisﬁes

text: (R

text: (x)

text: S

text: is

text: measure

text: transitive.

text: (xi)

text: S

text: is

text: measure

text: expanding.

text: Proof.

text: The

text: equivalence

text: of

text: (i),

text: (ii),

text: and

text: (iii)

text: is

text: a

text: consequence

text: of

text: Lemma

text: and

text: the

text: deﬁnition

text: of

text: the

text: Bohr

text: topology.

text: The

text: equivalence

text: of

text: (iv)

text: and

text: (v)

text: is

text: due

text: to

text: Part

text: (ii)

text: of

text: Proposition

text: (v)

text: (vi).

text: Let

text: (X,

text: T

text: be

text: a

text: minimal

text: topological

text: G-system

text: with

text: U,

text: V

text: X

text: nonempty

text: open

text: sets.

text: By

text: the

text: minimality

text: of

text: (X,

text: T

text: there

text: exists

text: g

text: G

text: such

text: that

text: W

text: U

text: T

text: gV

text: Since

text: S

text: g

text: is

text: a

text: set

text: of

text: topological

text: recurrence,

text: there

text: exists

text: h

text: S

text: such

text: that

text: W

text: T

text: h

text: gW

text: meaning

text: U

text: T

text: gV

text: T

text: h

text: g(U

text: T

text: gV

text: which

text: implies

text: U

text: T

text: hV

text: Since

text: U,

text: V

text: X

text: are

text: arbitrary

text: nonempty

text: open

text: sets,

text: we

text: have

text: shown

text: that

text: S

text: is

text: transitive

text: for

text: minimal

text: G-systems.

text: (vi)

text: (vii).

text: Let

text: (X,

text: T

text: be

text: a

text: minimal

text: topological

text: G-system

text: and

text: let

text: x

text: X.

text: We

text: will

text: show

text: that

text: for

text: each

text: nonempty

text: open

text: set

text: U,

text: there

text: is

text: a

text: dense

text: open

text: set

text: of

text: points

text: V

text: such

text: that

text: for

text: all

text: x

text: V

text: there

text: exists

text: U

text: U

text: g

text: S

text: such

text: that

text: T

text: gx

text: U.

text: Fix

text: a

text: nonempty

text: open

text: set

text: U

text: X.

text: By

text: condition

text: (vi)

text: for

text: every

text: nonempty

text: open

text: W

text: X

text: there

text: exists

text: g

text: S


text: SINGLE(cid:83)RECURRENCE 35 ∩ (cid:54) ∅ ∈ such that T gW U = . For each open set W and each g S let ∩ − (cid:84) W = W T gU. Then V := ⊆ ∈ W is the desired dense g U W X open,g G g open set. U Let be a countable base for the topology of X. Then E := ∈U V ∈ { ∈ } U U is a dense G set such that for all x E, T gx : g S is dense in X. ⇒ δ (vii) = (iv). Condition (vii) is translation invariant, so it suﬃces to prove that if (vii) holds, then S is a set of topological recurrence. ⊆ Let (X, T ) be a minimal topological G-system and U X a nonempty ∈ ∈ open set. Condition (vii) permits us to choose x U and g S such ∈ ∩ (cid:54) ∅ that T gx U. We conclude that U T gU = for this g. Since U is an arbitrary nonempty open set, we conclude that S is a set of topological recurrence. The equivalence of (viii) and (ix) follows directly from Part (i) of Proposition 2.9. ⇒ ⊆ (ix) = (x). Let S G satisfy (ix) and let (X, µ, T ) be a mea- ⊆ ∈ sure preserving G-system. Let C, D X and g G be such that ∩ ∩ − µ(C T gD) > 0. Let E = C T gD. Since S g is a set of mea- ∈ ∩ − surable recurrence, there is an h S such that µ(E T h gE) > 0. Consequently ∩ ∩ − ∩ µ(C T gD T h g(C T gD)) > 0, ∩ which implies µ(C T hD) > 0. Hence S is measure transitive. ⇒(cid:83) ⊆ (x) = (xi). Let S G satisfy condition (x) and let (X, µ, T ) be an ⊆ ergodic measure preserving G-system. Let D X have µ(D) > 0, and \ let E = ∈ T gD. Suppose, to get a contradiction, that µ(X E) > 0. g S ∈ \ ∩ By the ergodicity of (X, µ, T ) there exists g S such that µ((X E) ∈ T gD) > 0. Condition (x) then implies there exists h S such that \ ∩ ⊆ µ((X E) T hD) > 0, a contradiction, since T hD E. ⇒ (xi) = (viii). Since condition (xi) is translation invariant, it ⊆ suﬃces to prove that S is a set of density recurrence. Let A G have ∗ d (A) > 0. Then by Lemma 5.8 there is an ergodic measure preserving ⊆ − system (X, µ, T ) and a set D X having µ(D) > 0 such that A A (cid:0)(cid:83) { (cid:1)∈ ∩ } contains g G : µ(D T gD) > 0 . Now condition (xi) implies ∈ ∩ that there exists g S such that µ(D T gD) > 0 (since otherwise ≤ − − ∩ (cid:54) ∅ µ ∈ T gD 1 µ(D)) and we conclude that (A A) S = . g S ⊆ ∗ Since A G was an arbitrary set having d (A) > 0, we have shown (cid:3) that S is a set of density recurrence.

text: such

text: that

text: T

text: gW

text: U

text: For

text: each

text: open

text: set

text: W

text: and

text: each

text: g

text: S

text: let

text: W

text: W

text: T

text: gU.

text: Then

text: V

text: W

text: is

text: the

text: desired

text: dense

text: g

text: U

text: W

text: X

text: open,g

text: G

text: g

text: open

text: set.

text: U

text: Let

text: be

text: a

text: countable

text: base

text: for

text: the

text: topology

text: of

text: X.

text: Then

text: E

text: ∈U

text: V

text: U

text: U

text: is

text: a

text: dense

text: G

text: set

text: such

text: that

text: for

text: all

text: x

text: E,

text: T

text: gx

text: g

text: S

text: is

text: dense

text: in

text: X.

text: δ

text: (vii)

text: (iv).

text: Condition

text: (vii)

text: is

text: translation

text: invariant,

text: so

text: it

text: suﬃces

text: to

text: prove

text: that

text: if

text: (vii)

text: holds,

text: then

text: S

text: is

text: a

text: set

text: of

text: topological

text: recurrence.

text: Let

text: (X,

text: T

text: be

text: a

text: minimal

text: topological

text: G-system

text: and

text: U

text: X

text: a

text: nonempty

text: open

text: set.

text: Condition

text: (vii)

text: permits

text: us

text: to

text: choose

text: x

text: U

text: and

text: g

text: S

text: such

text: that

text: T

text: gx

text: U.

text: We

text: conclude

text: that

text: U

text: T

text: gU

text: for

text: this

text: g.

text: Since

text: U

text: is

text: an

text: arbitrary

text: nonempty

text: open

text: set,

text: we

text: conclude

text: that

text: S

text: is

text: a

text: set

text: of

text: topological

text: recurrence.

text: The

text: equivalence

text: of

text: (viii)

text: and

text: (ix)

text: follows

text: directly

text: from

text: Part

text: (i)

text: of

text: Proposition

text: (ix)

text: (x).

text: Let

text: S

text: G

text: satisfy

text: (ix)

text: and

text: let

text: (X,

text: µ,

text: T

text: be

text: a

text: mea-

text: sure

text: preserving

text: G-system.

text: Let

text: C,

text: D

text: X

text: and

text: g

text: G

text: be

text: such

text: that

text: µ(C

text: T

text: gD)

text: Let

text: E

text: C

text: T

text: gD.

text: Since

text: S

text: g

text: is

text: a

text: set

text: of

text: mea-

text: surable

text: recurrence,

text: there

text: is

text: an

text: h

text: S

text: such

text: that

text: µ(E

text: T

text: h

text: gE)

text: Consequently

text: µ(C

text: T

text: gD

text: T

text: h

text: g(C

text: T

text: gD))

text: which

text: implies

text: µ(C

text: T

text: hD)

text: Hence

text: S

text: is

text: measure

text: transitive.

text: (x)

text: (xi).

text: Let

text: S

text: G

text: satisfy

text: condition

text: (x)

text: and

text: let

text: (X,

text: µ,

text: T

text: be

text: an

text: ergodic

text: measure

text: preserving

text: G-system.

text: Let

text: D

text: X

text: have

text: µ(D)

text: and

text: let

text: E

text: T

text: gD.

text: Suppose,

text: to

text: get

text: a

text: contradiction,

text: that

text: µ(X

text: E)

text: g

text: S

text: By

text: the

text: ergodicity

text: of

text: (X,

text: µ,

text: T

text: there

text: exists

text: g

text: S

text: such

text: that

text: µ((X

text: E)

text: T

text: gD)

text: Condition

text: (x)

text: then

text: implies

text: there

text: exists

text: h

text: S

text: such

text: that

text: µ((X

text: E)

text: T

text: hD)

text: a

text: contradiction,

text: since

text: T

text: hD

text: E.

text: (xi)

text: (viii).

text: Since

text: condition

text: (xi)

text: is

text: translation

text: invariant,

text: it

text: suﬃces

text: to

text: prove

text: that

text: S

text: is

text: a

text: set

text: of

text: density

text: recurrence.

text: Let

text: A

text: G

text: have

text: d

text: (A)

text: Then

text: by

text: Lemma

text: there

text: is

text: an

text: ergodic

text: measure

text: preserving

text: system

text: (X,

text: µ,

text: T

text: and

text: a

text: set

text: D

text: X

text: having

text: µ(D)

text: such

text: that

text: A

text: A

text: contains

text: g

text: G

text: µ(D

text: T

text: gD)

text: Now

text: condition

text: (xi)

text: implies

text: that

text: there

text: exists

text: g

text: S

text: such

text: that

text: µ(D

text: T

text: gD)

text: (since

text: otherwise

text: µ

text: T

text: gD

text: µ(D))

text: and

text: we

text: conclude

text: that

text: (A

text: A)

text: S

text: g

text: S

text: Since

text: A

text: G

text: was

text: an

text: arbitrary

text: set

text: having

text: d

text: (A)

text: we

text: have

text: shown

text: that

text: S

text: is

text: a

text: set

text: of

text: density

text: recurrence.


text: SINGLE RECURRENCE 43 35. Imre Z. Ruzsa, Essential components, Proc. London Math. Soc. (3) 54 (1987), no. 1, 38–56. 36. , Arithmetic progressions in sumsets, Acta Arith. 60 (1991), no. 2, 191– 202. 37. Sadahiro Saeki, Bohr compactiﬁcation and continuous measures, Proc. Amer. Math. Soc. 80 (1980), no. 2, 244–246. 38. A. S´ark¨ozy, On diﬀerence sets of sequences of integers. III, Acta Math. Acad. Sci. Hungar. 31 (1978), no. 3-4, 355–386. MR 487031 39. Benjamin Weiss, Single orbit dynamics, CBMS Regional Conference Series in Mathematics, vol. 95, American Mathematical Society, Providence, RI, 2000. MR 1727510 40. J. Wolf, The structure of popular diﬀerence sets, Israel J. Math. 179 (2010), 253–278. Department of Applied Mathematics and Statistics, Colorado School of Mines, Golden, Colorado Email address: jtgriesmer@gmail.com ##LTLine##

text: SINGLE

text: RECURRENCE

label: reference

text: Imre

text: Z.

text: Ruzsa,

text: Essential

text: components,

text: Proc.

text: London

text: Math.

text: Soc.

text: no.

text: Arithmetic

text: progressions

text: in

text: sumsets,

text: Acta

text: Arith.

text: no.

text: Sadahiro

text: Saeki,

text: Bohr

text: compactiﬁcation

text: and

text: continuous

text: measures,

text: Proc.

text: Amer.

text: Math.

text: Soc.

text: no.

text: A.

text: S´ark¨ozy,

text: On

text: diﬀerence

text: sets

text: of

text: sequences

text: of

text: integers.

text: III,

text: Acta

text: Math.

text: Acad.

text: Sci.

text: Hungar.

text: no.

text: MR

text: Benjamin

text: Weiss,

text: Single

text: orbit

text: dynamics,

text: CBMS

text: Regional

text: Conference

text: Series

text: in

text: Mathematics,

text: vol.

text: American

text: Mathematical

text: Society,

text: Providence,

text: RI,

text: MR

text: J.

text: Wolf,

text: The

text: structure

text: of

text: popular

text: diﬀerence

text: sets,

text: Israel

text: J.

text: Math.

text: Department

text: of

text: Applied

text: Mathematics

text: and

text: Statistics,

text: Colorado

text: School

text: of

text: Mines,

text: Golden,

text: Colorado

text: Email

text: address:

text: jtgriesmer@gmail.com

text: ##LTLine##


text: ∪ (cid:48) (cid:48) ⊆ Since E has size n and is disjoint from D A , (4) implies we may choose E E such that for all ∈ D | ∪ (cid:48)∪ (cid:48)| ∈ D M M ∪ (cid:48)∪ (cid:48) H C¯ , C A E = n. Now for each C¯ , set = [C A E ]. Because is a hereditary L M ∈ H ∈ D C¯ ∗ ∗ ∈ D ∈ D -property, for all C¯ . Fix some C¯∗ = (c¯ , . . . , c¯ ) . Given C¯ = (c¯ , . . . , c¯ ) , C¯ 1 (cid:48) ∪m (cid:48) 1 m note that C¯∗ and C¯ have the same equality type over A E . Therefore there is a bijection ∪ (cid:48) ∪ (cid:48) → ∪ (cid:48) ∪ (cid:48) (cid:48) ∪ (cid:48) ∗ ≤ ≤ f : C A E C∗ A E , which ﬁxes A E and which sends c¯ to c¯ for each 1 i m. C¯ M∗ L ∪ (cid:48) ∪ (cid:48) i i M Let be the -structure with universe C∗ A E , and which is isomorphic to via the C¯ H M∗ ∈ H ∈ D (cid:54) C¯(cid:48) bijection f . Since is closed under isomorphism, for all C¯ . Clearly C¯ = C¯ implies M∗ (cid:54) M∗C¯ (cid:48) C¯ A (cid:22) {M∗ ∈ D} C¯ = C¯|(cid:48)D(|since then C¯ and C¯ rHealize distinct elements∪of S(cid:48) ϕ∪,m((cid:48) , ρ A(cid:48)))|. Th∪us (cid:48) ∪ C¯(cid:48)|: C¯ consists of distinct elements of , all with universe C∗ A E . Since C∗ A E = n and H |H | ≥ |D| (cid:98) (cid:99) is closed under isomorphism, this shows = 2m(cid:96). Since m = n/3t and n is large, we |H | ≥ ≥ n have 2m(cid:96) 2Cn(cid:96) for C = (1/4t)(cid:96). n We will use the following result from [22] in our proof of Theorem 2. H L Theorem 8. Suppose is a hereditary -property. Then the following limit exists. H |H | π( ) = l→im∞ n 1/(nr). n H |H | H H ≤ |H | Moreover, if π( ) > 1, then n = π( )(nr)+o(nr), and if π( ) 1, then n = 2o(nr). | | We now ﬁx some notation. A formula ϕ(x¯; y¯) is trivially partitioned if y¯ = 0. Given a set X ≥ { ∈ (cid:54) (cid:54) } M ∈ H and n 1, Xn = (x , . . . , x ) Xn : i = j implies x = x . If , ϕ(x¯; y¯) is a formula, A ⊆ | | 1 ∈ n| | i j M A M y¯ , and a¯ , . . . , a¯ M x¯ are pairwise distinct, then deﬁne qftp (a¯ , . . . , a¯ ; ) to be the ∪1 ∪ k A M | ∪ ∪ ϕ 1 k element p (x¯ ) . . . p (x¯ ) of S ( ) such that = p (a¯ ) . . . p (a¯ ). 1 1 k k ϕ,k 1 1 k k The following notation is from [3]. Let Index be the set of pairs (R, p) where R(x , . . . , x ) L ∈ 1 t is a relation of and p is a partition of [t]. Given (R, p) Index, deﬁne R (z¯) be the formula p obtained as follows. Suppose p , . . . , p are the parts of p, and for each i, m = min p . For each ∈ { } 1 s i i x x , . . . , x , ﬁnd which part of p contains j, say p , then replace x with x . Relabel the j 1 t (cid:86) i j mi L variables (x , . . . , x ) = (z , . . . , z ) and let R (z¯) be the resulting formula. Now let rel( ) m1 ms 1 s p consist of all formulas ϕ(u¯; v¯) obtained by permuting and/or partitioning the variables of a formula ∧ (cid:54) ∈ of the form R (z¯) ≤ (cid:54) ≤| | z = z , where (R, p) Index. p 1 i=j z¯ i Lj M M { ∈ | | | | M | } Given a formula ϕ(u¯; v¯) and an -structure , let ϕ( ) = a¯¯b M u¯ + v¯ : = ϕ(a¯;¯b) . ∈ L M L M ⊆ | | | | | | | | ≤ Observe that if ϕ(u¯; v¯) rel( ) and is an -structure, then ϕ( ) M u¯ + v¯ , and u¯ + v¯ r. L M M We will use the fact that any -structure is completely determined by knowing ϕ( ) for all ∈ L M ∈ L | | trivially partitioned ϕ rel( ), or by knowing ϕ( ) for all ϕ(u¯; v¯) rel( ) with u¯ = 1. Given ≥ a formula ϕ(u¯; v¯) and n 1, set F { ⊆ | | | | M ∈ H M } (n) := U [n] u¯ + v¯ : there is with ϕ( ) = U . ϕ n H We now prove Theorem 3 and then Theorem 2, which we restate here for convenience. Recall is L L a ﬁxed hereditary -property and the maximum arity of is r. Theorem 3. One of the following holds. ∗ H ∞ |H | ≤ (a) V C ( ) < and there K > 0 such that for suﬃciently large n, nK or 0 n ∗ H ∞ |H | ≥ (b) V C ( ) = , and there is a constant C > 0 such that for suﬃciently large n, 2Cn. 0 n 10 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Since

text: E

text: has

text: size

text: n

text: and

text: is

text: disjoint

text: from

text: D

text: A

text: implies

text: we

text: may

text: choose

text: E

text: E

text: such

text: that

text: for

text: all

text: D

text: D

text: M

text: M

text: H

text: C¯

text: C

text: A

text: E

text: n.

text: Now

text: for

text: each

text: C¯

text: set

text: [C

text: A

text: E

text: Because

text: is

text: a

text: hereditary

text: L

text: M

text: H

text: D

text: C¯

text: D

text: D

text: -property,

text: for

text: all

text: C¯

text: Fix

text: some

text: C¯∗

text: (c¯

text: c¯

text: Given

text: C¯

text: (c¯

text: c¯

text: C¯

text: ∪m

text: m

text: note

text: that

text: C¯∗

text: and

text: C¯

text: have

text: the

text: same

text: equality

text: type

text: over

text: A

text: E

text: Therefore

text: there

text: is

text: a

text: bijection

text: f

text: C

text: A

text: E

text: C∗

text: A

text: E

text: which

text: ﬁxes

text: A

text: E

text: and

text: which

text: sends

text: c¯

text: to

text: c¯

text: for

text: each

text: i

text: m.

text: C¯

text: M∗

text: L

text: i

text: i

text: M

text: Let

text: be

text: the

text: -structure

text: with

text: universe

text: C∗

text: A

text: E

text: and

text: which

text: is

text: isomorphic

text: to

text: via

text: the

text: C¯

text: H

text: M∗

text: H

text: D

text: bijection

text: f

text: Since

text: is

text: closed

text: under

text: isomorphism,

text: for

text: all

text: C¯

text: Clearly

text: C¯

text: C¯

text: implies

text: M∗

text: M∗C¯

text: C¯

text: A

text: {M∗

text: D}

text: C¯

text: then

text: C¯

text: and

text: C¯

text: rHealize

text: distinct

text: elements∪of

text: ρ

text: Th∪us

text: C¯

text: consists

text: of

text: distinct

text: elements

text: of

text: all

text: with

text: universe

text: C∗

text: A

text: E

text: Since

text: C∗

text: A

text: E

text: n

text: and

text: H

text: |H

text: |D|

text: is

text: closed

text: under

text: isomorphism,

text: this

text: shows

text: Since

text: m

text: and

text: n

text: is

text: large,

text: we

text: |H

text: n

text: have

text: for

text: C

text: n

text: We

text: will

text: use

text: the

text: following

text: result

text: from

text: in

text: our

text: proof

text: of

text: Theorem

text: H

text: L

text: Theorem

text: Suppose

text: is

text: a

text: hereditary

text: -property.

text: Then

text: the

text: following

text: limit

text: exists.

text: H

text: |H

text: π(

text: l→im∞

text: n

text: n

text: H

text: |H

text: H

text: H

text: |H

text: Moreover,

text: if

text: π(

text: then

text: n

text: π(

text: )(nr)+o(nr),

text: and

text: if

text: π(

text: then

text: n

text: We

text: now

text: ﬁx

text: some

text: notation.

text: A

text: formula

text: ϕ(x¯;

text: y¯)

text: is

text: trivially

text: partitioned

text: if

text: y¯

text: Given

text: a

text: set

text: X

text: M

text: H

text: and

text: n

text: Xn

text: (x

text: x

text: Xn

text: i

text: j

text: implies

text: x

text: x

text: If

text: ϕ(x¯;

text: y¯)

text: is

text: a

text: formula,

text: A

text: n|

text: i

text: j

text: M

text: A

text: M

text: y¯

text: and

text: a¯

text: a¯

text: M

text: x¯

text: are

text: pairwise

text: distinct,

text: then

text: deﬁne

text: qftp

text: (a¯

text: a¯

text: to

text: be

text: the

text: ∪1

text: k

text: A

text: M

text: ϕ

text: k

text: element

text: p

text: (x¯

text: p

text: (x¯

text: of

text: S

text: such

text: that

text: p

text: (a¯

text: p

text: (a¯

text: k

text: k

text: ϕ,k

text: k

text: k

text: The

text: following

text: notation

text: is

text: from

text: Let

text: Index

text: be

text: the

text: set

text: of

text: pairs

text: (R,

text: p)

text: where

text: R(x

text: x

text: L

text: t

text: is

text: a

text: relation

text: of

text: and

text: p

text: is

text: a

text: partition

text: of

text: [t].

text: Given

text: (R,

text: p)

text: Index,

text: deﬁne

text: R

text: (z¯)

text: be

text: the

text: formula

text: p

text: obtained

text: as

text: follows.

text: Suppose

text: p

text: p

text: are

text: the

text: parts

text: of

text: p,

text: and

text: for

text: each

text: i,

text: m

text: min

text: p

text: For

text: each

text: s

text: i

text: i

text: x

text: x

text: x

text: ﬁnd

text: which

text: part

text: of

text: p

text: contains

text: j,

text: say

text: p

text: then

text: replace

text: x

text: with

text: x

text: Relabel

text: the

text: j

text: t

text: i

text: j

text: mi

text: L

text: variables

text: (x

text: x

text: (z

text: z

text: and

text: let

text: R

text: (z¯)

text: be

text: the

text: resulting

text: formula.

text: Now

text: let

text: rel(

text: ms

text: s

text: p

text: consist

text: of

text: all

text: formulas

text: ϕ(u¯;

text: v¯)

text: obtained

text: by

text: permuting

text: and/or

text: partitioning

text: the

text: variables

text: of

text: a

text: formula

text: of

text: the

text: form

text: R

text: (z¯)

text: z

text: z

text: where

text: (R,

text: p)

text: Index.

text: p

text: i=j

text: z¯

text: i

text: Lj

text: M

text: M

text: M

text: Given

text: a

text: formula

text: ϕ(u¯;

text: v¯)

text: and

text: an

text: -structure

text: let

text: ϕ(

text: a¯¯b

text: M

text: u¯

text: v¯

text: ϕ(a¯;¯b)

text: L

text: M

text: L

text: M

text: Observe

text: that

text: if

text: ϕ(u¯;

text: v¯)

text: rel(

text: and

text: is

text: an

text: -structure,

text: then

text: ϕ(

text: M

text: u¯

text: v¯

text: and

text: u¯

text: v¯

text: r.

text: L

text: M

text: M

text: We

text: will

text: use

text: the

text: fact

text: that

text: any

text: -structure

text: is

text: completely

text: determined

text: by

text: knowing

text: ϕ(

text: for

text: all

text: L

text: M

text: L

text: trivially

text: partitioned

text: ϕ

text: rel(

text: or

text: by

text: knowing

text: ϕ(

text: for

text: all

text: ϕ(u¯;

text: v¯)

text: rel(

text: with

text: u¯

text: Given

text: a

text: formula

text: ϕ(u¯;

text: v¯)

text: and

text: n

text: set

text: F

text: M

text: H

text: M

text: (n)

text: U

text: [n]

text: u¯

text: v¯

text: there

text: is

text: with

text: ϕ(

text: U

text: ϕ

text: n

text: H

text: We

text: now

text: prove

text: Theorem

text: and

text: then

text: Theorem

text: which

text: we

text: restate

text: here

text: for

text: convenience.

text: Recall

text: is

text: L

text: L

text: a

text: ﬁxed

text: hereditary

text: -property

text: and

text: the

text: maximum

text: arity

text: of

text: is

text: r.

text: Theorem

text: One

text: of

text: the

text: following

text: holds.

text: H

text: |H

text: (a)

text: V

text: C

text: and

text: there

text: K

text: such

text: that

text: for

text: suﬃciently

text: large

text: n,

text: nK

text: or

text: n

text: H

text: |H

text: (b)

text: V

text: C

text: and

text: there

text: is

text: a

text: constant

text: C

text: such

text: that

text: for

text: suﬃciently

text: large

text: n,

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##