coprime_divisor_progression_graph
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
- coprime_divisor_progression_graph_decidable_adjAdjacency in the coprime divisor progression graph coprime_divisor_progression_graph n a b is decidable via Classical.decRel.
- op_657_half_degree_packing_of_min_degree_le_twoFor every squarefree natural number n with at least two distinct prime factors and any positive coprime integers a and b, if the coprime…
- op_652_half_degree_packing_of_min_degree_le_twoFor any natural number n ≥ 2 and integers a, b with b > 0, if the coprime divisor progression graph B has minimum degree at most 2 and…
- op_652_half_degree_packing_of_primeFor any prime p and integers a, b with b > 0, if the coprime divisor progression graph B has a perfect matching, then B contains at least…
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