W Bas De Haas
email: bas.dehaas@cs.uu.nl

Matthias Robine
email: matthias.robine@labri.fr

Pierre Hanna
email: pierre.hanna@labri.fr

Remco C Veltkamp
email: remco.veltkamp@cs.uu.nl

Frans Wiering
email: frans.wiering@cs.uu.nl

Comparing Approaches to the Similarity of Musical Chord Sequences

Keywords: MIR, Harmony, Chord Symbol, Similarity, Evaluation, Groundtruth data

We present an comparison between two recent approaches to the harmonic similarity of musical chords sequences. In contrast to earlier work, that mainly focuses on the similarity of musical scores or musical audio, in this paper we specifically use on the symbolic chord description as the primary musical representation and the similarity between sequences of these descriptions. In an experiment we compare a geometrical and an alignment approach to harmonic similarity, and measure the effects of chord description detail and a priori key information on retrieval performance. For this experiment a large new chord sequence corpus is assembled. The results show that a computational costly alignment approach significantly outperforms a much faster geometrical approach in most cases, that a priori key information boosts retrieval performance, and that using a triadic chord representation yields significantly better results than using more simple or more complex chord representations.

Introduction

In the last decades Music Information Retrieval (MIR) has evolved into a broad research area that aims in keeping large repositories of digital music maintainable and accessible. Within MIR two main directions can be discerned: symbolic music retrieval and the retrieval of musical audio. The first direction traditionally uses score-based representations to tackle typical retrieval problems. One of the most important and most intensively studied of these is probably the problem of determining the similarity of a specific musical feature, e.g. melody, rhythm, etc. The second direction-musical audio retrieval-extracts features from the audio signal and uses these features for estimating whether two pieces of music share certain musical properties. In this paper we focus on a musical representation that is symbolic but can be estimated reasonably well from audio: chord sequences.

Only recently, partly motivated by the growing interest in audio chord finding, MIR researchers have started using chords descriptions as principal representation for modeling music similarity. Naturally, these representations are specifically suitable for capturing the harmonic similarity of a musical piece. However, determining the harmonic similarity of sequences of chords gives rise to three questions. First, what is harmonic similarity? Second, why do we need harmonic similarity? Last, do chord descriptions provide a valid and useful abstraction of the musical data for determining music similarity? The first two questions we will address in this introduction; the third question we will answer empirically in a retrieval experiment. In this experiment we will compare a geometrical and an alignment based harmonic similarity measure.

The first question-what is harmonic similarity-is difficult to answer. We strongly believe that if we want to model what makes two pieces of music similar, we must not only look at the musical data, but especially at the human listener. It is important to realize that music only becomes music in the mind of the listener, and probably not all information needed for good similarity judgment can be found in the data alone. Human listeners, musician or non-musician, have extensive culture-dependent knowledge about music that needs to be taken into account when judging music similarity.

In this light we consider the harmonic similarity of two chord sequences to be the degree of agreement between structures of simultaneously sounding notes and the agreement between global as well as local relations between these structures in both sequences as perceived by the human listener. With the agreement between structures of simultaneously sounding notes we denote the similarity that a listener perceives when comparing two chords in isolation and without surrounding musical context. However, chords are rarely compared in isolation and the relations between the global context-the key-of a piece and the relations to the local context play a very important role in the perception of tonal harmony. The local relations can be considered the relations between functions of chords within a limited time frame, for instance the preparation of a chord with a dominant function with a sub-dominant. All these factors play a role in the perception of tonal harmony and should be shared by two compared pieces up to certain extent to if they are considered similar.

The second question about the usefulness of harmonic similarity is easier to answer, since music retrieval based on harmony sequences offers various benefits. It allows for finding different versions of the same song even when melodies vary. This is often the case in cover songs or live performances, especially when these performances contain improvisations. Moreover, playing the same harmony with different melodies is an essential part of musical styles like jazz and blues. Also, variations over standard basses in baroque instrumental music can be harmonically very related.

The application of harmony matching methods is broadened further by the extensive work on chord label extraction from musical audio data within the MIR community, e.g. [START_REF] Mauch | Using Musical Structure To Enhance Automatic Chord Transcription[END_REF][START_REF] Bello | A Robust Mid-Level Representation for Harmonic Content in Music Signals[END_REF]. Chord labeling algorithms extract symbolic chord labels from musical audio: these labels can be matched directly using the algorithms covered in this paper.

If you would ask a jazz musician to answer the third question-whether chord descriptions are useful-he will probably agree that they are, since working with chord labels is everyday practice in jazz. However, we will show in this paper that they are also useful for retrieving pieces with a similar but not identical chord sequence by performing a large experiment. In this experiment we compare two harmonic similarity measures, the Tonal Pitch Step Distance (TPSD) [START_REF] De Haas | Tonal Pitch Step Distance: A Similarity Measure for Chord Progressions[END_REF] and the Chord Sequence Alignment System (CSAS) [START_REF] Hanna | An Alignment Based System for Chord Sequence Retrieval[END_REF], and test the influence of different degrees of detail in the chord description and the knowledge of the global key of a piece on retrieval performance.

The next section gives a brief overview of the current achievements in chord sequence similarity matching and harmonic similarity in general, Section 3 describes the data used in the experiment and Section 4 presents the results.

Contribution. This paper presents an overview of chord sequence based harmonic similarity and two harmonic similarity approaches are compared in an experiment. For this experiment a new large corpus of 5028 chord sequences is assembled and both algorithms are subjected to six tasks. All tasks use the same dataset, but differ in the amount of chord detail and in the use of a priori key information. The results show that a computational costly alignment approach significantly outperforms a much faster geometrical approach in most cases, that a priori key information boosts retrieval performance, and that using a triadic chord representation yields significantly better results than using more simple or more complex chord representations.

Background: Similarity Measures for Chord Sequences

The harmonic similarity of symbolic music has been investigated by many authors, but the number of systems that focus solely on similarity chords sequences is much smaller. Of course it is always possible to convert notes into chords and vice versa, but this is not a trivial task. Nowadays, several algorithms can correctly segment and label approximately 80 percent of a symbolic dataset (see for a review [START_REF] Temperley | The Cognition of Basic Musical Structures[END_REF]). Within the audio domain hidden Markov Models are frequently used for chord label assignment, e.g. [START_REF] Mauch | Using Musical Structure To Enhance Automatic Chord Transcription[END_REF][START_REF] Bello | A Robust Mid-Level Representation for Harmonic Content in Music Signals[END_REF]. The algorithms considered in this paper abstract from these labeling tasks and focus on the similarity between chord progressions only. As a consequence, we assume that we have a sequence of symbolic chord labels describing the chord progression in a piece of music.

The systems currently known to us that are designed to match these sequences of symbolic chord descriptions are: the TPSD [START_REF] De Haas | Tonal Pitch Step Distance: A Similarity Measure for Chord Progressions[END_REF], the CSAS [START_REF] Hanna | An Alignment Based System for Chord Sequence Retrieval[END_REF] and a harmony grammar approach [START_REF] De Haas | Modeling Harmonic Similarity Using a Generative Grammar of Tonal Harmony[END_REF]. The first two are quantitatively compared in this paper and are introduced in the next two subsections, respectively. They have been compared before, but all previous evaluations of TPSD and CSAS were done with relatively small datasets (<600 songs) and the data in [START_REF] Hanna | An Alignment Based System for Chord Sequence Retrieval[END_REF] did not precisely match the one used in [START_REF] De Haas | Tonal Pitch Step Distance: A Similarity Measure for Chord Progressions[END_REF]. The harmony grammar approach could, All The Things You Are

TPS Score

Fig. 1. A plot demonstrating the comparison of two similar versions of All the Things You Are using the TPSD. The total area between the two step functions, normalized by the duration of the shortest song, represents the distance between both songs. A minimal area is obtained by shifting one of the step functions cyclically.

at the time of writing, not compete in this experiment because in its current state it is yet unable to parse all the songs in the used dataset. We expect this issue to be resolved in the near future. The next section introduces the TPSD and the improvements over the implementation used for the experiment here and the implementation in [START_REF] De Haas | Tonal Pitch Step Distance: A Similarity Measure for Chord Progressions[END_REF]. Section 2.2 highlights the different variants of the CSAS. The main focus of this paper is on the similarity of sequences of chord labels, but there exist other relevant harmony based retrieval methods: some of these are briefly reviewed in Section 2.3.

Tonal Pitch Step Distance

The TPSD uses Lerdahl's [START_REF] Lerdahl | Tonal Pitch Space[END_REF] Tonal Pitch Space (TPS) as its main musical model. TPS is a model of tonality that fits musicological intuitions, correlates well with empirical findings from music cognition [START_REF] Krumhansl | Cognitive Foundations of Musical Pitch[END_REF] and can be used to calculate a distance between two arbitrary chords. The TPS model can be seen as a scoring mechanism that takes into account the number of steps on the circle of fifths between the roots of the chords, and the amount of overlap between the chord structures of the two chords and their relation to the global key.

The general idea behind the TPSD is to use the TPS to compare the change of chordal distance to the tonic over time. For every chord the TPS distance between the chord and the key of the sequence is calculated, which results in a step function (see Figure 1). As a consequence, information about the key of the piece is essential. Next, the distance between two chord sequences is defined as the minimal area between the two step functions over all possible horizontal circular shifts. To prevent that longer sequences yield larger distances, the score is normalized by dividing it by the duration of the shortest song.

The TPS is an elaborate model that allows to compare every arbitrary chord in an arbitrary key to every other possible chord in any key. The TPSD does not use the complete model and only utilizes the parts that facilitate the comparison of two chords within the same key. In the current implementation of the TPSD time is represented in beats, but generally any discrete representation could be used.

The TPSD version used in this paper contains a few improvements compared to the version used in [START_REF] De Haas | Tonal Pitch Step Distance: A Similarity Measure for Chord Progressions[END_REF]: by applying a different step function matching algorithm from [START_REF] Arkin | An Efficiently Computable Metric for Comparing Polygonal Shapes[END_REF], and by exploiting the fact that we use discrete time units that enable us to sort in linear time using counting sort [START_REF] Cormen | Introduction to Algorithms[END_REF], a running time of O(nm) is achieved where n and m are the number of chord symbols in both songs. Furthermore, to be able to use the TPSD in situations where a priori key information is not available, the TPSD is extended with a key finding algorithm.

Key finding. The problem of finding the global key of piece of music is called key finding and in the current case this is done on the basis of chord information only. The rationale behind the key finding algorithm that we present here is the following: we consider the key that minimizes the total TPS distance and best matches the starting and ending chord, the key of the piece.

For minimizing the total TPS distance, the TPSD key finding uses TPS based step functions as well. We assume that when a song matches a particular key, the TPS distances between the chords and the tonic of the key are relatively small. The general idea is to calculate 24 step functions for a single chord sequence, one for each major and minor key. Subsequently, all these keys are ranked by sorting them on the area between their TPS step function and the x-axis; the smaller the total area, the better this key fits the piece, and the higher the rank. Often, the key at the top rank is the correct key. However, among the false positives at rank one, non-surprisingly, the IV, V and VI relative to the ground-truth key1 are found regularly. This makes sense because, when the total of TPS distances of the chords to C is small, the distances to F, G and Am might be small as well. Therefore, to increase performance, an additional scoring mechanism is designed that takes into account the IV, V and VI relative to the ground-truth key. Of all 24 keys, the candidate key that minimizes the following sum S is considered the key of the piece.

S = αr(I) + r(IV ) + r(V ) + r(V I) +
β if the first chord matches the key β if the last chord matches the key

Here r(.) denotes the rank of the candidate key, a parameter α determines how important the tonic is compared to other frequently occurring scale degrees and β controls the importance of the key matching first and last chord. The parameters α and β were tuned by hand and an α of 2, and a β of 4 were found to give good results. Clearly, this simple key-finding algorithm is biased towards western diatonic music, but for the corpus used in this paper it performs quite well. The algorithm scores 88.8 percent correct on a subset of 500 songs of the corpus used in the experiment below for which we manually checked the correctness of the ground-truth key. The above algorithm takes O(n) time, where n is the number of chord symbols, because the number of keys is constant.

Root interval step functions. For the tasks where only the chord root is used we use a different step function representation (See Section 4). In these tasks the interval between the chord root and the root note of the key defines the step height and the duration of the chord again defines the step length. This matching method is very similar to the melody matching approach by Aloupis et al. [START_REF] Aloupis | Algorithms for Computing Geometric Measures of Melodic Similarity[END_REF]. Note that the latter was never tested in practice. The matching and key finding methods are not different from the other variants of the TPSD. Note that in all TPSD variants chord inversions are ignored.

Chord Sequence Alignment System

The CSAS algorithm is based on local alignment and computes similarity scores between sequences of symbols representing chords or distances between chords and key. String matching techniques can be used to quantify the differences between two such sequences. Among several existing methods, Smith and Waterman's approach [START_REF] Smith | Identification of Common Molecular Subsequences[END_REF] detects similar areas in two sequences of abitrary symbols. This local alignment or local similarity algorithm locates and extracts a pair of regions, one from each of the two given strings, that exhibit high similarity. A similarity score is calculated by performing elementary operations transforming the one string into the other. The operations used to transform the sequences are deletion, insertion or substitution of a symbol. The total transformation from the one string into the other can be solved with a dynamic programming in quadratic time.

The following example illustrates local alignment by computing a distance between the first chords of two variants of the song All The Things You Are considering only the root notes of the chords. The I, S and D denote Insertion, Substitution, and Deletion of a symbol, respectively. An M represents a matching symbol:

string 1 F B♭ E♭ A♭ D♭ D G C C string 2 F F B♭ A A♭ A♭ D♭ D C C operation I M M S M I M M D M M score -1 +2 +2 -2 +2 -1 +2 +2 -1 +2 +2
Algorithms based on local alignment have been successfully adapted for melodic similarity [START_REF] Mongeau | Comparison of Musical Sequences[END_REF][START_REF] Hanna | On Optimizing the Editing Algorithms for Evaluating Similarity Between Monophonic Musical Sequences[END_REF][START_REF] Van Kranenburg | Musical Models for Folk-Song Melody Alignment[END_REF] and recently it has been used to determine harmonic similarity [START_REF] Hanna | An Alignment Based System for Chord Sequence Retrieval[END_REF] as well. Two steps are necessary to apply the alignment technique to the comparison of chord progressions: the choice of the representation of a chord sequence, and costs of the elementary operations between symbols. To take the durations of the chords into account, we represent the chords at every beat. The algorithm has therefore a complexity of O(nm), where n and m are the sizes of the compared songs in beats. The cost function can either be adapted to the chosen representation or can simply be binary, i.e. the cost is positive (+2) if the two chords described are identical, and negative (-2) otherwise. The insertion or deletion cost is set to -1.

Absolute representation. One way of representing a chord sequence is to simply represent the chord progression as a sequence of absolute root notes and in that case prior knowledge of the key is not required. An absolute representation of the chord progression of the 8 first bars of the song All The Things You Are is then:

F, B♭, E♭, A♭, D♭, D, G, C, C
In this case, the substitution costs may be determined by considering the difference in semitones, the number of steps on the circle of fifths between the roots, or by the consonance of the interval between the roots, as described in [START_REF] Hanna | On Optimizing the Editing Algorithms for Evaluating Similarity Between Monophonic Musical Sequences[END_REF].

For instance, the cost of substituting a C with a G (fifth) is lower than the substitution of a C with a D (Second). Taking into account the mode in the representation can affect the cost function as well: a substitution of a C for a Dm is different from a substitution of a C for a D, for example. If the two modes are identical, one may slightly increase the similarity score, and decrease it otherwise. Another possible representation of the chord progression is a sequence of absolute pitch sets. In that case one can use musical distances between chords, like Lerdahl's TPS model [START_REF] Lerdahl | Tonal Pitch Space[END_REF] or the distance introduced by Paiement et al. [START_REF] Paiement | A probabilistic model for chord progressions[END_REF], as a cost function for substitution.

Key-relative representation. If key information is known beforehand, a chord can be represented as a distance to this key. The distances can be expressed in various ways: in semitones, or as the number of fifths between the roots of the chords and the tonic of the key of the song, or with more complex musical models, such as TPS. If in this case the key is A♭ and the chord is represented by the difference in semitones, the representation of the chord progression of the first eight bars of the song All The Things You Are will be:

3, 2, 5, 0, 5, 6, 1, 4, 4

If all the notes of the chords are taken into account, the TPS or Paiement distances can be used between the chords and the triad of the key to construct the representation. The representation is then a sequence of distances, and we use an alignment between these distances instead of between the chords themselves. This representation is very similar to the representation used in the TPSD. The cost functions used to compare the resulting sequences can then be binary, or linear in similarity regarding the difference observed in the values.

Transposition invariance. In order to be robust to key changes, two identical chord progressions transposed in different keys have to be considered as similar. The usual way to deal with this issue [START_REF] Uitdenbogerd | Music Information Retrieval Technology[END_REF] is to choose a chord representation which is transposition invariant. A first option is to represent transitions between successive chords, but this has been proven to be less accurate when applied to alignment algorithms [START_REF] Hanna | On Optimizing the Editing Algorithms for Evaluating Similarity Between Monophonic Musical Sequences[END_REF]. Another option is to consider a key relative representation, like the representation described above which is by definition transposition invariant. However, this approach is not robust against local key changes. With an absolute representation of chords, we use an adaptation of the local alignment algorithm proposed in [START_REF] Allali | Local Transpositions in Alignment of Polyphonic Musical Sequences[END_REF]. It allows to take into account an unlimited number of local transpositions and can be applied to representations of chord progressions to account for modulations.

According to the choice of the representation and the cost function, several variants are possible in order to build an algorithm for harmonic similarity. In Section 4 we explain the different representations and scoring functions used in the different tasks of the experiment and their effects on retrieval performance.

Other Methods for Harmonic Similarity

The third harmonic similarity measure using chord descriptions is a generative grammar approach [START_REF] De Haas | Modeling Harmonic Similarity Using a Generative Grammar of Tonal Harmony[END_REF]. The authors use a generative grammar of tonal harmony to parse the chord sequences, which results in parse trees that represent harmonic analyses of these sequences. Subsequently, a tree that contains all the information shared by the two parse trees of two compared songs is constructed and several properties of this tree can be analyzed yielding several similarity measures. Currently a parser can reject a sequence of chords as being ungrammatical. We expect this issue to be resolved in the near future by applying a error-correcting parser [START_REF] Swierstra | Combinator parsing: A short tutorial[END_REF].

Another interesting retrieval system based on harmonic similarity is the one developed by Pickens and Crawford [START_REF] Pickens | Harmonic Models for Polyphonic Music Retrieval[END_REF]. Instead of describing a musical segment with one chord, they represent a musical segment as a vector describing the 'fit' between the segment and every major and minor triad. This system then uses a Markov model to model the transition distributions between these vectors for every piece. Subsequently, these Markov models are ranked using the Kullback-Liebler (KL) divergence. It would be interesting to compare the performance of these systems to the algorithms tested in here in the future.

