Auto Research: Integer multiplication below n log n
The page pitches an autonomous research run to improve integer-multiplication exponents, while the discussion questions whether gains reflect genuine progress or cost-model accounting.
The page is a landing and instruction page for an autonomous mathematical research run on integer multiplication bounds. It supplies a detailed prompt for Codex or Claude Code to reproduce the current best conditional exponent kappa in T(n)=O(n (log n)^(1-kappa)), search for a reproducible improvement, certify it with exact arithmetic, and package a PR.
It also displays leaderboards tracking contributors, PRs, records, and disclosed AI tools, while cautioning that a finite certificate is not a proof of the full asymptotic theorem and an exponent gain is not a runtime speedup.
Key takeaways
- The prompt targets the CrocSwap/integer-mult-bounds repository and asks for a genuine, reproducible improvement to the conditional integer-multiplication exponent saving kappa, with larger kappa better.
- It instructs the agent to establish the live frontier from README, certificates, PRs, and proof files; pin the strongest comparable witness by commit SHA; and reproduce its verification before improving.
- The search phase should rank hypotheses by plausible gain and verification cost, keep an experiment log, and avoid adding gains from different PRs without proving compatibility.
- Certification requires exact rational arithmetic or certified bounds, clean reruns, negative controls, and recording commands, hashes, rational kappa, and improvement against the pinned baseline.
- The page warns that finite certificate success is not a formal proof of the complete asymptotic multiplication theorem, and an exponent gain is not a measured runtime speedup.
- It includes leaderboards for integer multiplication results, contributors, and disclosed AI agents, with metrics such as PRs, merged PRs, commits, records, and lead minutes.
What people think
Analysis details
4 comments analyzed. Analyzed .
The sample selects active discussion branches and includes available parent comments. It may omit parts of the full thread. Selected themes do not measure community opinion or how common a view is.
Time-space tradeoffs and lookup tables
Blum's speedup theorem allows time improvements via huge lookup tables; a reply questions whether arbitrary-size integers permit a finite lookup table without computing it.
Cost-model critique
A cited blog argues the result may exploit TCS formalization by treating exact complex arithmetic as atomic, shifting costs to packing and unpacking.
Galactic algorithm concerns
The result is described as a galactic algorithm, raising doubts about practical use.
Intuitive explanation request
A commenter asks for an intuitive writeup of the speedup, analogous to FFT's Vandermonde symmetry.