AFTD Auto-Formalizing Theoretical Domains

direct_sum_cover_maximal_independent_truncated_cayley

theoremverifiedformalization

Let 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. Then the preimage of A in D is a maximal independent set in the truncated Cayley graph on D with connection set Z - Z.

Statement

open scoped Pointwise in
theorem direct_sum_cover_maximal_independent_truncated_cayley {G : Type*} [AddCommGroup G]
    {A D Z : Set G} (hAD : A ⊆ D) (h0 : (0 : G) ∈ Z)
    (h_dir : is_direct_sum_set A Z) (h_cov : D ⊆ A + Z) :
    Maximal (truncated_add_cayley D (Z - Z)).IsIndepSet (Subtype.val ⁻¹' A)
Formalizes
arXiv:2611.05321 Lemma 2.2
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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₂…
  • truncated_add_cayley_indep_of_is_direct_sum_setIf 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_add_cayley_exists_adj_of_not_memLet A ⊆ D and Z be subsets of an additive abelian group G such that 0 ∈ Z and D ⊆ A + Z. Then every vertex of D not belonging to A is…

Read back from the Lean

Let $G$ be an additive commutative group, and let $A, D, Z$ be subsets of $G$. Assume that: 1. $A \subseteq D$, 2. $0 \in Z$, 3. $A$ and $Z$ form a direct sum set (is_direct_sum_set A Z), meaning that for all $a_1, a_2 \in A$ and $z_1, z_2 \in Z$, if $a_1 + z_1 = a_2 + z_2$ then $a_1 = a_2$ and $z_1 = z_2$, and 4. $D \subseteq A + Z$ (the Minkowski sum of $A$ and $Z$). Then the preimage of $A$ under the canonical coercion $\text{Subtype.val} : D \to G$ (that is, $A$ viewed as a subset of the subtype $D$) is a maximal independent set in the truncated additive Cayley graph truncated_add_cayley D (Z - Z) (the subgraph induced on $D$ of the Cayley graph on $G$ with connection set $Z - Z$).

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

The preimage of A in D is first shown to be an independent set in the truncated Cayley graph using the direct sum condition on A + Z. To establish maximality, any independent set y containing this preimage cannot contain an element x outside it, because the covering hypothesis D ⊆ A + Z guarantees that x is adjacent to some element in A ⊆ y, contradicting the independence of y.

  1. The preimage of A in D is an independent set, and to show it is maximal, it suffices to show that any independent set containing it contains no other elements.

    By lemma `truncated_add_cayley_indep_of_is_direct_sum_set`, the hypothesis that A + Z is a direct sum implies that the preimage of A in D is an independent set in the truncated Cayley graph on D with connection set Z - Z. To establish maximality, consider an arbitrary independent set y ⊆ D containing Subtype.val ⁻¹' A and an element x ∈ y; it suffices to show that x belongs to Subtype.val ⁻¹' A.

    line 7

    uses truncated_add_cayley_indep_of_is_direct_sum_set

      refine ⟨truncated_add_cayley_indep_of_is_direct_sum_set h_dir, fun y hy hsub x hx => ?_⟩
  2. Every element x ∈ y belongs to the preimage of A, completing the proof of maximality.

    Suppose, for contradiction, that x does not belong to the preimage of A. Since A ⊆ D, 0 ∈ Z, and D ⊆ A + Z, lemma `truncated_add_cayley_exists_adj_of_not_mem` yields a vertex a in the preimage of A that is adjacent to x in the truncated Cayley graph. Since the preimage of A is a subset of y, a belongs to y as well. But x and a are distinct adjacent vertices both in y, which contradicts the hypothesis that y is an independent set.

    lines 8–10

    uses truncated_add_cayley_exists_adj_of_not_mem

      by_contra hxA
      obtain ⟨a, ha, hadj⟩ := truncated_add_cayley_exists_adj_of_not_mem hAD h0 h_cov x hxA
      exact hy hx (hsub ha) hadj.ne hadj
truncated_add_cayley_indep_of_is_direct_sum_set
If the 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.
truncated_add_cayley_exists_adj_of_not_mem
If A ⊆ D, 0 ∈ Z, and D ⊆ A + Z, then every vertex in D outside the preimage of A is adjacent in the truncated Cayley graph with connection set Z - Z to some vertex in the preimage of A.

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/-- Direct sum covers yield maximal independent sets in truncated Cayley graphs (Lemma 2.2). -/theorem direct_sum_cover_maximal_independent_truncated_cayley {G : Type*} [AddCommGroup G]    {A D Z : Set G} (hAD : A ⊆ D) (h0 : (0 : G) ∈ Z)    (h_dir : is_direct_sum_set A Z) (h_cov : D ⊆ A + Z) :    Maximal (truncated_add_cayley D (Z - Z)).IsIndepSet (Subtype.val ⁻¹' A) := by  refine ⟨truncated_add_cayley_indep_of_is_direct_sum_set h_dir, fun y hy hsub x hx => ?_⟩  by_contra hxA  obtain ⟨a, ha, hadj⟩ := truncated_add_cayley_exists_adj_of_not_mem hAD h0 h_cov x hxA  exact hy hx (hsub ha) hadj.ne hadj
See it in the graphDiscuss this resultChallenge it