AFTD Auto-Formalizing Theoretical Domains

truncated_add_cayley_indep_of_is_direct_sum_set

theoremverified

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

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.

  1. 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.

    lines 6–7

      intro u hu v hv huv
      rintro ⟨-, h | h⟩
  2. 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.

    lines 8–13

    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)
  3. 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.

    lines 14–19

    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.

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

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
See it in the graphDiscuss this resultChallenge it