Pith. sign in

REVIEW 2 major objections 2 minor 25 references

Enumerating Inclusion-Maximal Arithmetic Progressions

T0 review · 2 major / 2 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A new algorithm enumerates all inclusion-maximal arithmetic progressions in a sequence of n integers up to N in O(n² log N / log log N + N) time.

desk verdict The paper gives a concrete faster algorithm for listing inclusion-maximal APs plus new expected-count proofs, but the full proofs and experiment details need checking. read the letter →

arxiv 2606.11067 v1 pith:7AHH5R3H submitted 2026-06-09 cs.DS

Brian Bemman , Maximilien Gadouleau , Oliver W. Gnilke , George B. Mertzios This is my paper · ORCID
classification cs.DS
keywords arithmeticprogressionsenumerationalgorithminclusion-maximalmusicanalysiscomputationalcomplexityrandomsequences
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper presents an enumeration algorithm for inclusion-maximal arithmetic progressions in strictly increasing integer sequences. Given S with n entries and maximum N, it lists every IMAP in the claimed time bound. This bound improves on a prior algorithm running in O(N^{2+o(1)} n). The authors also prove the expected number of IMAPs in random sequences along with a growth bound, and they report experiments that compare both running times and observed counts against the theoretical expectations.

What carries the argument

An enumeration procedure that scans candidate arithmetic progressions by common differences, checks left and right extensions within S, and discards any progression properly contained in another maximal one.

What would settle it

Execute the algorithm on the sequence 1,3,5,7,9 and check whether the output contains exactly the single IMAP consisting of all five terms and no other.

Watch

Extended reading notes

Core claim

The central claim is an algorithm that, for any strictly increasing integer sequence S of length n with largest entry N, enumerates every inclusion-maximal arithmetic progression in O(n² log N / log log N + N) time while also establishing the expected number of such progressions under a uniform random model and a bound on their order of growth.

Load-bearing premise

The input sequence must be strictly increasing, and the maximality and inclusion checks must return exactly the inclusion-maximal progressions without omissions or duplicates.

Editorial extensions

If this is right

  • The algorithm supports faster processing of large rhythmically complex musical pieces than the earlier O(N^{2+o(1)} n) method.
  • The number of IMAPs in a random sequence of length n with maximum N obeys a stated expectation and growth bound.
  • Empirical counts of IMAPs match the derived mathematical expectations on the tested instances.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same enumeration structure could be applied to strictly increasing sequences arising in other ordered domains such as event timestamps.
  • If the maximality test can be relaxed, the approach might extend to approximate or near-arithmetic progressions.
  • The additive N term suggests that preprocessing the range up to N is a bottleneck that further data structures might reduce.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The manuscript presents a simple O(n² log N / log log N + N) enumeration algorithm for all inclusion-maximal arithmetic progressions (IMAPs) in a strictly increasing integer sequence S of length n with maximum entry N. An IMAP is defined as a subsequence that forms an arithmetic progression with common difference d, is maximal (cannot be extended left or right within S), and is inclusion-maximal (not properly contained in another maximal AP). The paper supplies proofs of the expected number of IMAPs under random sequences and a bound on their order of growth, plus empirical runtime comparisons against a prior O(N^{2+o(1)}n) algorithm and comparisons of observed versus expected IMAP counts.

Significance. If the correctness proof and complexity analysis hold, the result supplies a faster practical tool for enumerating IMAPs with direct application to rhythm analysis in computational musicology. The explicit proofs of expected counts together with the reproducible empirical validation against both theory and a baseline algorithm constitute a clear strength; the improved asymptotic and observed running time would enable scaling to larger musical corpora.

major comments (2)
  1. [§4] §4 (Complexity Analysis), the derivation of the O(n² log N / log log N + N) bound: the analysis must explicitly account for the cost of the inclusion-maximality test performed after candidate generation; if this test is implemented via a linear scan over previously found APs it could introduce an extra m factor that is not absorbed by the stated bound.
  2. [§5] §5 (Expected Number Proof), Theorem 1: the claimed expectation for the number of IMAPs in a random sequence relies on an independence assumption across possible differences d; the proof should state the precise probability model (uniform random subset or random permutation) and verify that the maximality condition does not introduce dependence that invalidates the closed-form expectation.
