AFTD Auto-Formalizing Theoretical Domains

op652_rel_decidable

instance

The coprimality relation on the model carriers is decidable (computably, via Int.gcd), so that kernel decide can evaluate degrees, matching conditions and cut counts on the 72-vertex model graph.

Statement

instance op652_rel_decidable : DecidableRel op652_rel
Source
step towards op_652_half_degree_packing_negation
Verified
29 Oct 2026
Axioms
none listed
Built on 3
  • op652_relThe adjacency relation of the coprime divisor-progression graph on the small carriers: a divisor d and a progression term x are related…
  • op652_progression_imageThe progression image {37 + 1·t : 0 ≤ t < 36} = {37, 38, …, 72}, as an explicit Finset ℤ.
  • op652_divisor_listThe 36 positive divisors of 1248191226 = 2·3²·37⁵, listed explicitly as a Finset ℕ.
Used by 1
  • op652_model_graphThe 72-vertex model graph: the same fromRel construction as coprime_divisor_progression_graph 1248191226 37 1, but on the explicit…

Lean source view module on GitHub

/-- Computable decidability of `op652_rel` (reduces to `Int.gcd`), enabling kernel `decide` on the model graph; built by case analysis on the two sides. -/
instance op652_rel_decidable : DecidableRel op652_rel := by
  intro u v
  cases u with
  | inl d => cases v with
    | inl d' => exact isFalse (by simp [op652_rel])
    | inr x  => exact decidable_of_iff (IsCoprime (d.1 : ℤ) x.1) (by simp [op652_rel])
  | inr x => cases v with
    | inl d  => exact isFalse (by simp [op652_rel])
    | inr x' => exact isFalse (by simp [op652_rel])
See it in the graphDiscuss this resultChallenge it