\section{Proofs for Section~\ref{sec:treewidth}: the treewidth transition}\label{app:treewidth}

\thminference*

\begin{proof}[Proof of \cref{thm:inference}]
\begin{steps}
\step{1}{1} Part (a) holds for $Z(\Phi)$.
\pf Each term of $Z(\Phi)$ is a product of $|\cF|$ entries below $2^b$, so $0\le Z(\Phi)<2^{n+b|\cF|}$. Apply
\cref{thm:sumproduct} over the counting ring $\Ring_{P,1}$ with $P=n+b|\cF|+1$. The hypotheses hold with
the given $s$, because $a\le s^{1/2}\le s^{9/10}$.

\step{1}{2} Part (a) holds for the marginals.
\pf $\Pr[x_i=1]=Z(\Phi\mid x_i=1)/Z(\Phi)$, where $\Phi\mid x_i=1$ restricts the tables that contain $x_i$.
A factor whose scope becomes empty is a constant (\cref{thm:sumproduct}). The size and $P$ do not grow.

\step{1}{3} Part (b) holds.
\pf Use the profile ring with $P=n+1$ and $\ell=b'|\cF|+1$, and give the factor $f$ with energy $E_f$ the
table $V^{E_f}$. The partition function is $\sum_jc_jV^j$, where $c_j$ counts the assignments of total energy
$j\le b'|\cF|<\ell$, and $c_j\le2^n<2^P$. The minimum energy is $\min\{j:c_j\ne0\}$, and the number of
minimizers is its coefficient. A minimizer follows by the self-reduction in the proof of \cref{thm:erm},
with $n+1$ computations.

\step{1}{4} For constant degree $\Delta$, arity, $b$ and $b'$, the time is $2^{O(n/\sqrt{\log n})}$.
\pf Then $|\cF|\le\|\Phi\|\le\Delta n$, so $s=O(n)$, and $s\ge n+1$ gives $\log s\ge\log n$.

\qedstep{1}{5}
\pf By \sref{1}{1}--\sref{1}{4}.
\end{steps}
\end{proof}

\corseparation*

\begin{proof}[Proof of \cref{cor:separation}]
\begin{steps}
\step{1}{1} Part (a) holds.
\pf The model has degree $\Delta$, arity $2$ and $0/1$ tables. Apply \cref{thm:inference}.
\step{1}{2} Part (b) holds.
\pf Every elimination order has induced width at least $\tw(G_n)$. So some elimination step multiplies
factors whose scopes together contain at least $\tw(G_n)+1$ variables, and tabulating their product takes
time $2^{\tw(G_n)}$. Likewise, every tree decomposition has a bag of size at least $\tw(G_n)+1$, and
junction-tree propagation tabulates a potential over each bag. Finally $\tw(G_n)=\Omega(n)$.
\step{1}{3} Part (c) holds.
\pf The substitution $x\mapsto\neg x$ maps the formula to the monotone $2$-CNF $\bigwedge_{uv}(x_u\vee x_v)$ of
degree $\Delta$, whose primal graph is $G_n$. It does not change the size of any structured DNNF.
Amarilli, Capelli, Monet and Senellart~\cite{ACMS20} prove that every structured DNNF for a monotone CNF
of bounded arity and degree has size $2^{\Omega(\tw)}$.
\qedstep{1}{4}
\pf By \sref{1}{1}--\sref{1}{3}.
\end{steps}
\end{proof}

\lemchain*

