AFTD Auto-Formalizing Theoretical Domains

tarski_box_query_le_two_five

theoremverified

Small instance at the exact target parameters: in dimension 5 over the two-element grid, every box is solvable with at most 2^5 = 32 queries. Consequently the box invariant of the open target is inhabited at (n, k) = (2, 5), and any constant in the target must be at least 32.

Statement

theorem tarski_box_query_le_two_five : tarski_box_query_le 2 5 32
Source
step towards tarski_box_query_le_five_log_sq
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • tarski_box_query_le_smallBrute force on small boxes: if every box in dimension k has at most M points, then every box query is answerable within M queries — and in…
  • tarski_box_query_leBox-local Tarski query invariant: for every sub-box [a,b] (a ≤ b) of [n]^k there is a single deterministic query tree — depending only on…

The proof, explained

The theorem establishes that in dimension 5 over the two-element domain {0, 1}, any box can be solved in at most 32 queries. By tarski_box_query_le_small, it suffices to bound the volume of any box [a, b] by 32. In each of the 5 coordinates, the side length is at most 2, so the product of the side lengths is at most 2⁵ = 32.

  1. To show that the query complexity is at most 32, it suffices to prove that every box in {0, 1}⁵ has volume at most 32.

    Applying tarski_box_query_le_small reduces the query-complexity bound to showing that for any box [a, b] in (Fin 5 → Fin 2) with a ≤ b, the volume ∏ j : Fin 5, (b(j) - a(j) + 1) is at most 32. We introduce the endpoints a and b and the hypothesis a ≤ b.

    lines 3–4

    uses tarski_box_query_le_small

      apply tarski_box_query_le_small 2 5 32
      intro a b _hab
  2. In each coordinate j, the factor (b(j) - a(j) + 1) is at most 2.

    For any coordinate j ∈ Fin 5, since b(j) ∈ Fin 2, its value as a natural number satisfies b(j) < 2 by isLt. Presburger linear arithmetic (omega) then establishes that b(j) - a(j) + 1 ≤ 2.

    lines 5–8

    uses isLt

      have h1 : ∀ j : Fin 5, ((b j : ℕ) - (a j : ℕ) + 1) ≤ (2 : ℕ) := by
        intro j
        have : (b j : ℕ) < 2 := (b j).isLt
        omega
  3. The total box volume is bounded by the product of the coordinate upper bounds: ∏ j : Fin 5, (b(j) - a(j) + 1) ≤ ∏ _ : Fin 5, 2.

    We apply Finset.prod_le_prod to compare the products coordinate by coordinate. Non-negativity of each factor 0 ≤ b(j) - a(j) + 1 holds by linear arithmetic on ℕ (omega), and the upper bound b(j) - a(j) + 1 ≤ 2 is our previous step h1.

    lines 9–14

    uses Finset.prod_le_prod

      have h2 : (∏ j : Fin 5, ((b j : ℕ) - (a j : ℕ) + 1)) ≤ ∏ _ : Fin 5, (2 : ℕ) := by
        apply Finset.prod_le_prod
        · intro j _hj
          omega
        · intro j _hj
          exact h1 j
  4. The constant product ∏ _ : Fin 5, 2 evaluates to 32.

    The product of 2 over the 5-element domain Fin 5 is 2⁵ = 32, which is verified by direct computational reduction of decidable propositions (decide).

    lines 15–16

      have h3 : (∏ _ : Fin 5, (2 : ℕ)) = 32 := by
        decide
  5. The box volume is at most 32, completing the proof.

    Chaining the product inequality h2 with the numerical equality h3 yields ∏ j : Fin 5, (b(j) - a(j) + 1) ≤ 32, fulfilling the premise of tarski_box_query_le_small.

    line 17

      exact h2.trans_eq h3
tarski_box_query_le_small
If the volume of every subgrid box [a, b] in Fin k → Fin n is at most M, then the box query complexity is at most M.
isLt
For any element x of Fin n, its value as a natural number is strictly less than n.
Finset.prod_le_prod
If 0 ≤ f(i) ≤ g(i) for all elements i in a finite set s, then ∏ i ∈ s, f(i) ≤ ∏ i ∈ s, g(i).

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

/-- Non-vacuity witness at the target parameters: the box invariant is satisfiable in dimension 5 with 32 = 2^5 queries when n = 2, so the target's constant must satisfy C ≥ 32. -/theorem tarski_box_query_le_two_five : tarski_box_query_le 2 5 32 := by  apply tarski_box_query_le_small 2 5 32  intro a b _hab  have h1 : ∀ j : Fin 5, ((b j : ℕ) - (a j : ℕ) + 1) ≤ (2 : ℕ) := by    intro j    have : (b j : ℕ) < 2 := (b j).isLt    omega  have h2 : (∏ j : Fin 5, ((b j : ℕ) - (a j : ℕ) + 1)) ≤ ∏ _ : Fin 5, (2 : ℕ) := by    apply Finset.prod_le_prod    · intro j _hj      omega    · intro j _hj      exact h1 j  have h3 : (∏ _ : Fin 5, (2 : ℕ)) = 32 := by    decide  exact h2.trans_eq h3
See it in the graphDiscuss this resultChallenge it