truncated_add_cayley_indep_of_is_direct_sum_set
If A and Z are subsets of an additive abelian group G whose sum A + Z is direct, then the preimage of A in D is an independent set in the truncated Cayley graph on D with connection set Z - Z.
Statement
open scoped Pointwise in theorem truncated_add_cayley_indep_of_is_direct_sum_set {G : Type*} [AddCommGroup G] {A D Z : Set G} (h_dir : is_direct_sum_set A Z) : (truncated_add_cayley D (Z - Z)).IsIndepSet (Subtype.val ⁻¹' A)
- Source
- arXiv:2611.05321 Lemma 2.2
- Verified
- 04 Nov 2026
- Axioms
Quot.soundpropext- Built on 2
- truncated_add_cayleyGiven a subset D and a connection set S in an additive abelian group G, the truncated Cayley graph on D with connection set S is the…
- is_direct_sum_setFor subsets A and Z of an additive abelian group G, the sum A + Z is direct if for all a₁, a₂ ∈ A and z₁, z₂ ∈ Z, a₁ + z₁ = a₂ + z₂…
- Used by 1
- direct_sum_cover_maximal_independent_truncated_cayleyLet G be an additive abelian group, and let A ⊆ D ⊆ G and Z ⊆ G be subsets with 0 ∈ Z. Suppose that the sum A + Z is direct and D ⊆ A + Z.…
Read back from the Lean
Let $G$ be an additive commutative group, and let $A, D, Z$ be subsets of $G$. If $A$ and $Z$ form a direct sum set (is_direct_sum_set A Z), then the preimage of $A$ under the subtype inclusion Subtype.val : D → G (i.e., the vertices in $D$ that belong to $A$) is an independent set in the truncated additive Cayley graph on $D$ with connection set $Z - Z$ (the pointwise difference of $Z$ with itself).
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
To show that the preimage of A in D forms an independent set in the truncated Cayley graph with connection set Z - Z, we assume for contradiction that two distinct vertices u, v ∈ D ∩ A are adjacent. Adjacency implies that either u + g = v or v + g = u for some difference g ∈ Z - Z. Writing g = z₁ - z₂ with z₁, z₂ ∈ Z, each equation rearranges into an equality of the form a₁ + z₁ = a₂ + z₂, which by the direct sum property of A + Z forces u = v, contradicting that the two vertices are distinct.
To show that the preimage of A in D is an independent set, it suffices to derive a contradiction from the existence of an edge between distinct vertices u, v ∈ D with values in A, which means either u + g = v or v + g = u for some g ∈ Z - Z.
By definition, a set of vertices in a simple graph is independent if no two distinct vertices in the set are adjacent. We assume for contradiction that there exist distinct vertices u, v in D whose values lie in A and that share an edge in the truncated Cayley graph with connection set Z - Z. Unfolding the definition of adjacency in the induced Cayley graph, an edge between u and v requires u ≠ v and either u + g = v or v + g = u for some element g in the connection set Z - Z.
intro u hu v hv huv rintro ⟨-, h | h⟩In the forward case where u + g = v, the direct sum property of A + Z forces u = v, contradicting u ≠ v.
Since g ∈ Z - Z, there exist z₁, z₂ ∈ Z such that g = z₁ - z₂ (via Set.mem_sub.mp). The equality u + (z₁ - z₂) = v is rewritten using associativity and group subtraction (add_sub_assoc and sub_eq_iff_eq_add) as u + z₁ = v + z₂. Because the sum A + Z is direct, any element has a unique representation as a sum of an element in A and an element in Z; since u, v ∈ A and z₁, z₂ ∈ Z, this implies u = v in G. Applying Subtype.ext shows that u and v are equal as vertices of D, contradicting the hypothesis that u ≠ v.
uses
Set.mem_sub.mp,sub_eq_iff_eq_add,add_sub_assoc,Subtype.ext· obtain ⟨g, hg, hguv⟩ := h obtain ⟨z₁, hz₁, z₂, hz₂, rfl⟩ := Set.mem_sub.mp hg have h' : u.val + z₁ = v.val + z₂ := by rw [← sub_eq_iff_eq_add, add_sub_assoc] exact hguv exact huv (Subtype.ext (h_dir u.val hu z₁ hz₁ v.val hv z₂ hz₂ h').1)
In the backward case where v + g = u, the direct sum property likewise forces u = v, contradicting u ≠ v.
Symmetrically, writing g = z₁ - z₂ with z₁, z₂ ∈ Z (via Set.mem_sub.mp), the equality v + (z₁ - z₂) = u rearranges via add_sub_assoc and sub_eq_iff_eq_add to v + z₁ = u + z₂. By the direct sum property of A + Z, this implies v = u in G, hence u = v as vertices by Subtype.ext, contradicting u ≠ v and completing the proof.
uses
Set.mem_sub.mp,sub_eq_iff_eq_add,add_sub_assoc,Subtype.ext· obtain ⟨g, hg, hgvu⟩ := h obtain ⟨z₁, hz₁, z₂, hz₂, rfl⟩ := Set.mem_sub.mp hg have h' : v.val + z₁ = u.val + z₂ := by rw [← sub_eq_iff_eq_add, add_sub_assoc] exact hgvu exact huv (Subtype.ext (h_dir v.val hv z₁ hz₁ u.val hu z₂ hz₂ h').1).symm
Set.mem_sub.mp- An element of the pointwise difference of two sets X - Y can be written as x - y for some x ∈ X and y ∈ Y.
sub_eq_iff_eq_add- In an additive group, a - b = c holds if and only if a = c + b.
add_sub_assoc- In an additive group, subtraction and addition associate as (a + b) - c = a + (b - c).
Subtype.ext- Two elements of a subtype are equal if their underlying values in the ambient type are equal.
- The vertices of the truncated Cayley graph on D are formally represented as elements of the subtype {x // x ∈ D}. The preimage `Subtype.val ⁻¹' A` corresponds to the vertices whose underlying group elements belong to A (i.e., D ∩ A), and `Subtype.ext` is required formally to deduce equality of vertices from equality of their group elements.
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 scoped Pointwise in/-- A direct sum component forms an independent set in the truncated Cayley graph with connection set Z - Z. -/theorem truncated_add_cayley_indep_of_is_direct_sum_set {G : Type*} [AddCommGroup G] {A D Z : Set G} (h_dir : is_direct_sum_set A Z) : (truncated_add_cayley D (Z - Z)).IsIndepSet (Subtype.val ⁻¹' A) := by intro u hu v hv huv rintro ⟨-, h | h⟩ · obtain ⟨g, hg, hguv⟩ := h obtain ⟨z₁, hz₁, z₂, hz₂, rfl⟩ := Set.mem_sub.mp hg have h' : u.val + z₁ = v.val + z₂ := by rw [← sub_eq_iff_eq_add, add_sub_assoc] exact hguv exact huv (Subtype.ext (h_dir u.val hu z₁ hz₁ v.val hv z₂ hz₂ h').1) · obtain ⟨g, hg, hgvu⟩ := h obtain ⟨z₁, hz₁, z₂, hz₂, rfl⟩ := Set.mem_sub.mp hg have h' : v.val + z₁ = u.val + z₂ := by rw [← sub_eq_iff_eq_add, add_sub_assoc] exact hgvu exact huv (Subtype.ext (h_dir v.val hv z₁ hz₁ u.val hu z₂ hz₂ h').1).symm