# The Non-Cancelling Intersections Conjecture

Antoine Amarilli
LTCI, Télécom Paris,
Institut Polytechnique de Paris
<EMAIL_ADDRESS>Mikaël Monet
Université de Lille, CNRS, Inria, UMR 9189 - CRIStAL, F-59000 Lille, France
<EMAIL_ADDRESS>Dan Suciu
University of Washington
<EMAIL_ADDRESS>
###### Abstract

In this note, we present a conjecture on intersections of set families, and a
rephrasing of the conjecture in terms of principal downsets of Boolean
lattices. The conjecture informally states that, whenever we can express the
measure of a union of sets in terms of the measure of some of their
intersections using the inclusion-exclusion formula, then we can express the
union as a set from these same intersections via the set operations of
disjoint union and subset complement. We also present a partial result towards
establishing the conjecture.

#### Acknowledgements.

We thank Louis Jachiet for helpful discussions on the problem, and for having
found the counterexample to a stronger version of the conjecture that is
mentioned at the end of Section 7. This work was done in part while the
authors were visiting the Simons Institute for the Theory of Computing.

##  1 Introduction

We present in this note a conjecture on intersection lattices of set families,
which can be equivalently stated on the Boolean lattice. The original
motivation for the conjecture comes from a problem in database theory about
the existence of certain circuit representations for probabilistic query
evaluation (see [Monet, 2020a]), but in this note we present the conjecture as
a purely abstract claim without any database prerequisites. A positive answer
to this abstract conjecture implies a positive answer to the database theory
conjecture.

The conjecture can be understood in terms of the inclusion-exclusion formula.
Consider a family of sets $S_{1},\ldots,S_{n}$. The inclusion-exclusion
formula can be used to express a quantity on the union $S_{1}\cup\cdots\cup
S_{n}$ (e.g., the cardinality, or the value of some measure) as a function of
the intersections of the $S_{i}$. In general, some of these intersections may
in fact be identical: we can in fact define the _intersection lattice_ of the
set family to represent the possible intersections that can be obtained.
Further, we can have _cancellations_ , i.e., some of the possible
intersections may end up having a coefficient of zero in the inclusion-
exclusion formula, due to cancellations. Thus, in the general case, inclusion-
exclusion allows us to express the measure of $S_{1}\cup\cdots\cup S_{n}$ in
terms of the measure of the intersections $I_{1},\ldots,I_{m}$ that have a
non-zero coefficient.

Our conjecture asks whether, in this case, one can obtain the _set_
$S_{1}\cup\cdots\cup S_{n}$ from the intersections $I_{1},\ldots,I_{m}$, using
the set operations of disjoint union and subset-complement. If this is true,
then it implies in particular the inclusion-exclusion formulation, provided
that our measure is additive in the sense that the measure of
$S\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}S^{\prime}$ (where
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$ denotes disjoint union and
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$ subset complement, as
per Definition 3.1) is the sum of the measure of $S$ and of $S^{\prime}$.
Obtaining such a set expression can sometimes be done simply by re-ordering
the inclusion-expression formula: for instance, if we write $|X\cup
Y|=|X|+|Y|-|X\cap Y|$, we can reorder to $|X\cup Y|=|X|-|X\cap Y|+|Y|$, and
then express $X\cup
Y=(X\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}(X\cap
Y))\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}Y$. However, in general,
it is unclear whether such an expression can be obtained. Before continuing,
let us give a first toy example.

######  Example 1.1.

Consider the set family $\mathcal{F}=\\{S_{1},S_{2},S_{3}\\}$ with
$S_{1}=\\{a,b,d\\}$, $S_{2}=\\{a,b,c,e\\}$, $S_{3}=\\{a,c,f\\}$. Then:

$\displaystyle|S_{1}\cup S_{2}\cup S_{3}|$
$\displaystyle=|S_{1}|+|S_{2}|+|S_{3}|$ $\displaystyle\phantom{=}-(|S_{1}\cap
S_{2}|+|S_{1}\cap S_{3}|+|S_{2}\cap S_{3}|)$
$\displaystyle\phantom{=}+|S_{1}\cap S_{2}\cap S_{3}|.$

Since we have $S_{1}\cap S_{3}=S_{1}\cap S_{2}\cap S_{3}$, we obtain

$\displaystyle|S_{1}\cup S_{2}\cup S_{3}|$
$\displaystyle=|\\{a,b,d\\}|+|\\{a,b,c,e\\}|+|\\{a,c,f\\}|-|\\{a,b\\}|-|\\{a,c\\}|.$

The non-cancelling intersections are the ones that remain, i.e.,
$\\{a,b,d\\}$, $\\{a,b,c,e\\}$, $\\{a,c,f\\}$, $\\{a,b\\}$, and $\\{a,c\\}$,
while $\\{a\\}$ ($=S_{1}\cap S_{3}=S_{1}\cap S_{2}\cap S_{3}$) is a cancelling
term.

Then, we can express $S_{1}\cup S_{2}\cup S_{3}=\\{a,b,c,d,e,f\\}$ with
$\big{[}\big{(}(\\{a,b,d\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\\{a,b\\})\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{a,b,c,e\\}\big{)}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\\{a,c\\}\big{]}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{a,c,f\\}$:
the reader can easily check that each
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$ (resp., each
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$) is a valid disjoint
union (resp., subset complement), and that we have only used the non-
cancelling intersections. Note that this is not the only valid expression, for
instance we can also obtain the union with the expression
$[\\{a,b,d\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\\{a,b\\}]\cup[\\{a,b,c,e\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\\{a,c\\}]\cup\\{a,c,f\\}$.

Our results imply that it is always possible when there are no cancellations
(Fact 4.8), or exactly one cancellation (in the equivalent formulation on
Boolean lattices, Theorem 6.2), but in general it seem challenging to do so
while avoiding those intersections which cancel out. The goal of this note is
to present the current status of our efforts in attacking the conjecture, in
particular showcasing some equivalent formulations, presenting examples, and
establishing a very partial result. After presenting preliminaries in Section
2, we formally state the conjecture and give examples in Section 3. We show in
Section 4 that it suffices to study the conjecture on specific intersection
lattices, which we call _tight_ , where informally the set family ensures that
every possible intersection contains exactly one element that is “specific” to
this intersection (in the sense that it is present precisely in this
intersection and in larger intersections). We use this in Section 5 to give an
alternative formulation: instead of working with intersection lattices, we can
work with downsets on the Boolean lattice. We show that this is equivalent to
the original conjecture. The hope is that the setting of the Boolean lattice
can be more convenient to work with, as its structure is more restricted, and
we can define quantities such as the Euler characteristic that seem useful in
understanding the structure of the problem.

We next present in Section 6 a partial result that we can show in the context
of the Boolean lattice. In the rephrased problem, we must express a downset of
that lattice using disjoint union and subset complement on principal downsets
spanned by elements which do not “cancel out” in the sense of having non-zero
Möbius value. Our result establishes that the rephrased conjecture is true
when there is one single node of the downset that has such value; this non-
trivially extends the fact that the result is true when no such nodes exist
(Lemma 5.7), but falls short of the goal as in general many such zeroes can
occur.

We conclude in Section 7 with further questions and directions on the
conjecture. We point out that the conjecture can be strengthened, in two
different ways, to restrict the shape of the disjoint-union and subset-
complement expressions: we also do not know the status of these stronger
conjectures. We briefly report on an unsuccessful experimental search for
counterexamples. We also hint at an incomplete proof of another partial result
where we can avoid more than one zero, provided the targeted downset satisfies
a certain decomposability condition.

##  2 Preliminaries

For a set $S$ we write $2^{S}$ its powerset. In this work, by _family of sets_
, or simply _set family_ , we always mean a finite set of (not necessarily
finite) sets. We generally use cursive letters to denote set families,
uppercase letters to denote sets, and lowercase letters for elements of sets.
For a set family $\mathcal{F}$ (resp., non-empty set family $\mathcal{F}$) we
write $\bigcup\mathcal{F}$ (resp., $\bigcap\mathcal{F}$) for
$\bigcup_{X\in\mathcal{F}}X$ (resp., $\bigcap_{X\in\mathcal{F}}X$). For a set
$X$ and two functions $f,g\colon X\to\mathbb{Z}$, we write $f+g$ (resp.,
$f-g$) the function defined by
$(f+g)(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}f(x)+g(x)$ (resp.,
$(f-g)(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}f(x)-g(x)$) for all $x\in
X$.

#### Posets.

Recall that a _poset_ $P=(A,\leq)$ is a pair consisting of a set $A$ and a
binary _partial order_ relation $\leq$ over $A$ that is reflexive,
antisymmetric and transitive. By slight abuse of notation, we may write $x\in
P$ to mean $x\in A$ (and $U\subseteq P$ to mean $U\subseteq A$).

A _greatest_ (resp., _least_) element of $P$ is an element $x\in P$ such that
for all $x^{\prime}\in P$ we have $x^{\prime}\leq x$ (resp., $x\leq
x^{\prime}$). When such an element exists it is unique, and we then denote it
by $\hat{1}$ (resp., $\hat{0}$). We may write $\hat{0}_{P},\hat{1}_{P}$ to
avoid confusion when multiple posets are involved.

For $G\subseteq A$, we define the _upset of $P$ generated by $G$_ (also called
an _order filter_), denoted $\uparrow_{P}(G)$, by
$\uparrow_{P}(G)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{x\in P\mid\exists
y\in G\text{~{}s.t.~{}}y\leq x\\}$. We also define the _downset generated by
$G$_ (also called an _order ideal_), denoted $\downarrow_{P}(G)$, by
$\downarrow_{P}(G)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{x\in
P\mid\exists y\in G\text{~{}s.t.~{}}x\leq y\\}$. Note that
$\uparrow_{P}(\emptyset)=\downarrow_{P}(\emptyset)=\emptyset$. An _upset_
(resp., a _downset_) of $P$ is a subset of $P$ of the form $\uparrow_{P}(G)$
(resp., $\downarrow_{P}(G)$) for $G\subseteq A$. When $|G|=1$ we call
$\uparrow_{P}(G)$ (resp., $\downarrow_{P}(G)$) a _principal upset_ (resp.,
_principal downset_), and by slight abuse of notation we sometimes write
$\uparrow_{P}(x)$ for $x\in P$ to mean $\uparrow_{P}(\\{x\\})$ (resp.,
$\downarrow_{P}(x)$ to mean $\downarrow_{P}(\\{x\\})$).

Two posets $P_{1}=(A_{1},\leq_{1})$ and $P_{2}=(A_{2},\leq_{2})$ are
_isomorphic_ if there exists a bijection $h\colon A_{1}\to A_{2}$ such that
for all $x,y\in P_{1}$ we have $x\leq_{1}y$ iff $h(x)\leq_{2}h(y)$. When this
is the case we write $P_{1}\simeq P_{2}$.

#### Lattices.

A poset $P=(A,\leq)$ is a _meet semilattice_ if, for every $x,y\in P$, there
exists $z\in P$ such that: (1) $z\leq x$ and $z\leq y$; and (2) for every
$z^{\prime}\in P$ such that $z^{\prime}\leq x$ and $z^{\prime}\leq y$, we have
$z^{\prime}\leq z$. This element $z$ is then unique and is called the _meet of
$x$ and $y$_, and written
$x\mathrel{\text{\raisebox{1.07639pt}{\scalebox{0.8}{$\wedge$}}}}y$. We
similarly define _join semilattices_ in the expected way, with the join
denoted $x\mathrel{\text{\raisebox{1.07639pt}{\scalebox{0.8}{$\vee$}}}}y$, and
then _lattices_ as posets that are both a meet semilattice and a join
semilattice.

We recall that a finite join (resp., meet) semilattice that has a least
(resp., greatest) element is a lattice (see, e.g., [Stanley, 2011, Proposition
3.3.1]). We also recall the property that in a meet semilattice $L$, the
intersection of two principal downsets $\downarrow_{L}(x)$ and
$\downarrow_{L}(y)$ generated by $x,y\in L$ is the principal downset generated
by $x\mathrel{\text{\raisebox{1.07639pt}{\scalebox{0.8}{$\wedge$}}}}y$; the
dual property holds about principal upsets in join semilattices with the join
operation.

For a set $S$ we write $\mathbbm{B}_{S}$ the Boolean lattice over $S$, by
which we mean the lattice $(2^{S},\subseteq)$, where join corresponds to set
union and meet to set intersection.

######  Definition 2.1.

A set family $\mathcal{F}$ is called _trivial_ if it is empty or if there is
$X\in\mathcal{F}$ such that $\bigcup\mathcal{F}=X$, and _non-trivial_
otherwise.

We define the standard notion of _intersection lattice_ of a non-trivial set
family:

######  Definition 2.2 ([Stanley, 2011], Section 3.7.2).

Let $\mathcal{F}$ be a non-trivial set family. For
$\mathcal{T}\subseteq\mathcal{F}$, $\mathcal{T}\neq\emptyset$, we define:
$S_{\mathcal{T}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\bigcap\mathcal{T}$.
We also define
$S_{\emptyset}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\bigcup\mathcal{F}$
with a slight abuse of notation as $S_{\emptyset}$ depends on the underlying
set family $\mathcal{F}$.

Define the poset $\mathbbm{L}_{\mathcal{F}}=(\mathcal{A},\subseteq)$, where
$\mathcal{A}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{S_{\mathcal{T}}\mid\mathcal{T}\subseteq\mathcal{F}\\}$.
Then one can check that $\mathbbm{L}_{\mathcal{F}}$ is a meet semilattice
whose meet operation is set intersection. We call $\mathbbm{L}_{\mathcal{F}}$
_the intersection lattice_ of $\mathcal{F}$. We say that a lattice $L$ is _an
intersection lattice_ if it is of the form $\mathbbm{L}_{\mathcal{F}}$ for
some non-trivial set family $\mathcal{F}$. (Note that we might have
$\mathbbm{L}_{\mathcal{F}_{1}}=\mathbbm{L}_{\mathcal{F}_{2}}$ for
$\mathcal{F}_{1}\neq\mathcal{F}_{2}$.)

######  Remark 2.3.

Every finite lattice $L=(A,\leq)$ is isomorphic to some intersection lattice.
Indeed, define
$\mathcal{F}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{\downarrow_{L}(\\{U\\})\mid
U\in A,U\neq\hat{1}_{L}\\}$, i.e., the set of principal downsets of $L$ except
$\downarrow_{L}(\\{\hat{1}_{L}\\})$ (as otherwise $\mathcal{F}$ is trivial).
Then one can easily check that $L\simeq\mathbbm{L}_{\mathcal{F}}$, since
$\downarrow_{L}(\\{U\\})\cap\downarrow_{L}(\\{V\\})=\downarrow_{L}(U\wedge_{L}V)$
for $U,V\in A$.

Such a lattice $L=\mathbbm{L}_{\mathcal{F}}$ has a $\hat{0}$, which is
$S_{\mathcal{F}}=\bigcap\mathcal{F}$, and a $\hat{1}$, which is
$S_{\emptyset}=\bigcup\mathcal{F}$. Notice that $\hat{1}\neq\hat{0}$ because
$\mathcal{F}$ is non-trivial. Since $L$ is a finite meet-semilattice that has
a $\hat{1}$, we know that $L$ is also a join-semilattice by the property
mentioned above, but for the purpose of this note we will not need to know
what the join operation corresponds to. Note that by definition
$S_{\mathcal{T}_{1}\cup\mathcal{T}_{2}}=S_{\mathcal{T}_{1}}\cap
S_{\mathcal{T}_{2}}$ for any
$\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\mathcal{F}$. Observe that we may
have $S_{\mathcal{T}_{1}}=S_{\mathcal{T}_{2}}$ with
$\mathcal{T}_{1}\neq\mathcal{T}_{2}$, in which case
$S_{\mathcal{T}_{1}}=S_{\mathcal{T}_{2}}=S_{\mathcal{T}_{1}\cup\mathcal{T}_{2}}$.

######  Example 2.4.

Figure 1 shows the Hasse diagrams of the various intersection lattices defined
next. (Ignore for now the integer annotations next to the nodes and the fact
that some nodes are colored.)

$L_{1}$.

The intersection lattice $L_{1}$ of (the non-trivial set family containing)
$S_{1}=\\{n\in\mathbb{N}\mid n\equiv 0\pmod{2}\\}$,
$S_{2}=\\{n\in\mathbb{N}\mid n\equiv 0\pmod{3}\\}$, and
$S_{3}=\\{n\in\mathbb{N}\mid n\equiv 0\pmod{12}\\}$ is shown in Figure 1(a).

$L_{2}$.

The intersection lattice $L_{2}$ of $S_{1}=\\{a,d\\}$, $S_{2}=\\{b,d\\}$, and
$S_{3}=\\{c,d\\}$ is shown in Figure 1(b). This example illustrates that an
intersection lattice is not necessarily distributive.

$L_{3}$.

The intersection lattice $L_{3}$ of $S_{1}=\\{a,b\\}$, $S_{2}=\\{a,c\\}$,
$S_{3}=\\{b,c\\}$, and $S_{4}=\\{d\\}$ is shown in Figure 1(c).

$L_{4}$.

The intersection lattice $L_{4}$ of $S_{1}=\\{a,c,d,g\\}$,
$S_{2}=\\{a,b,d,f\\}$, $S_{3}=\\{a,b,c,e\\}$, and $S_{4}=\\{a,h\\}$ is shown
in Figure 1(d). Observe that $L_{3}$ and $L_{4}$ are isomorphic.

Finally, another intersection lattice $L_{5}$ is depicted in Figure 2 (ignore
for now the tree).

$\\{n\in\mathbb{N}\mid n\equiv 0\pmod{2}\text{ or }n\equiv
0\pmod{3}\\}$$\\{n\in\mathbb{N}\mid n\equiv
0\pmod{2}\\}$$\\{n\in\mathbb{N}\mid n\equiv
0\pmod{3}\\}$$\\{n\in\mathbb{N}\mid n\equiv
0\pmod{6}\\}$$\\{n\in\mathbb{N}\mid n\equiv 0\pmod{12}\\}$$1$$-1$$-1$$1$$0$

(a) Lattice $L_{1}$

$\\{a,b,c,d\\}$$\\{a,d\\}$$\\{b,d\\}$$\\{c,d\\}$$\\{d\\}$$1$$-1$$-1$$-1$$2$

(b) Lattice $L_{2}$

$\\{a,b,c,d\\}$$\\{d\\}$$\\{a,b\\}$$\\{a\\}$$\\{a,c\\}$$\\{b\\}$$\\{b,c\\}$$\\{c\\}$$\emptyset$$1$$-1$$-1$$1$$-1$$-1$$1$$1$$0$

(c) Lattice $L_{3}$

$\\{a,b,c,d,e,f,g,h\\}$$\\{a,h\\}$$\\{a,c,d,g\\}$$\\{a,d\\}$$\\{a,b,d,f\\}$$\\{a,c\\}$$\\{a,b,c,e\\}$$\\{a,b\\}$$\\{a\\}$$1$$-1$$-1$$1$$-1$$-1$$1$$1$$0$

(d) Lattice $L_{4}$

Figure 1: Hasse diagrams of the intersection lattices from Example 2.4. The
integer value besides each node $n$ is $\mu_{L}(n,\hat{1})$ and is computed
top-down following Definition 2.6. The orange nodes are the non-cancelling
non-trivial intersections.

$abb^{\prime}cc^{\prime}dee^{\prime}ff^{\prime}gg^{\prime}$1$abb^{\prime}d\vphantom{f}$$-1$$abc^{\prime}f^{\prime}$$-1$$ab^{\prime}c^{\prime}e^{\prime}\vphantom{b^{\prime}f}$$-1$$ag^{\prime}\vphantom{b^{\prime}f}$$-1$$ab^{\prime}cf\vphantom{b^{\prime}f}$$-1$$abce\vphantom{b^{\prime}f}$$-1$$ag\vphantom{g^{\prime}f}$$-1$$ab^{\prime}\vphantom{b^{\prime}f}$2$ac^{\prime}\vphantom{b^{\prime}f}$1$ab\vphantom{b^{\prime}f}$2$ac\vphantom{b^{\prime}f}$1$a$0

$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$abce$$ab$$abc^{\prime}f^{\prime}$$ac^{\prime}$$ag$$ac$$ab^{\prime}cf$$ab^{\prime}$$ag^{\prime}$$ab$$abb^{\prime}d$$ab^{\prime}$$ab^{\prime}c^{\prime}e^{\prime}$$abb^{\prime}cc^{\prime}dee^{\prime}ff^{\prime}gg^{\prime}$$ce$$abcec^{\prime}f^{\prime}$$bcef^{\prime}$$abcef^{\prime}g$$bef^{\prime}g$$abb^{\prime}ceff^{\prime}g$$bceff^{\prime}g$$abceff^{\prime}gg^{\prime}$$ceff^{\prime}gg^{\prime}$$abb^{\prime}cdeff^{\prime}gg^{\prime}$$bcdeff^{\prime}gg^{\prime}$

Figure 2: A tight intersection lattice of seven sets, and a witnessing tree
showing that it does not violate the conjecture. For brevity we omit curly
braces and commas when writing sets, i.e., $ab$ stands for $\\{a,b\\}$.

In an intersection lattice $L=\mathbbm{L}_{\mathcal{F}}$, for every
$x\in\hat{1}$, the set of elements of $L$ in which $x$ occurs is the principal
upset of $L$ generated by
$\min_{L}(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}S_{\\{X\in\mathcal{F}\mid
x\in X\\}}$. Note that $\min_{L}(x)\neq\hat{1}$ because $\mathcal{F}$ is non-
trivial. In particular we have the following:

######  Fact 2.5.

Let $L$ be an intersection lattice and $U\in L$. Then we have
$U=\bigcup_{\begin{subarray}{c}U^{\prime}\in L\\\ U^{\prime}\subseteq
U\end{subarray}}\\{x\in\hat{1}\mid U^{\prime}=\min_{L}(x)\\}$, and this union
is disjoint.

#### Möbius inversion formula and inclusion-exclusion.

We now introduce the _Möbius function_ on finite posets.

######  Definition 2.6.

Let $P=(A,\leq)$ be a finite poset. The _Möbius function_ of $P$ is the
function $\mu_{P}$ with value in $\mathbb{Z}$ and domain the set of pairs
$(x,y)\in A\times A$ such that $x\leq y$, defined, for each $y\in A$, by
induction over the elements $x$ such that $x\leq y$:

  * •

$\mu_{P}(y,y)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}1$;

  * •

$\mu_{P}(x,y)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}-\sum_{x<z\leq
y}\mu_{P}(z,y)$.111The Möbius function is traditionally defined with
$\mu_{P}(x,y)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}-\sum_{x\leq
z<y}\mu_{P}(x,z)$, but the two definitions are equivalent [Rota, 1964,
Proposition 3]. We use this version as it simplifies our presentation.

######  Proposition 2.7 (Möbius inversion formula; see, e.g., Prop. 3.7.1 of
[Stanley, 2011]).

