truncated_add_cayley_exists_adj_of_not_mem
Let 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 adjacent to some vertex in A in the truncated Cayley graph on D with connection set Z - Z.
Statement
open scoped Pointwise in theorem truncated_add_cayley_exists_adj_of_not_mem {G : Type*} [AddCommGroup G] {A D Z : Set G} (hAD : A ⊆ D) (h0 : (0 : G) ∈ Z) (h_cov : D ⊆ A + Z) (x : D) (hx : x ∉ (Subtype.val ⁻¹' A : Set D)) : ∃ a : D, a ∈ (Subtype.val ⁻¹' A : Set D) ∧ (truncated_add_cayley D (Z - Z)).Adj x a
- Source
- arXiv:2611.05321 Lemma 2.2
- Verified
- 04 Nov 2026
- Axioms
Quot.soundpropext- Built on 1
- 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…
- 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 \subseteq G$ be subsets such that $A \subseteq D$, $0 \in Z$, and $D \subseteq A + Z$ (under pointwise addition). Let $x \in D$ be such that $x \notin A$ (viewed as a subset of the subtype $D$, i.e., $x \notin \operatorname{val}^{-1}(A)$). Then there exists $a \in D$ such that $a \in A$ (i.e., $a \in \operatorname{val}^{-1}(A)$) and $x$ is adjacent to $a$ in the graph truncated_add_cayley D (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
To show that every vertex x ∈ D ∖ A is adjacent to some vertex in A, we use the covering hypothesis D ⊆ A + Z to write x = a + z with a ∈ A and z ∈ Z. Since A ⊆ D, the element a is a vertex of D. The vertices x and a are distinct because a ∈ A while x ∉ A, and their difference -a + x = z = z - 0 belongs to Z - Z because z ∈ Z and 0 ∈ Z, satisfying the adjacency condition for the truncated Cayley graph.
There exists a vertex a ∈ D such that a ∈ A, reducing the goal to showing that x and a are adjacent in the truncated Cayley graph.
Since x ∈ D and D ⊆ A + Z, we have x ∈ A + Z. By definition of set addition (Set.mem_add.mp), x can be written as a + z for some a ∈ A and z ∈ Z. Since A ⊆ D, this element a belongs to D. Supplying a as the witness, the condition a ∈ A holds immediately, leaving only the requirement that x and a are adjacent in the truncated Cayley graph.
uses
Set.mem_add.mphave hx_cov : x.val ∈ A + Z := h_cov x.prop rcases Set.mem_add.mp hx_cov with ⟨a_val, ha, z, hz, hx_eq⟩ have haD : a_val ∈ D := hAD ha let a : D := ⟨a_val, haD⟩ use a refine ⟨ha, ?_⟩
To prove adjacency of x and a, it suffices to show that x ≠ a and -a + x ∈ Z - Z.
We unfold the definition of the truncated Cayley graph (truncated_add_cayley), the characterization of edges in an induced subgraph (SimpleGraph.induce_adj), and edges in an additive Cayley graph (SimpleGraph.addCayley_adj). Adjacency requires that x ≠ a and that either -x + a ∈ Z - Z or -a + x ∈ Z - Z. Choosing the right disjunct via Or.inr reduces the goal to proving x ≠ a and -a + x ∈ Z - Z.
uses
truncated_add_cayley,SimpleGraph.induce_adj,SimpleGraph.addCayley_adj,Or.inrrw [truncated_add_cayley, SimpleGraph.induce_adj, SimpleGraph.addCayley_adj] refine ⟨?_, Or.inr ?_⟩
x ≠ a
Suppose for contradiction that x = a. Since a ∈ A, this would imply x ∈ A, which contradicts the hypothesis that x ∉ A.
· intro h_eq apply hx change x.val ∈ A rw [h_eq] exact ha
-a + x ∈ Z - Z, which completes the proof of adjacency.
Substituting x = a + z, abelian group cancellation simplifies -a + (a + z) to z, establishing that -a + x = z. Since z = z - 0 with z ∈ Z and 0 ∈ Z, the definition of pointwise set subtraction (Set.sub_mem_sub) gives z - 0 ∈ Z - Z, which shows that -a + x ∈ Z - Z.
uses
sub_zero,Set.sub_mem_sub· have : -a.val + x.val = z := by rw [← hx_eq] change -a_val + (a_val + z) = z abel rw [this, ← sub_zero z] exact Set.sub_mem_sub hz h0
Set.mem_add.mp- An element of a sum of sets s + t can be decomposed as x + y with x ∈ s and y ∈ t.
truncated_add_cayley- The truncated Cayley graph on D with connection set S is the subgraph of the Cayley graph on G induced by the subset D.
SimpleGraph.induce_adj- Two vertices in an induced subgraph are adjacent if and only if they are adjacent in the ambient graph.
SimpleGraph.addCayley_adj- In an additive Cayley graph with connection set s, two vertices u and v are adjacent if and only if u ≠ v and either -u + v ∈ s or -v + u ∈ s.
Or.inr- If b holds, then the disjunction a ∨ b holds.
sub_zero- Subtracting zero from any element leaves it unchanged: a - 0 = a.
Set.sub_mem_sub- If a ∈ s and b ∈ t, then a - b ∈ s - t.
- Vertices of the graph are formalized as elements of the subtype corresponding to D, so membership in A is represented formally via the preimage under Subtype.val.
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/-- Every vertex outside A in D has a neighbor in A in the truncated Cayley graph with connection set Z - Z. -/theorem truncated_add_cayley_exists_adj_of_not_mem {G : Type*} [AddCommGroup G] {A D Z : Set G} (hAD : A ⊆ D) (h0 : (0 : G) ∈ Z) (h_cov : D ⊆ A + Z) (x : D) (hx : x ∉ (Subtype.val ⁻¹' A : Set D)) : ∃ a : D, a ∈ (Subtype.val ⁻¹' A : Set D) ∧ (truncated_add_cayley D (Z - Z)).Adj x a := by have hx_cov : x.val ∈ A + Z := h_cov x.prop rcases Set.mem_add.mp hx_cov with ⟨a_val, ha, z, hz, hx_eq⟩ have haD : a_val ∈ D := hAD ha let a : D := ⟨a_val, haD⟩ use a refine ⟨ha, ?_⟩ rw [truncated_add_cayley, SimpleGraph.induce_adj, SimpleGraph.addCayley_adj] refine ⟨?_, Or.inr ?_⟩ · intro h_eq apply hx change x.val ∈ A rw [h_eq] exact ha · have : -a.val + x.val = z := by rw [← hx_eq] change -a_val + (a_val + z) = z abel rw [this, ← sub_zero z] exact Set.sub_mem_sub hz h0