Recurrent cuts in a linked-pair factorization
Lax369799.LinkedPairFactorizations · concepts/Lax369799/LinkedPairFactorizations.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A linked-pair factorization can be thinned so that every cut visits the same vertex of a finite graph. Absorption and idempotence preserve the prefix and block values when successive blocks are grouped.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax369799.OmegaProducts |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Recurrent cuts in a linked-pair factorization |
| 6 | type: theorem |
| 7 | --- |
| 8 | A linked-pair factorization can be thinned so that every cut visits the |
| 9 | same vertex of a finite graph. Absorption and idempotence preserve the |
| 10 | prefix and block values when successive blocks are grouped. |
| 11 | -/ |
| 12 | |
| 13 | namespace Lax369799.LinkedPairFactorizations |
| 14 | open WordFactorization OmegaProducts |
| 15 | |
| 16 | axiom recurrent_factorization {M V : Type} [Monoid M] [Finite V] {u : ℕ} |
| 17 | (f : Fin u → M) (P : M → M → Prop) (w : ℕ → Fin u) (v : ℕ → V) |
| 18 | (h : Accepts f P w) : |
| 19 | ∃ (a e : M) (c : ℕ → ℕ) (r : V), P a e ∧ e * e = e ∧ a * e = a ∧ |
| 20 | StrictMono c ∧ 0 < c 0 ∧ (∀ i, v (c i) = r) ∧ |
| 21 | (∀ i, block (f ∘ w) 0 (c i) = a) ∧ |
| 22 | (∀ i j, i < j → block (f ∘ w) (c i) (c j) = e) |
| 23 | |
| 24 | end Lax369799.LinkedPairFactorizations |
| 25 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments