Subclaim 2.5 — at most distinct sets
ProvedBFAlmostLinear.subclaim_2_5graph-algorithmsnegative-weightsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithmsshortest-paths
There is an absolute constant with the following property. Let be a finite set, nonempty, and any function. For a potential let
Then, as ranges over all potentials, the number of distinct sets is at most
With the set is (p.7), so this is the union-bound count behind Lemma 2.4.
Formalization Note The family of sets is a finite set of subsets of , so its size cannot be a junk value.
Differences from the source:
- generalization: → any that is never ; reason: iff (p.7), and the hop distances are never under frozen flags, so the printed claim is the special case (including any hop pair ).
- encoding: and the set → nonempty; reason: for an empty set the printed bound is while one set exists, so the -bound is read for nonempty sets.
- encoding: → an absolute constant chosen before ; reason: Lean form of the .
Preamble
import Mathlib
Formal statement
namespace BFAlmostLinear
open Classical in
/-- **Subclaim 2.5**, p.7. "For any S, T ⊆ V, the number of possible distinct sets X_ϕ[S, ∗, T] over all possible
potential functions ϕ is O((|S| · |T| · |N|)^{|S∪T|})."
Hair, Li, Li, Zhang, *Bellman-Ford in Almost-Linear Time*, STOC 2027 submission (manuscript sha256
873b9acb…), Subclaim 2.5, p.7.
**Formalization Note.**
* The constant `C` is absolute: it comes before the types.
* `(s, r, t) ∈ X_ϕ` holds if and only if `c(s, r, t) + ϕ(s) − ϕ(t) < 0`, with `c(s, r, t) = d^{h₁}(s, r) + d^{h₂}(r, t)`, by
the shift of a reweighting (p.7). The statement is for any `c` that is never `⊥`, which covers this `c`.
* `S`, `T`, `N` are nonempty: the printed bound is `0` for `N = ∅` while one set exists.
* The family is a `Finset`, a filter of a powerset, so that its cardinality cannot be a junk value. -/
theorem subclaim_2_5 :
∃ C : ℝ, 0 < C ∧
∀ (V : Type) [Fintype V] (S T N : Finset V) (c : V → V → V → EReal),
S.Nonempty → T.Nonempty → N.Nonempty → (∀ s r t, c s r t ≠ ⊥) →
((((S ×ˢ N ×ˢ T).powerset.filter fun X =>
∃ ϕ : V → ℝ, ∀ x ∈ S ×ˢ N ×ˢ T,
x ∈ X ↔ c x.1 x.2.1 x.2.2 + ((ϕ x.1 - ϕ x.2.2 : ℝ) : EReal) < 0).card : ℕ) : ℝ) ≤
C * (((S.card * T.card * N.card : ℕ) : ℝ)) ^ (S ∪ T).card := by sorry
end BFAlmostLinear
Source
Hair, Li, Li, Zhang, Bellman-Ford in Almost-Linear Time, STOC 2027 submission (manuscript sha256 873b9acb…), Subclaim 2.5, p.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.