Fabian Arevalo

Amarilli–Monet–Suciu conjecture · order theory · session 2026-08-28

The smallest counterexample to the NCI conjecture has at least 16 elements

An exhaustive census of all 171,432,955 lattices with at most 15 elements: every one of them admits a winning dot-algebra tree, and in fact a winning left-linear one. The first lower bound on either of the two open problems posed by the conjecture's refutations.
28 August 2026 · AI-assisted (Claude), see disclosure · code, data and certificates

Start here, no maths required

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.

left-linear, seven steps
The game on the nine-element diagram of Wilhelm's Figure 3.1, solved live. The nine dots are the elements, drawn with smaller ones below larger ones. Filled dots are the elements you currently hold; the ring marks the top element, which must never be held. Each allowed set is everything at or below one chosen dot, and only dots with a nonzero Möbius value may be chosen, which here excludes the bottom. The winning line is not stored in this page: the figure runs a breadth-first search over all 256 possible positions each time it draws, then replays what it found and re-checks the legality of every move as it goes. It agrees, term for term, with the seven-step sequence the repository's independent checker extracts from the same diagram.

What this note adds

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.

  1. Every diagram with at most 15 elements is winnable. All 171,432,955 of them, generated from 34,978,238,589 underlying posets and decided exactly, one at a time. Zero losses. So the smallest losing diagram has at least 16 elements: the first lower bound recorded for either open problem.
  2. The restricted style of play suffices, everywhere in range. Wilhelm's first paper refutes the game for left-linear play, where every subtraction and addition must use an allowed set directly rather than a previously assembled combination. Below 16 elements that restriction costs nothing: every diagram is winnable in the restricted style too, so no diagram this small separates the two versions.
  3. The gap that remains is fourteen orders of magnitude. The smallest losing diagram lives somewhere in [16, 1.00011 × 1015], and nothing here narrows it further.

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.

AbstractSummary of results

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.

Section 1The game, precisely

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.

Definition (dot-algebra tree, after [3, Def. 3.1])

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.

Section 2The census

Theorem A · CERTIFIED

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.

nposets on n−2 (A000112)lattices (A006966)winningleft-linear winning
31111
42222
55555
616151515
763535353
8318222222222
92,0451,0781,0781,078
1016,9995,9945,9945,994
11183,23137,62237,62237,622
122,567,284262,776262,776262,776
1346,749,4272,018,3052,018,3052,018,305
141,104,891,74616,873,36416,873,36416,873,364
1533,823,827,452152,233,518152,233,518152,233,518
total34,978,238,589171,432,955171,432,955171,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.

hover a size for exact counts
What the census cost, and why 16 is the wall. Outline bars are posets streamed from the generator, solid bars the lattices that survive the filter and get decided. Both axes are drawn from the committed 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.

Corollary B, in set-family form

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.

Section 3Method, and what checks it

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:

  1. Count anchors. Poset and lattice counts match OEIS A000112 and A006966 at all thirteen sizes, b-files fetched 2026-08-28.
  2. Dual implementation. An independent Python implementation, written to the same specification and sharing no code, reproduces all four counters exactly: in full for every n ≤ 11, again in full at n = 12 (262,776 lattices), and on generator slices at n = 14 (1,201,420 posets, 41,149 lattices) and n = 15 (two slices, 2,841,817 and 123,283 posets).
  3. The published example. The nine-element lattice of [3, Figure 3.1] gives µ values matching that paper's remarks and is decided winning by both implementations. The witness extractor recovers the seven-step left-linear sequence in the figure at the top of this page and re-checks it against Definition 3.1 mechanically.
  4. Hand controls. M3 and N5 are winning with hand-checkable trees. An artificial negative control, a three-chain with the middle leaf deleted, is correctly reported non-winning, which exercises the exhaustion path rather than only the success path.
  5. Witness spot checks. For the worst-case lattice of every census part at n = 14 (8 of 8) and n = 15 (16 of 16), the independent verifier rebuilds the lattice from its digraph6 line by boolean-matrix closure, tests the lattice property from the raw definition on both joins and meets, recomputes µ, finds its own winning sequence, and re-verifies that sequence against Definition 3.1.

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.

Section 4Where the counterexample must live

Putting the census against the refutation gives a bracket, and the bracket is almost entirely empty.

The bracket on the smallest losing lattice. A logarithmic axis in the number of elements. The solid block at the left is this census: every lattice out to 15 elements checked, all winnable. The rule near the right is the smallest counterexample Wilhelm's Theorem 8.1 certifies, at p = 100003, about 1.00011 × 1015 elements. Everything hatched between is open, and it is fourteen orders of magnitude wide. Move the pointer along the axis to read what is known at a given size. Note that the right-hand end is the smallest instance their theorem certifies, not the smallest counterexample: the true value could be anywhere in the band.

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.

Section 5What this does not say

Section 6Open questions

  1. Close the gap. The minimal counterexample lies in [16, 1.00011 × 1015]. A lattice generator rather than a poset filter is the obvious next tool.
  2. Find the minimal lattice separating left-linear from general trees, now known to have at least 16 elements. The engine surfaces any such witness automatically.
  3. Decide winnability of the refutation's own small instances, P5,m and P7,m at 177 and 443 elements, for concrete markings. Find-a-win heuristics settle "winnable"; "not winnable" at that size needs a genuinely new idea, and that is the real lower-bound frontier.
  4. [3, §9 OP 2] asks how many µ = 0 leaves a weakened tree must use. The census infrastructure takes the leaf set as a parameter and can measure this in range with a one-line change.