recursive_nae_contractive_normalized_recurrence_implies_upper_bound
If a positive fixed depth b and constants 0 ≤ θ < 1 and K ≥ 0 give a recurrence u(k+b) ≤ θu(k)+K for every k, where u(k) is the exact quantum query complexity of recursive ternary NAE at depth k divided by (3/√2)^k, then these query complexities are at most C(3/√2)^k for all k ≥ 1 for a positive constant C.
Statement
theorem recursive_nae_contractive_normalized_recurrence_implies_upper_bound (b : ℕ) (hb : 0 < b) (θ K : ℝ) (hθ₀ : 0 ≤ θ) (hθ₁ : θ < 1)
(hK : 0 ≤ K)
(hrec : ∀ k : ℕ,
(exact_quantum_query_complexity (recursive_nae (k + b)) : ℝ) /
(3 / Real.sqrt 2) ^ (k + b) ≤
θ * ((exact_quantum_query_complexity (recursive_nae k) : ℝ) /
(3 / Real.sqrt 2) ^ k) + K) :
∃ C : ℝ, 0 < C ∧ ∀ k : ℕ, 1 ≤ k →
(exact_quantum_query_complexity (recursive_nae k) : ℝ) ≤
C * (3 / Real.sqrt 2) ^ k- Source
- arXiv:2611.16412, Problem 12.2, fixed-depth recurrence implication
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- exact_quantum_query_complexityExact quantum query complexity Q_E(f) of a Boolean function f on N bits, defined as the minimum number of phase queries needed to evaluate…
- recursive_naeThe k-th recursive block composition F_k = NAE₃^{∘ k} of the ternary not-all-equal Boolean function on 3^k bits.
The proof, explained
The theorem is proved by normalizing the quantum query complexity by a^k = (3/√2)^k to obtain a sequence u(k) that satisfies the contractive recurrence u(k+b) ≤ θ u(k) + K. We set C = max(M, K/(1-θ)) + 1, where M is the maximum of u over the base indices 0 ≤ k < b, and prove u(n) ≤ C for all n by strong induction. In the inductive step n ≥ b, the recurrence and induction hypothesis yield u(n) ≤ θ C + (1-θ) C = C, and multiplying back by a^k delivers the upper bound.
Define the scaling base a = 3/√2, the normalized query complexity sequence u, the initial maximum M, and the candidate bound C.
We define the growth base a = 3/√2 and verify that a > 0 using positivity of real constants. We define the normalized query complexity u(k) = Q(recursive_nae(k)) / a^k. Since b > 0, the initial segment {0, ..., b - 1} is non-empty, so we can define M as the maximum of u over this range. Finally, we set C = max(M, K / (1 - θ)) + 1.
uses
Finset.mem_range.mprlet a : ℝ := 3 / Real.sqrt 2 have ha : 0 < a := by dsimp [a]; positivity let u : ℕ → ℝ := fun k => (exact_quantum_query_complexity (recursive_nae k) : ℝ) / a ^ k let M : ℝ := (Finset.range b).sup' (⟨0, Finset.mem_range.mpr hb⟩) u let C : ℝ := max M (K / (1 - θ)) + 1
The constant C is strictly positive.
Since K ≥ 0 and θ < 1, the denominator 1 - θ is strictly positive, so K / (1 - θ) ≥ 0. By definition, C = max(M, K / (1 - θ)) + 1 ≥ K / (1 - θ) + 1, so linear arithmetic yields C > 0.
uses
div_nonneg,le_of_lt,sub_pos.mpr,le_max_righthave hCp : 0 < C := by have : 0 ≤ K / (1 - θ) := div_nonneg hK (le_of_lt (sub_pos.mpr hθ₁)) dsimp [C]; linarith [le_max_right M (K / (1 - θ))]
For any n < b, the normalized complexity satisfies u(n) ≤ C.
We start a proof by strong induction on n that u(n) ≤ C for all natural numbers n, splitting into cases on whether n < b. When n < b, the index n belongs to the finite range {0, ..., b - 1}, so u(n) ≤ M by definition of M as the supremum over that range. Since C = max(M, K / (1 - θ)) + 1 ≥ M + 1 > M, linear arithmetic gives u(n) ≤ C.
uses
Nat.strong_induction_on,Finset.le_sup',Finset.mem_range.mpr,le_max_lefthave hbound : ∀ n, u n ≤ C := by intro n induction n using Nat.strong_induction_on with | h n ih => by_cases hn : n < b · have hM : u n ≤ M := Finset.le_sup' u (Finset.mem_range.mpr hn) dsimp [C]; linarith [le_max_left M (K / (1 - θ))]
For all natural numbers n, the normalized complexity satisfies u(n) ≤ C.
For the inductive step where n ≥ b, the shifted index n - b satisfies n - b < n, so the induction hypothesis gives u(n - b) ≤ C. Evaluating the given recurrence at n - b shows that u(n) ≤ θ * u(n - b) + K. Furthermore, C ≥ K / (1 - θ) + 1 > K / (1 - θ), which rearranges to K ≤ (1 - θ) * C since 1 - θ > 0. Combining these inequalities with θ ≥ 0 gives u(n) ≤ θ * C + (1 - θ) * C = C, closing the induction.
uses
Nat.le_of_not_gt,Nat.sub_lt,Nat.sub_add_cancel,le_max_right,mul_comm,div_le_iff₀,sub_pos.mpr,mul_nonneg,sub_nonneg.mpr· have hbn : b ≤ n := Nat.le_of_not_gt hn have hlt : n - b < n := Nat.sub_lt (by omega) hb have hind := ih (n - b) hlt have hr := hrec (n - b) have hrel : u n ≤ θ * u (n - b) + K := by rw [Nat.sub_add_cancel hbn] at hr simpa [u, a] using hr have hKC : K ≤ (1 - θ) * C := by have hh : K / (1 - θ) ≤ C := by dsimp [C]; linarith [le_max_right M (K / (1 - θ))] simpa [mul_comm] using (div_le_iff₀ (sub_pos.mpr hθ₁)).mp hh nlinarith [mul_nonneg hθ₀ (sub_nonneg.mpr hind)]
There exists C > 0 such that the exact quantum query complexity of recursive ternary NAE at depth k is at most C * (3/√2)^k for all k ≥ 1.
We provide C as the witness with the positivity proof hCp. For any k ≥ 1, the induction established u(k) ≤ C. Because a > 0, the power a^k = (3/√2)^k is strictly positive. Multiplying u(k) ≤ C by a^k clears the denominator in u(k), yielding the desired upper bound.
uses
pow_pos,div_le_iff₀refine ⟨C, hCp, ?_⟩ intro k hk have hh := hbound k have hkpos : 0 < a ^ k := pow_pos ha k exact (div_le_iff₀ hkpos).mp hh
Finset.mem_range.mpr- An integer m strictly less than n belongs to the finite range {0, ..., n - 1}.
div_nonneg- The quotient of two non-negative numbers is non-negative.
le_of_lt- A strict inequality implies the corresponding non-strict inequality.
sub_pos.mpr- If b < a, then the difference a - b is strictly positive.
le_max_right- Any value b is less than or equal to max(a, b).
Nat.strong_induction_on- The strong (complete) induction principle on natural numbers: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) for all m < n.
Finset.le_sup'- For any element in a non-empty finite set, its value under a function is bounded above by the supremum of that function over the set.
le_max_left- Any value a is less than or equal to max(a, b).
Nat.le_of_not_gt- If a natural number is not strictly greater than another, it is less than or equal to it.
Nat.sub_lt- Subtracting a positive natural number from another positive natural number strictly decreases it.
Nat.sub_add_cancel- If m ≤ n, then (n - m) + m = n for natural numbers.
mul_comm- Multiplication is commutative.
div_le_iff₀- For a strictly positive denominator c, b / c ≤ a if and only if b ≤ a * c.
mul_nonneg- The product of two non-negative numbers is non-negative.
sub_nonneg.mpr- If b ≤ a, then the difference a - b is non-negative.
pow_pos- Any natural power of a strictly positive number is strictly positive.
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 recursive_nae_contractive_normalized_recurrence_implies_upper_bound (b : ℕ) (hb : 0 < b) (θ K : ℝ) (hθ₀ : 0 ≤ θ) (hθ₁ : θ < 1) (hK : 0 ≤ K) (hrec : ∀ k : ℕ, (exact_quantum_query_complexity (recursive_nae (k + b)) : ℝ) / (3 / Real.sqrt 2) ^ (k + b) ≤ θ * ((exact_quantum_query_complexity (recursive_nae k) : ℝ) / (3 / Real.sqrt 2) ^ k) + K) : ∃ C : ℝ, 0 < C ∧ ∀ k : ℕ, 1 ≤ k → (exact_quantum_query_complexity (recursive_nae k) : ℝ) ≤ C * (3 / Real.sqrt 2) ^ k := by let a : ℝ := 3 / Real.sqrt 2 have ha : 0 < a := by dsimp [a]; positivity let u : ℕ → ℝ := fun k => (exact_quantum_query_complexity (recursive_nae k) : ℝ) / a ^ k let M : ℝ := (Finset.range b).sup' (⟨0, Finset.mem_range.mpr hb⟩) u let C : ℝ := max M (K / (1 - θ)) + 1 have hCp : 0 < C := by have : 0 ≤ K / (1 - θ) := div_nonneg hK (le_of_lt (sub_pos.mpr hθ₁)) dsimp [C]; linarith [le_max_right M (K / (1 - θ))] have hbound : ∀ n, u n ≤ C := by intro n induction n using Nat.strong_induction_on with | h n ih => by_cases hn : n < b · have hM : u n ≤ M := Finset.le_sup' u (Finset.mem_range.mpr hn) dsimp [C]; linarith [le_max_left M (K / (1 - θ))] · have hbn : b ≤ n := Nat.le_of_not_gt hn have hlt : n - b < n := Nat.sub_lt (by omega) hb have hind := ih (n - b) hlt have hr := hrec (n - b) have hrel : u n ≤ θ * u (n - b) + K := by rw [Nat.sub_add_cancel hbn] at hr simpa [u, a] using hr have hKC : K ≤ (1 - θ) * C := by have hh : K / (1 - θ) ≤ C := by dsimp [C]; linarith [le_max_right M (K / (1 - θ))] simpa [mul_comm] using (div_le_iff₀ (sub_pos.mpr hθ₁)).mp hh nlinarith [mul_nonneg hθ₀ (sub_nonneg.mpr hind)] refine ⟨C, hCp, ?_⟩ intro k hk have hh := hbound k have hkpos : 0 < a ^ k := pow_pos ha k exact (div_le_iff₀ hkpos).mp hh