CS Paper Radar

Refutation of the Non-Cancelling Intersections Conjecture

Hermann Wilhelm

cs.DM math.CO ·submitted 2026-08-27 17:42 UTC · v2
theory

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.

Comment
v2: added a "Note added" reporting an independent equivalent result by A. Walz and comparing the two arguments; added a worked example of a winning plane da-tree over $\mathbb{F}_3^2$ (new figure); renamed "plane tree" to "plane da-tree" throughout; minor corrections and rewording; title hyphenation fixed

Closest papers

Nearest neighbours by meaning across the whole index.

The Non-Cancelling-Intersections Conjecture Fails for Left-Linear Trees

cs.DM math.CO ·2026-08-19 ·Hermann Wilhelm
theory similarity 0.68
Abstract

First formulated by Amarilli, Monet, and Suciu (arXiv:2401.16210, 2024), the Non-Cancelling Intersections (NCI) conjecture is an open problem in combinatorics stating that any set union can be constructively built from its algebraically non-cancelling intersections using only disjoint unions and subset complements. In the same paper, two orthogonal possible strengthenings are proposed: using only left-linear trees, and using non-trivial intersections only positively or only negatively depending on the sign of their Möbius value. Here we show that using only left-linear trees, the conjecture is false (independent of the other strengthening). Our argument is non-constructive. We prove the existence of a counterexample, though it is of immense size.

0.40

Graded Intersection Types

cs.LO cs.PL ·2026-11-12 ·Rémy Cerda, Ugo Dal Lago
similarity 0.55
Abstract

We introduce graded intersection types, in which arrow domains are multisets of types with coefficients in a semiring. Boolean and natural number grades recover idempotent and non-idempotent intersection types. We give algebraic conditions on the semiring for subject reduction and expansion in finite systems and in locally finite systems with guarded infinite types. We construct a lifting to multisets of grades corresponding, in this general setting, to lifting the idempotent system to the non-idempotent one. We recall the main existing operational characterisations from the literature, and show some general extensions.

0.34

The Lattice of Coalition Logics between MCL and CL: Coatoms and Compact Meets

cs.LO math.LO ·2026-10-17 ·Shanxia Wang, Yuqiang Dou
similarity 0.55
Abstract · 19 pages, one table; supplementary finite-checking Python program in ancillary files

For a fixed finite set $N$ of at least two agents, we investigate the lattice $L_N$ of coalition logics between minimal coalition logic (MCL) and classical coalition logic (CL), with extensions required to be structural. This lattice is order-dual to an interval in the subvariety lattice of Boolean coalition algebras. The eight basic extensions obtained by imposing seriality, independence of agents, and determinism form a Boolean cube under inclusion, but not a sublattice of $L_N$. Our main results concern coatoms and compact meets. First, finite critical coalition algebras, realized as complex algebras of finite general concurrent games, yield three infinite families of pairwise distinct coatoms containing seriality, distinguished by failures of independence, determinism, or both. An explicit splitting characterizes the unique coatom omitting seriality. Second, the meet of two basic extensions is compact if and only if the extensions are comparable. For incomparable pairs, no axiomatization of the meet can use formulas of uniformly bounded modal depth, even with infinitely many axioms. Consequently, $L_N$ and three natural principal intervals are non-coherent algebraic lattices. These results reveal lattice-theoretic phenomena beyond the inclusion order of the eight basic extensions.

0.28

Rational decomposition of polyhedra and a conjecture of Brlek and Reutenauer

cs.DM cs.FLmath.COmath.MG ·2026-10-15 ·Flavio D'Alessandro, Paolo Papi
theoryunusual similarity 0.53
Abstract

We prove in the affirmative a conjecture of Brlek and Reutenauer (2003), which relates unambiguous rational sets to a well known result due to Khovanskii and Pukhlikov (1992) and independently to Lawrence (1990) on the valuations of the algebra spanned by the indicator functions of polyhedra.

0.48

Finite $\mathbf{BM}$-algebras and fixed-point combinators

cs.LO math.LO ·2026-10-27 ·Takuma Imamura
theory similarity 0.52
Abstract

