CNFs and DNFs with Exactly $k$ Solutions

$\mathbb{N}$ denotes the set of natural numbers. We use $\log k$ to denote ${\log }_{2}k$. For a set $S$, $|S|$ and $2^S$ denote its cardinality and power set, respectively. The union of $A$ and $B$ is denoted as $A\cup B$. The union of two disjoint sets $A,B$ is denoted as $A\bigsqcup B$. The notation $[a,b]$ represents $\{a,a+1\mathrm{\cdots }b\}$ and $[b]$ represents $[1,b]$. For every number $i$, we create distinct copies $i_0,i_1,i_2\mathrm{\cdots }$. The set ${[w]}_i$ represents $\{1_i,2_i\mathrm{\cdots }{w}_i\}$. Note that the sets $[w],{[w]}_0,{[w]}_1\mathrm{\cdots }$ are all different from each other as these sets are pairwise disjoint. Given a family of sets $𝒮=\{S_1,S_2\mathrm{\cdots }{S}_t\}$ and a set $X$, we define $𝒮+X=\{S_1\cup X,S_2\cup X\mathrm{\cdots }{S}_t\cup X\}$.

An anti-chain is a subset $𝒜$ of a partially ordered set $P$ such that any two distinct elements of $𝒜$ are incomparable. An (order) ideal (also called semi-ideal, down-set, or monotone decreasing subset) of $P$ is a subset $I$ of $P$ such that if $t\in I$ and $s\le t$, then $s\in I$. Similarly, a dual order ideal (also called up-set or monotone increasing subset) is a subset $I$ of $P$ such that if $t\in I$ and $s\ge t$, then $s\in I$ [18]. When $P$ is finite, there is a one-to-one correspondence between anti-chains of $P$ and order ideals: the anti-chain $𝒜$ associated with the order ideal $I$ is the set of maximal elements of $I$, while $I=\{s\in P\mid s\le t\text{ for some }t\in 𝒜\}$. Then the anti-chain $𝒜$ is said to generate the ideal $I=\mathrm{𝐈𝐃}(𝒜)$.

Note that the minimal family of sets that generates a given ideal is an antichain.

Observe that for every natural number $k$, there is a family of sets $𝒮=\{\mathrm{\varnothing },\{1\},\{2\}\mathrm{\cdots }\{k-1\}\}$ such that $|\mathrm{𝐈𝐃}(𝒮)|=k$. Therefore, $\alpha (k)$ exists for all $k$ and moreover, $\alpha (k)\le k$. In this work, we establish more meaningful bounds on $\alpha (k)$.

Ideals and their symmetric counterpart filters are central concepts in the study of set systems. These concepts appear in some of the most fundamental theorems regarding set systems. For example, Bollobás and Thomason proved that every non-trivial monotone increasing/decreasing property of subsets of a set has a threshold function [5], in the probabilistic model where each element is chosen with probability $p$. Here, monotone decreasing property corresponds to ideals. This is one of the most significant results in the theory of random graphs (see chapter $6$ of [4]).

Another well-known result on ideals and dual order ideals is Kleitman’s lemma [12], which triggered a long line of research on correlation-type inequalities, culminating in the Four Functions Theorem of Ahlswede and Daykin [1] (see chapter $6$ of [3]). When studying extremal problems on set systems, it is often sufficient to prove the extremality restricted to set systems that are ideals or dual-order ideals. For example, see Kleitman’s proof establishing a tight bound for the cardinality of maximal $l$-intersecting families [13] (see chapter 13 of [4]).

In chapter $17$ of [4], Bollabás discusses theorems of the form $(m,k)\to (r,s)$ regarding traces. Such a theorem means if the universe $X=[k]$ and a family $ℱ$ consists of $m$ subsets of $X$, then there exists an $s$-element subset $S$ of $X$ such that when we take the intersection of $S$ with the members of $ℱ$, we get at least $r$ distinct subsets. Alon [2] and Frankl [11] independently proved that to establish any theorem of the form $(m,k)\to (r,s)$, it is sufficient to prove the corresponding statement when $ℱ$ is restricted to an ideal [11].

Ideals are also studied under the name abstract simplicial complex or abstract complex. This represents a combinatorial description of the geometric notion of a simplicial complex [15]. In the context of matroids and greedoids, these are also referred to as independence systems [14].

Several questions closely related to our work have been studied in the literature. For instance, Duffus, Howard, and Leader investigated the maximum cardinality of an anti-chain that can be present in a given ideal [9]. The problem we discuss in this paper – finding the minimum cardinality $\alpha (k)$ of the anti-chain that can generate an ideal of a given size $k$ – has been examined by both computer scientists and combinatorialists due to its applications in model counting.

The model counting problem for monotone DNF formulae has an interesting connection to the ideals of set systems. In fact, these problems are essentially equivalent. Let $x_1,x_2,\mathrm{\dots },x_m$ be the set of positive literals used in the monotone DNF formulae we consider. An assignment assigns a truth value to each of these $m$ variables; if the formula evaluates to TRUE under this assignment, then the assignment is called a satisfying assignment.

