Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Capacities of repeater-assisted quantum communications

Definition
QAlgorithms_Papers_Independent_Support50_P47

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The objects the formalized statements of Capacities of repeater-assisted quantum communications (arXiv:1601.00966) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • WeightedNetwork: PDF pp.16,23–24: an undirected weighted network with individually labelled edges. Endpoint ordering is only a representation; routes may traverse either way. Distinct labels may have the same endpoints, retaining parallel edges. Finiteness and connectedness are imposed in the proposition, not by this data.
  • Route: PDF pp.16,23–24: a nonempty simple route, including its actual edge labels. Injectivity forbids repeated vertices. The first and last vertices are fixed; there is no independently supplied collection that could omit legal routes.
  • IsConnected: PDF pp.23–24: every pair of distinct vertices has a simple route. On a singleton graph this is vacuous, but the proposition requires a ≠ b.
  • routeWeight: PDF pp.23–24, Eq.(131): minimum of the weights of the actual route edges. The finite range is nonempty by Route.positive, so real sInf is a genuine minimum.
  • cutWeight: PDF pp.20,23–24, Eqs.(107),(131): maximum weight over labelled edges crossing A and its complement, counted once regardless of endpoint ordering. For finite connected networks and an endpoint-separating A this set is finite and nonempty. Outside that domain real sSup assigns 0 to the empty cut.
Definition code
import Mathlib

/-! Pirandola, arXiv:1601.00966v4. Only the standalone graph proposition is
stated here. Operational and source-ambiguity deferrals are individually recorded
in the unit's HARD.md and GAPS.json. Compilation is pending batch handoff. -/

namespace QAlgorithms.Papers.Independent.Support50.P47

noncomputable section

universe u v

/-- PDF pp.16,23–24: an undirected weighted network with individually labelled
edges. Endpoint ordering is only a representation; routes may traverse either
way. Distinct labels may have the same endpoints, retaining parallel edges.
Finiteness and connectedness are imposed in the proposition, not by this data. -/
structure WeightedNetwork (V : Type u) (E : Type v) where
  left : E → V
  right : E → V
  separated : ∀ e, left e ≠ right e
  weight : E → ℝ

/-- PDF pp.16,23–24: a nonempty simple route, including its actual edge labels.
Injectivity forbids repeated vertices. The first and last vertices are fixed;
there is no independently supplied collection that could omit legal routes. -/
structure Route {V : Type u} {E : Type v} (G : WeightedNetwork V E) (a b : V) where
  length : ℕ
  positive : 0 < length
  vertex : Fin (length + 1) → V
  edge : Fin length → E
  start : vertex ⟨0, Nat.zero_lt_succ length⟩ = a
  finish : vertex (Fin.last length) = b
  simple : Function.Injective vertex
  follows : ∀ i : Fin length,
    (G.left (edge i) = vertex i.castSucc ∧ G.right (edge i) = vertex i.succ) ∨
    (G.right (edge i) = vertex i.castSucc ∧ G.left (edge i) = vertex i.succ)

/-- PDF pp.23–24: every pair of distinct vertices has a simple route.
On a singleton graph this is vacuous, but the proposition requires a ≠ b. -/
def IsConnected {V : Type u} {E : Type v} (G : WeightedNetwork V E) : Prop :=
  ∀ a b : V, a ≠ b → Nonempty (Route G a b)

/-- PDF pp.23–24, Eq.(131): minimum of the weights of the actual route edges.
The finite range is nonempty by Route.positive, so real sInf is a genuine minimum. -/
def routeWeight {V : Type u} {E : Type v} (G : WeightedNetwork V E)
    {a b : V} (p : Route G a b) : ℝ :=
  sInf (Set.range (fun i : Fin p.length => G.weight (p.edge i)))

/-- PDF pp.20,23–24, Eqs.(107),(131): maximum weight over labelled edges
crossing A and its complement, counted once regardless of endpoint ordering.
For finite connected networks and an endpoint-separating A this set is finite
and nonempty. Outside that domain real sSup assigns 0 to the empty cut. -/
def cutWeight {V : Type u} {E : Type v} (G : WeightedNetwork V E) (A : Set V) : ℝ :=
  sSup {w : ℝ | ∃ e : E,
    ((G.left e ∈ A ∧ G.right e ∉ A) ∨ (G.right e ∈ A ∧ G.left e ∉ A)) ∧
    w = G.weight e}

/-- A constant-weight nonempty route has that weight, even when it is negative. -/
example {V : Type u} {E : Type v} (G : WeightedNetwork V E)
    {a b : V} (p : Route G a b) (w : ℝ) (hw : ∀ e, G.weight e = w) :
    routeWeight G p = w := by
  letI : Nonempty (Fin p.length) := ⟨⟨0, p.positive⟩⟩
  simp [routeWeight, hw]

/-- The empty crossing set has the documented off-domain value 0. -/
example {V : Type u} {E : Type v} (G : WeightedNetwork V E) :
    cutWeight G Set.univ = 0 := by
  simp [cutWeight]

end

end QAlgorithms.Papers.Independent.Support50.P47
Source
Capacities of repeater-assisted quantum communications, arXiv:1601.00966v4, https://arxiv.org/abs/1601.00966v4
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

QAlgorithms.Papers.Independent.Support50.P47.IsConnected

For arbitrary types V,EV,EV,E and a network GGG with distinct endpoints ℓ(e),r(e)∈V\ell(e),r(e)\in Vℓ(e),r(e)∈V for every e∈Ee\in Ee∈E and arbitrary real edge weights, being connected means that for every pair a,b∈Va,b\in Va,b∈V with a≠ba\ne ba=b, there exists a route from aaa to bbb: a positive integer length nnn, pairwise distinct vertices v0,…,vnv_0,\ldots,v_nv0​,…,vn​ with v0=av_0=av0​=a and vn=bv_n=bvn​=b, and edges e0,…,en−1e_0,\ldots,e_{n-1}e0​,…,en−1​ whose endpoints are vi,vi+1v_i,v_{i+1}vi​,vi+1​ in either order for every 0≤i<n0\le i<n0≤i<n. There is no requirement to supply a route from a vertex to itself. This condition holds vacuously when VVV is empty or has only one element.

QAlgorithms.Papers.Independent.Support50.P47.Route

Let V,EV,EV,E be arbitrary types, and let GGG be a network with endpoint functions ℓ,r:E→V\ell,r:E\to Vℓ,r:E→V satisfying ℓ(e)≠r(e)\ell(e)\ne r(e)ℓ(e)=r(e) for every edge and with weights w:E→Rw:E\to\mathbb Rw:E→R. For vertices a,b∈Va,b\in Va,b∈V, a route from aaa to bbb consists of a natural number n>0n>0n>0, vertices v0,…,vnv_0,\ldots,v_nv0​,…,vn​, and edges e0,…,en−1e_0,\ldots,e_{n-1}e0​,…,en−1​, such that v0=av_0=av0​=a, vn=bv_n=bvn​=b, all n+1n+1n+1 vertices are pairwise distinct, and, for every 0≤i<n0\le i<n0≤i<n, either ℓ(ei)=vi\ell(e_i)=v_iℓ(ei​)=vi​ and r(ei)=vi+1r(e_i)=v_{i+1}r(ei​)=vi+1​, or r(ei)=vir(e_i)=v_ir(ei​)=vi​ and ℓ(ei)=vi+1\ell(e_i)=v_{i+1}ℓ(ei​)=vi+1​. Edges may therefore be traversed in either endpoint order. Length zero is excluded, and the distinctness requirement implies that no such route exists when a=ba=ba=b.

QAlgorithms.Papers.Independent.Support50.P47.WeightedNetwork

For arbitrary types VVV and EEE, a weighted network consists of two endpoint functions ℓ,r:E→V\ell,r:E\to Vℓ,r:E→V, a requirement that ℓ(e)≠r(e)\ell(e)\ne r(e)ℓ(e)=r(e) for every e∈Ee\in Ee∈E, and a real weight function w:E→Rw:E\to\mathbb Rw:E→R. Thus every edge has two distinct endpoints and an arbitrary real weight, which may be negative or zero. Different edges may have the same endpoints. No finiteness or nonemptiness requirement is imposed on either type.

QAlgorithms.Papers.Independent.Support50.P47.cutWeight

Let V,EV,EV,E be arbitrary types, let GGG have endpoint functions ℓ,r:E→V\ell,r:E\to Vℓ,r:E→V with ℓ(e)≠r(e)\ell(e)\ne r(e)ℓ(e)=r(e) for every edge and a real weight function w:E→Rw:E\to\mathbb Rw:E→R, and let A⊆VA\subseteq VA⊆V be any set. Its cut weight is defined by

cutWeight⁡G(A)=sup⁡{w(e):e∈E,  (ℓ(e)∈A ∧ r(e)∉A) ∨ (r(e)∈A ∧ ℓ(e)∉A)}.\operatorname{cutWeight}_G(A)= \sup\{w(e):e\in E,\;(\ell(e)\in A\ \land\ r(e)\notin A)\ \lor\ (r(e)\in A\ \land\ \ell(e)\notin A)\}.cutWeightG​(A)=sup{w(e):e∈E,(ℓ(e)∈A ∧ r(e)∈/A) ∨ (r(e)∈A ∧ ℓ(e)∈/A)}.

Thus it takes the real supremum of the weights of edges with exactly one endpoint in AAA, without requiring AAA to contain or exclude any specified vertices. Under the real supremum convention used here, its value is 000 if this set of weights is empty or unbounded above. In particular, it is 000 for A=∅A=\varnothingA=∅, A=VA=VA=V, or any other set with no crossing edges.

QAlgorithms.Papers.Independent.Support50.P47.routeWeight

Let V,EV,EV,E be arbitrary types, let GGG assign distinct endpoints to each edge and a real weight w(e)w(e)w(e) to each e∈Ee\in Ee∈E, and let a,b∈Va,b\in Va,b∈V. Given a route ppp from aaa to bbb, consisting of a positive length nnn, pairwise distinct vertices v0,…,vnv_0,\ldots,v_nv0​,…,vn​ starting at aaa and ending at bbb, and edges eie_iei​ joining viv_ivi​ to vi+1v_{i+1}vi+1​ in either endpoint order, its route weight is defined by

routeWeight⁡G(p)=inf⁡{w(ei):0≤i<n}.\operatorname{routeWeight}_G(p)=\inf\{w(e_i):0\le i<n\}.routeWeightG​(p)=inf{w(ei​):0≤i<n}.

Because n>0n>0n>0, this is the minimum of a finite nonempty set of real edge weights; the definition never takes an infimum of an empty set for a route.

Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

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