Skip to content

About

Conditional integer multiplication: kappa > 2^-15. Community proofs, exact certificates and reproducible audits; assumes the OpenAI #109 framework.

Resources

Contributing

Stars

0 stars

Watchers

0 watching

Forks

 
 

Repository files navigation

A sharper exponent for integer multiplication

Community research maintained by Douglas Colkitt — conditional on the original OpenAI #109 framework.

The reviewed community witness gives

$$ T(n)=O!\left(n(\log n)^{1-\kappa}\right),\qquad \boxed{\kappa=\frac{4123863984}{10^{14}} =4.123863984\times10^{-5}>2^{-15}}. $$

This uses the fixed finite-alphabet Turing-machine model with a fixed number of one-dimensional tapes in OpenAI's Integer multiplication below n log n. The saving is 6.10% above our previous PR #39 release, and still below 2^-14. These numbers compare asymptotic exponent savings, not practical running times.

Latest circuit contribution: Rohan Arun (@rohanarun), PR #49. This composes Chafik Boukhalfa's reordered exclusion sums and exact recovery, RaD / hipotures's alternating producers and physical compiler, and Rohan's weighted matching and order search. Their full dependency chain and AI-assistance disclosures remain credited in the source notices.

Proof and reproduction guide · Exact certificate · Maintainer review · Integration record

What changed

The community work combines recursive batching and partial-swap frames with semantic precision bounds, arbitrary-coordinate routing and bulk Gaussian resampling. Two-stage circuits, paid copied-center operations and improved contiguous blocks strengthen the finite networks. The latest increment reorders disjoint sums and retains more compatible carriers, with both local bases fixed and the entire physical circuit replayed exactly.

The selected bit network has m=575 and 177,284,805 roles. Its recursive saving is 4124034054/10^14; the unchanged complex network supplies 717/10^7. The assembly retains all seven strict exponent margins, including numerical, movement and normalization costs.

Also incorporated: Alejandro Zarzuelo Urdiales's Gaussian parity and finite tensor proofs (PR #45) and Ryan S's historical Lean certificates and circuit checks (PR #26). These strengthen verification within their stated scope; they do not change κ or formally verify the complete multiplication theorem.

Attribution

This is a community result. Principal incorporated contributions include:

  • Rohan Arun (@rohanarun): corner geometry, fixed-basis composition, weighted matching and the latest #49 circuit.
  • Chafik Boukhalfa (@chafreaky): exact data recovery, independent checkers and reordered exclusion sums (#43, #46, #48).
  • icekylinx: recursive batching, partial swaps, fixed projector profiles, copied retained centers and the selected complex construction.
  • Zhihao Chen (@jacklightChen): controlled bases, translated frames, semantic/bulk compatibility and two-stage integration.
  • RaD project (@hipotures): semantic precision, arbitrary-coordinate routing, phase-cell inversion, bulk resampling, alternating pair order and the independent physical role compiler (#41).
  • James Chang (@jamesyc): reversed two-stage geometry and exact controls.
  • Aurel Prosz (@Paureel) and Swapnil Jain: attributed two-stage development and the paid copied-stream endpoint construction.
  • Dominik Scholz (@DominikScholz): dimension, parameter and fixed-basis refinements.
  • eumemic: complex circuits, Gaussian resampling and source-frame work; Bortlesboat and dleen: aligned pairing, retained totals and sharing.
  • Alejandro Zarzuelo Urdiales (@alejandrozu): Gaussian parity, finite tensor execution proofs and mixed-center reference checks (#45).
  • Ryan S (@princezuda): historical Lean certificates, frame/movement lemmas and independent circuit checks (#26).

The full contribution record also credits parallel, incremental, superseded and pending work. Inclusion there does not claim incorporation or verification of every PR. Douglas Colkitt maintains the project and its original research, review and integration, with OpenAI Codex assistance. OpenAI's original manuscript and Harvey–van der Hoeven's analytic work retain their attribution. Contributor-specific AI disclosures remain in NOTICE.

Evidence and limits

The selected contribution is PR #49 at f95d2910e027495983b53cae1693cf535abf2569. The follow-up review accepts its increment conditionally on the retained PR #39 audit and original #109 framework. This is not a claim of full formal verification, independent human peer review, worldwide priority or optimality. No complete practical multiplication-machine implementation is supplied.

Validation includes fresh finite producers, exact rank profiles, full dirty workspace restoration, historical patch checks and an independent rational moment/assembly checker. Both formal submissions were built with their pinned Lean versions; their axiom audits accept only Lean's standard axioms. See the review receipts and combined integration record.

The earlier PR #39 release and 2^-30 checkpoint (1a74950) remain preserved, with all earlier certificates, proofs, patches and contributor notices.

Reproduce

Requires Python 3.11 or newer, Git, Make and a C++17 compiler with unsigned 128-bit integer support (tested with GCC and Clang). No third-party Python packages or network access are needed for the arithmetic/circuit verification. The separate formal targets require Lean and an initial toolchain/Mathlib download.

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

For the final witness and the independent arithmetic/source audit:

make copied-fixed-verify climbed-48-verify
make community-followup-check
make formal-verify

Allow several minutes and multiple gigabytes of memory for full producer rebuilds. See reproduction details.

Historical 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.

Patch Conditional saving Scope
frozen-154 2^-154 Original network and recurrence exponents
balanced-153 2^-153 Balanced assembly parameters
same-network-129 2^-129 Original network, sharper recurrence comparison
h46-111 2^-111 Smaller network, dyadic parameters
h46-109 2^-109 Rational recurrence saving, strict final margin
h46-108 2^-108 Variable stopping exponent
h46-rational 5.8e-33 Strongest supplied parameter-only witness
nonadjacent-layout Original parameters retained Routing proof and revised layout cost only
frozen-nonadjacent-107 2^-107 Direct routing, original network and recurrence exponents
h46-nonadjacent-78 2^-78 Direct routing with the h = 46 network
h46-nonadjacent-76 2^-76 Direct routing with tuned dimension and stopping parameters
h46-shared-side-75 2^-75 Stage-1/stage-3 side-role sharing, routing, and parameter tuning
h46-incidence-67 2^-67 Rectangle incidence circuits, full auxiliary sharing, routing, and parameter tuning
h46-dag-63 2^-63 Shared intermediate sums and reversible role allocation
h46-shared-point 13*2^-66 Cross-group sharing
h50-paired-59 2^-59 Paired sums, stopped guard and tighter Gaussian setup
compact-control-34 83/10^12 > 2^-34 Compact controls, complete reservations, local repair and separate complex arity
complex-compression-31 2^-31 Weighted complex circuits, binary phase frames and complete auxiliary sharing
ternary-30 2^-30 Ternary five-subset circuit, rational frames and fixed-alphabet interchange

Citation and license

Use CITATION.cff, cite the individual contributions used and include the repository version or commit. CONTRIBUTORS.md, NOTICE and source-specific manifests preserve the dependency credits.

The project is Apache-2.0. Bundled RaD sources retain their separate CC0 license and notices. The pinned original OpenAI manuscript remains unchanged under upstream/; its source hashes are in upstream/manifest.json. This project is not an official OpenAI release or endorsement.

About

Conditional integer multiplication: kappa > 2^-15. Community proofs, exact certificates and reproducible audits; assumes the OpenAI #109 framework.

Resources

Contributing

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages