direct_sum_cover_maximal_independent_truncated_cayley
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.
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.
uses
truncated_add_cayley_indep_of_is_direct_sum_setrefine ⟨truncated_add_cayley_indep_of_is_direct_sum_set h_dir, fun y hy hsub x hx => ?_⟩
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.
uses
truncated_add_cayley_exists_adj_of_not_memby_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.
- The vertex set of the truncated Cayley graph is the subtype D, so the subset A ⊆ D is formalized as the preimage Subtype.val ⁻¹' A under the canonical inclusion D ↪ G.
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/-- 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