Let $P=(A,\leq)$ be a finite poset, and let $f,g\colon A\to\mathbb{R}$. Then
we have:

$g(x)=\sum_{y\leq x}f(y)\text{~{}for all~{}}x\in P\text{~{}~{}~{}~{}if and
only if~{}~{}~{}~{}}f(x)=\sum_{y\leq x}\mu_{P}(y,x)g(y)\text{~{}for
all~{}}x\in P.$

One important application of the Möbius inversion formula is in determining
the _measure_ of a union of sets from the measure of some of their
intersections. For our purposes, given a set $S$, what we call a _measure on
$2^{S}$_ is a function $\xi\colon 2^{S}\to\mathbb{R}$ which is nonnegative
(i.e., $\xi(U)\geq 0$ for all $U\in 2^{S}$), which satisfies
$\xi(\emptyset)=0$, and which is additive under countable disjoint unions,
i.e., for any countable collection $\\{E_{k}\\}_{k=1}^{\infty}$ of pairwise
disjoint subsets of $S$, we have
$\xi\left(\bigcup_{k=1}^{\infty}E_{k}\right)=\sum_{k=1}^{\infty}\xi(E_{k})$.
In particular, $\xi$ is completely determined by the images of the singleton
sets $\\{x\\}$ for $x\in S$.

######  Proposition 2.8.

Let $L$ be an intersection lattice, and let $\xi$ be a measure on
$2^{\hat{1}}$. Then we have

$\xi(\hat{1})=-\sum_{\begin{subarray}{c}U\in L\\\
U\neq\hat{1}\end{subarray}}\mu_{L}(U,\hat{1})\xi(U).$ (1)

###### Proof.

This is a known result but, to be self-contained, we reproduce the proof from
[Stanley, 2011] (end of Section 3.7, page 304). Let us define two functions
$f,g\colon L\to\mathbb{R}$. For $U\in L$, let
$g(U)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\xi(U)$, and define $f(U)$ to
be the measure of all elements of $U$ which belong to no $U^{\prime}\subsetneq
U$, i.e.,
$f(U)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\xi(\\{x\in\hat{1}\mid\min_{L}(x)=U\\})$.
Observe that $g(U)=\sum_{\begin{subarray}{c}U^{\prime}\in L\\\ U^{\prime}\leq
U\end{subarray}}f(U^{\prime})$ for all $U\in L$, by additivity of $\xi$ and
using Fact 2.5. Therefore by Proposition 2.7 we have that
$f(\hat{1})=\sum_{U\in L}\mu_{L}(U,\hat{1})g(U)$. But notice that
$g(\hat{1})=\xi(\hat{1})$ and that $f(\hat{1})=\xi(\emptyset)$ (because
$L=\mathbbm{L}_{\mathcal{F}}$ for some $\mathcal{F}$ non-trivial), so that
$f(\hat{1})=0$. Therefore indeed $\xi(\hat{1})=-\sum_{\begin{subarray}{c}U\in
L\\\ U\neq\hat{1}\end{subarray}}\mu_{L}(U,\hat{1})\xi(U)$. ∎

We point out that the above proposition can fail if the underlying set family
$\mathcal{F}$ is trivial222Take for instance
$\mathcal{F}=\\{\\{a,b\\},\\{a\\}\\}$.: this is the reason why we always work
with non-trivial families of sets.

######  Example 2.9.

For the lattices $L_{1},L_{2},L_{3},L_{4},L_{5}$ from Example 2.4, the values
$\mu_{L_{i}}(U,\hat{1})$ for all elements $U\in L_{i}$ are shown next to the
corresponding nodes in Figures 1 and 2.

This motivates the following definitions.

######  Definition 2.10.

Let $L$ be an intersection lattice. We call $\hat{1}$ the _trivial
intersection_. We define the _non-trivial intersections of $L$_, denoted
$\mathtt{NTI}(L)$, by

$\mathtt{NTI}(L)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{U\in L\mid
U\neq\hat{1}\\},$

and we define the _non-cancelling, non-trivial intersections_ (or simply _non-
cancelling intersections_) of $L$, denoted $\mathtt{NCI}(L)$, by

$\mathtt{NCI}(L)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{U\in L\mid
U\neq\hat{1}\text{ and }\mu_{L}(U,\hat{1})\neq 0\\}.$

In other words, the non-cancelling intersections are those intersections that
do not cancel in the inclusion-exclusion formula, i.e., those $U$ such that
$\xi(U)$ occur in Equation (1) with non-zero coefficient.

Last, we will also need the following application of the Möbius inversion
formula, which is another formulation of the inclusion-exclusion principle.

######  Proposition 2.11.

Let $S$ be a finite set, and let $f,g\colon\mathbbm{B}_{S}\to\mathbb{R}$. Then
we have $g(X)=\sum_{\begin{subarray}{c}X^{\prime}\in\mathbbm{B}_{S}\\\
X\subseteq X^{\prime}\end{subarray}}f(X^{\prime})$ for all
$X\in\mathbbm{B}_{S}$ if and only if
$f(X)=\sum_{\begin{subarray}{c}X^{\prime}\in\mathbbm{B}_{S}\\\ X\subseteq
X^{\prime}\end{subarray}}(-1)^{|X^{\prime}|-|X|}g(X^{\prime})$ for all
$X\in\mathbbm{B}_{S}$.

This result can be obtained by observing that
$\mu_{\mathbbm{B}_{S}}(X,Y)=(-1)^{|Y|-|X|}$ for $X\subseteq Y$ as shown in
[Stanley, 2011, Example 3.8.1] and using the dual form of the Möbius inversion
formula [Stanley, 2011, Proposition 3.7.2].

##  3 The Non-Cancelling Intersections Conjecture

In this section we state the conjecture and illustrate it with a few toy
examples. We adapt to our context notation and terminology from [Hirsch and
McLean, 2017] for disjoint unions and subset complements.

######  Definition 3.1.

For two sets $S,T$, the _disjoint union_
$S\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}T$ equals $S\cup T$ if
$S\cap T=\emptyset$, else it is undefined. We generalize the disjoint union
operator to more than two operands in the expected way. The _subset
complement_ $S\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}T$ equals
$S\setminus T$ if $T\subseteq S$, else it is undefined.

Notice that

$S\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}T=U\text{ iff
}U\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}S=T\text{ iff
}U\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}T=S.$ (2)

######  Definition 3.2.

Let $\mathcal{F}$ be a set family. The _partial dot-algebra generated by
$\mathcal{F}$_, denoted $\bullet(\mathcal{F})$, is the smallest (for
inclusion) set family of subsets of $2^{\bigcup\mathcal{F}}$ which contains
$\emptyset$ as well as all the sets of $\mathcal{F}$ and is closed under
disjoint union and subset complement. Formally, it is defined inductively by:

  1. 1.

First base case: $\emptyset\in\bullet(\mathcal{F})$;

  2. 2.

Second base case: for each $X\in\mathcal{F}$, we have
$X\in\bullet(\mathcal{F})$;

  3. 3.

Induction: for each $X_{1},X_{2}\in\bullet(\mathcal{F})$, if
$X_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}X_{2}$ (resp.,
$X_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}X_{2}$) is well-
defined, then we have
$X_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}X_{2}\in\bullet(\mathcal{F})$
(resp.,
$X_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}X_{2}\in\bullet(\mathcal{F})$).

Note that when $\mathcal{F}$ is not empty, then item (1) is redundant as it
follows from (2) and (3): taking any $X\in\mathcal{F}$, we have
$X\in\bullet(\mathcal{F})$ by item (2), and
$X\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}X=\emptyset\in\bullet(\mathcal{F})$
by item (3).

Furthermore, observe that $\bullet(\mathcal{F})$ is always finite because
$\mathcal{F}$ is. What we call a _witnessing tree of
$X\in\bullet(\mathcal{F})$_ is a rooted ordered tree whose leaves are
annotated with $\emptyset$ or with elements of $\mathcal{F}$ and whose
internal nodes are annotated with either
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$ or
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$ (with the node being
binary if it is is annotated with
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$), with the expected
semantics. Obviously, we have $X\in\bullet(\mathcal{F})$ if and only if such a
witnessing tree exists.

######  Example 3.3.

Let $\mathcal{F}_{1}=\\{\\{a,d\\},\\{b,e\\},\\{a,b,c\\}\\}$. Then
$\bullet(\mathcal{F}_{1})=\mathcal{F}_{1}\cup\\{\emptyset,\\{a,b,d,e\\}\\}$.
Let $\mathcal{F}_{2}=\\{\\{a,c\\},\\{b,c\\},\\{c\\}\\}$. Then we have
$\bullet(\mathcal{F}_{2})=2^{\\{a,b,c\\}}$. Two trees $T_{0},T^{\prime}_{0}$
which witness that $\\{a,b,c\\}\in\bullet(\mathcal{F}_{2})$ are shown in
Figure 3.

$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\\{a,c\\}$$\\{c\\}$$\\{b,c\\}$$\\{a,b,c\\}$$\\{a\\}$

(a) Tree $T_{0}$

$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\\{a,c\\}$$\\{c\\}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\\{b,c\\}$$\\{c\\}$$\\{c\\}$$\\{a,b,c\\}$$\\{a\\}$$\\{b\\}$

(b) Tree $T^{\prime}_{0}$

$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\\{a,c,d,g\\}$$\\{a,c\\}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\\{a,b,d,f\\}$$\\{a,d\\}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\\{a,b,c,e\\}$$\\{a,b\\}$$\\{a,h\\}$$\\{a,b,c,d,e,f,g,h\\}$$\\{d,g\\}$$\\{b,f\\}$$\\{c,e\\}$

(c) Tree $T_{1}$

$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\\{a,c,d,g\\}$$\\{a,c\\}$$\\{a,b,c,e\\}$$\\{a,b\\}$$\\{a,h\\}$$\\{a,d\\}$$\\{a,b,d,f\\}$$\\{a,b,c,d,e,f,g,h\\}$$\\{d,g\\}$$\\{a,b,c,d,e,g\\}$$\\{c,d,e,g\\}$$\\{a,c,d,e,g,h\\}$$\\{c,e,g,h\\}$

(d) Tree $T^{\prime}_{1}$

$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$$\\{a,b\\}$$\\{b\\}$$\\{b,c\\}$$\\{c\\}$$\\{d\\}$$\\{a\\}$$\\{a,c\\}$$\\{a,b,c,d\\}$$\\{a\\}$$\\{a,b,c\\}$$\\{a,b\\}$$\\{a,b,d\\}$$\\{b,d\\}$

(e) Tree $T_{2}$

Figure 3: Various witnessing trees. The sets that internal nodes correspond to
are shown in orange.

We are now ready to state the conjecture.

######  Conjecture 3.4 ($\mathtt{NCI}$ conjecture, formulation I).

For every intersection lattice $L$, we have
$\hat{1}\in\bullet(\mathtt{NCI}(L))$.

In other words, the conjecture states that, given any non-trivial set family,
we can always express the union of the sets by starting with the set
intersections that do not cancel in the inclusion-exclusion formula and
applying the disjoint union and subset complement operators.

######  Example 3.5.

Continuing Example 2.4, the nodes corresponding to sets of
$\mathtt{NCI}(L_{i})$ are colored in orange in Figure 1: they are the nodes
different from $\hat{1}$ with a non-zero value of the Möbius function. We show
next that $\hat{1}\in\bullet(\mathtt{NCI}(L_{i}))$ for all of them.

$L_{1}$.

