Theorem 3.11 — Trajectory-dependent failure count
OpenPaceSSSP517.Certified.Supplement.trajectory_failuresUse the same graph, source, spanner and standing PACE parameters as Theorem 3.7, and any supported executed prefix. For every in that prefix, let be the maximum violating fraction among non-bulk rounds up to . When such a round exists, put
otherwise put the evaluated climb length equal to zero. Here is the actual reconstructed potential including round 's virtual multiplier.
Every edge fails in at most non-bulk rounds among the first , and at most one bulk round. Deterministically,
If
round 's stop flag is set, the actual execution is stopped, and its length is at most . This applies to every qualifying executed round, hence to the first.
The companion theorem bounds failures using the observed trajectory. It uses the base failure and potential mechanisms, Lemmas 3.1 and 3.5 (ids a30c6d5b-1d2e-4b3d-92a6-cfd0d670b856 and b92177bc-c841-45a8-be36-4c6cf9284c1d). No probabilistic premise or potential upper bound is assumed.
Differences from the source:
- encoding: finite connected positive-real weighted undirected graph and finite profiles → published graph and Algorithm 1 modules with Fin n vertices and one stored orientation per edge; reason: canonical storage permits walks and the Bellman–Ford operator to use both orientations; connected spanners make every asserted real distance finite
- generalization: H computed by the upstream spanner routine → any H satisfying the same (2k−1+ε) all-pairs spanner condition; reason: the added results have no space clause and use only this condition; the prescribed routine output is an instance
- encoding: deterministically on the actual PACE execution → every SampleTrace whose trajectory equals its executed prefix, using one-based executed indices; reason: SampleTrace is the support restriction of the conditional Bernoulli choices including probability-one and probability-zero edges; unsupported samples are excluded
- reading: maximum violating fraction over non-bulk rounds without an empty-set convention → evaluated climb length is zero when there is no non-bulk round; reason: the maximum is empty in already-exact/all-bulk executions; the source maximum is undefined on this empty set; the explicit zero extension records zero non-bulk failures without inventing a positive rho
- encoding: ceil of the logarithm ratio and stop by the first qualifying round → integer ceiling with actual Q^(R+1), and the stop flag at every positive executed R satisfying the threshold; reason: the integer ceiling avoids truncating a potentially negative formula; pointwise stopping at every qualifying executed round implies stopping by the first such round
import Definitions.Def_PaceSSSP517_Certified_Supplement_TraceStatistics set_option autoImplicit false
namespace PaceSSSP517.Certified.Supplement
/-- Theorem 3.11, p.9, display (2); proof A.9 p.20. Counts are compared in
integers to preserve the source's signed ceiling. The empty non-bulk maximum
has climb length zero. Every R is a positive, executed round. -/
theorem trajectory_failures
(n k : ℕ) (ε : ℝ) (G : WeightedGraph n) (H : Finset (Edge n)) (s₀ : Fin n)
(hparams : Parameters n k ε) (hG : Connected G.edges)
(hH : IsSpanner G H (2 * (k : ℝ) - 1 + ε))
(Fs : List (Finset (Edge n))) (hFs : SampleTrace G H s₀ k ε Fs)
(hexecuted : execution (trajectory G H s₀ k ε Fs).rounds =
(trajectory G H s₀ k ε Fs).rounds) :
let ts := (trajectory G H s₀ k ε Fs).rounds
∀ R ∈ past ts.length,
let f := climbLength G ts k ε R
(∀ e ∈ G.edges,
((failureRounds G ts (nonBulkRounds ts R) e).card : ℤ) ≤ f ∧
(failureRounds G ts (bulkRounds ts R) e).card ≤ 1) ∧
kappa G ts (past R) ≤ (2 * (k : ℝ) - 1) * ((f : ℝ) + 1) / (R : ℝ) ∧
((2 * (k : ℝ) / ε) * ((f : ℝ) + 1) ≤ (R : ℝ) →
(roundAt ts R).stopping = true ∧ stopped ts ∧ ts.length ≤ R) := by sorry
end PaceSSSP517.Certified.Supplement