Amarilli–Monet–Suciu conjecture · order theory · session 2026-08-28
Here is a solitaire game played on a diagram. You are given a collection of overlapping sets, and one target set you are trying to build. You may start from any of the allowed sets, and then repeatedly either add another allowed set, provided it does not overlap what you already hold, or subtract one, provided it sits entirely inside what you already hold. No other move exists. Win by reaching the target exactly.
The restriction is what makes it hard. Ordinary counting lets you add and subtract freely and fix the overcounting afterwards, which is what inclusion and exclusion does. This game forbids that: every intermediate position has to be an honest set, never a tally that is temporarily wrong. The question is whether the game can always be won.
Three computer scientists, Antoine Amarilli, Mikaël Monet and Dan Suciu, conjectured in 2024 that it always can, for every finite diagram of this kind. The conjecture came out of database theory, where winning corresponds to a query plan that never double-counts. In August 2026 it was refuted, twice, by Hannes Wilhelm: first for a restricted style of play, then in general. The figure below is a diagram on nine points, taken from the refutation paper itself, and a winning line of play found in your browser.
Both refutations are probabilistic. They prove that a losing diagram exists without producing one, and both close by asking the same question: how small can a losing diagram be? Wilhelm's full refutation certifies one of about 1.00011 × 1015 elements. Nothing was known from below. This session attacked that side.
Everything below is the technical version. The second figure shows the shape of what remains open; the third shows why 16 is where an exhaustive census stops rather than where the interesting mathematics stops.
The Non-Cancelling-Intersections conjecture of Amarilli, Monet and Suciu [1] states, in its lattice form, that every finite lattice admits a winning dot-algebra tree: a tree expression built from the principal down-sets of the elements of nonzero Möbius value, using disjoint union and guarded set difference, whose value is the whole lattice minus its top. Wilhelm refuted the conjecture for left-linear trees on 19 August 2026 [2] and in full on 27 August 2026 [3]. Both refutations are probabilistic, produce no explicit counterexample, and pose as their first open problem a lower bound on the size of the smallest one. The smallest counterexample size certified by [3] is p3 + 2p2 + 2 for a prime p ≥ 105, about 1.0001 × 1015.
We give the first lower bound: every lattice with at most 15 elements
admits a winning dot-algebra tree, in fact a winning left-linear one.
CERTIFIED, by exhaustive computation over all 171,432,955 lattices with 3 to 15
elements, streamed from nauty-genposetg with generation counts
matching OEIS A000112 and lattice counts matching A006966 at every size, with
dual independent implementations and machine-verified explicit trees for
controls. Hence the minimal counterexample of [3] has at least
16 elements, the minimal left-linear counterexample of [2] has
at least 16 elements, and, via the equivalences proved in
[1, §4–5], any counterexample set family to the
original conjecture has more than 15 distinct subfamily intersections. As a
further consequence, no lattice with at most 15 elements separates left-linear
from general dot-algebra trees: the separation that
[2] + [3] jointly imply exists
happens strictly above this range.
Fix a finite lattice P with top ⊤. The Möbius function used throughout is µ(⊤) = 1 and µ(v) = −∑u>v µ(u), which is µ(v,⊤) in the standard notation. For v ≠ ⊤ write Sv := ↓v ⊆ P ∖ {⊤} for the principal down-set.
A da-tree is a finite rooted binary tree whose leaves are labelled ∅ or by an element v ≠ ⊤ with µ(v) ≠ 0, and whose internal nodes are labelled + or −. States are assigned bottom-up: X∅ = ∅, Xv = Sv; a +-node requires its children's states to be disjoint and takes their union; a −-node requires its right child's state to be contained in its left child's and takes the difference. The tree is winning if the root state is P ∖ {⊤}, and left-linear if every right child of an internal node is a leaf.
The two requirements are the whole difficulty. Dropping them turns the question into ordinary inclusion and exclusion, which is always solvable; keeping them means every intermediate value must be a genuine set.
Three small reductions make the census possible, all elementary and all proved in the note:
Because the ground set has n − 1 points, every state is a bitmask below 2n−1 ≤ 16,384. Both decisions are therefore exact and total: no budgets, no sampling, no heuristic anywhere in the decision path, and no floating point.
Every lattice with at most 15 elements admits a winning left-linear da-tree. Consequently: (i) the minimal lattice with no winning da-tree ([3, §9 OP 1]) has at least 16 elements, against that paper's upper bound of about 1.00011 × 1015; (ii) the minimal lattice with no winning left-linear da-tree ([2, §9 OP 1]) has at least 16 elements; (iii) no lattice with at most 15 elements separates left-linear from general da-trees.
Scope: 171,432,955 lattices, 3 ≤ n ≤ 15. Nothing is claimed beyond n = 15.
| n | posets on n−2 (A000112) | lattices (A006966) | winning | left-linear winning |
|---|---|---|---|---|
| 3 | 1 | 1 | 1 | 1 |
| 4 | 2 | 2 | 2 | 2 |
| 5 | 5 | 5 | 5 | 5 |
| 6 | 16 | 15 | 15 | 15 |
| 7 | 63 | 53 | 53 | 53 |
| 8 | 318 | 222 | 222 | 222 |
| 9 | 2,045 | 1,078 | 1,078 | 1,078 |
| 10 | 16,999 | 5,994 | 5,994 | 5,994 |
| 11 | 183,231 | 37,622 | 37,622 | 37,622 |
| 12 | 2,567,284 | 262,776 | 262,776 | 262,776 |
| 13 | 46,749,427 | 2,018,305 | 2,018,305 | 2,018,305 |
| 14 | 1,104,891,746 | 16,873,364 | 16,873,364 | 16,873,364 |
| 15 | 33,823,827,452 | 152,233,518 | 152,233,518 | 152,233,518 |
| total | 34,978,238,589 | 171,432,955 | 171,432,955 | 171,432,955 |
Every generated-poset count equals A000112(n−2) and every lattice-filter count equals A006966(n) exactly. Those anchors are part of the certificate, not decoration: they validate the generator invocation and the lattice filter independently at every size, and they are what caught the first n = 14 launch, where a mis-specified split option silently produced empty parts.
census_summary.tsv, not from a model. Every solid bar is entirely
winnable, at every size. The Yield view shows the ratio: it falls to
0.45% at n = 15, which is the actual bottleneck. Generating and
parsing 3.38 × 1010 posets dominates the run; the 152
million lattice decisions are a small fraction of the work.Every set family whose intersection lattice has at most 15 elements satisfies the original NCI conjecture; equivalently, a counterexample family has more than 15 distinct subfamily intersections. This follows from Theorem A through the equivalences proved in [1, §4] and restated as a translation in [3, Remark 3.4]. Those statements were checked against the papers, but their proofs were not re-verified here, so the corollary's label is Certified modulo cited equivalences rather than CERTIFIED outright.
nauty-genposetg streams Hasse diagrams of all posets on
n − 2 points in digraph6; a C engine filters to lattices by
Lemma 3, computes µ by the defining recursion, forms the leaf masks, and decides
left-linear winnability by the Lemma 2 breadth-first search over bitmask states.
A left-linear win implies a win, so the general Lemma 1 closure runs only on
lattices that fail the left-linear search. In range, none did. A lattice failing
both would have been printed as a candidate counterexample; a lattice failing
left-linear but winning generally would have been printed as an explicit
separation witness.
Five things check it:
Cost. Four cores, cloud sandbox, 2026-08-28. Sizes up to 13 take about 80 seconds in a single pipeline. n = 14 takes 5 min 13 s wall and 15 min 9 s CPU over 8 generator parts; n = 15 takes 132 min 55 s wall and 8 h 14 min CPU over 16 parts, 4-way parallel. Peak memory per process is under 10 MB. There is no randomness anywhere and no seed to record.
Two structural observations fell out of the run, offered as data rather than theorems. Lattices whose top covers a single element are winning by a single leaf, and their count at size n is A006966(n−1), observed exactly at every size. And the worst-case number of search states is exactly 2n−1 − 1 at every size from 4 to 15: some lattice explores all but one subset of its ground set before its decision, while the median stays in single digits.
Putting the census against the refutation gives a bracket, and the bracket is almost entirely empty.
Closing the gap from below by more census is not promising. The smallest member of the refutation's construction family, at p = 5, already has 177 elements, far beyond exact state closure. The honest next step on the computational side is a canonical-construction-path generator that produces lattices directly rather than filtering them out of posets, which is how the literature reached A006966 at n ≈ 19–20 (secondary: Heitzig–Reinhold, Jipsen–Lawless; cited as future context, no result of theirs is used here). That would put n = 16 to 18 in reach of the same decision engine, which already prints a counterexample or a separating witness the moment one appears.