Paiva Tales
email: paivan@imag.fr

Hervé Nogueira

Martin

Qualitative Representation of Dynamic Attributes of Trajectories

Keywords: geographical information systems, trajectory analysis, semantic trajectories, dynamic, user profile, ontologies

Trajectory dynamic characteristics may be a very relevant source of information to analyze the behaviour of moving objects. However, most of existing works on trajectory representation deal only with basic parameters of trajectories, namely space and time. In this paper, we show how some derivatives of the spatio-temporal dimension, e.g. speed, acceleration, direction, may be integrated in trajectory modelling. We address the problem of representing trajectories in a way that qualitative descriptions of trajectories are stored and easily accessed through an ontology called QualiTraj which is also flexible enough to support relevant raw data representation. We validate our proposal with real GPS traces collected from a well-known sports tracking mobile application.

Introduction

The Internet as we know it today is constantly evolving to a more and more connected system thanks to the increasing quantity of data made available as linked data, building what is called the Semantic Web [START_REF] Bizer | Linked Data -The Story So Far[END_REF]. With semantic web technologies we are moving from the web of documents towards the web of data, where machines will be able to understand and reason about the connections among different datasets and therefore enable the development of richer applications. It is of common knowledge that ontologies are well suited to represent datasets in this new paradigm.

At the same time, we are witnessing the development of mobile technologies such as smart phones for the acquisition of data in conjunction with many sensors as well as the grow of technologies of geolocation (GPS, A-GPS, GLONASS) and identification (RFID). The convergence of these technologies allows the easy acquisition of information about the trajectories of users using mobile devices. The acquisition, management, modelling, and analysis of such data provide many challenges related to the integration of these data with systems that already exist. Therefore, it should be taken into account that the multidimensional and multifaceted aspects of these data potentially holds a very rich semantics. There is a vast amount of works that propose to bridge the gap between trajectory representation and Semantic Web technologies, mainly regarding the representation with ontologies [START_REF] Baglioni | An ontology-based approach for the semantic modelling and reasoning on trajectories[END_REF][START_REF] Camossi | Semanticbased Anomalous Pattern Discovery in Moving Object Trajectories[END_REF][START_REF] Van Hage | Combining ship trajectories and semantics with the simple event model (SEM)[END_REF][START_REF] Hu | A Geo-ontology Design Pattern for Semantic Trajectories[END_REF][START_REF] Parent | Semantic trajectories modeling and analysis[END_REF][START_REF] Wannous | Modelling Mobile Object Activities Based on Trajectory Ontology Rules Considering Spatial Relationship Rules[END_REF][START_REF] Yan | SeMiTri: A Framework for Semantic Annotation of Heterogeneous Trajectories[END_REF][START_REF] Yan | Trajectory Ontologies and Queries[END_REF].

The identification of mobility patterns has been an constant topic of interest in the GIScience area in several domains like tourism, road traffic, crisis management, marketing, etc. [START_REF] Güting | A foundation for representing and querying moving objects[END_REF]. Several works have dealt with trajectory analysis proposing new ways of comparing, segmenting and clustering moving object's paths. But most of them only handle the geometric aspect of trajectories and just a few deal with dynamic parameters like speed and acceleration explicitly [START_REF] Dodge | Revealing the physics of movement: Comparing the similarity of movement characteristics of different types of moving objects[END_REF][START_REF] Laube | Movement beyond the snapshot -dynamic analysis of geospatial lifelines[END_REF].

In most cases, the variability of dynamic properties is very high. Take as example the raw representation of speed of a runner in Figure 1. Although it is obvious that the movement did not suffer exactly the same variations as it is depicted in the graphic due to the intrinsic error and noise of GPS readings, we can observe that there is a need to simplify this information so it can become more useful. The development of new methods and tools to analyse movement components like the one shown in Figure 1 is still a great challenge. In this work, we argue that a qualitative representation of trajectories components are useful and enable new queries to be build and answer many application domain needs. The remainder of this paper is organized as follows: in section 2, we compare our work with similar proposals and highlight the differences between them. In section 3, we define what are the dynamic aspects considered in this paper. In section 4, the QualiTraj ontology is introduced, followed by a case study in section 5.

Related work

In [START_REF] Rehrl | An Approach to Semantic Processing of GPS Traces[END_REF], Rehrl et. al. proposed a method for semantic processing of GPS traces where information is extracted from raw data. Based on the assumption that the basic parameters to express motion in space and time are velocity and course, they defined six motion patterns with associated rules. The patterns are the following: stand still characterizes the absence of motion and is assumed when the velocity is less than 1 m/s; steady motion represents the periods when there is motion with constant velocity and is distinguished when velocity is greater than 1 m/s and acceleration lies between -0.3 m/s² and 0.3 m/s². Positive acceleration happens when the velocity increases and is greater than 1 m/s and acceleration is greater than 0.3 m/s²; negative acceleration is similar but acceleration should be less than -0.3 m/s². Positive course change is identified when there is a course change rate above 0.4 º/s, and negative course change is determined when this change is below -0.4 º/s.

While this categorization has as objective to improve the level of abstraction of motion data, the authors rely too heavily in thresholds to characterize speed, acceleration, and course changes. In an heterogeneous dataset, this approach does not seem adequate as these thresholds may vary depending on the mean of transportation. In our work, we preferred the usage of statistic measures whenever it was possible to avoid relying on thresholds that depends on the nature of the data being analyzed.

In [START_REF] Van Hage | Combining ship trajectories and semantics with the simple event model (SEM)[END_REF], van Hage et. al. presented the Simple Event Model (SEM) and its application in the maritime domain. In their use case, events are automatically recognized from the Automatic Identification System (AIS) raw data and represented as SEM instances. From that, it was possible to characterize some types of ship behavior like slowing down, speeding up, and anchored. Three types of data were collected in the form of time series: location, speed, and course. Due to the large dimensions of the tracked ships and the fact that they do not accelerate nor change their courses quickly, their movement are very regular and much more easy to compress by a piecewise linear algorithm. In our paper, instead of AIS data with speed information already included, we have at first just GPS raw data from which we have to calculate the speed profile. Moreover, the nature of motion data is very different: runners instead of ships. Runners may have a much more irregular speed, acceleration, and changes in course direction when compared to ships. Besides, we take a qualitative approach towards the characterization of movement.

What is dynamic?

One of the most important features of spatio-temporal systems is the ability to trace the path that a moving object follows during some time. A trajectory can be defined as the user defined record of the evolution of the position (perceived as a point) of an object that is moving in space during a given time interval in order to achieve a given goal [START_REF] Spaccapietra | A conceptual view on trajectories[END_REF]. A research topic that is constantly studied in the trajectory analysis domain is related to the representation of these spatio-temporal paths. While the representation of trajectories with ontologies have already been subject of many studies, the dynamic aspects of trajectories are generally just mentioned as simple attributes or even not mentioned. Most works about trajectory analysis limits themselves to the geometric representations of trajectories as a static curve [START_REF] Dodge | Towards a Taxonomy of Movement Patterns[END_REF].

The dynamic properties that we talk about in this paper may have different names among the literature. Dodge et. al. [START_REF] Dodge | Towards a Taxonomy of Movement Patterns[END_REF], for instance, call them movement parameters and separate them in three groups: primitive parameters, primary derivatives, and secondary derivatives. Each group is further organized in spatial, temporal and spatio-temporal dimensions. The primitive parameters are the ones that has been the subject of most studies in GIS (position and time). The primary derivatives are distance, direction, spatial extent, duration, travel time, speed and velocity. The secondary derivatives are spatial distribution, change of direction, sinuosity, temporal distribution, change of duration, acceleration, and approaching rate. In this work, we are going to focus on the speed derivative, as we believe that this aspect of trajectories is crucial to the characterization of the behaviour of a moving object.

The QualiTraj Ontology

In this section, we present a modeling approach that enables the representation of trajectories' dynamic characteristics in a high abstraction level through an ontology. Figure 2 shows the basic structure of QualiTraj, the main contribution of this work. The top level element is the Trajectory entity, which represents a spatio-temporal path followed by a moving object. Each trajectory may have one or more profiles. Each Profile represents one dynamic aspect of a trajectory (e.g. speed, acceleration, direction).

Profiles may have aggregated measures that might be useful depending on the application. Thus, we included the Global Attributes entity to store information like the average speed of the whole trajectory.

The Segment is the entity that represents a relevant change in the dynamic property occurred along the trajectory. This element contains the qualitative information itself stored in the Qualitative Value entity. Each Segment starts and ends at a Key Point, i.e. a location in space and time that define the bounds of the segment. The Key Points may also be used to retrieve important information, e.g. where and when the highest speed was achieved. While this kind of data is not mandatory because it is application-specific and, on the other hand, the start and end points must always be represented, there are three relationships between Segment and Key Point in the ontology being optional only the one called has_point.

The kind of change is stored in the Qualitative Value entity associated with each Segment. The application developer should determine which values compose the lexical space of this entity. Another important element to represent each Segment is the Coefficient, an entity that holds the slope of the line that connects the starting and ending points. Having this information may be useful if we want to infer the approximate value of the profiled characteristic using a linear equation. The next section shows an example of the usage of the QualiTraj ontology in a real scenario. Case study

The studies about mobility analysis are numerous in the literature. In order to validate them, it is of vital importance to work with a representative dataset. The capture of real-life spatio-temporal data is generally expensive and time consuming due to the need of adequate equipment, search for subjects willing to participate (e.g. taxi drivers, shoppers, students), among other factors. Fortunately, there are some available datasets that can be freely downloaded, like GeoLife [START_REF] Zheng | GeoLife: A collaborative social networking service among user, location and trajectory[END_REF][START_REF] Zheng | Mining interesting locations and travel sequences from GPS trajectories[END_REF], Reality Mining [START_REF] Eagle | Reality mining: sensing complex social systems[END_REF], geo-tagged photos from websites like Flickr 1 and Instagram 2 , among others.

One interesting source of trajectory data is sports tracking websites and mobile applications, e.g. RunKeeper 3 , Endomondo 4 , Sports Tracker 5 , Strava 6 , MapMyRun 7 , and have been source of studies like the one by Ferrari and Mamei [START_REF] Ferrari | Identifying and understanding urban sport areas using Nokia Sports Tracker[END_REF]. Notwithstanding the widespread adoption of these services by professional athletes as well as by casual practitioners of sports activities, the collected data is not always publicly available. The minor part of sites provide an open API for third-party applications to access user-generated data.

For our case study, we collected data from users of MapMyRun application that shared their workouts publicly. We gathered information about 10 users that logged activities in the city of Grenoble, France, represented by 66 trajectories in total. In order to be clearer, we are going to show the raw data transformation steps of one short workout as it becomes easier to spot the changes suffered by the time series through all the steps. Figure 3 shows the raw speed data being pre-1 www.flickr.com 2 www.instagram.com 3 www.runkeeper.com 4 www.endomondo.com 5 www.sports-tracker.com 6 www.strava.com 7 www.mapmyrun.com processed in order to simplify the stored data. The first graph shows the calculated speed at each point of the trajectory based on the latitude, longitude, and time difference between points. We have used the Haversine formula to calculate the approximate distance traveled during each sampled point. It is important to notice that a good speed approximation is heavily dependent on a good sampling rate, i.e. GPS fixes constantly recorded in small intervals of time.

The second step of the cleaning phase consists in detecting stops and moves of the tracked object. After that, we applied a Kalman filter [START_REF] Welch | An introduction to the Kalman filter[END_REF] in order to smooth the data and attenuate GPS position errors. The last step of the smoothing phase is to summary the data points with a piecewise linear segmentation [START_REF] Keogh | An online algorithm for segmenting time series[END_REF]. All the steps of the cleaning phase are depicted in Figure 3. In this specific example, the length of the time series was reduced from 60 points to only 28 points without losing the main characteristics of the signal. The final step in the speed representation of this trajectory consisted in creating the entities following the QualiTraj model. The lexical space used for the Qualitative Value entity was {"Increase", "Decrease", "Steady", and "Stop"}. Figure 4 shows the first two Segments represented with QualiTraj. The first segment consists in an increase of speed from 2.02 m/s to 2.40 m/s, which are the points of a line with an angle of 7.24 degrees. We omitted the timestamp and location of Key Points to improve the readability of the example. Notice that the same Key Point, "Key Point 2", has been reused in both segments, avoiding data duplication thanks to the graph structure of the ontological modeling approach.

