AFTD Auto-Formalizing Theoretical Domains

op861_no_right_equivariant_k6_r3

theoremverified

There are no two selectors on the six-subsets of eleven cyclic colors that both choose available colors, differ on every pair of subsets intersecting in at most three points, and have the second selector commute with every cyclic rotation.

Statement

theorem op861_no_right_equivariant_k6_r3 :
    ¬ ∃ (f g : Finset (Fin 11) → Fin 11),
      (∀ S, S.card = 6 → f S ∈ S) ∧
      (∀ T, T.card = 6 → g T ∈ T) ∧
      (∀ T d, T.card = 6 → g (T.image (fun z => z + d)) = g T + d) ∧
      (∀ S T, S.card = 6 → T.card = 6 → (S ∩ T).card ≤ 3 → f S ≠ g T)
Source
arXiv:2610.42094, Definition 1.2; a finite obstruction to rotation-equivariant selector constructions for OP-861, discovered in recorded computations 22111 and 22121.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is proved by finite reduction and exhaustive computational verification. Given assumed selectors f and g, their choices on a fixed family of six 6-element subsets A_a and five 6-element subsets B_b of cyclic colors determine coordinate vectors v and w. An exhaustive verification by boolean reflection shows that every possible choice vector v is blocked by some subset B_j, meaning that for the choice g(B_j), some A_a intersects the shifted set B_j + (f(A_a) - g(B_j)) in at most 3 elements. By translation equivariance, g evaluates to f(A_a) on this shifted set, contradicting the requirement that f and g disagree on subsets intersecting in at most 3 elements.

  1. The precomputed fast table matches the actual intersection calculation for all index combinations. automation

    By boolean evaluation (`decide`), Lean confirms across all 1080 parameter combinations that the bitmask lookup `op861_fast` computes whether the shifted intersection has size at most 3.

    lines 14–15

    theorem op861_table_correct : ∀ (a : Fin 6) (b : Fin 5) (y x : Fin 6),
        op861_fast a b y x = op861_actual a b y x := by decide
  2. For each fixed value of the first index (0 to 5), the core condition evaluates to true for all remaining assignments. automation

    Exhaustive boolean checks (`decide`) verify that for each fixed value of the first coordinate from 0 to 5 and all 6^5 = 7776 configurations of the remaining five coordinates, at least one subset B_j has all elements blocked.

    lines 30–41

    theorem op861_actual_core_0 : ∀ (b c d e f : Fin 6), op861_full_core 0 b c d e f = true := by decide
    
    theorem op861_actual_core_1 : ∀ (b c d e f : Fin 6), op861_full_core 1 b c d e f = true := by decide
    
    theorem op861_actual_core_2 : ∀ (b c d e f : Fin 6), op861_full_core 2 b c d e f = true := by decide
    
    theorem op861_actual_core_3 : ∀ (b c d e f : Fin 6), op861_full_core 3 b c d e f = true := by decide
    
    theorem op861_actual_core_4 : ∀ (b c d e f : Fin 6), op861_full_core 4 b c d e f = true := by decide
    
    theorem op861_actual_core_5 : ∀ (b c d e f : Fin 6), op861_full_core 5 b c d e f = true := by decide
    
  3. The families of subsets A_a and B_b each contain subsets of cardinality 6 whose elements are indexed by their respective color functions. automation

    Direct computation (`decide`) verifies that the bitset representations of A_a and B_b have 6 elements and that the color arrays enumerate these sets.

    lines 49–53

    theorem op861_A_card : ∀ a : Fin 6, (op861_A a).card = 6 := by decide
    theorem op861_B_card : ∀ b : Fin 5, (op861_B b).card = 6 := by decide
    theorem op861_A_index : ∀ (a : Fin 6) (c : Fin 11), c ∈ op861_A a → ∃ x : Fin 6, op861_a_col a x = c := by decide
    theorem op861_B_index : ∀ (b : Fin 5) (c : Fin 11), c ∈ op861_B b → ∃ y : Fin 6, op861_b_col b y = c := by decide
    
  4. The full core blocking condition holds for every possible 6-tuple of indices.

    A case analysis on the first index a using `fin_cases` dispatches each of the six branches using the corresponding pre-verified core lemma (`op861_actual_core_0` through `op861_actual_core_5`).

    lines 54–62

    uses op861_actual_core_0, op861_actual_core_1, op861_actual_core_2, op861_actual_core_3, op861_actual_core_4, op861_actual_core_5

    theorem op861_all_core (a b c d e f : Fin 6) : op861_full_core a b c d e f = true := by
      fin_cases a
      · exact op861_actual_core_0 b c d e f
      · exact op861_actual_core_1 b c d e f
      · exact op861_actual_core_2 b c d e f
      · exact op861_actual_core_3 b c d e f
      · exact op861_actual_core_4 b c d e f
      · exact op861_actual_core_5 b c d e f
    
  5. Satisfaction of the full core condition implies that some subset B_j is blocked for all its elements.

    Unfolding the core blocking definitions (`op861_full_core`, `op861_block_all`, `op861_blocked`) and converting boolean operations to logical quantifiers via `Fin.exists_fin_succ`, `Fin.forall_fin_succ`, `or_assoc`, and `and_assoc` shows that there exists a subset index j such that every element index y in B_j is blocked by some choice A_a.

    lines 63–68

    uses op861_full_core, op861_block_all, op861_blocked, Fin.exists_fin_succ, Fin.forall_fin_succ, or_assoc, and_assoc

    theorem op861_core_implies_blocked (v : Fin 6 → Fin 6)
        (h : op861_full_core (v 0) (v 1) (v 2) (v 3) (v 4) (v 5) = true) :
        ∃ j : Fin 5, ∀ y : Fin 6, ∃ a : Fin 6, op861_fast a j y (v a) = true := by
      simpa [op861_full_core, op861_block_all, op861_blocked,
        Fin.exists_fin_succ, Fin.forall_fin_succ, or_assoc, and_assoc] using h
    
  6. Assume for contradiction that selectors f and g with the specified properties exist.

    We introduce the assumed selectors f and g together with their hypotheses: f selects from S (hf), g selects from T (hg), g commutes with cyclic shifts (heqv), and f and g disagree whenever |S ∩ T| ≤ 3 (hproper).

    lines 74–75

          (∀ S T, S.card = 6 → T.card = 6 → (S ∩ T).card ≤ 3 → f S ≠ g T) := by
      rintro ⟨f, g, hf, hg, heqv, hproper⟩
  7. The selections of f on each A_a and g on each B_b define choice vectors v and w of coordinate indices.

    Since each A_a and B_b has 6 elements (by `op861_A_card` and `op861_B_card`), the selected colors f(A_a) and g(B_b) belong to the sets. By `op861_A_index` and `op861_B_index`, each selected color is indexed by some coordinate in Fin 6, which we select using `Classical.choose` to form index vectors v and w.

    lines 76–83

    uses op861_A_index, op861_A_card, op861_B_index, op861_B_card, Classical.choose, Classical.choose_spec

      have ha (a : Fin 6) : ∃ x : Fin 6, op861_a_col a x = f (op861_A a) :=
        op861_A_index a _ (hf _ (op861_A_card a))
      have hb (b : Fin 5) : ∃ y : Fin 6, op861_b_col b y = g (op861_B b) :=
        op861_B_index b _ (hg _ (op861_B_card b))
      let v : Fin 6 → Fin 6 := fun a => Classical.choose (ha a)
      let w : Fin 5 → Fin 6 := fun b => Classical.choose (hb b)
      have hv (a : Fin 6) : op861_a_col a (v a) = f (op861_A a) := Classical.choose_spec (ha a)
      have hw (b : Fin 5) : op861_b_col b (w b) = g (op861_B b) := Classical.choose_spec (hb b)
  8. There exists a subset B_j and an index a such that the actual intersection test succeeds for the chosen elements.

    The vector v satisfies the full core condition by `op861_all_core`. Applying `op861_core_implies_blocked` identifies a subset B_j where every element is blocked; evaluating at the specific index y = w(j) gives an A_a whose fast check succeeds, which converts to the actual geometric condition via `op861_table_correct`.

    lines 84–88

    uses op861_all_core, op861_core_implies_blocked, op861_table_correct

      have hcore := op861_all_core (v 0) (v 1) (v 2) (v 3) (v 4) (v 5)
      obtain ⟨j, hj⟩ := op861_core_implies_blocked v hcore
      obtain ⟨a, hfast⟩ := hj (w j)
      have hactual : op861_actual a j (w j) (v a) = true := by
        simpa [op861_table_correct a j (w j) (v a)] using hfast
  9. The cyclic shift d aligning the selected element of B_j to that of A_a yields a 6-element subset whose intersection with A_a has cardinality at most 3.

    Setting d = f(A_a) - g(B_j), `op861_actual` implies that |A_a ∩ (B_j + d)| ≤ 3. Since translation is injective by `add_right_cancel`, `Finset.card_image_of_injective` together with `op861_B_card` ensures that the shifted set B_j + d has size 6.

    lines 89–93

    uses op861_actual, op861_A, op861_B, Finset.card_image_of_injective, add_right_cancel, op861_B_card

      let d : Fin 11 := op861_a_col a (v a) - op861_b_col j (w j)
      have hsmall : (op861_A a ∩ (op861_B j).image (fun z => z + d)).card ≤ 3 := by
        simpa [op861_actual, op861_A, op861_B, d] using hactual
      have hcard : ((op861_B j).image (fun z => z + d)).card = 6 := by
        rw [Finset.card_image_of_injective _ (fun x y h => add_right_cancel h), op861_B_card]
  10. Equivariance forces g(B_j + d) = f(A_a), contradicting the condition that f and g differ on sets with small intersection.

    By shift equivariance (`heqv`), g(B_j + d) = g(B_j) + d = f(A_a). Since A_a and B_j + d are both 6-element subsets intersecting in at most 3 points, the hypothesis `hproper` asserts that f(A_a) ≠ g(B_j + d), producing a contradiction.

    lines 94–97

    uses op861_B_card, add_comm, op861_A_card

      have hs : f (op861_A a) = g ((op861_B j).image (fun z => z + d)) := by
        rw [heqv _ d (op861_B_card j), ← hv a, ← hw j]
        simp [d, add_comm]
      exact hproper _ _ (op861_A_card a) hcard hsmall hs
