prioritized_borel_fork_exponential_histories
For every history-dependent excursion response and every n, some common n-block output has at least (3/2)^n compatible hidden histories.
Statement
theorem prioritized_borel_fork_exponential_histories (color : List Bool → List Bool → Bool) (n : ℕ) :
∃ u : List Bool, ∃ S : Finset (List Bool),
u.length = n ∧ n + 1 ≤ S.card ∧ 3 ^ n ≤ 2 ^ n * S.card ∧
∀ h ∈ S, PrioritizedBorelForkValid color u h- Source
- arXiv:2611.10136, Section 5.3.2, smallest lower-bound arena; three-move fork obstruction
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- prioritized_borel_fork_majority_growthIf every history has a distinct stay extension and a distinct excursion extension colored by a bit, some common visible bit yields at…
- PrioritizedBorelForkValidBlockwise histories: every history may stay for an arbitrary visible bit, or take a hidden excursion only when the strategy chooses that…
- Used by 1
- prioritized_borel_fork_memory_fiber_unboundedFor every history-dependent response and every finite-memory assignment, arbitrarily many compatible hidden histories can reach one common…
The proof, explained
The theorem is proved by induction on the block length n. At each inductive step, each existing valid history can either 'stay' (appending false) or attempt to 'exit' (appending true), where exiting is valid only when the chosen output bit matches the history's excursion response. By a majority choice argument (prioritized_borel_fork_majority_growth), selecting the majority response bit ensures that the new set of valid histories grows by a factor of at least 3/2, preserving both the linear lower bound and the exponential bound 3^n ≤ 2^n * |S|.
Appending false or true to lists defines injective operations with disjoint images.
Appending any fixed suffix is injective by List.append_left_injective. Moreover, appending [false] and appending [true] produce disjoint images: if a ++ [false] = b ++ [true], applying List.getLast? via congrArg would imply some false = some true, an immediate contradiction.
uses
List.append_left_injective,congrArg,List.getLast?classical have hs : Function.Injective (fun h : List Bool => h ++ [false]) := List.append_left_injective [false] have he : Function.Injective (fun h : List Bool => h ++ [true]) := List.append_left_injective [true] have hdiff : ∀ a b : List Bool, a ++ [false] ≠ b ++ [true] := by intro a b h have hh := congrArg List.getLast? h simp at hh
The base case n = 0 holds with output u = [] and history set S = {[]}.
We proceed by induction on n. For n = 0, the empty list has length 0, the singleton set {[]} has size 1 ≥ 0 + 1, and 3^0 ≤ 2^0 * 1. The only history in this set is the empty list, which is valid for the empty output by PrioritizedBorelForkValid.root.
uses
Finset.mem_singleton,PrioritizedBorelForkValid.rootinduction n with | zero => refine ⟨[], {[]}, by simp, by simp, by simp, ?_⟩ intro h hh simp only [Finset.mem_singleton] at hh subst h exact PrioritizedBorelForkValid.root
In the inductive step, a majority bit exists that extends u to u ++ [bit] and forms a set T of compatible histories with 3|S| ≤ 2|T|.
Given the inductive hypothesis providing u of length n and compatible histories S, we apply prioritized_borel_fork_majority_growth with the stay map (appending false), exit map (appending true), and the response function color u. This yields a bit such that the union T of all stay extensions and matching exit extensions has cardinality at least (3/2)|S|, and appending bit extends u to length n + 1.
uses
prioritized_borel_fork_majority_growth| succ n ih => obtain ⟨u, S, hlen, hlinear, hgrowth, hvalid⟩ := ih obtain ⟨bit, hb⟩ := prioritized_borel_fork_majority_growth S (fun h => h ++ [false]) (fun h => h ++ [true]) hs he hdiff (color u) let T := (S.image (fun h => h ++ [false])) ∪ ((S.filter fun h => color u h = bit).image (fun h => h ++ [true])) refine ⟨u ++ [bit], T, by simp [hlen], ?_, ?_, ?_⟩The new history set satisfies the linear lower bound (n + 1) + 1 ≤ |T|. automation
From the induction hypothesis n + 1 ≤ |S| and the growth relation 3|S| ≤ 2|T|, linear integer arithmetic (omega) directly establishes (n + 1) + 1 ≤ |T|.
· have hm : 3 * S.card ≤ 2 * T.card := hb omega
The exponential bound 3^(n+1) ≤ 2^(n+1) * |T| holds.
We rewrite 3^(n+1) as 3 * 3^n, apply the induction hypothesis 3^n ≤ 2^n * |S| scaled by 3 via Nat.mul_le_mul_left, rearrange to 2^n * (3|S|), and substitute the growth inequality 3|S| ≤ 2|T| to arrive at 2^(n+1) * |T|.
uses
pow_succ,Nat.mul_comm,Nat.mul_le_mul_left· have hm : 3 * S.card ≤ 2 * T.card := hb calc 3 ^ (n+1) = 3 * 3 ^ n := by simp [pow_succ, Nat.mul_comm] _ ≤ 3 * (2 ^ n * S.card) := Nat.mul_le_mul_left 3 hgrowth _ = 2 ^ n * (3 * S.card) := by ring _ ≤ 2 ^ n * (2 * T.card) := Nat.mul_le_mul_left _ hm _ = 2 ^ (n+1) * T.card := by ring
Every history in T is valid for the extended output u ++ [bit].
Each history h in T is either a stay extension a ++ [false] for some a in S, or a matching exit extension a ++ [true] with color u a = bit. In the first case, h is valid for u ++ [bit] by PrioritizedBorelForkValid.stay. In the second case, since color u a = bit, h is valid by PrioritizedBorelForkValid.exit.
uses
Finset.mem_union.mp,Finset.mem_image.mp,Finset.mem_filter.mp,PrioritizedBorelForkValid.stay,PrioritizedBorelForkValid.exit· intro h hh rcases Finset.mem_union.mp hh with hs' | he' · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp hs' exact PrioritizedBorelForkValid.stay bit (hvalid a ha) · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp he' obtain ⟨haS, hcolor⟩ := Finset.mem_filter.mp ha simpa [hcolor] using (PrioritizedBorelForkValid.exit (hvalid a haS))
List.append_left_injective- Appending a fixed suffix to a list is an injective function.
congrArg- If two arguments are equal, applying any function to both produces equal values.
List.getLast?- Returns the last element of a list wrapped in some, or none if the list is empty.
Finset.mem_singleton- An element belongs to a singleton set if and only if it equals the unique member.
PrioritizedBorelForkValid.root- The empty history is valid for the empty output sequence.
prioritized_borel_fork_majority_growth- For any finite set with injective, disjoint stay and exit operations and a binary coloring, there is a bit whose matching exit set combined with the full stay set has size at least 3/2 times the original set.
pow_succ- The successor power a^(n+1) equals (a^n) * a in any monoid.
Nat.mul_comm- Multiplication of natural numbers is commutative.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers by a factor preserves the inequality.
Finset.mem_union.mp- An element belongs to a union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_image.mp- An element belongs to the image of a set under a function if and only if it is the image of some element in the set.
Finset.mem_filter.mp- An element belongs to a filtered set if and only if it belongs to the original set and satisfies the predicate.
PrioritizedBorelForkValid.stay- If a history is valid for an output sequence, then appending false to the history remains valid when extending the output by any bit.
PrioritizedBorelForkValid.exit- If a history is valid for an output sequence, then appending true to the history is valid when extending the output by the history's excursion response.
- In step 4, the linear bound (n + 1) + 1 ≤ |T| is deduced from 3|S| ≤ 2|T| and n + 1 ≤ |S| using Lean's omega tactic for Presburger arithmetic.
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.
theorem prioritized_borel_fork_exponential_histories (color : List Bool → List Bool → Bool) (n : ℕ) : ∃ u : List Bool, ∃ S : Finset (List Bool), u.length = n ∧ n + 1 ≤ S.card ∧ 3 ^ n ≤ 2 ^ n * S.card ∧ ∀ h ∈ S, PrioritizedBorelForkValid color u h := by classical have hs : Function.Injective (fun h : List Bool => h ++ [false]) := List.append_left_injective [false] have he : Function.Injective (fun h : List Bool => h ++ [true]) := List.append_left_injective [true] have hdiff : ∀ a b : List Bool, a ++ [false] ≠ b ++ [true] := by intro a b h have hh := congrArg List.getLast? h simp at hh induction n with | zero => refine ⟨[], {[]}, by simp, by simp, by simp, ?_⟩ intro h hh simp only [Finset.mem_singleton] at hh subst h exact PrioritizedBorelForkValid.root | succ n ih => obtain ⟨u, S, hlen, hlinear, hgrowth, hvalid⟩ := ih obtain ⟨bit, hb⟩ := prioritized_borel_fork_majority_growth S (fun h => h ++ [false]) (fun h => h ++ [true]) hs he hdiff (color u) let T := (S.image (fun h => h ++ [false])) ∪ ((S.filter fun h => color u h = bit).image (fun h => h ++ [true])) refine ⟨u ++ [bit], T, by simp [hlen], ?_, ?_, ?_⟩ · have hm : 3 * S.card ≤ 2 * T.card := hb omega · have hm : 3 * S.card ≤ 2 * T.card := hb calc 3 ^ (n+1) = 3 * 3 ^ n := by simp [pow_succ, Nat.mul_comm] _ ≤ 3 * (2 ^ n * S.card) := Nat.mul_le_mul_left 3 hgrowth _ = 2 ^ n * (3 * S.card) := by ring _ ≤ 2 ^ n * (2 * T.card) := Nat.mul_le_mul_left _ hm _ = 2 ^ (n+1) * T.card := by ring · intro h hh rcases Finset.mem_union.mp hh with hs' | he' · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp hs' exact PrioritizedBorelForkValid.stay bit (hvalid a ha) · obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp he' obtain ⟨haS, hcolor⟩ := Finset.mem_filter.mp ha simpa [hcolor] using (PrioritizedBorelForkValid.exit (hvalid a haS))