Other interesting work has been done by Paiement et al. [START_REF] Paiement | A probabilistic model for chord progressions[END_REF]. They define a similarity measure for chords rather that for chord sequences. Their similarity measure is based on the sum of the perceived strengths of the harmonics of the pitch classes in a chord, resulting in a vector of twelve pitch classes for each musical segment. Paiement et al. subsequently define the distance between two chords as the euclidean distance between two of these vectors that correspond to the chords. Next, they use a graphical model to model the hierarchical dependencies within a chord progression. In this model they used their chord similarity measure for the calculation of the substitution probabilities between chords.

A Chord Sequence Corpus

The Chord Sequence Corpus used in the experiment consists of 5,028 unique human-generated Band-in-a-Box files that are collected from the Internet. Bandin-a-Box is a commercial software package [START_REF] Gannon | Band-in-a-Box[END_REF] that is used to generate musical accompaniment based on a lead sheet. A Band-in-a-Box file stores a sequence of chords and a certain style, whereupon the program synthesizes and plays a MIDI-based accompaniment. A Band-in-a-Box file therefore contains a sequence of chords, a melody, a style description, a key description, and some information about the form of the piece, i.e. the number of repetitions, intro, outro etc.

For extracting the chord label information from the Band-in-a-Box files we have extended software developed by Simon Dixon and Matthias Mauch [START_REF] Mauch | Discovering Chord Idioms Through Beatles And Real Book Songs[END_REF]. Throughout this paper we have been referring to chord labels or chord descriptions. To rule out any possible vagueness, we adopt the following definition of a chord: a chord always consist of a root, a chord type and an optional inversion. The root note is the fundamental note upon which the chord is built, usually as a series of ascending thirds. The chord type (or quality) is the set of intervals relative to the root that make up the chord and the inversion is defined as the degree of the chord that is played as bass note. One of the most distinctive features of the chord type is its mode, which can either be major or minor.

Although a chord label always describes these three properties, root, chord type and inversion, musicians and researchers use different syntactical systems to describe them, and also Band-in-a-Box uses its own syntax to represent the chords. Harte et al. [START_REF] Harte | Symbolic Representation of Musical Chords: A Proposed Syntax for Text Annotations[END_REF] give an in depth overview of the problems related to representing chords and suggests a unambiguous syntax for chord labels. An example of a chord sequence as found in a Band-in-a-Box file describing the chord sequence of All the Things You Are is given in Table 1.

All songs of the chord sequence corpus were collected from various Internet sources. These songs were labeled and automatically checked for having a unique chord sequence. All chord sequences describe complete songs and songs with fewer than 3 chords or shorter than 16 beats were removed from the corpus in an earlier stage. The titles of the songs, which function as a ground-truth, as well as the correctness of the key assignments, were checked and corrected manually. The style of the songs is mainly jazz, latin and pop. Within the collection, 1775 songs contain two or more similar versions, forming 691 classes of songs. Within a song class, songs have the same title and share a similar melody, but may differ in a number of ways. They may, for instance, differ in key and form, they may differ in the number of repetitions, or have a special introduction or ending. The richness of the chords descriptions may also diverge, i.e. a C 7♭9♭13 may be written instead of a C 7 , and common substitutions frequently occur. Examples of the latter are relative substitution, i.e. Am instead of C, or tritone substitution, e.g. F# 7 instead of C 7 . Having multiple chord sequences describing the same song allows for setting up a cover-song finding experiment. The the title of the song is used as ground-truth and the retrieval challenge is to find the other chord sequences representing the same song.

The distribution of the song class sizes is displayed in Table 2 and gives an impression of the difficulty of the retrieval task. Generally, Table 2 shows that the song classes are relatively small and that for the majority of the queries there is only one relevant document to be found. It furthermore shows that 82.5% of the songs is in the corpus for distraction only. The chord sequence corpus is available to the research community on request.

Experiment: Comparing Retrieval Performance

We compared the TPSD and the CSAS in six retrieval tasks. For this experiment we used the chord sequence corpus described above, which contains sequences that clearly describe the same song. For each of these tasks the experimental setup was identical: all songs that have two or more similar versions were used as a query, yielding 1775 queries. For each query a ranking was created by sorting the other songs on their TPSD and CSAS scores and these rankings and the runtimes of the compared algorithms were analyzed. Complete Chord Key as stored in the Band-in-a-Box file Table 3. The TPSD and CSAS are compared in six different retrieval tasks.

Tasks

The tasks, summarized in Table 3, differed in the level of chord information used by the algorithms and in the usage of a priori global key information. In tasks 1-3 no key information was presented to the algorithms and in the remaining 3 tasks we used the key information, which was manually checked for correctness, as stored in the Band-in-a-Box files. The tasks 1-3 and 4-6 furthermore differed in the amount of chord detail that was presented to the algorithms: in tasks 1 and 4 only the root note of the chord was available to the algorithms, in tasks 2 and 5 the root and the triad were available and in tasks 3 and 6 the complete chord as stored in the Band-in-a-Box file was presented to the algorithms.

The different tasks required specific variants of the tested algorithms. For tasks 1-3 the TPSD used the TPS key finding algorithm as described in Section 2.1. For the tasks 1 and 4, involving only chord roots, a simplified variant of the TPSD was used, for the tasks 2, 3, 5 and 6 we used the regular TPSD, as described in Section 2.1 and [START_REF] De Haas | Tonal Pitch Step Distance: A Similarity Measure for Chord Progressions[END_REF].

To measure the impact of the chord representation and substitution functions on retrieval performance, different variants of the CSAS were built also. In some cases the choices made did not yield the best possible results, but they allow the reader to understand the effects of the parameters used on retrieval performance. The CSAS algorithms in tasks 1-3 all used an absolute representation and the algorithms in tasks 4-6 used a key relative representation. In tasks 4 and 5 the chords were represented as the difference in semitones to the root of the key of the piece and in task 6 as the Lerdahl's TPS distance between the chord and the triad from the key (as in the TPSD). The CSAS variants in tasks 1 and 2 used a consonance based substitution function and algorithms in tasks 4-6 a binary substitution function was used. In tasks 2 and 5 a binary substitution function for the mode was used as well: if the mode of the substituted chords matched, no penalty was given, if they did not match, a penalty was given. A last parameter that was varied was the use of local transpositions. The CSAS variants applied in tasks 1 and 3 did not consider local transpositions, but the CSAS algorithm used in task 2 did allow local transpositions (see Section 2.2 for details).

The TPSD was implemented in Java and the CSAS was implemented in C++, but a small Java program was used to parallelize the matching process. All runs were done on a Intel Xeon quad-core CPU at a frequency of 1.86 GHz. and 4 Gb of RAM running 32 bit Linux. Both algorithms were parallelized to optimally use the multiple cores of the CPUs.

Results

For each task and for each algorithm we analyzed the rankings of all 1775 queries with 11-point precision recall curves and Mean Average Precision (MAP). Figure 2 displays the interpolated average precision and recall chart for the TPSD and the CSAS for all tasks listed in Table 3. We calculated the interpolated average precision as in [START_REF] Manning | Introduction to Information Retrieval[END_REF] and probed it at 11 different recall levels. In all evaluations the query was excluded from the analyzed rankings. In tasks 2 and 4-6 the CSAS outperforms the TPSD and in tasks 1 and 3 the TPSD outperforms the CSAS. The curves all have a very similar shape, this is probably due to the specific sizes of the song classes and the fairly limited amount of large song classes (see Table 2).

In Figure 3 we present the MAP and the runtimes of the algorithms on two different axes. The MAP is displayed on the left axis and the runtimes are shown on right axis that has an exponential scale doubling the amount of time at every tick. The MAP is a single-figure measure, which measures the precision at all recall levels and approximates the area under the (uninterpolated) precision recall graph [START_REF] Manning | Introduction to Information Retrieval[END_REF]. Having a single measure of retrieval quality makes it easier to evaluate the significance of the differences between results. We tested whether the differences in MAP were significant by performing a non-parametric Friedman test, with a significance level of α = .05. We chose the Friedman test because the underlying distribution of the data is unknown and in contrast to an ANOVA the Friedman does not assume a specific distribution of variance. There were significant differences between the runs, χ2 (11, N = 1775) = 2, 618, p < .0001. To determine which of the pairs of measurements differed significantly we conducted a post hoc Tukey HSD test 2 . Opposed to a T-test the Tukey HSD test can be safely used for comparing multiple means [START_REF] Downie | The Music Information Retrieval Evaluation Exchange (2005-2007): A Window into Music Information Retrieval Research[END_REF]. A summary of the analyzed confidence intervals is given in Table 4. Significant and non-significant differences are denoted with +'s and -'s, respectively. The overall retrieval performance of all algorithms on all tasks can be considered good, but there are some large differences between tasks and between algorithms, both in performance and in runtime. With a MAP of .70 the overall best performing setup was the CSAS using triadic chord descriptions and a key relative representation (task 5). The TPSD also performs best on task 5 with an MAP of .58. In tasks 2 and 4-6 the CSAS significantly outperforms the TPSD. On tasks 1 and 3 the TPSD outperforms the CSAS in runtime as well as performance. For these two tasks, the results obtained by the CSAS are significantly lower because local transpositions are not considered. These results show that taking into account transpositions has a high impact on the quality of the retrieval system, but also on the runtime. The retrieval performance of the CSAS is good, but comes at a price. On average over six of the twelve runs, the CSAS runs need about 136 times as much time to complete as the TPSD. The TPSD takes about 30 minutes to 1.5 hours to match all 5028 pieces, while the CSAS takes about 2 to 9 days. Due to the fact that the CSAS run in task 2 takes 206 hours to complete, there was not enough time to perform a run on task 1 and 3 with the CSAS variant that takes local transpositions into account.