We have $\hat{1}=\\{n\in\mathbb{N}\mid n\equiv 0\pmod{2}\text{ or }n\equiv
0\pmod{3}\\}=[\\{n\in\mathbb{N}\mid n\equiv
0\pmod{2}\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\\{n\in\mathbb{N}\mid
n\equiv
0\pmod{6}\\}]\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{n\in\mathbb{N}\mid
n\equiv 0\pmod{3}\\}$.

$L_{2}$.

We have
$\hat{1}=\\{a,b,c,d\\}=[\\{a,d\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\\{d\\}]\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}[\\{b,d\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\\{d\\}]\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}[\\{c,d\\}]$.

$L_{3}$.

We have
$\hat{1}=\\{a,b,c,d\\}=\\{a\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{b\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{c\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{d\\}$.

$L_{4}$.

Two trees $T_{1},T^{\prime}_{1}$ which witness that
$\hat{1}\in\bullet(\mathtt{NCI}(L_{4}))$ can be found in Figure 3.

$L_{5}$.

A witnessing tree for $L_{5}$ can be found in Figure 2.

The motivation for the conjecture is to understand whether the inclusion-
exclusion formula can be understood using the Boolean operations of disjoint
union and subset complement. Specifically, let $\mathcal{F}$ be a non-trivial
set family, consider its intersection lattice $\mathbbm{L}_{\mathcal{F}}$,
recall that $\hat{1}=\bigcup\mathcal{F}$, and let $\xi$ be a measure on
$2^{\hat{1}}$. We know that the measure of $\hat{1}$ can be obtained from the
measure of the non-cancelling intersections, namely, Proposition 2.8 expresses
the measure $\xi(\hat{1})$ of the set $\hat{1}$ as an arithmetic combination
of the measures $\xi(S)$ with $S\in\mathtt{NCI}(L)$. The conjecture says that
we can also express the _set_ $\hat{1}$ from the _sets_ $S$ with
$S\in\mathtt{NCI}(L)$ using the Boolean operations of disjoint union and
subset complement.

#### Dual version: non-cancelling unions conjecture.

We end this section by presenting a dual version of the $\mathtt{NCI}$
conjecture that focuses on unions instead of intersections, and that we call
the _non-cancelling unions_ ($\mathtt{NCU}$) conjecture. Call a set family
$\mathcal{F}$ _co-trivial_ if it is empty or if there is $X\in\mathcal{F}$
such that $X=\bigcap\mathcal{F}$, and _non-co-trivial otherwise_. Define the
_union lattice_ $\mathbbm{U}_{\mathcal{F}}$ of a non-co-trivial set family
$\mathcal{F}$ as follows: let
$R_{\emptyset}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\bigcap\mathcal{F}$
and
$R_{\mathcal{T}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\bigcup\mathcal{T}$
for $\mathcal{T}\subseteq\mathcal{F}$, $\mathcal{T}\neq\emptyset$, and
$\mathbbm{U}_{\mathcal{F}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}(\\{R_{\mathcal{T}}\mid\mathcal{T}\subseteq\mathcal{F}\\},\subseteq)$.
Then $\mathbbm{U}_{\mathcal{F}}$ is a lattice whose join operation corresponds
to set union, has a greatest element $\hat{1}=\bigcup\mathcal{F}$ and a least
element $\hat{0}=\bigcap\mathcal{F}$ that are distinct. A lattice is a union
lattice if it is of the form $\mathbbm{U}_{\mathcal{F}}$ for some non-co-
trivial set family. Analogously to Proposition 2.8, it is easy to show that
for a union lattice $L$ and measure $\xi$ on $2^{\hat{1}}$, we have

$\xi(\hat{0})=-\sum_{\begin{subarray}{c}U\in L\\\
U\neq\hat{0}\end{subarray}}\mu_{L}(\hat{0},U)\xi(U).$ (3)

Define then the _non-cancelling (non-trivial) unions of $L$_ as

$\mathtt{NCU}(L)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{U\in L\mid
U\neq\hat{0},\mu_{L}(\hat{0},U)\neq 0\\}.$

The non-cancelling unions conjecture is then:

######  Conjecture 3.6 ($\mathtt{NCU}$ conjecture).

For every union lattice $L$, we have $\hat{0}\in\bullet(\mathtt{NCU}(L))$.

Notice here that the definition of the dot-algebra is unchanged: we still use
disjoint complement and disjoint union. Informally again, this is stating
that, given a set family, we can always express their intersection by applying
the disjoint union and subset complement operations to the set unions that do
not cancel in the (“union form” of the) inclusion-exclusion formula.

We show in Appendix LABEL:apx:conj that, unsurprisingly, the $\mathtt{NCI}$
and $\mathtt{NCU}$ conjectures are in fact equivalent. We decided to focus on
the intersections version of the conjecture because inclusion-exclusion is
most often presented in “intersection form”.

##  4 Simplifying to Tight Intersection Lattices

In this section we show that the $\mathtt{NCI}$ conjecture can be studied
without loss of generality on intersection lattices satisfying a certain
_tightness_ condition, that we define next. Intuitively, an intersection
lattice $L$ is _tight_ if for every $U\in L$, $U\neq\hat{1}$, there is exactly
one element $x\in\hat{1}$ such that $\min_{L}(x)=U$. We also define the notion
of an intersection lattice being _full_ , which will be useful in the next
section.

######  Definition 4.1.

An intersection lattice $L$ is _full_ if for every $U\in L$, $U\neq\hat{1}$,
we have $\\{x\in\hat{1}\mid\min_{L}(x)=U\\}\neq\emptyset$.333Note that
$\\{x\in\hat{1}\mid\min_{L}(x)=\hat{1}\\}=\emptyset$ because $\mathcal{F}$ is
non-trivial. The lattice $L$ is in addition called _tight_ if for every $U\in
L$, $U\neq\hat{1}$, we have $|\\{x\in\hat{1}\mid\min_{L}(x)=U\\}|=1$.

For instance, the intersection lattices $L_{2}$ and $L_{4}$ from Figure 1 and
$L_{5}$ from Figure 2 are tight (hence full), $L_{1}$ is full but not tight,
and $L_{3}$ is not full (hence not tight). Note that if an intersection
lattice $L=\mathbbm{L}_{\mathcal{F}}$ is tight, then $\hat{1}$ is finite,
i.e., the sets in $\mathcal{F}$ are themselves finite: this can be seen by
applying Fact 2.5 with $U=\hat{1}$. We then claim that we can reformulate the
$\mathtt{NCI}$ conjecture as follows:

######  Conjecture 4.2 ($\mathtt{NCI}$ conjecture, formulation II).

For every _tight_ intersection lattice $L$, we have
$\hat{1}\in\bullet(\mathtt{NCI}(L))$.

We prove this in two steps. First, we show that for every intersection lattice
$L$, there exists a _tight_ intersection lattice $L^{\prime}$ that is
isomorphic to $L$.

######  Lemma 4.3.

For every intersection lattice $L$, there exists a tight intersection lattice
$L^{\prime}$ such that $L\simeq L^{\prime}$.

###### Proof.

It suffices to observe that the intersection lattice constructed in Remark 2.3
(call it $L^{\prime}$) is tight. Indeed, letting $U\in
L\setminus\\{\hat{1}_{L}\\}$, corresponding to $\downarrow_{L}(\\{U\\})$ in
$L^{\prime}$, we have that
$\\{x\in\hat{1}_{L^{\prime}}\mid\min_{L^{\prime}}(x)=\downarrow_{L}(\\{U\\})\\}=\\{U\\}$.
∎

Second, we show that, for two isomorphic intersection lattices $L,L^{\prime}$
such that $L^{\prime}$ is full, then
$\hat{1}_{L^{\prime}}\in\bullet(\mathtt{NCI}(L^{\prime}))$ implies
$\hat{1}_{L}\in\bullet(\mathtt{NCI}(L))$.

######  Lemma 4.4.

Let $L,L^{\prime}$ be isomorphic intersection lattices such that $L^{\prime}$
is full and such that
$\hat{1}_{L^{\prime}}\in\bullet(\mathtt{NCI}(L^{\prime}))$. Then we have
$\hat{1}_{L}\in\bullet(\mathtt{NCI}(L))$.

###### Proof.

Let $h:L\to L^{\prime}$ be an isomorphism. Since $L^{\prime}$ is full, for
$U^{\prime}\in L^{\prime}$, $U^{\prime}\neq\hat{1}_{L^{\prime}}$, let
$\alpha_{U^{\prime}}$ be an element of
$\\{x^{\prime}\in\hat{1}_{L^{\prime}}\mid\min_{L^{\prime}}(x^{\prime})=U^{\prime}\\}$.
Define $g:\hat{1}_{L}\to\hat{1}_{L^{\prime}}$ by
$g(x)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\alpha_{h(\min_{L}(x))}$ for
$x\in\hat{1}_{L}$. Note that $g$ is not necessarily injective. For
$x^{\prime}\in\hat{1}_{L^{\prime}}$ let
$g^{-1}(x^{\prime})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{x\in\hat{1}_{L}\mid
g(x)=x^{\prime}\\}$, and for $X^{\prime}\subseteq\hat{1}_{L^{\prime}}$ let
$g^{-1}(X^{\prime})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\bigcup_{x^{\prime}\in
X^{\prime}}g^{-1}(x^{\prime})$. From Fact 2.5 and because $L^{\prime}$ is full
it is easy to see that ($\dagger$) for every $U^{\prime}\in L^{\prime}$ we
have $g^{-1}(U^{\prime})=h^{-1}(U^{\prime})$. In particular we have
$g^{-1}(\hat{1}_{L^{\prime}})=\hat{1}_{L}$. Hence, it is enough to prove that
for all $X^{\prime}\in\bullet(\mathtt{NCI}(L^{\prime}))$ we have
$g^{-1}(X^{\prime})\in\bullet(\mathtt{NCI}(L))$. We show this by induction on
$\mathtt{NCI}(L^{\prime})$. The first base case is when
$X^{\prime}=\emptyset$. But then observe that $g^{-1}(X^{\prime})=\emptyset$,
and that $\emptyset\in\bullet(\mathtt{NCI}(L))$ by definition. The second base
case is when $X^{\prime}\in\mathtt{NCI}(L^{\prime})$. But then
$g^{-1}(X^{\prime})\in\mathtt{NCI}(L)$ as well by ($\dagger$) and because $h$
is an isomorphism so clearly
$\mu_{L^{\prime}}(X^{\prime},\hat{1}_{L^{\prime}})=\mu_{L}(h^{-1}(X^{\prime}),\hat{1}_{L})$.
The first inductive case is when
$X^{\prime}=X^{\prime}_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}X^{\prime}_{2}$
with $X^{\prime}_{1},X^{\prime}_{2}\in\bullet(\mathtt{NCI}(L^{\prime}))$. By
induction hypothesis we have
$g^{-1}(X^{\prime}_{1}),g^{-1}(X^{\prime}_{2})\in\bullet(\mathtt{NCI}(L))$.
Moreover clearly $g^{-1}(X^{\prime}_{1})\cap g^{-1}(X^{\prime}_{2})=\emptyset$
since $X^{\prime}_{1}$ and $X^{\prime}_{2}$ are disjoint. So indeed
$g^{-1}(X^{\prime})=g^{-1}(X^{\prime}_{1})\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}g^{-1}(X^{\prime}_{2})\in\bullet(\mathtt{NCI}(L))$.
The second inductive case is when
$X^{\prime}=X^{\prime}_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}X^{\prime}_{2}$
with $X^{\prime}_{1},X^{\prime}_{2}\in\bullet(\mathtt{NCI}(L^{\prime}))$. By
induction hypothesis again we have
$g^{-1}(X^{\prime}_{1}),g^{-1}(X^{\prime}_{2})\in\bullet(\mathtt{NCI}(L))$.
Moreover clearly $g^{-1}(X^{\prime}_{2})\subseteq g^{-1}(X^{\prime}_{1})$
since $X^{\prime}_{2}\subseteq X^{\prime}_{1}$. So indeed
$g^{-1}(X^{\prime})=g^{-1}(X^{\prime}_{1})\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}g^{-1}(X^{\prime}_{2})\in\bullet(\mathtt{NCI}(L))$.
This concludes the proof. ∎

This indeed proves that the two formulations are equivalent. We illustrate
this last construction in the following example.

######  Example 4.5.

Consider the intersection lattices $L_{3}$ and $L_{4}$ from Figure 1, the
isomorphism $h:L_{3}\to L_{4}$ defined following their drawings, and
$\alpha_{U^{\prime}}$ for $U^{\prime}\in L_{4}$
$U^{\prime}\neq\hat{1}_{L_{4}}$ being the only element in
$\\{x^{\prime}\in\hat{1}_{L_{4}}\mid\min_{L_{4}}(x^{\prime})=U^{\prime}\\}$
(since $L_{4}$ is tight). Then we have, for instance, $g^{-1}(d)=\\{a\\}$,
$g^{-1}(a)=g^{-1}(f)=\emptyset$. Moreover, consider the tree $T^{\prime}_{1}$
from Figure 3(d) witnessing that
$\hat{1}_{L_{4}}\in\bullet(\mathtt{NCI}(L_{4}))$. Applying $g^{-1}$ to every
node of this tree yields the tree $T_{2}$ from Figure 3(e) that witnesses
$\hat{1}_{L_{4}}\in\bullet(\mathtt{NCI}(L_{4}))$. By contrast, consider the
expression
$\\{a\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{b\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{c\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{d\\}$
that also witnesses $\hat{1}_{L_{3}}\in\bullet(\mathtt{NCI}(L_{3}))$. This
expression cannot be translated through $h$ into a tree for $L_{4}$ as, e.g.,
the operation
$\\{b\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{c\\}$ would
translate to
$\\{a,c\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{a,b\\}$ in
$L_{4}$, which is not valid.

In fact we claim that, when $L$ is a full intersection lattice, any tree $T$
witnessing that $\hat{1}\in\bullet(\mathtt{NCI}(L))$ must use all of the sets
in $\mathtt{NCI}(L)$. (This is not the case of the expression
$\\{a\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{b\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{c\\}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\\{d\\}$
for $L_{3}$ for instance, but $L_{3}$ is not full.) In a sense, this means
that the full intersection lattices are the hardest cases for the
$\mathtt{NCI}$ conjecture. We formalize and state a stronger claim (on the
non-trivial intersections instead of only the non-cancelling ones) in the
remaining of this section.

######  Definition 4.6.

Let $\mathcal{F}$ be a set family, $X\in\bullet(\mathcal{F})$ and $T$ a tree
witnessing this. For a leaf $\ell$ of $T$, the _polarity of $\ell$ in $T$_,
denoted $\mathtt{pol}_{T}(\ell)$, is $1$ if the number of times we take the
right edge of a $\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$ node
in the path from the root of $T$ of $\ell$ is even; and $-1$ otherwise. The
_multiplicity of $U\in\mathcal{F}\cup\\{\emptyset\\}$ in $T$_ is then

$\mathtt{mult}_{T}(U)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{\begin{subarray}{c}\ell\text{
leaf of T}\\\ \text{of the form }U\end{subarray}}\mathtt{pol}_{T}(\ell).$

In other words, if we see each $U\in\mathcal{F}\cup\\{\emptyset\\}$ as a
variable and see $T$ as an arithmetic expression over these variables (by
replacing $\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$ nodes by $+$ and
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$ nodes by $-$), then
the multiplicity of $U$ in $T$ is the coefficient of the corresponding
variable once we develop this expression and factorize. We then have:

######  Proposition 4.7.

Let $L$ be a full intersection lattice such that
$\hat{1}\in\bullet(\mathtt{NTI}(L))$, and $T$ a tree witnessing this. Then we
have $\mathtt{mult}_{T}(U)=-\mu_{L}(U,\hat{1})$ for every
$U\in\mathtt{NTI}(L)$.

Since Proposition 4.7 will not be strictly needed to establish our main
results, we defer its proof to Appendix LABEL:apx:tight. (We include this
proposition as we think that it is relevant to motivate the conjecture.)
Notice that Proposition 4.7 can be false if we do not impose intersection
lattices to be full, see e.g., the expression for $L_{3}$ given in Example
3.5.

Furthermore, one can show that for any tight intersection lattice $L$ we have
$\bullet(\mathtt{NTI}(L))=2^{\hat{1}_{L}}$. In other words, intuitively, if we
use the non-trivial intersections instead of the non-canceling intersections
in the conjecture, then we can achieve all possible sets of elements:

######  Fact 4.8.

For every tight intersection lattice $L$ we have
$\bullet(\mathtt{NTI}(L))=2^{\hat{1}_{L}}$.

###### Proof.

Generalizing from tight intersection lattices, we will show that the result
holds more generally when we assume that for every $U\in L$, $U\neq\hat{1}$,
there is _at most_ one element $x\in\hat{1}$ such that $\min_{L}(x)=U$. Let
$L$ be an intersection lattice satisfying this weaker condition. We proceed by
induction on the downsets of $L$, showing the following by induction on $0\leq
n<|L|$: for any downset $D$ of $L$ containing $n$ nodes, letting
$X_{D}\subseteq\hat{1}$ be the set of elements introduced at nodes of $D$,
formally, $\\{x\in\hat{1}\mid\min_{L}(x)\in D\\}$, then we have
$\bullet(D)=2^{X_{D}}$. Note that, when taking this claim with $n=|L|-1$, then
the only downset $D$ of $L$ containing $|L|-1$ nodes is the downset $D$
containing all intersections except $S_{\emptyset}$, i.e., precisely
$\mathtt{NTI}(L)$, and then $X_{D}=\hat{1}$, so this claim with $n=|L|-1$ is
the result we want to show.

The base case is $n=0$, i.e., the downset $D=\emptyset$. Then
$X_{D}=\emptyset$ and $\bullet(\emptyset)=\\{\emptyset\\}=2^{X_{D}}$ and we
are done.

For the induction case, let $D$ be a downset containing at least one node, let
$U$ be some maximal node of $D$, and let $D^{\prime}=D\setminus\\{U\\}$. The
first case is then there is no element introduced at $U$, i.e.,
$U=\bigcup_{U^{\prime}\in L,U^{\prime}\subsetneq U}U^{\prime}$, then we have
$X_{D}=X_{D^{\prime}}$, and the induction hypothesis gives us that
$\bullet(D^{\prime})=2^{X_{D^{\prime}}}=2^{X_{D}}$, which concludes because
$\bullet(D)\supseteq\bullet(D^{\prime})$ (as $D^{\prime}\subseteq D$) and
clearly $\bullet(D)\subseteq 2^{X_{D}}$. Let us thus focus on the second case,
where there is an element $x$ introduced at $U$.

We first show that $\\{x\\}\in\bullet(D)$. Indeed, by definition we have
$U\in\bullet(D)$ because $U\in D$. Further, all elements of $U$ except $x$
were introduced below $U$ and in $D^{\prime}$, and therefore we have that
$U\setminus\\{x\\}\subseteq X_{D^{\prime}}$. Hence, by induction hypothesis,
we have $U\setminus\\{x\\}\in\bullet(D^{\prime})$, so
$U\setminus\\{x\\}\in\bullet(D)$ because $D^{\prime}\subseteq D$. From
$U\in\bullet(D)$ and $U\setminus\\{x\\}\in\bullet(D)$ we deduce
$\\{x\\}\in\bullet(D)$.

Now let us show that $\bullet(D)=2^{X_{D}}$. Pick $Y\in 2^{X_{D}}$. If
$x\notin Y$, then $Y\in 2^{X_{D^{\prime}}}$, so by induction hypothesis
$Y\in\bullet(D^{\prime})$, hence $Y\in\bullet(D)$, so we conclude immediately.
If $x\in Y$, let $Y^{\prime}=Y\setminus\\{x\\}$. We have $Y^{\prime}\in
2^{X_{D^{\prime}}}$, so by induction hypothesis we have
$Y^{\prime}\in\bullet(D^{\prime})$ hence $Y^{\prime}\in\bullet(D)$. Further,
we have established in the previous paragraph that $\\{x\\}\in\bullet(D)$. We
conclude that $Y\in\bullet(D)$. Thus, we have shown the inductive claim
$\bullet(D)=2^{X_{D}}$.

We have concluded the induction, which as we explained establishes the claim.
∎

By Proposition 4.7, in a tree $T$ which witnesses that
$\hat{1}\in\bullet(\mathtt{NTI}(L))$ for a full intersection lattice $L$, the
multiplicity of a cancelling intersection is zero. Intuitively, we can see
this as suggesting that we do not really need such intersections, and so that
the $\mathtt{NCI}$ conjecture should morally be true. In addition notice that,
for a measure $\xi$ on $2^{\hat{1}}$, applying $\xi$ to $T$ (and replacing
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$ nodes by $+$ and
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$ nodes by $-$) and
then factoring gives back exactly Equation (1) according to Proposition 4.7.

##  5 Alternative Formulation: Dot-Algebra of Non-Cancelling Principal
Downsets in the Boolean Lattice

In this section we give an alternative formulation of the conjecture which is
about the Boolean lattice. It will in particular use results from the previous
section. As the structure of the Boolean lattice is “simpler”, the hope is
that the alternative formulation of the conjecture may be easier to attack. We
present the alternative formulation and show that it is equivalent in Section
5.1, and show in Section 5.2 some useful properties that we can deduce from
this alternative formulation.

###  5.1 The $\mathtt{NCPD}$ conjecture

For $S$ finite, we call a _configuration of $\mathbbm{B}_{S}$_, or simply
_configuration_ when clear from context, a subset of $\mathbbm{B}_{S}$. Since
configurations are in particular set families, we will generally denote them
with cursive letters.

We start by defining what we call _generalized Möbius functions_ , that are
parameterized by a configuration, and that take only one argument.

######  Definition 5.1.

Let $S$ finite and $\mathcal{C}\subseteq\mathbbm{B}_{S}$ a configuration. We
define the _(generalized) Möbius function
$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}:\mathbbm{B}_{S}\to\mathbb{Z}$
associated to $\mathcal{C}$_ by top-down induction by:

$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}(X)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\begin{cases}1-\sum_{X\subsetneq
X^{\prime}}\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}(X^{\prime})\text{ if
}X\in\mathcal{C}\\\ -\sum_{X\subsetneq
X^{\prime}}\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}(X^{\prime})\text{ if
}X\notin\mathcal{C}\end{cases}.$

In particular, the value $\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}(S)$ is $0$
if $S\notin\mathcal{C}$, and $1$ if $S\in\mathcal{C}$.

######  Example 5.2.

Let $\mathcal{C}$ be the configuration

$\\{\\{0\\},\\{1\\},\\{0,1\\},\\{0,3\\},\\{1,2\\},\\{1,3\\},\\{0,1,3\\},\\{1,2,3\\}\\}$

of $\mathbbm{B}_{\\{0,1,2,3\\}}$. We have depicted in Figure 4 this
configuration and its associated Möbius function.

$\emptyset$$0$$0$$0$$1$$0$$2$$0$$3$$0$$01$$0$$02$$0$$03$$0$$12$$0$$13$$-1$$23$$-1$$012$$0$$013$$1$$023$$0$$123$$1$$0123$$0$
Figure 4: Visual representation of the configuration $\mathcal{C}$ from
Example 5.2 and of its associated Möbius function
$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}$ beside each node. Here,
$\mathcal{C}$ consists of all the colored nodes.

Next, we define the _non-cancelling principal downsets_ of such a
configuration.

######  Definition 5.3.

Let $S$ finite and $\mathcal{C}$ a configuration of $B_{S}$. The set of _non-
cancelling principal downsets of $\mathbbm{B}_{S}$ with respect to
$\mathcal{C}$_, denoted $\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{C})$, is
defined by

$\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{C})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{\downarrow_{\mathbbm{B}_{S}}(X)\mid
X\in\mathbbm{B}_{s},\ \hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}(X)\neq 0\\}.$

(Recall that we write $\downarrow_{\mathbbm{B}_{S}}(X)$ for
$\downarrow_{\mathbbm{B}_{S}}(\\{X\\})$.)

Note that the elements of $\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{C})$ are
subsets of $\mathbbm{B}_{S}$. The notation might appear heavy at first sight,
e.g., using subscripts in $\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}$ and
$\mathtt{NCPD}_{\mathbbm{B}_{S}}$ to always recall which Boolean lattice we
are considering. This will however help to avoid confusion in later proofs,
when multiple Boolean lattices and configurations will be involved.

We are now ready to state the alternative formulation, which we call for
convenience the  _$\mathtt{NCPD}$ conjecture_.

######  Conjecture 5.4 ($\mathtt{NCPD}$ conjecture).

For every finite $S$, for every configuration $\mathcal{I}$ of
$\mathbbm{B}_{S}$ that is a downset of $\mathbbm{B}_{S}$, we have that
$\mathcal{I}\in\bullet(\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{I}))$.

We point out that, if we do not ask the configuration to be a downset of
$\mathbbm{B}_{S}$ then the statement is false, i.e., there exists a finite $S$
and configuration $\mathcal{C}$ of $\mathbbm{B}_{S}$ such that
$\mathcal{C}\notin\bullet(\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{C}))$: see
Section 7.

We prove in the remaining of this section that this conjecture is equivalent
to the $\mathtt{NCI}$ conjecture. We start with a general-purpose lemma that
gives a correspondence between both formulations:

######  Lemma 5.5.

Let $S$ be a finite set and let $\mathcal{I}$ be a downset of
$\mathbbm{B}_{S}$ of the form
$\mathcal{I}={\downarrow_{\mathbbm{B}_{S}}(\mathcal{F})}$ for $\mathcal{F}$ a
non-trivial set family. For $X\in\mathcal{F}$ let
$X^{\prime}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\downarrow_{\mathbbm{B}_{S}}(X)$
(which is $2^{X}$), and let
$\mathcal{F}^{\prime}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{X^{\prime}\mid
X\in\mathcal{F}\\}$. Note that $\mathcal{F}^{\prime}$ is non-trivial as well,
and let then $L$ be its intersection lattice. Then we have
$\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{I})=\mathtt{NCI}(L)$.

The proof of this lemma is tedious and we defer it to Appendix LABEL:apx:alt.
We then show each direction of the equivalence in turn.

#####  $\mathtt{NCI}$ conjecture (formulation I) $\implies$ $\mathtt{NCPD}$
conjecture.

Assume Conjecture 3.4 to be true, let $\mathcal{I}$ be a configuration of
$\mathbbm{B}_{S}$ for some finite set $S$, assume that $\mathcal{I}$ is a
downset, and let us show that
$\mathcal{I}\in\bullet(\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{I}))$. If
$\mathcal{I}$ is empty this is clear because then we have
$\bullet(\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{I}))=\bullet(\emptyset)=\\{\emptyset\\}$.
If $\mathcal{I}$ is a principal downset of $\mathbbm{B}_{S}$ this is also
clear, because in that case we have that
$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{I}}(X)$ for $X\in\mathbbm{B}_{S}$ equals
$1$ if $\mathcal{I}=\downarrow_{\mathbbm{B}_{S}}(X)$ and $0$ otherwise, so
assume that $\mathcal{I}$ is not empty and is not a principal downset. Then
$\mathcal{I}$ is of the form $\downarrow_{\mathbbm{B}_{S}}(\mathcal{F})$ for
some non-trivial set family $\mathcal{F}$. Let then $L$ be the intersection
lattice constructed from $S$ and $\mathcal{F}$ as in Lemma 5.5. By this Lemma
we have that $\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{I})=\mathtt{NCI}(L)$.
By the hypothesis of Conjecture 3.4 being true we have
$\hat{1}_{L}\in\bullet(\mathtt{NCI}(L))$, but $\hat{1}_{L}$ is $\mathcal{I}$
so indeed
$\mathcal{I}\in\bullet(\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{I}))$.

#####  $\mathtt{NCPD}$ conjecture $\implies$ $\mathtt{NCI}$ conjecture
(formulation II).

Assume now that Conjecture 5.4 is true, let $\mathcal{F}$ be a non-trivial set
family such that the intersection lattice $L=\mathbbm{L}_{\mathcal{F}}$ is
tight, and let us show that $\hat{1}_{L}\in\bullet(\mathtt{NCI}(L))$. For
$X\in\mathcal{F}$ let
$X^{\prime}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}2^{X}$, and let
$\mathcal{F}^{\prime}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{X^{\prime}\mid
X\in\mathcal{F}\\}$. Note that $\mathcal{F}^{\prime}$ is non-trivial as well,
so let us consider $L^{\prime}=\mathbbm{L}_{\mathcal{F}^{\prime}}$. For
$\mathcal{T}\subseteq\mathcal{F}$, let $\mathcal{T}^{\prime}$ be the
corresponding subset of $\mathcal{F}^{\prime}$, i.e.,
$\mathcal{T}^{\prime}=\\{X^{\prime}\mid X\in\mathcal{T}\\}$, and vice versa.
Then observe that for
$\mathcal{T}\subseteq\mathcal{F},\mathcal{T}\neq\emptyset$ we have
$S_{\mathcal{T}^{\prime}}=2^{S_{\mathcal{T}}}$, so that $L\simeq L^{\prime}$.
Moreover we have that $L^{\prime}$ is full: indeed it is clear that for
$\mathcal{T}\subseteq\mathcal{F},\mathcal{T}\neq\emptyset$ we have
$S_{\mathcal{T}}\in\\{X\in\hat{1}_{L^{\prime}}\mid\min_{L^{\prime}}(X)=S_{\mathcal{T}^{\prime}}\\}$.444But
note that $L^{\prime}$ is never tight: indeed we have, e.g.,
$\\{X\in\hat{1}_{L^{\prime}}\mid\min_{L^{\prime}}(X)=\hat{0}_{L^{\prime}}\\}=\\{\hat{0}_{L},\emptyset\\}$.
Define now $S=\hat{1}_{L}$ (which is finite because $L$ is tight), and let
$\mathcal{I}$ be the downset of $\mathbbm{B}_{S}$ that is
$\downarrow_{\mathbbm{B}_{S}}(\mathcal{F})$. Observe then that $L^{\prime}$ is
exactly the intersection lattice that we would obtain from the construction
described in Lemma 5.5 applied on $S$ and $\mathcal{F}$, so that
$\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{I})=\mathtt{NCI}(L^{\prime})$ by
that lemma. Since Conjecture 5.4 is true by hypothesis we have
$\mathcal{I}\in\bullet(\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{I}))$, hence
$\mathcal{I}\in\bullet(\mathtt{NCI}(L^{\prime}))$. But
$\mathcal{I}=\\{Y\in\mathbbm{B}_{S}\mid\exists X\in\mathcal{F},~{}Y\subseteq
X\\}$ by definition, which is equal to $\bigcup\mathcal{F}^{\prime}$, which is
$\hat{1}_{L^{\prime}}$ by definition. Therefore
$\hat{1}_{L^{\prime}}\in\bullet(\mathtt{NCI}(L^{\prime}))$. This implies
$\hat{1}_{L}\in\bullet(\mathtt{NCI}(L))$ as well by Lemma 4.4.

###  5.2 Useful facts

We now present useful facts about the $\mathtt{NCPD}$ formulation of the
conjecture that motivate its introduction.

First, we observe that the generalized Möbius functions are linear (in their
parameters) under disjoint union and subset complement.

######  Fact 5.6.

Let $S$ finite and $\mathcal{C}_{1},\mathcal{C}_{2}$ be two configurations of
$\mathbbm{B}_{S}$ such that
$\mathcal{C}_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\mathcal{C}_{2}$
(resp.,
$\mathcal{C}_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\mathcal{C}_{2}$)
is well defined. Then
$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\mathcal{C}_{2}}=\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{1}}+\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{2}}$
(resp.,
$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\mathcal{C}_{2}}=\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{1}}-\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{2}}$).

###### Proof.

One can simply check by top-down induction that for all $X\in\mathbbm{B}_{S}$
we have
$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\mathcal{C}_{2}}(X)=\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{1}}(X)+\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{2}}(X)$
(resp.,
$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\mathcal{C}_{2}}(X)=\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{1}}(X)-\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{2}}(X)$).
∎

Second, we show that, if we allow any principal downset in the dot algebra,
then we can build any configuration: this is the analogue of Fact 4.8. In fact
we will use the following stronger result:555In this lemma and its proof we
correctly use the notation $\downarrow_{\mathbbm{B}_{S}}(\\{X\\})$ for
$X\in\mathbbm{B}_{S}$ instead of $\downarrow_{\mathbbm{B}_{S}}(X)$ to avoid
confusion.

######  Lemma 5.7.

Let $\mathcal{C}$ be a configuration of $\mathbbm{B}_{S}$ (for $S$ finite),
and let

$A_{\mathcal{C}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{\downarrow_{\mathbbm{B}_{S}}(\\{X\\})\mid
X\in{\downarrow_{\mathbbm{B}_{S}}(\mathcal{C})}\\}.$

Then we have $\mathcal{C}\in\bullet(A_{\mathcal{C}})$.

###### Proof.

By induction on the size of $\downarrow_{\mathbbm{B}_{S}}(\mathcal{C})$. The
base case is when $|\downarrow_{\mathbbm{B}_{S}}(\mathcal{C})|=0$, which can
only happen when $\mathcal{C}$ is $\emptyset$. Then clearly
$\mathcal{C}\in\bullet(A_{\mathcal{C}})$ as $A_{\mathcal{C}}=\emptyset$ and
$\bullet(\emptyset)=\\{\emptyset\\}$.

For the inductive case, assume the claim is true for all
${\mathcal{C}^{\prime}}$ with
$|\downarrow_{\mathbbm{B}_{S}}({\mathcal{C}^{\prime}})|\leq n$, and let us
show it is true for $\mathcal{C}$ with
$|\downarrow_{\mathbbm{B}_{S}}(\mathcal{C})|=n+1$. Let $X\in\mathcal{C}$ be
maximal, and consider
${\mathcal{C}^{\prime}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathcal{C}\setminus\\{X\\}$.
Then $|\downarrow_{\mathbbm{B}_{S}}({\mathcal{C}^{\prime}})|\leq n$, hence by
induction hypothesis we have
$\mathcal{C}^{\prime}\in\bullet(A_{\mathcal{C}^{\prime}})$. But it is clear
that $A_{{\mathcal{C}^{\prime}}}\subseteq A_{\mathcal{C}}$, so that
$\mathcal{C}^{\prime}\in\bullet(A_{\mathcal{C}})$ as well. Moreover, consider
$\mathcal{C}_{1}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\downarrow_{\mathbbm{B}_{S}}(\\{X\\})\setminus\\{X\\}}$.
By induction hypothesis and for the same reasons we have
$\mathcal{C}_{1}\in\bullet(A_{\mathcal{C}})$. Then
$\mathcal{C}^{\prime}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}(\downarrow_{\mathbbm{B}_{S}}(\\{X\\})\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\mathcal{C}_{1})$
is a valid expression witnessing that
$\mathcal{C}\in\bullet(A_{\mathcal{C}})$. ∎

Third, we show that all instances of the $\mathtt{NCPD}$ conjecture are
already “full”, in the sense that an analogous version of Proposition 4.7
automatically holds for them (whereas we saw that Proposition 4.7 might be
false for intersection lattices that are not full). Let
$\mathtt{PD}(\mathbbm{B}_{S})$ be the set of principal downsets of
$\mathbbm{B}_{S}$, i.e.,
$\mathtt{PD}(\mathbbm{B}_{S})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{\downarrow_{\mathbbm{B}_{S}}(X)\mid
X\in\mathbbm{B}_{S}\\}$. We show:

######  Proposition 5.8.

Let $S$ finite and $\mathcal{I}$ be a configuration of $\mathbbm{B}_{S}$ that
is a downset and $T$ a tree witnessing that
$\mathcal{I}\in\bullet(\mathtt{PD}(\mathbbm{B}_{S}))$. Then we have
$\mathtt{mult}_{T}(\downarrow_{\mathbbm{B}_{S}}(X))=\hat{\mu}_{\mathbbm{B}_{S},\mathcal{I}}(X)$
for every $X\in\mathbbm{B}_{S}$.

###### Proof.

It is routine to show by (bottom-up) induction on $T$ that, for every node
$n\in T$, letting $\mathcal{C}_{n}$ be the corresponding configuration
represented by the subtree of $T$ rooted at $n$ we have that
$\mathtt{mult}_{T_{n}}(\downarrow_{\mathbbm{B}_{S}}(X))=\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}_{n}}(X)$
for every $X\in\mathbbm{B}_{S}$; this in particular uses the linearity of
generalized Möbius functions under disjoint unions and subset complements.
Applying this claim to the root of $T$ gives the claim. ∎

Last, we establish a connection between the generalized Möbius function of a
configuration $\mathcal{C}$ and the _Euler characteristic_ of $\mathcal{C}$,
that will be crucial in the next section.

######  Definition 5.9.

Let $\mathcal{C}$ be a set family of finite sets. We define the  _Euler
characteristic of $\mathcal{C}$_, denoted $\mathsf{e}(\mathcal{C})$, by
$\mathsf{e}(\mathcal{C})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{X\in\mathcal{C}}(-1)^{|X|}$.

######  Proposition 5.10.

