AFTD Auto-Formalizing Theoretical Domains

truncated_add_cayley_exists_adj_of_not_mem

theoremverified

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

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.

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

    lines 7–12

    uses Set.mem_add.mp

      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, ?_⟩
  2. 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.

    lines 13–14

    uses truncated_add_cayley, SimpleGraph.induce_adj, SimpleGraph.addCayley_adj, Or.inr

      rw [truncated_add_cayley, SimpleGraph.induce_adj, SimpleGraph.addCayley_adj]
      refine ⟨?_, Or.inr ?_⟩
  3. x ≠ a

    Suppose for contradiction that x = a. Since a ∈ A, this would imply x ∈ A, which contradicts the hypothesis that x ∉ A.

    lines 15–19

      · intro h_eq
        apply hx
        change x.val ∈ A
        rw [h_eq]
        exact ha
  4. -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.

    lines 20–25

    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.

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