In task 6 both algorithms represent the chord sequences as TPS distances to the triad of the key. Nevertheless, the TPSD is outperformed by the CSAS. This difference as well as other differences in performance might well be explained by the insertion and deletion operations in the CSAS algorithm: if one takes two identical pieces an inserts one arbitrary extra chord somewhere in the middle of the piece, an asynchrony is created between the two step functions which has a large effect on the estimated distance, while the CSAS distance only gains one extra deletion score.

For the CSAS algorithm we did a few additional runs that are not reported here. These runs showed that the difference in retrieval performance using different substitution costs (binary, consonance or semi-tones) is limited.

The runs in which a priori key information was available performed better, regardless of the task or algorithm (compare tasks 1 and 4, 2 and 5, and 3 and 6 for both algorithms in Table 4). This was to be expected because there are always errors in the key finding, which hampers the retrieval performance.

The amount of detail in the chord description has a significant effect on the retrieval performance of all algorithms. In almost all cases, using only the triadic chord description for retrieval yields better results than using only the root or the complex chord descriptions. Only the difference in CSAS performance between using complex chords or triads is not significant in task 5 and 6. The differences between using only the root or using the complete chord are smaller and not always significant.

Thus, although colorful additions to chords may sound pleasant to the human ear, they are not always beneficial for determining the similarity between the harmonic progressions they represent. We think there might be a simple explanation for these differences. Using only the root of a chord already leads to good retrieval results, but by removing good information about the mode one looses information that can aid in boosting the retrieval performance. On the other hand keeping all rich chord additional information seems to distract the evaluated retrieval systems. Pruning the chord structure down to the triad might be seen as a form of syntactical noise-reduction, since these additions, if they do not have a voice leading function, have a rather arbitrary character and can only add some harmonic spice.

Concluding Remarks

We performed a comparison of two different chord sequence similarity measures, the TPSD and the CSAS, on a large newly assembled corpus of 5028 symbolic chord sequences. The comparison consisted of six different tasks in which we varied the amount of detail in the chord description and the availability of a priori key information. The CSAS variants outperform the TPSD significantly in most cases, but is in all cases far more costly to use. The use of a priori key information improves performance and using only the triad of a chord for similarity matching gives the best results for the tested algorithms. Nevertheless, we can positively answer the third question that we have asked ourselves in the introduction-do chord descriptions provided a useful and valid abstractionbecause the experiment presented in the previous section clearly shows that chord descriptions can be used for retrieving harmonically related pieces.

The retrieval performance of both algorithms is good, especially if one considers the size of the corpus and the relatively small class sizes (see Table 2), but there is still room for improvement. Both algorithms cannot deal with large structural changes, e.g. adding repetitions, a bridge, etc. A prior analysis of the structure of the piece combined with partial matching could improve the retrieval performance. Another important issue is that the compared systems treat all chords as equally important. This is musicologically not plausible. Considering the musical function in the local as well as global structure of the chord progression, like is done in [START_REF] De Haas | Modeling Harmonic Similarity Using a Generative Grammar of Tonal Harmony[END_REF] or with sequences of notes in [START_REF] Robine | Music Similarity: Improvements of Edit-based Algorithms by Considering Music Theory[END_REF], might improve the retrieval results.

With runtimes that are measured in days, the CSAS is a costly system. The runtimes might be improved by using GPU programming [START_REF] Ferraro | Accelerating Query-by-Humming on GPU[END_REF], or with filtering steps using algorithms such as BLAST [START_REF] Altschul | Basic Local Alignment Search Tool[END_REF].

The harmonic retrieval systems and experiments presented in this paper consider a specific form of symbolic music only. Nevertheless, the application of the methods here presented is not limited to symbolic music and audio applications are currently investigated. Especially the recent developments in chord label extraction are very promising because the output of these methods could be matched directly with the systems here presented. The good performance of the proposed algorithms lead us to believe that also in other musical domains, such as audio, retrieval systems will benefit from chord sequence based matching in the near future.

Fig. 2 .

 2 Fig. 2. The 11-point interpolated precision and recall charts for the TPSD and the CSAS for tasks 1-3, on the left, and 4-6 on the right.

Fig. 3 .

 3 Fig.3. The MAP and Runtimes of the TPSD and the CSAS. The MAP is displayed on the left axis and the runtimes are displayed on an exponential scale on the right axis. On the left side of the chart the key inferred tasks are displayed and the key relative tasks are displayed on the right side.

Table 1 .

 1 A leadsheet of the song All The Things You Are. A dot represents a beat, a bar represents a bar line, and the chord labels are presented as written in the Bandin-a-Box file.

	|Fm7 . . .	|Bbm7 . . .	|Eb7 . . .	|AbMaj7 . . . |
	|DbMaj7 . . . |Dm7b5 . G7b9 . |CMaj7 . . . |CMaj7 . . . |
	|Cm7 . . .	|Fm7 . . .	|Bb7 . . .	|Eb7 . . .	|
	|AbMaj7 . . . |Am7b5 . D7b9 . |GMaj7 . . . |GMaj7 . . . |
	|A7 . . .	|D7 . . .	|GMaj7 . . . |GMaj7 . . . |
	|Gbm7 . . .	|B7 . . .	|EMaj7 . . . |C+ . . .	|
	|Fm7 . . .	|Bbm7 . . .	|Eb7 . . .	|AbMaj7 . . . |
	|DbMaj7 . . . |Dbm7 . Gb7 .	|Cm7 . . .	|Bdim . . .	|
	|Bbm7 . . .	|Eb7 . . .	|AbMaj7 . . . |. . . .	|

Table 2 .

 2 The distribution of the song class sizes in the Chord Sequence Corpus.

	Class Size Frequency Percent
	1	3,253	82.50
	2	452	11.46
	3	137	3.47
	4	67	1.70
	5	25	.63
	6	7	.18
	7	1	.03
	8	1	.03
	10	1	.03
	Total	5028	100

Table 4 .

 4 This table shows for each pair of runs if the mean average precision, as displayed in Figure3differed significantly (+) or not (-).

		Key Inferred				Key Information available
		task1 task2 task3 task1 task2 task3 task4 task5 task6 task4 task5
		TPSD TPSD TPSD CSAS CSAS CSAS TPSD TPSD TPSD CSAS CSAS
	key	task2 TPSD +
	inferred	task3 TPSD -	+
		task1 CSAS +	+	+
		task2 CSAS +	+	+	+
		task3 CSAS +	+	+	+	+
	key	task4 TPSD +	-	+	+	+	+
	information task5 TPSD +	+	+	+	+	+	+
	available	task6 TPSD +	-	+	+	+	+	-	+
		task4 CSAS +	+	+	+	+	+	+	-	-
		task5 CSAS +	+	+	+	+	+	+	+	+	+
		task6 CSAS +	+	+	+	-	+	+	+	+	+	-

The roman numbers here represent the diatonic interval between the key in the ground-truth and the predicted key.

All statistical tests were performed in Matlab 2009a.


David Ralston
email: ralstond@oldwestbury.edu

Serge Troubetzkoy
email: serge.troubetzkoy@univ-amu.fr

RESIDUAL GENERIC ERGODICITY OF PERIODIC GROUP EXTENSIONS OVER TRANSLATION SURFACES

, we show that within each stratum of translation surfaces, there is a residual set of surfaces for which the geodesic flow in almost every direction is ergodic for almost-every periodic group extension produced using a technique referred to as cuts.

Introduction

A translation surface is a real 2-dimensional manifold with conical singularities equipped with an atlas for which transition functions are translations. The simplest example of a compact translation surface is the 2 dimensional torus. It is a classical result that the straight-line flow on the torus satisfies a dichotomy: for rational directions it is completely periodic, while for irrational directions it is uniquely ergodic. There has been considerable work in extending and generalizing this result to other translation surfaces; here we list the major achievements. Veech has shown that this dichotomy hold for any compact translation surface whose group of affine diffeormorphism is a lattice in SL(2, R) [START_REF] Veech | Teichmüller curves in moduli space, Eisenstein series and an application to triangular billiards[END_REF]. Such surfaces are now known as Veech surfaces, this class includes all regular polygons with an even number of sides, with parallel sides identified, as well as compact square-tiled translation surfaces and other examples. Kerckhoff, Masur, and Smillie have shown that on any compact translation surface, the geodesic flow in almost every direction is uniquely ergodic [START_REF] Kerckhoff | Ergodicity of billiard flows and quadratic differentials[END_REF]. Avila and Forni have shown that for almost every compact translation surface of genus at least 2, for almost every direction the geodesic flow is in fact weak-mixing [START_REF] Avila | Weak mixing for interval exchange transformations and translation flows[END_REF].