\begin{proof}[Proof of \cref{lem:chain}]
\begin{steps}
\step{1}{1} \Let $\Phi_F$ be built as follows. Each variable $z_i$ gets an initial copy $z_i^{(0)}$. Process
the literal occurrences in a fixed order, clause by clause. For the $t$-th literal of clause $j$, on the
variable $z_i$, create a fresh copy $z'_i$ and a chain variable $\zeta_{j,t}$. Add the factor
$\ind[z'_i=z_i^{\mathrm{cur}}]$, where $z_i^{\mathrm{cur}}$ is the most recent copy of $z_i$, and make $z'_i$ the
most recent copy. Add the factor $\ind[\zeta_{j,t}=\zeta_{j,t-1}\vee\lambda(z'_i)]$, where $\lambda$ applies the
sign of the literal. For each clause $j$ with $r_j$ literals, add a chain variable $\zeta_{j,0}$ with the
unary factor $\ind[\zeta_{j,0}=0]$, and the unary factor $\ind[\zeta_{j,r_j}=1]$.

\step{1}{2} $Z(\Phi_F)=\#F$.
\pf Fix $z\in\{0,1\}^N$. The equality factors force every copy of $z_i$ to equal $z_i$. The chain factors
force $\zeta_{j,t}$ to be the disjunction of the first $t$ literals of clause $j$. So $z$ has exactly one
extension with all factors equal to $1$ if $z$ satisfies $F$, and none otherwise. Variables of $F$ that
occur in no clause contribute a factor $2$ on both sides.

\step{1}{3} The factor graph $\Phi_F$ has arity and degree at most $3$ and at most $N+3L$ variables.
\pf A copy lies in at most two equality factors and one chain factor. A chain variable lies in at most
two factors. Every factor has at most $3$ variables. There are $N$ initial copies, $L$ further copies, and
$L+M\le2L$ chain variables.

\step{1}{4} The bags $B_{j,t}$, one for each occurrence $(j,t)$ in the processing order, form a path
decomposition of width at most $N+2$. Here $B_{j,t}$ contains the most recent copies of all $N$ variables
before the occurrence, the new copy $z'_i$, and $\zeta_{j,t-1}$ and $\zeta_{j,t}$.
\pf Each bag has at most $N+3$ elements. The equality and chain factors of $(j,t)$ lie in $B_{j,t}$, and
the unary factors of clause $j$ lie in its first and last bags. A copy occurs from its creation until it
is superseded, and $\zeta_{j,t}$ occurs only in $B_{j,t}$ and $B_{j,t+1}$, which are consecutive. So
every variable occurs in a contiguous run of bags.

\qedstep{1}{5}
\pf By \sref{1}{2}--\sref{1}{4}. The construction takes polynomial time.
\end{steps}
\end{proof}

\corinflen*

\begin{proof}[Proof of \cref{cor:inflen}]
\begin{steps}
\step{1}{1} \Let $F$ be a CNF of length $L$ in which every variable occurs, and \Let $\Phi_F$ be the factor
graph of \cref{lem:chain}. Then $\Phi_F$ has arity and degree at most $3$, at most $n\le4L$ variables,
treewidth at most $L+2$, and $Z(\Phi_F)>0$ if and only if $F$ is satisfiable.
\pf Variables that occur in no clause do not affect satisfiability, so we may delete them. Then $N\le L$,
and \cref{lem:chain} gives at most $N+3L\le4L$ variables and a path decomposition of width at most
$N+2\le L+2$. Also $Z(\Phi_F)=\#F$.
\step{1}{2} An algorithm that decides positivity in time $2^{\tw/(\log\tw)^{C+\theta}}\poly(n)$ decides $F$ in
time at most
\[
2^{(L+2)/(\log(L+2))^{C+\theta}}\cdot\poly(L),
\]
which is below $2^{L/(\log L)^C}$ for all large $L$.
\pf The function $x\mapsto x/(\log x)^{C+\theta}$ is increasing for large $x$, and $\tw\le L+2$. The reduction
takes polynomial time.
\step{1}{3} An algorithm that runs in time $2^{n/(\log n)^{C+\theta}}$ decides $F$ in time below $2^{L/(\log L)^C}$
for all large $L$.
\pf Here $n\le4L$, and $4L/(\log(4L))^{C+\theta}\le4L/(\log L)^{C+\theta}$, which is at most
$L/(\log L)^C-\log^2L$ for all large $L$.
\step{1}{4} If $C<1$, an algorithm in time $2^{O(\tw/\log\tw)}\poly(n)$ contradicts $\lenETH{C}$.
\pf Take $\theta=(1-C)/2$. For every constant $K$, we have $K\tw/\log\tw\le\tw/(\log\tw)^{C+\theta}+O(1)$, and
\sref{1}{2} applies.
\qedstep{1}{5}
\pf By \sref{1}{2}--\sref{1}{4}, each such algorithm contradicts $\lenETH{C}$.
\end{steps}
\end{proof}

\thminflower*

\begin{proof}[Proof of \cref{thm:inflower}]
\begin{steps}
\step{1}{1} \Let $c$ be the constant that \cref{hyp:sharpcnfseth} gives for $\gamma$, and \Let $F$ be a CNF
on $N\ge3$ variables with between $1$ and $N^c$ clauses, none of them tautological. Then $F$ has length
$L\le N^{c+1}$.
\pf Deleting tautological clauses changes neither the count nor the hypothesis, and a formula without
clauses is trivial. A non-tautological clause has at most $N$ literals.
\step{1}{2} \Let $r=\lceil\sqrt N\rceil$, and \Let $\Phi$ consist of $\Phi_F$ from \cref{lem:chain} and a disjoint
$r\times r$ grid of new variables with the all-ones factor on each grid edge. Then $Z(\Phi)=2^{r^2}\#F$, and
$\Phi$ has arity at most $3$ and degree at most $4$.
\pf All-ones factors leave the grid variables free. A grid vertex lies in at most $4$ edge factors, and
$\Phi_F$ has arity and degree at most $3$.
\step{1}{3} $\Phi$ has a path decomposition of width $t=N+2$, at most $5N^{c+1}\le5t^{c+1}$ variables, and
treewidth at least $\sqrt N\ge\sqrt t/2$.
\pf The $r\times r$ grid has treewidth and pathwidth $r$. Every bag of the decomposition of
\cref{lem:chain} has exactly $N+3$ elements: the $N$ current copies, the new copy and two chain
variables. Placing a path decomposition of the grid of width $r$ before it gives a path decomposition of
width $\max\{r,N+2\}=N+2$. The number of variables is at most $N+3L+r^2\le5N+3N^{c+1}\le5N^{c+1}$, because
$r^2\le4N$ and $N^c\ge3$. The treewidth is at least that of the grid, and $\sqrt N\ge\sqrt{N+2}/2$.
\step{1}{4} An algorithm in time $O(2^{(1-\gamma)t})$ would count the satisfying assignments of $F$ in time
$O(2^{(1-\gamma)N})$.
\pf It computes $Z(\Phi)$ in time $O(2^{(1-\gamma)(N+2)})=O(2^{(1-\gamma)N})$, and $\#F=Z(\Phi)/2^{r^2}$. The
reduction takes polynomial time.
\qedstep{1}{5}
\pf The algorithm of \sref{1}{4} contradicts \cref{hyp:sharpcnfseth}. For the decision version, $Z(\Phi)>0$ if
and only if $F$ is satisfiable, and \cref{hyp:cnfseth} applies in the same way. A MAP assignment of a $0/1$
model has weight $1$ if and only if $Z(\Phi)>0$.
\end{steps}
\end{proof}

\cortwtransition*

\begin{proof}[Proof of \cref{cor:twtransition}]
\begin{steps}
\step{1}{1} Part (a) holds.
\pf By \cref{thm:inference}, the time is $2^{O(n/\sqrt{\log n})}$. Because $n\ge\tw$, we have
$n/\sqrt{\log n}\le\tw(\log\tw)^{1/2-\theta}/\sqrt{\log\tw}=\tw(\log\tw)^{-\theta}=o(\tw)$.
Treewidth-based algorithms take time $2^{\Omega(\tw)}$ on the instances of \cref{cor:separation}, which
satisfy $n=O(\tw)$.
\step{1}{2} Part (b) holds.
\pf Let $c$ be as in \cref{thm:inflower} for $\gamma/2$. Its instances have degree at most $4$ and arity at
most $3$, and they satisfy $\sqrt t/2\le\tw\le t$ and $n\le5t^{c+1}\le5(4\tw^2)^{c+1}$, so $n\le\tw^{O(1)}$. An
algorithm in time $2^{(1-\gamma)\tw}\poly(n)$ would run there in time
$2^{(1-\gamma)t}\poly(t)=O(2^{(1-\gamma/2)t})$.
\qedstep{1}{3}
\pf By \sref{1}{1} and \sref{1}{2}.
\end{steps}
\end{proof}