Skip to content
FR · Français
Get started

Language: English · Français

Walsh–Hadamard and Fourier below n log n: Sussman's Lean proofs

≈ 0.000876248≤ value ≤no upper bound trackedlower boundupper bound
10−11​10−8​10−5​6 Oct11 Octupdated on Oct 12, 2026Lower bound 2/100000000000, Oct 6, 2026, OpenAI, publishedLower bound ≈ 0.000539923, Oct 9, 2026, jacobalansussman, mergedLower bound ≈ 0.000747455, Oct 9, 2026, jacobalansussman, mergedLower bound ≈ 0.000876248, Oct 10, 2026, jacobalansussman, merged≈ 0.000876248lower10−11​10−8​10−5​6 Oct8 Oct10 Oct12 Octupdated on Oct 12, 2026Lower bound 2/100000000000, Oct 6, 2026, OpenAI, publishedLower bound ≈ 0.000539923, Oct 9, 2026, jacobalansussman, mergedLower bound ≈ 0.000747455, Oct 9, 2026, jacobalansussman, mergedLower bound ≈ 0.000876248, Oct 10, 2026, jacobalansussman, merged≈ 0.000876248lower bound
Only one side is tracked: there is no space between two bounds to colour.Hover over the points or move through them with the keyboard; a click opens the PR, the commit or the source page.Tap a point to read its source; tap it again to open the PR or the page.
  1. lower bound ≈ 0.00053992by jacobalansussmangithub.com
  2. lower bound ≈ 0.00074745by jacobalansussmangithub.com
  3. lower bound ≈ 0.00087625by jacobalansussmangithub.com
  4. Last checked
Lower bound · merged · Oct 10, 2026
Exact value : 8762479/10000000000
Fourth result: a new unit, saving 8.762479e-4, checked in Lean; search programs, notes and rebuild scripts · github.com
by jacobalansussman
FollowReport

Cite this frontier

DiscoverIA. Walsh–Hadamard and Fourier below n log n: Sussman's Lean proofs [Frontier, checked on Oct 12, 2026]. DiscoverIA registry. https://discoveria.ai/en/frontieres/walsh-hadamard-lean/

Only the lower bound is tracked. The lower bound has moved 3 times since 2026, most recently on Oct 10, 2026.

1 − z, where one fixed program computes the Walsh–Hadamard transform of length n = 2^k in O(n (log n)^z) operations (z < 1) in the exact RAM model of OpenAI's family 130, with a Lean proof accepted by the kernel; a proof gives a lower bound on the best saving 1 − z.

The WHT statement is Sussman's (about 60 lines of definitions added to OpenAI's RAM model, kept verbatim): OpenAI states only the DFT. The repository's DFT-of-every-length (and convolution) values are shown off the staircase (comparable: false), one ten-billionth below the WHT; they reuse OpenAI's statement (UniformFourier.lean) with the exponent replaced. Proofs are accepted by the Lean kernel, the official comparator and Compare.lean; no line-by-line human review (README). Asymptotic exponent savings, not running times; no claim on bit complexity or numerical stability.

Linked announcement in the registry

Every step, as a table : Lower bound (8 points)

Best saving 1 − z proved in Lean for the WHT (start: constant of OpenAI's tensor engine).

Points : Lower bound
DateExact valueNatureAuthorsSource
Oct 10, 20268762479/10000000000 Current recordmergedjacobalansussmangithub.com
Oct 10, 20268762478/10000000000merged (≠)jacobalansussmangithub.com
Oct 10, 20267547361/10000000000proposedchafreakyPR #2
Oct 9, 20267474546/10000000000merged (≠)jacobalansussmangithub.com
Oct 9, 20267474547/10000000000 Current recordmergedjacobalansussmangithub.com
Oct 9, 20265399225/10000000000 Current recordmergedjacobalansussmangithub.com
Oct 6, 20262/100000000000 Current recordpublishedOpenAIgithub.com
Sep 25, 20261e-13published (≠)OpenAIgithub.com

(≠): value measured in another setting; shown, not counted in the bounds.

Other tracked problems (8)

Report an error or suggest a source

How DiscoverIA uses your address and how to exercise your rights: privacy policy.

Bot check not configured.