Conclusion

In this paper, we demonstrated how it is possible to enrich raw trajectory data with dynamic aspects of movement and provide an infrastructure for querying this new knowledge through an ontology.

The representation of spatio-temporal data by means of ontologies is even more useful when the inference features of reasoners are explored. As a following activity of this work, we will investigate how reasoners can improve the analysis of patterns of dynamic movement parameters of trajectories. Queries that involve more than one moving object form and important group of queries about relative motion and should be studied in the future.

Another important development will be the connection of the proposed ontology with different linked data sources like the LinkedGeoData project [START_REF] Stadler | LinkedGeoData: A Core for a Web of Spatial Open Data[END_REF], which provides OpenStreetMaps information in the format suitable for the Semantic Web. For instance, we could formulate queries in the domain of traffic analysis to find drivers that do not slow down near traffic-calming features as the OpenStreetMaps dataset has a traffic-calming key for many possible features of this type, like bumpers, chicanes, cushions, and others. In this way, more complex queries and reasoning tasks can be also envisaged as future work.

Figure 1 :

 1 Figure 1: Time series of the speed profile of a runner captured by a smart phone application without any post processing treatment.

Figure 2 :

 2 Figure 2: The QualiTraj ontology

Figure 3 :

 3 Figure 3: The evolution of speed during a four-minute walk and the steps of post-processing: (a) is the raw data, in (b) stops and moves are identified, (c) is the filtered signal, and (d) shows the piecewise linear segmentation result.

Figure 4 :

 4 Figure 4: Part of qualitative representation of a trajectory using the QualiTraj ontology

Acknowledgments

The authors would like to thank the French Ministry of Higher Education and Research (Ministère de l'Enseignement Supérieur et de la Recherche de la France -MESR) for supporting this work.


Nikos Frantzikinakis

AND Emmanuel Lesigne

Máté Wierdl

RANDOM DIFFERENCES IN SZEMERÉDI'S THEOREM AND RELATED RESULTS

come

CONVENTIONS

In this paper, a dynamical system is a quadruple (X , Σ, µ, T ) where (X , Σ, µ) is a probability space, and T is a Σ-measurable, measure preserving transformation, i.e. for any A ∈ Σ, we have µ(T -1 A) = µ(A). Since the σ-algebra Σ doesn't play any special role in what follows, we omit it from our notation, and we just write (X , µ, T ) instead of (X , Σ, µ, T ).

When we talk about functions defined on some measure space, we always assume, the function is measurable.

We use the usual notational convention that the isometry of L 1 induced by a measure preserving transformation T is also denoted by the same letter T : T f (x) = f (T x).

The arbitrary constants c or C appearing in an estimate are always positive, and are absolute unless otherwise noted. The same constant may have a different value even in the same series of estimates.

The notation n<N means 0≤n<N , so 0 is included in the range of summation.

A lacunary sequence of positive real numbers or integers is a sequence {a 1 < a 2 < a 3 < • • • < a n < . . .} such that lim inf n→∞ a n+1 a n > 1. The cardinality of a set A is denoted by |A|.

INTRODUCTION, HISTORY

2.1. Intersective and recurrent sets. For a set A of positive integers, let A(M ) denote its counting function, the number of elements in A that are less than M ,

A(M ) = {a | a ∈ A, a < M } .

We denote by d (A) the upper density of

A d (A) = lim sup M →∞ A(M ) M .
The celebrated result of [Sze75a, Sze75b] says that if A is a set of positive integers with positive upper density, then for any positive one can find an + 1 long arithmetic progression a, a + r, a + 2r, . . . , a + r in A. One way to generalize this result is to demand that the difference r is from some prescribed sequence.

Definition 2.1. Let be a positive integer. We say that a set R of positive integers is -recurrent orintersective if any set A of positive upper density contains an + 1 long arithmetic progression a, a + r, a + 2r, . . . , a + r with the difference r ∈ R.

We refer to as the order of intersectivity.

We note that an -intersective set may not be ( + 1)-intersective, see [START_REF] Frantzikinakis | Sets of k-recurrence but not (k + 1)-recurrence[END_REF]. The explanation for the terminology "intersective" is that saying R is -intersective is equivalent with (2.1)

d (A) > 0 implies A ∩ (A -r ) ∩ (A -2r ) ∩ • • • ∩ (A -r ) = for some r ∈ R.
For the term "recurrent", it is known that eq. (2.1) is equivalent with the following: In every dynamical system (X , µ, T )

µ(A) > 0 implies µ A ∩ T -r A ∩ T -2r A ∩ • • • ∩ T -r A > 0 for some r ∈ R.
The direction "recurrent =⇒ intersective" is known as Furstenberg's transfer principle, and it was proved in [Fur77].

It is known that the following sets are -intersective

• the squares {1 2 , 2 2 , 3 2 . . . , n 2 , . . .} or, more generally, the kth powers {1 k , 2 k , 3 k . . . , n k , . . .}. For = 1, this was a conjecture of Lovász, and was answered in [START_REF] Sárközy | On difference sets of sequences of integers[END_REF]Sár78b]. The case of any was proved in [START_REF] Bergelson | Polynomial extensions of van der Waerden's and Szemerédi's theorems[END_REF]. • the "prime minus ones" {2-1, 3-1, 5-1, . . . , p -1, . . .}, or the "prime plus ones" {2+1, 3+1, 5+1, . . . , p + 1, . . .} where p is a prime number. For = 1 this was a question raised by Erdős, and was answered by [Sár78b]. The = 2 case is solved in [START_REF] Frantzikinakis | Multiple recurrence and convergence for sequences related to the prime numbers[END_REF], the case of all other is solved in [START_REF] Wooley | Multiple recurrence and convergence along the primes[END_REF]. • [1 3/2 ], [2 3/2 ], [3 3/2 ], . . . , [n 3/2 ], . . . or, more generally, [1 δ ], [2 δ ], [3 δ ], . . . , [n δ ], . . . for any fixed positive, non-integer δ. For = 1, this probably was first noted in [START_REF] Wierdl | Almost everywhere convergence and recurrence along subsequences in ergodic theory[END_REF], but it's clear that Boshernitzan had been aware of the result. See [Bos83]. It also follows from the general result in [ES78]. For all , it is proved in [START_REF] Frantzikinakis | A Hardy field extension of Szemerédi's theorem[END_REF].

These intersective sequences don't increase faster to infinity than some power of n. In terms of the counting function R(N ) this means that any of the above sets is not very thin since it satisfies R(N ) > N for some positive . Are there any intersective sets which increase to infinity faster than any power of n? The question is not exactly a good one: [ES78] considered sets with dilations. A k-long dilation is a set of integers of the form {d , 2d , 3d , . . . , kd }. Now, if a set contains arbitrarily long dilations, then it is a consequence of Szemerédi's theorem, that the set is -intersective for all . This way, one can make -intersective sequences with arbitrarily thin counting functions. On the other hand, a lacunary sequence cannot contain arbitrarily long dilations and it is shown in [START_REF] Erdős | On differences and sums of integers[END_REF] that a lacunary sequence is not even 1-intersective. Are then the previously mentioned intersective sets exceptional in some sense, or a typical set is also intersective? To be able to talk more conveniently about these questions, we introduce the concept of a random sequence: Definition 2.2. Given a sequence u 1 , u 2 , . . . of probabilities, let U 1 ,U 2 , . . . be a sequence of independent 0-1 valued random variables on a probability space (Ω, P ) so that P (U n = 1) = u n = 1 -P (U n = 0). We think of the sequence U 1 (ω),U 2 (ω), . . . as the indicator of the set R ω defined by

R ω = {n | U n (ω) = 1}.
We say that the random sequence has some given property if there is a set Ω ⊂ Ω with P (Ω ) = 1 so that R ω has the property for all ω ∈ Ω . Note that the concept of a random sequence is always tied to a given sequence of probabilities u 1 , u 2 , . . . . WARNING 2.3. Unless we say otherwise, in this paper we assume that the probabilities u n form a nonincreasing sequence, {u 1 ≥ u 2 ≥ u 3 ≥ . . .}, and that they sum to ∞, n u n = ∞. The standing assumption n u n = ∞ guarantees, by the strong law of large numbers (cf. Theorem A.1 in the Appendix), that the random sequence R is infinite, since its counting function R(N ) = n<N U n is almost surely asymptotically equal to n<N u n . We make the decreasing assumption because intuitively it gives the expected behavior from a random set. Now we can make the concept of a typical set completely precise: it is the random set associated with a given sequence of probabilities u n . It is easy to see that if u n goes to 0 slower than any negative power of n, that is u n • n → ∞ for any > 0, then the random sequence contains arbitrarily long dilations (and intervals!), hence it is -intersective for all . On the other hand, if u n < n -for some positive , then the random sequence doesn't have arbitrarily long dilations. Nevertheless, [ES78] showed that if u n > log n • n -1/3 , then the random sequence is 1-intersective. Can a random sequence be arbitrarily thin but still intersec-

tive? Well, it is shown in [Bos83] that if u n • n → ∞, then the random sequence is still 1-intersective. Paul Balister pointed out to us that if u n = 1 n(log n) 1/2+
, then the random sequence is lacunary and hence is not 1intersective. Anthony Quas told us in private conversation that the method of [START_REF] Bourgain | Ruzsa's problem on sets of recurrence[END_REF] can be used to show that if u n = 1/n, then the random sequence is not 1-intersective.

While quite a lot is known about 1-intersective sets, much less is known about typical 2 or higher order intersective sets. We proved in [FLW12] that if u n = n -b for some some b < 1/2, then the random set is 2-intersective.

For general , we proved in [FLW12] that if

(2.2)

u n = n -b for some 0 < b < 1 2 -1
, then the random set is -intersective. This result was proved independently from us in [Chr11].

The main result on random intersective sets in this current paper is the following improvement of the above results Theorem A (Random -intersectivity theorem). Let be a positive integer, and assume the decreasing sequence u 1 ≥ u 2 ≥ . . . of probabilities satisfy

(2.3) u n • n 1/( +1) → ∞.
Then the random sequence is -intersective.

The condition in eq. (2.3) is better than the condition in eq. (2.2) for ≥ 4. The earlier result that used the condition in eq. (2.2) was obtained by using Van der Corput's inequality -1 times, and this iteration poses the restriction in eq. (2.2). Our method doesn't use iteration, and it doesn't reduce the case for to the case for -1. In particular, we give a new, quite elementary proof when = 1. If = 1, eq. (2.3) gives the restriction b < 1/2, while we know, after Boshernitzan, that every b < 1 works. Our proof doesn't use Fourier analysis or the spectral theorem.

Remark 2.4. We will see that instead of the individual behavior of the u probabilities, as expressed in eq. (2.3), only their average behavior is important. The exact assumption we use in the proof is

(2.4) n<N u n N 1-1/( +1) → ∞.
In other words, only the counting function R(N ) of the random set R matters: by the strong law of large numbers, the above is the same as saying that R(N )/N 1-1/( +1) → ∞.

This indicates that, in fact, the proof applies equally well to a finitary version of Theorem A; see Section 7.1. Now that we are close to the end of this introductory section, we state a conjecture which, if true, would be an extension of Boshernitzan's result for random 1-intersective sets to -intersective ones Conjecture 2.5. Suppose

u n • n → ∞.
Then the random sequence is -intersective.

As we mentioned earlier, if this conjecture is true, it's sharp in the sense that if u n = 1/n, then the random sequence is not 1-intersective.

Convergence of ergodic averages.

In this section (X , µ, T ) denotes a dynamical system. Definition 2.6. Let be a positive integer. We say that the set R = {r 1 < r 2 < r 3 < . . .} of positive integers is -averaging in norm if in any dynamical system the averages 1

