Satisfiable and Unsatisfiable k-SAT formulae that violate the same number of constraints on many inputs

Question

I want to, for arbitrary $k$ and $n$, construct two $k$-SAT formulae, one satisfiable ($f$) and one unsatisfiable ($g$), such that there are $\Omega(2^{\alpha n})$ inputs $x$ where $f(x)=g(x)+c$ for any constant $c$. Here $f(x)$ or $g(x)$ is the number of clauses in $f$ or $g$ satisfied by $x$. For a simple and dumb example if $k=n=2$:

f = $(x_1 \lor x_2) \land (x_1 \lor \neg x_2) \land (\neg x_1 \lor x_2) \land ( x_1 \lor x_2)$,

g= $(x_1 \lor x_2) \land (x_1 \lor \neg x_2) \land (\neg x_1 \lor x_2) \land (\neg x_1 \lor \neg x_2)$,

Then

$f(00)=2, f(01)=3, f(10)=3, f(11)=4$,

$g(00)=3, g(01)=3, g(10)=3, g(11)=3$,

so with $c=0$ there are two inputs such that $f(x)=g(x)+c$.

When $k=n$ a similar construction gives $2^k-2=\Theta(2^n)$ inputs that agree, however, there are now an exponential number of clauses.

I am wondering if there is a smarter construction possible, where the number of clauses is polynomial in $n$ while the number of inputs that agree is exponential, or if there is some proof that this may never be the case?

---

The context for the question is to find a worst-case example in order to prove an interesting lower bound on the quantum query complexity of deciding k-SAT problems with access to an oracle in the form of equation 2 in https://arxiv.org/pdf/1411.4028

Answer 1

Let $f$ be any satisfiable $k$-CNF formula on $n$ variables, and define $g$ by

$$g = f \land \text{True} \land \text{True} \land \dots \land \text{True} \land \text{False}.$$

If there are $c$ copies of $\text{True}$, then $f,g$ satisfy your conditions for all $x$, and thus there are $\Omega(2^{\alpha n})$ such inputs.

---

If you don't want to allow $\text{False}$, replace $\dots \land \text{False}$ by $\dots \land (x_1) \land (\neg x_1)$ (two separate clauses), and get rid of one of the $\text{True}$'s. Then $f,g$ still satisfy your conditions.

---

If you don't want to allow repeated clauses, you can tweak this to meet that constraint as well:

Choose $\beta$ such that ${2\beta \choose \beta} \ge c$, and replace each $\text{True}$ in the definition of $g$ above by a different disjunction of $\beta$ of the last $2\beta$ variables. Then $f(x)=g(x) + c$ for all inputs $x$ such that at least $\beta+1$ of the last $2\beta$ variables are True. There are $2^{n-1}$ such inputs (since, by symmetry, half of all assignments to the last $2\beta$ variables satisfy the condition), and this is $\Omega(2^{\alpha n})$.