Source-linked AI summary
Refutation of the Non-Cancelling-Intersections Conjecture
Hermann Wilhelm
TL;DR
The paper asks whether every finite lattice admits a dot-algebra representation of its top element, beyond the previously refuted left-linear setting. It replaces toggle sequences with plane trees and proves that, for every prime p ≥ 10^5, a lattice Pp,m admits no winning dot-algebra tree, thereby refuting the NCI conjecture in general.
Problem
The NCI conjecture claims that every finite lattice has a winning dot-algebra tree, but prior work refuted only the left-linear case.
Method
The paper replaces toggle sequences with plane trees and combines medium-node and tree blocking-gadget lemmas with a marking construction.
Results
Every prime p ≥ 10^5 admits a marking such that the lattice Pp,m has no winning dot-algebra tree, so the NCI conjecture is false.
Takeaways & Limitations
A finite lattice can admit no dot-algebra representation of its top element whatsoever, extending the refutation from left-linear trees to arbitrary trees.
Takeaways & Limitations
The first-moment argument produces no explicit marking, although exhaustive search for the smallest counterexample is conceivable for small p.
Abstract
from arXiv · showhide
The Non-Cancelling Intersections (NCI) conjecture of Amarilli, Monet and Suciu [arXiv:2401.16210] states that the union of a finite family of sets can always be built from its algebraically non-cancelling intersections using only disjoint unions and subset complements. In Wilhelm [arXiv:2608.19414] the conjecture was shown to fail when the witnessing dot-algebra expression is required to be left-linear. Here we remove that restriction and show that the conjecture is false in general: there is a finite lattice admitting no dot-algebra representation of its top element whatsoever. The counterexample is a lattice $P_{p,\mathfrak{m}}$ as in Wilhelm [arXiv:2608.19414], and the argument differs in only two ways. First, we replace the sequential "toggle game" of Wilhelm [arXiv:2608.19414] by a corresponding tree-shaped object, the plane tree, which stands to dot-algebra trees as the toggle game stands to left-linear ones. Second, we use a marked plane in which there is no admissible set of any size between $2p$ and $4p$, which also removes the need for the Erdős--Beck theorem and for the arithmetic Nullstellensatz. Consequently $p$ need not be astronomically large: every prime $p \ge 10^{5}$ works.
1 Introduction
The paper extends the refutation of the NCI conjecture from left-linear dot-algebra trees to arbitrary trees. It replaces sequence-based continuity arguments with tree-specific lemmas and proves a counterexample for every prime p ≥ 10^5.
- Problem: Tree node states can jump, so the sequence-based continuity arguments used for cardinality and near-collinearity no longer apply.Winning toggle sequences change red-point counts and off-line counts by at most one per move; trees do not preserve these properties.
- Tree replacement: Lemma 4.2 replaces exact cardinality coverage by guaranteeing a node carrying between N and 2N−2 points for every threshold N.This weaker medium-node property forces the later counting argument to exclude a range of cardinalities.
- Tree replacement: The tree version of the blocking-gadget argument replaces sequential counting with signed leaf counts over subtrees to account for cancellations.The sign records whether a leaf is inherited through an even or odd number of right-hand sides of subtraction nodes.
- Marking construction: Using point sets of size Θ(p) removes the degenerate collinear case above p, while elementary incidence identities support the probabilistic argument for 2p ≤ |T| ≤ 4p.Cauchy–Schwarz yields at least (p + 1)^2/12 traces of size at most 47 in that range.
- Main result: Every prime p ≥ 10^5 admits a marking whose lattice Pp,m has no winning dot-algebra tree, so the NCI conjecture is false.The result removes the earlier astronomical lower bound on p.
Organisation
The paper proceeds from preliminaries and tree definitions through blocking-gadget constraints and the marking construction before assembling the main theorem.
- Section 2 recalls the needed material from earlier work, while Section 3 defines dot-algebra trees and states the lattice formulation of the NCI conjecture.
- Sections 4–6 introduce winning plane trees, prove the tree blocking-gadget lemma, and connect winning dot-algebra trees to winning plane trees.
- Sections 7–8 construct the marking and assemble the proof; Remark 8.4 records a simplification of the earlier main result.
2 Preliminaries
The preliminaries define the poset, lattice, blocking-gadget, finite-plane, trace, and marking concepts used to construct the counterexample lattice Pp,m.
- Posets and lattices: For a poset element v, ↑v and ↓v denote its ancestors and descendants, while level(v) is the length of a longest upward path from v.Level-1 elements have only themselves and ⊤ above them; level-2 elements have themselves, their parents, and ⊤ above them.
- Posets and lattices: The lattice Möbius function satisfies µ(⊤) = 1, level-1 elements have µ = −1, and level-2 elements with two parents have µ = 1.
- Blocking gadgets: A blocking gadget is the interval induced by a level-3 element x with µ(x) = 0, partitioning its level-1 elements into blocked elements and unblocked elements M.Its level-2 elements have parents contained in M.
- Lines and markings: In Fp^2, every point lies on exactly p + 1 lines and every pair of distinct points lies on exactly one line.These identities provide the incidence structure used later in the construction.
- Lines and markings: A marking assigns marked points to each line, and a set is admissible when every line trace of size at least two contains a point marked for that line.
- The lattice Pp,m: The lattice Pp,m has depth 4, uses w := ⌈√2p⌉ + 1 marked points per line, and contains p^3 + 2p^2 + 2 elements.Its construction includes point elements, line-associated elements, and ⊥.
3 Dot-algebra trees
Dot-algebra trees encode set expressions over a lattice using disjoint unions and subset complements. The paper shows that arbitrary winning trees are strictly more general than the previously refuted left-linear case, yet still fail for some finite lattices.
- Dot-algebra trees: A da-tree is a finite rooted binary tree whose leaves use ∅ or non-top lattice vertices with nonzero Möbius value, and whose internal nodes use + or −.
- Dot-algebra trees: Node states are computed bottom-up: + forms a disjoint union, while − subtracts a right-child state contained in the left-child state.
- Dot-algebra trees: A da-tree is winning when its root state is P \ {⊤}, and it is left-linear when every right child of an internal node is a leaf.
- Interpretation: Leaves represent sets associated with lattice vertices, so a winning da-tree is precisely a dot-algebra expression for S⊤ = P \ {⊤}.The corresponding lattice and winning tree are illustrated in Figure 3.1.
- Interpretation: Empty leaves can be eliminated without changing the root state, although they are retained because the translation from lattice trees produces them.
- Contribution: The paper generalizes the earlier result that some finite lattices lack winning left-linear da-trees by proving that some lack winning da-trees altogether.
4 Winning plane trees
Winning plane trees are binary-tree counterparts to plane toggle sequences, with admissible states at every node and a root state equal to F2^p. Every winning plane tree contains an admissible intermediate state whose size lies between 2p and 4p.
- Definition: A plane tree is a finite rooted binary tree whose leaves are points or ∅ and whose internal nodes perform disjoint union or subset difference.The + operation requires disjoint child states, while the − operation requires the right state to be contained in the left state.
- Winning condition: A winning plane tree requires every node state to be admissible and its root state to be F2^p.Admissibility means every line trace contains a point marked for that line.
- Role in the proof: This lemma replaces the sequence-based continuity arguments, which do not hold for trees because node states can jump in size.The tree argument instead uses a largest node state still having at least 2p points along a heavy-child path.
- Medium-node lemma: The medium-node lemma guarantees a node with an admissible state of size at least 2p and at most 4p−2.Following a child carrying at least half the parent’s points yields the bound, since the winning root has p^2 points and leaves have at most one.
5 Blocking gadgets constrain every node of a da-tree
The tree version of the blocking-gadget lemma constrains every da-tree node: if no unblocked level-1 element is present, at most one level-1 or level-2 gadget element can occur. Signed leaf counts provide the mechanism for handling nested subtractions.
- Blocking-gadget constraint: Lemma 5.1 states that if a node state avoids the unblocked set M, it contains at most one element of L ∪ C.Equivalently, any node containing at least two level-1 elements must contain an unblocked one.
- Signed counting: The proof replaces sequence counting with signed subtree leaf counts, recording whether each leaf passes through an even or odd number of right-hand sides of − nodes.This sign accounts for cancellations introduced by nested set differences.
- Net-count invariant: For every node and every non-top element a, the signed leaf count net(a,u) equals 1 exactly when a belongs to the node state, and 0 otherwise.The result is proved by induction over the subtree, with + combining contributions and − subtracting the right-child contribution.
- Application: Applying the invariant to a blocking gadget shows that a node avoiding M cannot contain two elements from L ∪ C.The gadget structure supplies Q, with every level-2 element’s parents contained in M; the resulting sum has only 0-or-1 contributions.
- Scope: The constraint holds for every da-tree and every node, including leaves, without requiring the tree to be winning.Thus the lemma is a local structural property rather than a consequence of the root condition.
6 From da-trees to plane trees
A winning da-tree for Pp,m can be converted into a winning plane tree by retaining its operation structure and translating level-1 leaves into points. The blocking-gadget lemma then supplies admissibility for every resulting node state.
- Transfer lemma: If Pp,m admits a winning da-tree, then it admits a winning plane tree for the same prime p and marking m.This is the section’s main transfer lemma.
- Relabelling: The conversion preserves the underlying binary tree and +/− labels, maps each level-1 leaf ai,j to point (i,j), and maps other possible leaves to ∅.Vertices with zero Möbius value cannot label leaves, so these relabellings cover all cases.
- State preservation: Inductively, each converted node has the same point state as the level-1 part of the corresponding da-tree node.Leaf states match directly, and the disjoint-union and subset-difference requirements are inherited at internal nodes.
- Admissibility: Admissibility follows because a line trace with at least two points corresponds to at least two level-1 gadget elements, forcing an element of the marked unblocked set by Lemma 5.1.For the gadget generated by bi,j, L is the line and M is its marked subset.
- Winning root: The converted tree is winning because the original root contains every level-1 element, so its point state is F2^p.The root-state correspondence supplies the required winning condition.
7 A marking with no admissible set of medium size
For primes p ≥105, a probabilistic marking is shown to eliminate every admissible set T with 2p ≤|T| ≤4p. The proof combines elementary incidence counting with a first-moment bound whose slack makes the argument work without finer structural analysis.
- Every point lies on exactly p + 1 lines and every pair of points lies on exactly one line, providing the incidence identities used throughout the section.
- At least (p + 1)2/12 distinct lines determine traces of size at most 47 for every T with 2p ≤|T| ≤4p.
- A random marking independently selects w = ⌈√2p⌉ + 1 points on each line, so each short trace is hit with probability controlled by its size and w/p.
- The first-moment estimate gives Ep < 1, so some marking has no admissible set T with 2p ≤|T| ≤4p.
- The estimate has substantial slack: the admissibility cost is exp(−Θ(p2 ln p)), overwhelming the exp(O(p ln p)) number of candidate sets.
- Because the argument operates in the medium-size range, it needs no structural information about T beyond the trace-counting lemma and avoids the delicate constant-size analysis.
8 The main theorem
Using the marking from Lemma 7.2, the paper transfers any winning dot-algebra tree to a winning plane tree and derives an admissible medium-sized state, yielding a contradiction. Thus a finite lattice and a finite family of sets lack any dot-algebra representation of their union.
- Theorem 8.1 states that for every prime p ≥105 and a marking supplied by Lemma 7.2, Pp,m admits no winning da-tree.
- A hypothetical winning da-tree induces a winning plane tree, whose admissible state contradicts the marking constructed in Lemma 7.2.
- Consequently, a finite lattice admits no winning da-tree, and the NCI conjecture is false.
- For p = 100 003, the associated family of sets has a union admitting no dot-algebra representation.
- The lattice Pp,m has p3 + 2p2 + 2 elements, producing a counterexample substantially smaller in stated bound than the earlier result.
- The same medium-size admissibility argument also gives a shorter proof of the earlier left-linear result without the finite Erdős–Beck theorem or arithmetic Nullstellensatz.
9 Open problems
The paper leaves explicit counterexamples, minimum-size questions, and the structure of zero-measure vertices as open problems.
- The first-moment argument produces no explicit marking, leaving the smallest lattice with no winning da-tree unknown and making exhaustive search for small p conceivable.
- An open question asks how many vertices with µ = 0 a weakened da-tree must use and which vertices they are.
Use of AI
The author reports using Claude to formalize proofs from initial notes and sketches, while verifying the mathematical content personally.
- Claude was used to formalize proofs from the author’s initial notes and sketch, and the author verified all mathematical content.