N n<N T r n F 1 • T 2r n F 2 • • • T r n F
converge in L 1 norm for any choice of bounded functions F i on X .

While 1-averaging sequences have been studied for a long time, the study of -averaging sequences for > 1 is more recent than that of -intersective sets: That the natural numbers are 2-averaging was proved in [Fur77], the = 3 case was proved in [START_REF] Conze | Théorèmes ergodiques pour des mesures diagonales[END_REF], [HK01], and the breakthrough result of [START_REF] Host | Nonconventional ergodic averages and nilmanifolds[END_REF], where they show that the set of natural numbers is -averaging in norm, came 30 years after Szemerédi's and Furstenberg's result. Now the study of intersective and averaging sequences have been done parallel to each other: The following sets have been found -averaging in norm

• the squares {1 2 , 2 2 , 3 2 , . . . , n 2 , . . .} or, more generally, {p(1), p(2), p(3), . . . , p(n), . . .}, where p(x) is polynomial taking on positive integer values for large enough n. For = 1, this is a folklore result, and follows from Weyl's estimate on trigonometric sums. For all , it was proved in [HK05a] (weak convergence) and in [START_REF] Leibman | Convergence of multiple ergodic averages along polynomials of several variables[END_REF] for norm convergence. • {2, 3, 5, . . . , p, . . .}, where p is a prime number. For = 1 this follows from Vinogradov's classical estimates on the Fourier transform (trigonometric sum) of the sequence of primes. The = 2 case is solved in [START_REF] Frantzikinakis | Multiple recurrence and convergence for sequences related to the prime numbers[END_REF], the case of all other is solved in [START_REF] Wooley | Multiple recurrence and convergence along the primes[END_REF].

• [1 3/2 ], [2 3/2 ], [3 3/2 ], . . . , [n 3/2 ], . . . or, more generally, [1 δ ], [2 δ ], [3 δ ], . . . , [n δ ], .
. . for any fixed positive, non-integer δ. For = 1, this may have been first noted explicitly only in [START_REF] Wierdl | Almost everywhere convergence and recurrence along subsequences in ergodic theory[END_REF], but it's clear that Boshernitzan had been aware of the result. See [Bos83]. For all , the result is proved in [START_REF] Frantzikinakis | Multiple recurrence and convergence for Hardy sequences of polynomial growth[END_REF].

An important difference between intersective and averaging sets is that just because a set contains arbitrarily long dilations, it may not be an averaging set. In particular, it is not easy to construct fast growing averaging sequences. To avoid trivial examples, such as sequences consisting of longer and longer intervals of consecutive integers, we are asking the following: are there any averaging sets {r 1 , r 2 < r 3 < . . .} so that the gaps r n+1r n between consecutive terms goes to infinity faster than any polynomial? It follows from the estimates in [START_REF] Karacuba | Estimates of trigonometric sums by the method of I. M. Vinogradov, and their applications[END_REF] (see also [START_REF] Brüdern | Goldbach numbers in sparse sequences[END_REF]Theorem 2]), that if, for some positive , r n = exp (log n)

u n • n → ∞,
then the random sequence is 1-averaging. As in case of 1-intersective sets, it is known that this result is best possible: [START_REF] Jones | Integer sequences with big gaps and the pointwise ergodic theorem[END_REF] proved that if

u n = 1 n ,
then the random sequence is not 1-averaging. How about 2-averaging random sets? Well, we still don't know of any 2-averaging random set {r 1 , r 2 < r 3 < . . .} which goes to infinity as fast as the squares, that is

when u n = n -1/2 .
For all , we proved in [FLW12] that if

u n = n -b for some 0 < b < 1 2 -1 ,
then the random set is -averaging. This result was also proved independently from us by [Chr11]. Our main result on random -averaging sets in the present paper is the following Theorem B (Random -averaging theorem). Let be a positive integer, and suppose the decreasing sequence

u 1 ≥ u 2 ≥ . . .

of probabilities satisfy

(2.5)

u n • n 1/( +1) → ∞.
Then the random sequence R ω = {r 1 < r 2 < r 3 < . . .} is -averaging in norm, and the limit of the averages 1

N n<N T r n F 1 • T 2r n F 2 • • • T r n F
along the sequence is the same as the limit of the multiple averages 1

N n<N T n F 1 • T 2n F 2 • • • T n F .
Here, again, the real assumption the proof uses is in terms of the average behavior of the the u n , that is, in terms of the counting function of the random sequence: the assumption in eq. (2.5) can be weakened to

n<N u n N 1-1/( +1) → ∞.
We have a conjecture similar to the one for intersective sets Conjecture 2.7. Suppose

u n • n → ∞.
Then the random sequence is -averaging.

In Section 5.3, we examine almost everywhere convergence, and show in Theorem D that a.e. convergence of the difference between the random averages and their expectations follows if we add a mild speed condition to the assumption in eq. (2.5).

Semirandom averages.

Our third main topic is the convergence of double ergodic averages with different rates. Combinatorial applications and norm-convergence are also of interest, but the novelty is the pointwise convergence result, since it's the first result for non-linear sequences. For linear sequences, it was [START_REF] Bourgain | Double recurrence and almost sure convergence[END_REF] who proved that the averages 1 N n<N T n F 1 T 2n F 2 converge a.e. Our main result for "semirandom" averages is Theorem C (Semirandom pointwise averaging theorem). Suppose the decreasing sequence u 1 ≥ u 2 ≥ . . . of probabilities satisfy (2.6)

u n • n 1/2 log 3+δ n → ∞ for some δ > 0,

and

(2.7)

u n → 0.

Then the random sequence R ω = {r 1 < r 2 < r 3 < . . .} satisfies, in every dynamical system (X , µ, T ), for bounded functions F i , that

(2.8) lim N →∞ 1 N n<N T n F 1 (x)T r n F 2 (x) = F 1 F 2 for a.e. x ∈ X ,
where F i is the L 2 projection of F i to the T -invariant functions.

Remark 2.8. It will be clear from the proof that if we weaken the assumption in eq. (2.6) to

u n • n 1/2 → ∞,
we can still conclude mean convergence, and we have recurrence (intersectivity). What we mean by intersectivity in this context is that if the set of positive integers A has positive upper density, then for some n and a, the three numbers a, a + n, a + r n belong to A. In fact, the lower density of such n's is at least d (A)

3 lim inf N →∞ 1 N n<N d (A ∩ (A -n) ∩ (A -r n )) ≥ d (A) 3 .
In [FLW12], we proved eq. (2.8) with the condition u n = n -b for some b < 1/14, so with our theorem, we improve the range of b to b < 1/2. Note that the assumption in eq. (2.7) is equivalent with the random sequence having 0 density. This assumption is necessary to have the limit equal F 1 F 2 . If we drop the assumption that u n → 0, then we don't know if we have convergence-such as in the most basic "coin flipping" case, Unsolved problem 2.9. Suppose u n = 1/2.

Is it true that the random sequence R ω = {r 1 < r 2 < r 3 < . . .} satisfies, in every dynamical system and for bounded functions F i , that the averages 1

N n<N T n F 1 (x)T r n F 2 (x)
converge for a.e. x ∈ X ?

Conjecture 2.10. Suppose the decreasing sequence u 1 ≥ u 2 ≥ . . . of probabilities satisfy u n • n log log n 1+δ → ∞ for some δ > 0, and

u n → 0.
Then the random sequence R ω = {r 1 < r 2 < r 3 < . . .} satisfies, in every dynamical system, for bounded functions F i , that lim

N →∞ 1 N n<N T n F 1 (x)T r n F 2 (x) = F 1 F 2 for a.e. x ∈ X ,
where F i is the projection of the function F i to the T -invariant functions.

If F 1 is T -invariant, then the conjecture is true. See [Bou88]. Even in this case, a speed of a power of log log n is necessary as shown in [START_REF] Jones | Integer sequences with big gaps and the pointwise ergodic theorem[END_REF].

GENERAL IDEAS BEHIND THE PROOFS

Our proof of Theorem A will be presented in an elementary way, but here we explain how the idea of the proof came about because we believe this is a good general context to search for further improvements.

In case of 1-and 2-intersectivity, the main tasks to prove are lim

N →∞ sup A 1 n<N u n n<N (U n -u n ) • d A ∩ (A -n) = 0 with probability 1, and lim N →∞ sup A 1 n<N u n n<N (U n -u n ) • d A ∩ (A -n) ∩ (A -2n) = 0 with probability 1,
respectively, where in sup A we take the supremum over all subsets of the positive integers. For 1-and 2averaging the main tasks are lim

N →∞ sup (X ,T,µ),F X 1 n<N u n n<N (U n -u n )T n F = 0 with probability 1, and lim N →∞ sup (X ,T,µ),F i X 1 n<N u n n<N (U n -u n )T n F 1 • T 2n F 2 = 0 with probability 1,
respectively, where in sup (X ,T,µ),F i we take the supremum over all dynamical systems (X , T, µ) and indicators F i . After a duality consideration, all these cases are proved via estimates of the form

(3.1) P sup (a 1 ,a 2 ,a 3 ,...,a N -1 )∈A 1 n<N u n n<N (U n -u n ) • a n > < exp -c 2 n<N u n ,
where in sup (a 1 ,a 2 ,a 3 ,...,a N -1 )∈A we take the the supremum over a certain class A of vectors (a 1 , a 2 , a 3 , . . . , a N -1 ) of real numbers with |a n | ≤ 1. For example, in case of 2-averaging, we have

a n = X G • T n F 1 • T 2n F 2
and the supremum is taken over all dynamical systems (X , T, µ), indicators F i and ±1-valued functions G.

The inequality in eq. (3.1) for a fixed vector (a 1 , a 2 , a 3 , . . . , a N -1 ) with |a n | ≤ 1 follows from Bernstein's exponential inequality, Lemma 4.1 below, so the difficulty is to handle the supremum. Now, for estimating the supremum of a class of random variables Y k , k ∈ K , the best estimate we have is the union estimate,

P sup k∈K Y k > ≤ |K | • sup k∈K P (Y k > ).
In our case, K would be the class of vectors A = (a 1 , a 2 , a 3 , . . . , a N -1 ). This requires the reduction of the number of vectors (a 1 , a 2 , a 3 , . . . , a N -1 ) in the supremum: we need to be able to find a subclass A 0 of A which has the following properties

A 0 approximates A within : for any (a 1 , a 2 , a 3 , . . . , a N -1 ) ∈ A there is a 1 , a 2 , a 3 , . . . , a N -1 ∈ A 0 so that |a n -a n | < , n = 1, 2, 3, . . . , N .
The cardinality of A 0 is exp o n<N u n : More precisely, for every , we need to have log

(|A 0 |) = O 2 n<N u n .
In other words, the existence of A 0 with the above properties means that the -covering number of A in the ∞ metric needs to be exp O 2 n<N u n . In both the intersective and averaging case, A is uncountably infinite, but via appropriate (and more or less standard) transference arguments, we will show that in both cases A has finite -covering numbers. In case of 1-intersectivity and 1-averaging, the set A contains vectors (a 1 , a 2 , a 3 , . . . , a N -1 ) given by single correlation, that is, by convolution,

a n = 1 Q a<Q g (a) f (a + n),
where Q < N , and f and g are two-valued functions defined on the interval [0, 2N ]. In this case, Parseval's formula easily yields that the -covering number is

O(N ) = exp O log N which implies that n<N u n only needs to satisfy (3.2) n<N u n log N → ∞.
But in case of 2-intersectivity and 2-averaging, the structure of a n is more complicated: the set A contains vectors (a 1 , a 2 , a 3 , . . . , a N -1 ) given by order 2-correlation

