Corollary 5.5 — $\mathsf T(n)<\frac{1728}{d-1/2}\mathsf T(3rp)+O(1)$ for the recursive multiplication algorithm

Corollary 5.5 of Harvey–van der Hoeven. Fix a dimension parameter $d\ge2$ and put $n_0=2^{d^{12}}$. For $n\ge n_0$, the parameters of §5.1 are:

• $b=\lceil\log_2 n\rceil$ and $p=6b$;
• $T$, the unique power of two with $4n/b\le T<8n/b$;
• $r$, the unique power of two with $T^{1/d}\le r<2T^{1/d}$.

There is a deterministic multitape Turing machine $M$, correct on all $n$-bit inputs for every $n\ge1$, with worst-case running time $\mathsf M(n)$, and a constant $A$, such that for every $n\ge n_0$, with $\mathsf T(n):=\mathsf M(n)/(n\log n)$,

Here $\log$ is the natural logarithm. Taking $d=1729$, the factor is below $0.9998$, and an induction on $n$ then gives $\mathsf T(n)=O(1)$, that is, Theorem 1.1, $\mathsf M(n)=O(n\log n)$. In the paper this corollary follows from Proposition 5.4, $\mathsf M(n)<\frac{12T}{r}\mathsf M(3rp)+O(n\log n)$, the recursive step of the algorithm.

Formalization Note The machine model is IntMul_MultitapeModel. $\mathsf M(n)$ is $\inf\{\tau:\mathrm{MultipliesAt}(M,n,\tau)\}$, which is exactly $M$'s worst-case halting time on pairs of $n$-bit inputs. The parameters $b,p,T,r$ are universally quantified under their defining conditions, and these conditions determine them uniquely. The paper's $\mathsf M$ is the running time of its specific algorithm. The statement asserts the existence of a correct machine satisfying the recurrence, which is what the paper establishes for that algorithm.