Let $S$ finite and $\mathcal{C}$ a configuration of $\mathbbm{B}_{S}$. Then we
have
$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}(X)=(-1)^{|X|}\times\mathsf{e}(\mathcal{C}\cap\uparrow_{\mathbbm{B}_{S}}(X))$
for every $X\in\mathbbm{B}_{S}$.

###### Proof.

Define $f,g:\mathbbm{B}_{S}\to\mathbb{Z}$ by
$f(X)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}(X)$
and $g(X)=1$ if $X\in\mathcal{C}$ and $0$ otherwise. Observe then that, by
definition of $\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}$ we have
$g(X)=\sum_{\begin{subarray}{c}X^{\prime}\in\mathbbm{B}_{S}\\\ X\subseteq
X^{\prime}\end{subarray}}f(X^{\prime})$ for all $X\in\mathbbm{B}_{S}$. Then by
Proposition 2.11 we have that
$f(X)=\sum_{\begin{subarray}{c}X^{\prime}\in\mathbbm{B}_{S}\\\ X\subseteq
X^{\prime}\end{subarray}}(-1)^{|X^{\prime}|-|X|}g(X^{\prime})$ for all
$X\in\mathbbm{B}_{S}$, i.e.,

$\displaystyle\hat{\mu}_{\mathbbm{B}_{S},\mathcal{C}}(X)$
$\displaystyle=\sum_{\begin{subarray}{c}X^{\prime}\in\mathbbm{B}_{S}\\\
X\subseteq X^{\prime}\end{subarray}}(-1)^{|X^{\prime}|-|X|}g(X^{\prime})$
$\displaystyle=\sum_{X^{\prime}\in{\mathcal{C}\cap\uparrow_{\mathbbm{B}_{S}}(X)}}(-1)^{|X^{\prime}|-|X|}$
$\displaystyle=(-1)^{|X|}\times\sum_{X^{\prime}\in\mathcal{C}\cap\uparrow_{\mathbbm{B}_{S}}(X)}(-1)^{|X^{\prime}|}$
$\displaystyle=(-1)^{|X|}\times\mathsf{e}(\mathcal{C}\cap\uparrow_{\mathbbm{B}_{S}}(X))$

for all $X\in\mathbbm{B}_{S}$, which is what we wanted to show. ∎

Connections between the Möbius function and the Euler characteristic have
already been shown, for instance see Philip Hall’s theorem [Rota, 1964,
Proposition 6 and Theorem 3]. As far as we can tell, however, the connection
from Proposition 5.10 seems new.

##  6 Partial result on $\mathtt{NCPD}$: avoiding a given zero

In this section we present a partial result on the $\mathtt{NCPD}$ conjecture
intuitively saying that we can “avoid” any given non-trivial zero. We first
define what these are.

######  Definition 6.1.

Let $\mathcal{I}$ be a downset of $\mathbbm{B}_{S}$. We define the _non-
trivial zeros of $\mathcal{I}$_, denoted
$\mathtt{NTZ}_{\mathbbm{B}_{S}}(\mathcal{I})$, by

$\mathtt{NTZ}_{\mathbbm{B}_{S}}(\mathcal{I})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{Z\in\mathcal{I}\mid\hat{\mu}_{\mathbbm{B}_{S},\mathcal{I}}(Z)=0\\}.$

By opposition, the _trivial_ zeros of $\mathcal{I}$ are the elements
$Z\in\mathbbm{B}_{S}\setminus\mathcal{I}$ such that
$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{I}}(Z)=0$ (notice that these form an
upset of $\mathbbm{B}_{S}$).

Observe that if $\mathcal{I}$ does not have non-trivial zeros, i.e.,
$\mathtt{NTZ}_{\mathbbm{B}_{S}}(\mathcal{I})=\emptyset$, then we have indeed
that $\mathcal{I}\in\bullet(\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{I}))$,
that is, the $\mathtt{NCPD}$ conjecture holds, as can be seen by taking
$\mathcal{C}=\mathcal{I}$ in Lemma 5.7. So we can focus on downsets
$\mathcal{I}$ having as least one such non-trivial zero.

The partial result that we show in this section is that, for any given such
non-trivial zero $Z$, if we are allowed to use all the non-trivial principal
downsets _except the one generated by $Z$_, then we can construct
$\mathcal{I}$. Formally we will prove the following:

######  Theorem 6.2.

Let $\mathcal{I}$ be a downset of $\mathbbm{B}_{S}$ such that
$\mathtt{NTZ}_{\mathbbm{B}_{S}}(\mathcal{I})$ is not empty, and let
$Z\in\mathtt{NTZ}_{\mathbbm{B}_{S}}(\mathcal{I})$. Then we have
$\mathcal{I}\in\bullet(\\{\downarrow_{\mathbbm{B}_{S}}(X)\mid X\in
I\setminus\\{Z\\}\\})$.

The proof reuses and extends some ideas and notions from [Monet, 2020a]. We
first define some of these notions in Section 6.1, in particular the notion of
_adjacent pairs_ and certain equivalence classes. In Section 6.2 we show what
we call the _lifting lemma_ , and show adjacent pairs can be simulated with
principal downsets. We combine everything in Section 6.3 to prove Theorem 6.2.

###  6.1 Adjacent pairs

######  Definition 6.3.

An _adjacent pair_ of $\mathbbm{B}_{S}$ is a configuration $\mathcal{P}$ of
the form
$\\{X,X\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\\{x\\}\\}$ (with
$X\in\mathbbm{B}_{S}$ and $x\in X$).

######  Definition 6.4.

Let $A$ be a set of adjacent pairs of $\mathbbm{B}_{S}$, and let
$\mathcal{C},\mathcal{C}^{\prime}$ be two configurations of $\mathbbm{B}_{S}$.
We then write
$\mathcal{C}\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{+
A\,}}}\mathcal{C}^{\prime}$ when there exists an adjacent pair $\mathcal{P}\in
A$ such that
$\mathcal{C}^{\prime}=\mathcal{C}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\mathcal{P}$.
Similarly we write
$\mathcal{C}\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{-A\,}}}\mathcal{C}^{\prime}$
whenever
$\mathcal{C}^{\prime}\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{+A\,}}}\mathcal{C}$
(i.e., when there exists $\mathcal{P}\in A$ such that
$\mathcal{C}^{\prime}=\mathcal{C}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\mathcal{P}$),
and write
$\mathcal{C}\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{$\pm$
A\,}}}\mathcal{C}^{\prime}$ when
$\mathcal{C}\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{+A\,}}}\mathcal{C}^{\prime}$
or
$\mathcal{C}\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{-A\,}}}\mathcal{C}^{\prime}$.
Observe that
$\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{$\pm
A$\,}}}$ is symmetric. We write
$\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{$\pm
A$\,}}}^{*}$ the reflexive transitive closure of
$\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{$\pm
A$\,}}}$, and write $\simeq_{A}$ the induced equivalence relation.

In other words, we have $\mathcal{C}\simeq_{A}\mathcal{C}^{\prime}$ when we
can go from $\mathcal{C}$ to $\mathcal{C}^{\prime}$ by iteratively (1) adding
an adjacent pair from $A$ to the current configuration if the pair is disjoint
from the configuration; or (2) removing an adjacent pair from $A$ to the
current configuration if the pair was included in the configuration.

######  Definition 6.5.

For a subset $\mathcal{G}$ of $\mathbbm{B}_{S}$, define the set of _allowed
adjacent pairs of $\mathbbm{B}_{S}$ relative to $\mathcal{G}$_, denoted
$\mathtt{AP}_{\mathbbm{B}_{S}}(\mathcal{G})$, by

$\mathtt{AP}_{\mathbbm{B}_{S}}(\mathcal{G})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{\mathcal{P}\mid\mathcal{P}\text{
is an adjacent pair of }\mathbbm{B}_{S}\text{ and
}\mathcal{P}\subseteq\mathcal{G}\\}.$

######  Definition 6.6.

For $S$ finite, define the undirected graph $G_{S}$ with vertex set $2^{S}$
whose edges are all adjacent pairs of $\mathbbm{B}_{S}$. A subset
$\mathcal{G}$ of $\mathbbm{B}_{S}$ is _connected_ if it is a connected set of
nodes in $G_{S}$.

The goal of this section is to establish the following proposition:

######  Proposition 6.7.

Let $\mathcal{G}$ be a connected subset of $\mathbbm{B}_{S}$, and
$\mathcal{C}_{1},\mathcal{C}_{2}$ two configurations that are included in
$\mathcal{G}$. We have
$\mathsf{e}(\mathcal{C}_{1})=\mathsf{e}(\mathcal{C}_{2})$ if and only if
$\mathcal{C}_{1}\simeq_{\mathtt{AP}_{\mathbbm{B}_{S}}(\mathcal{G})}\mathcal{C}_{2}$.

This result already appears in [Monet, 2020a, Proposition 6.1], but only when
$\mathcal{G}$ is the whole Boolean lattice, i.e., when666We will actually only
use this result when $\mathcal{G}$ is a downset of $\mathbbm{B}_{S}$, but we
still prove this more general version for completeness and because it is not
much more complicated. we have $\mathcal{G}=2^{S}$. Observe that the “if”
direction in Proposition 6.7 is trivial, since adding or removing an adjacent
pair (with disjoint union or subset complement) does not modify the Euler
characteristic. Hence we need to prove the “only if” direction. To this end,
we reproduce the following lemma from [Monet, 2020a]:

######  Lemma 6.8 (Lemma 5.10 of [Monet, 2020a]).

Let $\mathcal{C}$ be a configuration of $\mathbbm{B}_{S}$, and $X\neq
X^{\prime}$ be two subsets of $S$ such that there is a simple path $P$ of the
form $X=X_{0}-\cdots-X_{n+1}=X^{\prime}$ from $X$ to $X^{\prime}$ in $G_{S}$
with $n\geq 0$ and $X_{i}\notin\mathcal{C}$ for $1\leq i\leq n$. Then we have
the following:

Erasing.

If $(-1)^{|X|}\neq(-1)^{|X^{\prime}|}$ (i.e., $n$ is even) and
$\\{X,X^{\prime}\\}\subseteq\mathcal{C}$ then, defining $\mathcal{C}^{\prime}$
by
$\mathcal{C}^{\prime}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathcal{C}\setminus\\{X,X^{\prime}\\}$,
we have
$\mathcal{C}\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{$\pm\mathtt{AP}_{\mathbbm{B}_{S}}(P)$\,}}}^{*}\mathcal{C}^{\prime}$.
We say that we go from $\mathcal{C}$ to $\mathcal{C}^{\prime}$ by _erasing $X$
and $X^{\prime}$_.

Teleporting.

If $(-1)^{|X|}=(-1)^{|X^{\prime}|}$ (i.e., $n$ is odd) and $X\in\mathcal{C}$
and $X^{\prime}\notin\mathcal{C}$ then, defining $\mathcal{C}^{\prime}$ by
$\mathcal{C}^{\prime}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}(\mathcal{C}\setminus\\{X\\})\cup\\{X^{\prime}\\}$,
we have
$\mathcal{C}\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{$\pm\mathtt{AP}_{\mathbbm{B}_{S}}(P)$\,}}}^{*}\mathcal{C}^{\prime}$.
We say that we go from $\mathcal{C}$ to $\mathcal{C}^{\prime}$ by _teleporting
$X$ to $X^{\prime}$_.

###### Proof.

We only explain the erasing part, as teleporting works similarly. Let $n=2i$.
For $0\leq j<i$, do the following: add the adjacent pair
$\\{X_{2j+1},X_{2j+2}\\}$ and remove the adjacent pair
$\\{X_{2j},X_{2j+1}\\}$. Finally, remove the adjacent pair
$\\{X_{2i},X_{2i+1}\\}$. ∎

Teleporting is illustrated in Figure 5 (adapted from [Monet, 2020a]).

$X_{0}$$X_{1}$$X_{2}$$X_{3}$$X_{4}$$X_{0}$$X_{1}$$X_{2}$$X_{3}$$X_{4}$$X_{0}$$X_{1}$$X_{2}$$X_{3}$$X_{4}$$X_{0}$$X_{1}$$X_{2}$$X_{3}$$X_{4}$$X_{0}$$X_{1}$$X_{2}$$X_{3}$$X_{4}$$\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{$-\mathtt{AP}_{\mathbbm{B}_{S}}(P)$\,}}}$$\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{$+\mathtt{AP}_{\mathbbm{B}_{S}}(P)$\,}}}$$\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{$-\mathtt{AP}_{\mathbbm{B}_{S}}(P)$\,}}}$$\mathbin{\stackon[2pt]{{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\sim\mkern-3.9mu}{\scriptstyle\rule{0.3014pt}{0.0pt}\rhd}}{\scriptscriptstyle\text{$+\mathtt{AP}_{\mathbbm{B}_{S}}(P)$\,}}}$$X_{0}$$X_{0}$$X_{1}$$X_{2}$$X_{2}$$X_{2}$$X_{3}$$X_{4}$$X_{4}$
Figure 5: Imagine that the path at the top occurs in $G_{S}$ for some
configuration $\mathcal{C}$ of $\mathbbm{B}_{S}$ (in orange), and let
$P=\\{X_{0},\ldots,X_{4}\\}$. The consecutive orange configurations of
$\mathbbm{B}_{S}$ are obtained by single steps of the transformation. The
total transformation illustrates what is called _teleporting_ in Lemma 6.8: we
go from $\mathcal{C}$ to $\mathcal{C}^{\prime}$ in the bottom path by
teleporting $X_{1}$ to $X_{4}$.

We will also reuse the _fetching lemma_ from [Monet, 2020a], extending it to
connected subsets of $\mathbbm{B}_{S}$ (instead of the full Boolean lattice).
Given the right circumstances, this lemma fetches for us two sets
$X,X^{\prime}\in\mathcal{C}$ and a suitable path so that we can erase $X$ and
$X^{\prime}$. Formally:

######  Lemma 6.9 (Fetching lemma, slightly extending Lemma 5.11 of [Monet,
2020a]).

Let $\mathcal{G}$ be a subset of $\mathbbm{B}_{S}$ and
$\mathcal{C}\subseteq\mathcal{G}$ a configuration such that
$|\mathcal{C}|\neq|\mathsf{e}(\mathcal{C})|$. Then there exist
$X,X^{\prime}\in\mathcal{C}$ with $(-1)^{|X|}\neq(-1)^{|X^{\prime}|}$ and a
simple path $X=X_{0}-\cdots-X_{n+1}=X^{\prime}$ from $X$ to $X^{\prime}$ in
$G_{S}$ (hence with $n$ even) with all nodes in this path being in
$\mathcal{G}$ such that $X_{i}\notin\mathcal{C}$ for $1\leq i\leq n$.

