AFTD Auto-Formalizing Theoretical Domains

recursive_nae_contractive_normalized_recurrence_implies_upper_bound

theoremverified

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.

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

    lines 11–15

    uses Finset.mem_range.mpr

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

    lines 16–18

    uses div_nonneg, le_of_lt, sub_pos.mpr, le_max_right

      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 - θ))]
  3. 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.

    lines 19–25

    uses Nat.strong_induction_on, Finset.le_sup', Finset.mem_range.mpr, le_max_left

      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 - θ))]
  4. 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.

    lines 26–36

    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)]
  5. 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.

    lines 37–41

    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

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