Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A complete finite alphabet for sensitivity recipe search

Definition
SensitivityWordFinite

by dmilosch · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

discrete-dynamicsexact-searchfinite-certificatessensitivity

For a fixed number NNN of states, a letter consists of target and gate maps into the state set, an auxiliary map into three values, and a tolerance map into six values. Its decoded recipe is the original recipe with each tolerance read as a natural number. Thus the ambient alphabet is finite, of cardinality

N2N18N.N^{2N}18^N.N2N18N.

Recipe validity remains exactly the original monotonicity predicate. No admissibility or growth conclusion is built into the data type. The alphabet can represent every admissible recipe's transfer map: tolerance values on the first three states are unused and may be replaced by zero; on all other states the admissibility condition already bounds the tolerance by five. That completeness assertion is proved separately in the search-correctness theorem.

Definition code
import Definitions.Def_SensitivityProfileWord

/-! A finite alphabet for exact searches over admissible recipe words. -/

set_option autoImplicit false

namespace SensitivityWordFinite
open SensitivityProfileCycle SensitivityProfileSearch SensitivityProfileWord

structure Letter (n : ℕ) where
  target : Fin n → Fin n
  gate : Fin n → Fin n
  aux : Fin n → Fin 3
  tol : Fin n → Fin 6
  deriving Fintype, DecidableEq

def Letter.recipe {n : ℕ} (C : Letter n) : Recipe n :=
  ⟨C.target, C.gate, C.aux, fun i => (C.tol i).val⟩

instance {n : ℕ} (C : Letter n) : Decidable C.recipe.Valid := by
  unfold Recipe.Valid Monotone
  infer_instance

end SensitivityWordFinite
Source
Original complete finite-search reduction of SensitivityProfileWord.exists_215_word, https://prove2.me/theorems/76888ed0-dff9-4b8d-b69f-5a603abeb564. Exact source definitions: SensitivityProfileWord.run, Admissible, Crosses215; SensitivityProfileSearch.step and envelope; SensitivityProfileCycle.Recipe.Valid. The recurrence originates in accepted submission a9d25c46-43bd-4fb1-826b-0ed075b8cf0a (yousofy with Codex), retaining OpenAI/math, Robin Kothari with Codex, and community attribution. The finite alphabet and dominance-pruning algorithm are new. No crossing witness or search-success bound is supplied or claimed to be known.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me