AFTD Auto-Formalizing Theoretical Domains

apx_search

def

Pruned search over candidate seat vectors for a list of profiles; succeeds iff every complete assignment contains a population paradox.

Statement

def apx_search (done : List ((Fin 4 → ℕ) × (Fin 4 → ℕ)))
    (todo : List ((Fin 4 → ℕ) × List (Fin 4 → ℕ))) : Bool
Source
step towards quota_population_monotone_incompatible_four_states_common_house (common-house-size variant left open by arXiv:2608.02759, Sec. 5; cf. arXiv:2202.11061, Sec. 3.1)
Verified
06 Oct 2026
Axioms
none listed
Built on 1
  • apx_paradoxBoolean test for a population paradox between two four-state profiles with given seat vectors.
Used by 2
  • apx_search_soundIf the pruned search succeeds, every seat assignment choosing candidates for the profiles has a population paradox between two of them.
  • apx_kernel_checkThe pruned search succeeds on the twelve profiles at house size 8 (kernel computation).

Lean source view module on GitHub

/-- Pruned search: assign each pending profile one of its candidate seat vectors; a branch is closed as soon as the new assignment forms a population paradox with an earlier one. Returns `true` iff every complete branch is closed. -/
def apx_search (done : List ((Fin 4 → ℕ) × (Fin 4 → ℕ)))
    (todo : List ((Fin 4 → ℕ) × List (Fin 4 → ℕ))) : Bool :=
  match todo with
  | [] => false
  | (p, cs) :: rest => cs.all fun a =>
      (done.any fun x => apx_paradox x.1 x.2 p a || apx_paradox p a x.1 x.2) ||
        apx_search ((p, a) :: done) rest
See it in the graphDiscuss this resultChallenge it