Random-order switching chain for single-cycle colored matchings
ProvedWeldedPath.single_cycle_switching_chainLet , with even and , and let be a valid properly three-colored welded-tree instance with nonempty single-cycle support. Let be the finite set of class-preserving edge permutations, and let be its single-cycle subset. There is a nonnegative joint weight on reference edge permutations and paths . Its reference marginal is uniform on ; every positive-weight path has ; and the marginal of is uniform on . For each fixed reference , each original edge , and each ,
The path index is the remaining matching size, so the random-order process runs from down to zero. A color class of size is padded with identity stages above ; its final deterministic stage may also be an identity. All distributions retain the original colored edge-permutation coordinates. The statement is the stochastic construction only: it asserts no bound on oracle answers and contains no quantum algorithm, label permutation, or query-count parameter. Endpoint disagreement and the harmonic estimate are proved separately from this certificate.
import Definitions.Def_WeldedPath_successProb
namespace WeldedPath
open Classical
open scoped BigOperators
/-- The random-order switching construction underlying Lemma 4.13 of Carolan et al.,
arXiv:2611.05912v1, Section 4.4, equation (76) and the subsequent coupling process.
The path is indexed backwards by the number of remaining entries: its last state is
the reference single-cycle edge permutation and its zeroth state has the product
law. An adjacent transition indexed by `i` corresponds to remaining count `i+1`.
Each color class uses its original colored matching coordinates; unused stages are
identity transitions. The statement concerns only forward images of fixed edges.
It contains neither labels nor quantum algorithms nor an oracle-disagreement bound. -/
theorem single_cycle_switching_chain :
∀ n l : ℕ, Even n → 2 ≤ l → l ≤ n - 4 →
∀ G : WeldedInstance n, G.IsValid → (G.singSupport l).Nonempty →
∃ v : Equiv.Perm G.edges →
(Fin (2 ^ n + 1) → Equiv.Perm G.edges) → ℝ,
(∀ h p, 0 ≤ v h p) ∧
(∀ h, (∑ p, v h p) =
if h ∈ ((Finset.univ.filter (G.IsEdgePerm l)).filter G.SingleCycle) then
1 / (((Finset.univ.filter (G.IsEdgePerm l)).filter G.SingleCycle).card : ℝ)
else 0) ∧
(∀ h p, v h p ≠ 0 → p (Fin.last (2 ^ n)) = h) ∧
(∀ g, (∑ h, ∑ p, if p 0 = g then v h p else 0) =
if g ∈ Finset.univ.filter (G.IsEdgePerm l) then
1 / ((Finset.univ.filter (G.IsEdgePerm l)).card : ℝ) else 0) ∧
(∀ h (e : G.edges) (i : Fin (2 ^ n)),
(∑ p, if (p i.castSucc) e ≠ (p i.succ) e then v h p else 0) ≤
(4 / ((2 : ℝ) ^ n * ((i.val : ℝ) + 1))) *
(if h ∈ ((Finset.univ.filter (G.IsEdgePerm l)).filter G.SingleCycle) then
1 / (((Finset.univ.filter (G.IsEdgePerm l)).filter G.SingleCycle).card : ℝ)
else 0)) := by
sorry
end WeldedPath