Let $F(N,M)$ be the set of 3-SAT formula with $N$ variables and $M$ clauses. For a given formula $f\in F(N,M)$, we can ask for the set $s_f$ of truth assignments that satisfy $f$. (If $f$ is unsatisfiable, then $s_f$ will be the empty set.) Let's consider all the possible sets of truth assignments that we can specify by these formulas: $$S(N,M)=\{s_f | f\in F(N,M)\}$$ Finally, define the size of this set of sets as $$T(N,M) = |S(N,M)|$$
If we keep our variables fixed and keep adding clauses, we can express more complicated sets $s_f$. I had always assumed that for some sufficiently large $M$, I could express any set of assignments. In other words, if we define $$W(N)=\max_M T(N,M)$$ then I had assumed that $$W(N)=2^{2^N}$$
However, this is not true; there are forbidden sets of assignments that cannot be expressed by 3-SAT. This is easy to see-- each clause of a 3-SAT formula forbids 1/8th of the possible truth assignments, so we cannot have a set of assignments with at least one but less than 1/8th of the assignments forbidden. For example, there is no $f\in F(4,M)$ such that $|s_f|=15$, regardless of how big we make $M$. It follows that for $N>3$, $$W(N) < 2^{2^N}$$
But that might just be the tip of the iceberg in terms of "missing" sets. Define the size of the missing sets as: $$V(N) = 2^{2^N} - W(N)$$ Question: How does $V(N)$ grow with $N$? Or, equivalently, how does $W(N)$ grow with $N$?
(There's a second question about growth in $N$ and $M$ that I will ask separately.)
Edit #1: Although it's probably not helpful for the asymptotics, I enumerated $T(N,M)$ to convergence for small $N$. For $N<6$, the calculation is complete (i.e., the set does not grow by adding more clauses). Modulo programming bugs, I get:
| $T(N,M)$ | $M=0$ | $M=1$ | $M=2$ | $M=3$ | $M=4$ | $M=5$ | $M=6$ | $M=7$ | $M=8$ | $M=9$ | $M=10$ | $M=11$ | $M=12$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $N=1$ | 1 | 3 | 4 | ||||||||||
| $N=2$ | 1 | 9 | 16 | ||||||||||
| $N=3$ | 1 | 27 | 158 | 246 | 256 | ||||||||
| $N=4$ | 1 | 65 | 1,430 | 11,334 | 31,402 | 41,746 | 43,074 | 43,138 | 43,146 | ||||
| $N=5$ | 1 | 131 | 6,992 | 193,872 | 2,766,512 | 19,160,896 | 62,432,832 | 103,652,512 | 117,960,004 | 120,336,724 | 120,509,092 | 120,510,052 | 120,510,132 |
| $N=6$ | 1 | 233 | 24,084 | 1,459,044 | 56,328,304 | 1,382,172,232 | ? | ||||||
| $N=7$ | 1 | 379 | 66,586 | 7,224,786 | 538,779,796 | ? |
Note that $T(N,0)=1$ and $$T(N,1)=8{M \choose 3} + 4{M \choose 2} + 2{M\choose 1} + 1$$
For $N\leq 5$ we have convergence; the summarized results are:
| $W(N)$ | $2^{2^N}$ |
|---|---|
| $W(1)$=4 | 4 |
| $W(2)$=16 | 16 |
| $W(3)$=256 | 256 |
| $W(4)$=43,146 | 65,536 |
| $W(5)$=120,510,132 | 4,294,967,296 |
Edit #2: We can translate the "each clause forbids 1/8th of the truth assignments" observation above into an explicit bound using large deviation theory. Let $P$ be a Bernoulli distribution with probability 7/8 of zero and $H(P)$ be its entropy. Then, ignoring sub-exponential terms: $$V(N) \geq 2^{H(P)\times N} = 2^{0.543564443... \times N}$$
