sievemin

sievemin finds the shortest Xenakis sieve that produces a given set of integers, and proves nothing shorter exists in the formula shape you asked for. Against music21's greedy compressor it is shorter on 928 of 1,000 random segments, and it shortens several published Xenakis sieves.

A sieve is a formula built from residue classes m@r (every n with n mod m = r), joined with union |, intersection & and complement -. The output uses music21's sieve syntax, so you can paste it into music21.sieve.Sieve.

I make metal and produce records. Sieves are a tidy way to write down a scale or a rhythm that doesn't repeat every octave or every bar. I wanted to know whether the formulas people publish, and the ones music21 generates, are actually the short ones. Mostly they're close. Sometimes they aren't.

Key findings

Random point sets are where the greedy does worst. Real material is more structured, and there the gain is smaller.

Install

pip install sievemin

or with uv:

uv add sievemin

pip install "sievemin[music21]" also installs music21, so you can check the output with music21.sieve.Sieve. sievemin itself only needs numpy and scipy.

Quick start

sievemin 0 2 4 5 7 9 11 --period 12
# (-(12@1|12@3|12@6|12@8|12@10))
# size 10 (leaves 5, operators 5); optimal: True; ...

That takes a few seconds, mostly Python start-up. The solve itself is tens of milliseconds.

from sievemin import Domain, parse, evaluate, minimize_dnf, to_music21

nomos = '(-(13@3|13@5|13@7|13@9)&11@2)|(-(11@4|11@8)&13@9)|(13@0|13@1|13@6)'
dom = Domain.periodic(143)
r = minimize_dnf(evaluate(parse(nomos), dom), dom, max_modulus=13, max_neg=4)
r.text, r.size, r.optimal
# ('11@2&-(13@3|13@5|13@7)|13@0|13@1|13@6|13@9&-(11@4|11@8)', 21, True)
to_music21(r.formula)   # bracketed, see the music21 note below

Domain.window(z) matches exactly on the points of z, which is how music21 works. Pass max_modulus=len(z) - 1 to stay inside the moduli music21 itself would try. Domain.periodic(P) matches on every integer.

For unions you can choose what "shortest" means: minimize_union(..., objective='leaves' | 'chars' | 'period').

minimize_union_tolerant(points, dom, max_edits=2, edit_cost=1) returns a formula plus the notes to add and the notes to remove.

One music21 note: music21 10.5.2 crashes on an unbracketed intersection with a complemented class, for example Sieve('3@1&-4@2'). to_music21() puts brackets around the formula to avoid it.

Reproduce everything

git clone https://github.com/DuncanBentley/sievemin
cd sievemin
pip install -e ".[test]"          # adds pytest and music21
python -m pytest                  # 127 tests
python bench/reproduce.py         # benchmark and tolerant study, a few minutes
python bench/reproduce.py --all   # adds the 1,000 random segments, 1 to 2 hours

bench/reproduce.py writes bench/results.md and results.csv, plus bench/tolerant_study.md and tolerant_study.csv. With --all it also writes bench/random_segments.md and random_segments.csv. The 100 random Xenakis-style sieves are in bench/random_study.csv. Seeds are fixed (2026), so the optimal values reproduce exactly. Runtimes depend on the machine. Mine is a Ryzen 9 8940HX laptop, where the 1,000-segment run took 1 hour 54 minutes.

What it guarantees

Size means leaves plus operators, so a union of n classes has size 2n - 1. Every result says whether the solver proved it optimal. I also ran every published result in this repo back through music21's own Sieve and checked it gives the same set.

Method

Unions are an exact set cover, solved as an ILP with HiGHS through scipy. The candidate list is every residue class that stays inside the target, so the minimum is global. Terms with complement are enumerated per positive class, then another set cover picks the cheapest union. The any-shape search is dynamic programming over all subsets of up to 14 points. REPORT.md has the details, the benchmarks and the prior-work notes.

Limits / what this does not show

minimize_dnf is only optimal within its own shape. A formula nested differently can be shorter. With moduli up to 4, the major scale has a size 16 formula, and the best union of terms is 17. Only minimize_general covers every shape, and it runs out of room past 14 points.

A result on a window only holds on that window, as with music21. If the formula has to hold on every integer, use Domain.periodic(P). A window formula can use moduli no composer would pick, like 41@24.

Exact set cover is NP-hard. Most sets solve in milliseconds, but some 100-point windows take tens of seconds, and the slowest random segment took 248 s.

The error-tolerant mode only works with unions, and its answer depends on the exception cost λ, which you choose. That it finds structure in Xenakis's sets is not evidence that he edited notes by hand.

On music21's own 12 test segments the greedy is already optimal. The 1,000 random segments have no structure, so 22.4% is not what to expect on a real scale or rhythm.

I haven't read Formalized Music or Xenakis 1990 directly. The published formulas come from music21's tests and the hmt library, and the value lists I generate match hmt's for Nomos Alpha, Psappha and À R.

Whether a shorter formula is better music is not something this measures.

Upstream and sources

• music21: https://github.com/cuthbertLab/music21. I studied version 10.5.2 (release), specifically music21/sieve.py. Docs: https://www.music21.org/music21docs/moduleReference/moduleSieve.html.
• hmt (Rohan Drape, Haskell), a second source for the published sieves: https://github.com/rd--/hmt.
• Ariza, C. 2005. "The Xenakis Sieve as Object: A New Model and a Complete Implementation." Computer Music Journal 29(2). DOI 10.1162/0148926054094396. This is the model behind music21's sieve.
• Xenakis, I. 1990. "Sieves." Perspectives of New Music 28(1): https://doi.org/10.2307/833343.
• Bliznets, Nederlof and Szilágyi, "Parameterized Algorithms for Covering by Arithmetic Progressions": https://arxiv.org/abs/2312.06393.

No external data is downloaded. The published sieve definitions are re-typed from music21's tests and hmt, and the random sets come from fixed seeds.

Status of upstream reports

Citation

See CITATION.cff.

@software{bentley2026_sievemin,
  author = {Bentley, Duncan},
  title  = {sievemin: exact minimisation of Xenakis sieves},
  year   = {2026},
  url    = {https://github.com/DuncanBentley/sievemin},
  doi    = {10.5281/zenodo.23816540}
}

License

BSD-3-Clause, the same as music21. See LICENSE. The repo contains no third-party data.

Acknowledgements

Thanks to Michael Scott Cuthbert and the music21 contributors, whose sieve.py I tested against, to Christopher Ariza for the sieve model it implements, and to Rohan Drape for hmt.