SETH implies the Orthogonal Vectors Conjecture (deterministic word RAM)

SETH implies the Orthogonal Vectors Conjecture (Williams 2005), stated for deterministic algorithms on a concrete word RAM.

All notions are from the definition Def_WordRAM_Conjectures. An algorithm is a fixed finite word-RAM program, the same at every input size, whose word width is a constant multiple of the logarithm of the input magnitude. For SAT the width also gets $n$ extra bits. Its running time $t$ is the exact number of instructions executed before it halts with the correct answer bit.

1. SETH. For every $q\ge 2$ there is a clause width $k\ge 3$ such that no algorithm decides satisfiability of every $n$-variable $k$-CNF formula $F$ within $t$ steps, where $t^q\le C\,2^{(q-1)n}(L_F+1)^p$ for all $n\ge n_0$. Here $L_F$ is the encoding length of $F$, and $C>0$, $p$, $n_0$ are fixed constants.
2. OVC. For every $q\ge 2$ there is a $c\ge 1$ such that no algorithm decides, for every pair of lists of $n\ge2$ Boolean vectors of dimension $d\le c\lceil\log_2 n\rceil$, whether there is an orthogonal pair (one vector from each list) within $t$ steps, where $t^q\le C\,n^{2q-1}$ for all $n\ge n_0$, with fixed constants $C>0$ and $n_0$.

The theorem asserts

Equivalently: if for some $\varepsilon=1/q>0$ and every constant $c$, Orthogonal Vectors in dimension $c\log n$ could be solved in $O(n^{2-\varepsilon})$ word-RAM steps, then for every $k$, $k$-SAT could be solved in $O(2^{(1-\varepsilon)n}\operatorname{poly}(L))$ steps. The OV conjecture is the most common starting point for conditional quadratic lower bounds in P, such as for diameter, edit distance and LCS. This implication is what ties those bounds back to SETH.

Formalization Note Both hypotheses are the deterministic, exact-step versions in Def_WordRAM_Conjectures. Improvements are quantified as $\varepsilon=1/q$ and time bounds are raised to the $q$-th power to stay in $\mathbb N$. The statement is WordRAM.Conjectures.SETHImpliesOV with the definition unfolded.