A sharper exponent for integer multiplication

Research draft by Douglas Colkitt — conditional on the underlying manuscript and the written extensions supplied here.

This draft improves OpenAI's Integer multiplication below n log n (result family #109). In its fixed finite-alphabet Turing-machine model with a fixed number of one-dimensional tapes, the strongest supplied witness is

$$ T(n)=O!\left(n(\log n)^{1-\kappa}\right),\qquad \boxed{\kappa=\frac{83}{10^{12}}=8.3\times10^{-11}>2^{-34}}. $$

The simpler kappa = 2^-34 is a corollary. The witness remains below 2^-33. It increases the exponent saving by approximately 47.85 million fold over our preceding published 2^-59 witness. The original manuscript uses 2^-182. These compare asymptotic exponents, not practical runtimes.

Read the compact-control proof note (PDF) · Review the combined source patch · Inspect the exact certificate · Review guide and dependencies

This is a research claim supported by written proofs and reproducible checks. The complete upstream theorem is assumed; the new arguments have not received independent mathematical review or formal verification.

What changed

The new construction moves compact control fields instead of entire spaced windows. For f selected axes, it replaces the layer's movement cost O(V*((f*K)^tau+1)) by

$$ O!\left(V\bigl((f\log p)^\tau+1\bigr)\right). $$

The proof reserves temporary fields from existing address coordinates, allows arbitrary initial temporary values, restores them exactly, and charges exceptional-address repair at every recursion node. The temporary ranges remain complete through padding and recursive row splitting.

Removing K^tau removes the restriction responsible for the preceding quadratic dependence on the finite-network saving. The bit network stays at h=50. The original complex network is separately instantiated at h=25, and a generalized stopping-depth guard completes the new parameter witness. This is a change to the movement construction and its proof, beyond parameter tuning of the preceding algorithm.

The exact minimum assembly margin is

$$ G_* = \frac{333833}{4\cdot10^{15}} = 8.345825\times10^{-11} > \kappa. $$

The remaining bottleneck is the complex layer's saving. With the fixed h=25 complex motif and retained Gaussian/leaf inequalities, the scoped ceiling is below 8.369598075e-11, hence below 2^-33. This is not a ceiling for other networks or integer multiplication in general.

Evidence and scope

The review guide identifies the new proof obligations and their tests. Current research status is authoritative when older notes describe superseded barriers or hypothetical witnesses. The earlier artifacts remain available and unchanged.

Reproduce

With Python 3.11 or newer, Git and Make, run from the repository root:

make verify
git diff --exit-code -- certificates patches

No third-party Python packages or network access are needed for these checks. They regenerate the certificates and patches, run the tests, verify upstream hashes, and check each patch against the pinned manuscript. The second command checks exact regeneration on a clean checkout.

With Tectonic installed, rebuild the latest note using:

make compact-note

The output is artifacts/compact-control-note.pdf. The first PDF build may download TeX resources. See reproducibility instructions for applying the combined patch in a disposable copy and building older notes. GitHub Actions runs the arithmetic and patch checks. Passing tests does not establish the complete multiplication theorem; this repository contains no full multiplication-machine implementation.

Earlier witnesses and independent patches

Each patch applies independently to the unmodified pinned source; they are alternatives, not a sequence to apply together. The result history records the earlier mechanisms and scoped ceilings.

Attribution, citation, and license

Author: Douglas Colkitt. Research, implementation and drafting were performed with assistance from OpenAI Codex. The compact-control proposal originated with a separate research agent; the supplied note develops its tape, layout, repair and assembly arguments. AI assistance is not independent review or endorsement by OpenAI. No priority or unrestricted optimality claim is made.

The original manuscript is by OpenAI, pinned at commit adc7f1241b42e322a6451854ab7e4b4c146bf78a. Source URLs and SHA-256 hashes are in upstream/manifest.json. Files under upstream/ remain unchanged; modifications are supplied as separate patches.

Use CITATION.cff and also cite the upstream manuscript. Until a release is archived, include the repository commit used. Licensed under Apache-2.0; see NOTICE and CONTRIBUTING.md.