Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PR #6453: the rank-moment inequality at κ=0.003287014\kappa = 0.003287014κ=0.003287014

Proved
Pr6453.moment_kappa_gt

by gustasmickus · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinteger-multiplication

The two rank histograms of the PR #6453 word satisfy the price inequality at the claimed saving κ=1643507/500000000=0.003287014\kappa = 1643507/500000000 = 0.003287014κ=1643507/500000000=0.003287014:

∑rTr r1−κ  >  ∑rPr r1−κ,\sum_{r} T_r\, r^{1-\kappa} \;>\; \sum_{r} P_r\, r^{1-\kappa},r∑​Tr​r1−κ>r∑​Pr​r1−κ,

where TrT_rTr​ counts the productive target fields of rank rrr and PrP_rPr​ the paid calls of rank rrr, and r1−κ=exp⁡((1−κ)log⁡r)r^{1-\kappa} = \exp((1-\kappa)\log r)r1−κ=exp((1−κ)logr) with a real exponent.

This is the numerical step on which the exponent of the construction rests. The pricing engine of the source bisects the difference of the two moments in κ\kappaκ; its root is 0.00328701955375063425072028…0.00328701955375063425072028\ldots0.00328701955375063425072028…, and any κ\kappaκ strictly below that root makes the recursive call tree of the word cheaper than it is productive, which is what a time bound O(n(lg⁡n)1−κ)O(n(\lg n)^{1-\kappa})O(n(lgn)1−κ) requires. The claimed value sits 5.5537×10−95.5537\times 10^{-9}5.5537×10−9 below the crossing, so the margin is 1.2756×10−31.2756\times 10^{-3}1.2756×10−3 against a total moment of 1.858×1051.858\times 10^{5}1.858×105 — a relative margin of 6.87×10−96.87\times 10^{-9}6.87×10−9, and the inequality is a genuinely tight numerical fact rather than a formal one.

The support of the two histograms is 191919 ranks: 1,…,9,16,17,24,25,32,33,56,57,73,1451,\dots,9,16,17,24,25,32,33,56,57,73,1451,…,9,16,17,24,25,32,33,56,57,73,145. At rank 111 the two sides contribute their counts with opposite signs (a deficit of 41 66041\,66041660), at τ=0\tau = 0τ=0 the inequality is reversed, and at τ=1\tau = 1τ=1 the rank-mass surplus is 760760760; the crossing of the two moments lies in between, and this node records that the claimed saving is still on the correct side of it.

Preamble
import Definitions.Def_Pr6453_RankMoments

set_option autoImplicit false
Formal statement
namespace Pr6453

theorem moment_kappa_gt :
    moment paid (1 - (kappa : ℝ)) < moment targets (1 - (kappa : ℝ)) := by
  sorry

end Pr6453
Source
CrocSwap/integer-mult-bounds, PR #6453, head b1a3e525793eca35c56324aa7ffd0b714cf606d4, research/p104-third-anchor-clean-mixed-root/RESULT.json (complete_cost.kappa, .tested, .raw_root_interval, .targets, .paid) and pricing.py (margin k = moment T (1-k) - moment P (1-k)). The inequality is the certificate's own crossing test at the claimed saving.

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