tarski_query_complexity_dim_le
General dimension simulation reduction: any query algorithm finding a fixed point in dimension k in at most q queries can be simulated in any lower dimension j ≤ k with at most q queries.
Statement
theorem tarski_query_complexity_dim_le (n j k q : ℕ) (hjk : j ≤ k) (h : tarski_query_complexity_le n k q) :
tarski_query_complexity_le n j q- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
Quot.soundpropext- Built on 2
- tarski_query_complexity_dim_le_succDimension reduction: any query algorithm finding a fixed point in dimension k + 1 in at most q queries can be simulated in dimension k…
- tarski_query_complexity_leTarski(n, k) ≤ q: some deterministic query algorithm finds a fixed point of every monotone map f : [n]^k → [n]^k (componentwise order)…
The proof, explained
The proof proceeds by induction on the difference d = k - j ≥ 0. In the base case d = 0, the dimensions coincide and the claim is trivial. For the inductive step, the dimension is decreased from (j + d) + 1 to j + d using the one-step dimension reduction lemma tarski_query_complexity_dim_le_succ, and the induction hypothesis then reduces the problem all the way to dimension j.
We can express k as j + d for some natural number d.
Since j ≤ k (hypothesis hjk), there exists some d such that k = j + d by Nat.exists_eq_add_of_le. We substitute j + d for k throughout.
uses
Nat.exists_eq_add_of_leobtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hjk
The base case d = 0 holds.
We argue by induction on the difference d. When d = 0, the dimension j + 0 simplifies to j, so the hypothesis h immediately yields the goal tarski_query_complexity_le n j q.
induction d with | zero => simpa using h
The query complexity bound holds in dimension (j + d) + 1.
In the inductive step d + 1, hypothesis h provides the query bound in dimension j + (d + 1). By associativity of addition (Nat.add_assoc), this is rewritten as dimension (j + d) + 1 to obtain hypothesis h'.
uses
Nat.add_assoc| succ d ih => have h' : tarski_query_complexity_le n (j + d + 1) q := by simpa [Nat.add_assoc] using hThe query complexity bound holds in dimension j + d.
Applying the single-step dimension reduction tarski_query_complexity_dim_le_succ to h' lowers the dimension from (j + d) + 1 to j + d with the same query bound q, giving hypothesis h''.
uses
tarski_query_complexity_dim_le_succhave h'' : tarski_query_complexity_le n (j + d) q := tarski_query_complexity_dim_le_succ n (j + d) q h'The query complexity bound holds in dimension j.
Applying the induction hypothesis ih to h'', together with the fact that j ≤ j + d (from Nat.le_add_right), completes the proof.
uses
Nat.le_add_rightexact ih (Nat.le_add_right j d) h''
Nat.exists_eq_add_of_le- If m ≤ n, there exists a natural number k such that n = m + k.
Nat.add_assoc- Addition of natural numbers is associative: (n + m) + k = n + (m + k).
tarski_query_complexity_dim_le_succ- If the Tarski fixed-point query complexity in dimension k + 1 is at most q, then in dimension k it is also at most q.
Nat.le_add_right- For any natural numbers n and k, n ≤ n + k.
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.
/-- Any query algorithm finding a fixed point in dimension k in at most q queries can be simulated in any dimension j ≤ k with at most q queries. -/theorem tarski_query_complexity_dim_le (n j k q : ℕ) (hjk : j ≤ k) (h : tarski_query_complexity_le n k q) : tarski_query_complexity_le n j q := by obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hjk induction d with | zero => simpa using h | succ d ih => have h' : tarski_query_complexity_le n (j + d + 1) q := by simpa [Nat.add_assoc] using h have h'' : tarski_query_complexity_le n (j + d) q := tarski_query_complexity_dim_le_succ n (j + d) q h' exact ih (Nat.le_add_right j d) h''