###### Proof.

Since $|\mathcal{C}|\neq|\mathsf{e}(\mathcal{C})|$, there exist
$X^{\prime\prime},X^{\prime\prime\prime}\in\mathcal{C}$ with
$(-1)^{|X^{\prime\prime}|}\neq(-1)^{|X^{\prime\prime\prime}|}$. Let
$X^{\prime\prime}=X^{\prime\prime}_{0}-\cdots-X^{\prime\prime}_{m+1}=X^{\prime\prime\prime}$
be an arbitrary simple path from $X^{\prime\prime}$ to
$X^{\prime\prime\prime}$ in $G_{S}$ with all nodes being in $\mathcal{G}$
(such a path clearly exists because $\mathcal{G}$ is a connected subset of
$G_{S}$). Now, let $k_{1}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max(0\leq
j\leq m\mid(-1)^{|X^{\prime\prime}_{j}|}=(-1)^{|X^{\prime\prime}|}\text{ and
}X^{\prime\prime}_{j}\in\mathcal{C})$, and then let
$k_{2}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min(k_{1}<j\leq
m+1\mid(-1)^{|X^{\prime\prime}_{j}|}=(-1)^{|X^{\prime\prime\prime}|}\text{ and
}X^{\prime\prime}_{j}\in\mathcal{C})$, which are well-defined. Then we can
take $X$ to be $X^{\prime\prime}_{k_{1}}$ and $X^{\prime}$ to be
$X^{\prime\prime}_{k_{2}}$, which satisfy the desired property. ∎

With these in place we are ready to prove Proposition 6.7.

###### Proof of Proposition 6.7.

As mentioned above, we only need to prove the “only if” part of the statement.
Starting from $\mathcal{C}_{1}$, we repeatedly use the fetching lemma and
Erasing until we obtain a configuration
$\mathcal{C}_{1}^{\prime}\subseteq\mathcal{G}$ such that
$\mathcal{C}_{1}^{\prime}\simeq_{\mathtt{AP}_{\mathbbm{B}_{S}}(\mathcal{G})}\mathcal{C}_{1}$
and $|\mathcal{C}_{1}^{\prime}|=\mathsf{e}(\mathcal{C}_{1}^{\prime})$. We do
the same with $\mathcal{C}_{2}$, obtaining
$\mathcal{C}_{2}^{\prime}\subseteq\mathcal{G}$ with
$\mathcal{C}_{2}^{\prime}\simeq_{\mathtt{AP}_{\mathbbm{B}_{S}}(\mathcal{G})}\mathcal{C}_{2}$
and $|\mathcal{C}_{2}^{\prime}|=\mathsf{e}(\mathcal{C}_{2}^{\prime})$. If
$\mathcal{C}_{1}^{\prime}=\mathcal{C}_{2}^{\prime}$ we are done. Otherwise,
let
$n\stackrel{{\scriptstyle\mathrm{def}}}{{=}}|\mathcal{C}_{1}^{\prime}\setminus\mathcal{C}_{2}^{\prime}|$,
which is $>0$ because $|\mathcal{C}_{1}^{\prime}|=|\mathcal{C}_{2}^{\prime}|$.
We build by induction a sequence of configurations
$\mathcal{C}_{1}^{\prime}=\mathcal{C}^{\prime\prime}_{0},\ldots,\mathcal{C}^{\prime\prime}_{n}=\mathcal{C}_{2}^{\prime}$
that are all included in $\mathcal{G}$ and that satisfy (1)
$\mathcal{C}^{\prime\prime}_{i}\simeq_{\mathtt{AP}_{\mathbbm{B}_{S}}(\mathcal{G})}\mathcal{C}^{\prime\prime}_{i+1}$
for all $0\leq i\leq n-1$ and (2)
$|\mathcal{C}^{\prime\prime}_{i}|=\mathsf{e}(\mathcal{C}^{\prime\prime}_{i})$
and $|\mathcal{C}^{\prime\prime}_{i}\setminus\mathcal{C}_{2}^{\prime}|=n-i$
for all $0\leq i\leq n$. It is clear that this indeed implies the claim. As
$\mathcal{C}^{\prime\prime}_{0}$ satisfies condition (2), it is enough to
explain how to build $\mathcal{C}^{\prime\prime}_{i+1}$ from
$\mathcal{C}^{\prime\prime}_{i}$ for $i<n$, and then to argue that the
$\mathcal{C}^{\prime\prime}_{n}$ from this construction is indeed equal to
$\mathcal{C}_{2}^{\prime}$. We have
$|\mathcal{C}^{\prime\prime}_{i}\setminus\mathcal{C}_{2}^{\prime}|=n-i>1$ by
induction hypothesis, so there exists
$X^{\prime}\in\mathcal{C}^{\prime\prime}_{i}\setminus\mathcal{C}_{2}^{\prime}$
and
$X^{\prime\prime}\in\mathcal{C}_{2}^{\prime}\setminus\mathcal{C}^{\prime\prime}_{i}$
(because
$|\mathcal{C}_{i}^{\prime\prime}|=\mathsf{e}(\mathcal{C}_{i}^{\prime\prime})=\mathsf{e}(\mathcal{C}_{1}^{\prime})=|\mathcal{C}_{1}^{\prime}|=|\mathcal{C}_{2}^{\prime}|$).
Let $X^{\prime}=X^{\prime}_{0}-\cdots-X^{\prime}_{m+1}=X^{\prime\prime}$ be an
arbitrary simple path from $X^{\prime}$ to $X^{\prime\prime}$ in $G_{S}$ with
all nodes being in $\mathcal{G}$ (such a path exists because $\mathcal{G}$ is
a connected subset of $G_{S}$, and $m$ is odd and $\geq 1$). Observe that all
nodes $X^{\prime}_{k}$ with $k$ odd are not in
$\mathcal{C}^{\prime\prime}_{i}\cup\mathcal{C}_{2}^{\prime}$, because
$|\mathcal{C}^{\prime\prime}_{i}|=\mathsf{e}(\mathcal{C}^{\prime\prime}_{i})|$
and $|\mathcal{C}_{2}^{\prime}|=\mathsf{e}(\mathcal{C}_{2}^{\prime})$ . Now,
let $k_{1}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max(0\leq j\leq m\mid
X^{\prime}_{j}\in\mathcal{C}^{\prime\prime}_{i}\setminus\mathcal{C}_{2}^{\prime})$,
and then let $k_{2}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min(k_{1}<j\leq
m+1\mid
X^{\prime}_{j}\in\mathcal{C}_{2}^{\prime}\setminus\mathcal{C}^{\prime\prime}_{i})$,
which are well-defined. Define
$\mathcal{C}^{\prime\prime}_{i+1}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathcal{C}^{\prime\prime}_{i}\setminus\\{X_{k_{1}}\\}\cup\\{X_{k_{2}}\\}$.
Notice that $\mathcal{C}^{\prime\prime}_{i+1}$ satisfies condition (2), so all
we need to show is that
$\mathcal{C}^{\prime\prime}_{i}\simeq_{\mathtt{AP}_{\mathbbm{B}_{S}}(\mathcal{G})}\mathcal{C}^{\prime\prime}_{i+1}$.
We know the following: for a node $X^{\prime}_{k}$ with $k_{1}<k<k_{2}$, if
$k$ is odd then
$X^{\prime}_{k}\notin\mathcal{C}^{\prime\prime}_{i}\cup\mathcal{C}^{\prime}_{2}$,
and if $k$ is even then either
$X^{\prime}_{k}\in\mathcal{C}^{\prime\prime}_{i}\cap\mathcal{C}^{\prime}_{2}$
or
$X^{\prime}_{k}\notin\mathcal{C}^{\prime\prime}_{i}\cup\mathcal{C}^{\prime}_{2}$.
If there is no node $X^{\prime}_{k}$ with $k_{1}<k<k_{2}$, $k$ even such that
$X^{\prime}_{k}\in\mathcal{C}_{i}^{\prime\prime}$, then we can simply use
Lemma 6.8 to teleport $X_{k_{1}}$ to $X_{k_{2}}$ and we are done. Otherwise,
let $X^{\prime}_{\ell_{1}},\ldots,X^{\prime}_{\ell_{m}}$ with $m\geq 1$ be all
the nodes with $k_{1}<\ell_{p}<k_{2}$ even that are in
$\mathcal{C}^{\prime\prime}_{i}$, in order, i.e., $\ell_{1}<\ldots<\ell_{m}$.
Then we can successively teleport $X^{\prime}_{\ell_{m}}$ to
$X^{\prime}_{k_{2}}$, $X^{\prime}_{\ell_{m-1}}$ to $X^{\prime}_{\ell_{m}}$,
and so on, until we teleport $X^{\prime}_{\ell_{1}}$ to
$X^{\prime}_{\ell_{2}}$ and finally we teleport $X^{\prime}_{k_{1}}$ to
$X^{\prime}_{\ell_{1}}$, thus obtaining $\mathcal{C}^{\prime\prime}_{i+1}$ as
promised. It is then clear that $\mathcal{C}^{\prime\prime}_{n}$ is
$\mathcal{C}_{2}^{\prime}$, because we have
$|\mathcal{C}^{\prime\prime}_{n}\setminus\mathcal{C}^{\prime}_{2}|=0$ by
condition (2), and
$|\mathcal{C}^{\prime\prime}_{n}|=|\mathcal{C}^{\prime}_{2}|$ by construction.
This concludes the proof. ∎

###  6.2 Lifting lemma and simulating adjacent pairs with principal downsets

A simple, yet important component of the proof of Theorem 6.2 will be what we
call the _lifting lemma_. We first state and prove it before giving intuition.

######  Lemma 6.10 (Lifting lemma).

Let $Z\in\mathbbm{B}_{S}$ and
$\mathcal{A}\subseteq{\uparrow_{\mathbbm{B}_{S}}(Z)}$. Let
$I_{\mathcal{A}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{{\downarrow_{\mathbbm{B}_{S}}(X)}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)}\mid
X\in\mathcal{A}\\}$ and
$I^{\prime}_{\mathcal{A}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{\downarrow_{\mathbbm{B}_{S}}(X)\mid
X\in\mathcal{A}\\}$. Then, for any $\mathcal{C}\in\bullet(I_{\mathcal{A}})$,
defining the configuration

$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{X\in\mathbbm{B}_{S}\mid
X\cup Z\in\mathcal{C}\\},$

we have that
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C})\in\bullet(I^{\prime}_{\mathcal{A}})$.

###### Proof.

This is shown by induction on $\mathcal{C}\in\bullet(I_{\mathcal{A}})$. The
first base case is when $\mathcal{C}=\emptyset$, but then we have
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C})=\emptyset$ as well, which is
in $\bullet(I^{\prime}_{\mathcal{A}})$ by definition. The second base case is
when
$\mathcal{C}={\downarrow_{\mathbbm{B}_{S}}(X)}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)}$
for some $X$ in $\mathcal{A}$. In this case, it is easy to show that
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C})={\downarrow_{\mathbbm{B}_{S}}(X)}$;
this uses in particular that set union is the join operation of the lattice
$\mathbbm{B}_{S}$. But then this implies
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C})\in\bullet(I^{\prime}_{\mathcal{A}})$
indeed. For the inductive case, we focus on
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}$ as
$\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}$ works similarly. Let
$\mathcal{C}_{1},\mathcal{C}_{2}\in\bullet(I_{\mathcal{A}})$ such that
$\mathcal{C}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathcal{C}_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\mathcal{C}_{2}$
is well-defined, and let us show that
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C})\in\bullet(\mathcal{I}^{\prime}_{\mathcal{A}})$.
By induction hypothesis we have that
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C}_{1})\in\bullet(\mathcal{I}^{\prime}_{\mathcal{A}})$
and
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C}_{2})\in\bullet(\mathcal{I}^{\prime}_{\mathcal{A}})$.
Now, observe that
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C}_{1})\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C}_{2})$
is well defined, and furthermore that we have
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C}_{1}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\mathcal{C}_{2})=\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C}_{1})\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C}_{2})$.
This implies
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C})\in\bullet(\mathcal{I}^{\prime}_{\mathcal{A}})$
as wanted, and concludes the proof. ∎

The intuition behind the lifting lemma is the following. Notice that
$\uparrow_{\mathbbm{B}_{S}}(Z)$ is isomorphic to the Boolean lattice
$\mathbbm{B}_{S^{\prime}}$ with
$S^{\prime}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}S\setminus Z$. Consider a
witnessing tree $T^{\prime}$ representing a configuration $\mathcal{C}$ of
$\mathbbm{B}_{S^{\prime}}$ that is formed from principal downsets of
$\mathbbm{B}_{S^{\prime}}$. Consider the “lifted tree” $T^{\prime}$ that is
obtained from $T$ by replacing every leaf of $T$ of the form
$\downarrow_{\mathbbm{B}_{S^{\prime}}}(X)$ for $X\subseteq S^{\prime}$ by the
principal downset of $\mathbbm{B}_{S}$ that is
$\downarrow_{\mathbbm{B}_{S}}(X\cup Z)$. The lifting lemma says that the
obtained tree $T^{\prime}$ is valid (i.e., the internal nodes are well-defined
disjoint unions and subset complements) and that it represents the
configuration of $\mathbbm{B}_{S}$ that is
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{C})$.

This lemma will have two uses in the proof of Theorem 6.2. The first is that
said proof will work by first constructing a configuration in the principal
upset generated by the non-trivial zero $Z$ that is fixed in the theorem
statement, and then this lemma will be used to “lift” the result to the whole
Boolean lattice $\mathbbm{B}_{S}$. The second use of this lemma is that it
helps us show that adjacent pairs can be simulated by principal downsets,
while avoiding the principal downset that is at the bottom. We explain this
second use in the following lemma.

######  Lemma 6.11.

Let
$\mathcal{P}=\\{X,X\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\\{x\\}\\}$
be an adjacent pair of $\mathbbm{B}_{S}$. Then we have
$\mathcal{P}\in\bullet(\\{\downarrow_{\mathbbm{B}_{S}}(Y)\mid\emptyset\subsetneq
Y\subseteq X\\})$.

