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

Claim. The theorem takes no hypotheses and no parameters. It says that one deterministic multitape Turing machine multiplies $n$-bit integers exactly, for every $n \ge 1$, and that for all sufficiently large $n$ it does so within

$$c \cdot n \cdot (\lg n)^{\,1-\kappa}\ \text{steps}, \qquad \kappa = \frac{1}{2^{182}} = 2^{-182} \approx 1.6 \times 10^{-55},$$

where $c > 0$ is a constant. The exponent is the real number $1 - 2^{-182}$, which is strictly between $0$ and $1$. Here $\lg n = \max(\lceil \log_2 n \rceil, 1)$ for natural $n$, where $\lceil \log_2 n\rceil$ is the least $j \ge 0$ with $n \le 2^j$. So $\lg 1 = \lg 2 = 1$, $\lg 3 = \lg 4 = 2$, and $\lg n \ge 1$ always, which means the real power is always of a base $\ge 1$.

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

• A finite alphabet $\Sigma$ containing five pairwise distinct symbols: a blank $\square$, a start marker $\triangleright$, bit symbols $\mathtt 0, \mathtt 1$, and a separator $\#$.
• A finite state set $K$ with a start state $q_{\mathrm{start}}$ and a halting state $q_{\mathrm{halt}} \ne q_{\mathrm{start}}$.
• A number of tapes $k \ge 2$. Tape $0$ is the input tape, tape $1$ is the output tape, and any others are work tapes. Each tape has cells indexed by $0,1,2,\dots$, and each tape has one head.
• A transition function $\delta : K \times \Sigma^k \to K \times (\Sigma \times \{\leftarrow, -, \rightarrow\})^k$.

The transition function must satisfy four conditions:

1. If a head scans $\triangleright$, it writes $\triangleright$ back and does not move left.
2. $\triangleright$ is never written on a cell that does not already hold it.
3. $\delta(q_{\mathrm{halt}}, a) = (q_{\mathrm{halt}}, (a_i, -)_i)$, so a halted configuration never changes.
4. The symbol written on tape $0$ always equals the symbol scanned there, so the input tape is read-only.

A configuration consists of a state, the contents of every tape (a function from cell indices to $\Sigma$) and the head positions. One step reads the scanned symbols $a$ and applies $\delta(q,a)=(q',(\sigma_i,d_i)_i)$: it overwrites the scanned cell of each tape $i$ with $\sigma_i$, moves head $i$ by $d_i$, and enters state $q'$. A left move from cell $0$ would truncate to $0$, but condition 1 rules this out because cell $0$ holds $\triangleright$.

Inputs and outputs. For bit strings $x, y$, the initial configuration on input $x\#y$ is as follows:

• The state is $q_{\mathrm{start}}$.
• The input tape holds $\triangleright\, x\, \#\, y\, \square\square\cdots$. Each bit is written with $\mathtt 0$ or $\mathtt 1$, and the first bit of each string comes first.
• Every other tape holds $\triangleright\,\square\square\cdots$.
• All heads are on cell $0$.

"$M$ halts with output $w$ at time $t$" means two things. After exactly $t$ steps the state is $q_{\mathrm{halt}}$. Also, the whole output tape (tape $1$) equals $\triangleright\, w\, \square\square\cdots$: $\triangleright$ in cell $0$, the bits of $w$ in cells $1,\dots,|w|$, and blanks in every later cell. Halted configurations are frozen, so this holds at some $t \le T$ exactly when $M$ halts within $T$ steps with that output. The work tapes, the input tape's contents beyond the read-only constraint, and the final head positions are unconstrained.

For $x = x_1\cdots x_m$, $\mathrm{val}(x) = \sum_i x_i 2^{m-i}$, with the most significant bit first and $\mathrm{val}(\text{empty}) = 0$. The string $\mathrm{bin}_{2n}(z)$ is the length-$2n$ string whose $i$-th symbol ($i = 0,\dots,2n-1$) is bit $2n-1-i$ of $z$. This is $z$ in binary, most significant bit first, left-padded with zeros to exactly $2n$ bits.

Multiplying in time $T$. "$M$ multiplies at size $n$ within $T$" (with $T$ real) means: for all bit strings $x, y$ that both have length exactly $n$, there is a natural number $t \le T$ such that $M$ on input $x\#y$ halts at time $t$ with output $\mathrm{bin}_{2n}(\mathrm{val}(x)\cdot \mathrm{val}(y))$. Leading zeros are allowed in $x$ and $y$. Inputs of unequal lengths are never considered.

Full unfolded statement. There exists a machine $M$ as above such that:

1. Correctness. For every natural $n \ge 1$ there is some real $T$ such that $M$ multiplies at size $n$ within $T$. This amounts to: on every pair of $n$-bit inputs, $M$ halts with the correct $2n$-bit product.
2. Time bound. There exist a real $c > 0$ and a natural number $n_0$ such that for every natural $n$ with $n \ge n_0$ and $n \ge 1$, $M$ multiplies at size $n$ within the real bound

$$c \cdot n \cdot (\lg n)^{1 - 2^{-182}}.$$

For each such $n$ and every pair of $n$-bit inputs, the number of steps $t$ satisfies $t \le c\, n\, (\lg n)^{1-2^{-182}}$ as real numbers.

The time bound is required only for $n \ge \max(n_0, 1)$. Below that threshold only correctness with some finite step count is required. The constant $c$ and the threshold $n_0$ may depend on $M$ but not on $n$ or on the inputs. The machine itself is one fixed machine for all $n$: its number of tapes, alphabet and state set are fixed.