A short mixed bank has a translation or reflected collision
ProvedCouret.STROBO2TORS.recoh_short_bank_collision_dichotomycouret-programmecouret-unification-20261108
Let be an abelian group and a commutative ring. Let finite abelian groups embed additively and injectively into , with , and . Let , , and functions for satisfy and . Supply additive and such that on embedded , when and otherwise; on embedded , implies . Assume that injectivity of the full binary map implies existence of distinct selected indices whose binary map onto is surjective. For every triple , one of the following collisions exists:
- A nonzero with such that , their ordered squares agree, and all probe sums agree.
- Nonzero with , such that and are distinct, their ordered squares agree, and all probe sums agree.
No assumption is made directly; the stated information-set contract supplies the needed rank property.
Preamble
import Aesop
import Definitions.Def_Couret_RecohRankKernel_9b83850e485b
import Lean.Elab.Tactic.Omega
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Data.Finset.Card
import Mathlib.Data.Finset.Powerset
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Data.Fintype.Card
import Mathlib.Data.ZMod.Basic
import Mathlib.Tactic.Abel
import Mathlib.Tactic.Ring
import Mathlib.Tactic.Tauto
import Theorems.Thm_Couret_STROBO2TORS_recoh_binary_bank_kernel_or_injective
import Theorems.Thm_Couret_STROBO2TORS_recoh_binary_kernel_genuine_collision
import Theorems.Thm_Couret_STROBO2TORS_recoh_pivot_bank_has_genuine_collision
import Definitions.Def_Couret_RecohRankKernel_9b83850e485b
set_option autoImplicit false
/-!
RECOH: binary evaluation dichotomy and exact collision reduction.
This module eliminates a manual case split for arbitrary finite banks:
either a nonzero binary kernel exists or the binary evaluation is injective.
In the injective case it records the information-set selection as one
EXPLICIT hypothesis. It does not claim that selection for general rank.
The rank-one case has a separate certified branch and is not duplicated.
-/
namespace Couret.STROBO2TORS
variable {G : Type*} [AddCommGroup G] [DecidableEq G]
Formal statement
theorem recoh_short_bank_collision_dichotomy
{H V R : Type*}
[AddCommGroup H] [Fintype H]
[AddCommGroup V] [Fintype V]
[CommRing R]
(r s k : ℕ) (hr : 0 < r) (hk : k < r + s)
(hcardV : Fintype.card V = 3 ^ s)
(h2 : ∀ a : H, a + a = 0)
(h3 : ∀ a : V, (a + a) + a = 0)
(embH : H →+ G) (injH : Function.Injective embH)
(embV : V →+ G) (injV : Function.Injective embV)
(bank : Fin k → G → R)
(hadd : ∀ i : Fin k, ∀ a b : G,
bank i (a + b) = bank i a * bank i b)
(hval0 : ∀ i : Fin k, bank i 0 = 1)
(binary : Fin k → H →+ ZMod 2)
(hbinary0 : ∀ i : Fin k, ∀ a : H,
binary i a = 0 → bank i (embH a) = 1)
(hbinary1 : ∀ i : Fin k, ∀ a : H,
binary i a ≠ 0 → bank i (embH a) = -1)
(ternary : Fin k → V →+ ZMod 3)
(hternary : ∀ i : Fin k, ∀ a : V,
ternary i a = 0 → bank i (embV a) = 1)
(hinfo : Function.Injective
(fun a : H => fun i : Fin k => binary i a) →
∃ pivot : Fin r → Fin k,
Function.Injective pivot ∧
Function.Surjective
(fun a : H => fun j : Fin r => binary (pivot j) a))
(x y z : G) (hcard : ({x, y, z} : Finset G).card = 3) :
(∃ d : G, d ≠ 0 ∧ d + d = 0 ∧
({x, y, z} : Finset G) ≠ {x + d, y + d, z + d} ∧
(∀ q : G,
orderedSquare ({x, y, z} : Finset G) q =
orderedSquare ({x + d, y + d, z + d} : Finset G) q) ∧
(∀ i : Fin k,
recohTripleProbe (bank i) x y z =
recohTripleProbe (bank i) (x + d) (y + d) (z + d))) ∨
(∃ d v : G, d ≠ 0 ∧ d + d = 0 ∧
v ≠ 0 ∧ (v + v) + v = 0 ∧
({0, v, v + d} : Finset G) ≠ {0, -v, -v + d} ∧
(∀ q : G,
orderedSquare ({0, v, v + d} : Finset G) q =
orderedSquare ({0, -v, -v + d} : Finset G) q) ∧
(∀ i : Fin k,
recohTripleProbe (bank i) 0 v (v + d) =
recohTripleProbe (bank i) 0 (-v) (-v + d))) := by sorry
end Couret.STROBO2TORS
Source
Alexandre Couret, Couret — Additive reconstruction: STROBO-4, singleton collisions and RECOH formal proof artifacts, https://zenodo.org/records/23980513; archive COURET_MATHEMATIQUES_20261105.zip, SHA-256 19a3b59aee930df74cab79c27b29e014843bd17179a26fef1261ed6b5a651ab7; file RECOH/lean/RecohBinaryDichotomy.lean, lines 97–157; source file SHA-256 740733aa832d9a2d29988c8cbc79b0861bfba8e7e0e0aa8e9f9826db98ef1779; theorem Couret.STROBO2TORS.recoh_short_bank_collision_dichotomy