Theorem 1.1 in the $\kappa$-framework — $\mathrm{KappaBound}(0)$: multiplication in time $O(n\lg n)$

Read-back of IntMul.HvdH.theorem_1_1_kappa_zero. The theorem has no hypotheses and no free variables; it asserts the proposition $\mathrm{KappaBound}(0)$. Unfolding, $\mathrm{KappaBound}(\kappa)$ is "multiplication is possible in time $O(g)$" for the bound function

where the power is the real power with real exponent. With $\kappa = 0$ the exponent is $1 - 0 = 1$, and $x^{1} = x$ for every real $x$, so the bound function is exactly

where $\lceil \log_2 n\rceil$ is the natural-number ceiling logarithm (the least $e$ with $n \le 2^e$; it equals $0$ for $n \le 1$). Thus $\lg 1 = 1$, $\lg 2 = 1$, $\lg 3 = \lg 4 = 2$, $\lg 5 = \dots = \lg 8 = 3$, and so on; in particular $\lg n \ge 1$ always, and $g(1) = 1$, $g(2) = 2$, $g(3) = 6$, $g(4) = 8$.

The statement. There exists a deterministic multitape Turing machine $M$ (model described below) such that both of the following hold:

1. Correctness / totality on every length $n \ge 1$: for every natural number $n \ge 1$ there is some real number $T$ such that $M$ multiplies $n$-bit integers within $T$ steps (definition below). Since $T$ is arbitrary, this just says: for every $n \ge 1$ and every pair of $n$-bit strings, $M$ halts after finitely many steps with the correct output.
2. Time bound: there exist a real constant $c > 0$ and a natural number $n_0$ such that for every natural number $n$ with $n \ge n_0$ and $n \ge 1$, $M$ multiplies $n$-bit integers within $c \cdot n \cdot \lg n$ steps.

Nothing is required for input length $n = 0$ (both clauses exclude it), and nothing is required of $M$ on inputs whose two halves have different lengths, or on any input not of the form described below. The constant $n_0$ may be $0$; the clause $n \ge 1$ is imposed separately. No explicit value of $c$ or $n_0$ is asserted.

"$M$ multiplies $n$-bit integers within $T$ steps" (for $T \in \mathbb{R}$) means: for all bit strings $x, y \in \{0,1\}^*$ with $|x| = n$ and $|y| = n$, there is a natural number $t$ with $t \le T$ (compared as reals) such that after exactly $t$ steps from the initial configuration on input $x\#y$:

• the state of $M$ is $\mathrm{HALT}$, and
• the output tape (tape $1$) holds exactly $\triangleright\, w_1 w_2 \cdots w_{2n}\, \square\, \square \cdots$, i.e. $\triangleright$ in cell $0$, the bit-symbols of $w$ in cells $1,\dots,2n$, and the blank $\square$ in every cell after $2n$, where

Here $\mathrm{val}(x) = \sum_{i=1}^{|x|} x_i\, 2^{|x|-i}$ reads $x$ as a binary numeral with the leftmost bit most significant ($\mathrm{val}$ of the empty string is $0$), and $\mathrm{bin}_{k}(z)$ is the list of $k$ bits whose $i$-th entry ($i = 0,\dots,k-1$) is bit number $k-1-i$ of $z$, i.e. the binary representation of $z$ most significant bit first, left-padded with zeros to length exactly $k$ (higher bits of $z$, if any, are dropped). Since $\mathrm{val}(x), \mathrm{val}(y) < 2^n$, the product is $< 2^{2n}$, so $w$ is exactly the product written in $2n$ bits with leading zeros. Inputs $x, y$ may have leading zeros (any $n$-bit strings, including all-zero ones). Bits are written as the symbols $0 \mapsto \mathtt{0}$, $1 \mapsto \mathtt{1}$. Because the halting state freezes the configuration, "halted with the right output at some $t \le T$" is the same as "halts within at most $T$ steps, with that output". The contents of the input tape and work tapes at halting are unconstrained.

The machine model. A machine $M$ consists of:

• a finite alphabet $\Sigma$ containing five pairwise distinct designated symbols: blank $\square$, start symbol $\triangleright$, bit symbols $\mathtt{0}, \mathtt{1}$, and separator $\#$ (it may contain arbitrarily many further symbols);
• a finite set of states $K$ with designated states $\mathrm{START} \ne \mathrm{HALT}$;
• a number of tapes $k \ge 2$ (any fixed $k$, chosen with the machine): tape $0$ is the input tape, tape $1$ the output tape, tapes $2,\dots,k-1$ work tapes; each tape has cells indexed by $0,1,2,\dots$;
• a transition function $\delta : K \times \Sigma^k \to K \times (\Sigma \times \{\leftarrow, -, \rightarrow\})^k$ satisfying: (i) whenever the scanned symbol on tape $i$ is $\triangleright$, it is rewritten as $\triangleright$ and the head on tape $i$ does not move left; (ii) whenever the scanned symbol on tape $i$ is not $\triangleright$, the symbol written there is not $\triangleright$; (iii) $\delta(\mathrm{HALT}, a) = (\mathrm{HALT}, (a_i, -)_i)$ for every scanned tuple $a$, so a halted configuration never changes; (iv) the symbol written on tape $0$ always equals the symbol scanned there (the input tape is read-only).

A configuration is a state, the contents of every cell of every tape, and a head position $\in \mathbb{N}$ on each tape. One step reads the scanned symbols $a = (a_i)_i$, computes $\delta(q, a) = (q', (\sigma_i, d_i)_i)$, overwrites each scanned cell with $\sigma_i$, moves each head left/stays/right according to $d_i$ (moving left from position $p$ gives $p - 1$ with truncated natural-number subtraction, though by (i) and the fact that $\triangleright$ sits only in cell $0$ a head never actually moves left from cell $0$), and sets the state to $q'$. The initial configuration on input $x\#y$ has state $\mathrm{START}$, every head on cell $0$, the input tape holding $\triangleright\, x_1\cdots x_n\, \#\, y_1 \cdots y_n\, \square\,\square\cdots$ (bit symbols for the bits), and every other tape holding $\triangleright\,\square\,\square\cdots$. Each step counts as one unit of time; there is no bound on the number of tapes, states, alphabet size, or space used, beyond their being fixed and finite for the single machine $M$, which must work uniformly for all $n$.

In summary, the theorem asserts: there is a single deterministic multitape Turing machine (in the above model) that, for every $n \ge 1$ and all $x, y \in \{0,1\}^n$, halts on input $x\#y$ with output tape exactly $\triangleright\,\mathrm{bin}_{2n}(\mathrm{val}(x)\mathrm{val}(y))\,\square\square\cdots$, and there are $c > 0$ and $n_0$ such that for all $n \ge \max(n_0, 1)$ it does so within at most $c \cdot n \cdot \max(\lceil \log_2 n\rceil, 1)$ steps on every such input — i.e. integer multiplication in time $O(n \lg n)$ on this model.