Enumerating Inclusion-Maximal Arithmetic Progressions

Abstract

We present a simple $\mathcal{O}\left(n^2\frac{\log N}{\log \log N}+N\right)$ enumeration algorithm for solving a problem from mathematical and computational music analysis where, given a strictly increasing integer sequence, $S$, with $n$ entries and maximum value $N$, the task is to enumerate all $m$ $\text{inclusion-maximal arithmetic progressions (IMAPs)}$ in this sequence. An IMAP is a subsequence, $S^{\prime }\subseteq S$ with $k>2$ integers, in which (i) the difference between any two consecutive integers is the same number, $d$ (i.e., $S^{\prime }$ is an $\text{arithmetic progression}$), (ii) $S^{\prime }$ cannot be further extended to the left or to the right with any additional integers from $S$ while still remaining an arithmetic progression (i.e., $S^{\prime }$ is a $\text{maximal}$ arithmetic progression), and (iii) there is no other maximal arithmetic progression, $S^{\prime \prime }\subseteq S$, which $\text{properly}$ contains $S^{\prime }$ (i.e., $S^{\prime }$ is an $\text{inclusion-maximal}$ arithmetic progression). We further provide proofs for the expected number of IMAPs in random integer sequences, $S$, and a bound on their order of growth. Finally, we provide empirical experiments comparing both (a) the practical running time performance of the proposed algorithm against that of a previously known algorithm which has higher time complexity $\mathcal{O}(N^{2+o(1)}n)$, and (b) the actual enumerated number of IMAPs to that of their mathematically expected number. Notably, the proposed algorithm demonstrates a significant improvement in running time over the previously known algorithm, and in immediate practical applications, will allow for more efficient analysis of large and rhythmically complex musical pieces.