a n = 1 Q a<Q g (a) f 1 (a + n) f 2 (a + 2n).
The novelty of our paper is that even in this case we manage to show that the -covering number is better than the trivial exp O(N ) estimate: we show that for order correlation sequences, the -covering number is exp O N 1-1/( +1 , which yields the condition

(3.3) n<N u n N 1-1/( +1) → ∞,
appearing in both Theorems A and B. We achieve this by restricting the functions f i and g to thin, independent subsets each of a certain appropriate density. The independence of these support sets results in restricting the order correlation sequences to the product of these densities. The fact that we have + 1 factors in an order correlation sequence explains the appearance of + 1 in the condition eq. (3.3). The origin of the idea of thinning via independent sets is coming from [CG10]. We later noticed that instead of using independent random variables, we can simply use independent residue classes and the Chinese remainder theorem, and this less sophisticated method yields more accurate results. We do believe, though, that even for order > 1 correlation sequences, the -covering numbers are not greater than some power of N . Hence the -covering number is always exp O log N , which would give the condition eq. (3.2). This belief is behind Conjectures 2.5 and 2.7. We close this section by stating that finding optimal -covering numbers is behind many convergence theorems. The general techniques of maximal inequalities, convexity methods (cf. Section 7.3), Fourier transform, spectral theorem, uniform boundedness and transference principles can be viewed as tools to help us reduce the original class of functions for which we need to check convergence.

PROOF OF THEOREM A, THE RANDOM INTERSECTIVITY THEOREM

The proof is completely elementary, and, unlike earlier methods, the = 2 case contains all the ingredients of the proof. Hence, we give the detailed proof for = 2, and only indicate the minor adjustments to be made for ≥ 3. 4.1. The = 2 case. As we indicated, we shall work with the weaker assumption in eq. (2.4) which in this case is (4.1)

n<N u n N 2/3 → ∞,
and we shall prove a little more than required: we shall prove that the set of differences r ∈ R ω for which

d A ∩ (A -r ) ∩ (A -2r ) > 0 is of positive lower density in R ω , (4.2) lim inf N →∞ 1 n<N U n n<N U n • d A ∩ (A -n) ∩ (A -2n) > 0.
By the strong law of large numbers, Theorem 6.1,

1 n<N u n n<N U n → 1 with probability 1, so eq. (4.2) is equivalent with lim inf N →∞ 1 n<N u n n<N U n • d A ∩ (A -n) ∩ (A -2n) > 0.
Let us consider the expectation of the averages

1 n<N u n n<N U n • d A ∩ (A -n) ∩ (A -2n) , 1 n<N u n n<N u n • d A ∩ (A -n) ∩ (A -2n) .
Using that the sequence (u n ) is decreasing1 , summation by parts gives the estimate lim inf

N →∞ 1 n<N u n n<N u n • d A ∩ (A -n) ∩ (A -2n) ≥ lim inf N 1 N n<N d A ∩ (A -n) ∩ (A -2n) .
Now, Szemerédi's (actually, in this = 2 case, Roth's) result has been strengthened by [Fur77] to the extent that for any A (of positive upper density) the lower density of the differences of three term arithmetic progressions in A is positive

(4.3) lim inf N →∞ 1 N n<N d A ∩ (A -n) ∩ (A -2n) > 0.
In fact, we need a more precise version of this result: Examining Furstenber's transfer principle in [Fur77], it is clear that for a fixed A of positive upper density, there is a single sequence M 1 , M 2 , . . . , M k , . . . so that for every n the limit

ρ A ∩ (A -n) ∩ (A -2n) = lim k→∞ a | a ∈ A ∩ (A -n) ∩ (A -2n), a < M k M k
exists and satisfies

(4.4) lim inf N →∞ 1 N n<N ρ A ∩ (A -n) ∩ (A -2n) > 0.
Those who seek a more elementary reason for this can use the method of [Var59] to establish eq. (4.4) and hence eq. (4.3). It is then enough to prove that the difference between the averages along the random sequence and the expectation of the averages goes to 0 (4.5) lim

N →∞ sup A 1 n<N u n n<N (U n -u n ) • ρ A ∩ (A -n) ∩ (A -2n) = 0 with probability 1,
where in sup A we take the supremum over all subsets of the positive integers. By the assumption in eq. (4.1), we can choose a sequence 1 , 2 , . . . , N , . . . of positive numbers so that

(4.6) N → 0 and 2 N n<N u n N 2/3
> C , with some constant C > 0 to be chosen later, for all N > N (C ).

We will show that, for each N > N (C ), the N th average is greater than N with small probability (4.7)

P sup A 1 n<N u n n<N (U n -u n ) • ρ A ∩ (A -n) ∩ (A -2n) > N < exp -c 2 N n<N u n .
This implies eq. (4.5) since, by the choice of N in eq. (4.6), we have exp -c 2

N n<N u n < exp -C c N 2/3
which is summable in N , hence we can apply the Borel-Cantelli lemma. Now, the difficulty in proving eq. (4.7) is the requirement that we need to have the estimate of the average simultaneously for all A. Indeed, the estimate for a fixed set A instead of sup A follows readily from Bernstein's exponential inequality, [Pet75, page 52], Lemma 4.1 (Bernstein's exponential inequality). Let X 1 , X 2 , . . . , X N be independent, mean zero random variables with |X n | ≤ K .

Then

(U n -u n ) • a n > < exp - 1 4 2 n<N u n . Proof of Corollary 4.2. Set X n = (U n -u n ) • a n . Then |X n | ≤ 1 and EX 2 n ≤ E(U n -u n ) 2 ≤ u n .
Now use Lemma 4.1 with this X n and t = • n<N u n .

Using this corollary with a n = ρ A ∩ (An) ∩ (A -2n) and = N , we readily get

P 1 n<N u n n<N (U n -u n ) • ρ A ∩ (A -n) ∩ (A -2n) > N < exp - 1 4 2 N n<N u n .
How can we get almost the same estimate when, instead a fixed A, we take sup A ? The best general estimate we have for the supremum of a class of random variables

Y k , k ∈ K , is what is known as the union estimate (4.8) P sup k∈K Y k > ≤ |K | • sup k∈K P (Y k > ).
In view of the above, since in our case we would take K to be a set of A's, our task is to reduce the number of sets A we need to consider in sup A . Our first step is to show that we can take finitely many A. In calculating

ρ A ∩ (A -n) ∩ (A -2n) , we are taking the limit of 1 M k a | a ∈ A ∩ (A -n) ∩ (A -2n), a < M k as k → ∞. Our
formulas become simpler if we use the indicator 1 A of A. We can then write 1

M k a | a ∈ A ∩ (A -n) ∩ (A -2n), a < M k = 1 M k a<M k 1 A (a)1 A (a + n)1 A (a + 2n).
Let us divide up the interval [1, M k ) of summation into intervals of length Q, where we'll see that the best choice for the positive integer Q will be a constant multiple of N 2/3 , 1

M k a<M k 1 A (a)1 A (a + n)1 A (a + 2n) = 1 M k /Q i <M k /Q 1 Q iQ≤a<(i +1)Q 1 A (a)1 A (a + n)1 A (a + 2n) + O Q/M k . It follows, since M k → ∞ hence the error term O Q/M k goes to 0, that 1 n<N u n n<N (U n -u n ) • ρ A ∩ (A + n) ∩ (A + 2n) ≤ sup j 1 n<N u n n<N (U n -u n ) • 1 Q jQ≤a<( j +1)Q 1 A (a)1 A (a + n)1 A (a + 2n) .
Now, instead of taking the supremum sup j over varying intervals of length Q, we can take the fixed interval [0,Q), and take the supremum over indicators over the intervals [0,Q), [0,Q + N ) and [0,Q + 2N ). For this, simply change variable b = a -jQ, and define

f 0 (b) = 1 A ( jQ + b)1 [0,Q) (b), f 1 (b) = 1 A ( jQ + b)1 [0,Q+N ) (b), f 2 (b) = 1 A ( jQ + b)1 [0,Q+2N ) (b). It follows that sup j 1 n<N u n n<N (U n -u n ) • 1 Q jQ≤a<( j +1)Q 1 A (a)1 A (a + n)1 A (a + 2n) ≤ sup f i ∈F i 1 n<N u n n<N (U n -u n ) • 1 Q b<Q f 0 (b) f 1 (b + n) f 2 (b + 2n) ,
where

F i = F i (N ) is the family of indicators supported on the interval [0,Q + i N ) for i = 0, 1, 2, F i = f i | f i : [0,Q + i N ) → {0, 1} , i = 0, 1, 2.
We've reduced the inequality in eq. (4.7) to (4.9) P sup

f i ∈F i 1 n<N u n n<N (U n -u n ) • 1 Q a<Q f 0 (a) f 1 (a + n) f 2 (a + 2n) > N < exp -c 2 N n<N u n .
The important thing is that in sup f i ∈F i , i = 0, 1, 2, we take the supremum over finite sets. The cardinality of F 0 is 2 Q and at this point it is still at our disposal, so it is of no concern right now except we note that Q < N . But we do have a problem with the cardinalities of

F i , i = 1, 2: their cardinalities is at least 2 N = exp (c N ). Applying Corollary 4.2 with a n = 1 Q a<Q f 0 (a) f 1 (a + n) f 2 (a + 2n
), and using the union estimate eq. (4.8), we only get

P sup f i ∈F i 1 n<N u n n<N (U n -u n ) • 1 Q a<Q f 0 (a) f 1 (a + n) f 2 (a + 2n) > N ≤ exp (c N ) • exp - 1 4 2 N n<N
u n , which is not good enough since the best estimate we have is 2

N n<N u n > C N 2/3 .
To reduce the cardinality of the f 1 , f 2 further, we restrict their support, the [0,Q + N ) and [0,Q +2N ) intervals, to "independent" arithmetic progressions. We choose 2 moduli q 1 , q 2 , and we split the support of f i , the interval [0,Q+i N ), according to the residue classes (mod q i ). This results in splitting the supports of the products f 1 (a +n) f 2 (a +2n) into q 1 q 2 residue classes: Let χ i be the indicator of the multiples of q i

χ i (x) = 1 if q i | x, 0 otherwise.
Since χ i (xr ) is the indicator of the r (mod q i ) residue class, we can write (4.10) 1

Q a<Q f 0 (a) f 1 (a + n) f 2 (a + 2n) = 1 Q a<Q f 0 (a) r 1 <q 1 χ 1 (a + n -r 1 ) f 1 (a + n) r 2 <q 2 χ 2 (a + 2n -r 2 ) f 2 (a + 2n) = 1 Q r 1 <q 1 r 2 <q 2 a<Q f 0 (a)χ 1 (a + n -r 1 ) f 1 (a + n)χ 2 (a + 2n -r 2 ) f 2 (a + 2n).
We want the q i to be as big as possible, but we don't want the number of terms q 1 q 2 in the sum r 1 <q 1 r 2 <q 2 to be greater than Q, so we require (4.11) q 1 q 2 ≤ Q.

We also need to make sure a<Q f 0 (a)χ 1 (a+n-r 1 ) f 1 (a+n)χ 2 (a+2n-r 2 ) f 2 (a+2n) is bounded independently of n for fixed r i . We can achieve this if the equation (4.12) χ 1 (a + nr 1 )χ 2 (a + 2nr 2 ) = 1 has, say, at most 1 solution in a ∈ [0,Q). We can rewrite eq. (4.12) as simultaneous congruences a ≡ r 1n (mod q 1 ), a ≡ r 2 -2n (mod q 2 ). Now, if the q i are coprimes, then the above system of congruences has a single solution (mod q 1 q 2 ) by the Chinese remainder theorem. It follows that eq. (4.12) has at most 1 solution in a ∈ [0,Q) if

Q ≤ q 1 q 2 .
Comparing this with eq. (4.11), we commit to

Q = q 1 q 2 .
We then have

1 n<N u n n<N (U n -u n ) • 1 Q a<Q f 0 (a) f 1 (a + n) f 2 (a + 2n)
by eq. (4.10) and since

Q = q 1 q 2 = 1 Q r 1 <q 1 r 2 <q 2 1 n<N u n n<N (U n -u n ) • a<Q f 0 (a)χ 1 (a + n -r 1 ) f 1 (a + n)χ 2 (a + 2n -r 2 ) f 2 (a + 2n) ≤ sup r i <q i 1 n<N u n n<N (U n -u n ) • a<Q f 0 (a)χ 1 (a + n -r 1 ) f 1 (a + n)χ 2 (a + 2n -r 2 ) f 2 (a + 2n) .
It follows, using the union estimate eq. (4.8), P sup

