op_1710_kuramoto_coupling_iso_eq
For any two isomorphic graphs T and T' on a finite vertex set V, any probability measure μ on ℝ, and any threshold s, the probability that the Kuramoto critical coupling is at most s is identical for T and T'.
Statement
theorem op_1710_kuramoto_coupling_iso_eq {V : Type*} [Fintype V] (T T' : SimpleGraph V) (e : T ≃g T') (μ : MeasureTheory.Measure ℝ) [MeasureTheory.IsProbabilityMeasure μ] (s : ℝ) : MeasureTheory.Measure.pi (fun (_ : V) ↦ μ) { ω | kuramoto_critical_coupling T ω ≤ s } = MeasureTheory.Measure.pi (fun (_ : V) ↦ μ) { ω | kuramoto_critical_coupling T' ω ≤ s }
- Source
- folklore
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- kuramoto_critical_couplingThe critical coupling K_H of a tree H under natural frequencies ω is the maximum over all edges e of the absolute sum of deviations (ω_v -…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
For any finite type $V$, any two simple graphs $T$ and $T'$ on $V$, any graph isomorphism $e : T \simeq_g T'$, any probability measure $\mu$ on $\mathbb{R}$, and any real number $s \in \mathbb{R}$: The measure of the set of frequency configurations $\omega : V \to \mathbb{R}$ such that $\operatorname{kuramoto\_critical\_coupling}(T, \omega) \le s$ with respect to the product measure $\mu^{\otimes V} = \prod_{v \in V} \mu$ is equal to the measure of the set of configurations $\omega : V \to \mathbb{R}$ such that $\operatorname{kuramoto\_critical\_coupling}(T', \omega) \le s$ with respect to the same product measure.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof shows the measure of the sublevel set is preserved under graph isomorphism by using the measure-preserving pushforward under the vertex permutation.
The measure is invariant.
By measure preserving.
let F := MeasurableEquiv.piCongrLeft (fun _ : V ↦ ℝ) e.toEquiv have hmp : MeasureTheory.MeasurePreserving F (MeasureTheory.Measure.pi fun _ ↦ μ) (MeasureTheory.Measure.pi fun _ ↦ μ) := MeasureTheory.measurePreserving_piCongrLeft (fun _ ↦ μ) e.toEquiv have hpre := hmp.measure_preimage_equiv { ω | kuramoto_critical_coupling T' ω ≤ s } rw [← hpre] congr 1 ext ω have hF : F ω = fun v ↦ ω (e.symm v) := by ext v simp [F, MeasurableEquiv.coe_piCongrLeft, Equiv.piCongrLeft_apply] rfl change kuramoto_critical_coupling T ω ≤ s ↔ kuramoto_critical_coupling T' (F ω) ≤ s rw [hF, op_1710_kuramoto_coupling_comp_symm T T' e ω]
- Unresolved check: no step explains line(s) 5, 6, 7, 8, 9, 10, 11, 12, 22, 23, 24, 25, 26, 32, 33, 34, 35, 36, 37, 38 -- every tactic of the proof has to belong to some step
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
def op_1710_deleteEdgesIso {V : Type*} (T T' : SimpleGraph V) (e : T ≃g T') (u v : V) : T.deleteEdges {s(u, v)} ≃g T'.deleteEdges {s(e u, e v)} where toEquiv := e.toEquiv map_rel_iff' := by intro x y change (T'.deleteEdges {s(e u, e v)}).Adj (e x) (e y) ↔ (T.deleteEdges {s(u, v)}).Adj x y simp only [SimpleGraph.deleteEdges_adj, Set.mem_singleton_iff] rw [SimpleGraph.Iso.map_adj_iff e] have : s(e x, e y) = s(e u, e v) ↔ s(x, y) = s(u, v) := by rw [← Sym2.map_mk, ← Sym2.map_mk] exact (Sym2.map.injective e.injective).eq_iff exact and_congr_right_iff.mpr fun _ => not_congr thistheorem op_1710_reachable_deleteEdges_iff {V : Type*} (T T' : SimpleGraph V) (e : T ≃g T') (u v w : V) : (T'.deleteEdges {s(e u, e v)}).Reachable (e u) (e w) ↔ (T.deleteEdges {s(u, v)}).Reachable u w := (op_1710_deleteEdgesIso T T' e u v).reachable_iff (u := u) (v := w)open scoped Classical inlemma op_1710_inner_sum_eq {V : Type*} [Fintype V] (T T' : SimpleGraph V) (e : T ≃g T') (ω : V → ℝ) (m : ℝ) (u v : V) : (∑ w : V, if (T'.deleteEdges {s(e u, e v)}).Reachable (e u) w then (ω (e.symm w) - m) else 0) = (∑ w : V, if (T.deleteEdges {s(u, v)}).Reachable u w then (ω w - m) else 0) := by have h := (e.toEquiv.sum_comp (fun w => if (T'.deleteEdges {s(e u, e v)}).Reachable (e u) w then (ω (e.symm w) - m) else 0)).symm rw [h] refine Finset.sum_congr rfl fun w _ => ?_ have h1 : (e.toEquiv w : V) = e w := rfl simp only [h1, op_1710_reachable_deleteEdges_iff, RelIso.symm_apply_apply]open scoped Classical inlemma op_1710_kuramoto_coupling_comp_symm {V : Type*} [Fintype V] (T T' : SimpleGraph V) (e : T ≃g T') (ω : V → ℝ) : kuramoto_critical_coupling T' (fun v => ω (e.symm v)) = kuramoto_critical_coupling T ω := by unfold kuramoto_critical_coupling dsimp only have hmean_sum : (∑ v : V, ω (e.symm v)) = ∑ v : V, ω v := by have : (fun v => ω (e.symm v)) = (fun v => ω (e.symm.toEquiv v)) := rfl rw [this, e.symm.toEquiv.sum_comp] rw [hmean_sum] rw [← e.toEquiv.iSup_comp] refine iSup_congr fun u => ?_ rw [← e.toEquiv.iSup_comp] refine iSup_congr fun v => ?_ have hadj : T'.Adj (e.toEquiv u) (e.toEquiv v) ↔ T.Adj u v := by change T'.Adj (e u) (e v) ↔ T.Adj u v exact SimpleGraph.Iso.map_adj_iff e refine iSup_congr_Prop hadj fun h => ?_ congr 1 set m := (∑ v, ω v) / (Fintype.card V : ℝ) exact op_1710_inner_sum_eq T T' e ω m u v/-- Isomorphic trees have identical Kuramoto critical coupling cumulative distributions under exchangeable i.i.d. frequencies. -/theorem op_1710_kuramoto_coupling_iso_eq {V : Type*} [Fintype V] (T T' : SimpleGraph V) (e : T ≃g T') (μ : MeasureTheory.Measure ℝ) [MeasureTheory.IsProbabilityMeasure μ] (s : ℝ) : MeasureTheory.Measure.pi (fun (_ : V) ↦ μ) { ω | kuramoto_critical_coupling T ω ≤ s } = MeasureTheory.Measure.pi (fun (_ : V) ↦ μ) { ω | kuramoto_critical_coupling T' ω ≤ s } := by let F := MeasurableEquiv.piCongrLeft (fun _ : V ↦ ℝ) e.toEquiv have hmp : MeasureTheory.MeasurePreserving F (MeasureTheory.Measure.pi fun _ ↦ μ) (MeasureTheory.Measure.pi fun _ ↦ μ) := MeasureTheory.measurePreserving_piCongrLeft (fun _ ↦ μ) e.toEquiv have hpre := hmp.measure_preimage_equiv { ω | kuramoto_critical_coupling T' ω ≤ s } rw [← hpre] congr 1 ext ω have hF : F ω = fun v ↦ ω (e.symm v) := by ext v simp [F, MeasurableEquiv.coe_piCongrLeft, Equiv.piCongrLeft_apply] rfl change kuramoto_critical_coupling T ω ≤ s ↔ kuramoto_critical_coupling T' (F ω) ≤ s rw [hF, op_1710_kuramoto_coupling_comp_symm T T' e ω]