\section{What satisfiability still supports}\label{sec:sat}

\Cref{thm:ldovlb,thm:curve,thm:parity} rest on \cref{hyp:ldov}, which no open hypothesis about satisfiability is
known to imply. This section asks what CNF-SETH gives instead. The answer depends on the clause exponent of the
hard formulas and on whether the threshold is measured by the spread or by the entry bound $B$.

\subsection{CNF-SETH in polylogarithmic dimension}\label{sec:cnfseth}

Williams' reduction turns CNF-SETH into hardness of $\OV$ in dimension $(\log n)^{O(1)}$. Without a gap,
the softmax must separate one orthogonal pair from $n$ pairs whose inner products are only one larger, so
every unit of inner product costs $\ln n$ in the logit.

\begin{restatable}[CNF-SETH, exact embedding]{proposition}{thmcnfseth}\label[proposition]{thm:cnfseth}
Assume \cref{hyp:cnfseth}. For every $\gamma\in(0,1)$ there is $C\ge1$ such that, with
$d=\lceil(\log n)^C\rceil$, the problem $\ATT(n,d,d\ln(16n),1/6)$ cannot be solved in time
$O(n^{2-\gamma})$. This holds already for $d_v=1$ and values in $\{0,1\}$.
\end{restatable}

The queries are $(-\lambda a,-11/10)$ with $\lambda=\lceil10\ln(14n)\rceil/10$, the keys are $(b,0)$ with value
$1$, and a dummy key $(0,1)$ has value $0$; the proof is in \cref{app:cnfseth}. This is the exact embedding of Gupta
et al.~\cite[Lemma~5.6]{GHSXY25} combined with Williams' reduction. The reductions of Keles, Wijewardena and
Hegde~\cite{KWH23}, proved for every $d=\omega(\log n)$, are exact as well and survive under CNF-SETH in dimension
$(\log n)^{O(1)}$, with the precision they need there (\cref{tab:ledger2}). In terms of the entry bound
of~\cite{AS23}, the instances of \cref{thm:cnfseth} can be written with $B=O(\sqrt{d\log n})$.

\subsection{Clause exponent below two}\label{sec:below-two}

The gap machinery of \cref{fact:chen} needs $\OV$ in dimension $O(\log n)$. Its engine, Rubinstein's
protocol (\cref{fact:rub}), works in every dimension $m$, but the instance grows by the factor $2^p$ for a
proof of $p\approx(m/s)\log s$ bits, and the dimension by the factor $2^{O(s\log s)}$ for Bob's message. With
$m=(2\log n)^{c_0}$ from Williams' reduction and $s\approx m\log m/(\gamma\log n)$, the first factor is at most
$n^{\gamma/8}$, and the second is then $n^{o(1)}$ exactly when $c_0<2$.

\begin{restatable}[Gap instances from MA protocols]{lemma}{lemmagap}\label[lemma]{lem:magap}
Let $m\ge s\ge2$ and $k\ge1$ be integers, and let $p$, $\rho$ and $\ell$ be the lengths of Merlin's proof, of
the coins and of Bob's message in the protocol of \cref{fact:rub} for $(m,s)$. There is a map from
instances $(A,B)$ of $\OV_{n,m}$ to $2^p$ instances of Boolean Max-IP, each with $n$ vectors per side in
dimension $2^{k(\rho+\ell)}$, such that with $T_k=2^{k\rho}$:
\begin{enumerate}[label=(\roman*)]
\item every inner product lies in $[0,T_k]$;
\item if $(A,B)$ has an orthogonal pair, some instance has a pair with inner product $T_k$;
\item otherwise every inner product is at most $2^{-k}T_k$.
\end{enumerate}
The map takes time $2^{p+k(\rho+\ell)}\,nk\poly(m)$.
\end{restatable}

\begin{restatable}[Clause exponent below two]{theorem}{thmbelowtwo}\label{thm:belowtwo}
Assume $\mathrm{CNF\text{-}SETH}_{c_0}$ for some $c_0<2$. For all $\gamma\in(0,1)$, $\theta\in(0,1]$ and
$\eps\in(0,1/2)$ there is $K\ge1$ such that $\ATT(n,d(n),(1+\theta)\ln n,\eps)$ with
$d(n)=\lceil2^{K(\log n)^{c_0-1}(\log\log n)^2}\rceil=n^{o(1)}$ cannot be solved in time $O(n^{2-\gamma})$. This holds
already for instances with $d_v=1$, values in $\{0,1\}$, and all logits in $[0,(1+\theta)\ln n]$.
\end{restatable}

