Reverse-doubling budgets produce an envelope with final error below one half
ProvedWikipedia.SzemeredisTheorem.bundleRankwiseEnvelope_and_error_lt_half_of_reverseDoublingBudgetadditive-combinatoricsgreen-tao-port-8822number-theory
Let , , and . For natural bounds , put and . Assume and , and for every and assume
Then the canonical rankwise error schedule is a valid bundle-counting envelope for these density floors and errors, and its value at rank and edge count is strictly below . The exponent in uses natural subtraction.
Preamble
/- Mechanically transplanted from https://github.com/plby/lean-proofs.git at 8822f7ddef30fadbd92e1c6ab4ed897af356af5e. Original scopes and proof bytes are oracle-derived. -/ import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Finite_Mean import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_HypergraphBundleCounting import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_HypergraphBundleDuplication import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_HypergraphBundleFiltration import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_HypergraphBundleGeneralizedCounting import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_HypergraphBundleIndicatorDuplication import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_RankwiseBundleEnvelopeSelection import Mathlib.Algebra.BigOperators.Expect import Mathlib.Data.Fintype.Card import Mathlib.Tactic set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 /-! # Rankwise numerical envelopes for bundle counting The generalized bundle-counting recurrence permits the density and localized-defect parameters to depend on the rank. This file supplies a direct numerical envelope for those rankwise parameters. Its density floor is the prefix minimum of the rankwise densities, so no global density lower bound is needed. The row constructor takes a maximum with the preceding-order row. This makes monotonicity in bundle order automatic even when consecutive ranks use unrelated parameters; its other branch is equality in the one-edge counting recurrence. -/ open Wikipedia.SzemeredisTheorem open Filter Topology /-! ## Prefix density floors -/ /-! ## The rankwise recurrence -/ /-! ## Positivity and monotonicity -/ /-! ## The generalized-counting interface -/ /-! ## Vanishing and continuous rankwise parameter paths -/ /-! ## Density-scaled finite-horizon selection -/ /-! ## Explicit finite-horizon sufficient bounds -/
Formal statement
theorem Wikipedia.SzemeredisTheorem.bundleRankwiseEnvelope_and_error_lt_half_of_reverseDoublingBudget
{α β : ℕ → ℝ} {τ η : ℝ}
(hα : ∀ d, 0 < α d) (hα_one : ∀ d, α d ≤ 1)
(hβ : ∀ d, 0 ≤ β d) (hτ : 0 ≤ τ) (hη : 0 ≤ η)
(rankBound edgeBound : ℕ)
(hcap :
(rankBound : ℝ) *
(bundleReverseDoublingHorizon rankBound edgeBound 0 : ℝ) * η ≤ 1)
(hfinal :
(rankBound : ℝ) *
(bundleReverseDoublingHorizon rankBound edgeBound 0 : ℝ) * η < 1 / 2)
(hdefect : ∀ d, d < rankBound → ∀ n,
n < bundleReverseDoublingHorizon rankBound edgeBound (d + 1) →
Real.sqrt
(β (d + 1) * (1 + (1 : ℝ)) * (1 + (1 : ℝ))) /
(α (d + 1)) ^ (n + 1) ≤ η / 2)
(huniform : ∀ d, d < rankBound → ∀ n,
n < bundleReverseDoublingHorizon rankBound edgeBound (d + 1) →
τ /
(bundleRankwiseDensityFloor α (d + 1)) ^ (n + 1) ≤
η / 2) :
IsBundleCountingEnvelope α β
(bundleRankwiseDensityFloor α) τ
(bundleRankwiseEnvelopeError α β
(bundleRankwiseDensityFloor α) τ) ∧
bundleRankwiseEnvelopeError α β
(bundleRankwiseDensityFloor α) τ rankBound edgeBound < 1 / 2 := by sorry
Source