minor comments (2)
  1. [§6] The experimental section should report the precise generation method for the random test sequences (e.g., uniform sampling of n distinct integers from 1..N) and the number of trials used to compute average runtimes and IMAP counts.
  2. Notation: the variable m (number of IMAPs) is introduced in the abstract but never appears in the complexity statement; clarify whether the algorithm’s running time is independent of m or whether an output-sensitive term is omitted.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and for identifying points that can strengthen the presentation. We address each major comment below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [§4] §4 (Complexity Analysis), the derivation of the O(n² log N / log log N + N) bound: the analysis must explicitly account for the cost of the inclusion-maximality test performed after candidate generation; if this test is implemented via a linear scan over previously found APs it could introduce an extra m factor that is not absorbed by the stated bound.

    Authors: We agree that §4 should explicitly bound the inclusion-maximality test. The manuscript describes the test but does not separately analyze its cost. If implemented via a naïve linear scan, an extra factor linear in the number of previously reported APs could appear. We will revise the analysis to show that the test can be performed in amortized O(1) time per candidate using a suitable hash-based data structure on the generated APs, keeping the overall bound unchanged. The revised §4 will contain the updated derivation. revision: yes

  2. Referee: [§5] §5 (Expected Number Proof), Theorem 1: the claimed expectation for the number of IMAPs in a random sequence relies on an independence assumption across possible differences d; the proof should state the precise probability model (uniform random subset or random permutation) and verify that the maximality condition does not introduce dependence that invalidates the closed-form expectation.

    Authors: The proof in §5 models S as a uniformly random strictly increasing sequence of length n drawn from {1,…,N}. We acknowledge that the current write-up invokes an independence assumption across differences d without a detailed justification. We will revise Theorem 1 and its proof to (i) state the probability space explicitly and (ii) bound the dependence introduced by the maximality conditions, showing that the expectation remains asymptotically the same as the closed-form expression given in the manuscript. The revised proof will appear in the next version. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation is self-contained algorithmic construction

full rationale

The paper presents an enumeration algorithm whose time bound and correctness rest on explicit checks for maximality and inclusion in strictly increasing sequences, together with separate mathematical proofs of expected IMAP counts and empirical runtime comparisons. No equation or claim reduces a derived quantity to a fitted parameter, self-referential definition, or load-bearing self-citation; the expected-count proofs and complexity analysis are independent of the algorithm's output values. The contribution therefore contains no circular steps of the enumerated kinds.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

Review performed on abstract only; the main domain assumption is the strictly increasing integer input format. No free parameters, invented entities, or additional axioms are identifiable from the given text.

assumptions (1)
  • domain assumption Input is a strictly increasing integer sequence with n entries and maximum value N.
    Explicitly stated as the problem input in the abstract.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Enumerating Inclusion-Maximal Arithmetic Progressions." pith.science (2026). https://pith.science/paper/7AHH5R3H

