A stabilizer obstruction for classification aggregation

This repository contains a counterexample to a conjecture in anonymous and object-neutral classification aggregation, a social-choice problem studied by Cailloux, Hervouin, Ozkes, and Sanver at COMSOC 2025.

Theorem. For every number of objects m >= 5, every number of individuals n >= 2, and rho = m - 2 nonempty categories, no deterministic anonymous and object-neutral classification aggregation function exists.

Taking (n,m,rho) = (7,5,3) refutes the proposed sufficiency of the prime-divisor condition: the only prime divisor of n is 7, which exceeds m=5, yet aggregation is impossible.

The complete write-up is paper/paper.pdf.

Author: Richie Sater, Independent Researcher (ORCID 0009-0007-9051-8207).

Archival DOI: 10.5281/zenodo.21901923.

Cite

Sater, Richie. 2026. “A Stabilizer Obstruction for Anonymous and Object-Neutral Classification Aggregation.” Zenodo. https://doi.org/10.5281/zenodo.21901923.

Machine-readable citation metadata is available in CITATION.cff.

The idea

A classification is a surjection from the objects to the categories. Consider this seven-individual profile:

individuals	x1	x2	x3	x4	x5
1, 2	A	B	C	C	C
3, 4	B	A	C	C	C
5	A	A	B	B	C
6	A	A	B	C	B
7	A	A	C	B	B

Every row uses all three categories. Swapping x1,x2 only permutes individuals, as does cycling x3,x4,x5. Anonymity and object neutrality would therefore force the collective classification to be constant on {x1,x2} and on {x3,x4,x5}. It could use at most two categories, contradicting the required surjection onto three.

The uniform theorem packages this observation as a stabilizer lemma. It uses a two-classification orbit and a three-classification orbit. Since every n >= 2 is 2k + 3l, the construction works for every number of individuals, not merely for the seven-individual certificate.

Reproduce the certificate

Requirements:

• Python 3;
• a recent stable Rust toolchain with rustfmt and clippy;
• Tectonic only if rebuilding the paper.

Run both independent verifiers:

make verify

The essential output is:

surjective_outputs=150
surjective_outputs_fixed_by_s_and_t=0
general_family_grid m=5..12 n=2..40: PASS
VERDICT: no anonymous object-neutral CAF can exist for this profile

surjective outputs checked: 150
outputs fixed by both object permutations: 0
VERDICT: anonymous + object-neutral aggregation is impossible

Rebuild everything and refresh the checked-in verification artifacts:

make all

Check the recorded hashes without changing anything:

make check-checksums

Repository layout

.
├── paper/
│   ├── paper.tex                 # self-contained research note
│   └── paper.pdf                 # rendered note
├── src/main.rs                   # Rust certificate + family checker
├── verify.py                     # independent stdlib Python checker
├── artifacts/
│   ├── rust-verification.log
│   ├── python-verification.log
│   └── SHA256SUMS
├── RESEARCH.md                   # problem-selection and novelty-search log
├── AGENTS.md                     # maintenance and verification instructions
├── CITATION.cff                  # citation metadata
├── .zenodo.json                  # archival metadata
├── Makefile
└── Cargo.toml

The code is corroborative rather than load-bearing: the theorem has a uniform proof. The Rust parameter grid is explicitly a regression test, not a bounded substitute for that proof.

Target and research status

The target is Cailloux, Hervouin, Ozkes, and Sanver, Anonymous and Neutral Classification Aggregation, COMSOC 2025, paper 36, especially Appendix A and Table 4. The conjecture also appears on the authors' SSRN record.

The public-source search described in RESEARCH.md found no prior resolution of the exact conjecture through 2026-08-07. That is not a claim of peer-reviewed novelty: private, unpublished, or unindexed work cannot be excluded, and novelty should be checked again before submission or publicity.

Scope

The result applies to deterministic, resolute aggregation with surjective individual and collective classifications, exactly as in the target model. It does not address randomized or set-valued rules and does not classify all remaining (n,m,rho) triples.

The target selection and proof discovery occurred in an AI-assisted research workflow. The explicit proof, finite certificate, and two independent checkers are provided so the claim can be assessed independently of its origin.

Licensing

The paper and documentation are licensed under CC BY 4.0, whose legal text is in LICENSE. The Rust and Python source code are additionally available under the MIT License.