Reducing #SAT to MAJ-SAT I once read in a paper: &quot;given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm.&quot;
What is the approach to this?
Emil Jeřábek's construction [Gill 1977, Simon 1975] works indeed. Assume the formula $A$ has the propositional variables $x = \langle x_1,..,x_n \rangle$ and $y$ is some fresh variable. We can then construct $B$ as a formula $(y \rightarrow A) \wedge (\neg y \rightarrow C)$ whereby the formula $C$ needs to be further specified.
For the formula $C$ we assume the threshold given binary as $s = \langle s_1,..,s_n \rangle$. We can encode the arithmetic comparison $s \leq x$ in binary form, which is the lexicographic order union equality: $\langle s_j,..,s_n \rangle \leq \langle x_j,..,x_n \rangle  := (\neg s_j \wedge x_j) \vee ((s_j \leftrightarrow x_j) \wedge \langle s_{j+1},..,s_n \rangle \leq \langle x_{j+1},..,x_n \rangle)$ for $j&lt;n$ and $(s_n \leq x_n) := (s_n \rightarrow x_n)$ otherwise.
So the formula $C$ will be just $s \leq x$. Now we have for the count of $B$:
$$|B| = |A| + |C| = |A| + 2^n-s$$
And therefore for the majority of $B$:
$$|B| \geq 2^n  \Leftrightarrow |A| \geq s$$
Since $\langle 0,..,0 \rangle \leq \langle x_j,..,x_n \rangle$ is trivially true, we can even construct $C$ gradually via binary search, and thus determine $|A| = s$ by calling $n$-times the majority oracle.