f i ∈F i 1 n<N u n n<N (U n -u n ) • a<Q f 0 (a) f 1 (a + n) f 2 (a + 2n) > N ≤ q 1 q 2 sup r i <q i P sup f i ∈F i 1 n<N u n n<N (U n -u n ) • a<Q f 0 (a)χ 1 (a + n -r 1 ) f 1 (a + n)χ 2 (a + 2n -r 2 ) f 2 (a + 2n) > N .
The contribution of q 1 q 2 = Q < N = exp log N is insignificant to the order of exp -2

N n<N u n = exp -O(N 2/3 )
which we aim to achieve in eq. (4.9), so we ignore it in further considerations. For given r i , i = 1, 2, the function g i defined by g i (x) = χ(xr i ) f i (x) is supported on the part of the residue class r i (mod q i ) that falls into the interval [0,Q +i N ). Denote by G i those functions from F i which are supported on the residue class r i (mod q i )

G i = g i | g i : [0,Q + i N ) → {0, 1}, g i (x) = 0 =⇒ x ≡ r i (mod q i ) .
Since the cardinality of the residue class r i (mod q i ) that falls into the interval [0,Q + i N ) is not more than (Q + i N )/q i < 3N /q i , we have (4.13)

|G i | ≤ 2 2N /q i , i = 1, 2.
Our remaining task is to estimate, using the convenient notation G 0 = F 0 , P sup

g i ∈G i 1 n<N u n n<N (U n -u n ) • a<Q g 0 (a)g 1 (a + n)g 2 (a + 2n) > N .
In the above, a<Q g 0 (a)g 1 (a + n)g 2 (a + 2n) is bounded by 1 for each n. This is because q 1 q 2 = Q, q 1 and q 2 are coprimes, hence, by the Chinese remainder theorem, there is one a < Q for which a +n ≡ r 1 (mod q 1 ) and a + 2n ≡ r 2 (mod q 2 ). Clearly

|G 0 | = 2 Q ,
hence, using eq. (4.13),

|G 0 × G 1 × G 2 | ≤ 2 Q+2N /q 1 +2N /q 2 .
We can now estimate, using the union estimate eq. (4.8) and Corollary 4.2 with a n = a<Q g 0 (a)g 1 (a + n)g 2 (a + 2n), as (4.14) P sup

g i ∈G i 1 n<N u n n<N (U n -u n ) • a<Q g 0 (a)g 1 (a + n)g 2 (a + 2n) > N ≤ 2 Q+2N /q 1 +2N /q 2 • exp - 1 4 2 N n<N u n ≤ exp (Q + 2N /q 1 + 2N /q 2 ) - 1 4 2 N n<N u n ,
where we used that log 2 < 1. In order to have a nontrivial estimate, we need to have something like (4.15)

Q + 2N q 1 + 2N q 2 ≤ 1 5 • 2 N n<N u n .
Treating the left hand side as if q i and Q were real variables, since Q = q 1 q 2 , the left hand side has a minimum at Q = c N 2/3 , and q 1 = q 2 = cN 1/3 . We certainly can choose coprime integers q i which nearly satisfy these requirements. With these choices eq. (4.15) becomes

cN 2/3 ≤ 1 5 • 2 N n<N u n .
We certainly can achieve this by taking C large enough in eq. (4.6). With these choices of C ,Q, q i , the estimate in eq. (4.14) becomes P sup

g i ∈G i 1 n<N u n n<N (U n -u n ) • a<Q g 0 (a)g 1 (a + n)g 2 (a + 2n) > N ≤ exp -c N 2/3 ,
finishing our proof.

The general case.

There are only three remarks we need to make here, and then the proof goes through verbatim.

The first remark is that in [Fur77] eq. (3.2) is proved for all :

lim inf N →∞ 1 N n<N d A ∩ (A -n) ∩ • • • ∩ (A -( -1)n) ∩ (A -n) > 0.
For an elementary proof: N. Hegyvári pointed out to us that the method of [Var59] can be used for the same conclusion 2 . The slightly strengthened version we really need, and which we described in eq. (4.4), is also valid.

Second, this time we need to choose the ( N ) so that N → 0 and 2 N n<N u n N 1-1/( +1) > C , with some constant C > 0 to be chosen later, for all N > N (C ). For the third remark, let us look at the essential inequality we really need to prove: with a Q < N to be chosen later, we need to prove the following analog of eq. (4.9) P sup

f i ∈F i 1 n<N u n n<N (U n -u n ) • 1 Q a<Q f 0 (a) f 1 (a + n) . . . f -1 (a + ( -1)n) f (a + n) > N < exp -c 2 N n<N u n ,
where

F i = f i | f i : [0,Q + i N ) → {0, 1} , i = 0, 1, 2, . . . , .
This time, we need to slim down the supports of functions f 1 , f 2 , . . . , f . Correspondingly, we choose pairwise coprime moduli q 1 , q 2 , . . . , q to split the support of f i , the interval [0,Q + i N ), according to the residue classes (mod q i ). Proceeding as in the case = 2, we get the requirements (4.16) q 1 q 2 . . . q = Q, and (4.17)

N q 1 + N q 2 + • • • + N q +Q ≤ 1 5 2 N n<N u n .
If the q i and Q were real variables, the left hand side would be minimized when

Q = c N /( +1) ,
and the q i were equal to each other. By eq. (4.16) this means (4.18)

q i = Q 1/ = c N 1/( +1) .
2 In [Var59], only the = 2 case is treated, but the method works for any . For a proof for any , see Theorem 8 in http: //terrytao.wordpress.com/2008/08/30/the-correspondence-principle-and-finitary-ergodic-theory/.

With these values, eq. (4.17) becomes, with some c depending on only,

(4.19) cN 1-1/( +1) < 2 N n<N u n ,
which suggested the assumption in eq. (2.4). The only question remains if we can choose pairwise coprime q i 's near the optimal value N 1/( +1) of eq. (4.18)? To do this, choose each q i to be a prime number with N 1/( +1) < q i < 2N 1/( +1) . This is possible for large enough N by the prime number theorem. The much simpler Chebyshev estimate 1 2 t / log t < π(t ) < 2t / log t is also enough, but then the primes would satisfy N 1/( +1) < q i < 5N 1/( +1) .

PROOF OF THEOREM B, THE RANDOM AVERAGING THEOREM

Similarly to the proof of Theorem A, we just explain the idea of the proof for = 2. Since the proof is very similar to the proof of Theorem A, we just point out the differences between the arguments. 5.1. The = 2 case. We want to show that with probability 1 in any dynamical system (5.1)

1 n<N U n n<N U n • T n F 1 • T 2n F 2 converge in L 1 norm.
Approximating F i in L 1 norm by linear combinations of indicator functions, we see it's enough to show convergence for indicators F i of measurable subsets of X . By the strong law of large numbers, Theorem A.1, we have n<N U n n<N u n → 1 with probability 1, hence eq. (5.1) is equivalent to

1 n<N u n n<N U n • T n F 1 • T 2n F 2 converge in L 1 norm.
The expectation of the averages

1 n<N u n n<N U n • T n F 1 • T 2n F 2 is (5.2) 1 n<N u n n<N u n • T n F 1 • T 2n F 2 .
Summation by parts shows that the averages in eq. (5.2) converge to the same limit as the double ergodic averages 1

N n<N T n F 1 • T 2n F 2 .
That these double averages converge in norm was proved by [Fur77], so it is enough to prove that the differences between the random averages and their expectations go to 0 in L 1 norm lim

N →∞ sup (X ,T,µ),F i X 1 n<N u n n<N (U n -u n ) • T n F 1 • T 2n F 2 = 0 with probability 1,
where in sup (X ,T,µ),F i we take the supremum over all dynamical systems (X , T, µ) and indicators F i , 1 = 1, 2.

We first reduce all to a single dynamical system using an appropriate version of the transference principle of A. Calderón. Since T is measure preserving, we have, for every integer a

X 1 n<N u n n<N (U n -u n ) • T n F 1 • T 2n F 2 = X 1 n<N u n n<N (U n -u n ) • T a+n F 1 T a+2n F 2 .
Average this in a over the interval [0,Q), where Q is the same as in the proof of Theorem A in the = 2 case, so its best choice will be Q ∼ N 2/3 . We get

X 1 n<N u n n<N (U n -u n ) • T n F 1 • T 2n F 2 = X 1 Q a<Q 1 n<N u n n<N (U n -u n ) • T a+n F 1 T a+2n F 2 . It follows that (5.3) sup F i X 1 n<N u n n<N (U n -u n ) • T n F 1 • T 2n F 2 ≤ X sup F i 1 Q a<Q 1 n<N u n n<N (U n -u n ) • T a+n F 1 T a+2n F 2 . Define the N → {0, 1} indicators f 1 , f 2 by f 1 (a) = f 1 (x, a) = T a F 1 (x)1 [0,Q+N ) (a), f 2 (a) = f 2 (x, a) = T a F 2 (x)1 [0,Q+2N ) (a).
Then for the values of a and n considered above we have T a+n F 1 (x) = f 1 (a +n) and T a+2n F 1 (x) = f 2 (a +2n).

Denote by F i the family of indicators supported on the interval [0,Q + i N )

F i = f i | f i : [0,Q + i N ) → {0, 1} .
We then have the pointwise estimate sup

F i 1 Q a<Q 1 n<N u n n<N (U n -u n ) • T a+n F 1 (x)T a+2n F 2 (x) ≤ sup f i ∈F i 1 Q a<Q 1 n<N u n n<N (U n -u n ) • f 1 (a + n) f 2 (a + 2n) .
Integrating this over the probability space X , and using eq. ( 5.3), we get

(5.4) sup (X ,T,µ) sup F i X 1 n<N u n n<N (U n -u n ) • T n F 1 T 2n F 2 ≤ X sup f i ∈F i 1 Q a<Q 1 n<N u n n<N (U n -u n ) • f 1 (a + n) f 2 (a + 2n) = sup f i ∈F i 1 Q a<Q 1 n<N u n n<N (U n -u n ) • f 1 (a + n) f 2 (a + 2n)
The important thing to notice is that the final estimate of eq. (5.4) doesn't depend on the dynamical system (X , T, µ) anymore and, furthermore, in sup f i ∈F i we take the supremum over finitely many functions f i , i = 1, 2. Our remaining task is to show that (5.5) lim

N →∞ sup f i ∈F i 1 Q a<Q 1 n<N u n n<N (U n -u n ) • f 1 (a + n) f 2 (a + 2n) = 0 with probability 1.
Let us write the above average in dual form: Let G = G (N ) be the family of ±1-valued functions supported on the interval [0,Q)

G = g | g : [0,Q) → {-1, 1} .
We then have (5.6)

sup f i ∈F i 1 Q a<Q 1 n<N u n n<N (U n -u n ) • f 1 (a + n) f 2 (a + 2n) = sup f i ∈F i ,g ∈G 1 Q a<Q 1 n<N u n n<N (U n -u n ) • g (a) f 1 (a + n) f 2 (a + 2n) = sup f i ∈F i ,g ∈G 1 n<N u n n<N (U n -u n ) 1 Q a<Q g (a) f 1 (a + n) f 2 (a + 2n).
The only difference between the right hand side of eq. (5.6) above and

(5.7) sup

f i ∈F i 1 n<N u n n<N (U n -u n ) 1 Q a<Q f 0 (a) f 1 (a + n) f 2 (a + 2n)
of eq. (4.9) is that G contains ±1-valued functions while the F 0 of eq. (5.7) contains indicators. But this difference doesn't change anything in the proof, since the only thing we use about the functions in G is that they take on two values. So the method used to establish eq. (4.9) works equally well to prove, for all large enough N , (5.8) P sup

f i ∈F 〉 ,g ∈G 1 n<N u n n<N (U n -u n ) 1 Q a<Q g (a) f 1 (a + n) f 2 (a + 2n) > N < exp -c 2 N n<N u n ,
where N is chosen to satisfy eq. (4.6). But this choice of N implies that the right hand side of eq. (5.8) is summable and hence, by the Borel-Cantelli lemma, we have eq. (5.5).

The general case.

Our remarks are similar to the three remarks we made in Section 4.2. The only difference is in the first remark: While in the = 2 case, we invoked Furstenberg's double convergence theorem, this time we need to refer to the "multiple mean ergodic theorem" of [START_REF] Host | Nonconventional ergodic averages and nilmanifolds[END_REF] (cf [START_REF] Ziegler | Universal characteristic factors and Furstenberg averages[END_REF] for another proof). The multiple mean ergodic theorem says that the set of positive integers is -averaging, that is the averages 1

N n<N T n F 1 • T 2n F 2 • • • T n F
converge in L 1 norm for bounded F i . Then the proof proceeds to show that the averages along the random sequence converge to the same limit as the multiple averages above.

Pointwise convergence.

The main philosophy on pointwise convergence for any averages (not just those in our paper) is that if mean convergence takes place with an appropriate speed, then we also have pointwise convergence. It is enough to prescribe the speed for a subsequence of the averages (5.9)

1 n<N U n n<N (U n -u n )T n F 1 (x) • T 2n F 2 (x) • • • T n F (x).
What is the sparsest subsequence of the averages the convergence of which implies the convergence of all the averages? Actually, we are going to consider a class of subsequences: for σ > 1, let {N 1 < N 2 < N 3 < . . .} be such that

n<N i u n ≈ σ i .
Roughly speaking, for each σ > 1, the N i defined above is a sequence along which the averages could still change significantly, but as σ gets closer and closer to 1, this change is as small as we want. To understand why, consider the simplest random average relevant to our problem

1 n<N u n n<N U n .
The N i th sum n<N i U n has an expected mass of n<N i u n ≈ σ i and the N i +1 st sum n<N i +1 U n has an expected mass of n<N i +1 u n ≈ σ i +1 . Hence the difference N i ≤n<N i +1 U n has an expected mass of N i ≤n<N i +1 u n ≈ σ i +1 -σ i . What is the proportion of this increase in mass to σ i , the expected mass of the N i th average? It is (σ i +1 -σ i )/σ i = σ-1. This means, the proportion of this difference is a fixed positive number (independent of i ), so if changes happen in this difference, it may affect averages that are between the N i th and N i +1 st average. On the other hand, the proportion σ -1 of this difference goes to 0 as σ gets closer to 1. We then expect that if the N i th average and the N i +1 st averages are both close to 1, and if N is between N i and N i +1 , then the N th average will also be close to 1, and the difference will not be much more than σ -1.

Let us now carry out this argument for our averages precisely. Our random average in eq. (5.9) is of the form 1

n<N U n n<N (U n -u n )G n
for some uniformly bounded sequence of functions G 1 ,G 2 ,G 3 , . . . . We can assume G n ∞ ≤ 1. By the strong law of large numbers, Theorem A.1, with probability 1, we can divide by the expectation n<N u n instead of

n<N U n 1 n<N u n n<N (U n -u n )G n .
For σ > 1, we choose the subsequence

I σ = {N 1 < N 2 < N 3 < . . .} so that n<N i u n ≈ σ i , n<N i u n ≥ σ i but n<N u n < σ i for N < N i .
In words: N i is the smallest index N for which n<N u n ≥ σ i . That I σ is well defined and infinite follows from the dissipative assumption n u n = ∞. Clearly (5.10) 1) for all i = 1, 2, 3, . . . .

n<N i u n = σ i + O(
Note that we also have that n<N i U n ≈ σ i . More precisely, we have, by the strong law of large numbers, Theorem A.1, and by eq. (5.10),

n<N i U n = σ i + o σ i with probability 1.
Let us see how convergence along the subsequences I σ 's, σ > 1, imply convergence along the full sequence N = 1, 2, 3, . . . . Assume that for each fixed σ > 1, there is Ω σ with P (Ω σ ) = 1 so that (5.11) lim

i →∞

1 n<N i u n n<N i (U n (ω) -u n )G n (x)
= 0 for ω ∈ Ω σ and for a.e. x ∈ X .

We want to show that then for each fixed σ > 1, there is Ω σ with P (Ω σ ) = 1 so that (5.12) lim sup

N →∞ 1 n<N u n n<N (U n (ω) -u n )G n (x) ≤ 4(σ -1)
for ω ∈ Ω σ and for a.e. x ∈ X .

It's important to emphasize that the construction of the set Ω σ is independent of x ∈ X , and that the only property of the sequence G 1 (x),G 2 (x), . . . ,G n (x), . . . we use is that it's bounded by 1. For this reason, we suppress the argument x in G n (x). Now, if we choose a sequence of σ's which go to 1, then the intersection Ω of the corresponding sets Ω σ for which eq. (5.12) holds will give convergence to 0, lim

N →∞ 1 n<N u n n<N (U n (ω) -u n )G n = 0 for ω ∈ Ω .
So fix σ > 1. By the assumption in eq. (5.11), eq. (5.12) follows if we show that there is Ω σ with P (Ω σ ) = 1 so that (5.13)

lim sup i →∞ max N i ≤N <N i +1 1 n<N u n n<N (U n (ω) -u n )G n - 1 n<N i u n n<N i (U n (ω) -u n )G n ≤ 4(σ -1) for ω ∈ Ω σ .
For a given N , choose the i so that

N i ≤ N < N i +1 .
To estimate the difference between the N th and N i th average, denote

H n = (U n (ω) -u n )G n ,
and write 1

n<N u n n<N H n - 1 n<N i u n n<N i H n = 1 n<N u n n<N H n - 1 n<N u n n<N i H n + 1 n<N u n n<N i H n - 1 n<N i u n n<N i H n = 1 n<N u n N i ≤n<N H n + n<N i H n 1 n<N u n - 1 n<N i u n . (5.14)
To estimate the two terms in eq. (5.14), we need the following consequence of the strong law of large numbers, Theorem A.1, (5.15) lim i →∞

N i ≤n<N i +1 U n (ω) N i ≤n<N i +1 u n = 1 with probability 1.
To see eq. (5.15), write as

N i ≤n<N i +1 U n (ω) N i ≤n<N i +1 u n = 1 N i ≤n<N i +1 u n n<N i +1 U n (ω) - n<N i U n (ω) .
Writing 1

N i ≤n<N i +1 u n n<N i +1 U n (ω) = n<N i +1 u n N i ≤n<N i +1 u n • 1 n<N i +1 u n n<N i +1 U n (ω),
we see that by the strong law of large numbers, we have, with probability 1,

lim i →∞ 1 N i ≤n<N i +1 u n n<N i +1 U n (ω) = lim i →∞ n<N i +1 u n N i ≤n<N i +1 u n using eq. (5.10) = lim i →∞ σ i +1 + O(1) σ i +1 -σ i + O(1) = σ σ -1 . (5.16) Similarly lim i →∞ 1 N i ≤n<N i +1 u n n<N i U n (ω) = lim i →∞ n<N i u n N i ≤n<N i +1 u n = 1 σ -1 . (5.17)
Now take the difference of eqs. (5.16) and (5.17) to get our claim in eq. (5.15).

Let's go back to our main task of estimating the two terms in eq. (5.14). Estimate as

1 n<N u n N i ≤n<N H n ≤ 1 n<N i u n N i ≤n<N i +1 |H n | ≤ 1 n<N i u n N i ≤n<N i +1 (U n (ω) + u n ) = N i ≤n<N i +1 u n n<N i u n • 1 N i ≤n<N i +1 u n N i ≤n<N i +1 (U n (ω) + u n ).
Take "lim sup i →∞ max N i ≤N <N i +1 " of both ends, to get

lim sup i →∞ max N i ≤N <N i +1 1 n<N u n N i ≤n<N H n ≤ lim sup i →∞ N i ≤n<N i +1 u n n<N i u n • 1 N i ≤n<N i +1 u n N i ≤n<N i +1 (U n (ω) + u n ) using eq. (5.15) = 2 • lim i →∞ N i ≤n<N i +1 u n n<N i u n using eq. (5.10) = 2 • lim i →∞ σ i +1 -σ i + O(1)
σ i + O(1) = 2(σ -1). (5.18) Similarly (5.19) lim sup i →∞ max N i ≤N <N i +1 n<N i H n 1 n<N u n - 1 n<N i u n ≤ 2(σ -1).
The estimates in eqs. (5.18) and (5.19) imply eq. (5.13).

The consequence of this lacunary subsequence trick is that for the averages in eq. (5.9), it is enough to prove, for all σ > 1, almost sure convergence along the subsequence I σ . This is accomplished if we ensure that the sequence { 1 , 2 , . . . , n , . . .} satisfies (5.20)

N ∈I σ N < ∞ for all σ > 1
in addition to the requirement in eq. (4.19). To see this implication of the condition in eq. (5.20), note first that by the Borel-Cantelli lemma we have, for almost every ω,

sup (X ,T,µ),F i X 1 n<N u n n<N (U n (ω) -u n ) • T n F 1 (x) • T 2n F 2 (x) • • • T n F (x) ≤ N for N ≥ N (ω).
By eq. (5.20), we have, for almost every ω,

sup (X ,T,µ),F i X N ∈I σ 1 n<N u n n<N (U n (ω) -u n ) • T n F 1 (x) • T 2n F 2 (x) • • • T n F (x) ≤ N ∈I σ sup (X ,T,µ),F i X 1 n<N u n n<N (U n (ω) -u n ) • T n F 1 (x) • T 2n F 2 (x) • • • T n F (x) < ∞.
This implies that the series N ∈I σ

1 n<N u n n<N (U n (ω) -u n ) • T n F 1 (x) • T 2n F 2 (x) • • • T n F (x) is convergent
for almost every x, and hence

1 n<N u n n<N (U n (ω)-u n )•T n F 1 (x)•T 2n F 2 (x) • • • T n F (x) → 0 for almost every x as N ∈ I σ goes to ∞.
To ensure eq. (5.20), note that in our case, since we at least assume n<N u n N 1-1/( +1) → ∞, the subsequence I σ does not increase faster to ∞ than a geometric progression. So a near optimal choice for N to ensure eq. (5.20) is N = log -(1+δ) N for some fixed positive δ.

Putting all this together, we get the following theorem for the case when the F i are indicator functions Theorem D (Random pointwise -averaging theorem). Let be a positive integer and suppose that for some positive δ we have

(5.21)

u n • n 1/( +1) log 2+δ n → ∞.
Then, with probability 1, in any dynamical system (X , T ),

(5.22) lim

N →∞ 1 n<N U n (ω) n<N (U n (ω) -u n ) • T n F 1 (x) • T 2n F 2 (x) • • • T n F (x) = 0 for a.e. x ∈ X ,
for bounded functions F i .

The main utility of this theorem is that once we have almost everywhere convergence for the multiple averages

(5.23) 1

N n<N T n F 1 (x) • T 2n F 2 (x) • • • T n F (x), then the averages 1 n<N U n n<N U n • T n F 1 (x) • T 2n F 2 (x) • • • T n F (x)
along the random sequence also converge and to the same limit for almost every x. So far, the a.e. convergence of eq. (5.23) in every dynamical system is known only in case = 1, 2. For = 1, this is the pointwise ergodic theorem, for = 2 it was proved by [START_REF] Bourgain | Double recurrence and almost sure convergence[END_REF]. Moreover, the pointwise convergence of the averages in eq. (5.23) for any is known in a great variety of particular dynamical systems such as in

• discrete spectrum or quasi-discrete spectrum dynamical systems;

• K-systems (cf. [DL96]);

• a large class of skew-product extensions of ergodic compact group translations (cf. [Les93]);

• a lot of dynamical systems with a compact topological structure where everywhere convergence can be proved for continuous functions, hence the general pointwise ergodic theorem follows by a maximal inequality. An example for this that we haven't mentioned is a horocycle flow on a compact surface with negative curvature, or, more generally, unipotent transformations (Ratner's theory).