and_assoc
Disjunction is associative: (a ∨ b) ∨ c ↔ a ∨ b ∨ c.
add_right_cancel
In an additive structure, right addition is cancellative: a + b = c + b implies a = c.
add_comm
Addition is commutative: a + b = b + a.
or_assoc
Conjunction is associative: (a ∧ b) ∧ c ↔ a ∧ b ∧ c.
Classical.choose
Given an existential proof, produces a witness element satisfying the predicate.
Classical.choose_spec
The witness returned by Classical.choose satisfies the underlying predicate.
Fin.exists_fin_succ
An existential statement over Fin (n + 1) is equivalent to the case 0 or an existential statement over the successors.
Fin.forall_fin_succ
A universal statement over Fin (n + 1) is equivalent to the case 0 and a universal statement over the successors.
Finset.card_image_of_injective
The image of a finite set under an injective function has the same size as the original set.
op861_A
Family of six 6-element subsets A_a of Fin 11.
op861_A_card
Every subset A_a has cardinality exactly 6.
op861_A_index
Every element in A_a is enumerated at some index in the color array for A_a.
op861_actual
The boolean test determining whether the intersection of A_a and shifted B_b has size at most 3.
op861_actual_core_0
When the first index is 0, the full core blocking condition holds for all choices of the remaining 5 indices.
op861_actual_core_1
When the first index is 1, the full core blocking condition holds for all choices of the remaining 5 indices.
op861_actual_core_2
When the first index is 2, the full core blocking condition holds for all choices of the remaining 5 indices.
op861_actual_core_3
When the first index is 3, the full core blocking condition holds for all choices of the remaining 5 indices.
op861_actual_core_4
When the first index is 4, the full core blocking condition holds for all choices of the remaining 5 indices.
op861_actual_core_5
When the first index is 5, the full core blocking condition holds for all choices of the remaining 5 indices.
op861_all_core
The full core blocking condition holds unconditionally for every 6-tuple of indices.
op861_B
Family of five 6-element subsets B_b of Fin 11.
op861_B_card
Every subset B_b has cardinality exactly 6.
op861_B_index
Every element in B_b is enumerated at some index in the color array for B_b.
op861_block_all
Boolean predicate testing whether all six elements of B_j are blocked by the given choices for A_0, ..., A_5.
op861_blocked
Boolean predicate testing whether the y-th element of B_j intersects some A_i in at most 3 points under the corresponding alignment shift.
op861_core_implies_blocked
If the full core condition holds for a choice function v, then some subset B_j has all of its elements blocked by some A_a.
op861_full_core
Boolean predicate testing whether at least one B_j has all of its elements blocked by the given choices for A_0, ..., A_5.
op861_table_correct
The precomputed bitmask table op861_fast agrees with the actual intersection size condition op861_actual for all indices.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

set_option maxRecDepth 8192set_option maxHeartbeats 0def op861_a_mask : Fin 6 → Nat := ![159, 287, 567, 231, 711, 683]def op861_b_mask : Fin 5 → Nat := ![63, 95, 159, 207, 215]def op861_a_col : Fin 6 → Fin 6 → Fin 11 := ![![0, 1, 2, 3, 4, 7], ![0, 1, 2, 3, 4, 8], ![0, 1, 2, 4, 5, 9], ![0, 1, 2, 5, 6, 7], ![0, 1, 2, 6, 7, 9], ![0, 1, 3, 5, 7, 9]]def op861_b_col : Fin 5 → Fin 6 → Fin 11 := ![![0, 1, 2, 3, 4, 5], ![0, 1, 2, 3, 4, 6], ![0, 1, 2, 3, 4, 7], ![0, 1, 2, 3, 6, 7], ![0, 1, 2, 4, 6, 7]]def op861_bitset (m : Nat) : Finset (Fin 11) := Finset.univ.filter (fun i => m.testBit i.val)def op861_fast_mask : Fin 6 → Fin 5 → Fin 6 → Nat := ![![![56, 48, 32, 33, 35, 7], ![60, 56, 48, 33, 35, 15], ![60, 56, 49, 35, 39, 31], ![60, 57, 51, 39, 31, 31], ![28, 57, 51, 46, 27, 23]], ![![28, 56, 48, 32, 33, 35], ![24, 48, 32, 32, 33, 7], ![28, 56, 49, 34, 37, 15], ![24, 49, 35, 38, 23, 15], ![24, 17, 35, 44, 19, 7]], ![![28, 24, 56, 48, 33, 35], ![28, 56, 56, 49, 35, 39], ![24, 25, 50, 36, 33, 7], ![27, 62, 52, 41, 39, 15], ![14, 61, 58, 19, 54, 45]], ![![56, 57, 59, 55, 39, 7], ![52, 40, 25, 59, 55, 6], ![54, 36, 8, 25, 59, 4], ![38, 4, 9, 27, 36, 8], ![36, 8, 25, 55, 4, 9]], ![![7, 15, 30, 28, 56, 56], ![6, 37, 10, 29, 26, 48], ![22, 36, 40, 25, 27, 33], ![54, 36, 41, 27, 52, 33], ![38, 37, 11, 30, 48, 41]], ![![14, 61, 30, 57, 62, 49], ![49, 30, 33, 62, 1, 2], ![6, 61, 14, 57, 30, 33], ![22, 61, 46, 57, 62, 37], ![33, 62, 1, 2, 6, 57]]]def op861_fast (a : Fin 6) (b : Fin 5) (y x : Fin 6) : Bool := (op861_fast_mask a b y).testBit x.valdef op861_actual (a : Fin 6) (b : Fin 5) (y x : Fin 6) : Bool :=  decide (((op861_bitset (op861_a_mask a)) ∩ (op861_bitset (op861_b_mask b)).image    (fun z => z + (op861_a_col a x - op861_b_col b y))).card ≤ 3)theorem op861_table_correct : ∀ (a : Fin 6) (b : Fin 5) (y x : Fin 6),    op861_fast a b y x = op861_actual a b y x := by decidedef op861_blocked (a b c d e f : Fin 6) (j : Fin 5) (y : Fin 6) : Bool :=  op861_fast 0 j y a || op861_fast 1 j y b || op861_fast 2 j y c ||  op861_fast 3 j y d || op861_fast 4 j y e || op861_fast 5 j y fdef op861_block_all (a b c d e f : Fin 6) (j : Fin 5) : Bool :=  op861_blocked a b c d e f j 0 && op861_blocked a b c d e f j 1 &&  op861_blocked a b c d e f j 2 && op861_blocked a b c d e f j 3 &&  op861_blocked a b c d e f j 4 && op861_blocked a b c d e f j 5def op861_full_core (a b c d e f : Fin 6) : Bool :=  op861_block_all a b c d e f 0 || op861_block_all a b c d e f 1 ||  op861_block_all a b c d e f 2 || op861_block_all a b c d e f 3 ||  op861_block_all a b c d e f 4theorem op861_actual_core_0 : ∀ (b c d e f : Fin 6), op861_full_core 0 b c d e f = true := by decidetheorem op861_actual_core_1 : ∀ (b c d e f : Fin 6), op861_full_core 1 b c d e f = true := by decidetheorem op861_actual_core_2 : ∀ (b c d e f : Fin 6), op861_full_core 2 b c d e f = true := by decidetheorem op861_actual_core_3 : ∀ (b c d e f : Fin 6), op861_full_core 3 b c d e f = true := by decidetheorem op861_actual_core_4 : ∀ (b c d e f : Fin 6), op861_full_core 4 b c d e f = true := by decidetheorem op861_actual_core_5 : ∀ (b c d e f : Fin 6), op861_full_core 5 b c d e f = true := by decideset_option maxHeartbeats 0set_option maxRecDepth 8192def op861_A (a : Fin 6) : Finset (Fin 11) := op861_bitset (op861_a_mask a)def op861_B (b : Fin 5) : Finset (Fin 11) := op861_bitset (op861_b_mask b)theorem op861_A_card : ∀ a : Fin 6, (op861_A a).card = 6 := by decidetheorem op861_B_card : ∀ b : Fin 5, (op861_B b).card = 6 := by decidetheorem op861_A_index : ∀ (a : Fin 6) (c : Fin 11), c ∈ op861_A a → ∃ x : Fin 6, op861_a_col a x = c := by decidetheorem op861_B_index : ∀ (b : Fin 5) (c : Fin 11), c ∈ op861_B b → ∃ y : Fin 6, op861_b_col b y = c := by decidetheorem op861_all_core (a b c d e f : Fin 6) : op861_full_core a b c d e f = true := by  fin_cases a  · exact op861_actual_core_0 b c d e f  · exact op861_actual_core_1 b c d e f  · exact op861_actual_core_2 b c d e f  · exact op861_actual_core_3 b c d e f  · exact op861_actual_core_4 b c d e f  · exact op861_actual_core_5 b c d e ftheorem op861_core_implies_blocked (v : Fin 6 → Fin 6)    (h : op861_full_core (v 0) (v 1) (v 2) (v 3) (v 4) (v 5) = true) :    ∃ j : Fin 5, ∀ y : Fin 6, ∃ a : Fin 6, op861_fast a j y (v a) = true := by  simpa [op861_full_core, op861_block_all, op861_blocked,    Fin.exists_fin_succ, Fin.forall_fin_succ, or_assoc, and_assoc] using htheorem op861_no_right_equivariant_k6_r3 :    ¬ ∃ (f g : Finset (Fin 11) → Fin 11),      (∀ S, S.card = 6 → f S ∈ S) ∧      (∀ T, T.card = 6 → g T ∈ T) ∧      (∀ T d, T.card = 6 → g (T.image (fun z => z + d)) = g T + d) ∧      (∀ S T, S.card = 6 → T.card = 6 → (S ∩ T).card ≤ 3 → f S ≠ g T) := by  rintro ⟨f, g, hf, hg, heqv, hproper⟩  have ha (a : Fin 6) : ∃ x : Fin 6, op861_a_col a x = f (op861_A a) :=    op861_A_index a _ (hf _ (op861_A_card a))  have hb (b : Fin 5) : ∃ y : Fin 6, op861_b_col b y = g (op861_B b) :=    op861_B_index b _ (hg _ (op861_B_card b))  let v : Fin 6 → Fin 6 := fun a => Classical.choose (ha a)  let w : Fin 5 → Fin 6 := fun b => Classical.choose (hb b)  have hv (a : Fin 6) : op861_a_col a (v a) = f (op861_A a) := Classical.choose_spec (ha a)  have hw (b : Fin 5) : op861_b_col b (w b) = g (op861_B b) := Classical.choose_spec (hb b)  have hcore := op861_all_core (v 0) (v 1) (v 2) (v 3) (v 4) (v 5)  obtain ⟨j, hj⟩ := op861_core_implies_blocked v hcore  obtain ⟨a, hfast⟩ := hj (w j)  have hactual : op861_actual a j (w j) (v a) = true := by    simpa [op861_table_correct a j (w j) (v a)] using hfast  let d : Fin 11 := op861_a_col a (v a) - op861_b_col j (w j)  have hsmall : (op861_A a ∩ (op861_B j).image (fun z => z + d)).card ≤ 3 := by    simpa [op861_actual, op861_A, op861_B, d] using hactual  have hcard : ((op861_B j).image (fun z => z + d)).card = 6 := by    rw [Finset.card_image_of_injective _ (fun x y h => add_right_cancel h), op861_B_card]  have hs : f (op861_A a) = g ((op861_B j).image (fun z => z + d)) := by    rw [heqv _ d (op861_B_card j), ← hv a, ← hw j]    simp [d, add_comm]  exact hproper _ _ (op861_A_card a) hcard hsmall hs
See it in the graphDiscuss this resultChallenge it