Jain round six — multiplication in time $O(n(\lg n)^{1-\kappa})$, $\kappa=3666565558019/10^{17}>2^{-15}$

Claim. There is a deterministic multitape Turing machine that multiplies $n$-bit integers in time $O\big(n\,(\lg n)^{1-\kappa}\big)$. Here $\kappa$ is the exact real number

$$\kappa \;=\; \frac{3666565558019}{10^{17}} \;=\; 0.00003666565558019 \;\approx\; 3.6666\times 10^{-5},$$

so the exponent is exactly $1-\kappa = 0.99996333434441981$. The power $(\lg n)^{1-\kappa}$ is the real power function, and it is always applied to a base $\ge 1$. The theorem has no hypotheses or free variables. All of its content sits in the definitions below, which are unfolded here.

Logarithm. For a natural number $n$, define $\lg n = \max(\lceil \log_2 n\rceil, 1)$. Here $\lceil\log_2 n\rceil$ is the least $j\in\mathbb N$ with $n \le 2^j$, which is $0$ for $n\in\{0,1\}$. So $\lg 1 = \lg 2 = 1$, $\lg 3=\lg 4 = 2$, $\lg 5 = 3$, and so on. Always $\lg n \ge 1$. The bounding function is

$$g(n) \;=\; n\cdot(\lg n)^{1-\kappa}\qquad(n\in\mathbb N,\ g(n)\in\mathbb R).$$

Machine model. A machine $M$ consists of the following data:

• a finite alphabet $\Sigma$ containing five pairwise distinct symbols: blank $\square$, start symbol $\triangleright$, and the symbols $0$, $1$ and $\#$;
• a finite state set $K$ with a start state $q_{\mathrm{start}}$ and a halting state $q_{\mathrm{halt}}\neq q_{\mathrm{start}}$;
• a number of tapes $k\ge 2$, where tape $0$ is the input tape, tape $1$ is the output tape, and the rest are work tapes;
• a transition function $\delta: K\times\Sigma^k\to K\times(\Sigma\times\{\leftarrow,-,\rightarrow\})^k$.

The transition function must satisfy four constraints:

1. Start symbol. Whenever tape $i$ scans $\triangleright$, it writes $\triangleright$ back and does not move left.
2. No new start symbols. Whenever tape $i$ scans a symbol other than $\triangleright$, it does not write $\triangleright$.
3. Halting freezes. In state $q_{\mathrm{halt}}$, $\delta$ keeps the state $q_{\mathrm{halt}}$, rewrites every scanned symbol unchanged and moves no head. The configuration is therefore frozen from then on.
4. Read-only input. On tape $0$, the written symbol always equals the scanned symbol. The input head may still move.

A configuration consists of a state, a content function $\mathbb N\to\Sigma$ for each tape (cells $0,1,2,\dots$, infinite to the right only) and a head position in $\mathbb N$ for each tape. One step works as follows. Apply $\delta$ to the current state and the $k$ scanned symbols. Overwrite each scanned cell with the prescribed symbol. Move each head by $-1$, $0$ or $+1$. A move of $-1$ uses truncated subtraction, so position $0$ would stay at $0$, but constraint 1 already rules this out at cell $0$. Finally, adopt the new state.

Encodings. For a bit string $x=x_1\cdots x_m$, write $\mathrm{val}(x)=\sum_i x_i 2^{m-i}$, with the most significant bit first and $\mathrm{val}(\text{empty})=0$. For naturals $\ell, z$, the string $\mathrm{bin}_\ell(z)$ has length exactly $\ell$, and its $i$-th entry is bit $\ell-1-i$ of $z$, for $i=0,\dots,\ell-1$. So it is $z$ written in binary, most significant bit first, left-padded with zeros, and truncated to the low $\ell$ bits if $z\ge 2^\ell$.

On input $(x,y)$, the initial configuration is as follows:

• the state is $q_{\mathrm{start}}$;
• tape $0$ holds $\triangleright\, x\,\#\, y\,\square\square\cdots$, with each bit written as the symbol $0$ or $1$;
• every other tape holds $\triangleright\,\square\square\cdots$;
• all heads are on cell $0$.

"$M$ halts with output $w$ at time $t$" means this: after exactly $t$ steps from that configuration, the state is $q_{\mathrm{halt}}$, and the entire output tape equals $\triangleright\, w\,\square\square\cdots$. That is, cell $0$ holds $\triangleright$, cells $1,\dots,|w|$ hold the bits of $w$, and every later cell is blank. The work tapes and head positions are unconstrained. Because halting freezes the configuration, this is equivalent to $M$ having halted by step $t$ with that output tape.

Multiplying at a given length. For $n\in\mathbb N$ and a real number $T$, "$M$ multiplies at length $n$ within $T$" means the following. For all bit strings $x,y$ of length exactly $n$, leading zeros allowed, there is a $t\in\mathbb N$ with $t\le T$ such that $M$ on input $(x,y)$ halts at time $t$ with output

$$\mathrm{bin}_{2n}\big(\mathrm{val}(x)\cdot\mathrm{val}(y)\big).$$

Since $\mathrm{val}(x)\,\mathrm{val}(y)<2^{2n}$, this is the exact product, written with exactly $2n$ bits.

Full statement. There exists a machine $M$, as above, satisfying two conditions:

1. Correctness. For every $n\ge 1$ there is some real $T$ such that $M$ multiplies at length $n$ within $T$. In other words, $M$ correctly multiplies every pair of equal-length inputs of positive length, with no time constraint.
2. Time bound. There exist a real constant $c>0$ and a threshold $n_0\in\mathbb N$ such that, for every $n$ with $n\ge n_0$ and $n\ge 1$,

$$M \text{ multiplies at length } n \text{ within } c\cdot n\cdot(\lg n)^{1-\kappa}.$$

Edge cases and scope.

• Length $n=0$ is never constrained.
• Nothing is required on inputs where $x$ and $y$ have different lengths, or on tape contents not of the form $\triangleright\,x\#y$.
• There is no additive constant in the bound: for $n\ge n_0$, the step count itself must be at most $c\,g(n)$.
• The alphabet size, number of states and number of tapes $k\ge 2$ are arbitrary but fixed for the one machine $M$, which must work for all lengths $n$.