@misc{pith2026260611067,
  author       = {Pith},
  title        = {Pith review of: Enumerating Inclusion-Maximal Arithmetic Progressions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7AHH5R3H}},
  note         = {Machine review of arXiv:2606.11067}
}
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$ $\textit{inclusion-maximal arithmetic progressions (IMAPs)}$ in this sequence. An IMAP is a subsequence, $S' \subseteq S$ with $k>2$ integers, in which (i) the difference between any two consecutive integers is the same number, $d$ (i.e., $S'$ is an $\textit{arithmetic progression}$), (ii) $S'$ 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'$ is a $\textit{maximal}$ arithmetic progression), and (iii) there is no other maximal arithmetic progression, $S'' \subseteq S$, which $\textit{properly}$ contains $S'$ (i.e., $S'$ is an $\textit{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.

Figures

Figures reproduced from arXiv: 2606.11067 by the authors.

Figure 1
Figure 1. Experiment 1: Average number of inclusion-maximal arithmetic progressions (IMAPs) in (a) and average running times in seconds to enumerate them using Alg. 1 (red triangles, solid line) and Alg. 2 (blue diamonds, solid line) in (b) for strictly increasing integer sequences of varying length, 𝑛, drawn uniformly at random without replacement from (0. . 𝜆𝑛], ∀𝑛 ∈ {1000, 2000, … , 20000} and where 𝜆 = 2.5. In (b), Alg. 1… view at source ↗
Figure 2
Figure 2. Log-log plot with linear regression fitted lines of the average running times taken from Experiment 1 (shown in [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. Experiment 2: Average number of inclusion-maximal arithmetic progressions (IMAPs) in (a) and average running times in seconds to enumerate them using Alg. 1 (red triangles, solid line) and Alg. 2 (blue diamonds, solid line) in (b) for strictly increasing integer sequences of fixed length, 𝑛 = 10, 000, drawn uniformly at random without replacement from (0. . 𝜆𝑛], ∀𝜆 ∈ {1.0, 1.2,… , 10.0}. In (b), Alg. 1opt (red trian… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Experiment 3: The number of inclusion-maximal arithmetic progressions (IMAPs) enumerated by Alg. 2 (blue lines) and expected number of IMAPs (black circles) as calculated in section 5.2.1 for strictly increasing integer sequences of varying length, 𝑛, drawn uniformly a…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 3 canonical work pages

  1. [1]

    Constraint programming systems for modeling music theories and composition

    Anders, T., Miranda, E.R., 2011. Constraint programming systems for modeling music theories and composition. ACM Computing Surveys (CSUR) 43, 1–38

    2011

  2. [2]

    Inner Metric Analysis as a measure of rhythmic syncopation, in: 2024 ISMIR 24th Annual International Symposium of Music Information Retrieval, ISMIR, San Franciso, CA, U.S.A

    Bemman, B., Christensen, J., 2024. Inner Metric Analysis as a measure of rhythmic syncopation, in: 2024 ISMIR 24th Annual International Symposium of Music Information Retrieval, ISMIR, San Franciso, CA, U.S.A.. pp. 389–396

    2024

  3. [3]

    Backtrackingsearchheuristicsforsolvingtheall-partitionarrayproblem.,in:The20thInternationalSociety for Music Information Retrieval Conference, ISMIR, Delft, Netherlands

    Bemman,B.,Meredith,D.,2019. Backtrackingsearchheuristicsforsolvingtheall-partitionarrayproblem.,in:The20thInternationalSociety for Music Information Retrieval Conference, ISMIR, Delft, Netherlands. pp. 391–397

    2019

  4. [4]

    An improvement to the Kelley-Meka bounds on three-term arithmetic progressions

    Bloom, T.F., Sisask, O., 2023a. An improvement to the Kelley-Meka bounds on three-term arithmetic progressions.arXiv:2309.02353

    work page Pith review arXiv

  5. [5]

    The Kelley–Meka bounds for sets free of three-term arithmetic progressions

    Bloom, T.F., Sisask, O., 2023b. The Kelley–Meka bounds for sets free of three-term arithmetic progressions. Essential Number Theory 2, 15–44

  6. [6]

    Multiple Mertens theorems for arithmetic progressions.arXiv:2512.07336

    Chen, Z., Luo, J., 2025. Multiple Mertens theorems for arithmetic progressions.arXiv:2512.07336

    work page arXiv 2025

  7. [7]

    Dance music classification using Inner Metric Analysis, in: Golden, B., Raghavan, S., Wasil, E

    Chew, E., Volk, A., Lee, C.Y., 2005. Dance music classification using Inner Metric Analysis, in: Golden, B., Raghavan, S., Wasil, E. (Eds.), The Next Wave in Computing, Optimization, and Decision Technologies, Springer US, Boston, MA. pp. 355–370

    2005

  8. [8]

    De Haas, W.B., Volk, A., 2016. Meter detection in symbolic music using Inner Metric Analysis, in: Proceedings of the 17th International Society for Music Information Retrieval Conference, ISMIR, New York, NY, U.S.A.. pp. 441–447

    2016

Show all 25 references
  1. [9]

    Finding longest arithmetic progressions

    Erickson, J., 1999. Finding longest arithmetic progressions. University of Illinois at Urbana-Champaign

    1999

  2. [10]

    Arithmetic progressions at the journal of the LMS

    Green, B., 2026. Arithmetic progressions at the journal of the LMS. Journal of the London Mathematical Society 113, e70483

    2026

  3. [11]

    Green,B.,Sisask,O.,2008.Onthemaximalnumberof3-termarithmeticprogressionsinsubsetsofℤ/𝑝ℤ.BulletinoftheLondonMathematical Society 40, 945–955

    2008

  4. [12]

    A linear sieve algorithm for finding prime numbers

    Gries, D., Misra, J., 1978. A linear sieve algorithm for finding prime numbers. Communications of the ACM 21, 999–1003

    1978

  5. [13]

    AnIntroductiontotheTheoryofNumbers

    Hardy,G.,Wright,E.,Heath-Brown,D.,Silverman,J.,2008. AnIntroductiontotheTheoryofNumbers. OxfordMathematics,OUPOxford, Oxford University Press, U.S.A

    2008

  6. [14]

    On the normal number of prime factors of a number n

    Hardy, G.H., 1917. On the normal number of prime factors of a number n. Quart. J. Math. Oxford Ser. 48, 76–92

    1917

  7. [15]

    Aclassicalintroductiontomodernnumbertheory.volume84

    Ireland,K.,Rosen,M.I.,1990. Aclassicalintroductiontomodernnumbertheory.volume84. SpringerScience&BusinessMedia,Springer- Verlag New York, NY, U.S.A

    1990

  8. [16]

    Strong bounds for 3-progressions, in: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Santa Cruz, CA, U.S.A

    Kelley, Z., Meka, R., 2023. Strong bounds for 3-progressions, in: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Santa Cruz, CA, U.S.A.. pp. 933–973

    2023

  9. [17]

    Corpus-based rhythmic pattern analysis of ragtime syncopation, in: Proceedings of the 16th International Society for Music Information Retrieval Conference, ISMIR, Málaga, Spain

    Koops, H.V., Volk, A., De Haas, W.B., 2015. Corpus-based rhythmic pattern analysis of ragtime syncopation, in: Proceedings of the 16th International Society for Music Information Retrieval Conference, ISMIR, Málaga, Spain. pp. 483–489

    2015

  10. [18]

    Imacpp.https://github.com/pvankranenburg/imacpp

    Kranenburg, P.V., 2022. Imacpp.https://github.com/pvankranenburg/imacpp

    2022

  11. [19]

    Inner Metric Analysis

    Nestke, A., Noll, T., 2001. Inner Metric Analysis. Tatra Mountains Mathematical Publications 23

    2001

  12. [20]

    Majorations explicites pour le nombre de diviseurs de n

    Nicolas, J.L., Robin, G., 1983. Majorations explicites pour le nombre de diviseurs de n. Canadian Mathematical Bulletin 26, 485–492. doi:10.4153/CMB-1983-078-5

    1983 doi

  13. [21]

    Linear prime-number sieves: A family tree

    Pritchard, P., 1987. Linear prime-number sieves: A family tree. Science of Computer Programming 9, 17–35

    1987

  14. [22]

    Applied combinatorics, in: Applied Combinatorics, Second Edition

    Roberts, F.S., Tesman, B., 2009. Applied combinatorics, in: Applied Combinatorics, Second Edition. Taylor and Francis, New York, NY, U.S.A., pp. 1–848

    2009

  15. [23]

    Tanaka, T., Bemman, B., Meredith, D., 2016a. Constraint programming approach to the problem of generating Milton Babbitt’s all-partition arrays, in: International Conference on Principles and Practice of Constraint Programming, Springer, Toulouse, France. pp. 802–810. Bemman e...

  16. [24]

    Tanaka, T., Bemman, B., Meredith, D., 2016b. Integer programming formulation of the problem of generating Milton Babbitt’s all-partition arrays, in: The 17th International Society for Music Information Retrieval Conference, ISMIR, New York, NY, U.S.A.. pp. 172–177

  17. [25]

    The study of syncopation using Inner Metric Analysis: Linking theoretical and experimental analysis of metre in music

    Volk, A., 2008. The study of syncopation using Inner Metric Analysis: Linking theoretical and experimental analysis of metre in music. Journal of New Music Research 37, 259–273. Bemman et al.:Preprint Page 23 of 23

    2008

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.