Colkitt — multiplication in time $O(n(\lg n)^{1-\kappa})$, $\kappa=2^{-30}$

Statement. This theorem has no hypotheses and no free variables. It says that $\kappa = 2^{-30}$ satisfies the property $\mathrm{KappaBound}(\kappa)$. Here the value $\tfrac{1}{2^{30}}$ is an exact real number, not a truncated natural-number quotient. Unfolding all of the definitions, the claim is the following.

There exists a deterministic multitape Turing machine $M$ (in the model described below) such that:

1. Correct and halting for every input length $n \ge 1$. For every $n \ge 1$ there is some real number $T$ such that $M$ multiplies $n$-bit integers within $T$ steps.
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$, the machine $M$ multiplies $n$-bit integers within

$$c \cdot n \cdot \bigl(\operatorname{lg} n\bigr)^{\,1 - 2^{-30}}$$

steps.

The exponent $1 - 2^{-30} = 1 - \tfrac{1}{1073741824}$ is a real number, and the power is the real power function. Its base is $\operatorname{lg} n = \max\bigl(\lceil \log_2 n \rceil, 1\bigr)$, where $\lceil \log_2 n\rceil$ is the least $m \in \mathbb{N}$ with $n \le 2^m$. So $\operatorname{lg} 1 = \operatorname{lg} 2 = 1$, $\operatorname{lg} 3 = \operatorname{lg} 4 = 2$, and so on. The base is always at least $1$, so the power is never applied to $0$ or to a negative number. The case $n = 0$ is excluded from both clauses. The same machine $M$, constant $c$ and threshold $n_0$ must work for all $n$. Neither $M$ nor $c$ nor $n_0$ may depend on $n$.

"Multiplies $n$-bit integers within $T$ steps." For a real number $T$, this means the following. For all bit strings $x, y \in \{0,1\}^n$, both of length exactly $n$ and with leading zeros allowed, there is a natural number $t$ with $t \le T$ such that two things hold after exactly $t$ steps from the initial configuration on input $x\#y$:

• the machine is in the state $\mathrm{HALT}$;
• the output tape (tape $1$) holds exactly

$$\triangleright\ b_1 b_2 \cdots b_{2n}\ \square\ \square\ \cdots$$

Here $b_1 \cdots b_{2n} = \operatorname{bin}_{2n}\bigl(\operatorname{val}(x)\cdot\operatorname{val}(y)\bigr)$, each bit is written as the machine's symbol $0$ or $1$, and every cell after position $2n$ is blank.

The two functions used here are defined as follows.

• $\operatorname{val}(x_1\cdots x_m) = \sum_i x_i 2^{m-i}$ reads a bit string as a binary number, most significant bit first, with $\operatorname{val}(\text{empty}) = 0$.
• $\operatorname{bin}_{k}(z)$ is the list of the $k$ low-order bits of $z$, most significant first: its $i$-th entry ($i = 0,\dots,k-1$) is bit number $k-1-i$ of $z$. Since $\operatorname{val}(x)\operatorname{val}(y) < 2^{2n}$, this is the full product written with exactly $2n$ bits, padded with leading zeros.

Nothing is required of the work tapes, the head positions, or the input tape's final contents. Because $\mathrm{HALT}$ freezes the configuration (see below), "some $t \le T$" is the same as "halts with this output after at most $T$ steps". If $T < 0$, no $t$ qualifies.

The machine model. A machine $M$ consists of the following data.

• Alphabet. An arbitrary finite alphabet $\Sigma$ with five pairwise distinct named symbols: blank $\square$, start marker $\triangleright$, $0$, $1$ and separator $\#$. It may contain other symbols as well.
• States. An arbitrary finite state set $K$ with a start state $\mathrm{START}$ and a halting state $\mathrm{HALT} \ne \mathrm{START}$.
• Tapes. A number of tapes $k \ge 2$. Tape $0$ is the input tape, tape $1$ is the output tape, and the rest are work tapes. Each tape has cells indexed by $0,1,2,\dots$.
• Transition function. A function $\delta : K \times \Sigma^k \to K \times (\Sigma \times \{\leftarrow, -, \rightarrow\})^k$.

The transition function must satisfy four conditions:

• Start marker is kept. Whenever tape $i$ scans $\triangleright$, that tape writes $\triangleright$ back and does not move left.
• Start marker is never written elsewhere. Whenever tape $i$ scans a symbol other than $\triangleright$, it does not write $\triangleright$.
• HALT is frozen. $\delta(\mathrm{HALT}, a) = (\mathrm{HALT}, (a_i, -)_i)$ for every $a$, so once halted, the configuration never changes.
• Input tape is read-only. Tape $0$ always writes back the symbol it scans.

A configuration consists of the current state, the contents of every tape, and the position of every head. One step works as follows. Read the scanned symbols $a$ and compute $\delta(q, a) = (q', (\sigma_i, d_i)_i)$. Then every tape $i$ overwrites its scanned cell with $\sigma_i$ and moves its head according to $d_i$; a left move from position $p$ goes to $p-1$, truncated at $0$. Finally the state becomes $q'$.

On input $x\#y$, the initial configuration is:

• the state is $\mathrm{START}$;
• the input tape holds $\triangleright\, x_1 \cdots x_n\, \#\, y_1 \cdots y_n\, \square\,\square\cdots$, with bits encoded as the symbols $0$ and $1$;
• every other tape holds $\triangleright\,\square\,\square\cdots$;
• every head is on cell $0$.

The running time counted is the number $t$ of applications of this step map.