In this statement, pay attention that the principal downset
$\downarrow_{\mathbbm{B}_{S}}(\emptyset)$ is not in the base set of the dot-
algebra.777Recall that to alleviate the notation we write
$\downarrow_{\mathbbm{B}_{S}}(\emptyset)$ to mean
$\downarrow_{\mathbbm{B}_{S}}(\\{\emptyset\\})$, which is then
$\\{\emptyset\\}$. In other words, we are allowed to use any principal downset
that is generated by an element that is below $X$ and strictly above
$\emptyset$ in $\mathbbm{B}_{S}$. The reason is that in the proof of Theorem
6.2, $Z$ will correspond to $\emptyset$ here and it generates the only downset
we are not allowed to use. We now prove Lemma 6.11.

###### Proof of Lemma 6.11.

Clearly, it suffices to show the claim in the case that $X=S$. To this end, it
is enough to show that we have
$\mathbbm{B}_{S}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\mathcal{P}\in\bullet(\\{\downarrow_{\mathbbm{B}_{S}}(Y)\mid\emptyset\subsetneq
Y\subseteq X\\})$: indeed we can then obtain $\mathcal{P}$ as
$\downarrow_{\mathbbm{B}_{S}}(S)\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}(\mathbbm{B}_{S}\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\mathcal{P})$.
Let $\mathcal{C}^{\prime}$ be the configuration
$\\{X\in\mathbbm{B}_{S}\mid\\{x\\}\subseteq X\subsetneq S\\}$. Using Lemma 5.7
appropriately we have that
$\mathcal{C}^{\prime}\in\bullet(\\{{\downarrow_{\mathbbm{B}_{S}}(Y)}\cap{\uparrow_{\mathbbm{B}_{S}}(\\{x\\})}\mid\\{x\\}\subseteq
Y\subsetneq S\\})$. We now use the lifting lemma (invoked with $Z=\\{x\\}$) to
obtain that
$\mathtt{lift}_{\mathbbm{B}_{S},\\{x\\}}(\mathcal{C}^{\prime})\in\bullet(\\{\downarrow_{\mathbbm{B}_{S}}(Y)\mid\\{x\\}\subseteq
Y\subsetneq S\\})$, hence in particular
$\mathtt{lift}_{\mathbbm{B}_{S},\\{x\\}}(\mathcal{C}^{\prime})\in\bullet(\\{\downarrow_{\mathbbm{B}_{S}}(Y)\mid\emptyset\subsetneq
Y\subseteq S\\})$. But notice that
$\mathtt{lift}_{\mathbbm{B}_{S},\\{x\\}}(\mathcal{C}^{\prime})$ is actually
$\mathbbm{B}_{S}\setminus\mathcal{P}$, which concludes the proof. ∎

###  6.3 Proof of Theorem 6.2

We now prove Theorem 6.2. Fix the finite set $S$ and the configuration
$\mathcal{I}$ that is a downset of $\mathbbm{B}_{S}$ such that
$\mathtt{NTZ}_{\mathbbm{B}_{S}}(\mathcal{I})$ is not empty, and let
$Z\in\mathtt{NTZ}_{\mathbbm{B}_{S}}(\mathcal{I})$. By Proposition 5.10 we have
$\hat{\mu}_{\mathbbm{B}_{S},\mathcal{I}}(Z)=(-1)^{|Z|}\times\mathsf{e}(\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)})$,
therefore $\mathsf{e}(\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)})=0$. We
now instantiate Proposition 6.7 with
$\mathcal{G}=\mathcal{C}_{1}=\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)}$
and $\mathcal{C}_{2}=\emptyset$ to obtain
$\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)}\simeq_{\mathtt{AP}_{\mathbbm{B}_{S}}(\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z))}}\emptyset$.
This gives us a left-linear tree $T$ for
$\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)}$ with disjoint unions and
subset complements and whose leaves are adjacent pairs from
$\mathtt{AP}_{\mathbbm{B}_{S}}(\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)})$.
Next we use Lemma 6.11 to simulate, in $\uparrow_{\mathbbm{B}_{S}}(Z)$, each
such adjacent pair using the principal downsets of
$\uparrow_{\mathbbm{B}_{S}}(Z)$, except the one generated by $Z$ (thanks to
the fact that $\emptyset\subsetneq Y$ in the statement of the lemma).
Therefore, we obtain that
$\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)}\in\bullet(\\{\downarrow_{\mathbbm{B}_{S}}(X)\cap{\uparrow_{\mathbbm{B}_{S}}(Z)}\mid
X\in\mathcal{I},Z\subsetneq X\\})$. We now use Lemma 6.10 to obtain that
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)})\in\bullet(\\{\downarrow_{\mathbbm{B}_{S}}(X)\mid
X\in I\setminus\\{Z\\}\\})$. Notice that
$\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)})\cap{\uparrow_{\mathbbm{B}_{S}}(Z)}=\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)}$,
i.e., restricted to $\uparrow_{\mathbbm{B}_{S}}(Z)$ we have the correct
configuration, and we now only need to “fix” what is outside.

Now let
$\mathcal{C}^{\prime}_{1}=\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z))}\setminus(\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)})$
and
$\mathcal{C}^{\prime}_{2}=\mathcal{I}\setminus(\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)})$.
We use Lemma 5.7 to obtain that $\mathcal{C}_{1}^{\prime}$ is in
$\bullet(\\{\downarrow_{\mathbbm{B}_{S}}(X)\mid
X\in\mathcal{C}_{1}^{\prime}\\})$, and likewise for
$\mathcal{C}_{2}^{\prime}$. Observe that $\mathcal{C}_{1}^{\prime}$ and
$\mathcal{C}_{2}^{\prime}$ only consist of elements outside of
$\uparrow_{\mathbbm{B}_{S}}(Z))$, in particular
$\mathcal{C}_{1}^{\prime},\mathcal{C}_{2}^{\prime}\subseteq
I\setminus\\{Z\\}$, so that $\mathcal{C}_{1}^{\prime}$ and
$\mathcal{C}_{2}^{\prime}$ are in
$\bullet(\\{\downarrow_{\mathbbm{B}_{S}}(X)\mid X\in I\setminus\\{Z\\}\\})$.
Finally we can obtain $\mathcal{I}$ with the expression
$(\mathtt{lift}_{\mathbbm{B}_{S},Z}(\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(Z)})\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\setminus}}\mathcal{C}_{1}^{\prime})\stackrel{{\scriptstyle\mbox{$\bullet$}}}{{\cup}}\mathcal{C}_{2}^{\prime}$,
which is in $\bullet(\\{\downarrow_{\mathbbm{B}_{S}}(X)\mid X\in
I\setminus\\{Z\\}\\})$ by what precedes. This concludes the proof.

##  7 Extensions, Variants and Counterexample Search

In this section we present a generalization of Theorem 6.2 that we believe to
be true, present variants of the conjectures, and talk about our experimental
search for counterexamples.

#### Extension of Theorem 6.2.

We sketch here a proposed generalization that allows us to avoid not one
single zero, but subsets of zeros while requiring that the lattice has a
certain structure. We first define a few notions.

######  Definition 7.1.

Let $\mathcal{I}$ be a downset of $\mathbbm{B}_{S}$. For
$X\in\mathbbm{B}_{S}$, the _non-trivial covering zeros of $X$ relative to
$\mathcal{I}$_ are

$\mathtt{NTCZ}_{\mathbbm{B}_{S},\mathcal{I}}(X)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{Z\in\mathtt{NTZ}_{\mathbbm{B}_{S}}(\mathcal{I})\mid
X\subsetneq Z\text{ and there is no
}Z^{\prime}\in\mathtt{NTZ}_{\mathbbm{B}_{S}}(\mathcal{I})\text{ s.t.
}X\subsetneq Z^{\prime}\subsetneq Z\\}.$

In other words, $\mathtt{NTCZ}_{\mathbbm{B}_{S},\mathcal{I}}(X)$ simply
consists of the minimal non-trivial zeros of $\mathcal{I}$ that are strictly
above $X$. Observe that we have
$\mathtt{NTCZ}_{\mathbbm{B}_{S},\mathcal{I}}(X)=\emptyset$ whenever
$X\notin\mathcal{I}$. We now define _$k$ -decomposable_ downsets.

######  Definition 7.2.

A configuration $\mathcal{I}$ of $\mathbbm{B}_{S}$ that is a downset is called
_$k$ -decomposable_ if for every $X\in\mathbbm{B}_{S}$ we have
$|\mathtt{NTCZ}_{\mathbbm{B}_{S},\mathcal{I}}(X)|\leq k$.

This intuitively means that, in every upset, there are at most two non-trivial
covering zeroes. We believe that the following is true, but have not
completely formalized the proof.

######  Conjecture 7.3.

For every finite $S$, for every configuration $\mathcal{I}$ of
$\mathbbm{B}_{S}$ that is a $2$-decomposable downset of $\mathbbm{B}_{S}$, we
have that
$\mathcal{I}\in\bullet(\mathtt{NCPD}_{\mathbbm{B}_{S}}(\mathcal{I}))$.

###### Proof sketch..

For an element $X\in\mathbbm{B}_{S}$, let
$I_{X}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\\{{\downarrow_{\mathbbm{B}_{S}}(Y)}\cap{\uparrow_{\mathbbm{B}_{S}}(X)}\mid
Y\in{\uparrow_{\mathbbm{B}_{S}}(X)},\allowbreak\hat{\mu}_{\mathbbm{B}_{S},\mathcal{I}}(Y)\neq
0\\}$. The idea of the proof would be to show by top-down induction on
$\mathbbm{B}_{S}$ that for every $X\in\mathbbm{B}_{S}$, we have
$\mathcal{I}\cap{\uparrow_{\mathbbm{B}_{S}}(X)\in\bullet(I_{X})}$. Applying
this claim to $X=\emptyset$ yields the desired result. To show this, we use
similar tools to those developed for the proof of Theorem 6.2, extended with
an accounting of Euler characteristics of diverse sets of configurations. It
does not seem that the proposed proof would directly generalize to the general
case, or indeed to $3$-decomposable configurations. ∎

#### Strengthenings.

We present here two possible orthogonal ways in which we canstrengthen the
conjecture; we do not know whether the stronger conjectures are true, nor
whether they are equivalent to the original conjecture.

First, in view of Proposition 4.7, we could require that the non-trivial
intersections are only used positively or only negatively depending on the
sign of their Möbius value. Indeed, Proposition 4.7 implies that, on tight
intersection lattices, the non-trivial intersections have total multiplicity
equal to their Möbius value, but they may be used both positively and
negatively. Likewise, in view of Proposition 5.8, we could require that the
principal downsets are only used positively and negatively.

Second, we do not know if the witnessing trees can be required to be left-
linear, i.e., whether we can obtain $\hat{1}$ (for the $\mathtt{NCI}$
conjecture) or the desired configuration (for the $\mathtt{NCPD}$ conjecture)
by a series of operations where, at each step, we add a (disjoint) non-trivial
intersection (or principal downset), or subtract one (which must be a subset).
For instance, this formulation does not allow us to express a disjoint union
of two configurations themselves obtained with more complex witnessing trees.
This stronger conjecture is the topic of the question asked in [Amarilli,
2019] (up to replacing upsets by downsets and to working in general lattices
instead of only on Boolean lattices). This question also explains why the
conjecture is false if asked about general DAGs (instead of lattices), and
shows that the conjecture can be true for so-called _crown-free lattices_.

We note that the construction for the proof of Theorem 6.2 (or the one that we
have in mind for Conjecture 7.3) does not satisfy either of these
strengthenings. However, the proof of Fact 4.8 can be adjusted to satisfy the
left-linear condition.

#### Counterexample search.

We have implemented a search for counterexamples of the $\mathtt{NCI}$
conjecture. We consider Sperner families [Monet, 2020b], which give all sets
of subsets of a base set of $n$ elements that are non-equivalent (i.e., that
are not the same up to permuting the elements). We have checked in a brute-
force fashion that the conjecture holds up to $n=5$, i.e., on all intersection
lattices such that $\hat{1}$ has cardinality at most $5$. Unfortunately,
already for $n=6$ there are intersection lattices that are too large for the
computation to finish sufficiently quickly. We also generated random
intersection lattices over larger sets of elements, but could not find a
counterexample (assuming that our code is correct). The code checks the strong
version of the $\mathtt{NCI}$ conjecture in the previous terminology, i.e., it
searches for left-linear trees and requires the non-trivial intersections to
be used precisely with the right polarity. The code is available as-is
[Amarilli, 2023]. We have also improved the implementation to search for
solutions on each lattice using a SAT-solver rather than a brute-force search:
this speeds up the computation but also did not yield any counterexample.

We had also implemented, earlier, a search for counterexamples of an
alternative phrasing of the $\mathtt{NCPD}$ conjecture: see [Amarilli et al.,
2020]. This also illustrates that the $\mathtt{NCPD}$ conjecture is false if
the configuration to reach is not a downset; see Figure 4 of [Amarilli et al.,
2020] (up to reversing directions, i.e., considering downsets instead of
upsets).

## References

  * [Amarilli, 2019] Amarilli, A. (2019).  Lighting up all elements of a poset by toggling upsets.  Theoretical Computer Science Stack Exchange.  URL:https://cstheory.stackexchange.com/q/45679 (version: 2019-10-12).
  * [Amarilli, 2023] Amarilli, A. (2023).  Code.  https://gitlab.com/Gruyere/mobius-unions-differences/-/blob/master/code_a3nm/brute_sets.cpp.
  * [Amarilli et al., 2020] Amarilli, A., Jachiet, L., and Monet, M. (2020).  Which sets can be expressed as disjoint union and subset complement without möbius cancellations?  https://mikael-monet.net/share/note.pdf. Unpublished.
  * [Hirsch and McLean, 2017] Hirsch, R. and McLean, B. (2017).  Disjoint-union partial algebras.  Log. Methods Comput. Sci., 13(2).
  * [Monet, 2020a] Monet, M. (2020a).  Solving a special case of the intensional vs extensional conjecture in probabilistic databases.  In PODS.
  * [Monet, 2020b] Monet, M. (2020b).  Sperner families generator.  https://gitlab.com/Gruyere/sperner-families-generator.
  * [Rota, 1964] Rota, G.-C. (1964).  On the foundations of combinatorial theory I. Theory of Möbius functions.  Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 2(4).
  * [Stanley, 2011] Stanley, R. P. (2011).  Enumerative Combinatorics: Volume 1.  2nd edition.