So the lower bound of \cref{thm:ldovlb} at spread $(1+\theta)\ln n$ follows, in dimension $n^{o(1)}$ instead of
$O(\log n)$, from a hypothesis about satisfiability, provided the hard CNF formulas have $N^{c_0}$ clauses for
some $c_0<2$. Formulas with $O(N)$ clauses are easy~\cite[Proposition~6.1]{Li26}, so the relevant range is
$1<c_0<2$, where the question is open: \cite[Proposition~6.1]{Li26} is proved for linearly many clauses, and the
bound $2^{O(k^2N\log\log N/\sqrt{\log N})}$ of~\cite{Cla26} for $k$-CNF is trivial once $k=\omega((\log N)^{1/4})$. The
exponent $2$ in \cref{thm:belowtwo} is a limit of the reduction, not of its analysis (\cref{rem:forced}).

\begin{remark}[The exponent $2$]\label[remark]{rem:forced}
The construction of \cref{lem:magap} applies to every one-message MA protocol for disjointness with perfect
completeness and soundness $1/2$, such as that of \cref{fact:rub}: with $p$-bit proofs and $\ell$-bit messages it
gives $2^p$ instances of dimension at least $2^{\ell}$. Running such a protocol twice with independent coins and
letting Alice announce her decision gives a protocol with $c_M=p$ and $c_P=2\ell+1$ that computes $\DISJ_D$ with
error $1/4$, so $(p+1)(2\ell+1)\ge\alpha_0D$ by \cref{lem:klauck}. Polynomially many instances of \cref{lem:magap} of
dimension $n^{o(1)}$ therefore force $D=o(\log^2n)$, and Williams' instances with $D=\lceil(2\log n)^{c_0}\rceil$ reach polynomially many
instances of dimension $n^{o(1)}$ through this construction only if $c_0<2$.
\end{remark}

\subsection{A barrier for the bounded-entry threshold}\label{sec:barrier}

The reductions of \cref{thm:ldovlb,thm:curve,thm:cnfseth,thm:belowtwo}, and the reduction of~\cite{AS23}, which
composes Rubinstein's reduction from $\OV$ to approximate nearest neighbor with~\cite[Lemma~4.7]{AS23}, map each
vector separately to at most $2^p$ query or key vectors, one for each value of an index that the reduction
enumerates, and separate orthogonal from non-orthogonal pairs by a gap in the logits. We call such a map a gap
embedding.

\begin{definition}[Gap embedding]\label[definition]{def:gapemb}
Let $D,p\ge0$ and $d\ge1$ be integers and $\Delta>0$. A \emph{$(D,p,d,\Delta)$-gap embedding} consists of maps
$q,k:\{0,1\}^p\times\{0,1\}^D\to\R^d$ and $h:\{0,1\}^p\times\{0,1\}^D\to\R$ such that for all
$a,b\in\{0,1\}^D$:
\begin{enumerate}[label=(G\arabic*)]
\item if $\ip ab=0$, then $\ip{q(\mu,a)}{k(\mu,b)}\ge h(\mu,a)$ for some $\mu$;
\item if $\ip ab\ge1$, then $\ip{q(\mu,a)}{k(\mu,b)}\le h(\mu,a)-\Delta$ for all $\mu$.
\end{enumerate}
Its \emph{scale} is $\sigma=\max_{\mu,a}\|q(\mu,a)\|_2\cdot\max_{\mu,b}\|k(\mu,b)\|_2$.
\end{definition}

Reductions that make copies of the queries and of the keys independently are the special case in which the
index is a pair $\mu=(\mu_1,\mu_2)$, $q$ depends only on $\mu_1$ and $k$ only on $\mu_2$. The scale bounds every
logit, by the Cauchy--Schwarz inequality, and it is at most $d\cdot\max|q(\mu,a)_t|\cdot\max|k(\mu,b)_t|$; in the
normalization $\exp(QK^\top/d)$ with entries in $[-B,B]$ it is at most $B^2$. Building attention instances from a gap
embedding multiplies the number of queries and keys, or the number of attention calls, by at most $2^p$, and in the
product case by $2^{p_1}$ and $2^{p_2}$ with $p_1+p_2=p$; so subpolynomial blowup means $p=o(\log n)$ and polynomial
blowup means $p=O(\log n)$. The reductions of \cref{thm:ldovlb,thm:cnfseth,thm:belowtwo} and of~\cite{HAPTP26}, at
constant precision, have $\Delta\ge\ln n-O(1)$, because the keys above the threshold must outweigh the others; those
of \cref{thm:curve} have $\Delta\ge\alpha\ln n$, and the reduction of~\cite[Lemma~4.7]{AS23}, at precision $n^{-C_a}$, has
$e^{\Delta}>4n$, so that the $n$ far keys together stay below one near key. The counting reductions of
\cref{thm:parity} and~\cite[Theorem~5.7]{GHSXY25}, read with negated queries, have $\Delta=\ln(1+1/r)$ and are not
covered by the corollary below. The next theorem shows that a gap embedding with small scale is an efficient
Merlin--Arthur protocol for disjointness, so Klauck's lower bound~\cite{Kla03} applies.

