Refutation of the Non-Cancelling-Intersections Conjecture
2026-08-27 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a mathematical idea called the Non-Cancelling Intersections conjecture, which was thought to describe how certain sets can be built from simple pieces. Previous work showed the idea doesn't always hold if the building blocks are arranged in a certain linear way. The authors here remove that restriction and prove the conjecture is false in general, by constructing a specific example (a lattice) that cannot be represented as required. They use a new tree-based approach and a special marked plane to make their argument simpler and applicable with reasonably sized primes.
Non-Cancelling Intersections conjecturedot-algebra representationfinite latticeleft-linear expressionsplane treetoggle gamemarked planeErdős–Beck theoremarithmetic Nullstellensatz
Authors
Hermann Wilhelm
Abstract
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.