We study algebras for the $\mathbf{BM}$-, $\mathbf{BI}$-, and $\mathbf{BMI}$-fragments of combinatory logic, where $\mathbf{B} xyz \to_{w} x\left(yz\right)$, $\mathbf{M} x \to_{w} xx$ and $\mathbf{I} x \to_{w} x$. We prove that every finite $\mathbf{BM}$-algebra $\mathcal{A}$ contains an element $Y$ satisfying $Yx = x\left(Yx\right)$ for all $x\in A$. Moreover, a single closed $\mathbf{BM}$-term represents such an element in every finite $\mathbf{BM}$-algebra. On the other hand, we show that there exists an infinite $\mathbf{BMI}$-algebra with no such element. Consequently, the variety of $\mathbf{BM}$-algebras is not generated by finite $\mathbf{BM}$-algebras. We also characterise finite $\mathbf{BI}$-algebras as finite semigroups with two distinguished left units $B$ and $I$, and finite $\mathbf{BMI}$-algebras as finite idempotent semigroups with three distinguished left units $B$, $M$ and $I$.

0.25

Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse

cs.LO math.LO ·2026-10-29 ·Kirill Osipov
theory similarity 0.52
Abstract

For a strictly increasing $G:\mathbb{N}\to\mathbb{N}$ with $G(0)\geq 1$, we study minimal-basis function algebras generated by recursion along generalized inverses of its iterates. Bounded recursion requires an earlier pointwise majorant; unbounded recursion has no such requirement. If the orbit $G^{[t]}(0)$ has no polynomial upper bound, we obtain exact fixed-function membership spectra, reverse-divisibility inclusion, and indexed intersections that need not be single-stride algebras. Every finite divisibility-downset is realized in both regimes, and mixed strides admit fixed functions expressing any finite monotone Boolean condition on their additive stride monoid. For every generator, the realized bounded spectra form a bounded meet-semilattice: a construction sharing a bounding input coordinate realizes finite intersections without an unrestricted selector. Polynomial orbit growth is equivalent to definability of each of ordinary predecessor, unary doubling, and addition in any fixed unbounded stride algebra. In this case the algebra is ordinary primitive recursion relative to its inverse map, giving full collapse for primitive-recursive $G$. Ordinary predecessor belongs to a bounded stride algebra exactly when the orbit is polynomially bounded and $G$ has bounded successive differences; equivalently, ordinary bounded recursion embeds. A locality obstruction explains the additional bounded requirement, and two primitive-recursive generators with quadratic orbits have opposite bounded collapse behavior.

0.23

Generalized Hamming weights of codes arising from complete intersection

cs.IT math.AC ·2026-08-20 ·Eduardo Camps Moreno, Flavio Salizzoni, Rodrigo San-José
similarity 0.51
Abstract · 5 pages

We provide a positive answer to a conjecture proposed by Tohǎneanu and Van Tuyl regarding the minimum distance of codes whose underlying set of points is a reduced complete intersection. Despite the technical nature of the conjecture, we show that it follows directly from a not-well-known refinement of the classical Bézout bound for overdetermined polynomial systems. For completeness, this paper presents a self-contained proof of this refined bound. Furthermore, we show that using the same approach, it is possible to obtain a bound on the generalized Hamming weights of such a code and, more generally, to control the minimum distance of the codes obtained by evaluating forms of degree $d$ on the points of a zero-dimensional complete intersection.

0.33

Guillotine and Tiling Cofiniteness in Unary Picture Languages

cs.FL ·2026-08-25 ·Pierluigi San Pietro, Stefano Crespi Reghizzi, Antonio Restivo
publishedtheory similarity 0.51
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

Motivated by the study of closure operations on picture languages, we ask when a set of unary tiles can generate all sufficiently large pictures either via repeated horizontal and vertical concatenations or via tiling operations. In one dimension, the lengths of words in the concatenation closure of a unary language form an additive subsemigroup of positive natural numbers; hence, they are finitely generated. Cofiniteness is characterized by the gcd of these generators being one. Since ordinary cofiniteness in two dimensions is too restrictive and essentially reduces to degenerate one-dimensional conditions on strips, we introduce and study asymptotic cofiniteness: all sufficiently large rectangular pictures are generated. A direct extension of the one-dimensional criterion, requiring the gcd of the tile heights and of the tile widths to be one, is not sufficient, because local congruence obstructions may persist in two dimensions. We give an exact arithmetic characterization of asymptotic cofiniteness for arbitrary, possibly infinite, sets of unary rectangular tiles. The characterization is the same for the guillotine closure, obtained by horizontal and vertical concatenation, and for the full tiling closure. For finite tile sets, the proof combines semigroup arguments and an explicit least-common-multiple stacking construction for sufficiency, while necessity is obtained by a roots-of-unity argument applying also to nonsliceable tilings. The extension to infinite tile sets follows from the finite-basis theorem for Klarner systems.

0.36