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