AFTD Auto-Formalizing Theoretical Domains

is_strongly_matchable

def

A natural number n is strongly matchable if for every pair of natural numbers a and b with 0 < b and Nat.Coprime a b, there exists an equivalence e : Fin (Nat.divisors n).card ≃ Nat.divisors n such that (e i : ℕ) and a + b * (i : ℕ) are coprime for all i : Fin (Nat.divisors n).card.

Statement

def is_strongly_matchable (n : ℕ) : Prop
Defined in
arXiv:2610.37512 Section 1
Verified
28 Oct 2026
Axioms
none listed
Used by 1

Read back from the Lean

A natural number n is defined to be "strongly matchable" if for all natural numbers a and b such that b > 0 and a and b are coprime, there exists a bijection e between Fin (Nat.divisors n).card (the set {0, 1, ..., d - 1}, where d is the number of positive divisors of n) and the finset of divisors of n, such that for all i in Fin (Nat.divisors n).card, the divisor e(i) and the value a + b * i are coprime.

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

/-- A positive integer n is strongly matchable if its positive divisor set admits a coprime matching with every primitive arithmetic progression of length tau(n). -/
def is_strongly_matchable (n : ℕ) : Prop := ∀ (a b : ℕ), 0 < b → Nat.Coprime a b →
  ∃ e : Fin (Nat.divisors n).card ≃ Nat.divisors n,
    ∀ i : Fin (Nat.divisors n).card, Nat.Coprime (e i : ℕ) (a + b * (i : ℕ))
See it in the graphDiscuss this resultChallenge it