How many $k$-SAT functions on $n$ boolean variables are there?
What does a typical such function look like?
Bollobás, Brightwell, and Leader conjectured that, for each fixed $k \ge 2$, the number of $k$-SAT functions on $n$ variables is $(1+o(1))2^{\binom{n}{k} + n}$, or equivalently: a $1-o(1)$ fraction of all $k$-SAT functions are unate, i.e., monotone after negating some variables. They proved a weaker version of the conjecture for $k=2$. The conjecture was confirmed for $k=2$ by Allen and $k=3$ by Ilinca and Kahn.

We show that the problem of enumerating $k$-SAT functions is equivalent to a Turán density problem for partially directed hypergraphs.
Our proof uses the hypergraph container method.
Furthermore, we confirm the Bollobás–Brightwell–Leader conjecture for $k=4$ by solving the corresponding Turán density problem.
Our solution applies a recent result of Füredi and Maleki on the minimum triangular edge density in a graph of given edge density.
In an appendix (by Nitya Mani and Edward Yu), we further confirm the $k=5$ case of the conjecture via a brute force computer search.

§ INTRODUCTION

§.§ Background

We study the following basic question on boolean functions:

How many $k$-SAT functions on $n$ boolean variables are there?
What does a typical such function look like?

This question was first studied by Bollobás, Brightwell, and Leader [7].
We focus on the regime where $k$ is fixed and $n \to \infty$.
We will consider $k$-SAT functions in their disjunctive normal form (DNF). It would be an equivalent problem to enumerate $k$-SAT functions in their conjunctive normal form (CNF) since the negation of a DNF is a CNF and vice-versa.
For our purpose, a $k$-SAT function on $n$ boolean variables is a function $f \colon \{0,1\}^n \to \{0,1\}$ of the form

\[
f(x_1, \dots, x_n) = C_1 \lor C_2 \lor  \cdots \lor C_m,
\]

where each $C_i$ has the form $z_1 \land \cdots \land z_k$ with $z_1, \dots, z_k \in \{x_1, \ol {x_1}, \dots, x_n, \ol {x_n}\}$.
Here we call $x_1, \dots, x_n$ the variables.
Each of $x_i$ and $\ol{x_i}$ is a called a literal (positive literal and negative literal, respectively). Each clause $C_i$ is a conjunction (“and”) of $k$ literals.
We further restrict that every clause uses $k$ distinct variables (e.g., both $x_1 \land x_2$ and $x_1 \land x_2 \land \ol{x_2}$ are invalid 3-SAT clauses).
This restriction does not lose any generality (the first example can be replaced by $(x_1 \land x_2 \land x_3) \lor (x_1 \land x_2 \land \ol{x_3})$ and the second example is a clause that is never satisfied and so can be deleted).
To simplify notation, we will drop the “and” symbol $\land$ when writing a clause.
A formula is a set of clauses.
For instance, the $2$-SAT formula
$(x_1 \land x_2) \lor  (\ol{x_1}\land x_3) \lor (x_3 \land x_4)$ is written as
$\{x_1x_2, \ol{x_1} x_3, x_3 x_4\}$.
Every $k$-SAT function has a $k$-SAT formula, but different $k$-SAT formulae may correspond to the same $k$-SAT function.

Given the importance of $k$-SAT functions, it is a natural question to try to understand how rich this family of functions is.
While the total number of functions $\{0,1\}^n \to \{0,1\}$ is $2^{2^n}$, the number of $k$-SAT functions is significantly smaller.
As an easy upper bound, since there are $2^k \binom{n}{k}$ possible clauses, the number of $k$-SAT formulae is $2^{2^k \binom{n}{k}}$.
So the number of $k$-SAT functions is at most $2^{2^k \binom{n}{k}}$,
which is significantly smaller than $2^{2^n}$ for a fixed $k$ and large $n$.
The actual number of $k$-SAT functions turns out to be considerably smaller than even this upper bound.

A $k$-SAT formula is monotone if it only uses positive literals.
A $k$-SAT function is monotone if it has a monotone $k$-SAT formula.
There are $\binom{n}{k}$ possible monotone clauses, and every monotone $k$-SAT formula produces a unique monotone $k$-SAT function, and so there are $2^{\binom{n}{k}}$ monotone $k$-SAT functions.

A $k$-SAT function or formula is unate if it is monotone after replacing some variables with their negations (e.g., $\{\ol{x_1}x_2, \ol{x_1}x_2,x_2x_3\}$ is unate but $\{\ol{x_1}x_2, x_1x_2, x_2x_3\}$ is not).
The number of unate $k$-SAT formulae that use all $n$ variables is at least

\[
2^n \left(2^{\binom{n}{k}} - n 2^{\binom{n-1}{k}} \right) = (1+o(1)) 2^{n + \binom{n}{k}},
\]

for fixed $k$ as $n \to \infty$. Indeed, for each variable $x_i$, there are $2^n$ choices as to whether to use it as a positive literal or a negative literal and there are at least $2^{\binom{n}{k}} - n 2^{\binom{n-1}{k}}$ monotone formulae that use all $n$ variables.
All unate $k$-SAT formulae represent distinct functions, and thus the number of unate $k$-SAT functions on $n$ variables is at least $(1+o(1)) 2^{n + \binom{n}{k}}$.

Bollobás, Brightwell, and Leader [7] conjectured the following.

Fix $k \ge 2$.
The number of $k$-SAT functions on $n$ boolean variables is $(1+o(1)) 2^{n + \binom{n}{k}}$.
Equivalently: a $1-o(1)$ fraction of all $k$-SAT functions on $n$ variables are unate.

Bollobás, Brightwell, and Leader also proposed a weaker version of this conjecture, namely that the number of $k$-SAT functions on $n$ boolean variables is $2^{(1+o(1))\binom{n}{k}}$, and established this weaker conjecture for $k=2$.
<ref> was proved for $k=2$ by Allen [1] and for $k=3$ by Ilinca and Kahn [18]. The proofs in [7, 1] for $k=2$ used graph regularity ([17] gave an alternate regularity-free proof for $k=2$), whereas the proof for $k=3$ [18]  used hypergraph regularity. Bollobás and Brightwell [6] further conjectured that even if $k = k(n)$ is allowed to increase with $n$, as long as $k \le (1/2-c) n$ for some constant $c > 0$, the number of $k$-SAT functions on $n$-variables is $2^{(1+o(1))\binom{n}{k}}$. In that paper [6], they proved bounds on the number of $k$-SAT functions on $n$ variables in the regime $k \ge n/2$, where a completely different asymptotic behavior arises.

The goal of our paper here is two-fold. First, we reduce <ref> for each $k$ to a specific extremal problem about partially directed hypergraphs, analogous to classical hypergraph Turán density problems.
Hypergraph Turán density problems have been intensely studied, although only solved in a relatively small number of cases (see survey by Keevash [22]).
Our reduction is essentially lossless, as we show that the $k$-SAT enumeration problem (for fixed $k$) is equivalent to the corresponding Turán density problem.
Whereas previous approaches to enumerating $k\SAT$ functions looked at specific forbidden structures (e.g., odd-blue-triangle-free graphs [7, 1, 17]), our approach is more systematic and identifies all relevant obstructions.
Our reduction uses the hypergraph container method, as opposed to the graph and hypergraph regularity methods used in earlier works.

The second goal of our paper is to prove <ref> for $k=4$ by solving the corresponding hypergraph Turán density problem, <ref> below.
We also give an easier proof of the corresponding $k=3$ problem compared to the methods in [18].
For every fixed $k$, in principle one might be able to confirm the conjecture (after our reduction) via a finite computation, but the size of the computation grows extremely quickly (the approach in [18] for $k=3$ essentially amounts to checking 5-vertex cases by hand).
To solve the $k=4$ case of the problem, we apply a recent result of Füredi and Melaki [13] on the minimum number of triangular edges in a graph with a given number of vertices and edges.
In an appendix, we further confirm the $k=5$ case via a brute force computer search.
To prove <ref> for additional values of $k$ (or ideally for all $k$), it remains to solve a Turán density type problem, <ref> below.

§.§ Acknowledgments
Zhao first learned of this problem as a graduate student from Jeff Kahn and would like to thank him for the encouragement to work on this problem.

§.§ An extremal open problem

We state a tantalizing conjecture that would imply <ref>.

A partially directed graph (also known as a mixed graph) is formed by taking a graph and orienting a subset of its edges (to orient an edge means to choose one of two directions for the edge), so every edge is either directed or undirected. An example is illustrated below.

v/.style = circle, fill, inner sep = 0pt, minimum size = 3pt,
e/.style = thick, red, postaction=decorate,decoration=
mark=at position .5*+1.5pt
with angle 90
[v,label=left:1] (1) at (0,0) ;
[v,label=above left:2] (2) at (1,1) ;
[v,label=above right:3] (3) at (2,1) ;
[v,label=right:4] (4) at (3,0) ;
[e] (2)–(4);
[e] (1)–(2);

Given a pair of partially directed graphs $\vec H$ and $\vec G$, we say that $\vec H$ is a subgraph of $\vec G$ if one can obtain $\vec H$ from $\vec G$ by a combination of (1) removing vertices, (2) removing edges, and (3) removing the orientation of some edges.

The following partially directed graph plays a special role:

\[
\vec T_2 =
\begin{tikzpicture}[
baseline={([yshift=-.8ex]current bounding box.center)},
v/.style = {circle, fill, inner sep = 0pt, minimum size = 3pt},
e/.style = {thick, red, postaction={decorate,decoration={
mark=at position .5*\pgfdecoratedpathlength+1.5pt
with {\arrow{angle 90}}
\node[v] (1) at (90:1) {};
\node[v] (2) at (210:1) {};
\node[v] (3) at (-30:1) {};
\draw (3)--(1)--(2);
\draw[e] (2)--(3);
\end{tikzpicture}.
\]

Below, the left graph contains $\vec T_2$ as a subgraph, and the right does not contain $\vec T_2$ as a subgraph.

v/.style = circle, fill, inner sep = 0pt, minimum size = 3pt,
e/.style = thick, red, postaction=decorate,decoration=
mark=at position .5*+1.5pt
with angle 90

[v] (1) at (0,0) ;
[v] (2) at (1,1) ;
[v] (3) at (2,1) ;
[v] (4) at (3,0) ;
[e] (2)–(3);
[e] (3)–(4);
[e] (1)–(2);

[v] (1) at (0,0) ;
[v] (2) at (1,1) ;
[v] (3) at (2,1) ;
[v] (4) at (3,0) ;
[e] (1)–(2);

The following statement implies <ref> for $k=2$ (see <ref> for the full statement of the implication).

For all sufficiently large $n$,
every $n$-vertex partially directed graph with $\alpha \binom{n}{2}$ undirected edges and $\beta \binom{n}{2}$ directed edges and not containing $\vec T_2$ as a subgraph satisfies

\[
\alpha + (\log_2 3)\beta \le 1.
\]

In fact, we know the optimal constant in front of $\beta$: it is $2-o(1)$ (see <ref>).
By orientating all the edges of $K_{\floor{n/2}, \ceil{n/2}}$ from one part to the other part, we obtain a partially directed graph with $\floor{n^2/4}$ directed edges and no $\vec T_2$. This construction shows that one cannot do better than $\beta = 2-o(1)$.

Now let us generalize the problem to hypergraphs.

A partially directed 3-graph (3-PDG) is formed by taking a 3-graph and orienting a some subset of edges. Here to orient an edge means to pick some vertex in the edge (we say that this is a directed edge that is directed towards or pointed at the chosen vertex). We notate a directed edge by putting a $\vee$ on top of the pointed vertex, e.g., $12\wc3$.

This following 3-PDG plays the role of $\vec T_2$ from earlier:

\[
\vec T_3
\begin{tikzpicture}[
baseline={([yshift=-.8ex]current bounding box.center)},
v/.style = {circle, fill, inner sep = 0pt, minimum size = 3pt},
e/.style = {thick, red, postaction={decorate,decoration={
mark=at position .5*\pgfdecoratedpathlength+1.5pt
with {\arrow{angle 90}}
\node[v] (0) at (0:0) {};
\node[v] (1) at (90:1) {};
\node[v] (2) at (210:1) {};
\node[v] (3) at (-30:1) {};

\draw[red, thick, rounded corners=10pt] (90:.4) -- +(-40:1.6) coordinate (a) -- +(-140:1.6)--cycle;
\draw[red,  thick] ($ (a) + (-180:.6) $) arc (180:140:.6);

\draw[rounded corners=10pt,rotate=120] (90:.4) -- +(-40:1.6) coordinate (a) -- +(-140:1.6)--cycle;
\draw[rounded corners=10pt,rotate=-120] (90:.4) -- +(-40:1.6) coordinate (a) -- +(-140:1.6)--cycle;
\end{tikzpicture}
\qquad
\text{edges = }
\{ 123, 12\wc 4, 134 \}.
\]

We define subgraph the same as earlier, i.e., obtainable by deleting vertices and edges as well as removing the orientation of some edges.

We prove the following result, which in turn (via <ref>) implies <ref> for $k=3$.

For all sufficiently large $n$,
every $n$-vertex 3-PDG with $\alpha \binom{n}{3}$ undirected edges and $\beta \binom{n}{3}$ directed edges and not containing $\vec T_3$ as a subgraph satisfies

\[
\alpha + (\log_2 3)\beta \le 1.
\]

We can extend the above definitions to partially directed $k$-graphs ($k$-PDG).
For each $k \ge 3$, we define $\vec T_k$, the partially directed $k$-triangle, as the $k$-PDG obtained by starting with $\vec T_2$ and then adding $k-2$ common vertices to all three edges, e.g.,

\[
\vec T_4
\begin{tikzpicture}[
baseline={([yshift=-.8ex]current bounding box.center)},
v/.style = {circle, fill, inner sep = 0pt, minimum size = 3pt},
e/.style = {thick, red, postaction={decorate,decoration={
mark=at position .5*\pgfdecoratedpathlength+1.5pt
with {\arrow{angle 90}}
\node[v] (0) at (0:.2) {};
\node[v] (0') at (180:.2) {};

\node[v] (1) at (90:1) {};
\node[v] (2) at (210:1) {};
\node[v] (3) at (-30:1) {};

\draw[red, thick, rounded corners=10pt] (90:.4) -- +(-40:1.6) coordinate (a) -- +(-140:1.6)--cycle;
\draw[red,  thick] ($ (a) + (-180:.6) $) arc (180:140:.6);

\draw[rounded corners=10pt,rotate=120] (90:.4) -- +(-40:1.6) coordinate (a) -- +(-140:1.6)--cycle;
\draw[rounded corners=10pt,rotate=-120] (90:.4) -- +(-40:1.6) coordinate (a) -- +(-140:1.6)--cycle;
\end{tikzpicture}
\qquad
\text{edges = }
\{ 1234, 123\wc 5, 1245 \},
\]

\[
\vec T_5
\begin{tikzpicture}[
baseline={([yshift=-.8ex]current bounding box.center)},
v/.style = {circle, fill, inner sep = 0pt, minimum size = 3pt},
e/.style = {thick, red, postaction={decorate,decoration={
mark=at position .5*\pgfdecoratedpathlength+1.5pt
with {\arrow{angle 90}}
\node[v] at (90:.1) {};
\node[v] at (210:.1) {};
\node[v] at (-30:.1) {};

\node[v] (1) at (90:1) {};
\node[v] (2) at (210:1) {};
\node[v] (3) at (-30:1) {};

\draw[red, thick, rounded corners=10pt] (90:.4) -- +(-40:1.6) coordinate (a) -- +(-140:1.6)--cycle;
\draw[red,  thick] ($ (a) + (-180:.6) $) arc (180:140:.6);

\draw[rounded corners=10pt,rotate=120] (90:.4) -- +(-40:1.6) coordinate (a) -- +(-140:1.6)--cycle;
\draw[rounded corners=10pt,rotate=-120] (90:.4) -- +(-40:1.6) coordinate (a) -- +(-140:1.6)--cycle;
\end{tikzpicture}
\qquad
\text{edges = }
\{ 12345, 1234\wc 6, 12356 \}.
\]

For each fixed $k$, the following conjecture implies <ref> (via <ref>).

Fix $k \ge 2$.
For all sufficiently large $n$,
every $n$-vertex $k$-PDG with $\alpha \binom{n}{k}$ undirected edges and $\beta \binom{n}{k}$ directed edges and not containing $\vec T_k$ as a subgraph satisfies

\[
\alpha + (\log_2 3)\beta \le 1.
\]

We also show that by enlarging the set of forbidden subgraphs from $\vec T_k$ to some special finite set $\cF_k$, the extremal claim $\alpha + (\log_2 3)\beta \le 1$ becomes essentially equivalent to <ref>. This set $\cF_k$ is constructed in <ref> below.

For each $k$, if the statement is true for some $n$, then it is true for all larger $n$ by a standard averaging argument.
So in principal, the conjecture could be verified via a finite computation.
However, this computation grows extremely quickly with $k$.
<ref> contains our proof of the conjecture for $k \le 4$ via extremal graph theoretic techniques.
Appendix <ref> contains a brute force solution to $k=5$.
The brute force method is unlikely to extend further, and so the extremal graph theoretic techniques may be valuable for future work.

§.§ Strategy

Now let us describe our strategy for enumerating $k$-SAT functions.
Our setup is closest to the work of Ilinca and Kahn [18] where they enumerated $3$-SAT functions.

A formula $G = \{ C_1, C_2, \dots , C_l\}$ on variables $\{x_1, \ldots x_n\}$ is minimal if deleting any clause from $G$ changes the resulting boolean function.
Equivalently, $G$ is minimal if for each clause $C_i \in G$, there is an assignment $\mathsf w \in \{0, 1\}^n$ that satisfies $C_i$ but no other $C_j \in G$, $j \neq i$. We call such $\mathsf w$ (not necessarily unique) a witness to $C_i$.[In [18], the term “non-redundant” is used for what we are calling “minimal.”]

The $2$-SAT formula $\{wx,wy,x\ol{z},\ol{y}z\}$ is not minimal since it is impossible to satisfy only $wx$ and no other clause.
Indeed, if we attempt to only satisfy $wx$, we must assign $w=1$ and $x=1$;
to avoid satisfying $wy$ and $x\ol{z}$, we must assign $y=0$ and $z=1$, which would then lead to the final clause $\ol{y}z$ being satisfied.

Every $k$-SAT function can be expressed as a minimal formula, but possibly in more than one way. We upper bound the number of minimal $k$-SAT formulae, which in turn upper bounds the number of $k$-SAT functions.

To bound the number of minimal $k$-SAT formulae, we identify a fixed set $\cB$ of non-minimal formulae, and then find an upper bound to the number of (not necessarily minimal) formulae not containing anything from $\cB$ as a subformulae.
We will show that, by setting $\cB$ to be all non-minimal formulae on a constant number of variables, the number of $\cB$-free formulae is asymptotically the same as the number of minimal formulae.

Given a formula $G$, a subformula of $G$ is a subset of clauses of $G$.
We say that two formulae are isomorphic if one can be obtained from the other by relabeling variables.
Given another formula $F$, a copy of $F$ in $G$ is a subformula of $G$ that is isomorphic to $F$.
Given a set $\cB$ of $k$-SAT formulae, we say that $G$ is $\cB$-free if $G$ has no copy of $B$ for every $B \in \cB$.

The problem of counting $\cB$-free formulae is analogous to counting $F$-free graphs on $n$ vertices.
A classic result by Erdős, Kleitman, and Rothschild [11] shows that almost all triangle-free graphs are bipartite.
Erdős, Frankl, and Rödl [10] generalized this result and showed that for a fixed graph $F$, the number of $n$-vertex $F$-free graph is $2^{\operatorname{ex}(n, F) + o(n^2)}$.
This result was initially proved using the graph regularity method.
It can also be proved as quick application of the more recently developed hypergraph container method [3, 26] (see survey [4]).
Earlier works on $k$-SAT enumeration are closer in spirit to the regularity approach to counting $F$-free graphs.
Here we instead use the container method, which is simpler to carry out.

Here is a quick sketch of how to use the container method to enumerate $n$-vertex triangle-free graphs.
By an application of the hypergraph container theorem, there is a collection $\cG$ of $n$-vertex graphs (“containers”)
each with $(1/4 + o(1))n^2$ edges,
such that $\abs{\cG} = 2^{o(n^2)}$
and every $n$-vertex triangle-free graph is a subgraph of some container $G \in \cG$.
It then follows that the number of $n$-vertex triangle-free graphs is at most $\sum_{G \in \cG} 2^{e(G)} = 2^{(1/4 + o(1)) n^2}$.

As in the case of counting $F$-free graphs, the enumeration of $\cB$-free formulae reduces to a certain extremal problem.
Here the situation diverges from the graph theory setting.

A $k$-SAT formula is simple if no two clauses use exactly the same set of $k$ variables.

The 3-SAT formula $\{wxy, wx\ol{z},xyz\}$ is simple, whereas $\{xyz,xy\ol{z}\}$ is not.

What happens when we apply a similar approach to enumerate $\cB$-free formulae?
Every minimal $k$-SAT formula on $n$ variables can be made simple by removing $o(n^k)$ clauses (<ref>).
So let us focus on enumerating simple $\cB$-free formulae.
The container theorem gives us a collection $\cG$ of $n$-variable “container” formulae with $\abs{\cG} = 2^{o(n^k)}$
such that every $n$-variable $\cB$-free formula is a subformula of some $G \in \cG$.
Furthermore, every $G \in \cG$ is “not too large” in a certain sense.
For a container $G \in \cG$, suppose $\alpha \binom{n}{k}$ $k$-subsets of variables support exactly one clause, and $\beta \binom{n}{k}$ $k$-subsets of variables support exactly two clauses.
It will always be the case that $o(n^k)$ $k$-subsets of variables support more than two clauses.
Then the number of simple subformulae of $G$ is $2^{\alpha\binom{n}{k}} 3^{\beta\binom{n}{k}} 2^{o(n^k)}$, and we would like to guarantee that $\alpha + (\log_2 3) \beta \le 1 +o(1)$.

Even if we wish to only enumerate simple formulae, we need to solve an extremal problem for non-simple formulae.
This is not an inadequacy of our approach, but actually an essential feature of the problem (see a related discussion at the end of <cit.>).
This is where our situation differs from enumerating $F$-free graphs, which reduces to an extremal problem on $F$-free graphs instead of some more complicated object.

The extremal problem for formulae is rather unwieldly.
In earlier approaches, the idea is to isolate some specific patterns and analyze them by hand.
Here we take a different approach which is both simpler and more systematic.
We show that the extremal problem for formulae actually reduces to a Turán density type extremal problem on partially directed hypergraphs.
We explain what these objects are shortly in the next subsection.
We will define a concrete finite set $\cF_k$ of small partially directed $k$-graphs that turn out to completely capture the asymptotic enumeration of $k$-SAT functions.
This is a self-contained Turán density problem and can be studied independently of the $k$-SAT enumeration problem.
A solution to this Turán density problem would yield a resolution to <ref>.
If the Turán density conjecture were false, then there would be way more $k$-SAT functions than in <ref>.
Unfortunately, we were not able to resolve the Turán density conjecture in full, although we solve it for $k=4$, which is new.
Readers who are interested in working on the Turán problem only need to read the first two sections of this paper, as the rest of the paper concerns the reduction from the $k$-SAT enumeration problem to this Turán problem.

The container approach as described can only deduce an upper bound of the form $2^{(1+o(1))\binom{n}{k}}$.
Obtaining the tighter asymptotic $(1+o(1))2^{n + \binom{n}{k}}$ of <ref> requires additional stability arguments.
By analogy, the container method sketched earlier shows that there are $2^{(1/4+o(1))n^2}$ triangle-free graphs on $n$ vertices.
To obtain the Erdős–Kleitman–Rothschild result in its full strength, namely that $1-o(1)$ fraction of all triangle-free graphs are bipartite, one needs to apply additional stability arguments on top of the container method, as done in [2] (and later strengthened in [5]).

Recall that  <ref> is equivalent to saying that a $1-o(1)$ fraction of all $k$-SAT functions are unate.
Far-from-unate formulae can be effectively handled by the container argument.
The final piece to show is that that almost all nearly unate formulae are unate.
We do this by extending the argument from <cit.>, which only dealt with the $3$-SAT case;
our $k$-SAT argument has to overcome further technical challenges.

§.§ Partially directed hypergraphs

Now we provide some precise definitions.
While there are many possible notions of a directed hypergraph, the relevant notion for us is the one where a directed edge is an edge with along with “pointed” vertex on the edge.
A partially directed hypergraph is formed from a hypergraph by directing some of its edges and leaving others intact.

A partially directed $k$-graph, abbreviated $k$-PDG, is given by a set $V$ of $n$ vertices, and, for each unordered $k$-element subset $\{v_1, \dots, v_k\}$, one of the following possibilities:

(a) No edge with vertices $\{v_1, \dots, v_k\}$, or

(b) An undirected edge with vertices  $\{v_1, \dots, v_k\}$, or

(c) A directed edge using vertices  $\{v_1, \dots, v_k\}$ along with a choice of some $v_i \in \{v_1, \dots, v_k\}$;  we say that the edge is directed (or pointed) towards $v_i$. We notate such a directed edge by $v_1 \cdots \wc v_i \cdots v_k$.

In particular, no two edges (whether directed or undirected) of a $k$-PDG can use the exact same set of $k$ vertices.

This is the edge set of a $3$-PDG: $\{123,12\wc4, 134,235,\wc245\}$.

Non-examples of edge sets of $3$-PDGs include $\{123,12\wc 3\}$ (two edges using the same triple of vertices), $\{1\wc2\wc3\}$ (not a valid edge), and $\{123,12\}$ (not 3-uniform).

Given a $k$-PDG $\vec{H}$, let $e_u(\vec H)$ be the number of undirected edges in $\vec H$ and $e_d(\vec H)$ be the number of directed edges in $\vec H$. Denote their edge densities by

\[
\alpha(\vec{H}) = \frac{e_u(\vec H)}{\binom{n}{k}}
\quad \text{and} \quad
\beta(\vec{H}) = \frac{e_d(\vec H)}{\binom{n}{k}}.
\]

We say that a $k$-PDG $\vec{F}$ is a subgraph of another $k$-PDG $\vec{H}$ if we can obtain a $k$-PDG isomorphic to $\vec{F}$ starting from $\vec{H}$ by some sequence of actions of the following types: (a) deleting an edge, (b) deleting a vertex, and (c) forgetting the direction of an edge.

Given a set $\cF$ of $k$-PDGs, we say that a $k$-PDG $\vec{H}$ is $\cF$-free if $\vec{H}$ does not contain any element of $\cF$ as a subgraph.

We usually denote $k$-PDGs by simply writing their edge sets.

$\{123,12\wc4\}$ is a subgraph of $\{12\wc3,12\wc 4\}$ by (c) in <ref>.
However, $\{1\wc23,12\wc4\}$ is not a subgraph of $\{12\wc3,12\wc 4\}$.
Another example is that by removing the second edge from $\{123,1\wc24,12\wc5\}$, we obtain a subgraph isomorphic to $\{123,12\wc4\}$.

Given a set $\cF$ of $k$-PDGs, let $\pi(\cF, \theta)$ be the smallest real number such that every $n$-vertex $\cF$-free $k$-PDG $\vec{H}$ satisfies

\[
\alpha(\vec{H}) +\theta\cdot \beta(\vec{H})  \le \pi(\cF, \theta) + o_{n\to\infty}(1).
\]

We will consider the following finite family $\mcF_k$ of forbidden structures, that will completely certify minimality of the $k$-SAT formula associated to a particular $k$-PDG.

As it turns out, our proof of <ref> for $k=2,3,4$, and $5$, the Turán density problem only needs to forbid $\vec T_k$, which recall is the generalized triangle with one directed edge introduced in the previous subsection; $T_k$ is also the first listed element (a) of $\cF_k$ in <ref>.

Let $k\ge 2$ be an integer.
Let the family $\mcF_k$ be the set of $k$-PDGs that can be built from the following procedure, and furthermore are non-redundant in the sense of not containing as a subgraph a different $k$-PDG arising from the same procedure.

* Initialization. Start with a single edge $e_0$ that may be directed or undirected.
If $e_0$ is undirected, then let $S$ be its set of $k$ vertices.
If $e_0$ is directed, then let $S$ be the set of $k-1$ undirected vertices of $e_0$. Note that $S$ is a set of unpointed vertices and it will maintain this property later.

* Extensions. Add $j$ directed edges $e_1, \dots, e_j$, with $0 \le j \le k$, where each new edge $e_i$ is directed towards some new vertex $w_i$ and its $k-1$ remaining vertices are chosen from $S$. Here $w_1, \dots, w_j$ are all distinct and outside $e_0$. Let $T$ be the set of all $k+j$ vertices seen so far.

* Closure. Either

(a) add a new undirected edge contained in $T$ (note that this can only happen if we had $j > 0$ in the previous step, as every $k$ vertices are allowed to support at most one edge), or

(b) add an edge directed towards some new vertex $w_0 \notin T$ with its remaining $k-1$ vertices all contained in $T$ and at least one of these $k-1$ vertices outside $S$.

Call this final edge $e_{j+1}$.

It is perhaps unclear why the above forbidden structures are of interest. To give a brief glimpse, consider associating $\vec T_4 \in \mcF_4$ with the following $4$-SAT formula:
$$\phi_{\vec T_4} = (x_1 \land x_2 \land x_3 \land x_4) \lor (x_1 \land x_2 \land x_3 \land \overline{x_5}) \lor (x_1 \land x_2 \land x_4 \land x_5).$$

Observe that $\phi_{\vec T_4}$ is non-minimal, as satisfying the first clause by assigning $x_1 = x_2 = x_3 = x_4 = 1$ necessitates that one of the latter two clauses in $\phi_{\vec T_4}$ is satisfied (which one depends on our assignment of $x_5$). Further, any $4$-SAT formula that contains a pattern like $\phi_{\vec T_4}$ is also non-minimal. Thus, one can think of $\vec T_4$ as a a representation of a “short certificate for non-minimality” (noting that non-minimal formula may still lack a $\vec T_k$-type pattern).

Let us emphasize again that some of the subgraphs generated by this procedure may include another as a subgraph, in which case we do not include the supergraph in $\cF_k$. For example, both $F = \{123,124,13\wc4\}$ and $F' = \{12\wc 3,124,13\wc4\}$ can be generated by the procedure, but $F$ is a subgraph of $F'$ and so we do not include $F'$ in $\cF_3$;  on the other hand, $F \in \cF_3$ since no subgraph of $F$ other than itself can be generated by the procedure.

Every $k$-PDG in $\mcF_k$ has at most $2k$ vertices and at most $k+2$ edges.
Indeed, by the end of the extension step, we can have up to $2k$ vertices and $k+1$ edges.
If the closure edge adds a new vertex, then one of the edges added in the extension much must have been redundant (see previous remark).

Here are all the elements of $\cF_2$:

* $12,1\wc3,23$;

* $1\wc 2, 2\wc 3$.

Here are all the elements of $\cF_3$. For each $3$-PDG listed, the edges are printed in the order of their generation in <ref> (the initialization edge appears first and the closure edge appears last).

* $123, 12\wc 4, 134$

* $12\wc3,13\wc4$

* $123, 12\wc 4, 12\wc 5, 345$

* $123,12\wc4,13\wc5,145$

* $123,12\wc4,13\wc5,245$

* $123,12\wc4,12\wc5,12\wc6,456$

* $123,12\wc4,12\wc5,13\wc6,456$

* $123,12\wc4,13\wc5,23\wc6,456$

* $123,12\wc4,34\wc5$

* $123,12\wc4,13\wc5,45\wc6$

Here are two of the elements of $\cF_4$, although there are many more not listed.

* $1234,123\wc 5, 1245$

* $123\wc 4, 124\wc 5$

§.§ Results

We will show how the enumeration of $k$-SAT functions is determined by the Turán density problem $\pi(\cF_k, \log_2 3)$.
Note that for every $k$ and $\theta$ we always have

\[
\pi(\cF_k, \theta) \ge 1
\]

since the complete undirected $k$-PDG is $\cF_k$-free. (This is related to the fact that every monotone formula is minimal.)
Also, note the trivial inequality $\pi(\cF_k, \theta) \le \pi(\cF_k,\theta')$ if $\theta < \theta'$.

Fix $k \ge 2$.
The number of $k$-SAT functions on $n$ variables is

\[ 2^{(\pi(\cF_k, \log_2 3)+o(1))\binom{n}{k}}.
\]

In particular, for each $k \ge 2$, if $\pi(\cF_k,\log_23) = 1$ (conjectured to be true, and we can prove it for $k \le 4$), then the number of $k$-SAT functions is $2^{(1+o(1))\binom{n}{k}}$, which corresponds to a weaker version of <ref>. To get the full <ref>, we just need a tiny bit more on the Turán density problem.

Fix $k \ge 2$. If $\pi(\cF_k, \theta) = 1$ for some $\theta > \log_2 3$, then the number of $k$-SAT functions on $n$ variables is $(1+o(1))2^{n+\binom{n}{k}}$ (i.e., <ref> is true for this $k$).

Thus, to prove <ref>, we simply need to show the following.

For every $k \ge 2$, there is some constant $\theta > \log_2 3$ such that $\pi(\cF_k, \theta) = 1$.

We prove this conjecture for $k = 2, 3,4$, thereby yielding the following result.

For $k=2,3,4$, $\pi(\cF_k, \theta) = 1$ for some $\theta > \log_2 3$.
Consequently, the number of $k$-SAT functions on $n$ variables is $(1+o(1)) 2^{n+\binom{n}{k}}$.

If one could prove $\pi(\cF_k, \log_2 3) = 1$ then almost certainly the same proof verbatim would also yield $\pi(\cF_k, \theta) =1$ for some $\theta > \log_23$.
Indeed, the number $\log_2 3$ plays no special role for the Turán density problem and is only meaningful because of its applications for $k$-SAT enumeration.
So our results show that the $k$-SAT enumeration problem is essentially equivalent to determining $\pi(\cF_k, \log_23)$.

For any fixed $k$, <ref>, if true, is verifiable via a finite computation, namely by checking over all $n_k$-vertex $\cF_k$-free $k$-PDGs for some sufficiently large but finite $n_k$ (depending on $\theta$).
In [18], an extremal problem of similar nature for $k=3$ was checked “by hand” over $5$-vertex graphs.

We do not take the brute-force computational approach for Theorem <ref>.
Instead, we solve the $k=4$ problem using extremal graph theoretic arguments, with the help of a recent result of Füredi and Maleki [13].
We also give a much simpler argument for $k=3$, which does not involve any case checking.

In Appendix <ref>, we include a description of a C++ implementation of an algorithm that does a brute force check to find that for all $7$-vertex $4$-PDGs, $\pi(\vec T_k, 7/4) = 1$. This, in concert with Lemma <ref>, verifies Conjecture <ref> for $k=5$.

For larger values of $k$, previously <cit.> showed that the number of $k$-SAT functions on $n$ variables is at most $2^{\sqrt{(k+1)\pi}\binom{n}{k}}$ for all $n \ge 2k$.
We obtain the following improved bound, shy of proving of <ref>.

For all fixed $k \ge 5$ we have

\[
\pi(\cF_k, \log_23) \le \frac{\log_23}{2.727/k + 1}.
\]

Consequently, the number of $k$-SAT functions on $n$ variables is

\[
2^{(\pi(\cF_k, \log_23)+o(1))\binom{n}{k}} \le 2^{\paren{\frac{\log_23}{2.727/k + 1} + o(1)}\binom{n}{k}}.
\]

§.§ Outline

The rest of the paper can be divided into three parts.

Part I. A Turán density problem.

In <ref>, we study the Turán density problem and prove <ref> for $k=2,3,4$. The readers who are interested in working on <ref> only need to solve the remaining Turán density problem and thus do not need to read beyond this section.

Part II. Exponential asymptotics.

The goal of this part is to prove <ref>.
In <ref>, we recall some tools for hypergraphs, including the hypergraph container theorem.
In <ref>, we prove an upper bound on the number of $k$-SAT functions.
In <ref>, we prove a matching lower bound.

Part III. A stability argument.

In the last part of this article, we prove <ref>.
In <ref>, by a more careful analysis of the containers, we reduce the problem to showing there are a negligibly many non-unate but close-to-unate minimal formulae.
This final claim is then established in <ref> by extending the arguments in <cit.>.

§ A TURÁN DENSITY PROBLEM

The general hypergraph Turán problem seeks to answer the following extremal question: how many edges can an $n$-vertex $k$-uniform hypergraph have without containing a copy of forbidden $k$-uniform hypergraph (“$k$-graph”) $F$?
Many methods for tackling such problems are described in [22].
We consider a variant of the classical hypergraph Turán problem and work with $k$-PDGs as defined in the introduction.
The main objective here is to show <ref>, that for each $k\ge 2$, $\pi(\cF_k,\theta) = 1$ for some $\theta > \log_23$; we prove this conjecture for $k=2,3,4$ here (and also $k = 5$ in the appanedix), and leave all larger values of $k$ as an open problem.
Towards the conjecture, it suffices to prove
$\pi(\vec T_k,\theta) = 1$ for some $\theta > \log_23$
where $\vec T_k \in \cF_k$ is the special $k$-PDG defined in <ref> (since $\cF_k$-free implies $\vec T_k$-free).

§.§ Results

We prove the following recursive bound relating the Turán problem associated to $k$-SAT with that of $(k-1)$-SAT.

For $k \ge 3$, we have that

\[
\pi\paren{\vec T_k, \frac{(k-1)\theta + 1}{k}} \le \pi( \vec T_{k-1}, \theta).
\]

The same proof also shows the inequality

\[
\pi\paren{\cF_k, \frac{(k-1)\theta + 1}{k}} \le \pi(\cF_{k-1}, \theta).
\]

Recall that since the complete undirected $k$-PDG on $n$ vertices is $\vec T_k$-free, $\pi(\vec T_k, \theta) \ge 1$ for all $\theta > 0$.
The following result solves the Turán problem for enumerating $2$-SAT and $3$-SAT functions ($5/3 > \log_23=1.58496\dots$).
We will see its short proof momentarily.
The second claim follows from the first by <ref>.

$\pi(\vec T_2, 2) = 1$.  Therefore, $\pi(\vec T_3, 5/3) = 1$.

The result for $4$-SAT follows from the following improved bound on $\pi(\vec T_3, \theta)$.
The second claim again follows from the first by <ref>.

$\pi(\vec T_3, \phi) = 1$ with $\phi = 1.909 > (4\log_23-1)/3$. Consequently, $\pi(\vec T_4, \theta) = 1$ for $\theta = (3\phi+1)/4 > \log_23$.

To prove <ref> for $k=5$,
by applying <ref> twice,
it suffices to show $\pi(\vec T_3, \phi) = 1$ for some $\phi > 1.975 >(5\log_23-2)/3$.

<ref> and <ref> together lead to <ref>. To obtain an upper bound on $\pi(\vec T_k, \phi)$ for larger $k$,
iterating <ref> gives

\[
\pi\paren{\vec T_k, \frac{\ell}{k}(\phi - 1) + 1} \le \pi(\vec T_\ell, \phi)
\qquad \text{for } k > \ell \ge 2.
\]

Using $\ell = 3$ and $\phi = 1.909$, we get
$\pi(\vec T_k, 3(\phi-1)/k + 1) = 1$ for all $k \ge 4$.
Since $3(\phi-1)/k + 1 < \log_23$ for all $k \ge 5$, we have

\[
\pi(\vec T_k, \log_23) \le \frac{\log_23}{3(\phi - 1)/k + 1}\cdot  \pi\paren{\vec T_k, \frac{3}{k}(\phi - 1){k} + 1}
\le \frac{\log_23}{2.727/k + 1}
\qquad \text{for all } k \ge 5.
\]

This gives <ref>.
Our work leads to the following natural Turán problem for $k$-PDGs.

For each $k \ge 2$, what is the largest $\theta$ such that $\pi(\cF_k, \theta) = 1$?

The following $k$-PDG is $\cF_k$-free:
partitioning the $n$ vertices as $A \cup B$ with $\abs{A} = n/k$ and $\abs{B} = (k-1)n/k$, and add all directed edges with $k-1$ vertices in $B$ and directed towards a vertex in $A$.
This $k$-PDG has $\abs{A}\binom{\abs{B}}{k-1} = (n/k) \binom{(1-1/k)n}{k-1} = (1+o(1))(1-1/k)^{k-1}\binom{n}{k}$ edges. So $\pi(\cF_k, \theta) > 1$ whenever $\theta >  (1-1/k)^{-k+1}$.
We conjecture that this construction is optimal in the following sense.

$\pi(\vec T_k, (1-1/k)^{-k+1}) = 1$ for every $k \ge 2$.

<ref> confirms this conjecture for $k=2$.
The conjectured optimal construction is reminiscent of the solution to the hypergraph Turán problem corresponding to 3-graphs with independent  neighborhoods by Füredi, Pikhurko, and Simonovits [14].
Our techniques are partly inspired by their work.

The following conjecture is a restatement of <ref>, which would imply <ref> and hence <ref>.
In this section, we prove it for $k \le 4$, and in the appendix we prove it for $k \le 5$.

For every $k \ge 2$, $\pi(\vec T_k, \theta) = 1$ for some $\theta > \log_23$.

§.§ An averaging argument

We first prove <ref> via an averaging argument.

Given a $k$-PDG $\vec{H} = (V, E)$ and a vertex $v \in V$, the link of $v$, denoted $\vec{H}_v$, is the $(k-1)$-PDG with vertex set $V \setminus \{v\}$ and with edges obtained by taking all edges of $\vec H$ containing $v$ and then deleting the vertex $v$ from each edge. We preserve all the direction data, except that every edge directed towards $v$ in $\vec H$ becomes an undirected edge in $\vec H_v$.

If $\vec{H}$ is $\vec T_k$-free, then $\vec{H}_v$ is $\vec T_{k-1}$-free for all $v \in V(\vec{H})$.

If, for some vertex $v$, $\vec H_v$ contains $\vec T_{k-1}$ as a subgraph, then adding $v$ to all the edges shows that $\vec H$ contains $\vec T_k$ as a subgraph.

In the proofs below, we drop dependencies on $\vec H$ from notation when there is no confusion:

\[
\alpha = \alpha(\vec H), \quad
\alpha_v = \alpha(\vec H_v), \quad
\beta = \beta(\vec H), \quad
\beta_v = \beta(\vec H_v).
\]

Let $\vec H$ be a $\vec T_k$-free $k$-PDG.
By linearity of expectation over a uniform random vertex $v \in V$, $\EE_v \alpha_v = \alpha + \beta/k$ and
$\EE_v \beta_v = (k-1)\beta/k$.
For every $v \in V$, $\vec{H}_v$ is $\vec T_{k-1}$-free, so $\alpha_v + \theta\cdot \beta_v \le \pi(\vec T_{k-1}, \theta)+o(1)$. Thus, we have that

\[
\alpha + \frac{\theta(k-1) + 1}{k}\cdot \beta
\le
\EE_v[\alpha_v + \theta\cdot \beta_v]
\le \pi(\vec T_{k-1}, \theta)+o(1).
\]

This implies $\pi\left(\vec T_k, \frac{(k-1)\theta + 1}{k}\right) \le \pi(\vec T_{k-1}, \theta)$.

§.§ Turán density for 2-PDGs

We leverage the following lemma of Füredi to show <ref>, that partially directed graphs $\vec{H}$ satisfy $\pi(\vec T_2, 2) = 1$.

Given a graph $G = (V, E)$, let $G^2$ be the graph on vertex set $V$ with $xy \in E(G^2)$ if and only if there is some $z \in V$ with $xz, yz \in E$. Then, for any graph $G$,

$$e(G^2) \ge e(G) - \lfloor n/2 \rfloor.$$

In a graph $G$, we say that edge $xy \in E(G)$ is a triangular edge if there exists some $z \in V(G)$ so that $xz,yz \in E(G)$.
We then have the following corollary, showing that $\pi(\vec T_2, 2) = 1$, which completes the proof of <ref>.

If a 2-PDG $\vec{H}$ does not contain $\vec T_2$ as a subgraph, then $\alpha + 2\beta \le 1 + o(1)$.

Let $G$ be the underlying simple graph of $\vec{H}$ (the graph obtained from $\vec H$ by replacing directed edges with simple edges).
Then $e(G) = (\alpha + \beta){n \choose 2}$.
Only non-triangular edges in $G$ can arise as directed edges in $\vec{H}$. We further note that all triangular edges in $G$ are in $G^2$. Thus by <ref>,

$${n\choose 2} \ge e(G^2) + \beta{n \choose 2} \ge e(G) + \beta{n \choose 2} - O(n)
= (\alpha + 2\beta){n \choose 2} - O(n),$$

which implies that $\alpha + 2 \beta \le 1 + o(1)$.

§.§ An improvement for 3-PDGs

Here we prove <ref> that $\pi(\vec T_3, 1.909) = 1$.
We begin with a more careful decomposition of the links, followed by  an averaging-inductive argument.

For a $3$-PDG $\vec H = (V,E)$ and a vertex $v\in V$, we define four associated link (di)graphs. Let $A_v$ be a graph with edges arising from undirected edges in $\vec H$ containing $v$, i.e.,

\[
A_v = \left(V \backslash \{v\},\{w_1w_2:vw_1w_2\in E\}\right).
\]

Let $a_v := e(A_v)/{n-1\choose 2}$.
Let $B_v$ be a graph arising from edges in $\vec H$ containing but not directed towards $v$,  i.e.,

\[
B_v = \left(V\backslash \{v\}, \{w_1w_2:vw_1\wc w_2\in E\}\right).
\]

Let $b_v:= e(B_v)/{n-1\choose 2}$.
Let $C_v$ be a graph arising from directed edges in $\vec H$ pointed at $v$, i.e.,

\[
C_v=\left(V\backslash \{v\},\{w_1w_2:\wc v w_1w_2\in E\}\right).
\]

Let $c_v:= e(C_v)/{n-1\choose 2}$.
So $B_v$ is comprised of the directed edges of the link $\vec H_v$, whereas $A_v \cup C_v$ is comprised of the subgraph consisting of undirected edges of $\vec H_v$.

Finally, we write $H_v$ for the undirected graph formed by forgetting the directions in $\vec H_v$, i.e., the union of $A_v$, $B_v$, and $C_v$.

Let $\phi = 1.909$.
For every $\epsilon > 0$, there is some $n_0(\epsilon)$ such that for every $\vec T_3$-free $3$-PDG $\vec H$ on $n \ge n_0(\epsilon)$ vertices, every vertex $v$ satisfies

\[
a_v+\frac{3\phi-1}{2}\cdot b_v+c_v\leq 1 + \epsilon \qquad \text{or} \qquad
a_v+\phi \cdot (b_v + c_v) \le 1 + \epsilon.
\]

It suffices to show that, for every fixed $\epsilon > 0$, there is some $C = C(\epsilon)$ so that every $n$-vertex $\vec T_3$-free $3$-PDG $\vec H$ satisfies

\[
(\alpha + \phi\cdot \beta)\binom{n}{k}
= e_u + \phi \cdot e_d \le (1+\epsilon)\binom{n}{k} + C
\]

By choosing a large constant $C$, we may assume that the inequality holds for all $n < n_0(\epsilon)$.
So assume $n \ge n_0(\epsilon)$.
By <ref>, every vertex $v$ of $H$ satisfies

\[
a_v+\frac{3\phi-1}{2}\cdot b_v+c_v\leq 1 + \epsilon \qquad \text{or} \qquad
a_v+\phi \cdot (b_v + c_v) \le 1 + \epsilon.
\]

By linearity of expectation, we have

\[
\EE_v a_v = \alpha, \quad
\EE_v b_v = \frac{2\beta}3 , \quad \text{and}\quad
\EE_v c_v = \frac{\beta}3.
\]

Thus, if the first inequality in the statement is true for all $v$, then averaging over all $v$ yields $\alpha + \phi \cdot \beta \le 1+\epsilon$, as desired.

Now suppose that there is some $v$ with $a_v + \phi \cdot (b_v + c_v)\le 1+\epsilon$.
The $(n-1)$-vertex $3$-PDG $\vec H - v$ is also $\vec T_3$-free, so by the induction hypothesis,

\[
e_u(\vec H-v) + \phi \cdot e_d(\vec H-v) \le (1+\epsilon)\binom{n-1}{k} + C.
\]

By separately considering edges in $\vec H$ containing $v$ and not containing $v$, we obtain

\[
e_u(\vec H) = a_v(\vec H) \binom{n}{k-1} + e_u(\vec H-v)
\]

\[
e_d(\vec H) = (b_v(\vec H) + c_v(\vec H)) \binom{n}{k-1} + e_d(\vec H-v).
\]

\begin{align*}
e_u(\vec H) + \phi \cdot  e_d(\vec H)
&\le (a_v(\vec H)+\phi \cdot (b_v(\vec H) + c_v(\vec H)))\binom{n}{k-1} + (1+\epsilon)\binom{n-1}{k} + C
\\ &\le (1+\epsilon)\binom{n}{k-1} + (1+\epsilon)\binom{n-1}{k} + C
\\
& \le (1+\epsilon)\binom{n}{k} + C.
\end{align*}

This completes the induction.

Thus, it remains to show <ref>.

Since $\vec T_3=\{vxy, vx\wc z, vyz\}$ is forbidden, we see that every edge of $B_v$ is non-triangular in the graph $H_v$.
This leads to the following natural question. What is the maximum possible density of non-triangular edges in a graph of given edge density (over 1/2)?
Fortunately, this problem was recently solved by Füredi and Maleki [13].
An optimal construction comes from partitioning the vertex set into $A\cup B\cup C$ and adding all edges within $A$ as well as edges between $A\cup C$ and $B$.
In this construction, the non-triangular edges are those between $B$ and $C$.
One should optimize over possible sizes of the partition $A \cup B \cup C$ to maximize the number of non-triangular edges while maintaining the required total number of edges (that this number is optimal is proved asymptotically in [13] and exactly in [15] for sufficiently large graphs).
The precise statement that we will use is given below, where the the function $f(\rho)$ below is best possible due to the construction just described.

Fix $0 \le \rho \le 1$. In an $n$-vertex graph with at least $\rho \binom{n}{2}$ edges, the number of non-triangular edges is at most

\[
(f(\rho) + o(1)) \binom{n}{2},
\]

\begin{equation} \label{eq:t-delta}
f(\rho) = \max \set{ 2yz : x+y+z=1, x^2 + 2xy + 2yz \ge \rho, \ x,y,z \in \RR_{\ge 0}}.
\end{equation}

In contrast, the easier <ref> amounts to the inequality $f(\rho) \le 1 - \rho$, whereas $f(\rho)$ is strictly convex for $1/2 \le \rho \le 1$ with $f(1/2) = 1/2$ and $f(1) = 0$.
Here the strict convexity of $f$ is crucial for our proof.

Suppose that for some vertex $v$ of $\vec H$, one has both

\[
a_v+\frac{3\phi-1}{2}\cdot b_v+c_v > 1+\epsilon  \qquad \text{and} \qquad
a_v+\phi \cdot (b_v + c_v) > 1+\epsilon.
\]

Since every edge of $B_v$ is non-triangular in $H_v$, by <ref>,

\[
b_v \le f(a_v + b_v + c_v) + o(1).
\]

It follows, provided $n$ is sufficiently large, there exist real numbers $x,y,z,a,b,c$ satisfying the following system (to get to this system, we set $a=a_v$, $b= \min\{b_v,f(a_v+b_v+c_v)\}$, and $c=c_v$, so that $b > b_v - o(1)$, which implies the first two inequalities as $1+\epsilon-o(1)$ is strictly larger than $1$ if $n$ is sufficiently large):

\begin{align*}
a + \frac{3\phi-1}{2}\cdot b +c &> 1, \\
a + \phi \cdot (b + c) &> 1, \\
x + y + z &= 1, \\
x^2 + 2xy + 2yz &\ge a+b+c, \\
2yz & \ge b, \\
a,b,c,x,y,z &\ge 0.
\end{align*}

The following Mathematica code outputs to  when executed (under a second on a modern computer).
It proves that the above system has no real solutions for $\phi = 1.909$, thereby yielding the desired contradiction.
This computer verification is rigorous and uses Collins' cylindrical algebraic decomposition [9] (a form of quantifier elimination). See [21] for a tutorial.

§ HYPERGRAPH TOOLS

We recall several standard tools on hypergraphs that will prove useful in our analysis of minimal $k$-SAT formulae and $k$-PDGs.

§.§ Densities of blowups

Given a $k$-graph $H$, we write $H[b]$ for the $b$-blowup of $H$, defined to be the $k$-graph obtained by replacing every $v \in V(H)$ with $b$ duplicates, where $k$ vertices in $V(H[b])$ form an edge if and only if the vertices they originate from form an edge in $H$.

By a standard Cauchy–Schwarz argument, we know that if some $n$-vertex $k$-graph contains $\delta n^{\abs{V(H)}}$ homomorphic copies of $H$, then it contains at least $\delta n^{2\abs{V(H)}}$ homomorphic copies of $H[2]$.
For sufficiently large $n$, all but $O_H(n^{2\abs{V(H)}-1})$ such homomorphic copies of $H[2]$ are actual subgraphs. So we have the following (here “copies” refers to isomorphic copies as subgraphs).

For every $\epsilon > 0$ and $k$-graph $H$, there is some $\delta > 0$ and $n_0$ such that for all $n > n_0$, if an $n$-vertex $k$-graph has at least $\epsilon n^{\abs{V(H)}}$ copies of $H$ then it has at least $\delta n^{2\abs{V(H)}}$ copies of $H[2]$.

Given a $k$-SAT formula $G$, its $b$-blowup, denoted $G[b]$, is obtained from $G$ by replacing each variable by $b$ identical duplicates. For example, for the $3$-SAT formula $G = \{x_1x_2x_3,x_1\ol x_3x_4\}$, we have

\begin{multline*}
G[2]=\left\{x_1x_2x_3, x_1x_2x_3',x_1x_2'x_3,x_1x_2'x_3',
x_1'x_2x_3, x_1'x_2x_3',x_1'x_2'x_3,x_1'x_2'x_3',\right. \\
\left.x_1\ol {x_3}x_4,x_1\ol {x_3}x_4', x_1\ol {x_3'}x_4,x_1\ol {x_3'}x_4',
x_1'\ol {x_3}x_4,x_1'\ol {x_3}x_4', x_1'\ol {x_3'}x_4,x_1'\ol {x_3'}x_4'\right\}
\end{multline*}

We have a similar conclusion for blowups of formulae.

For every $\epsilon > 0$ and $k$-SAT formula $G$, there is some $\delta > 0$ and $n_0$ such that for all $n > n_0$, if a $k$-SAT formula on $n$ variables has at least $\epsilon n^{v(G)}$ copies of $G$, then it has at least $\delta n^{2v(G)}$ copies of $G[2]$.

§.§ Kruskal–Katona theorem

We need the following special case of the Kruskal–Katona theorem [23, 20].
Here a simplex in a $k$-graph is a clique on $k+1$ vertices.

A $k$-uniform hypergraph on $n$-vertices with at most $\beta n^k/k!$ edges contains at most $\beta^{\frac{k+1}{k}} n^{k+1}/(k+1)!$ simplices.

Here is a quick proof of this statement using Shearer's entropy inequality [8] (see [19]).

Let $(X_1, \dots, X_{k+1})$ be the vertices of a uniformly chosen simplex in the $k$-graph, with the $k+1$ vertices permutated uniformly at random.
By Shearer's inequality, letting $\vec X_{-i}$ denote $(X_1, \dots, X_{k+1})$ with the $i$-th coordinate removed, we have

\begin{align*}
k \log((k+1)!\text{\#simplices})
&= k H(X_1, \dots, X_{k+1})
\\
&\le H(\vec X_{-1}) + \cdots +  H(\vec X_{-(k+1)})
\\
&= (k+1) H(X_1, \dots, X_{k})
\le (k+1) \log (k!\text{\#edges}).
\end{align*}

Since $k!\text{\#edges} \le \beta n^k$, we have $(k+1)!\text{\#simplices} \le \beta^{\frac{k+1}{k}}n^{k+1}$.

§.§ Hypergraph containers

For any formula $B$, we let $v(B)$ denote the number of variables that appear in some clause in $B$. For a finite set $\cB$ of $k$-SAT formulae, we let

\[
\]

We use the hypergraph container theorem, proved independently by
Balogh, Morris, and Samotij [3]
Saxton and Thomason [26]
to show the following.

Let $\cB$ be a finite set of simple $k$-SAT formulae.
For every $\delta > 0$, there exists $C = C(\cB, \delta)$ such that for every $n$, there exists a collection $\cG=\cG(\cB,\delta)$ of formulae on variable set $X = \{x_1, \dots, x_n\}$ such that:

(a) Every $\cB$-free formula with variables in $X$ is a subformula of some $G \in \cG$, and

(b) For every $G \in \cG$ and $B \in \cB$, $G$ has at most $\delta n^{v(B)}$ copies of $B$, and

(c) $\abs{\cG} \le n^{Cn^{k-1/(m(\cB)-1)}}$.

In the remainder of this section, we deduce the above claim from the more general hypergraph container theorem. To state the general result, we introduce some notation for an  $\ell$-uniform hypergraph $\cH$. Let $\mathcal I(\cH)$ denote the collection of independent vertex sets in $\cH$. For every $j\in\{1,\dots,\ell\}$, let $\Delta_j(\cH)$ denote the maximum $j$-codegree of vertices in $\cH$, i.e., the maximum number of edges containing a given $j$-vertex subset in $\cH$. Let $\cP(V)$ denote the family of all subsets of $V$, and let ${V\choose \leq s}$ denote the family of those subsets of $V$ having size at most $s$.

For an increasing family (i.e., closed under taking supersets)  of vertex sets $\cF\subset \cP(V(\cH))$, we say that $\cH$ is $(\cF,\epsilon)$-dense if $e(\cH[A])\geq\epsilon e(\cH)$ for every $A\in\cF$. A simple example of $\cF\subset \cP(V(\cH))$ for which $\cH$ is $(\cF,\epsilon)$-dense is the family

$$\cF_\epsilon=\{A\subset V(\cH):e(\cH[A])\geq\epsilon e(\cH)\}.$$

We apply the following version of the
hypergraph container theorem as stated in <cit.>,
A similar result was proved in [26].

For every $\ell\in\NN$ and $c,\epsilon>0$, there exists $C_0=C_0(\ell,c,\epsilon)>0$ such that the following holds. Let $\cH$ be an $\ell$-uniform hypergraph and $\cF\subset \cP(V(\cH))$ be an increasing family of sets such that $|A|\geq \epsilon v(\cH)$ for all $A\in\cF$. Suppose that $\cH$ is $(\cF,\epsilon)$-dense and there exists $p\in(0,1)$ such that, for every $j\in\{1,\dots,\ell\}$, we have

$$\Delta_j(\cH)\leq c\cdot p^{j-1}\cdot\frac{e(\cH)}{v(\cH)}.$$

Then there exists a family $\mathcal S\subset {V(\cH)\choose \leq C_0\cdot p\cdot v(\cH)}$ and functions $f:\mathcal S\rightarrow\ol{\cF}$, $g:\cI(\cH)\rightarrow\cS$ such that for every $I\in \mathcal I(\mcH)$, we have:

(i) $g(I)\subset I$;

(ii) $I\setminus g(I)\subset f(g(I))$.

To prove <ref> using <ref>, we
proceed in two steps. First, we enlarge $\cB$ to a set $\cB'$ of formulae, each with $m(\cB)$ clauses. This allows us to construct an $m(\cB)$-uniform hypergraph $\cH_k$ on the set of all clauses on $X=\{x_1,\dots,x_n\}$, and apply the container argument. We then verify the codegree bounds of <ref>, which relies on all the elements of $\cB$ being simple.

We use <ref> to show that for every $\cB$ and $\delta>0$, we can take family $\cG$ of at most $n^{Cn^{k-1/(m(\cB)-1)}}$ formulae on $X$, such that: (1) every $n$-vertex $\cB$-free formula on $X$ is a subformula of some $G\in\cG$; (2) for any $B\in\cB$, every $G\in\cG$ has at most $\delta n^{v(B)}$ copies of $B$.

Fix a finite set $\cB$ of simple $k$-SAT formulae. We set $m= m(\cB)$, $v= km$ and $\cB'$ to be the set of all isomorphism classes of formulae $B'$ having the following properties:

* $B'$ has exactly $m$ clauses;

* $B'$ has a variable set of size $v$; here we allow isolated variables (i.e., variables not used by any clause in $B'$);

* $B'$ is simple;

* there exists some $B \in \cB$ such that $B'$ has a copy of $B$.

Notice that $\cB'$ is uniquely determined by $\cB$.

Let $\mcH_k = (V, E(\mcH_k))$ be an $m$-uniform hypergraph, where $V$ is the set of all $k$-SAT clauses on $X=\{x_1,\dots,x_n\}$ (so $|V| = 2^k{n\choose k}$), and

$$E(\mcH_k)=\{G\subset V\mid G\text{ is isomorphic to some }B'\in \cB'\}.$$

Every $k\SAT$ formula $G$ on $X$ can be viewed as a vertex subset of $\mcH_k$. For any $B \in \cB$, if $G$ has more than $\delta n^{v(B)}$ copies of $B$, then there exists some $\eta_0=\eta_0(B,\delta)>0$ and $B'\in \cB'$ such that $G$ has more than $\eta_0 n^{v}$ copies of $B'$, with the property that $B'$ has a copy of $B$. Since $\cB$ is finite, we can take

This implies that there exists $\eta=\eta(\cB,\delta)>0$ such that if $G$ has more than $\delta n^{v(B)}$ copies of $B$ for any $B\in\cB$, then $|E(\mcH_k[G])|>\eta n^{v}$.

Since every formula $B'\in\cB'$ has variable set of size $v$, for a formula $G\subset V$, the number of formulae $G'\subset V$ such that (1) $G\subset G'$ and (2) there exists some $B'\in\cB'$ with $G'$ isomorphic to $B'$ is $O_\cB(n^{v - v(G)})$.
In particular, taking $G$ to be the empty formula, we have $e(\cH_k)= O_\cB(n^v)$.

We therefore have the following upper bounds on the maximum $j$-codegrees of vertices in $\cH_k$. When $j=1$, since every single-clause formula $G=\{C\}$ has $v(G)=k$, we have $\Delta_1(\cH_k)=O_\cB(n^{v-k})$.
For all $j\in\{2,\dots, m\}$, since $\cB'$ is a set of simple formulae, and any simple formula $G=\{C_1,\dots,C_j\}$ with $j$ clauses has $v(G)\geq k+1$, we have $\Delta_j(\cH_k)= O_\cB(n^{v-k-1})$.

Let $p=n^{-1/(m-1)}$. Using a trivial lower bound $e(\cH_k)\geq {n\choose v}$ (say) and the fact that $|V|= 2^k{n\choose k}$, we can choose some $c=c(\cB)>0$ such that

$$\Delta_1(\mcH_k)\leq c\cdot\frac{{n\choose v}}{2^k{n\choose k}}\leq c\cdot \frac{e(\cH_k)}{|V|}$$

$$\Delta_j(\cH_k)\leq c\cdot \frac{1}{n}\cdot\frac{{n\choose v}}{2^k{n\choose k}}\leq  c\cdot p^{j-1}\cdot\frac{e(\cH_k)}{|V|}$$

for all $j\in\{2,\dots,m\}$.

For any $\delta>0$, we set $\eta=\eta(\cB,\delta)>0$ as above, $\epsilon=\epsilon(\cB,\delta)>0$ sufficiently small, and

$$\cF=\{A\subset V(\cH):|A|\geq \epsilon \cdot v(\cH_k)\text{ and }e(\cH_k[A])\geq \epsilon \cdot e(\cH_k)\},$$

so that $\cF$ is an increasing family of sets such that $|A|\geq \epsilon v(\cH_k)$ for all $A\in\cF$, and $\cH_k$ is $(\cF,\epsilon)$-dense.

Applying <ref>, we know that there exists $C_0=C_0(m,c,\epsilon)=C_0(\cB,\delta)$, a family

$$\mathcal S\subset {V\choose \leq C_0\cdot n^{-1/(m-1)}\cdot |V|}$$

and functions $f:\mathcal S\rightarrow\ol{\cF}$, $g:\cI(\cH)\rightarrow\cS$ such that for every $I\in \mathcal I(\mcH)$, we have:

(i) $g(I)\subset I$;

(ii) $I\setminus g(I)\subset f(g(I))$.

Let $\cG=\cG(\cB,\delta)=\{S \cup f(S):S\in\cS\}$. We show that $\cG$ meets all the conditions decribed in <ref>.

(a) Every $\cB$-free formula with $n$ variables is a subformula of some $G \in \cG$.

Since every $\cB$-free formula is clearly $\cB'$-free, it is an independent set $I\in \cI(\cH_k)$. Since $I\setminus g(I)\subset f(g(I))$ and $g(I)\in\cS$, we have $I\subset (g(I)\cup f(g(I))) \in\cG$.

(b) For every $G \in \cG$ and $B \in \cB$, $G$ has at most $\delta n^{v(B)}$ copies of $B$.

Every $G \in \cG$ is of the form $G=S \cup f(S)$ for some $S\in\cS$. Since $|S|\leq  C_0\cdot n^{-1/(m-1)}\cdot |V|$, the number of edges incident to $S\setminus f(S)$ is at most

C_0\cdot n^{-1/(m-1)}\cdot |V|\cdot \Delta_1(\cH_k)
\leq C_0\cdot n^{-1/(m-1)}\cdot 2^k{n\choose k}\cdot  \Delta_1(\cH_k)

Meanwhile, since $f(S)\in\ol{\cF}$, we either have $e(\cH_k[f(S)])<\epsilon e(\cH_k)\leq \epsilon|\cB'|\cdot {n\choose v}\cdot (v!)$ or have $|f(S)|<\epsilon v(\cH)$, in which case $e(\cH_k[f(S)])<|\cB'|\cdot {\epsilon n\choose v}\cdot (v!)$.
Hence for every $G=S\cup f(S) \in \cG$, we have (recall that we have set $\epsilon=\epsilon(\cB,\delta)>0$ sufficiently small)

$$e(\cH_k[G])\leq \epsilon|\cB'|\cdot {n\choose v}\cdot (v!)+O_{\cB,\delta}\left(n^{v-1/(m-1)}\right)\leq \eta n^{v}.$$

Recall that if $G$ has more than $\delta n^{v(B)}$ copies of $B$ for any $B\in\cB$, then we will have $e(\mcH_k[G])>\eta n^{v}$. Hence for every $B \in \cB$, $G$ has at most $\delta n^{v(B)}$ copies of $B$.

(c) $\abs{\cG} \le n^{Cn^{k-1/(m-1)}}$ for some $C=C(\cB,\delta)$.

Since $|\cG|\leq |\cS|\leq \left|\binom{V}{\leq C_0\cdot n^{-1/(m-1)}\cdot |V|}\right|$ with $|V|=2^k{n\choose k}$, we have

\begin{align*}
|\cG|&\leq \sum_{s=1}^{C_0\cdot n^{-1/(m-1)}\cdot |V|}{|V|\choose s}\leq C_0\cdot n^{-1/(m-1)}\cdot |V|\cdot {|V|\choose C_0\cdot n^{-1/(m-1)}\cdot |V|}\\
&\leq n^{Cn^{k-1/(m-1)}}=n^{Cn^{k-1/(m-1)}}
\end{align*}

for some $C=C(C_0)=C(\cB,\delta)$.

§ WEAK UPPER BOUND ON THE NUMBER OF $K$-SAT FUNCTIONS USING CONTAINERS

In this section, we prove the upper bound in <ref>.

For every fixed $k \ge 2$, the number of minimal $k$-SAT formulae on $n$ variables is at most $2^{(\pi(\cF_k, \log_2 3) + o(1)) \binom{n}{k}}$.

To prove this theorem, we first observe that every minimal formula is nearly simple.
To  count simple minimal formulae, we apply the container method.
The container method requires us to characterize formulae with many instances of small non-minimal simple formulae, and these turn out to be related to the appearance of $\cF_k$ in an associated $k$-PDG.

§.§ Minimal formulae are nearly simple

The 2-blowup of a pair of clauses on the same set of $k$ variables is non-minimal.

For example, the lemma tells us that the 2-blowup of $\{xyz,xy\ol z\}$ is non-minimal.

Up to relabeling and/or negating some of the variables, we can write the pair of clauses as $v_1 v_2 \cdots v_k$ and $\overline{v_1} \cdots \ol {v_j}v_{j+1}\cdots v_k$ for some $1\leq j\leq k$.
Then its 2-blowup has clauses (among others)

$$v_1 v_2 \cdots v_k,v_1' v_2 v_3 \cdots v_k, v_1 v_2' v_3 \cdots v_k, \ldots, v_1 \cdots v_{j-1}v_j'v_{j+1}\cdots v_k, \overline{v_1'} \cdots \ol {v_j'}v_{j+1}\cdots v_k.$$

It is impossible to satisfy the first clause only, since it would involve setting $v_1 = \cdots = v_k = 1$ and $v'_1 = \cdots = v'_j = 0$, which would then satisfy the last clause.
So the 2-blowup is non-minimal.

In the above proof, if the initial pair of clauses differ by at least two negations, i.e., $j\ge 2$, then the selected clauses of the 2-blowup form a simple non-minimal subformula.
We will use this fact later in <ref>.

Every minimal $k$-SAT formula on $n$ variables can be made simple by deleting $o(n^k)$ clauses.

Let $G$ be a minimal $k$-SAT formula on $n$ variables.
By <ref>, $G$ does not contain any 2-blowup of a pair of clauses on the same $k$ variables.
It follows from <ref> that the number of $k$-subsets of variables that support at least two clauses in $G$ is $o(n^k)$. Removing all such clauses yields a simple subformula of $G$.

§.§ From $k$-SAT to $k$-PDGs

As hinted by <ref>, for the container argument, we focus our attention on the following special type of formulae.

A $k$-SAT formula is semisimple if for every $k$-subset $S$ of variables, one of the following is true:

(a) There is no clause on $S$, or

(b) There is exactly one clause on $S$, or

(c) There are exactly two clauses on $S$ and they differ by exactly one variable negation.

The 3-SAT formula $\{ x_1\overline{x_2}x_3, x_1\ol{x}_2\ol{x}_3,x_1x_2\overline{x_4}\}$ is semisimple, whereas the formula $\{ x_1\overline{x_2}x_3, x_1 x_2 \ol{x_3}\}$ is not semisimple.

We define a forgetful map from semisimple formulae to $k$-PDGs.

\[
\type\colon \{\text{semisimple $k$-SAT formula on $n$ variables} \} \to \{\text{$k$-PDGs on $n$ vertices}\}
\]

as follows.
Given a semisimple formula $G$, let  $\type(G)$ be the $k$-PDG with vertices being the variables of $G$, where we add an undirected edge to every $k$-subset of variables supporting exactly one clause in $G$, and add a directed edge to every $k$-subset of variables support exactly two clauses in $G$, and for the latter, we direct the edge towards the variable where the two clauses differ by negation.

The semisimple formula

\[
abc,ab\ol{c}, \ol{a}b \ol{d},bd\ol{e},\ol{b}d\ol{e}
\]

has type

\[
ab\wc{c}, abd, \wc{b}de.
\]

§.§ Forbidden subgraphs and non-minimal formulae

The following proposition explains why $\cF_k$ plays a central role.

Let $G$ be a $k$-SAT semisimple formula whose type lies in $\cF_k$.
Then $G[2]$ has a simple non-minimal subformula.

We consider a $3\SAT$ example.
An example of a semisimple formula with type $\vec{H}= (\{1,2,3,4\}, \{12\wc 3, 23\wc 4\})$ is the collection of $4$-clauses on $4$-variables $G =\{abc, ab\ol c, \ol b c d, \ol bc \ol d\} $.
The $2$-blowup of $G$ has the following simple non-minimal formula: $B = \{abc, ab'c, ab\ol{c'}, \ol{b'}cd,\ol{b'}c'\ol{d}\}$. We can observe that $B$ is non-minimal by noting that to only satisfy $abc$, we must assign $a,b,c \mapsto 1$ which forces us to assign $b' \mapsto 0, c' \mapsto 1$ to avoid satisfying the second or third clause in $B$. However then we must assign $d \mapsto 0$ to avoid satisfying the fourth clause in $B$ and this combination of assignments satisfies the fifth clause in $B$.

Suppose the initialization edge in $\type(G)$ is undirected. For clarity, we use two examples of $G$ and $\type(G)$ to illustrate this result that capture the fully generality of our argument.  We then summarize the general algorithm for identifying a simple non-minimal formula in the $2$-blowup of a general $G$.

We first look at the case where the final edge in $\type(G)$ does not introduce any new vertex. Let

\begin{align*}
G&=\{abcd,a\bar bce,a\bar bc\bar e, \bar ac\bar df,\bar ac\bar d\bar f, \bar a  de\bar f\}\\
\end{align*}

so that every label names the clause of the same order (i.e., $C_0=abcd$, …, $C_3=\bar a  de\bar f$). We have

Using the notation in <ref>, $\type(G)$ is a 4-PDG in $\cF_4$ with:

* $j=2$, $S=\{1,2,3,4\}$, $T=\{1,2,\dots,6\}$;

* Initialization: $e_0=1234$;

* Extension: $e_1=123\wc5$, $e_2=134\wc6$;

* Closure: $e_3=1456$.

We pick a simple non-minimal formula

$$G'=\{\widetilde C_0,\widetilde C_0^{(1)},\dots, \widetilde C_0^{(4)},\widetilde C_1,\widetilde C_2,\widetilde C_3\}\subset G[2]$$

\begin{align*}
\widetilde C_0,\widetilde C_0^{(1)},\dots, \widetilde C_0^{(4)}&\in C_0[2],\\
\widetilde C_1&\in C_1^{(1)}[2]\cup C_1^{(2)}[2],\\
\widetilde C_2&\in C_2^{(1)}[2]\cup C_2^{(2)}[2],\\
\widetilde C_3&\in C_3[2],
\end{align*}

using the following steps:

* Set $\widetilde C_0=abcd\in C_0[2]$.

* Set $\widetilde C_0^{(1)}=a'bcd, \widetilde C_0^{(2)}=ab'cd, \widetilde C_0^{(3)}=abc'd, \widetilde C_0^{(4)}=abcd'\in C_0[2]$.

* Set $\widetilde C_3=\ol{a'}de\ol{f'}\in C_3[2]$. We pick the variables $a',d,e,f'$ because the clause $C_4=\ol a d e\ol f\in G$ uses positive literals $d,e$ and negative literals $\ol a,\ol f$.

* Set $\widetilde C_1=a\ol{b'}c\ol e$. We pick the variables $a,b',c$ because $C_1^{(1)}, C_1^{(2)}\in G$ use positive literals $a,c$ and negative literal $\ol b$. We pick the variable $e$ because $\widetilde C_3$ uses the variable $e$, and then pick the literal $\ol e$ (instead of $e$) because $e$ appears as a positive literal in $\widetilde C_3$, and we want the literal here to be the opposite of it.

* Set $\widetilde C_2=\ol{a'}c\ol{d'}f'$. We pick the variables $a',c,d'$ because $C_2^{(1)}, C_2^{(2)}\in G$ use positive literal $c$ and negative literals $\ol a,\ol d$. We pick the variable $f'$ because $\widetilde C_3$ uses the variable $f'$, and then pick the literal $f'$ (instead of $\ol{f'}$) because $\ol{f'}$ appears as a negative literal in $\widetilde C_3$, and we want the literal here to be the opposite of it.

We show that it is impossible to uniquely satisfy $\widetilde C_0\in G'$. Suppose to the contrary that there exists a witness that maps $\widetilde C_0$ to 1 and all other clauses in $G'$ to 0. We clearly have $a,b,c,d\mapsto 1$. Since all of $C_0^{(1)},\dots,C_0^{(4)}$ are mapped to 0, we then have $a',b',c',d'\mapsto 0$. Now since $\widetilde C_1$ is mapped to 0, we have $e\mapsto 1$. Since $\widetilde C_2$ is mapped to 0, we have $f'\mapsto 0$. This forces $\widetilde C_{3}$ to get mapped to 1, a contradiction.

We now look at the case where the final edge in $\type(G)$ is pointed at some new vertex. Let

\begin{align*}
G&=\{abcd,\bar ab\bar ce, \bar ab\bar c\bar e, a c\bar df, ac\bar d\bar f, b\bar e\bar fg,b\bar e\bar f\bar g\}\\
\end{align*}

so that every label names the clause of the same order. We have

Using the notation in <ref>, $\type(G)$ is a 4-PDG in $\cF_4$ with:

* $j=2$, $S=\{1,2,3,4\}$, $T=\{1,2,\dots,6\}$;

* Initialization: $e_0=1234$;

* Extension: $e_1=123\wc5$, $e_2=134\wc6$;

* Closure: $e_3=256\wc7$.

We pick a simple non-minimal formula

$$G'=\{\widetilde C_0,\widetilde C_0^{(1)},\dots, \widetilde C_0^{(4)},\widetilde C_1,\widetilde C_1',\widetilde C_2,\widetilde C_3,\widetilde C_3'\}\subset G[2]$$

\begin{align*}
\widetilde C_0,\widetilde C_0^{(1)},\dots, \widetilde C_0^{(4)}&\in C_0[2],\\
\widetilde C_1,\widetilde C_1'&\in C_1^{(1)}[2]\cup C_1^{(2)}[2],\\
\widetilde C_2&\in C_2^{(1)}[2]\cup C_2^{(2)}[2],\\
\widetilde C_3,\widetilde C_3'&\in C_3^{(1)}[2]\cup C_3^{(2)}[2],
\end{align*}

using the following steps.

* Set $\widetilde C_0=abcd\in C_0[2]$.

* Set $\widetilde C_0^{(1)}=a'bcd, \widetilde C_0^{(2)}=ab'cd, \widetilde C_0^{(3)}=abc'd, \widetilde C_0^{(4)}=abcd'\in C_0[2]$.

* Set $\widetilde C_3=b\bar{e'}\bar{f'}g$ and $\widetilde C_3'=b\bar{e}\bar{f'}\bar g\in C_3[2]$. For $\widetilde C_3$, we pick the variables $b,e',f'$ because the clauses $C_3^{(1)},C_3^{(2)}\in G$ uses positive literal $b$ and negative literals $\ol e,\ol f$. We then pick the positive literal $g$ (it does not matter whether we use $g$ or $g'$ here). We obtain $\widetilde C_3'$ from $\widetilde C_3$ by replacing the variable $e'$ with $e$ and replacing the literal $g$ with $\ol g$.

* Set $\widetilde C_1=\ol{a'}b\ol{c'}e'$ and $\widetilde C_1'=\ol{a'}b\ol{c'}e$. We pick $\widetilde C_1$ exactly as how we would pick $\widetilde C_1$ in the previous case. We obtain $\widetilde C_1'$ from $\widetilde C_1$ by replacing the variable $e$ with $e'$.

* Set $\widetilde C_2=ac\ol{d'} f'$. We pick $\widetilde C_2$ exactly as how we would pick $\widetilde C_2$ in the previous case.

We show that it is impossible to uniquely satisfy $\widetilde C_0\in G'$. Suppose to the contrary that there exists a witness that maps $\widetilde C_0$ to 1 and all other clauses in $G'$ to 0. By the same reasoning as before, we have $a,b,c,d\mapsto 1$ and $a',b',c',d'\mapsto 0$. Now since $\widetilde C_1,\widetilde C_1'$ are mapped to 0, we have $e,e'\mapsto 0$. Since $\widetilde C_2$ is mapped to 0, we have $f'\mapsto 0$. This forces at least one of $\widetilde C_{3},\widetilde C_{3}'$ to get mapped to 1, a contradiction.

We can generalize this strategy to any such $G$. Let $C_0\in G$ be the clause corresponding to the initialization edge $e_0$. Consider a witness $\mathsf w\in\{0,1\}^n$ that maps the original clause in $C_0[2]$ to 1 and all other clauses in $G[2]$ to 1. It follows that for every variable $v\in S$, we must assign one of $v,v'$ to 0 and the other to 1. Then for each of $e_1,\dots,e_{j+1}$, we can  pick one or two clauses appropriately from the 2-blowup of clauses in $G$ corresponding to it, and show that it is impossible to map all of these clauses to 0. The strategy when the initialization edge in $\type(G)$ is directed is very similar, and we do not elaborate here.

If a semisimple formula $G$ has type $\vec{H}$ where $\vec{H}$ contains many copies of some $\vec{F} \in \cF_k$, then we'd like to show that $G$ contains many non-minimal, simple formulae. We make this intuition quantitative below.

§.§ Supersaturation

Now we show that, roughly speaking, if a formula has many clauses (with respect to some weighting), then it contains a small simple non-miminal subformula.

For a $k$-SAT formula $G$ on $n$ variables, define

\[
\alpha_i(G) {n \choose k} = \left| \left\{S \in {V \choose k} \mid  G \text{ has exactly } i \text{ clauses with variables } S \right\} \right|.
\]

Furthermore, define
$\alpha_{2,1}(G){n \choose k}$ to be the number of $S \in {V \choose k}$ such that
$G$ has exactly two clauses with variables $S$ and the pair differs on exactly on variable by negation.
Also set

\[
\alpha_{2,2}(G) = \alpha_2(G) - \alpha_{2,1}(G).
\]

Let $\epsilon > 0$ and $\theta>0$.
There exists $\delta = \delta(\epsilon, \theta) > 0$ such that for all sufficiently large $n$, if an $n$-variable $k$-SAT formula $G$ satisfies $\alpha_1(G)+\theta \alpha_{2,1}(G)\geq \pi(\cF_k,\theta)+\epsilon$,
then there is some simple non-minimal subformula $B$ on at most $4k$ vertices, such that $G$ contains at least $\delta n^{v(B)}$ copies of $B$ as subformulae.

Fix $\epsilon > 0$ and $\theta>0$. Consider an $n$-variable $k$-SAT formula $G$ such that $\alpha_1(G)+\theta \alpha_{2,1}(G)\geq \pi(\cF_k,\theta)+\epsilon$. Up to deleting all the clauses of $G$ not accounted for by $\alpha_1(G)$ and $\alpha_{2,1}(G)$, we can assume that $G$ is semisimple.

Let $\vec H = \type(G)$. Then $\vec H$ has $\alpha_1(G) \binom{n}{k}$ undirected edges and $\alpha_{2,1}(G)\binom{n}{k}$ directed edges.
It follows by the definition of Turán density $\pi(\cF_k,\theta)$ and a standard supersaturation argument that there is some $\vec F \in \cF_k$ such that $\vec H$ contains at least $\Omega(n^{v(\vec F)})$ copies of $\vec F$.
There are only finitely many isomorphism classes of semisimple formulae with type $\vec F$, so by pigeonhole, there is some $k$-SAT semisimple formula $G'$, with $\type(G')=\vec F$, such that $G$ contains at least $\Omega(n^{v(\vec F)})$ copies of $G'$ as subformulae.
Then, by <ref>, $G$ contains $\Omega(n^{2v(\vec F)})$ copies of $G'[2]$ as subformulae.
By <ref>, each copy of $G'[2]$ contains some simple non-minimal subformula.
Note that $G'[2]$ has at most $4k$ variables since every element of $\cF_k$ has at most $2k$ variables. The conclusion then follows immediately after another application of pigeonhole.

Let $\epsilon > 0$.
There exists $\delta = \delta(\epsilon)>0$ such that for all sufficiently large $n$, if an $n$-variable $k$-SAT formula has at least $\alpha_i(G) \ge \epsilon$ for some $i \ge 3$ or $\alpha_{2,2}(G) \ge \epsilon$, then there is some simple non-minimal subformula $B$ on at most $2k$ vertices such that $G$ contains at least $\delta n^{v(B)}$ copies of $B$ as subformulae.

Fix $\epsilon > 0$. Consider an $n$-variable $k$-SAT formula $G$ such that $\alpha_i(G) \ge \epsilon$ for some $i \ge 3$, or $\alpha_{2,2}(G) \ge \epsilon$. By pigeonhole, there is some $2 \le j \le k$ such that $G$ has at least $\Omega(\epsilon n^k)$ subformulae of the form $G' = \{v_1 v_2 \cdots v_k$ and $\overline{v_1} \cdots \ol {v_j}v_{j+1}\cdots v_k\}$.
By <ref>, $G$ contains $\Omega(n^{2k})$ copies of $G'[2]$ as subformulae. Since every copy of $G'[2]$ has a non-minimal simple formula by <ref>, the result follows.

§.§ Applying the container theorem

Recall the definition of the $\alpha_i$'s from the beginning of <ref>.

Define the weight of the formula of a $k$-SAT formula $G$ by

\[
\wt(G)=\alpha_1(G)+\log_23 \cdot \alpha_2(G)+\log_24 \cdot \alpha_3(G)+\dots+\log_2(2^k+1) \cdot \alpha_{2^k}(G).
\]

Given a $k$-SAT formula $G$ on $n$ variables, the number of simple $k$-SAT subformulae of $G$ is

\[
\prod_{j =1}^{2^k} (j+1)^{\alpha_j(G) {n \choose k}} = 2^{\wt(G) {n \choose k}}
\]

since there are $j+1$ ways to choose at most one clause from  $j$ clauses. This motivates our definition of weight.

We are now ready to prove <ref> that the number of minimal $k$-SAT formulae on $n$ variables is at most $2^{(\pi(\cF_k, \log_2 3) + o(1)) \binom{n}{k}}$.

Let $\cB$ be the set of all non-minimal simple formulae on at most $4k$ variables, one for each isomorphism class (so that $\cB$ is finite).
Fix any $\epsilon > 0$.
Pick $\delta > 0$ to be smaller than the minimum of the $\delta$'s chosen in <ref> (with $\theta = \log_2 3$) and <ref>.
Applying the container result, <ref>, we find a collection $\cG$ of $n$-variable formulae on $X=\{x_1,\dots,x_n\}$ such that

(a) Every $\cB$-free formula on $X$ is a subformula of some $G \in \cG$, so in particular, every simple minimal formula on $X$ is a subformula of some $G \in \cG$; and

(b) For every $G \in \cG$ and $B \in \cB$, $G$ contains at most $\delta n^{v(B)}$ copies of $B$, which implies, by <ref>, that $\alpha_1(G) + \log_2 3 \cdot \alpha_{2,1}(G)< \pi(\cF_k, \log_2 3) + \epsilon$, $\alpha_{2,2}(G) < \epsilon$ and $\alpha_i(G)< \epsilon$ for all $i \ge 3$; and

(c) $\abs{\cG} \le 2^{o(n^k)}$.

The number of simple minimal $k$-SAT subformula of each $G \in \cG$ is thus at most

\[
2^{\wt (G) \binom{n}{k}} \le 2^{(\pi(\cF_k, \log_2 3) + O(\epsilon))\binom{n}{k}}.
\]

By taking a union bound over all $G \in \cG$, of which there are at most $2^{o(n^k)}$, and noting that $\epsilon$ can be taken to be arbitrarily small, we see that the number of simple minimal $k$-SAT formula on $n$ variables is $2^{(\pi(\cF_k, \log_2 3) + o(1))\binom{n}{k}}$.

Finally, by <ref>,  we can obtain any minimal $k$-SAT formulae by adding $o(n^k)$ clauses to a simple minimal formula. This adds a neglible factor $\binom{2^k{n\choose k}}{\le o(n^k)} = 2^{o(n^k)}$. So the total number of minimal $k$-SAT formulae on $n$ variables is $2^{(\pi(\cF_k, \log_2 3) + o(1))\binom{n}{k}}$.

§ A LOWER BOUND ON THE NUMBER OF $K$-SAT FUNCTIONS

In this section, we prove the lower bound in <ref>, namely that for every fixed $k \ge 2$, there are at least $2^{(\pi(\cF_k, \log_2 3)+o(1))\binom{n}{k}}$ distinct $k$-SAT functions on $n$ variables.

Given an $k$-PDG $\vec H$, let the positive instance of $\vec H$ be the semisimple $k\SAT$ formula $G \in \type^{-1}(\vec H)$ obtained as follows:

* $G$ has the clause $v_1\cdots v_k$ if and only if there exists an edge (directed or undirected) on $\{v_1,\dots, v_k\}$ in $\vec H$;

* $G$ has the clause $v_1\cdots v_{k-1}\ol v_k$ if and only if $v_1\cdots  v_{k-1}\wc v_k\in E(\vec H)$.

We observe that the positive instance $G \in \type^{-1}(\vec H)$ on $n$ vertices has $2^{\alpha(\vec H) {n \choose k}} 3^{\beta(\vec H) {n \choose k}}=2^{(\alpha(\vec H)+\log_23\cdot \beta(\vec H)) {n \choose k}}$ simple subformulae, as there are $\alpha(\vec H){n\choose k}$ $k$-subsets of variables in $G$ that support exactly one clause, and $\beta(\vec H){n\choose k}$ $k$-subsets of variables in $G$ that support exactly two clauses.

Fix $\cF_k$-free $k$-PDG $\vec H$ on $n$ vertices with positive instance $G \in \type^{-1}(\vec H)$. Let $\cS$ denote the collection of simple subformulae of $G$. Then all $G' \in \cS$ are minimal.

Fix any $G' \in \cS$. To prove that $G'$ is minimal, we show that for every clause $C_0\in G'$, we can find a witness $\mathsf w\in\{0,1\}^n$ such that $\mathsf w$ maps $C_0$ to 1 and all other clauses in $G'$ to $0$.

Fix any clause $C_0\in G'$. First suppose that $C_0$ is of the form $v_1\cdots v_k$. Let

$$X_1=\{v_1,\dots,v_k\}\cup\{w:v_{i_1}\cdots v_{i_{k-1}}\ol w\in G\text{ for some }i_1,\dots,i_{k-1}\in[k]\}.$$

Choose $\mathsf w\in\{0,1\}^n$ such that $\mathsf w(v)=1$ if $v\in X_1$ and $\mathsf w(v)=0$ otherwise. We show that $\mathsf w$ is a witness to $C_0$. For every $C\in G'\setminus\{C_0\}$, there are three cases:

* $C$ uses at least two variables outside $X_1$. In this case, since $C$ has at most one negative literal, we know that $\mathsf w$ maps $C$ to 0.

* $C$ uses exactly one variable $u_0$ outside $X_1$. In this case, we show that the corresponding literal in $C$ cannot be $\ol u_0$, so $\mathsf w$ still maps $C$ to 0. By contradiction, suppose that $C$ contains $\ol u_0$, so $C$ is of the form $v_{i_1}\cdots v_{i_j}w_{i_{j+1}}\cdots w_{i_{k-1}}\ol u_0$ for some $i_1,\dots,i_{j}\in[k]$ and some $w_{i_{j+1}},\dots,w_{i_{k-1}}\in X_1\setminus \{v_1,\dots,v_k\}$. However, if $j=k-1$, then $u_0\in X_1$, a contradiction; if $j<k-1$, then the underlying $k$-PDG $\vec H$ is not $\cF_k$-free, as it has a subgraph of the form

$$\qquad\{v_1\cdots v_k, v_{i^{(j+1)}_1}\cdots v_{i^{(j+1)}_{k-1}}\wc w_{i_{j+1}},\dots, v_{i^{(k-1)}_1}\cdots v_{i^{(k-1)}_{k-1}}\wc w_{i_{k-1}}, v_{i_1}\cdots v_{i_j}w_{i_{j+1}}\cdots w_{i_{k-1}}\wc u_0\},$$

another contradiction.

* $C$ only uses variables in $X_1$. In this case, to show that $\mathsf w$ maps $C$ to 0, it suffices to show that $C$ cannot be monotone. By contradiction, suppose that $C$ is of the form $v_{i_1}\dots v_{i_j}w_{i_{j+1}}\dots w_{i_{k}}$ for some $i_1,\dots,i_{j}\in[k]$ and some $w_{i_{j+1}},\dots,w_{i_{k}}\in X_1\setminus \{v_1,\dots,v_k\}$. However, if $j=k$, then $C=C_0$, a contradiction;  if $j<k$, then the underlying $k$-PDG $\vec H$ is not $\cF_k$-free, as it has a subgraph of the form

$$\{v_1\cdots v_k, v_{i^{(j+1)}_1}\cdots v_{i^{(j+1)}_{k-1}}\wc w_{i_{j+1}},\dots, v_{i^{(k)}_1}\cdots v_{i^{(k)}_{k-1}}\wc w_{i_{k}}, v_{i_1}\dots v_{i_j}w_{i_{j+1}}\dots w_{i_{k}}\},$$

another contradiction.

We now suppose that $C_0$ is of the form $v_1\dots v_{k-1}\ol v_k$. Let

$$X_1=\{v_1,\dots,v_{k-1}\}\cup\{w:v_1\cdots v_{k-1}\ol w\in G'\}.$$

Choose $\mathsf w\in\{0,1\}^n$ such that $\mathsf w(v)=1$ if $v\in X_1$ and $\mathsf w(v)=0$ otherwise. By an almost identical argument, we can show that $\mathsf w$ is a witness to $C_0$.

Fix $\cF_k$-free $k$-PDG $\vec H$ on $n$ vertices with positive instance $G \in \type^{-1}(\vec H)$. Let $\cS$ denote the collection of simple subformulae of $G$. If $G_1 \neq G_2 \in \cS$, then $G_1, G_2$ encode distinct $k\SAT$ functions.

Consider two distinct formulae in $\cS$, $G_1$ and $G_2$. First suppose that there exists a $k$-subset of variables $S\in{X\choose k}$ such that $G_1$ has a clause $C_1$ on $S$ but $G_2$ does not. By the above claim, $C_1\cup G_2$ is minimal, so there exists some $\mathsf w\in\{0,1\}^n$ that maps $C_1$ to 1 (and thus $G_1$ to 1) and $G_2$ to 0. Hence $G_1$ and $G_2$ encode distinct $k$-SAT functions.

Now suppose that there exists a $k$-subset of variables $S\in{X\choose k}$ such that $G_2$ has a clause $C_2$ on $S$ but $G_1$ does not. By the same argument, we know that $G_1$ and $G_2$ encode distinct $k$-SAT functions.

Finally, suppose that the clauses in $G_1$ and the clauses in $G_2$ lie on exactly the same $k$-subsets of variables. In this case, since $G_1\neq G_2$, there must exist some $S=\{v_1,\dots,v_k\}\in{X\choose k}$ such that $v_1\cdots v_k\in G_1$ and $v_1\cdots \ol v_k\in G_2$ (or vice versa). In this case, since $\{v_1\cdots v_k\}\cup G_2\setminus\{v_1\cdots \ol v_k\}$ is minimal, there exists some $\mathsf w\in\{0,1\}^n$ that maps $v_1\cdots v_k$ to 1 (and thus $G_1$ to 1) and $G_2\setminus\{v_1\cdots \ol v_k\}$ to 0 (and thus $G_2$ to 0). Hence $G_1$ and $G_2$ encode distinct $k$-SAT functions.

Combining <ref> and <ref> implies that for $\cF_k$-free PDG $\vec H$ with positive instance $G$, all simple subformulae of $G$ are minimal and yield distinct $k\SAT$ functions. This immediately implies the following lower bound.

For every $\cF_k$-free $k$-PDG $\vec H$ on $n$ vertices, the number of distinct $k$-SAT functions on $n$ variables is at least $2^{(\alpha(\vec H)+\log_23\cdot \beta(\vec H)) {n \choose k}}$.

The upper bound follows from <ref>.
To obtain the lower bound, notice that for every $n$, we have

$$\max\{\alpha(\vec H) + \log_23 \cdot (\vec H): \vec H\text{ is an $\cF_k$-free $k$-PDG on $n$ variables}\}\geq \pi(\cF_k, \log_23).$$

This is because we always have

\begin{multline*}
\max\{\alpha(\vec H) + \log_23 \cdot \beta(\vec H): \vec H\text{ is an $\cF_k$-free $k$-PDG on $n$ variables}\}\\
\leq \max\{\alpha(\vec H) + \log_23 \cdot \beta(\vec H): \vec H\text{ is an $\cF_k$-free $k$-PDG on $n-1$ variables}\}
\end{multline*}

due to an averaging argument, so the left-hand side is non-increasing with respect to $n$.

Hence for all $n$, we can we can take an $\cF_k$-free $k$-PDG $\vec H_n$ with

$$\alpha(\vec H_n) + \log_23 \cdot \beta(\vec H_n) \geq \pi(\cF_k, \log_23).$$

By <ref>, the number of distinct $k$-SAT functions on $n$ variables is at least $2^{\pi(\cF_k, \log_23){n\choose k}}$.

§ FORMULAE THAT ARE FAR FROM UNATE

We prove <ref> in the following two sections. Let $\cI(n)$ be the set of minimal $k$-SAT formulae on $n$ variables; notice that the number of $k\SAT$ functions is at most $|\cI(n)|$. In this section, we reduce the problem of bounding $|\cI(n)|$ to bounding the size of $\cI^*(n, \zeta)$, the collection of minimal formulae that satisfy a given witness condition. This collection of formulae is defined as follows:

Fix a $k$-SAT formula $G$.
Given a variable $x$, let $m(x)$ denote the number of clauses in $G$ in which the positive literal $x$ appears; analogously, $m(\overline{x})$ is the number of clauses in  $G$ in which the negative literal $\overline{x}$ appears.

For $\zeta>0$, let $\cI^*(n, \zeta)$ be the collection of minimal $k$-SAT formulae where $m(x) \ge m(\overline{x})$ for every variable $x$, and each clause in each formula has a witness $\mathsf w$ (an element of $\{0, 1\}^n$ that satisfies only that clause in the formula) with fewer than $\zeta n$ variables assigned to $1$.

We work to obtain a more precise estimate on the number of simple, minimal $k\SAT$ formulae by analyzing the set of containers arising from applying <ref>, where $\cB$ is the set of simple non-minimal formulae on at most $2(k+1)$ vertices.

In this section, we use these containers to enumerate those relatively “small” minimal formulae $G$, characterized by having $\alpha_1(G)$ bounded away from $1$. We also bound the number of simple, minimal formulae that are “far from unate.” We are able to bound the remaining “large” and “almost unate” formulae in terms of $|\cI^*(n, \zeta)|$, and give an upper bound on this quantity in <ref>, which allows us to complete the proof of <ref>.

We make the notion of being “almost unate” precise below.

For every $\rho > 0$, we say that a $k$-SAT formula $G$ is $\rho$-close to unate it can be made unate by removing up to  $\rho\binom{n}{k}$ clauses.
Otherwise we say that $G$ is $\rho$-far from unate.

In addition, for every variable $v$, we say that $v$ is $\rho$-close to unate if either $m(v)\leq \rho{n-1\choose k-1}$ or $m(\ol v)\leq \rho {n-1\choose k-1}$. Otherwise we say that $v$ is $\rho$-far from unate.

§.§ Large, simple $\rho$-far from unate formulae have many subformulae in $\cB$

We prove that for some appropriately chosen $\rho>0$, $a>0$ and $n$ sufficiently large, every simple $\rho$-far from unate formula with more than $(1-a){n\choose k}$ clauses has many non-unate $(k+1)$-cliques, where a $(k+1)$-clique is a simple formula with $k+1$ clauses on $k+1$ variables.

By <ref>, such a formula also contains many 2-blowups of non-unate $(k+1)$-cliques. Since the 2-blowup of every non-unate $(k+1)$-clique is non-minimal, such $G$ has many simple non-minimal subformulae on $2(k+1)$ vertices. The following definition of “link" formula will be used in our proof:

Given $k$-SAT formula $G$ and variable $v$, the positive link of $v$, denoted $G_{v}$, is the $(k-1)\SAT$ formula whose clauses are obtained by taking all clauses in $G$ that contain literal $v$ and removing $v$ from each such clause. The negative link of $v$, denoted $G_{\ol v}$, is the $(k-1)\SAT$ formula obtained by taking all all clauses in $G$ that contain literal $\overline{v}$ and removing $\overline{v}$ from each such clause.

For every $0 < \rho < 1$, we can take sufficiently small $a := a(\rho) > 0$ such that the following holds for $n$ sufficiently large. If $G$ is a simple $\rho$-far from unate formula with at least $(1 - a){n\choose k}$ clauses, then for some $\delta_1 = \delta_1(\rho, a)>0$, $G$ has at least $\delta_1 {n \choose k+1}$ non-unate $(k+1)$-cliques.

Take $c = \rho/2k$, $N>c^{-1}$ and  $a > 0$ sufficiently small so that

$$1-kN\cdot a -c^\frac{k}{k-1}-(1-c)^\frac{k}{k-1}>0.$$

Fix some $G$ that is $\rho$-far from unate with $|G|> (1 - a){n\choose k}$. We first show that there are at least $cn$ variables $v\in X$ that are $c$-far from unate in $G$. Notice that we can obtain a unate subformula $G'\subset G$ by doing the following: for every variable $v\in X$, if $m(v)\geq m(\ol v)$, then we delete all clauses in $G$ containing the literal $\ol v$; otherwise we delete all clauses in $G$ containing the literal $v$. If there are less than  $c n$ variables $v\in X$ that are $c$-far from unate in $G$, then we can delete at most

\begin{align*}
n\cdot c {n-1\choose k-1}+ cn \cdot {n-1\choose k-1} \le \rho{n\choose k}
\end{align*}

clauses to make $G$ unate, which contradicts the fact that $G$ is $\rho$-far from unate.
Also notice that there are at most $n/N$ vertices $v\in X$ with $m(v)+m(\ol v)\leq (1-Na){n-1\choose k-1}$, as otherwise we would have

$$|G|<\frac{1}{k}\left(\frac{n}{N}(1-Na){n-1\choose k-1}+\left(1-\frac{1}{N}\right)n{n-1\choose k-1}\right)\leq (1-a){n\choose k}.$$

Combining the above tells us that there are at least $\left(c-N^{-1}\right)n$ variables that are $c$-far from unate with $m(v)+m(\ol v)> (1-Na){n-1\choose k-1}$.

For every such $v$, consider the positive and negative link $(k-1)$-graphs $G_v$ and $G_{\ol v}$. By the Kruskal–Katona theorem in the form of <ref>, the number of $k$-cliques in $G_v$ is at most $\left((k-1)!|G_v|/(n-1)^{k-1}\right)^\frac{k}{k-1}\cdot (n-1)^{k}/k!$ and the number of $k$-cliques in $G_{\ol v}$ is at most $\left((k-1)!|G_{\ol v}|/(n-1)^{k-1}\right)^\frac{k}{k-1}\cdot (n-1)^{k}/k!$. Since $|G_v|=m(v)$, $|G_{\ol v}|=m(\ol v)$ and $v$ is $c$-far from unate, we know that $|G_v|,|G_{\ol v}| \geq c{n-1\choose k-1}$. By convexity, the number of monochromatic $k$-cliques in $G_v\cup G_{\ol v}$ is at most

$$\left(c^\frac{k}{k-1}+(1-c)^\frac{k}{k-1}+o(1)\right){n-1\choose k}.$$

Meanwhile, since $|G_v|+|G_{\ol v}|=m(v)+m(\ol v)> (1-Na){n-1\choose k-1}$, the number of $k$-cliques in $G_v\cup G_{\ol v}$ is at least $(1-Nk\cdot a ){n-1\choose k}$.
The number of non-monochromatic $k$-cliques in $G_v\cup G_{\ol v}$ is thus at least

$$\left(1-N k\cdot a-c^\frac{k}{k-1}-(1-c)^\frac{k}{k-1}+o(1)\right){n-1\choose k}.$$

Hence $G$ has at least

$$\frac{1}{k+1}\left(c-N^{-1}\right)n\cdot \left(1-N k\cdot a-c^\frac{k}{k-1}-(1-c)^\frac{k}{k-1}+o(1)\right){n-1\choose k}$$

non-unate $(k+1)$-cliques. Choosing any $0<\delta_1 < \left(c-N^{-1}\right)\left(1-N k\cdot a-c^\frac{k}{k-1}-(1-c)^\frac{k}{k-1}\right)$ yields the result.

It remains to show that the 2-blowup of any non-unate simplex is non-minimal.

Let $H$ be a non-unate simple formula with $k+1$ clauses on $k+1$ variables. Then the 2-blowup $H[2]$ is non-minimal.

Let $\{v_1,\dots, v_{k+1}\}$ be the variable set of $H$, and $\{v_1,v_1',\dots,v_{k+1},v_{k+1}'\}$ be the variable set of $H[2]$. Up to negating and/or relabeling some of the variables, $H$ contains a subformula $H'$ comprising $3$ clauses: a clause $C_1 = v_2 \cdots v_{k-1} v_k v_{k+1}$, a clause $C_2$ with positive literal $v_1$ and variables $v_2, v_3, \ldots, v_{k-1}, v_k$ (that may appear as positive or negative literals), and a clause $C_3$ with negative literal $\overline{v_1}$ and variables $v_2, v_3, \ldots, v_{k-2}, v_{k-1}, v_{k+1}$ (that may appear as positive or negative literals).

We show that $H'[2]$ is non-minimal. Since

$$\{v_2v_3\cdots v_{k+1},v_2'v_3\cdots v_{k+1},v_2v_3'\cdots v_{k+1},\dots,v_2v_3\cdots v_{k+1}'\}\subset H'[2],$$

if $\mathsf w\in\{0,1\}^{k+1}$ is a witness to the clause $v_2v_3\cdots v_{k+1}\in H'[2]$, then we must have

$$\mathsf w(v_2)=\dots=\mathsf w(v_{k+1})=1,$$

$$\mathsf w(v_2')=\dots=\mathsf w(v_{k+1}')=0.$$

Now if $\mathsf w(v_1)=1$, then there must be a clause in the 2-blowup of $C_2$ that gets mapped to 1. If $\mathsf w(v_1)=0$, then there must be a clause in the 2-blowup of $C_3$ that gets mapped to 1. This is a contradiction, so there is no witness $\mathsf w\in\{0,1\}^{k+1}$ to the clause $v_2v_3\cdots v_{k+1}\in H'[2]$.

Combining <ref>,  <ref> and <ref>, we have the following:

For every $\rho>0$, we can take sufficiently small $a := a(\rho) > 0$ such that the following holds for $n$ sufficiently large. If $G$ is a simple $\rho$-far from unate formula with at least $(1 - a){n\choose k}$ clauses, then there exists $\delta_2 = \delta_2(\rho, a)$ such that $G$ has at least $\delta_2 n^{2(k+1)}$ simple non-minimal subformulae on $2(k+1)$ variables.

§.§ Reducing the problem to bounding the size of some $\cI^*(n, \zeta)$

We are now able to give an upper bound on the number of minimal $k$-SAT formulae that do not satisfy a particular witness condition, thereby reducing the problem of bounding the size of $\cI(n)$ to bounding the size of $\cI^*(n,\zeta)$.

We first show that for any collection of $\rho$-close to unate formulae $\cG$, all but few elements of $\bigcup_{G\in\cG}\{H\subset G:H\text{ is minimal}\}$ lie in $\cI^*(n,\zeta)$ up to replacing some of the variables by their negations.

For any collection $\cG$ of $\rho$-close to unate formulae and $\zeta>0$, we have

\begin{align*}
\left|\bigcup_{G\in \cG}\{H\subset G:H\textup{ is minimal}\}\right|&\leq  |\cG|\cdot \left({n\choose\floor{\zeta n}}\left({\floor{\zeta n}\choose k}+1\right)2^{{n\choose k}-{\floor{\zeta n}\choose k}}2^{\rho{n\choose k}}\right)\\
\end{align*}

For every $G\in\cG$, there exists a negation of some variables that maps $G$ to some formula $G'$ having at most $\rho{n\choose k}$ non-monotone clauses. Without loss of generality, we assume that $G'$ has the greatest number of non-monotone clauses. In other words, no negation of variables maps $G$ to a formula having more non-monotone clauses. Notice that this automatically implies that $m(x)\geq m(\ol {x})$ in $G'$ for every $x\in X$.

We give an upper bound on the number of minimal subformulae of $G'$ that do not lie in $\cI^*(n, \zeta)$. By <ref>, for all $H\notin\mathcal \cI^*(n, \zeta)$, there exists a clause in $H$ and a witness $\mathsf w\in\{0,1\}^n$ to that clause, such that $\mathsf w$ assigns at least $\floor{\zeta n}$ variables to 1. Let $(v_1,\dots,v_{\floor{\zeta n}})$ be the lexicographically smallest $(\floor{\zeta n})$-tuple of variables, such that there exists some witness $\mathsf w$ to some clause in $H$ with $\mathsf w(v_1)=\dots=\mathsf w(v_{\floor{\zeta n}})=1$. Notice that since $\mathsf w$ is a witness to some clause in $H$, it cannot map two clauses in $H$ to 1. Hence at most one clause of the form $v_{i_1}\cdots v_{i_k}$ can appear in $H$.

We obtain a minimal formula $H\subset G'$ with $H\notin\mathcal \cI^*(n, \zeta)$ by making the following set of choices.

* We pick the non-monotone clauses in $H$. There are at most $2^{\rho {n \choose k}}$ such ways to make this selection since $G'$ has at most $\rho {n \choose k}$ non-monotone clauses.

* We pick the lexicographically smallest subset of literals $\{v_1, \ldots, v_{\floor{\zeta n}}\}$ so that there exists some witness $\mathsf w$ to a clause in $H$ with $\mathsf w(v_1)=\dots=\mathsf w(v_{\floor{\zeta n}})=1$. There are at most ${n \choose \floor{\zeta n}}$ ways to make such a choice.

* We choose the monotone clauses of the form $v_{i_1}\cdots v_{i_k}$, of which there are $({\floor{\zeta n}\choose k}+1)$ possible subsets since we can include at most one such clause.

* Finally, we choose the remaining monotone clauses, with variables not entirely drawn from $v_1, \ldots, v_{\floor{\zeta n}}$.

This yields the following upper bound on the number of  minimal formulae $H \subset G'$ with $H \not \in \cI^*(n, \zeta)$:

$$    {n\choose\floor{\zeta n}}\left({\floor{\zeta n}\choose k}+1\right)2^{{n\choose k}-{\floor{\zeta n}\choose k}}2^{\rho{n\choose k}}.$$

Hence all but at most $|\cG|\cdot \left({n\choose\floor{\zeta n}}\left({\floor{\zeta n}\choose k}+1\right)2^{{n\choose k}-{\floor{\zeta n}\choose k}}2^{\rho{n\choose k}}\right)$ elements of $\bigcup_{G\in\cG}\{H\subset G:H\text{ is minimal}\}$ lie in $\cI^*(n,\zeta)$ up to replacing some of the variables by their negations, and we have the desired bound.

We now state our main reduction step.

For every $\zeta>0$ and $\theta>\log_23$ with $\pi(\cF_k,\theta)=1$, there exists $\epsilon>0$ such that for all sufficiently large $n$ we have

$$|\cI(n)| \leq 2^{(1-\epsilon)\binom{n}{k}} + 2^{n} \abs{\cI^*(n, \zeta)}.$$

Given $\zeta>0$ and $\theta>\log_23$ with $\pi(\cF_k,\theta)=1$, we first choose $\rho>0$ sufficiently smaller than $\zeta$ and $\theta$, and then choose $\epsilon>0$ sufficiently smaller than $\rho$.

Let $\cB$ be the set of all simple non-minimal $k\SAT$ formulae on at most $2(k+1)$ vertices. Applying <ref> with $\cB$ and some $\delta > 0$ sufficiently smaller than $\epsilon$, we obtain a collection $\cG=\cG(\cB,\delta)$ of formulae that meets the following conditions:

* Every $\cB$-free formula with $n$ variables is a subformula of some $G \in \cG$;

* For every $G \in \cG$ and $B \in \cB$, $G$ has at most $\delta n^{v(B)}$ copies of $B$;

* $\abs{\cG} \le n^{C(\cB,\delta)n^{k-1/(m(\cB)-1)}}$.

Moreover, due to <ref>,  <ref> and the assumption that $\delta$ is sufficiently smaller than $\epsilon$, every $G\in \cG(\cB,\delta)$ also meets the following conditions:

* $\alpha_1(G)+\theta\cdot\alpha_{2,1}(G)< 1+\epsilon$;

* $\log_23 \cdot \alpha_{2,2}(G)+\log_24 \cdot \alpha_3(G)+\dots+\log_2(2^k+1) \cdot \alpha_{2^k}(G)<\epsilon$.

Every formula in $\cI(n)$ is $\cB$-free, so it is a subformula of some $G\in\cG(\cB,\delta)$. Hence we have

$$|\cI(n)|\leq\left|\bigcup_{G\in \cG(\cB,\delta)}\{H\subset G:H\text{ is minimal}\}\right|.$$

Define a partition $\cG(\cB,\delta)=\cG^{\sm} \sqcup \cG^{\lg}$ by

\begin{align*}
\cG^{\sm}&=\left\{G\in \cG(\cB,\delta):\alpha_1(G)\leq 1- 2\epsilon - \frac{3\epsilon }{\theta - \log_23}\right\},\\
\cG^{\lg}&=\left\{G\in \cG(\cB,\delta):\alpha_1(G)> 1- 2\epsilon - \frac{3\epsilon }{\theta - \log_23}\right\}.
\end{align*}

We first give an upper bound on the number of minimal subformulae of every $G\in \cG^{\sm}$. According to <ref>, every minimal $k\SAT$ formula can be made simple by deleting $o(n^k)$ clauses. This implies that for every $\epsilon>0$, we have

\begin{align*}
(\text{\# of minimal subformulae of $G$})&\leq \left(\sum_{t=1}^{o( n^k)}{2^k{n\choose k}\choose t}\right)\cdot(\text{\# of simple minimal subformulae of $G$})\\
&\leq 2^{\frac\epsilon2 {n\choose k}}\cdot (\text{\# of simple minimal subformulae of $G$})
\end{align*}

for sufficiently large $n$.

We now show that every $G\in \cG^{\sm}$ has $\wt(G)<1-\epsilon$, so $G$ has at most $2^{(1-\epsilon){n\choose k}}$ simple minimal subformulae. For all $G\in \cG^{\sm}$, since

$$\log_23 \cdot \alpha_{2,2}(G)+\log_24 \cdot \alpha_3(G)+\dots+\log_2(2^k+1) \cdot \alpha_{2^k}(G)<\epsilon,$$
we have

$$\wt(G) < \alpha_1(G)+\log_23\cdot \alpha_{2,1}(G)+\epsilon.$$

If $\alpha_1(G)+\theta\cdot\alpha_{2,1}(G)\leq 1-2\epsilon$, then since $\theta>\log_23$, we clearly have $\wt(G) < 1-\epsilon$. If $\alpha_1(G)+\theta\cdot\alpha_{2,1}(G)> 1-2\epsilon$, then since $\alpha_1(G)\leq 1- 2\epsilon - \frac{3\epsilon}{\theta - \log_23}$, we have $\alpha_{2,1}(G)>\frac{3\epsilon}{\theta-\log_23}$, so that

$$\wt(G) < \alpha_1(G) + \theta \cdot \alpha_{2,1}(G) - (\theta - \log_23)\cdot \alpha_{2,1}(G) +\epsilon< (1 + \epsilon) - 3 \epsilon +\epsilon = 1 - \epsilon.$$

Hence every $G\in \cG^{\sm}$ has $\wt(G)<1 - \epsilon$, which implies that $G$ has at most $2^{(1-\epsilon){n\choose k}}$ simple minimal subformulae. Therefore, when $n$ is sufficiently large, every $G\in \cG^{\sm}$ has at most $2^{\left(1-\frac\epsilon2\right){n\choose k}}$ minimal subformulae, and we have the upper bound

\begin{align}\label{eq:gsmall}
\left|\bigcup_{G\in \cG^{\sm}}\{H\subset G:H\text{ is minimal}\}\right|\leq |\cG^{\sm}|\cdot 2^{\left(1-\frac\epsilon2\right){n\choose k}}.
\end{align}

We now give an upper bound on $\left|\bigcup_{G\in \cG^{\lg}}\{H\subset G:H\text{ is minimal}\}\right|$. For all $G\in\cG^{\lg}$, we know that

$$\alpha_1(G) > 1 - 2\epsilon - \frac{3\epsilon}{\theta - \log_23}.$$

Choose a simple subformula $G_s\subset G$ with $|G_s|=\alpha_1(G){n\choose k}$.
Since $G$ has at most $\delta n^{v(B)}\leq \delta n^{2(k+1)}$ copies of any $B\in\cB$,  we know that $G_s\subset G$ has a total of at most
$$|\cB|\cdot \delta n^{2(k+1)}\overset{(*)}{<}\delta_2\left(\frac{\rho}{2},2\epsilon + \frac{3\epsilon }{\theta - \log_23}\right)n^{2(k+1)}$$

simple non-minimal formulae on $2(k+1)$ variables, where $\delta_2$ is defined in <ref>. Here (*) is due to the fact that $\delta$ is much smaller than $\epsilon$ (and thus also $\rho,\theta$). Since $\epsilon$ is significantly smaller than $\rho$,  <ref> applies, so $G_s$ is $\frac{\rho}{2}$-close to unate.

Meanwhile, since $\alpha_1(G)$ is large, $\alpha_{2,1}(G),\alpha_{2,2}(G),\alpha_3(G),\dots,\alpha_{2^k}(G)$ are all very small. In particular, we have

$$\alpha_{2,1}(G)<\frac{1}{\theta}\left((1+\epsilon)-\left(1 - 2\epsilon - \frac{3\epsilon }{\theta - \log_23}\right)\right)=\frac{3\epsilon}{\theta}+\frac{3\epsilon }{\theta(\theta - \log_23)}$$

$$\log_23 \cdot \alpha_{2,2}(G)+\log_24 \cdot \alpha_3(G)+\dots+\log_2(2^k+1) \cdot \alpha_{2^k}(G)<\epsilon.$$

This gives

\begin{align*}
|G\setminus G_s|&\leq (\alpha_{2,1}(G)+\alpha_{2,2}(G)){n\choose k}+2\alpha_{3}(G){n\choose k}+\dots+(2^k-1)\alpha_{2^k}(G){n\choose k}\\
&\overset{(**)}{<}\frac{\rho}{2}{n\choose k},
\end{align*}

where (**) is due to the fact that $\epsilon$ is sufficiently smaller than $\rho$.

Combining the above, we know that every $G\in \cG^{\lg}$ is $\rho$-close to unate. Hence $\cG^{\lg}$ is a family of $\rho$-close to unate formulae. By <ref>, we have

\begin{align}\label{eq:glarge}
\begin{split}
\left|\bigcup_{G\in \cG^{\lg}}\{H\subset G:H\text{ is minimal}\}\right|&\leq  |\cG^{\lg}|\cdot\left({n\choose\floor{\zeta n}}\left({\floor{\zeta n}\choose k}+1\right)2^{{n\choose k}-{\floor{\zeta n}\choose k}}2^{\rho{n\choose k}}\right)\\
&\overset{(***)}{\leq} |\cG^{\lg}|\cdot  2^{(1-\epsilon){n\choose k}}+2^n|\cI^*(n, \zeta)|,
\end{split}
\end{align}

for sufficiently large $n$, where (***) is due to the fact that $\epsilon$ is sufficiently smaller than $\rho$.

$$|\cG^{\sm}|,|\cG^{\lg}|\leq|\cG(\cB,\delta)|\leq n^{C(\cB,\delta)n^{k-1/(m(\cB)-1)}},$$

combining <ref> and <ref>, we have the following upper bound on $|\cI(n)|$ for $n$ sufficiently large:

\begin{align*}
|\cI(n)|&\leq \left|\bigcup_{G\in \cG(\cB,\delta)}\{H\subset G:H\text{ is minimal}\}\right|\\
&\leq |\cG^{\sm}|\cdot 2^{\left(1-\frac\epsilon2\right){n \choose k}}+|\cG^{\lg}|\cdot 2^{(1-\epsilon){n\choose k}}+2^n|\cI^*(n, \zeta)|\\
&\leq n^{C(\cB,\delta)n^{k-1/(m(\cB)-1)}}\left(2^{\left(1-\frac\epsilon2\right){n \choose k}}+2^{(1-\epsilon){n\choose k}+n}\right)+2^n|\cI^*(n, \zeta)|\\
&\leq 2^{\left(1-\frac\epsilon3\right){n \choose k}}+ 2^n|\cI^*(n, \zeta)|. \qedhere
\end{align*}

§ NEARLY UNATE FORMULAE

In this section we prove the following recursive bound.

There exist $\zeta>0$ and $c>0$ such that for all $n$, we have

\begin{multline*}
|\cI^*(n, \zeta)| \le 2^{n\choose k}+\exp_2\sqb{(1-c){n\choose k}}+\sum_{i=1}^{k-2}\exp_2\sqb{i(1-c){n\choose k-1}}|\cI(n-i)|
\\+\exp_2\sqb{(1-c)k{n\choose k-1}} |\cI(n-k)|+\exp_2\sqb{{n\choose k}-cn^{k-2}}.
\end{multline*}

Our approach in this section extends the arguments in Ilinca–Kahn <cit.>.
To obtain the above bound, we consider a sequence of subcollections of $\cI^*(n, \zeta)$ and bound the size of each one, showing that most of the formulae in $\cI^*(n, \zeta)$ are monotone.

* We first show that most formulae in $\cI^*(n, \zeta)$ use each of the $n$ variables a comparable number of times amongst their clauses, thus disregarding those formulae that have very few occurrences of at least one variable.

* We then observe that most formulae in $\cI^*(n, \zeta)$ have very few non-monotone clauses that contain at most $k-2$ negative literals.

* Next, we show that most formulae in $\cI^*(n, \zeta)$ have very few non-monotone clauses that contain $k-1$ or $k$ negative literals.

* Finally, we give an upper bound on the number of non-monotone formulae that satisfy the above three conditions.

* We combine the above to obtain a recursive bound on $|\cI^*(n, \zeta)|$ that gives the desired stability result.

We let $H(\cdot)$ denote the binary entropy function, $H(p)=-p\log_2p-(1-p)\log_2(1-p)$. Recall the standard inequality

\[
\sum_{t\leq p n}{n\choose i}\leq 2^{H(p)n} \quad \text{ for all } 0<p\le 1/2 \text{ and } n \in \NN.
\]

We also recall several definitions regarding $k\SAT$ formulae. Let $X=\{x_1,\dots,x_n\}$ denote the set of $n$ variables on which we count the $k$-SAT formulae in $\cI^*(n, \zeta)$. For every clause $C$ in a minimal formula $G$, we say that $\mathsf w\in\{0,1\}^n$ is a witness to $G$ if $\mathsf w$ maps $C$ to 1 and all other clauses in $G$ to $0$.

The following steps <ref> to <ref> roughly correspond to Steps 1 to 5 in <cit.>.

§.§ Most minimal formulae have large support for each variable
We start by observing that most formulae in $\cI^*(n, \zeta)$ have lots of clauses involving $v$ for every variable $v\in X$. More precisely, we show that for most formulae in $\cI^*(n, \zeta)$, each variable $v \in X$ is used in at least $\frac{1}{10k}{n-1\choose k-1}$ clauses.

$$\cI_1^*(n, \zeta)=\left\{G\in \cI^*(n, \zeta):\text{each variable $v\in X$ is used at least $\frac{1}{10 k}{n-1\choose k-1}$ times in $G$}\right\}.$$

We have

$$|\cI^*(n, \zeta)\setminus \cI_1^*(n, \zeta)| < \exp_2\sqb{\frac12 {n-1\choose k-1}} |\cI(n-1)|.$$

We count the number of $G\in \cI^*(n, \zeta)\setminus \cI_1^*(n, \zeta)$. There are at most
$$n\sum_{t\leq \frac{1}{10 k}{n-1\choose k-1}}{{2^k{n-1\choose k-1}}\choose t}  < \exp_2\sqb{H\left(\frac{1}{ 10k\cdot 2^k}\right)2^k{n-1\choose k-1}}  < \exp_2\sqb{\frac12{n-1\choose k-1}} $$
ways to choose a variable $v\in X$ that occurs fewer than $\frac{1}{10 k} {n-1 \choose k-1}$ times in $G$, along with the clauses containing $v$. The remaining clauses in $G$ form a minimal formula on $n-1$ variables, so there are at most $|\cI(n-1)|$ ways to choose the remaining clauses. Combining gives the desired bound.

Using the fact that every variable appears in many clauses in $\cI_1^*(n, \zeta)$ we are able to conclude that for formulae in $\cI^*_1(n, \zeta)$, most clauses are monotone. We make the following more precise observations that will prove useful in subsequent steps.

For every $G \in \cI_1^*(n, \zeta)$, the following are true.

* For every $k-1$ variables $v_1,\dots, v_{k-1}$, there are at most $\zeta n$ variables $w$ such that $v_1\cdots v_{k-1}\ol w\in G$. The same bound holds for $w$'s with $\ol v_1v_2\cdots v_{k-1}\ol w\in G$, $w$'s with $ v_1\ol v_2v_3 \cdots v_{k-1}\ol w\in G$,  $w$'s with $\ol v_1\ol v_2 v_3\cdots  v_{k-1}\ol w\in G$, and so on.

* For every variable $v$ and $j\in\{1,\dots,k-1\}$, there are at most $\zeta n^{k-1}$ clauses in $G$ containing the positive literal $v$ and exactly $j$ negative literals.

* For every variable $v$ and $j\in\{1,\dots,k-1\}$, there are at most $\zeta n^{k-1}$ clauses in $G$ containing the negative literal $\ol v$ and exactly $j$ negative literals other than $\ol v$.

* For every $i\in \{1,\dots,k\}$, there are at most $\zeta n^{k}$ clauses in $G$ having exactly $i$ negative literals.

* $G$ has at most $k\zeta n^{k}$ non-monotone clauses.

* For every variable $v\in X$, $G$ has at least $\frac{1}{20k}  {n-1 \choose k-1} - (k-1)\zeta n^{k-1}$ monotone clauses containing $v$.

We prove these properties of formulae $G\in \cI_1^*(n, \zeta)$.

* If there are more than $\zeta n$ such $w$, then consider a witness $\mathsf w\in\{0,1\}^n$ to some $v_1\cdots v_{k-1}\ol w_0$. For any other $w\neq w_0$ such that  $v_1\cdots v_{k-1}\overline{w} \in G$, we must have $\mathsf w(w)=1$, a contradiction. Other cases are similar.

* For any $k-2$ literals $ \ol v_1, \dots, \ol v_{j-1}, v_j,\ldots,v_{k-2}$, by (a), $G$ contains at most $\zeta n$ clauses of the form $v\ol v_1 \cdots \ol v_{j-1} v_j\cdots v_{k-2}\ol w$. There are at most $n^{k-2}$ ways to choose these $k-2$ literals.

* Same as above.

* This easily follows from (b) and (c).

* Follows from (d).

* Since $G \in \cI^*(n, \zeta)$, we have $m(v) \ge m(\overline{v})$ for all variables $v\in X$. Since $G \in \cI_1^*(n, \zeta)$, we have $m(v) + m(\overline{v}) \ge \frac{1}{10k} {n-1\choose k-1}$. This implies $m(v) \ge \frac{1}{20k}{n-1\choose k-1}$. By (b), there are at most $(k-1)\zeta n^{k-1}$ non-monotone clauses that contain the positive literal $v$.

§.§ Most minimal formulae have few clauses with negated literals

We will eventually show that most formulae in $\cI_1^*(n, \zeta)$ have very few clauses containing any negative literals. In this subsection, we give an upper bound on the number of formulae in $\cI_1^*(n, \zeta)$ having a large numbers of clauses containing $i$ negative literals, for any $1 \le i \le k-2$.

For every $\beta_1>0$, we define

\begin{multline*}
\cI^*_{2,1}(n, \zeta,\beta_1)=\left\{G\in \cI_{1}^*(\zeta):\text{for all $u\in X$, $G$ contains at most $\beta_1n^{k-1}$ clauses}\right. \\\left.\text{of the form } \ol uv_1\cdots v_{k-1}\right\}.
\end{multline*}

For every $i\in\{2,\dots,k-2\}$ and $\beta_i>0$, we define

\begin{multline*}
\cI^*_{2,i}(n, \zeta,\beta_1,\beta_i)=\left\{G\in \cI_{2,1}^*(n, \zeta,\beta_1):\text{for all $\{u_1,\dots,u_i\}\in{X\choose i}$, }\right. \\\left.\text{$G$ contains at most $\beta_in^{k-i}$ clauses of the form } \ol u_1\cdots\ol u_iv_1\cdots v_{k-i}\right\}.
\end{multline*}

For every vector $\vec\beta=(\beta_1,\dots,\beta_{k-2})$, we define $\cI_2^*(n, \zeta,\vec\beta)=\bigcap_{i=2}^{k-2}\cI^*_{2,i}(n, \zeta,\beta_1,\beta_i)$.

We will first show that most formulae in $\cI_1^*(n, \zeta)$ are in $\cI_{2,1}^*(n, \zeta,\beta_1)$ for every $\beta_1 > 0$ and sufficiently small $\zeta$.

§.§.§ Formulae with lots of clauses $\overline{u}v_1 \cdots v_{k-1}$

For every $\beta_1>0$, there exist $\zeta>0$ and $c > 0$ such that

$$|\cI^*_{1}(n, \zeta)\setminus \cI_{2,1}^*(n, \zeta,\beta_1)|\leq \exp_2\sqb{(1-c){n\choose k}}+\exp_2\sqb{(1-c){n\choose k-1}}|\cI (n-1)|.$$

For every $\beta_1>0$, we choose $\xi>0$ sufficiently smaller than $\beta_1$, choose $\theta_1>0$  sufficiently smaller than $\xi$, and then choose $\zeta>0$  sufficiently smaller than $\theta_1$. Take a small constant $c=c(\beta_1,\xi,\theta_1,\zeta)>0$.

For every $G\in \cI^*_{1}(n,\zeta)\setminus \cI_{2,1}^*(n, \zeta,\beta_1)$, by definition, there exists some $u\in X$ such that $G$ contains more than $\beta_1n^{k-1}$ clauses of the form $\ol uv_1\cdots v_{k-1}$. Set $X_u=X\setminus \{u\}$ and

\begin{align*}
N_u^+&=\left\{\{v_1,\dots,v_{k-1}\}\subset X_u:uv_1\cdots v_{k-1}\in G\right\},\\
N_u^-&=\left\{\{v_1,\dots,v_{k-1}\}\subset X_u:\ol uv_1\cdots v_{k-1}\in G\right\},\\
S_1&=\left\{\{v_1,\dots,v_{k-2}\}\subset X_u:\codeg_{N_u^+}(\{v_1,\dots,v_{k-2}\})<\theta_1n\right\},\\
S_2&=\left\{\{v_1,\dots,v_{k-2}\}\subset X_u:\codeg_{N_u^-}(\{v_1,\dots,v_{k-2}\})<\theta_1n\right\},\\
T&={X_u\choose k-2}\setminus(S_1\cup S_2),
\end{align*}

where  $\codeg_{N_u^+}$ (resp. $\codeg_{N_u^-}$) is defined to be

$$\codeg_{N_u^+}(\{v_1,\dots,v_{k-2}\})=|\{w\in X_u: \{v_1,\dots,v_{k-2},w\}\in N_u^+\}|.$$

Since there are at most

$$|S_2|\theta_1 n+\left({n-1\choose k-2}-|S_2|\right)n\leq (|S_1|+|T|)n+\frac{\theta_1 n^{k-1}}{(k-2)!}$$

clauses of the form $\ol uv_1\cdots v_{k-1}$, we have

$$\beta_1n^{k-1}\leq (|S_1|+|T|)n+\frac{\theta_1 n^{k-1}}{(k-2)!},$$

and at least one of the following:

* $|T|>\theta_1 n^{k-2}$;

* $|T|\leq \theta_1 n^{k-2}$ and $|S_1|\geq \left(\beta_1-\frac{(k-2)!+1}{(k-2)!}\cdot \theta_1\right)n^{k-2}>\xi n^{k-2}$. (Here we used the fact that  $\theta_1$ is sufficiently smaller than $\xi$.)

For sufficiently small $c>0$, there are at most $\exp_2\left[(1-c){n\choose k}\right]$ formulae $G\in \cI^*_{1}(\zeta)\setminus \cI_{2,1}^*(n, \zeta,\beta_1)$ where $|T| > \theta_1 n^{k-2}$, for $T$ defined as above.

Consider one such $G$.
Notice that if $\{v_1,\dots,v_{k-2},v_{k-1}\}\in N_u^+$ and $\{v_1,\dots,v_{k-2},v_{k}\}\in N_u^-$, then we cannot have $v_1\cdots v_{k-2}v_{k-1}v_k\in G$ due to the non-minimal formula

$$\{v_1\cdots v_{k-2}v_{k-1}u, v_1\cdots v_{k-2}v_{k}\ol u, v_1\cdots v_{k-2}v_{k-1}v_k\}$$

(as it is impossible to satisfy only the first clause). Hence after specifying (1) $u$ and $T$, (2) the elements in $N_u^+$ containing some element in $T$, and (3) the elements in $N_u^-$ containing some element in $T$, we know at least

$$\frac{1}{{k\choose 2}}\cdot |T|\cdot \theta_1n\cdot \theta_1n>\frac{1}{{k\choose 2}}\cdot \theta_1n^{k-2}\cdot \theta_1n\cdot \theta_1n=\frac{\theta_1^3n^k}{{k\choose 2}}$$

monotone clauses that cannot belong to $G$.
To specify some $G \in \cI_1^*(n, \zeta) \backslash \cI_{2, 1}(n,\zeta, \beta_1)$ where $|T| > \theta_1 n^{k-2}$, it suffices to make the following choices.

* We choose a variable $u \in X$ where $G$ has more than $\beta_1 n^{k-1}$ clauses $\overline{u} v_1 \cdots v_{k-1}$. There are at most $n$ such choices.

* We pick the set $T$. Since each element of $T$ is a set of $k-2$ variables, there are at most $2^{{n\choose k-2}}$ choices for $T$.

* We choose the elements of $N_u^+$ and $N_u^-$ that contain some element of $T$. Since $N_u^+,N_u^-\subset {X_u\choose k-1}$ and $T\subset {X_u\choose k-2}$, the number of choices is at most $2^{|T|n} \cdot 2^{|T|n} \leq \exp_2[2\theta_1n^{k-1}]$.

* We choose the non-monotone clauses in $G$.  <ref> tells us that $G$ has at most $k\zeta n^k$ non-monotone clauses, so the number of such choices is at most $\binom{(2^k-1)\binom{n}{k}}{\le k \zeta n^k} = \exp_2[O_k(\zeta \log(1/\zeta))\binom{n}{k}]$.

* Finally, we choose the monotone clauses in $G$. Per above, we know that there are at least $\theta_1^3 n^k / {k \choose 2}$ monotone clauses that cannot belong to $G$; this implies the simple upper bound
$\exp_2\left[{n\choose k}-\frac{\theta_1^3n^k}{{k\choose 2}}\right]$.

Hence the number of possible $G$ is at most

$$n\cdot 2^{{n\choose k-2}}\cdot \exp_2[2\theta_1n^{k-1}]\cdot  \exp_2\left[O_k(\zeta \log(1/\zeta))\binom{n}{k}+{n\choose k}-\frac{\theta_1^3n^k}{{k\choose 2}}\right]\overset{(*)}{\leq} \exp_2\left[(1-c){n\choose k}\right],$$

where (*) is due to the fact that $\zeta$ is sufficiently smaller than $\theta_1$, and $c$ is small.

For sufficiently small $c>0$, there are at most $\exp_2\sqb{(1-c){n\choose k-1}}|\cI(n-1)|$ formulae $G\in \cI^*_{1}(n,\zeta)\setminus \cI_{2,1}^*(n, \zeta,\beta_1)$ where $|T|\leq \theta_1 n^{k-2}$ and $|S_1| >\xi n^{k-2}$, for $S_1, T$ defined as above.

Consider one such $G$. We can uniquely specify $G$ via the following 5 choices:

* $u$;

* the monotone clauses containing $u$;

* the clauses containing $\ol u$ where all other literals are positive;

* the clauses containing (i) either $u$ or $\ol u$; (ii) some negative literal other than $\ol u$;

* the clauses not involving the variable $u$.

Observe that choosing (2) and (3) is equivalent to choosing $N_u^+$ and $N_u^-$. Since the number of monotone clauses in $G$ using $u$ is at least $\frac{1}{20}{n-1\choose k-1}-(k-1)\zeta n^{k-1}$ according to <ref>, and also at most $\frac{1}{k-1}(|S_1|\theta_1n+({n-1\choose k-2}-|S_1|)n)$, we have the inequality

$$\frac{1}{20}{n-1\choose k-1}-(k-1)\zeta n^{k-1}\leq \frac{1}{k-1}\left(|S_1|\theta_1n+\left({n-1\choose k-2}-|S_1|\right)n\right).$$

After some rearrangement, this gives an upper bound on the size of $S_1$ and thus a lower bound on the size of $S_2$:

\begin{align*}
&|S_1|\leq \frac{1}{1-\theta_1}\left(\frac{1}{(k-2)!}+(k-1)^2\zeta-\frac{0.9}{20(k-2)!}\right)n^{k-2},\\
&|S_2|\overset{(*)}{\geq} {n\choose k-2}-\theta_1n^{k-2}-\frac{1}{1-\theta_1}\left(\frac{1}{(k-2)!}+(k-1)^2\zeta-\frac{0.9}{20(k-2)!}\right)n^{k-2}\overset{(**)}{\geq}\xi n^{k-2}.
\end{align*}

Here (*) is due to the fact that $|T|\leq\theta_1n^{k-2}$, and (**) is due to the fact that $\theta_1$ is sufficiently smaller than $\xi$, and $\zeta$ is sufficiently smaller than $\theta_1$. We then count the ways to choose such $G$.

* We choose a variable $u \in X$ where $G$ has more than $\beta_1 n^{k-1}$ clauses $\overline{u} v_1 \cdots v_{k-1}$. There are at most $n$ such choices.

* We choose sets $S_1, S_2, T$. There are at most $2^{{n\choose k-2}} \cdot 2^{{n\choose k-2}} = 4^{{n\choose k-2}}$ to choose $S_1, S_2$ (and consequently $T$).

* We then choose which elements of $N_u^+$ meet $S_1 \cup T$ and which elements of $N_u^-$ meet $S_2 \cup T$. The number of such choices is at most

\begin{align*}
2^{|T|n}\left(\sum_{t=1}^{\theta_1n}{n\choose t}\right)^{|S_1|} \cdot 2^{|T|n}\left(\sum_{t=1}^{\theta_1n}{n\choose t}\right)^{|S_2|}&\leq \exp_2\sqb{ 2\theta_1n^{k-1}+H(\theta_1)n (|S_1|+|S_2|)}\\
&\leq \exp_2\sqb{ 2\theta_1n^{k-1}+H(\theta_1)n^{k-1}}.
\end{align*}

* We then choose the elements of $N_u^-$ that only meet $S_1\setminus S_2$ and the elements of $N_u^+$ that only meet $S_2\setminus S_1$. By the Kruskal–Katona theorem in the form of <ref>, the number of such choices is at most

\begin{align*}
\exp_2 &\sqb{ \frac{((k-2)!|S_1\setminus S_2|)^\frac{k-1}{k-2}}{(k-1)!}+\frac{((k-2)!|S_2\setminus S_1|)^\frac{k-1}{k-2}}{(k-1)!} } \\
&\leq \exp_2 \sqb{ \frac{((k-2)!)^\frac{k-1}{k-2}}{(k-1)!}\left(|S_1\setminus S_2|^\frac{k-1}{k-2}+|S_2\setminus S_1|^\frac{k-1}{k-2} \right)}\\
&\overset{(*)}\le \exp_2 \sqb{\frac{((k-2)!)^\frac{k-1}{k-2}}{(k-1)!} \left(\xi^\frac{k-1}{k-2}+\left(\frac{1}{(k-2)!}-\xi\right)^\frac{k-1}{k-2}\right)n^{k-1}}.
\end{align*}

We obtain (*) by noting that since $x^{(k-1)/(k-2)}$ is convex and $|S_2|\geq \xi n^{k-2}$, we have

$$|S_1\setminus S_2|^\frac{k-1}{k-2}+|S_2\setminus S_1|^\frac{k-1}{k-2}\leq |S_1|^\frac{k-1}{k-2}+\left({n\choose k-2}-|S_1|\right)^\frac{k-1}{k-2}\leq \left(\xi^\frac{k-1}{k-2}+\left(\frac{1}{(k-2)!}-\xi\right)^\frac{k-1}{k-2}\right)n^{k-1}.$$

* We choose those non-monotone clauses containing the variable $u$ and at least one negated literal that is not $\ol u$. By <ref>, there are at most

$$\left((k-1)!\sum_{t=1}^{\zeta n^{k-1}}{{n\choose k-1}\choose t}\right)^{2(k-1)}=\exp_2\left[O_k(\zeta\log(1/\zeta)){n\choose k-1}\right]$$

* We choose the clauses not containing $u$, which we can do in at most $|\cI (n-1)|$ ways.

Consequently the number of $G \in \cI^*_{1}(n,\zeta)\setminus \cI_{2,1}^*(n,\zeta,\beta_1)$ with $|T|\leq \theta_1 n^{k-2}$ and $|S_1|>\xi n^{k-2}$ is bounded above by

\begin{align*}
&n \cdot 4^{{n\choose k-2}} \cdot  \exp_2\left[2\theta_1n^{k-1}+H(\theta_1)n^{k-1}+\frac{((k-2)!)^\frac{k-1}{k-2}}{(k-1)!}\left(\xi^\frac{k-1}{k-2}+\left(\frac{1}{(k-2)!}-\xi\right)^\frac{k-1}{k-2}\right)n^{k-1}\right.\\
&\left.\hspace{8cm}+O_k(\zeta\log(1/\zeta)){n\choose k-1}\right]|\cI (n-1)|\\
&\overset{(*)}{\leq}\exp_2\sqb{(1-c){n\choose k-1}}|\cI (n-1)|,
\end{align*}

where (*) is due to the fact that $\theta_1$ and $\zeta$ are sufficiently smaller than $\xi$, and $c$ is small.

Combining the above two cases, we have

$$|\cI^*_{1}(n,\zeta)\setminus \cI_{2,1}^*(n, \zeta,\beta_1)|\leq \exp_2\sqb{(1-c){n\choose k}}+\exp_2\sqb{(1-c){n\choose k-1}}|\cI (n-1)|.$$

§.§.§ Formulae with lots of clauses $\overline{u_1} \cdots \ol u_i v_1 \cdots v_{k-i}$

Next, we bound the number of formulae in $\cI_{2,1}^*(n, \zeta,\beta_1)$ that have many clauses of the form $\ol u_1\cdots \ol u_iv_1\cdots v_{k-i}$ for some $2\leq i\leq k-2$ and $u_1,\dots,u_i\in X$.

Fix some  $i\in\{2,\dots,k-2\}$. Then, for any $\beta_i>0$, there exist $\beta_1>0$, $\zeta>0$ and $c > 0$ such that

$$|\cI^*_{2,1}(n, \zeta,\beta_1)\setminus \cI_{2,i}^*(n, \zeta,\beta_1,\beta_i)|\leq \exp_2\left[(1-c){n\choose k}\right]+\exp_2\left[i(1-c){n\choose k-1}\right]|\cI(n-i)|.$$

Fix $i$. For every $\beta_i>0$, we choose $\theta_i>0$ and $\beta_1>0$ sufficiently smaller than $\beta_i$, and then choose $\zeta>0$ sufficiently smaller than $\theta_i$. Take a small constant $c = c(\beta_i,\theta_i, \beta_1,\zeta) > 0$.

For every $G\in \cI_{2,1}^*(n,\zeta,\beta_1)\setminus \cI_{2,i}^*(n,\zeta,\beta_1,\beta_i)$, by definition, there exist some $u_1,\dots,u_i\in X$ such that there are more than $\beta_in^{k-i}$ clauses of the form $\ol u_1\cdots\ol u_iv_1\cdots v_{k-i}$. Let $X_{\mathbf u}=X\setminus\{u_1,\dots,u_i\}$. For every $j\in\{1,\dots,i\}$ and $\mathbf v=\{v_1,\dots,v_{k-i}\}\subset X_{\mathbf u}$, set

$$N_{u_j,\mathbf v}=\left\{\{w_1,\dots,w_{i-1}\}\in {X_{\mathbf u}\choose i-1}:u_jv_1\cdots v_{k-i}w_1\cdots w_{i-1}\in G\right\}.$$

Additionally, let

\begin{align*}
M&=\left\{\{v_1,\dots,v_{k-i}\}\in{X_{\mathbf u}\choose k-i}:\ol u_1\cdots\ol u_iv_1\cdots v_{k-i}\in G\right\},\\
A&=\left\{\mathbf v=\{v_1,\dots,v_{k-i}\}\in M:\left|\bigcap_{j=1}^iN_{u_j,\mathbf v}\right|\geq\theta_in^{i-1}\right\}, \\
B&=M\setminus A.
\end{align*}

Since $|M|>\beta_in^{k-i}$, at least one of the following holds:

* $|A|>\theta_in^{k-i}$;

* $|B|>(\beta_i-\theta_i)n^{k-i}$.

For sufficiently small $c>0$, there are at most $\exp_2\left[(1-c){n\choose k}\right]$ formulae $G \in \cI_{2,1}^*(n,\zeta,\beta_1)\setminus \cI_{2,i}^*(n,\zeta,\beta_1,\beta_i)$, with $|A|>\theta_in^{k-i}$ for $A$ defined as above.

Consider one such $G$. Since $G$ is minimal, for every $\mathbf v=\{v_1,\dots,v_{k-i}\}\in M$ and $\{w_1,\dots,w_{i-1}\}\in \bigcap_{j=1}^iN_{u_j,\mathbf v}$, to avoid the non-minimal subformula

$$\{v_1\cdots v_{k-i}w_1\cdots w_{i-1}z, v_1\cdots v_{k-i}w_1\cdots w_{i-1}u_1,\ldots,v_1\cdots v_{k-i}w_1\cdots w_{i-1}u_i, \ol u_1\cdots\ol u_iv_1\cdots v_{k-i}\},$$

(as it is impossible to satisfy only the first clause), we cannot have $v_1\cdots v_{k-i}w_1\cdots w_{i-1}z\in G$ for any $z\in X$. Hence after specifying (1) $u_1,\dots,u_i$, (2) $A$ and (3) $\bigcap_{j=1}^iN_{u_j,\mathbf v}$ for every $\mathbf v\in A$, we know at least

$$\frac{1}{i{k\choose i}}\cdot |A|\cdot \theta_in^{i-1}\cdot (n-(k-1))\geq \frac{1}{i{k\choose i}}\cdot \theta_in^{k-i}\cdot \theta_in^{i-1}\cdot (n-(k-1))\geq \frac{\theta_i^2\cdot k!}{i{k\choose i}}{n\choose k}$$

monotone clauses that cannot belong to $G$. We can specify some $G$ by making the following set of choices.

* We choose $i$ variables $u_1, \ldots , u_i$. This can be done in at most ${n\choose i}$ ways.

* We choose $A$. There are at most $2^{n\choose {k-i}}$ possibilities.

* For each $\mathbf v\in A$, we pick  $\bigcap_{j=1}^iN_{u_j,\mathbf v}$. There are at most $2^{{n\choose {i-1}}|A|}\leq 2^{n^{k-1}}$ ways to make this set of choices.

* We select the non-monotone clauses in $G$, from at most $\exp_2\sqb{O_k(\zeta\log(1/\zeta)){n\choose k}}$ choices.

* Finally, we choose the monotone clauses in $G$. We can do this in at most
$$\exp_2\left[{n\choose k}-\frac{\theta_i^2\cdot k!}{i{k\choose i}}{n\choose k}\right]$$
ways given the set of monotone clauses excluded by the above argument.

Hence the number of possible $G$ is at most

\begin{align*}
&{n\choose i}\cdot 2^{n\choose {k-i}}\cdot 2^{n^{k-1}}\cdot \exp_2\left[O_k(\zeta\log(1/\zeta)){n\choose k}+{n\choose k}-\frac{\theta_i^2\cdot k!}{i{k\choose i}}{n\choose k}\right]\\
&\overset{(*)}{\leq}\exp_2\left[(1-c){n\choose k}\right],
\end{align*}

where (*) is due to the fact that $\zeta$ is sufficiently smaller than $\theta_i$, and $c$ is small.

For sufficiently small $c>0$, there are at most $\exp_2\left[i(1-c){n\choose k-1}\right]|\cI(n-i)|$ formulae $G \in \cI^*_{2,1}(n,\zeta,\beta_1)\setminus \cI^*_{2,i}(n,\zeta,\beta_1,\beta_i)$, with  $|B|>(\beta_i-\theta_i)n^{k-i}$ for $B$ defined as above.

Consider one such $G$.
We set

$$    Q=\left\{\{w_1,\dots,w_{k-1}\}\in {X_{\mathbf u}\choose k-1}:\exists j\in[i]\text{ such that }u_jw_1\cdots w_{k-1}\notin G\right\},$$

so that for every $\{w_1,\dots,w_{k-1}\}\in Q$, there are at most $2^i-1$ ways to choose which of $u_1w_1\cdots w_{k-1}$, …, $u_iw_1\cdots w_{k-1}$ lie in $G$. Notice that for every $\mathbf v=\{v_1,\dots,v_{k-i}\}$, we have

$$\left\{\{v_1,\dots,v_{k-i},w_1,\dots,w_{i-1}\}\in{X_\mathbf{u}\choose k-1}:\{w_1,\dots,w_{i-1}\}\notin \bigcap_{j=1}^iN_{u_j,\mathbf v}\right\} \subset Q.$$

We can fully specify $G$ via the following choices.

* We choose $u_1,\dots,u_i$. There are at most ${n \choose i}$ ways to do this.

* We choose $B$. There are at most $2^{n\choose k-i}$ possibilities.

* We then choose $\bigcap_{j=1}^iN_{u_j,\mathbf v}$ for every $\mathbf v\in B$. Since every $\mathbf v\in B$ has $|\bigcap_{j=1}^iN_{u_j,\mathbf v}|<\theta_in^{i-1}$, the number of such choices is bounded above by
$$\left(\sum_{t=1}^{\theta_in^{i-1}}{{n\choose i-1}\choose t}\right)^{|B|}\leq\exp_2\left[O_k(\theta_i\log(1/\theta_i)){n\choose i-1}{n\choose k-i}\right].$$

* We choose the monotone clauses involving some $u_j$. Since $|B|>(\beta_i-\theta_i)n^{k-i}$ and $|\bigcap_{j=1}^iN_{u_j,\mathbf v}|<\theta_in^{i-1}$ for every $\mathbf v\in B$,  after specifying $B$ and $\bigcap_{j=1}^iN_{u_j,\mathbf v}$ for every $\mathbf v\in B$, we know at least
$${k-1\choose i-1}^{-1} (\beta_i-\theta_i)n^{k-i} \left({|X_\mathbf{u}\setminus \{v_1,\dots,v_{k-i}\}|\choose i-1}-\theta_in^{i-1}\right)$$
$(k-1)$-subsets of variables that belong to $Q$. Hence there are at most

\begin{multline*}
\exp_2\left[i{n-1\choose k-1}-(i-\log(2^i-1)){k-1\choose i-1}^{-1}(\beta_i-\theta_i)n^{k-i} \left({n-1-(k-i)\choose i-1}-\theta_in^{i-1}\right)\right]
\end{multline*}

ways of choosing the monotone clauses in $G$ that contain some $u_j$.

* We next select the clauses containing some $\ol u_j$ where all other literals are positive. Since $G\in \cI_{2,1}^*(n, \zeta,\beta_1)$, there can be at most $\beta_1n^{k-1}$ such clauses for every $u_j$, so the total number of choices is at most

$$\left(\sum_{t\leq \beta_1n^{k-1}}{{n-1\choose k-1}\choose t}\right)^i\leq\exp_2\sqb{O_k(\beta_1\log(1/\beta_1)){n-1\choose k-1}}.$$

* We then select the clauses containing some variable $u_j$ and some negative literal other than $\ol u_j$. By <ref>, we can choose them in at most $\exp_2\sqb{O_k(\zeta\log(1/\zeta)){n\choose k-1}}$ ways.

* Finally we select the clauses that do not involve any variable $u_j$. There are at most $|\cI(n-i)|$ choices.

Hence the number of possible $G$ is at most

\begin{align*}
&{n\choose i}\cdot 2^{n\choose k-i}\cdot |\cI(n-i)|\\
&\quad\cdot  \exp_2\left[O_k(\theta_i\log(1/\theta_i)){n\choose i-1}{n\choose k-i}+O_k(\zeta\log(1/\zeta)){n\choose k-1}+O_k(\beta_1\log(1/\beta_1)){n-1\choose k-1}\right.\\
&\left.\qquad\qquad+i{n-1\choose k-1}-(i-\log(2^i-1)){k-1\choose i-1}^{-1}(\beta_i-\theta_i)n^{k-i} \left({n-1-(k-i)\choose i-1}-\theta_in^{i-1}\right)\right]\\
&\overset{(*)}{\leq} \exp_2\left[i(1-c){n\choose k-1}\right]|\cI(n-i)|,
\end{align*}

where (*) is due to the fact that $\theta_i$, $\beta_1$ and $\zeta$ are all sufficiently smaller than $\beta_i$, and $c$ is small.

Combining the above two cases, we have

$$|\cI^*_{2,1}(n,\zeta,\beta_1)\setminus \cI_{2,i}^*(n, \zeta,\beta_1,\beta_i)|\leq \exp_2\sqb{(1-c){n\choose k}}+\exp_2\sqb{i(1-c){n\choose k-1}}|\cI(n-i)|$$

for sufficiently small $c > 0$.

§.§ Monotone neighborhoods of variables
We build the tools for bounding the number of formulae in $\cI_2^*(n, \zeta,\vec\beta)$ having a large number of clauses containing either $k-1$ or $k$ negative literals.
Here we consider the size of the “monotone neighborhoods” of variable $u$ and the intersections of these neighborhoods, an idea we make more precise below.

For every $u\in X$, let $Z_{u} = \{\{v_1, \ldots v_{k-1}\} \in \binom{X}{k-1} \mid uv_1\cdots v_{k-1} \in G\}$, i.e., those $(k-1)$-subsets of variables that form a monotone clause with $u$. Let $\overline{Z_u} = {X \backslash \{u\} \choose k-1} \backslash Z_u$, i.e., those $(k-1)$-subsets of variables that do not form a monotone clause with $u$. Let

\begin{align*}
\cI_3^*(n, \zeta, \vec\beta) &=\left\{G \in \cI_2^*(n, \zeta, \vec\beta) : \forall u_1, u_2, \ldots, u_k \in X,\,\right. \\
&\left.\qquad|Z_{u_1} \cap \cdots \cap Z_{u_{k-1}} \cap Z_{u_k}|, |Z_{u_1} \cap \cdots \cap Z_{u_{k-1}} \cap \overline{Z_{u_k}}|,|Z_{u_1} \cap \cdots \cap \overline{Z_{u_{k-1}}} \cap \overline{Z_{u_k}}|,\right. \\
&\left.\qquad\qquad\dots,|\overline{Z_{u_1}} \cap \cdots \cap \overline{Z_{u_{k-1}}} \cap \overline{Z_{u_k}} | \ge \frac{1}{2^{k+1}} {n-k \choose k-1} \right\}.
\end{align*}

For all $\vec \beta=(\beta_1,\dots,\beta_{k-2}) > 0$ with $\beta_1$ sufficiently small, there exist $\zeta, c > 0$ such that

$$|\cI_2^*(n, \zeta, \vec\beta) \backslash \cI_3^*(n, \zeta, \vec\beta)| \le \exp_2\left[k(1-c){n\choose k-1}\right]|\cI(n-k)|.$$

Fix $\vec \beta > 0$ with $\beta_1$ sufficiently small. Take $\zeta>0$ sufficiently smaller than $\beta_1$, and  $c=c(\beta_1,\zeta)>0$. To specify some $G\in\cI_2^*(n, \zeta, \vec\beta) \backslash \cI_3^*(n, \zeta, \vec\beta)$, it suffices to pick the following.

* We choose $u_1, \ldots, u_k$ violating the condition for $\cI_3^*(n, \zeta, \vec\beta)$, which we can do in at most ${n \choose k}$ ways.

* We choose the non-monotone clauses that include at least one of $u_1, \ldots, u_k$. For every $u_j$, since there are at most $\beta_1n^{k-1} + 2(k-1)\zeta n^{k-1}$ such clauses, we choose from at most

\begin{align*}
&\sum_{t \le (\beta_1 + 2(k-1)\zeta)n^{k-1}} {(2^k - 1){ n - 1 \choose k-1} \choose t} \\
&\le \exp_2 \left[  H \left( \frac{(\beta_1 + 2(k-1)\zeta) n^{k-1}}{(2^k - 1){n-1 \choose k-1}} \right) \cdot (2^k - 1) {n-1 \choose k-1} \right]
\end{align*}
This gives in total at most

$$\exp_2\left[ O_k((\zeta+\beta_1)\log(1/(\zeta+\beta_1))){n \choose k-1}\right]$$

* We pick the monotone clauses involving at least one of $u_1, \ldots, u_k$. Note that there are $2^{O(n^{k-2})}$ choices of subsets of clauses involving at least two of $u_1,\ldots, u_k$. Meanwhile, the number of monotone clauses involving exactly $1$ of $u_1, \ldots u_k$ is bounded by the number of choices of an ordered partition of ${X \backslash \{ u_1, \ldots, u_k\} \choose k-1}$ into $2^k$ parts (i.e., choosing membership in $Z_{u_i}$ or $\overline{Z_{u_i}}$ for every $(k-1)$-subset of variables), at least one of which has size less than $\frac{1}{2^{k+1}} {n-k \choose k-1}$. Note that for $N = {n-k \choose k-1}$ and $K = 2^k$, there are $\binom{N}{< \frac{1}{2^{k+1}} N} \le 2^{H\left(\frac{1}{2^{k+1}}\right) \cdot N}$ to choose $Z_{u_i}$ to be small for any fixed $i$ and $(K - 1)^N$ ways to choose membership for the remaining $u_j$ for $j \neq i$.
The total number of choices is bounded above by
$$2^k \exp_2\left[\left(H \left(\frac{1}{2^{k+1}}\right) + \log_2 (2^k - 1) \right) {n-k \choose k-1}  \right].$$

* Finally, we choose the clauses not involving any of $u_1, \ldots, u_k$. We can do this in at most $|\cI(n-k)|$ ways.