Take the universe $U=[m]=\{1,\mathrm{\dots },m\}$. Given any subset $S$ of $U$, we can associate to $S$ a term $T_S={\bigwedge }_{i\in S}{x}_i$. Conversely, given a term $T=\{x_{i_1}\wedge x_{i_2}\wedge \mathrm{\dots }\wedge x_{i_t}\}$ of a monotone DNF formula, we can associate the subset $S_T=\{i_1,i_2,\mathrm{\dots },i_t\}$ to $T$. Also, to a family $ℱ=\{S_1,S_2,\mathrm{\dots },S_t\}$ of subsets of $U$, we can associate a monotone DNF formula $f_{ℱ}=T(S_1)\vee T(S_2)\vee \mathrm{\dots }\vee T(S_t)$. Conversely, to a monotone DNF formula $f=T_1\vee T_2\vee \mathrm{\dots }\vee T_{\mathrm{\ell }}$, we can associate a family of subsets of $U$, namely ${ℱ}_f=\{S_{T_1},S_{T_2},\mathrm{\dots },S_{T_{\mathrm{\ell }}}\}$.

Thus, there is a one-to-one correspondence between monotone DNF formulae using variables $x_1,x_2,\mathrm{\dots },x_m$ and families of subsets of $U$.

Let $ℱ$ be a family of subsets. Then let $\overline{ℱ}=\{\overline{S}:S\in ℱ\}$, where $\overline{S}=U\setminus S$ is the complement of $S$. We can show that the set of satisfying assignments of a monotone DNF formula $f$ has a one-to-one correspondence with the ideal generated by the family $\overline{{ℱ}_f}$. This is because for $f$ to be satisfied, at least one term of $f$ must be satisfied. If term $T_i$ is satisfied, then all literals appearing in $T_i$ must be set to TRUE. So, the set of literals that are set to FALSE must correspond to a set of indices $S^{\prime }$ such that $S^{\prime }\subseteq \overline{S_{T_i}}$. In other words, $S^{\prime }\in \mathrm{𝐈𝐃}(\overline{{ℱ}_f})$.

The converse is also true: For $S^{\prime }\in \mathrm{𝐈𝐃}(\overline{{ℱ}_f})$, the assignment where each variable $x_i$ with $i\in S^{\prime }$ is set to FALSE and the remaining variables set to TRUE will be a satisfying assignment for $f$. This is because there will be a superset of $S^{\prime }$ in $\overline{{ℱ}_f}$, and the term in $f$ that corresponds to the complement of this superset would evaluate to TRUE. Since every satisfying assignment can be bijectively mapped to the set of variables that are set to FALSE, the set of satisfying assignments of $f$ are bijectively mapped to the ideal of $\overline{{ℱ}_f}$. From this discussion, we have:

A key insight for our analysis is understanding how the inclusion-exclusion principle applies to unions of power sets. This is captured in the following observation:

We now introduce two fundamental operations that will serve as building blocks for our upper-bound construction. These operations allow us to construct ideals with specific cardinalities efficiently.

Using the operations we’ve developed, we can now establish a simple relationship between $\alpha (k)$ and the block count of $k$:

We now present our main technical result, which establishes a much tighter bound on $\alpha (k)$. The key insight is to construct specialized sets for numbers of a particular form and then extend these constructions to all natural numbers.

The proof of this theorem is technical and will be presented in Section 4.5. First, we’ll show how this theorem helps us establish our main result, Theorem 3.

We now present the most technical part of our proof: constructing an ideal with specific properties for numbers of the form $2^{3q^2}+\beta$ where . The key idea is to carefully design a collection of sets based on the binary representation of $\beta$.

Let $m=2^{3q^2}+\beta$ where . For $i,j\in [0,q-1]$, we define $F_{ij}$ in the following way:

• $\mathrm{■}$

  If the $(jq+i+1)$th least significant bit of $\beta$ is $1$, then fix $F_{ij}=\mathrm{\varnothing }$.
  Let ${ℱ}_0$ be the family of all such sets.

• $\mathrm{■}$

  If the $(jq+i+1)$th least significant bit of $\beta$ is $0$, then fix $F_{ij}={[i]}_{jq+i}$.
  Let ${ℱ}_1$ be the family of all such sets.

We note that the least significant bit of $\beta$ is indexed to be the $1$st bit. On the other hand the indices $i,j$ start from $0$. From this construction, several important properties immediately follow:

These observations lead to the following key relationship:

Using these $F_{ij}$ sets, we construct two families of sets that will form the basis of our ideal. For all $i,j\in [0,q-1]$, let $S_i^{\prime }=[q^2],T_j^{\prime }=[jq]$ and let

We define $𝒮=\{S_0,\mathrm{\cdots }{S}_{q-1}\},{𝒮}^{\prime }=\{S_0^{\prime },\mathrm{\cdots }{S}_{q-1}^{\prime }\},𝒯=\{T_0,\mathrm{\cdots }{T}_{q-1}\}$ and ${𝒯}^{\prime }=\{T_0^{\prime },\mathrm{\cdots }{T}_{q-1}^{\prime }\}$

Our strategy is to compute the cardinality of the ideal generated by $𝒮\cup 𝒯$. We want to show that $\alpha (|\mathrm{𝐈𝐃}(𝒮\cup 𝒯)|)\le 2q$, and since $q=O(\sqrt{\log k})$, this would give us the desired upper bound if $|\mathrm{𝐈𝐃}(𝒮\cup 𝒯)|=\beta =m-2^{3q^2}$. However, this equality doesn’t hold exactly, but we’ll show that the difference has a small $\alpha$-value.

Computing $|\mathrm{𝐈𝐃}(𝒮\cup 𝒯)|$ directly is complex, so we first relate it to $|\mathrm{𝐈𝐃}({𝒮}^{\prime }\cup {𝒯}^{\prime })|$, which equals $2^{q^2}$ because all sets in ${𝒮}^{\prime }$ and ${𝒯}^{\prime }$ are subsets of $[q^2]$ and every $S_i^{\prime }=[q^2]$.