\begin{restatable}[Barrier]{theorem}{thmbarrier}\label{thm:barrier}
There is an absolute constant $\alpha_2>0$ such that every $(D,p,d,\Delta)$-gap embedding with $D\ge1$ and
scale $\sigma$ satisfies $\Gamma=\sigma/\Delta\ge1/2$ and
\[
\Gamma^2\log(2+\Gamma)\ \ge\ \alpha_2\,\frac{D}{p+1}.
\]
\end{restatable}

In the protocol, Merlin names the copy $\mu$, and the players estimate $\ip{q(\mu,a)}{k(\mu,b)}$ from
$O(\Gamma^2)$ random-sign projections of $k(\mu,b)$, each sent with $O(\log(2+\Gamma))$ bits; the dimension $d$ does not
enter. \Cref{app:barrier} gives the proof.

\begin{corollary}\label[corollary]{cor:barrier}
Let $c_0>1$, $\delta_0>0$ and $D=\lceil(2\log n)^{c_0}\rceil$. For all large $n$, every $(D,p,d,\Delta)$-gap embedding with
$p=O(\log n)$ and $\Delta\ge\delta_0\ln n$ has scale $\sigma\ge\delta_0(\log n)^{(1+c_0)/2}/O(\sqrt{\log\log n})$, where the
$O$ depends on $c_0$ and on the constant in $p=O(\log n)$. If every copy $\mu$ is written in the normalization
of~\cite{AS23} with entries in $[-B,B]$, then $B\ge(\delta_0)^{1/2}(\log n)^{(1+c_0)/4}/O((\log\log n)^{1/4})$.
\end{corollary}

\begin{proof}
\Cref{thm:barrier} gives $\Gamma^2\log(2+\Gamma)\ge\alpha_2D/(p+1)=\Omega((\log n)^{c_0-1})$. If $\Gamma\ge(\log n)^{c_0}$
the claim holds; otherwise $\log(2+\Gamma)=O(\log\log n)$, so $\Gamma=\Omega((\log n)^{(c_0-1)/2}/\sqrt{\log\log n})$ and
$\sigma=\Gamma\Delta\ge\delta_0\Gamma\ln n$. For the entries, multiplying $q(\mu,\cdot)$ by $c_\mu>0$ and $k(\mu,\cdot)$ by
$1/c_\mu$ changes neither the logits nor (G1) and (G2), so the bound holds for the rescaled embedding; choosing
$c_\mu$ to equalize $\max_a\|q(\mu,a)\|_2$ and $\max_b\|k(\mu,b)\|_2$ makes its scale equal to the largest product of these
two maxima over $\mu$, which is at most $B^2$ in that normalization.
\end{proof}

\paragraph{The spread and the entry bound come apart.}
\Cref{thm:belowtwo,cor:barrier} together say that after the refutation the two forms of the threshold have
different bases. In terms of the spread, hardness at $(1+\theta)\ln n$ follows, in dimension $n^{o(1)}$, from
$\mathrm{CNF\text{-}SETH}_{c_0}$ for any $c_0<2$. In terms of the entry bound, gap embeddings with polynomial
blowup and gap $\Delta=\Omega(\log n)$ cannot derive the threshold $B=\Theta(\sqrt{\log n})$ of~\cite{AS23} from $\OV$
in dimension $(\log n)^{c_0}$ for any $c_0>1$: they need $B\ge(\log n)^{(1+c_0)/4-o(1)}$. The instances of
\cref{thm:belowtwo} are consistent with this. They reach spread $(1+\theta)\ln n$ through vectors with up to
$2^{O(s\log s)}$ nonzero coordinates, so their logits stay below $(1+\theta)\ln n$ while their scale, which
\cref{thm:barrier} bounds from below, is not limited by the spread. At $D=O(\log n)$ nothing is lost: \cref{rem:entries} attains scale $O(\log n)$. By
\cref{thm:barrier}, a gap embedding of $\OV$ in dimension $D$ with $p=O(\log n)$, $\Delta=\Theta(\log n)$ and scale
$O(\log n)$ exists only if $D=O(\log n)$. So for gap embeddings, the entry form of the threshold needs $\OV$ to be
hard in dimension $O(\log n)$, which is \cref{hyp:ldov}. The barrier constrains the scale, not the spread, and it
does not cover counting reductions with a small gap, adaptive reductions, or reductions from satisfiability that
do not pass through $\OV$.