AFTD Auto-Formalizing Theoretical Domains

is_matchable

def

A natural number n is matchable if there exists an equivalence e : Fin (Nat.divisors n).card ≃ Nat.divisors n such that (e i : ℕ) and (i : ℕ) + 1 are coprime for all i : Fin (Nat.divisors n).card.

Statement

def is_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

The definition is_matchable n asserts that for a natural number n, there exists a bijection (equivalence) e from Fin (Nat.divisors n).card to Nat.divisors n such that for every i : Fin (Nat.divisors n).card, the divisor e(i) (viewed as a natural number) is coprime to (i : ℕ) + 1. In other words, if n has k divisors, they can be matched one-to-one with the integers 1, 2, ..., k such that each divisor is coprime to the integer it is paired with.

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 natural number n is matchable if D(n) admits a coprime matching with {1, 2, ..., tau(n)}. -/
def is_matchable (n : ℕ) : Prop := ∃ e : Fin (Nat.divisors n).card ≃ Nat.divisors n,
    ∀ i : Fin (Nat.divisors n).card, Nat.Coprime (e i : ℕ) ((i : ℕ) + 1)
See it in the graphDiscuss this resultChallenge it