Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact integer multiplication with saving κ = 0.00363797977

Open
IntMul.Kappa.conditional_kappa_00363797977_pr7113

by Secousses · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinteger-multiplicationturing-machines

There exists one deterministic multitape Turing machine, with fixed finite alphabet and tape count, that correctly multiplies every pair of n-bit inputs for all n ≥ 1, with worst-case time O(n L(n)^(1−0.00363797977)), where L(n) = max(ceil(log₂ n), 1). This is the full bound with no assumed algorithmic or analytic framework. Its proof is Open.

Preamble
import Definitions.Def_IntMul_MultitapeModel
Formal statement
namespace IntMul.Kappa

theorem conditional_kappa_00363797977_pr7113 : KappaBound (0.00363797977 : ℝ) := by
  sorry

end IntMul.Kappa
Source
https://github.com/CrocSwap/integer-mult-bounds/pull/7113 (head 07a76c5e2738882c0cb322278e56f6cae3c9885d); original framework: https://github.com/openai/math/tree/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Integer-multiplication-below-n-log-n-September-23-2026
Read-back

What the Lean code literally says, in plain math · claude-sonnet-5-5

Read-back de IntMul.Kappa.conditional_kappa_00363797977_pr7113

L'énoncé affirme, sans aucune hypothèse supplémentaire, que la propriété KappaBound(κ)\mathrm{KappaBound}(\kappa)KappaBound(κ) est vraie pour le réel κ=0,00363797977\kappa = 0{,}00363797977κ=0,00363797977 (littéral décimal, interprété comme un réel).

Machines. Une machine de Turing déterministe à kkk rubans, avec k≥2k \ge 2k≥2, se compose d'un alphabet fini Σ\SigmaΣ contenant cinq symboles deux à deux distincts (le blanc □\square□, le symbole de début ▹\triangleright▹, 000, 111, #\##), d'un ensemble fini d'états KKK avec un état initial et un état d'arrêt différents, et d'une fonction de transition δ:K×Σk→K×(Σ×{←,−,→})k\delta : K \times \Sigma^k \to K \times (\Sigma \times \{\leftarrow, -, \rightarrow\})^kδ:K×Σk→K×(Σ×{←,−,→})k. Sur une cellule portant ▹\triangleright▹, la machine réécrit ▹\triangleright▹ et ne va pas à gauche ; ▹\triangleright▹ n'est jamais écrit ailleurs ; dans l'état d'arrêt la configuration est figée ; le ruban 000 (entrée) n'est jamais modifié. Le ruban 111 est le ruban de sortie, les autres sont des rubans de travail, tous infinis à droite.

Configuration initiale sur x#yx\#yx#y (x,yx, yx,y listes de bits) : état initial, ruban d'entrée ▹ x # y □⋯\triangleright\, x\, \#\, y\, \square \cdots▹x#y□⋯, autres rubans ▹ □⋯\triangleright\, \square \cdots▹□⋯, têtes en cellule 000.

Arrêt avec sortie. Après exactement ttt pas, l'état est l'état d'arrêt et le ruban de sortie contient exactement ▹ w □⋯\triangleright\, w\, \square \cdots▹w□⋯ ; les autres rubans ne sont pas contraints.

Fonctions auxiliaires. val(x)\mathrm{val}(x)val(x) est l'entier écrit en binaire par xxx (bit de poids fort en premier). binm(z)\mathrm{bin}_m(z)binm​(z) est la liste des mmm bits de zzz (poids fort en premier, troncature modulo 2m2^m2m). lg(n)=max⁡(⌈log⁡2n⌉,1)\mathrm{lg}(n) = \max(\lceil \log_2 n \rceil, 1)lg(n)=max(⌈log2​n⌉,1), donc lg(0)=lg(1)=1\mathrm{lg}(0) = \mathrm{lg}(1) = 1lg(0)=lg(1)=1.

Borne de temps. MulTimeBound(g)\mathrm{MulTimeBound}(g)MulTimeBound(g) signifie : il existe une machine MMM à k≥2k \ge 2k≥2 rubans telle que (1) pour tout n≥1n \ge 1n≥1 et toutes listes de bits x,yx, yx,y de longueur nnn, MMM arrête sur x#yx\#yx#y avec la sortie bin2n(val(x)val(y))\mathrm{bin}_{2n}(\mathrm{val}(x)\mathrm{val}(y))bin2n​(val(x)val(y)) ; (2) il existe c>0c > 0c>0 et n0n_0n0​ tels que, pour tout n≥max⁡(n0,1)n \ge \max(n_0, 1)n≥max(n0​,1), cet arrêt a lieu en au plus c⋅g(n)c \cdot g(n)c⋅g(n) pas. La même machine convient pour tous les nnn ; alphabet, états et nombre de rubans sont libres mais finis.

Borne κ\kappaκ. KappaBound(κ)\mathrm{KappaBound}(\kappa)KappaBound(κ) est MulTimeBound(gκ)\mathrm{MulTimeBound}(g_\kappa)MulTimeBound(gκ​) avec gκ(n)=n⋅(lg n)1−κg_\kappa(n) = n \cdot (\mathrm{lg}\, n)^{1-\kappa}gκ​(n)=n⋅(lgn)1−κ (puissance réelle).

Énoncé complet. Il existe une machine de Turing déterministe multiruban MMM et des constantes c>0c > 0c>0, n0n_0n0​ telles que MMM calcule le produit sur 2n2n2n bits pour tout n≥1n \ge 1n≥1 et le fait en au plus c n (lg n)1−0,00363797977=c n (lg n)0,99636202023c\, n\, (\mathrm{lg}\, n)^{1 - 0{,}00363797977} = c\, n\, (\mathrm{lg}\, n)^{0{,}99636202023}cn(lgn)1−0,00363797977=cn(lgn)0,99636202023 pas pour tout n≥max⁡(n0,1)n \ge \max(n_0, 1)n≥max(n0​,1). C'est une affirmation inconditionnelle d'existence, sans autre paramètre ; la preuve est laissée en sorry.

Human review
  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Secousses · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me