So far, we showed how to prove Theorem D for indicator functions. The extension to bounded functions is more or less standard: Since we have a.e. convergence for a dense set of functions, namely for linear combinations of indicators, we just need a "maximal inequality" argument. As we will see, in this maximal inequality argument, we will work with a set of ω which satisfy conditions that are independent of the dynamical system. The two main conditions are the a.e. convergence of the averages in eq. (5.22) when the F i are indicators, and the maximal inequality in eq. (5.25) below. We will also use the strong law of large numbers, Theorem A.1.

The way we'll do the extension of a.e. convergence to bounded functions is that we first extend a.e. convergence to all bounded F 1 , then we extend it to all bounded F 1 , F 2 , then to all bounded F 1 , F 2 , F 3 , etc.

For this argument, it is convenient to introduce three notations: one for our averages, normalized by

n<N u n instead of n<N U n A N (F 1 , F 2 , . . . , F ) = 1 n<N u n n<N (U n -u n ) • T n F 1 • T 2n F 2 • • • T n F ,
and two for the 1-linear, dominating averages

B N F = 1 n<N u n n<N u n • T n F , C N F = 1 n<N u n n<N U n • T n F .
A summation by parts argument shows that B N is pointwise dominated by the usual ergodic averages 1 N n<N |T n F |, and hence we have the maximal inequality for the B N

(5.24)

X sup N B N F 2 ≤ c X F 2 .
With probability 1, we also have a maximal inequality for the C N (5.25)

X sup N C N F 2 ≤ c ω X F 2 .
This was established by [Bou88] for a much wider range of u n than we consider in this theorem: they just need to satisfy

n<N u n (log log N ) 1+δ log N → ∞ for some positive δ.
That this extra log log N factor is necessary for the maximal inequality and a.e. convergence, compared to the lone log N needed for mean convergence, was proved in [START_REF] Jones | Integer sequences with big gaps and the pointwise ergodic theorem[END_REF].

Let now F 1 be a function bounded by 1, and assume F 2 , F 3 , . . . , F are indicators. We want to show that, with probability 1, the oscillation of the A N is 0 almost surely

µ lim sup N |A N (F 1 , F 2 , . . . , F )| = 0 = 1.
We show this by showing that for any > 0 (5.26) µ lim sup

N |A N (F 1 , F 2 , . . . , F )| > ≤ .
Let > 0 be given and let G 1 be a linear combination of indicators so that (5.27)

X |F 1 -G 1 | 2 1/2 < δ,
where we'll choose δ later appropriately for . By Theorem D, we have lim sup

N |A N (G 1 , F 2 , . . . , F )(x)| = 0 for a.e. x.
We then have lim sup

N |A N (F 1 , F 2 , . . . , F )(x)| = lim sup N |A N (F 1 -G 1 , F 2 , . . . , F )(x)| for a.e. x.
Using the boundedness of the F i by 1 we can estimate pointwise as

|A N (F 1 -G 1 , F 2 , . . . , F )(x)| ≤ B N (F 1 -G 1 )(x) +C N (F 1 -G 1 )(x).
We thus have

X lim sup N |A N (F 1 -G 1 , F 2 , . . . , F )| ≤ X sup N B N (F 1 -G 1 ) + X sup N C N (F 1 -G 1 )
by the Cauchy-Schwarz-Bunyakovsky inequality for the integral

X ≤ X sup N B N (F 1 -G 1 ) 2 1/2 + X sup N C N (F 1 -G 1 )
2 1/2 using the maximal inequalities for B N in eq. (5.24) and for C N in eq. (5.25)

≤ c X (F 1 -G 1 ) 2 1/2 + c ω X (F 1 -G 1 ) 2 1/2
by the approximation in eq. (5.27)

≤ c ω δ.
Using this and Markov's inequality, we finally get

µ lim sup N |A N (F 1 , F 2 , . . . , F )| > ≤ 1 • X lim sup N |A N (F 1 -G 1 , F 2 , . . . , F )| ≤ c ω δ .
We see, we just have to choose δ small enough so that c ω δ < to get eq. (5.26). What we have accomplished so far is that our averages A N (F 1 , F 2 , . . . , F ) converge a.e. to 0 for all bounded F 1 and indicators F 2 , F 3 , . . . , F . But we can repeat the argument with F 2 in place of F 1 to get that A N (F 1 , F 2 , . . . , F ) converge a.e. to 0 for all bounded F 1 , F 2 and indicators F 3 , F 4 , . . . , F . Repeating the argument times, we eventually get that A N (F 1 , F 2 , . . . , F ) converge a.e. to 0 for bounded F 1 , F 2 , . . . , F .

PROOF OF THEOREM C, THE SEMIRANDOM CONVERGENCE THEOREM

Our first observation is that the a.e. convergence of our averages (6.1) 1

N n<N T n F 1 • (x)T r n F 2 (x)
to F 1 F 2 needs to be proved only for indicator functions F 1 , F 2 . This follows from a similar maximal inequality argument as we used to extend Theorem D from indicators to bounded functions. So, unless we say otherwise, we now assume, for the rest of the proof, that the F i are indicator functions. We will follow the general structure of the proof in [FLW12]. As in the proof of Theorem D, it is enough to prove convergence along a sparse subsequence of the N . As in that proof, for σ > 1, we choose the subsequence

I σ = {N 1 < N 2 < N 3 < . . .} so that n<N i u n ≈ σ i (and hence n<N i U n ≈ σ i ) (6.2) n<N i u n ≥ σ i but n<N u n < σ i for N < N i .
To be exact, since u n → 0, we have 1) for all i = 1, 2, 3, . . . We notice, that the averages in eq. (6.1) can be written in the form

