AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_exponential_histories

theoremverified

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

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|.

  1. 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.

    lines 5–13

    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
  2. 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.

    lines 14–20

    uses Finset.mem_singleton, PrioritizedBorelForkValid.root

      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
  3. 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.

    lines 21–27

    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], ?_, ?_, ?_⟩
  4. 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|.

    lines 28–29

          · have hm : 3 * S.card ≤ 2 * T.card := hb
            omega
  5. 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|.

    lines 30–36

    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
  6. 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.

    lines 37–43

    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.

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

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))
See it in the graphDiscuss this resultChallenge it