On the other hand, much less is known for noncompact translation surfaces. For aperiodic infinite translation surfaces, recurrence is known for generic translation surfaces in certain classes [START_REF] Troubetzkoy | Typical recurrence for the Ehrenfest wind-tree model[END_REF][START_REF] Troubetzkoy | Recurrence in generic staircases[END_REF]. A bit more is known for periodic infinite translation surfaces. Hubert, Hooper, and Weiss constructed an example of an infinite translation surface for which the geodesic flow is ergodic in almost every direction [START_REF] Hooper | Dynamics on the infinite staircase[END_REF]. One of the most famous infinite translation surfaces arises from the classical Ehrenfest wind-tree model, introduced by Paul and Tatiana Ehrenfest in 1912 [START_REF] Ehrenfest | The conceptual foundations of the statistical approach in mechanics[END_REF]. Hubert, Lelièvre, and Troubetzkoy, and Avila and Hubert proved the recurrence of the geodesic flow for periodic wind-tree model [START_REF] Hubert | The Ehrenfest wind-tree model: periodic directions, recurrence, diffusion[END_REF][START_REF] Avila | Recurrence for the wind-tree model[END_REF] and the diffusion rate was calculated by Delecroix, Hubert, and Lelièvre to be 2/3 [START_REF] Delecroix | Diffusion for the periodic wind-tree model[END_REF]. Fraçzek and Ulcigrai have shown that the geodesic flow for wind-tree model is not ergodic for almost all directions [START_REF] Fraçzek | Non-ergodic Z-periodic billiards and infinite translation surfaces[END_REF]. In [START_REF] Ralston | Ergodic infinite group extensions of geodesic flows on translation surfaces[END_REF] we showed that for square tiled translation surfaces which have a single cylinder direction, almost every infinite group extensions of geodesic flows produced by cuts is ergodic in almost every direction.

Date: June 16, 2014. This work was partially supported by ANR Perturbations.

In this article we extend this result to the following: there is a residual set of surfaces for which the geodesic flow in almost every direction is ergodic for generic periodic group extensions produced by cuts. The techniques used are the same ones as in [START_REF] Ralston | Ergodic infinite group extensions of geodesic flows on translation surfaces[END_REF]: essential values and approximation by purely periodic directions.

Background and Details of the Construction

A translation surface is a Riemannian surface M , a finite or countable set of points Σ := {x 1 , x 2 , . . . } ⊂ M (the singularity set) and an open cover of M \ Σ by sets {U α }, together with charts φ α : U α → R 2 such that for all α, β with U α ∩U β = ∅ the map φ α • φ -1 β is a translation. The Euclidean metric and Lebesgue measure on R 2 may be pulled back to M via these charts except at singular points x i ∈ Σ with cone angle 2π(d i + 1) for d i ∈ Z + ; this set Σ is finite if M is compact. We denote by µ the pull-back of Lebesgue measure to M (if µ(M ) < ∞, we normalize to that µ(M ) = 1). The collection of all compact translation surfaces with n singularities of cone angles 2π(d i + 1) for i = 1, 2, . . . , n (where the d i are monotone decreasing by convention) is referred to as a stratum, and denoted by H(d 1 , . . . , d n ). Any compact translation surface M may be viewed (in a non unique way) as a polygon (not necessarily convex) in R 2 , where pairs of parallel congruent sides are identified (see e.g. [19, §12]). The precise parameterization of strata that we will use is that of the space of zippered rectangles, which we will define later.

When M is a k-fold cover of the torus ramified over a point, then M is called square-tiled. On each flat surface M we also choose a marked point p in a specified chart U α , and we require only p / ∈ Σ. On M , with the flat metric lifted from the charts, geodesics that do not go through singularities project to straight lines in the plane in a fixed direction, and such geodesics are either periodic or simple (do not intersect themselves). If the geodesic in direction θ starting at x ∈ M does not intersect with Σ then we define the geodesic flow ϕ θ t (x) to the point obtained after moving in the direction θ for a time t starting at x. If θ is fixed, we may simply write ϕ t (x). If the geodesic hits a singularity, then the geodesic flow ϕ t (x) is defined up to this time. The geodesic flow preserves the surface area measure µ. For a survey on translation surfaces, see [START_REF] Viana | Ergodic theory of interval exchange maps[END_REF][START_REF] Zorich | Flat surfaces[END_REF].

We may lift generic points and geodesics from the plane to M ; more precisely consider the marked point p ∈ U α and p ′ := φ α (p) ∈ R 2 Let x ∈ R 2 be arbitrary, and consider the line segment connecting p ′ to x. Let ℓ denote the length of this segment, note that part of this segment is in φ α (U α ). Lift this part to U α and, if possible (i.e. if the procedure does not run into a singularity), continue this line in M until it is of length ℓ, in which case the line segment from p ′ to x on R 2 lifts to a unique geodesic on M . This lift exists for almost all x ∈ R 2 . Definition 1. A collection of cuts γ is a finite collection of pairs of parallel congruent line segments in the plane. Specifically, let N ∈ Z + , and for each i = 1, 2, . . . , N , let

x + i , x - i := (x + i , y + i ), (x - i , y - i ) ∈ R 2 × R 2 be
a pair of points in the plane, ζ i ∈ S 1 , and ℓ i ∈ R + . Denote by γ + i and γ - i the pair of geodesics beginning at the two points x ± i , in direction ζ i and of length ℓ i . All possible finite collections of cuts are parameterized by the σ-finite measure space [START_REF] Aaronson | An introduction to infinite ergodic theory[END_REF] Γ :=

∞ N =1 R 2 × R 2 × S 1 × R + N ,
equipped with Lebesgue measure. We will generally not distinguish between the points x ± i in the plane and their lifts to a surface M , and similarly for the segments γ ± i , allowing us to more easily speak of placing the same collection of cuts on two different surfaces.

Given a compact translation surface M , we will form skew products over M in the following manner: let G be a locally compact Abelian group with translationinvariant metric • , whose identity element we denote e G , and let γ be a collection of N cuts. Lift each segment in γ to M ; if some γ ± i encounters a singularity on M then the lift will not be unique, but there will be only finitely many continuations, and for the time being we may simply make a choice of continuation. Let {g 1 , g 2 , . . . , g N } be a finite set in G. Define f : M → G to take value g i on the lift of each γ + i , value -g i on the lift of γ - i , and value e G elsewhere. Wherever two (or more) lifts of γ i cross, define the function at these points to be the sum of the function on those segments. Given a point x ∈ M and a direction θ which is not equal to any ζ i , denote

(2) S t (x) := S t (x, M, θ) := 0≤s<t f (ϕ θ s (x)) =eG f (ϕ θ s (x)),
and with M and θ fixed,

(3) S -1 t (B ǫ (g)) := {x ∈ M : S t (x)g < ǫ} . Then the transformation φt , from M = M × G to itself, is given by φt (x, g) = (ϕ t (x), g + S t (x)), and it is this continuous time flow which we study; φt preserves the measure μ = µ × ν, where ν is the Haar measure on G. See Figure 1 to see how one single cut γ + i might be appear on a surface with a single-cylinder direction, i.e. a direction θ so that the flow on M in this direction is completely periodic, with all points having the same period h, such that there is an open, connected set which is invariant under the flow in this direction, contains no singularities, and is of full measure. The surface M may thus be represented as a strip with the elements of Σ restricted to the sides parallel to the flow. Geodesics which connect two singularities are called saddle connections.

In order for the flow on M to be ergodic in direction θ, it is necessary that the projection of the cuts to a segment in a direction transverse to θ has an average value of e G (for example, projected to the base of a single-cylinder). Note that by assigning the values ±g i on parallel segments of equal length, we have ensured that this condition is always met.

Definition 2 (Generically ergodic extensions). Suppose that M is a compact translation surface so that for any locally compact Abelian group G, for almost every collection of cuts and almost every θ ∈ S 1 , the flow φθ t on M is ergodic for any choice of values {g 1 , g 2 , . . . , g N } on the cuts which generate a dense subgroup of G. Then M will be said to produce generically ergodic extensions via cuts. Let E be

x + i • ϕ ζi ℓi (x + i ) • • • • • • • • • • • h w θ Figure 1.
The single-cylinder representation for a surface M with completely periodic flow in direction θ with period h, with the flow represented as vertical. The length w = µ(M )/h is called the width of the cylinder. Parallel saddle connections of equal lengths are identified by the letters a through d, and the top and bottom are identified. A sample cut on the surface is the lift of γ + i , beginning at x + i (the lift of (x + i , y + i ) to M ), in direction ζ i and of length ℓ i . A corresponding cut, parallel and of equal length, is the lift of γ - i .

the set of translation surfaces M which produce generically ergodic extensions via cuts.

One central result of [START_REF] Ralston | Ergodic infinite group extensions of geodesic flows on translation surfaces[END_REF] is that if M is a square-tiled surface with a singlecylinder direction, then M ∈ E. It is of interest to know how typical this property is for translation surfaces in general. In this article we are not concerned with answering this question regarding measure-theoretic generic M , but rather we answer the question of topological genericity. In a Baire space Y , a set A ⊆ Y is called G δ if it may be written as the countable intersection of open, dense sets, and A is called residual if it contains a G δ set.

We will work in the space of zippered rectangles; this space was introduced by Veech [START_REF] Veech | Gauss measures for transformations on the space of interval exchange maps[END_REF], and we follow the presentation of Zorich [20, §5.7]. Fix integers d i ≥ 1, and the corresponding stratum H(d 1 , . . . , d n ). Surfaces in this stratum have n singular points, their genus g satisfies n i=1 d i = 2g -2. Fix a translation surface M in this stratum and a direction θ without saddle connections, this direction will be called vertical, the perpendicular direction will be called horizontal. For the rest of this article the term translation surface will correspond to the pair (M, θ). Suppose that X is a horizontal section. The first return map to X is always an interval exchange transformation. We suppose furthermore that X satisfies Convention 2 of [START_REF] Zorich | Flat surfaces[END_REF]: the first return of the vertical flow to X has the minimal possible number

N := (d j + 1) + 1 = 2g + n -1
of subintervals under exchange. Furthermore we will always place the left endpoint of X at a singularity, the convention leaves a discrete choice for the position of the right endpoint. The first return map decomposes M into rectangles: these rectangles together with their identifications are referred to as zippered rectangles.

