Metadata-Version: 2.4
Name: sievemin
Version: 0.1.1
Summary: Exact (provably minimal) Xenakis sieve formulas for integer sets
Author: Duncan Bentley
License-Expression: BSD-3-Clause
Project-URL: Homepage, https://github.com/DuncanBentley/sievemin
Project-URL: Repository, https://github.com/DuncanBentley/sievemin
Project-URL: Issues, https://github.com/DuncanBentley/sievemin/issues
Project-URL: Changelog, https://github.com/DuncanBentley/sievemin/blob/main/CHANGELOG.md
Project-URL: DOI, https://doi.org/10.5281/zenodo.23816540
Keywords: Xenakis,sieve theory,music theory,set cover,integer linear programming,music21,computational musicology
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Education
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Topic :: Artistic Software
Classifier: Topic :: Multimedia :: Sound/Audio :: Analysis
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy
Requires-Dist: scipy>=1.9
Provides-Extra: music21
Requires-Dist: music21; extra == "music21"
Provides-Extra: bench
Requires-Dist: music21; extra == "bench"
Provides-Extra: test
Requires-Dist: pytest; extra == "test"
Requires-Dist: music21; extra == "test"
Dynamic: license-file

# 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.

[![CI](https://github.com/DuncanBentley/sievemin/actions/workflows/ci.yml/badge.svg)](https://github.com/DuncanBentley/sievemin/actions) [![License: BSD-3-Clause](https://img.shields.io/badge/license-BSD--3--Clause-blue.svg)](https://github.com/DuncanBentley/sievemin/blob/main/LICENSE) [![Python 3.10+](https://img.shields.io/badge/python-3.10%2B-blue.svg)](https://github.com/DuncanBentley/sievemin/blob/main/pyproject.toml) [![DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.23816540.svg)](https://doi.org/10.5281/zenodo.23816540)

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

| finding | numbers | where |
|---|---|---|
| music21's greedy is already optimal on its own small examples | 12 of 12 music21 test segments match the exact class count | [REPORT.md](https://github.com/DuncanBentley/sievemin/blob/main/REPORT.md) section 3 |
| It loses on bigger sets (z = 0..99, music21's modulus limit) | Psappha 20 classes down to 15, Nomos Alpha 8 to 7, À R. 17 to 14, Nekuïa 11 to 8 | [bench/results.md](https://github.com/DuncanBentley/sievemin/blob/main/bench/results.md), Table 1 |
| It loses on random segments of 5 to 100 points | 928 of 1,000 shorter, 22.4% fewer classes on average, max 40.5%, never longer | [bench/random_segments.md](https://github.com/DuncanBentley/sievemin/blob/main/bench/random_segments.md) |
| Smaller period | median period 70 against 21,162,960 for music21, at the price of 34.5 classes on average | [bench/random_segments.md](https://github.com/DuncanBentley/sievemin/blob/main/bench/random_segments.md) |
| Published Xenakis formulas are not all minimal, even with the composer's own moduli | Nomos Alpha size 23 to 21, Psappha (Flint) 59 to 36, À R. 99 to 88, Jonchaies already minimal | [bench/results.md](https://github.com/DuncanBentley/sievemin/blob/main/bench/results.md), Table 2 |
| Complement makes formulas shorter | the major scale goes from 18 to 10 (any modulus); on 251 small random segments, `&` and `-` beat the best union on 180 | [REPORT.md](https://github.com/DuncanBentley/sievemin/blob/main/REPORT.md) section 3 |
| The gain is smaller on structured material | 100 random Xenakis-style sieves: 37 shorter, 11.4% on average, median 0% | [bench/random_study.csv](https://github.com/DuncanBentley/sievemin/blob/main/bench/random_study.csv) |
| Error-tolerant mode (formula plus k wrong notes) | recovers a planted sieve with 1, 2, 3 flipped notes in 100%, 96%, 95% of 150 trials each (cost 1) | [bench/tolerant_study.md](https://github.com/DuncanBentley/sievemin/blob/main/bench/tolerant_study.md) |

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

## Install

```bash
pip install sievemin
```

or with uv:

```bash
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

```bash
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.

```python
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

```bash
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

| function | what it searches | what is proven |
|---|---|---|
| `minimize_union` | unions of residue classes, the form music21's `CompressionSegment` outputs | the fewest classes, the shortest string, or the smallest period, by exact ILP over every candidate class |
| `minimize_dnf` | unions of terms `P & -(N1\|...\|Nk)`, the shape of Xenakis's published sieves | the smallest formula of that shape, for a given cap on k and, optionally, on the moduli |
| `minimize_general` | formulas of any shape | the smallest formula there is, by exhaustive search, for domains of up to 14 points |
| `minimize_union_tolerant` | a union of classes plus up to k notes added or removed | the smallest formula size + λ × exceptions |

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](https://github.com/DuncanBentley/sievemin/blob/main/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](https://github.com/cuthbertLab/music21/releases/tag/v10.5.2)), specifically [`music21/sieve.py`](https://github.com/cuthbertLab/music21/blob/v10.5.2/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

| Report | Status |
|---|---|
| music21: crash on `Sieve('3@1&-4@2')` (unbracketed intersection with a complemented class), one-line fix plus test | issue filed: [cuthbertLab/music21#2131](https://github.com/cuthbertLab/music21/issues/2131), fixed and merged in [#2135](https://github.com/cuthbertLab/music21/pull/2135) |
| music21: opt-in exact compression, `CompressionSegment(..., method='exact')` | to be filed |

## Citation

See [CITATION.cff](https://github.com/DuncanBentley/sievemin/blob/main/CITATION.cff).

```bibtex
@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](https://github.com/DuncanBentley/sievemin/blob/main/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.