n<N i u n = σ i + o(
1 n<N U n n<N U n T U 1 +U 2 +•••+U n F 1 T n F 2 .
The two main steps in proving that the above converges a.e. are that the "partial" expectations (6.3)

1 n<N u n n<N u n T U 1 +U 2 +•••+U n F 1 T n F 2
for all large enough N . This implies eq. (6.5) if N can be chosen so that, for all σ > 1 we have

N ∈I σ N < ∞, (6.7) and N ∈I σ exp -c 2 N n<N u n < ∞, (6.8)
where I σ is defined in eq. (6.2). This is because we need to show convergence only for the subsequence I σ . Following the proof of Theorem B, a duality and a transference argument shows that eq. (6.6) follows from (6.9) P sup

f ∈F ,g ∈G 1 n<N u n n<N (U n -u n ) 1 Q a<Q g (a) f a + (U 1 +U 2 + • • • +U n ) > N < exp -c 2 N n<N
u n for all large enough N , where G is the same as before, that is, it contains ±1 valued functions supported on the interval [0,Q)

G = g | g : [0,Q) → {-1, 1} ,
and F contains indicators supported on the interval 0,

Q +U 1 +U 2 + • • • +U N F = f | f : 0,Q +U 1 +U 2 + • • • +U N → {0, 1} .
In fact, except on a set with small probability, we can replace the interval [0,

Q +U 1 +U 2 + • • • +U N above,
which depends on ω, by the interval 0,Q + 2 n<N u n . This is because when we put X n = U n -u n and t = n<N u n in Bernstein's inequality, Lemma 4.1, we get (6.10)

P U 1 +U 2 + • • • +U N - n<N u n > n<N u n < exp -c n<N u n ,
and, of course, N ∈I σ exp -c n<N u n < ∞. So from now on, F denotes indicators on the interval 0,Q +

2 n<N u n F = f | f : 0,Q + 2 n<N u n → {0, 1} .
The next step in our method is to divide up the interval 0,Q + 2 n<N u n into residue classes (mod q)

for an appropriate q. The same way as in previous proofs, we get that a good choice for q is q = Q. We also get the requirement, using the cardinality of functions supported on a single residue class (mod q) in 0,Q + 2 n<N u n and the cardinality of G , that (6.11)

2 n<N u n q +Q ≤ c 2 N n<N u n .
Since q = Q, the left hand side of eq. (6.11) is smallest when (6.12)

q = Q = c n<N u n 1/2 .
In the above, nothing changes significantly, if we choose the constant c so that Q is an integer. Substituting eq. (6.12) into eq. (6.11), we get

N = c n<N u n -1/4
.

With these values all our requirements are satisfied including eqs. (6.7) and (6.8), and our proof of eq. (6.5) is finished.

Our next step in proving Theorem 6.1 is to consider the case when F 2 is orthogonal to the invariant functions. Since in this case, F 2 = 0, we want to prove

1 n<N u n n<N u n T U 1 +U 2 +•••+U n F 1 T n F 2 → 0.
By a maximal inequality argument-similar but simpler than the one we used to extend Theorem D to bounded functions-it is enough to prove eq. (6.12) for a class of functions which generates an L 2 -dense linear subspace of the orthocomplement of the T -invariant functions. This class of functions will be the "bounded" coboundaries, so those functions F 2 which can be written in the form F 2 = T G -G for some bounded G.

So let F 2 be a coboundary. We shall prove a much more general result: The only property of the sequence T 1 F 2 (x), T 2 F 2 (x), . . . we use is that 1 N L<n<L+N T n F 2 (x) converges to 0 uniformly in L as N → ∞. The only property of the random sequence {r 1 < r 2 < r 3 < . . .} we use is that it has 0 density as a consequence of the assumption that u n → 0. Lemma 6.2. Suppose the set R of positive integers has 0 density, and let X (n) denote its indicator. Let g 1 , g 2 , g 3 , . . . be a bounded sequence of real numbers which satisfy (6.13) lim

L→∞ 1 L M ≤n<M +L g n = 0 uniformly in M .
Then for any bounded sequence f 1 , f 2 , f 3 . . . of numbers and decreasing sequence w 1 ≥ w 2 ≥ w 3 ≥ . . . of weights with n w n = ∞ we have

lim N →∞ 1 n<N w n n<N w n f X (1)+X (2)+•••+X (n) g n = 0.
Proof. A summation by parts argument shows that we can assume all the weights w n are equal to 1, so we need to show 1

N n<N f X (1)+X (2)+•••+X (n) g n → 0.
The main observation is that the complement of R is basically a set which is the union of longer and longer intervals. More precisely, for any given length L, there is a S ⊂ R c of density 1 so that S is the union of intervals of length at least L. To see this, suppose to the contrary: there is a length L so that the set of k, k = 1, 2, 3, . . . , for which the interval [kL, (k + 1)L) contains a point from R has positive upper density, say, δ > 0. But then the upper density of R is at least δ/L, a contradiction. To prove the lemma, let L be arbitrary, and consider the average

1 K L k≤K kL≤n<(k+1)L f X (1)+X (2)+•••+X (n) g n . Let k 1 < k 2 < . . . be a sequence so that R ⊂ ∪ i [k i L, (k i + 1)L), and the density of (k i ) is 0. Write 1 K L k≤K kL≤n<(k+1)L f X (1)+X (2)+•••+X (n) g n = 1 K L i k i L≤n<(k i +1)L f X (1)+X (2)+•••+X (n) g n + 1 K L k =k i kL≤n<(k+1)L f X (1)+X (2)+•••+X (n) g n .
The first sum above goes to 0, since (k i ) has 0 density and the functions are assumed to be bounded. For the second sum, note that on each interval [kL, (k + 1)L), we have X

(n) = 0, hence f X (1)+X (2)+•••+X (n) is constant. We can estimate 1 K L k =k i kL≤n<(k+1)L f X (1)+X (2)+•••+X (n) g n ≤ 1 K k =k i 1 L kL≤n<(k+1)L g n .
By the assumption in eq. (6.13), 1 L kL≤n<(k+1)L g n is uniformly small if L is big, finishing the proof of the lemma.

This ends the proof of Theorem 6.1.

Our last task in the proof of Theorem C is to prove that with probability 1 we have, in every dynamical system, lim

N →∞ 1 n<N u n n<N (U n -u n )T U 1 +U 2 +•••+U n F 1 (x)T n F 2 (x) = 0 for almost every x. Let δ > 0 and (6.14) N = log n<N u n - (1+δ)
.

As many times before in this paper, our task is reduced to proving an inequality for the probability of averages on the integers

P sup f i ∈F i ,g ∈G 1 n<N u n n<N (U n -u n ) 1 Q a<Q g (a) f 1 a + U 1 +U 2 + • • • +U n f 2 (a + n) > N ≤ exp -c 2 N n<N u n , for all large enough N ,
where Q is to be determined momentarily, F 1 contains all the indicators supported in the interval 3 0,Q +

2 n<N u n F 1 = f | f : 0,Q + 2 n<N u n → {0, 1} , F 2 contains all the indicators supported in the interval [0,Q + N ), F 2 = f | f : [0,Q + N ) → {0, 1} ,
and G contains all the ±1 valued functions supported on the interval [0,Q)

G = g | g : [0,Q) → {-1, 1} .
We now choose the relatively prime moduli q 1 , q 2 , and we divide up the support of f i according to the residue classes (mod q i ). With the assumption that q 1 q 2 = Q, we further reduce the problem to the case when the f i are supported on a fixed r i residue class (mod q i ). This way, following the proof of Theorem A, we get the estimate (6.15) P sup

f i ∈F i ,g ∈G 1 n<N u n n<N (U n -u n ) 1 Q a<Q g (a) f 1 a + U 1 +U 2 + • • • +U n f 2 (a + n) > N ≤ q 2 q 1 exp Q + n<N u n q 1 + N q 2 - 1 4 2 N n<N u n .
Ignoring the negligible q 1 q 2 < exp c log N product (negligible compared to exp 2 N n<N u n , which is assumed to be exp O(N 1/2 ) ), we see our task is to choose the parameters Q, q 1 , q 2 so that

Q + n<N u n q 1 + N q 2 < c 2 N n<N u n .
3 We already showed in eq. (6.10) that we make only a small error in probability, if we replace the random interval 0,Q + n<N U n by the deterministic one 0,Q + 2 n<N u n .

If Q and q i were real variables, the left hand side is minimal if

Q = c 2 N n<N u n , q 1 = c -2 N , q 2 = c N 2 N n<N u n .
We certainly can choose integer values for Q, q i so that they are within constant multiples of the above optimal values, q 1 and q 2 are coprimes, and q 1 q 2 = Q. Using that q 1 q 2 = Q, we get the requirement

N 4 N n<N u n ≤ c 2 N n<N u n , hence N 1/2 ≤ c 3 N n<N u n ,
which is possible, since the value of N in eq. (6.14) is compatible with the assumption in eq. (2.6). With this, our proof is finished. Then there is a set Ω ⊂ Ω with P (Ω ) = 1 such that for every ω ∈ Ω the following is true: for all α > 0 there is N (α) so that if A ⊂ [1, N ] for some N > N (α) and A has more than αN elements, then A contains an arithmetic progression a, a + r, a + 2r, . . . , a + r of length ( + 1) with some r ∈ R ω N .

7.2. Our method for bounded functions. In our paper, we chose to extend almost everywhere convergence results from indicators to bounded functions using the method of maximal inequalities. Our method can be applied directly to bounded functions, though. The modification in the proof is needed only in the definition of the sets F . For example, consider the proof of Theorem D in the = 1 case. We need to consider the averages (7.1)

1 n<N u n n<N (U n -u n ) 1 Q a<Q f (a + n) for f : [0,Q + N ) → [-1, 1].
As a first step, we want to replace f by a function which take on values from a sufficiently dense discrete subset of the interval [0, 1]. Assume, for notational simplicity, that N is the reciprocal of a positive integer. A dense enough set is the set

D = -1, --1 N -1 N , • • • -2 N ,
-N , 0, N , 2 N , . . . , -1 N -1 N , 1 , so we define

F = f | f : [0,Q + N ) → D .
Now, if we replace f in eq. (7.1) by a function from F , then with probability very close to 1, we only make a 2 N error. It follows that it is enough to consider functions from F in eq. (7.1). The cardinality of F is not much bigger than it was before: since |D| = c -1 N , we have |F | < |D| 2N < exp c N log -1 N .

Since in Theorem D, N is a negative power of log N , this extra log -1 N factor would account for an extra log log N speed-negligible as the speed in Theorem D is stated, but it would not be negligible if we wanted to state the best possible speed our proof could give. For example, it's clear from the proof that we can weaken the assumption in eq. (5.21) of Theorem D to u n • n 1/2 (log n) 2 log log 2+δ n → ∞ for some δ > 0.

But if we used our method directly to bounded functions instead of maximal inequalities we would have needed the stronger

u n • n 1/2
(log n) 2 log log 3+δ n → ∞ for some δ > 0 assumption. This is the reason why we decided to use the well-known maximal inequality techniques, and hence we avoided the slight inefficiency and complications in our method when dealing with bounded functions instead of indicators. 7.3. Convexity methods. We can also use the more geometric convexity methods to extend almost sure convergence results from indicators to bounded functions. This method is signified by the Krein-Milman theorem, though we need only the simplest version of it for finite sets. Let us briefly give here the representation needed to do the extension from indicators to nonnegative functions bounded by 1 4 . Let

Γ = g |g : [1, K ] → {0, 1} = {0, 1} K , F = f | f : [1, K ] → [0, 1] = [0, 1] K .
We want to show that for each f ∈ F there is a probability measure µ f on Γ so that There is only a slight complication when we have to extend results for multiple averages from indicators to bounded functions. For example, for double averages, we need to be able to represent the product f 1 (b 1 ) f 2 (b 2 ) in an integral form. This can be done using the representation in eq. (7.2) for f 1 and f 2 separately and Fubini's theorem

f 1 (b 1 ) f 2 (b 2 ) = G g (b 1 )d µ f 1 (g ) G g (b 2 )d µ f 2 (g ) = G ×G g 1 (b 1 )g 2 (b 2 )d µ f 1 × µ f 2 (g 1 , g 2 ),
which is just a fancy (but useful) way of writing

f 1 (b 1 ) f 2 (b 2 ) = µ f 1 g |g (b 1 ) = 1 • µ f 2 g |g (b 2 ) = 1 .
4 Similar representation applies for extending results for ±1-valued functions to functions bounded by 1. This follows if the above series is integrable, so from (A.4)

E i 1 n<N i EX n n<N i X n -EX n 2 = i E 1 n<N i EX n n<N i X n -EX n 2 < ∞.
A consequence of the multiplicativity assumption in eq. (A.1) is orthogonality E(X n -EX n )(X m -EX m ) = 0 for n = m, and hence we have

E n<N i X n -EX n 2 = n<N i E(X n -EX n ) 2 . Since E(X n -EX n ) 2 ≤ EX 2 n ≤ cEX n ,

  Finitary version of Theorem A. We use the setup commonly used in combinatorics: for a given N , we want to select each integer 1, 2, . . . , N with a uniform probability u N . So for each N , we take U N 1 ,U N 2 , . . . ,U N N , a sequence of independent, identically distributed, 0 -1-valued random variables, with the lawP (U N n = 1) = 1 -P (U N n = 0) = u N , n = 1, 2, . . . , N . The sequence U N 1 ,U N 2 , . . . ,U N N is the indicator of the set R ω N , R ω N = n|U N n (ω) = 1 .The proof of Theorem A can easily be adjusted to giveTheorem (Finitary version of Theorem A). Let be a positive integer and assumeu N • N 1/( +1) → ∞.

g

  (b)d µ f (g ).The requirement of the representation uniquely determines the measure. For any b, eq. (7.2) looks likef (b) = 1 • µ f g |g (b) = 1 . It follows µ f g |g (b) = 1 = f (b), µ f g |g (b) = 0 = 1f (b).Since the sets µ g |g (b) = 1 and µ g |g (b) = 0 , b = 1, 2, . . . , K are all the cylinder sets of Γ = {0, 1} K , the measure µ f is uniquely determined as a product measure.With this representation, it's a simple exercise to extend, say, eq. (5.8), from indicators to nonnegative functions bounded by 1.

  Let {a 1 , a 2 , a 3 , . . . , a n , . . .} be a sequence of real or complex numbers with |a n | ≤ 1.

	Then for any , 0 ≤ < 1, we have
	P	1

we have P n<N X n ≥ t ≤ 2 max exp -t 2 /4 n<N EX 2 n , exp -t /(2K ) for all t > 0. Corollary 4.2. n<N u n n<N

  , which, by eq. (A.2), establishes eq. (A.4).We now want to show that the N th average is close to the N i th if N i ≤ N < N i +1 . We can estimate, since the X n are non-negative,

		we have
	E	1 n<N i EX n n<N i	X n -EX n	2	≤	c n<N i EX n
	1 n<N EX n n<N	X n ≤	1 n<N i EX n n<N i +1	X n
			=	n<N i +1 EX n n<N i EX n	•	1 n<N i +1 EX n n<N i +1	X n .
	This implies, by eq. (A.3) and eq. (A.2),
	lim sup N →∞	1 n<N EX n n<N	X n ≤ lim i →∞	(i + 1) 2 + O(1) i 2 + O(1)
						= 1.
	Similar estimate shows that	lim inf N →∞	1 n<N EX n n<N	X n ≥ 1,
	finishing our proof.

This is the only place where we use that the (u n ) is decreasing.

converge to F 1 F 2 , and that the difference between the two averages

We will be able to prove the convergence of the partial expectations in eq. ( 6.3) for any sequence (u n ) with u n → 0 and satisfying the dissipative property n u n = ∞. To emphasize this fact, we formulate the result explicitly Theorem 6.1. Suppose the decreasing sequence

and lim

We then have, with probability 1, in any dynamical system,

x ∈ X and any bounded functions F i .

Proof. We divide the proof into two cases: first, when F 2 is T -invariant, and second, when F 2 is orthogonal to all T -invariant functions. The function F 1 is an indicator throughout the proof. Let thus F 2 be T -invariant. We then need to prove the pointwise convergence of

The a.e. convergence of the averages (6.4)

to F 1 follows from the pointwise ergodic theorem. To see this, let

all the elements of our random sequence which are less than N . Since U 1 ,U 2 , . . . is the indicator of the random sequence, U n = 1 exactly when n = r k for some k ≤ K . It follows that n<N U n = K , and

so the average in eq. (6.4) is the K th ergodic average 1 K 1≤k≤K T k F 1 . Since the averages in eq. (6.4) converge a.e. to F 1 , by the strong law of large numbers, the averages

also converge to F 1 . We then need to show that, with full probability, the difference between the two averages converges to 0 a.e. (6.5) lim

Let N → 0. Later we'll find that the fastest rate our method allows N to go to 0 is O n<N u n -1/4 which is plenty, as we will soon see. We shall prove (6.6)

7.4. Extension to commuting transformations. In short: our method in its present form doesn't work for commuting transformations. For example, we have Unsolved problem 7.1. Let b < 1/( + 1) and u n = n -b .

Show that with probability 1 in any dynamical system, for any commuting transformations T 1 , T 2 , . . . , T , the averages 1

The good news is that the extension of Theorem C to commuting transformations is true. In other words, the semirandom averages 1

do converge almost everywhere for commuting measure preserving transformations T i as long as the random sequence {r 1 < r 2 < r 3 < . . .} satisfies r n /n 2-for some positive . The proof of this will be discussed in an upcoming paper.

APPENDIX A. STRONG LAW OF LARGE NUMBERS

Here we give a quick proof of the strong law of large numbers in a form needed in our paper. The result is due to Kolmogorov.

Theorem A.1 (Strong law of large numbers for uniformly bounded rv's). Suppose the random variables X 1 , X 2 , . . . are non-negative, uniformly bounded For an example of two random variables which are nonnegative, uncorrelated but not independent, take X 1 (x) = 1 + sin(2πx) and X 2 (x) = 1 + sin(2π2x) defined on the unit interval [0, 1]. (Looking at the graph of the two functions, by inspection we can find a λ, 0 < λ < 2, so that the level sets {X 1 > λ} and {X 2 > λ} are nonempty, but disjoint.)

Proof. We want to use a subsequence argument. Define the set

In words: N i is the smallest index N for which n<N EX n ≥ i 2 . That I is well defined and infinite follows from the dissipative assumption N EX n = ∞. Since the X n are uniformly bounded, we have (A.2)

We first want to show that we have a.e. convergence along the subsequence I