See Figure 2 for a convex polygon with vertical flow in which we induce the firstreturn flow to a horizontal segment, and Figure 3 for the rearrangement of the figure as a collection of rectangles. The coordinates of zippered rectangle start with the usual coordinates of interval exchange: the widths λ := (λ 1 , . . . , λ N ) of the rectangles (intervals), and the permutation π ∈ S N describing the order of the exchanged intervals. Next we need the heights of h := (h 1 , . . . , h N ) the rectangles, and a := (a 1 , . . . , a N ) the altitudes responsible for the position of the singularities (note that the left endpoint of X starts at a singularity, and the vertical direction does not have any saddle connections, thus it gets mapped to X without hitting another singularity). We zip neighboring rectangles R j and R j+1 from the bottom upto the height a j and then split them. To complete the zipping, neighboring rectangles R π -1 (j) and R π -1 (j+1) are zipped from the top down to the height h π -1 (j)a π -1 (j) .

• • • • • • • • • •
The parameters h j and a j are not independent, they satisfy certain linear equations and linear inequalities (the picture zips up completely, and the zippers do not exceed the top of the rectangles). Continuously varying the parameters λ, h, a while respecting the linear relations yields coordinates in the stratum. Veech showed that given an interval exchange transformation without saddle connections, one can always construct a translation surface M and a horizontal segment X ⊂ M such that that the first return map of the vertical flow to X gives the initial interval exchange transformation. Moreover, there is a n-dimensional family of such flat surfaces, suspensions over the interval exchange transformation. The continuous variation is a completion of the procedure, it includes directions with saddle connections, we will refer to the completion as the boundary of the space of zippered rectangles.

The choice of X completely determines the decomposition, thus one would like a canonical way to choose X. There is an almost canonical way to choose X, namely place the left endpoint of X at one on the singularities and choose the length of X in such a way that X is the shortest interval satisfying Convention 2 and the length of X is at least 1. We will not need to use it, but we remark that there is a constructive way to find X, start with a sufficiently long interval X have its left end point at a singular point and satisfying Convention 2. Apply the "slow" Rauzy induction as long as the resulting interval has length at least one. For almost all flat surface this procedure will stop after a finite number of steps, yielding the desired interval X.

Since M has a finite number of singularities, and each singularity has a finite number of horizontal prongs, this yields

n i=1 (d i + 1) = 2g -2 + n choices for X.
Thus the space of zippered rectangles can be essentially viewed as a ramified covering of the corresponding connected component H comp (d 1 , . . . , d n ) of the stratum. Supposing that the area of the surfaces is one, defined by the condition λ • h = 1 (a final linear equation), yields the space of zippered rectangles of area one covering the space H comp (d 1 , . . . , d n ) of translation surfaces of area one. Slightly abusing notation, we will refer to the space of zippered rectangles as H(d 1 , . . . , d n ). Summarizing, we have shown that the space H(d 1 , . . . , d n ) is the product of a discrete countable parameter, the permutation (Rauzy class) and the closure of an open subset of R 3N (given by the linear equations and linear inequalities), yielding

Lemma 3. Each stratum H(d 1 , . . . , d n ) is a separable, metric Baire space.
Note that if we have a translation surface M and a direction θ which decomposes M into a single cylinder, then this direction on this surface is in the boudary of the space of zippered rectangles since the direction of the flow contains saddle connections). However, for nearby directions θ ′ , the pair (M, θ ′ ) will appear in the interior of the space of zippered rectangles (there are only countably many directions which admit saddle connections in any translation surface). See Figure 5, left. Lemma 4. Within each stratum H(d 1 , . . . , d n ), there is a countable, dense set of (M m , α m ), where M m is compact, square-tiled, and has a single-cylinder direction.

Proof. Lemma 18 and Remark 7 of [START_REF] Kontsevich | Connected components of the moduli spaces of abelian differentials with prescribed singularities[END_REF] show that the set of compact surfaces with single-cylinder directions is dense in each stratum, where denseness is not in the set of zippered rectangles but in the sense of closeness of Abelian differentials. The constructed surfaces have the vertical direction as single-cylinder (which is forbidden in the space of zippered rectangles); we denote this direction as θ.

By making arbitrarily small changes to the vectors of the vertical saddle connections, we ensure that the lengths of all vertical saddle connections are rational multiples of the width of the cylinder without changing the fact that the vertical flow is a single-cylinder direction. By rescaling the width by an arbitrarily small amount, we may ensure all such lengths are in fact rational. We then need only translate all the charts of M by an arbitrarily small amount to ensure that all singularities project to rational coordinates; the surface is now square-tiled with a vertical single-cylinder direction.

Periodic directions correspond to rational directions (now that the singularities all project to rational coordinates), so the flow in any irrational direction will be completely aperiodic. By choosing a direction arbitrarily close to vertical, but still irrational, and labeling this direction as α m , we obtain our countable, dense set. See Figure 4 to see the effect of this minor shear in direction.

In the language of zippered rectangles, we may make arbitrarily small changes to the lengths of the intervals of the base so that the interval exchange is purely periodic, and without loss of generality we may assume that all lengths are rational. By also forcing the heights of the rectangles to be rational, the surface is squaretiled. While this change forbids the surface from the space of zippered rectangles in the vertical direction, which now has saddle connections, an arbitrarily small change to the direction of the flow will remove all saddle connections, so some representation of this surface appears in the space of zippered rectangles.

We will have no further explicit use for the directions α m ; their inclusion is a formality to ensure that our surfaces are proper zippered rectangles. We will generally be more concerned with the single-cylinder direction(s) on M m . In this case we will represent single-cylinder directions as 'vertical' in figures for convenience. As such, we will refer to the zippered rectangle (M m , α m ) simply as M m . Let {M m } be the countable, dense set of surfaces guaranteed by Lemma 4. Comparing the surfaces in Figure 5, the new surface is nearby within the same stratum. The flow in direction θ was periodic for the original surface, and a slight adjustment to the direction of the flow in the new surface will yield a cylinder which is of large measure, periodic in a direction very close to θ, with nearly the same period. These claims (direct from Figure 5) are summarized for convenience in the following lemma. Lemma 5. Let M m0 be some particular surface taken from the countable, dense subset given by Lemma 4, with a single-cylinder direction given by θ. Then for any ǫ > 0, there is some δ > 0 (depending not just on ǫ but also on the choice of θ) such that for any (M ′ , α ′ ) ∈ B δ (M m0 , α m0 ), we have some direction θ * on M ′ for which there is a set A ⊂ M ′ with the following properties:

• A is a periodic cylinder in direction θ * , of period h * and width (measured

perpendicular to θ * ) w * , • µ(A) > (1 -ǫ)µ(M ′ ), • |h -h * | < ǫ min{h, h * } and |w -w * | < ǫ min{w, w * }, • max{h, h * }|θ -θ * | < ǫ min{w, w * }.
That is, the surface (M ′ , α ′ ) ∈ H(d 1 , . . . , d n ) has a direction θ ′ which is very nearly a single-cylinder direction: the representation of the flow in direction θ ′ is closely approximated by the single-cylinder direction θ on the surface M m0 .

We now are ready to state our main result:

Theorem 1 (Residual Generic Ergodicity). For each H(d 1 , . . . , d n ), E is residual within H(d 1 , . . . , d n ): there is a dense G δ set of surfaces for which the skew product formed with almost-every collection of cuts is ergodic in almost-every direction.

Proof of Residual Generic Ergodicity

Lemma 6. Let {P, µ} be a σ-finite measure space, and let Y be a separable metric Baire space such that {y i } (i = 1, 2, . . .) is dense in Y . Assume that there is a measurable function ǫ(i, k, ψ) :

Z + × Z + × P -→ R + . Define the sets A ψ = ∞ k=1 ∞ i=1 B ǫ(i,k,ψ) (y i ),
where B ǫ (y) ⊂ Y is the open ball of radius ǫ centered at y. Then the set

A = {y ∈ Y : µ ({ψ ∈ P : y / ∈ A ψ }) = 0}
is residual.

Proof. Note that the A ψ are dense G δ sets. Without loss of generality, we may assume that µ(P) = 1; if the result holds in this circumstance, then the assumption that {P, µ} is σ-finite and the fact that a countable intersection of residual sets in a Baire space is residual completes the proof. It then suffices to prove that for all δ > 0, the set

A(δ) = {y ∈ Y : µ ({ψ ∈ P : y ∈ A ψ }) ≥ 1 -δ} is residual; if this is shown, then we may intersect A(1/n) for n = 1, 2, . . .. So let δ > 0.
For each i and k, define ǫ * (i, k) > 0 so that

µ ({ψ ∈ P : ǫ(i, k, ψ) < ǫ * (i, k)}) ≤ δ • 2 -k .
Then the set

A * = ∞ k=1 ∞ i=1 B ǫ * (i,k) (y i )
is a dense G δ set. Let y ∈ A * . Then for each k, there is some i so that y ∈ B ǫ * (i,k) (y i ), which implies that

µ {ψ ∈ P : y / ∈ B ǫ(i,k,ψ) (y i )} ≤ δ • 2 -k .
By intersecting the above over k = 1, 2, . . ., we have µ(

A * ) ≥ 1 -δ, or A * ⊆ A(δ).
That is, if for almost every parameter ψ the set A ψ is residual, then there is a residual set of y which belong to almost-every A ψ . It is quite important that the set {y i } (the centers of the balls) be invariant with respect to different ψ ∈ P; otherwise, the result may not hold. For example, one may readily construct secondcountable Y and {P, µ} a probability space so that for almost every ψ ∈ P there is some associated residual set A ψ ⊂ Y , but for every y ∈ Y , µ (ψ ∈ P : y ∈ A ψ ) = 0.

