AFTD Auto-Formalizing Theoretical Domains

coprime_divisor_progression_graph

def

For a natural number n and integers a and b, the coprime divisor progression graph is the bipartite simple graph on the disjoint union of the positive divisors of n and the set of integers in the arithmetic progression image {a + bt : t ∈ {0, ..., |D(n)| - 1}}, with an edge between a divisor d and a progression term x if and only if d and x are coprime in ℤ.

Statement

def coprime_divisor_progression_graph (n : ℕ) (a b : ℤ) :
    SimpleGraph ({ d : ℕ // d ∈ Nat.divisors n } ⊕ { x : ℤ // x ∈ (Finset.range (Nat.divisors n).card).image (fun (t : ℕ) => a + b * (t : ℤ)) })
Defined in
arXiv:2610.37512
Verified
29 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

A definition of a simple graph coprime_divisor_progression_graph n a b parameterized by a natural number n and integers a and b. The vertex type is the disjoint sum V₁ ⊕ V₂, where: - V₁ = { d : ℕ // d ∈ Nat.divisors n } is the set of positive divisors of n. - V₂ = { x : ℤ // x ∈ (Finset.range (Nat.divisors n).card).image (fun t => a + b * (t : ℤ)) } is the set of values of the arithmetic progression a + b * t for 0 ≤ t < τ(n), where τ(n) is the number of divisors of n. Two vertices are adjacent if and only if one vertex is Sum.inl d (from V₁) and the other is Sum.inr x (from V₂) and d (cast to ℤ) is coprime to x (i.e., IsCoprime (d : ℤ) x). There are no edges between two vertices in V₁ or between two vertices in V₂.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The bipartite simple graph on D(n) and the progression image set {a + bt : 0 ≤ t < |D(n)|} with edges for coprimality. -/
def coprime_divisor_progression_graph (n : ℕ) (a b : ℤ) :
    SimpleGraph ({ d : ℕ // d ∈ Nat.divisors n } ⊕ { x : ℤ // x ∈ (Finset.range (Nat.divisors n).card).image (fun (t : ℕ) => a + b * (t : ℤ)) }) := SimpleGraph.fromRel fun u v =>
    match u, v with
    | Sum.inl d, Sum.inr x => IsCoprime (d.1 : ℤ) x.1
    | _, _ => False
See it in the graphDiscuss this resultChallenge it