Executed windows, density, bulk intervals and trajectory climb length
DefinitionPaceSSSP517_Certified_Supplement_TraceStatisticsFor a published PACE round list , retain its one-based indices, profiles , bulk flags, relative jumps , total weights and violating fractions . Write . For , let and let be the least positive with . The execution-wide maximum is . Define
Count non-bulk and bulk executed rounds through a specified horizon. Count maximal bulk intervals by their starts: a bulk round that is round 1 or follows a non-bulk round. Failure counts filter a round set using the published violation predicate.
Over non-bulk rounds , let . When this set is nonempty, define
When there is no such round, the evaluated climb length is zero. The general formula climbAt keeps as an argument; climbLength handles the empty maximum without dividing by zero.
These are statistics of the actual trace, not success assumptions. Theorems must establish the existence, minimality and bounds for the qualifying window and all failure and stopping estimates.
Formalization Note Finite real maxima include zero, changing no nonempty maximum of these nonnegative quantities. Only to totalize the least-window search after a finite execution ends, nonexistent rounds contribute no jump. Every claimed window inequality and stopping window is wholly executed. Empty infima for the least qualifying length default to zero, with nonemptiness and a positive least length asserted by Theorem 3.7. The climb formula uses an integer ceiling, including on negative numerators, and actual Qat at . No potential upper bound is substituted.
import Definitions.Def_PaceSSSP517_Certified_Resources
set_option autoImplicit false
open Classical
namespace PaceSSSP517.Certified.Supplement
/-- The source's one-based half-open window S_L. -/
def window (r₀ L : ℕ) : Finset ℕ := Finset.Ico r₀ (r₀ + L)
/-- Maximum jump in a finite execution window. Nonexecuted indices contribute
zero; this only totalizes L⋆ when its proposed window outlasts the execution.
Every asserted window inequality uses a completely executed window. -/
noncomputable def windowJump {n : ℕ} (G : WeightedGraph n) (ts : List (Round n))
(r₀ L : ℕ) : ℝ :=
let S := (window r₀ L).filter (fun j => 1 ≤ j ∧ j ≤ ts.length)
let values := S.biUnion (fun j => G.edges.image (jump G (profile ts j)))
(insert 0 values).max' (Finset.insert_nonempty _ _)
/-- Least positive L satisfying the observed-window stopping inequality.
Existence and the source's ceiling bound are theorem conclusions, not fields. -/
noncomputable def firstWindow {n : ℕ} (G : WeightedGraph n) (ts : List (Round n))
(ε : ℝ) (r₀ : ℕ) : ℕ :=
sInf {L : ℕ | 1 ≤ L ∧ windowJump G ts r₀ L / ε ≤ (L : ℝ)}
noncomputable def executionJump {n : ℕ} (G : WeightedGraph n)
(ts : List (Round n)) : ℝ := windowJump G ts 1 ts.length
noncomputable def density {n : ℕ} (G : WeightedGraph n) (k : ℕ) (ε : ℝ) : ℝ :=
G.edges.card / budget n k ε
/-- Natural floor of the nonnegative horizon in Theorem 3.10, p.8. -/
noncomputable def earlyHorizon {n : ℕ} (G : WeightedGraph n) (k : ℕ) (ε : ℝ) : ℕ :=
⌊min (5 * (k : ℝ) / ε)
((k : ℝ) * (n : ℝ) ^ (2 / (k : ℝ)) / (3 * ε * density G k ε))⌋₊
noncomputable def nonBulkRounds {n : ℕ} (ts : List (Round n)) (R : ℕ) : Finset ℕ :=
(past (min R ts.length)).filter (fun j => (roundAt ts j).bulk = false)
noncomputable def bulkRounds {n : ℕ} (ts : List (Round n)) (R : ℕ) : Finset ℕ :=
(past (min R ts.length)).filter (fun j => (roundAt ts j).bulk = true)
/-- Each maximal interval of executed bulk rounds has exactly one start. -/
noncomputable def bulkRunCount {n : ℕ} (ts : List (Round n)) : ℕ :=
((bulkRounds ts ts.length).filter (fun j =>
j = 1 ∨ (roundAt ts (j - 1)).bulk = false)).card
noncomputable def failureRounds {n : ℕ} (G : WeightedGraph n)
(ts : List (Round n)) (S : Finset ℕ) (e : Edge n) : Finset ℕ :=
S.filter (fun j => fails G (profile ts j) e)
/-- Maximum violating fraction over the executed non-bulk rounds up to R.
Zero is an empty-maximum convention; climbLength handles that case separately. -/
noncomputable def rhoStar {n : ℕ} (G : WeightedGraph n)
(ts : List (Round n)) (R : ℕ) : ℝ :=
let values := (nonBulkRounds ts R).image (rhoAt G ts)
(insert 0 values).max' (Finset.insert_nonempty _ _)
/-- The exact integer ceiling in display (2), p.9, with the actual Q^(R+1).
The real formula is used at positive rho, never at the empty maximum. -/
noncomputable def climbAt {n : ℕ} (G : WeightedGraph n) (ts : List (Round n))
(k : ℕ) (ε : ℝ) (R : ℕ) (ρ : ℝ) : ℤ :=
⌈Real.log (2 * Qat G ts (R + 1) / budget n k ε) /
Real.log (1 + ε / (10 * (k : ℝ) * ρ))⌉
/-- f⋆_R(rho⋆_R), with value zero when no non-bulk round has occurred. -/
noncomputable def climbLength {n : ℕ} (G : WeightedGraph n) (ts : List (Round n))
(k : ℕ) (ε : ℝ) (R : ℕ) : ℤ :=
if (nonBulkRounds ts R).Nonempty then climbAt G ts k ε R (rhoStar G ts R) else 0
end PaceSSSP517.Certified.Supplement