Theorem C.15 — Characterisation of the CSinglAIP reduction
OpenAbelianPromises.Dichotomy.Supplement.csinglaip_characterisationLet and be finite ternary promise templates: and . Suppose that contains no constant tuple. The specific constraint singleton AIP transformation of Definition C.13 is a polynomial-time reduction exactly when there exists an arity- and minor-preserving map
The transformation first forms using the source template's domains, prunes constraint tuples by singleton AIP to a fixed point, and applies the universal -gadget to the residual Label Cover instance. Rejection outputs the single-variable instance with constraint . The left side requires both YES and NO preservation and a fixed finite program with polynomial step bounds for this construction. The right side is a family at every nonempty finite arity commuting with every minor map. The polymorphisms use the actual relation domains.
This companion theorem characterizes the entire reduction class and is not used in the proof of the mission's dichotomy goal. No symmetry, nonempty-relation, group, prime, rounding, or bounded-arity-cutoff assumption is added. Empty template domains and relations are included, with unsatisfiable intermediate data handled explicitly.
Differences from the source:
- encoding: arbitrary nonempty finite coordinate and column sets → all nonempty finite subsets of Nat for coordinates and Fin(j+1) for arbitrary finite columns; reason: a size-unbounded finite-set skeleton; bijective reindexing preserves every instance and minor.
- encoding: minor operations and the omega construction → the exact graph of each derived minor operation; reason: the graph records the same fibre-sum matrix and restricted minor without assuming derived closure facts.
- encoding: pruning to a fixed point and restricting domains → simultaneous tuple deletion for N0+1 rounds followed by all incident positional compatibility tests; reason: finite monotone deletion gives the same greatest fixed point, and fixed-point pinned feasibility makes all incident supports agree; isolated domains are unchanged.
- encoding: empty initial domains or relations interpreted as unsatisfiable → kappa returns rejection for any empty current domain or relation, including an initially empty isolated domain; reason: makes the nonempty-domain LC construction total on empty templates without removing any satisfiable source instance.
- encoding: the specified transformation Phi_S on finite instances → a polynomial-time bit machine outputs an instance isomorphic to the concrete quotient gadget Phi_S; reason: finite instances in the source have no prescribed variable or constraint numbering; both bijections preserve all ordered scopes, so this only specifies their encoding.
import Mathlib import Definitions.Def_AbelianPromises_Dichotomy_Supplement_Reduction import Definitions.Def_AbelianPromises_Dichotomy_Supplement_SkeletalOmega set_option autoImplicit false
namespace AbelianPromises.Dichotomy.Supplement
/-- Theorem C.15: both directions, arbitrary finite ternary promise templates.
No symmetry, nonempty-relation, group, or rounding hypothesis is added. -/
theorem csinglaip_characterisation
{A B C D : Type} [Fintype A] [Fintype B] [Fintype C] [Fintype D]
(R : Relation A) (Q : Relation B) (S : Relation C) (T : Relation D)
(hRQ : Hom R Q) (hST : Hom S T)
(hT : ∀ a : D, (fun _ : Fin 3 => a) ∉ T.rel ()) :
CSinglAIPReduction R Q S T ↔
HasMinionHom (omega (polPresentation S T hST)) (polPresentation R Q hRQ) := by sorry
end AbelianPromises.Dichotomy.Supplement