wild_binary_leaf_signature_collision_closed
For a properly colored complete graph whose vertex/color labels bijectively enumerate the nonzero elements of an exponent-two commutative group and whose edge labels add, take two disjoint triples each containing a pair separated by the same e. A collision of their leaf signatures modulo {0,e} forces their six-vertex union to be closed for some color whose missing vertex lies outside that union.
Statement
theorem wild_binary_leaf_signature_collision_closed {G : Type*} [AddCommGroup G] [DecidableEq G] {n : ℕ} (h2 : ∀ a : G, a + a = 0) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (lab : Fin n → G) (hinj : Function.Injective lab) (hnz : ∀ u, lab u ≠ 0) (hsurj : ∀ g : G, g ≠ 0 → ∃ u, lab u = g) (hcol : ∀ u v (h : u ≠ v), lab (c ⟨s(u,v), wild_kn_mem h⟩) = lab u + lab v) (e : G) (a b z d f w : Fin n) (hb : lab b = lab a + e) (hf : lab f = lab d + e) (hA : ({a,b,z} : Finset (Fin n)).card = 3) (hB : ({d,f,w} : Finset (Fin n)).card = 3) (hdis : Disjoint ({a,b,z} : Finset (Fin n)) {d,f,w}) (hsig : lab a + lab z = lab d + lab w ∨ lab a + lab z = lab d + lab w + e) : let U := ({a,b,z} : Finset (Fin n)) ∪ {d,f,w} U.card = 6 ∧ ∃ i : Fin n, i ∉ U ∧ w279_closed c i U
- Source
- OP-306 / IN-338 general-route helpers for the strict prescribed-coloring conjecture in arXiv:2610.22142, Sections3.3.2 and6. Structural analysis of binary factorizations and exact finite averaging in experiments8399,8400,8402,8414. These are conditional certificate or method-diagnostic lemmas, not a new wild-number bound or research advance.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- wild_two_leaf_signature_translation_sealIn a commutative group of exponent two, take two disjoint three-element sets {x,x+e,z} and {y,y+e,w} containing no zero. If x+z equals y+w…
- wild_closed_cut_of_additive_translationLet a proper complete-graph edge coloring have an injective labeling of its vertices and colors in an exponent-two commutative group, with…
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
The proof, explained
The proof transports the two disjoint vertex triples into the exponent-two group G via the injective labeling function. Under the collision of their leaf signatures modulo {0, e}, the lemma wild_two_leaf_signature_translation_seal shows that the element lab z + lab w is nonzero, lies outside the 6-element label union, and acts as a translation symmetry of that label union. Surjectivity yields an external vertex i with that label, and wild_closed_cut_of_additive_translation establishes that U is closed for color i.
Define the vertex sets A = {a, b, z}, B = {d, f, w}, and U = A ∪ B.
We enable classical logic and introduce names for the two triples of vertices and their six-vertex union.
classical let A : Finset (Fin n) := {a,b,z} let B : Finset (Fin n) := {d,f,w} let U := A ∪ B
The label sets of A and B are {lab a, lab a + e, lab z} and {lab d, lab d + e, lab w}.
Since lab b = lab a + e and lab f = lab d + e, simplifying the image of each triple under the labeling function replaces b and f with their shifted labels.
have hAI : A.image lab = {lab a, lab a + e, lab z} := by simp [A, hb] have hBI : B.image lab = {lab d, lab d + e, lab w} := by simp [B, hf]
The label sets of A and B each have cardinality 3.
Because lab is injective, taking the image of a finite set preserves its size (card_image_of_injective). Since A and B each have size 3, their images also have size 3.
uses
card_image_of_injectivehave hcardAI : ({lab a, lab a + e, lab z} : Finset G).card = 3 := by rw [← hAI, card_image_of_injective _ hinj] exact hA have hcardBI : ({lab d, lab d + e, lab w} : Finset G).card = 3 := by rw [← hBI, card_image_of_injective _ hinj] exact hB
The label sets of A and B are disjoint.
To show disjointness (disjoint_left.mpr), suppose an element g belongs to both label sets. Then g = lab u for some u ∈ A and g = lab v for some v ∈ B (mem_image.mp). By injectivity of lab, u = v, which contradicts the assumed disjointness of A and B (disjoint_left.mp).
uses
disjoint_left.mpr,mem_image.mp,disjoint_left.mphave hdisI : Disjoint ({lab a, lab a + e, lab z} : Finset G) {lab d, lab d + e, lab w} := by rw [← hAI, ← hBI] apply disjoint_left.mpr intro g hgA hgB obtain ⟨u, hu, he⟩ := mem_image.mp hgA obtain ⟨v, hv, he'⟩ := mem_image.mp hgB have huv := hinj (he.trans he'.symm) exact disjoint_left.mp hdis hu (huv ▸ hv)
The label set of U is the union of the label sets of A and B.
The image of a union is the union of the images (image_union), so the image of U = A ∪ B is the union of the explicit label sets computed for A and B.
uses
image_unionhave hUI : U.image lab = ({lab a, lab a + e, lab z} : Finset G) ∪ {lab d, lab d + e, lab w} := by change (A ∪ B).image lab = _ rw [image_union, hAI, hBI]
The zero element of G does not belong to the label set of U.
If 0 were in the image of U (mem_image.mp), it would be the label of some vertex in U, contradicting the hypothesis that every vertex has a nonzero label.
uses
mem_image.mphave hzero : (0 : G) ∉ ({lab a, lab a + e, lab z} : Finset G) ∪ {lab d, lab d + e, lab w} := by rw [← hUI] rintro hz obtain ⟨v, hv, he⟩ := mem_image.mp hz exact hnz v he
The shift lab z + lab w is nonzero, lies outside the label set of U, is invariant on U under addition, and is realized as the label of a vertex i.
The algebraic lemma wild_two_leaf_signature_translation_seal shows that under the leaf signature collision hypothesis in an exponent-two group, the shift lab z + lab w is nonzero, does not belong to lab(U), and satisfies v + (lab z + lab w) ∈ lab(U) for all v ∈ lab(U). By surjectivity of lab on nonzero elements, there exists a vertex i with lab i = lab z + lab w.
uses
wild_two_leaf_signature_translation_sealobtain ⟨_, hc, hcU, ht⟩ := wild_two_leaf_signature_translation_seal h2 e (lab a) (lab d) (lab z) (lab w) hcardAI hcardBI hdisI hzero hsig obtain ⟨i, hi⟩ := hsurj (lab z + lab w) hc
The union U has cardinality 6.
We supply i as the existential witness and split into subgoals. Because A and B are disjoint, the cardinality of U = A ∪ B is 3 + 3 = 6 (card_union_of_disjoint).
uses
card_union_of_disjointrefine ⟨?_, i, ?_, ?_⟩ · rw [card_union_of_disjoint hdis, hA, hB]
The vertex i does not belong to U.
If i were in U, its label lab i = lab z + lab w would belong to lab(U) (mem_image.mpr), which contradicts the fact established by the seal lemma that lab z + lab w ∉ lab(U).
uses
mem_image.mpr· intro hiU apply hcU rw [← hUI, ← hi] exact mem_image.mpr ⟨i, hiU, rfl⟩
The set U is closed for color i.
By wild_closed_cut_of_additive_translation, U is closed for color i if translating any vertex label in U by lab i stays within lab(U). Since lab i = lab z + lab w, this holds directly by the translation stability property from the seal lemma (mem_image.mpr).
uses
wild_closed_cut_of_additive_translation,mem_image.mpr· apply wild_closed_cut_of_additive_translation h2 c lab hinj hcol i U intro u hu rw [hi, hUI] apply ht rw [← hUI] exact mem_image.mpr ⟨u, hu, rfl⟩
card_image_of_injective- An injective function preserves the cardinality of a finite set: |f(s)| = |s|.
card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities: |s ∪ t| = |s| + |t|.
disjoint_left.mp- If two sets are disjoint, any element of the first does not belong to the second.
disjoint_left.mpr- Two sets are disjoint if no element of the first belongs to the second.
image_union- The image of a union of two sets under a function is the union of their images: f(s ∪ t) = f(s) ∪ f(t).
mem_image.mp- If an element belongs to the image of a set under a function, it is the image of some element of that set.
mem_image.mpr- If an element is the image of some element of a set under a function, it belongs to the image of that set.
wild_closed_cut_of_additive_translation- For an additive edge coloring over an exponent-two group, a subset of vertices U is closed for color i if adding the label of i to any vertex label in U remains within the label set of U.
wild_two_leaf_signature_translation_seal- In an exponent-two commutative group, two disjoint 3-element sets of the forms {x, x + e, z} and {y, y + e, w} avoiding 0 whose leaf signatures collide modulo {0, e} have a 6-element union U such that z + w ≠ 0, z + w ∉ U, and U is invariant under translation by z + w.
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.
open Finsetset_option maxHeartbeats 2500000theorem wild_binary_leaf_signature_collision_closed {G : Type*} [AddCommGroup G] [DecidableEq G] {n : ℕ} (h2 : ∀ a : G, a + a = 0) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (lab : Fin n → G) (hinj : Function.Injective lab) (hnz : ∀ u, lab u ≠ 0) (hsurj : ∀ g : G, g ≠ 0 → ∃ u, lab u = g) (hcol : ∀ u v (h : u ≠ v), lab (c ⟨s(u,v), wild_kn_mem h⟩) = lab u + lab v) (e : G) (a b z d f w : Fin n) (hb : lab b = lab a + e) (hf : lab f = lab d + e) (hA : ({a,b,z} : Finset (Fin n)).card = 3) (hB : ({d,f,w} : Finset (Fin n)).card = 3) (hdis : Disjoint ({a,b,z} : Finset (Fin n)) {d,f,w}) (hsig : lab a + lab z = lab d + lab w ∨ lab a + lab z = lab d + lab w + e) : let U := ({a,b,z} : Finset (Fin n)) ∪ {d,f,w} U.card = 6 ∧ ∃ i : Fin n, i ∉ U ∧ w279_closed c i U := by classical let A : Finset (Fin n) := {a,b,z} let B : Finset (Fin n) := {d,f,w} let U := A ∪ B have hAI : A.image lab = {lab a, lab a + e, lab z} := by simp [A, hb] have hBI : B.image lab = {lab d, lab d + e, lab w} := by simp [B, hf] have hcardAI : ({lab a, lab a + e, lab z} : Finset G).card = 3 := by rw [← hAI, card_image_of_injective _ hinj] exact hA have hcardBI : ({lab d, lab d + e, lab w} : Finset G).card = 3 := by rw [← hBI, card_image_of_injective _ hinj] exact hB have hdisI : Disjoint ({lab a, lab a + e, lab z} : Finset G) {lab d, lab d + e, lab w} := by rw [← hAI, ← hBI] apply disjoint_left.mpr intro g hgA hgB obtain ⟨u, hu, he⟩ := mem_image.mp hgA obtain ⟨v, hv, he'⟩ := mem_image.mp hgB have huv := hinj (he.trans he'.symm) exact disjoint_left.mp hdis hu (huv ▸ hv) have hUI : U.image lab = ({lab a, lab a + e, lab z} : Finset G) ∪ {lab d, lab d + e, lab w} := by change (A ∪ B).image lab = _ rw [image_union, hAI, hBI] have hzero : (0 : G) ∉ ({lab a, lab a + e, lab z} : Finset G) ∪ {lab d, lab d + e, lab w} := by rw [← hUI] rintro hz obtain ⟨v, hv, he⟩ := mem_image.mp hz exact hnz v he obtain ⟨_, hc, hcU, ht⟩ := wild_two_leaf_signature_translation_seal h2 e (lab a) (lab d) (lab z) (lab w) hcardAI hcardBI hdisI hzero hsig obtain ⟨i, hi⟩ := hsurj (lab z + lab w) hc refine ⟨?_, i, ?_, ?_⟩ · rw [card_union_of_disjoint hdis, hA, hB] · intro hiU apply hcU rw [← hUI, ← hi] exact mem_image.mpr ⟨i, hiU, rfl⟩ · apply wild_closed_cut_of_additive_translation h2 c lab hinj hcol i U intro u hu rw [hi, hUI] apply ht rw [← hUI] exact mem_image.mpr ⟨u, hu, rfl⟩