op861_no_right_equivariant_k6_r3
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.
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.
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
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.
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
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.
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
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`).
uses
op861_actual_core_0,op861_actual_core_1,op861_actual_core_2,op861_actual_core_3,op861_actual_core_4,op861_actual_core_5theorem 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
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.
uses
op861_full_core,op861_block_all,op861_blocked,Fin.exists_fin_succ,Fin.forall_fin_succ,or_assoc,and_assoctheorem 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
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).
(∀ S T, S.card = 6 → T.card = 6 → (S ∩ T).card ≤ 3 → f S ≠ g T) := by rintro ⟨f, g, hf, hg, heqv, hproper⟩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.
uses
op861_A_index,op861_A_card,op861_B_index,op861_B_card,Classical.choose,Classical.choose_spechave 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)
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`.
uses
op861_all_core,op861_core_implies_blocked,op861_table_correcthave 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
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.
uses
op861_actual,op861_A,op861_B,Finset.card_image_of_injective,add_right_cancel,op861_B_cardlet 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]
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.
uses
op861_B_card,add_comm,op861_A_cardhave 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.
- The core combinatorial exhaustion (checking that every choice vector is blocked) is verified by boolean reflection using the `decide` tactic over a finite search space.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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