Our σ-finite parameter space in applying Lemma 6 will be

P = S 1 × Γ,
where Γ was given in [START_REF] Aaronson | An introduction to infinite ergodic theory[END_REF]. A point in this space corresponds to a choice of direction θ for geodesic flow φt , combined with a collection of cuts γ ∈ Γ. Our Baire space Y will be a stratum of translation surfaces (Lemma 3).

Let the stratum H(d 1 , . . . , d n ) be fixed, and denote by {M m } the countable, dense collection of square-tiled translation surfaces which admit some single-cylinder direction from Lemma 4. Lemma 7. For almost-every direction θ, for each M m there is a sequence {θ n } of single-cylinder directions of period h n and width w n on M m such that

(4) lim n→∞ h n w n θ n -θ = 0.
Proof. As there are only countably many M m , it suffices to prove the claim for a single M m , which follows from [13, Lemma 2.6].

We recall [13, Def. 3.1] and strengthen: Definition 8. Let M be a fixed compact translation surface which has a dense set of single-cylinder directions, let θ be some direction, and let D be a finite subset of M . We will say that the set D is uniformly self-avoiding in direction θ if there is a sequence of single-cylinder directions θ n → θ such that for each d ∈ D there is a subsequence θ nj , along which we may place d at the center of an invariant subset of the single cylinder, the complement of which tends towards zero measure, which contains no singularities of M and no other points of D. See Figure 6. The two sides of this set, separated by the orbit of d, are called the left and right halves of the orbit neighborhoods of d.

θ nj • d L j R j h nj Figure 6.
By assumption the only element of the set D not within the gray region is the point d, which may then be placed in the center of a sub-cylinder of large measure which avoids all singularities and all other elements of D. As j → ∞ the grayedout region tends to zero measure, and thus d tends towards the center of the cylinder. The remaining sub-cylinders are called orbit neighborhoods of d, with left and right halves L j and R j .

Lemma 9. For any N ∈ N, almost every choice of N points in the plane lifts to every M m as a uniformly self-avoiding set. Furthermore, if M m0 is fixed, and θ is an irrational direction which admits a sequence {θ n } of single-cylinder directions (with periods h n ) which satisfies Equation 4, then for each d in this self-avoiding set, if we pass to the subsequence n j from Definition 8 and denote the left and right halves of a sequence of orbit neighborhoods corresponding to d by L j and R j , then we have subsets

L * j ⊂ L j , R * j ⊂ R j such that as j → ∞, • µ(L * j ) → (1/2)µ(M m0 ), • sup x∈L * j ϕ θ hn j (x) -x → 0, • for any fixed t 0 ∈ R + , µ ϕ θ t0 L * j △L * j → 0,
and similarly for R * j . Proof. Note that the flows are in direction θ, not θ nj . For the first claim, as there are countably many M m , it suffices to prove that almost every choice of N points lifts to any particular M m0 as a uniformly self-avoiding set. We rescale a fixed M m0 to be a k-fold cover of the unit square and denote the affine image of θ n by p n /q n (periodic directions on covers of the unit square must be rational). Single cylinders therefore have width 1/q n and height kq n for some fixed k ∈ Z + . The first claim now follows from [START_REF] Kuipers | Uniform distribution of sequences[END_REF]Thm 4.1]: for any sequence q n → ∞, for almost every x we have the sequence kq n x uniformly distributed modulo one. So if there are N points d 1 , d 2 , . . . , d N , let π x (d i ) be the x-coordinate of the projection to the plane. So for each i ′ ∈ {1, 2, . . . , n} we can create a subsequence p nj /q nj such that modulo 1 q nj π x (d i ′ ) tends towards 1/2 as j → ∞ (and therefore d i ′ is arbitrarily close to the center of the cylinder) while modulo 1 every other i = i ′ , q nj π x (d i ) tends to either zero or one (and therefore all other d i are arbitrarily close to the boundary of the cylinder). Now let d be an element of a uniformly self-avoiding set. We form the sets L * j and R * j by removing a small neighborhood of the orbit of d (in the direction θ). See Figure 7. Using Equation 4and Definition 8, we see that L * j and R * j will tend to half of the total measure. That the sets are nearly invariant under the flow in direction θ (pointwise through time h nj and as a set through any fixed time t 0 ) follows from Equation 4and the fact that h nj is diverging, respectively: the flow for any fixed t 0 will produce a negligible change in either L * j or R * j . Compare to [START_REF] Ralston | Ergodic infinite group extensions of geodesic flows on translation surfaces[END_REF]Cor. 3.4]. In that result only a specific square-tiled surface was considered, so any positive measure for the sets L, R sufficed. We have strengthened that approach to provide the same positive limiting measure for the sets L * j and R * j for every M m .

Corollary 10. For almost every collection of cuts γ ∈ Γ, the lift of γ to each M m is unique, and for almost every direction θ the starting points x ± i of the segments of the lift of γ are a uniformly self-avoiding set in the direction θ on every M m .

Proof. Uniqueness of the lift of γ to each M m merely requires that the geodesic from p ′ , the projection of the marked point p ∈ M m0 , to each (x ± i , y ± i ), as well as the line segments originating from these points, not encounter a singularity when lifted to M . As there set of singularities is of zero measure (it is finite), generic cuts lift uniquely to each M m .

It follows from [START_REF] Patterson | Diophantine approximation in Fuchsian groups[END_REF][START_REF] Sullivan | Disjoint spheres, approximation by imaginary quadratic numbers, and the logarithm law for geodesics[END_REF] (see also [START_REF] Ralston | Ergodic infinite group extensions of geodesic flows on translation surfaces[END_REF]Lemma 2.6]) that for any fixed M m0 , almost every θ admits a sequence {θ n } as in Lemma 9, so for each M m , for almost every θ we have that almost every collection of cuts lifts to M m uniquely (as outlined above) and with endpoints which are a uniformly self-avoiding set in direction θ. Fubini's theorem allows us to rephrase: almost every collection of cuts lifts uniquely as a self-avoiding set to any fixed M m0 in almost-every direction. Since the collection {M m } is countable, it follows that almost every collection of cuts lifts to a uniformly self-avoiding set on every M m in almost every direction. Definition 11. We call the pair (γ, θ) generic if it satisfies the conclusion of Corollary 10.

To summarize our progress so far: we have a countable, dense collection of surfaces M m in each stratum. For almost-every direction θ, each one of these surfaces has a sequence of single-cylinder directions converging in a very strong manner to θ. For almost-every collection of cuts, for each starting point of each cut, on each M m we may pass to a subsequence of these directions which isolates that starting point from the orbits of every other starting point in a uniform manner. We will now show how this isolation of starting points of the cuts leads to ergodic skew products.

An essential value of the skew product { M , μ, φt } is a g ∈ G such that for any set A ⊂ M of positive measure and ǫ > 0 there is a t > 0 such that (recall (3))

µ A ∩ ϕ t (A) ∩ S -1 t (B ǫ (g)) > 0.
The set of essential values forms a closed subgroup of G, and the skew product is ergodic if and only if the flow {M, µ, ϕ t } is ergodic and the set of essential values is all of G (see e.g. [START_REF] Aaronson | An introduction to infinite ergodic theory[END_REF]). Clearly, for { M , μ, φt } to be ergodic it is necessary that the values f takes on the cuts to generate a dense subgroup of G. Our technique for finding essential values is the following:

Lemma 12. Suppose that M is a translation surface with geodesic flow {M, µ, ϕ t } in some direction θ, with a collection of cuts γ and corresponding skew product { M , μ, φt }. For j = 1, 2, . . ., assume we have times t j → ∞ and sets L * j such that • L * j contains no singularities of M and no endpoints of any cut,

• lim µ(L * j ) = (1/2)µ(M ), • sup x∈L * j ϕ θ tn (x) -x → 0, • for any fixed t 0 ∈ R + , µ L * j △ϕ θ t0 L * j → 0, and • for all x ∈ L * j , S tj (x) = f (γ i ).

Then the skewing values ±g

i = f (γ ± i ) taken on the cuts γ ± i are essential values of { M , μ, φt }.
Proof. Note that we have required the ergodic sums S tj (x) to be constant on each L * j and R * j , which each form a sequence of quasi-rigidity sets [13, Def. 2.1], and we directly have each of ±g i as essential values by applying [START_REF] Ralston | Ergodic infinite group extensions of geodesic flows on translation surfaces[END_REF]Lemma 2.2].

θ nj • d L * j R * j Figure 7.
The flow in direction θ is slightly skewed compared to direction θ nj , but sufficiently close to allow for the construction of the sets L * j and R * j , each of measure very nearly one half the total measure.

Compare to Lemma 9 and Figure 7: the last condition in Lemma 12 is the last remaining condition to verify in order to begin producing essential values for our skew products.

Lemma 13. Fix generic (γ, θ) ∈ Γ × S 1 , and let f : γ → G, where G is a locally compact Abelian group. Then for each M m0 we have that for each γ ± i with value f (γ ± i ) we may pass to a subsequence {θ nj } of single cylinder directions so that we may find a sequence of sets L * j to satisfy Lemma 12.

Proof. The proof is a slightly more refined application of the same use of [START_REF] Kuipers | Uniform distribution of sequences[END_REF]Thm. 4.1] that we used in Lemma 9. Pick a generic (γ, θ), and let M m0 be fixed. From Lemma 7 we obtain a sequence θ n of single-cylinder directions on M m0 converging to θ. For each pair of cuts γ ± i , in direction ζ i and with length ℓ i , project the length of γ i in the direction θ and denote this projected length π(ℓ i ). Let w n be the width of the single-cylinder on M m0 in direction θ n .

