Deterministic 3SUM in $O(n^{1.962})$ word-RAM steps

For every nonnegative integer $\kappa$, there exist a finite deterministic program $P$, nonnegative integers $b$ and $K$, and a function $T:\mathbb N\to\mathbb N$, all chosen independently of the input size, input values, and word width, such that $T(n)^{500}\le K n^{981}$ for every integer $n\ge 2$; the exponents $981$ and $500$ come from the exact rational number $1.962=981/500$. These choices must also satisfy the following condition: for every nonnegative integer $n$, every sequence of integers $x_0,\ldots,x_{n-1}$ with $|x_i|\le n^\kappa$ for every $0\le i<n$, and every nonnegative integer word width $W$ with $W\ge b(\ell(n)+1)$, where $\ell(0)=0$ and $\ell(n)=\lfloor\log_2 n\rfloor$ for $n\ge1$, running $P$ from program position $0$ on the memory specified below must halt within $T(n)$ steps with some Boolean verdict $v$ and some final memory $m$, with $v=\mathrm{true}$ if and only if there exist indices $i,j,k\in\{0,\ldots,n-1\}$ such that $i\ne j$, $j\ne k$, $i\ne k$, and $x_i+x_j+x_k=0$ as an equality of the original integers. The indices must be distinct, but the corresponding integer values need not be distinct. Memory has a cell at every integer address, each containing a $W$-bit word, represented by a residue in $\{0,\ldots,2^W-1\}$. Initially cell $0$ contains $n$ reduced modulo $2^W$, cell $i+1$ contains $x_i$ reduced modulo $2^W$ for every $0\le i<n$, and every other cell, including every negative-addressed cell, contains zero. For $W>0$, a word with residue $u$ has signed value $u$ when $u<2^{W-1}$ and $u-2^W$ otherwise; for $W=0$ the only word has residue and signed value zero. The instructions available to $P$ are exactly the following: write the word obtained from the integer $1$ into a fixed cell; add, subtract, or multiply the words in two fixed cells and write the result, reduced modulo $2^W$, into a fixed cell; read the signed value of the word in a fixed cell as an address and copy the word at that address into a fixed cell; read the signed value of the word in a fixed cell as an address and copy the word from another fixed cell to that address; jump to a fixed nonnegative program position if the signed value in a fixed cell is negative, and otherwise proceed to the next position; accept; or reject. Every fixed cell address appearing in an instruction is an integer. Every writing instruction proceeds to the next program position after updating only its destination cell. Acceptance returns verdict $\mathrm{true}$ with the current memory, and rejection returns verdict $\mathrm{false}$ with the current memory. Program positions are numbered starting at $0$, and attempting a position outside the finite program executes a rejection. Every executed instruction consumes one step, including an accept, reject, or rejection at an out-of-range position; an execution with zero available steps returns no verdict. There is no additional output requirement on the final memory. Correctness and halting are required also for $n=0$ and $n=1$, although the displayed growth bound constrains only $n\ge2$; for each $n<3$, the required verdict is $\mathrm{false}$. The input bound is vacuous when $n=0$, and $n^0=1$, including when $n=0$. There are no separate positivity assumptions on $b$ or $K$, and the quantification over widths includes $W=0$ whenever it satisfies the stated width inequality.