Pick a particular pair of cuts γ ± i ′ . From Lemma 9, let us assume without loss of generality that our sequence θ n already isolates the starting point

x + i ′ of γ + i ′
from the starting point of every other cut (including x - i ′ ). For each i = i ′ (and x - i ′ ), we pass to successive subsequences to guarantee that the endpoints of the cuts γ ± i are also forced to be near the boundary of the cylinders. More precisely we require that (π(ℓ i )/w nj ) mod 1 converges to zero/one as j → ∞, i.e. the cuts γ ± i cross the cylinders very nearly an exact integer number of times. As the projected length π(ℓ i ) is equal for both γ + i and γ - i this subsequence automatically isolates the endpoint of γ - i near the boundary as well. Since there are only finitely many i = i ′ , we may presume, then, that every cut other than γ i ′ has this property: both endpoints of each γ ± i are trapped near the boundaries of the cylinders. So now consider the chosen pair of cuts γ ± i ′ , with starting points x ± i ′ . Since we began with a subsequence of directions according to Definition 8, we have that x + i ′ is placed near the centers of the cylinders, and x - i ′ is trapped near the boundary along with all the other starting points. Since the length ℓ i ′ of this particular pair of cuts was chosen generically, by passing to a subsequence once more we may force the endpoint ϕ

ζ i ′ ℓ i ′ (x +
i ′ ) to be trapped near the boundary of the cylinder. Equivalently, we may generically force (π(ℓ i ′ )/w nj ) mod 1 to converge to 1/2: the length of this cut traverses the cylinders very nearly an integer number of times, plus one half.

So for i = i ′ , the cuts begin very near the boundary of the single cylinders and are of length (projected to direction θ, which is very near to the directions θ nj ) very nearly an integer times the width of the cylinder. Away from the boundary of the cylinder, then, the ergodic sums of any point flowing the height of the cylinder see no contribution from the cut γ ± i ! As the pair of cuts γ ± i are of equal length, they must traverse the cylinder an equal number of times. Since we have f (γ - i ) = -f (γ + i ), the net effect is that these cuts do not contribute to the ergodic sums for most points in this direction through the height of the cylinder.

For the remaining cut γ ± i ′ , the endpoint of γ + i ′ is very near the boundary of the cylinder, while the endpoint of γ - i ′ is very near the middle of the cylinder (a reversal of the placement of the starting points x ± i ′ , as the projected length π(ℓ i ′ ) is very nearly an integer-plus-one-half times the width of the cylinder). So we find that the ergodic sums neatly split the cylinder; away from the boundary and away from the middle, the only two values seen are exactly g i ′ = f (γ i ′ ) on the right half of the cylinder and -g i ′ = -f (γ i ′ ) on the left. See Figure 8; the sets L * j and R * j are obtained from this representation in the same way as in Figure 7.

θ n x - i ′ x + i ′ • • • • -g i ′ g i ′ Figure 8.
For generic cuts and generic directions, on each particular M m0 we may pass to a subsequence of single-cylinder directions on which the cuts traverse the single cylinder in a regular manner. All cuts other than a chosen γ ± i ′ have both endpoints restricted near the boundary and therefore contribute nothing to the ergodic sums in the cylinder, while the chosen cut γ ± i ′ splits the cylinder into two halves with very precise ergodic sums.

We finally turn to the question of the appropriate ǫ to use as the radius of the balls in constructing our G δ sets to complete the proof of Theorem 1. Let ψ = (θ, γ) ∈ P be generic in the sense that all generic results proved up to this point hold simultaneously (Lemma 7, Lemma 9, Corollary 10, Lemma 12, and Lemma 13).

Let k be a fixed positive integer, and fix some M m0 . For each d, an endpoint of a cut, we have a sequence of single-cylinder directions θ n according to Lemma 9. We may therefore find some single-cylinder direction θ nj on M m0 which produces two orbit-neighborhoods L * j and R * j according to Figure 7 such that each has measure at least (k -1)/2k and each is of height at least k. Fix this choice of single-cylinder direction θ nj (which depends not only on m 0 and θ, but also k).

We let ǫ(m 0 , k, d) > 0 be small enough (recall Lemma 5, making the size of the balls in the stratum smaller if necessary) that any surface within ǫ(m 0 , k) of each (M m0 , α m0 ) satisfies:

(1) the lift of γ to all nearby M in this neighborhood will be unique, (2) excluding a set of measure at most µ(M )/k, there is a periodic cylinder in direction θ ′ of period h ′ such that max (h, h ′ ) • |θ njθ ′ | < w/(2k) for all points in this cylinder, where w is the width of the cylinder. See Figure 5, right. (3) for those x ∈ M of within this large set and also not within distance w/(2k) of any lift of a cut, we have

S h ′ (x, M, θ) = S h ′ (x, M, θ ′ ) = S h (x, M m0 , θ nj ) = S h (x, M m0 , θ),
where x denotes the lift to M m0 of the projection of x ∈ M to the plane, and θ nj is a single-cylinder direction on M m0 very near θ. Informally, point-by-point these conditions amount to:

(1) varying the edges of the polygon will not cause any cut to cross a singularity, (2) the flows in the two directions θ and θ ′ through times h or h ′ are more-orless indistinguishable for most points, and also virtually indistinguishable from the single-cylinder direction θ nj , and (3) for most of the surface M , the ergodic sum through time h ′ in direction θ is identical to the ergodic sum through time h in direction θ of the corresponding point on M m0 .

The equality in the last item is accomplished by starting with M m0 in direction θ, approximating by a single-cylinder direction θ nj , choose a surface in the ǫ-ball around M m0 by making small adjustments to the vectors which define the saddle connection in direction θ nj to form the surface M , finding a cylinder of large measure on the resulting surface in direction θ ′ , and then returning the flow to direction θ. At each stage, ergodic sums are maintained pointwise except on sets of arbitrarily small measure, according to the diameter of the ball used.

Having chosen the cuts γ and the direction of the flow θ, we therefore have a small ball around M m0 for which any surface in that ball is very closely approximated by the single-cylinder direction θ nj on M m0 , at least through time h nj ≥ k. As k increases, the strength of this approximation necessarily improves in two ways: increasing height of the cylinders forces θ nj → θ, and the measure of the orbit neighborhoods which directly transfer to any M in the ball is tending towards 1/2. So with m 0 fixed, for each k and each endpoint of each cut d, we obtain an allowable radius ǫ(m 0 , k, d). Define ǫ(m 0 , k, ψ) to be the minimum of these radii across the finite number of endpoints of the cuts (recall the original dependence on ψ, the collection of cuts and the direction of geodesic flow).

Let

A ψ = (E(θ)) ∩ k∈N i∈N B ǫ(i,k,ψ) (M m , α m ) ,
where E(θ) is the set of M for which the flow in direction θ is ergodic, and θ was the direction of geodesic flow specified in ψ.

Lemma 14. Let M ∈ A ψ , and let M = M × G with geodesic flow in direction θ defined as the skew product over M given by [START_REF] Avila | Recurrence for the wind-tree model[END_REF]. Then the geodesic flow on M in direction θ is ergodic.

Proof. The set E(θ) is residual in each stratum for any θ [9, Corollary 2], so A ψ is residual as well. For M ∈ A ψ , then, the flow in direction θ is ergodic. It remains to show that each value g ∈ G which is the value assigned to some cut is an essential value of the flow { M , μ, φt }; since these values generate a dense subgroup of G, this finding will complete the proof. Pick an arbitrary g ∈ {g 1 , . . . , g N } (the values taken on the cuts), and let x + i be the starting point of a cut which takes value g. Create a sequence of approximations as in Figure 9. By construction, as M ∈ A ψ , we have a sequence of single-cylinder surfaces M m with corresponding representations as in Figure 9, from which we may pull back to M a set of measure arbitrarily close to 1/2 on which we have ergodic sums constantly equal to g; via Lemma 13 the ergodic sums on the corresponding

• x = ϕ θ ′ h ′ (x) • • • • • • • • • • Figure 9.
If M is sufficiently close to M m0 , then 'most' of M looks like a single cylinder (all but the dark-gray region, as in Figure 5 (right) and Figure 6), and the cuts are in almost the same place, with the same number of crossings, so that for 'most' of this periodic cylinder (now also excluding the light-gray regions) the ergodic sums are identical to corresponding points on M m0 (as in Figure 8).

sets in M m are constant, and our balls were picked small enough that most of these sets transfer to M without affecting the ergodic sums. The value g, then, is an essential value of the flow in direction θ on M (Lemma 12). Since the choice of g was arbitrary and we assumed that {g 1 , . . . , g N } generate a dense subgroup of G, it follows that the flow on M in direction θ is ergodic.

So for any generic choice of direction θ and cuts γ, we form a residual set of surfaces M for which the skew product transformation on M is ergodic in direction θ. By applying Lemma 6, this completes the proof of Theorem 1.

Figure 2 .Figure 3 .

 23 Figure 2. A polygon (e.g. a decagon) with pairs of parallel sides defines a translation structure (side identifications are marked).By defining a segment transverse to the vertical flow, we define a first-return map to this segment.

Figure 4 .Figure 5 .

 45 Figure 4. The zippered rectangle representation where the vertical direction α m has no saddle connections and is close to the original single-cylinder direction θ. Parallel saddle connections of equal lengths are identified by the letters a through d, and the top and bottom are identified via an interval exchange.