AFTD Auto-Formalizing Theoretical Domains

multiqubit_dof_inequality_fails

theoremverifiedformalization

For every n ≥ 4, the multiqubit degree-of-freedom inequality fails strictly: 4 * n < 2^n + n.

Statement

theorem multiqubit_dof_inequality_fails (n : ℕ) (hn : 4 ≤ n) : 4 * n < 2^n + n
Formalizes
arXiv:2611.16921 Sec. II.2 -- When can local unitaries generate a complete orthogonal basis?
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

Read back from the Lean

For every natural number $n$, if $4 \le n$, then $4n < 2^n + n$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

Subtracting n from both sides reduces the target inequality 4n < 2^n + n to 3n < 2^n. This auxiliary inequality is proved by induction on n starting at n = 4: the base case 12 < 16 is immediate, and the induction step decomposes 2^(m+1) into 2^m + 2^m to dominate 3m + 3. Finally, adding n back to both sides completes the proof.

  1. Base case: the lemma 3 * n < 2^n holds for n = 4.

    To prove 4n < 2^n + n, we first establish the stronger inequality 3n < 2^n by induction on n ≥ 4 using `Nat.le_induction`. For the base case n = 4, this reduces to 3 * 4 < 2^4 (that is, 12 < 16), which is verified by direct numerical evaluation.

    lines 3–5

    uses Nat.le_induction

      have h : 3 * n < 2^n := by
        induction n, hn using Nat.le_induction with
        | base => norm_num
  2. In the inductive step, 2^m ≥ 3 holds for any m ≥ 4.

    For the induction step at m ≥ 4, we establish the auxiliary lower bound 2^m ≥ 3. Since the base 2 is positive and 4 ≤ m, exponent monotonicity (`Nat.pow_le_pow_right`) gives 3 ≤ 4 ≤ 2^4 ≤ 2^m.

    lines 6–10

    uses Nat.pow_le_pow_right

        | succ m hm ih =>
          have h2 : (2:ℕ)^m ≥ 3 := by
            calc (3:ℕ) ≤ 4 := by norm_num
              _ ≤ 2^4 := by norm_num
              _ ≤ 2^m := Nat.pow_le_pow_right (by norm_num) hm
  3. The inductive step holds: 3 * (m + 1) < 2^(m + 1).

    We rewrite 2^(m + 1) as 2^m * 2 using `Nat.pow_succ`. Splitting 2^m * 2 into 2^m + 2^m, the inequality 3(m + 1) = 3m + 3 < 2^m + 2^m follows directly from the induction hypothesis 3m < 2^m and the lower bound 3 ≤ 2^m, closed by nonlinear arithmetic (`nlinarith`).

    lines 11–12

    uses Nat.pow_succ

          rw [Nat.pow_succ]
          nlinarith
  4. The main inequality 4 * n < 2^n + n holds for all n ≥ 4.

    Adding n to both sides of the lemma 3n < 2^n yields 4n < 2^n + n, which linear integer arithmetic (`omega`) closes immediately.

    line 13

      omega
Nat.le_induction
Induction principle on natural numbers starting from a base value m: if P(m) holds and P(k) implies P(k+1) for all k ≥ m, then P(n) holds for all n ≥ m.
Nat.pow_le_pow_right
For a positive base n > 0, the power function n^k is nondecreasing in the exponent: if i ≤ j, then n^i ≤ n^j.
Nat.pow_succ
Powers of natural numbers satisfy n^(m+1) = n^m * n.

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

/-- For n ≥ 4 qubits, the dimensional degree-of-freedom inequality fails: 4n < 2^n + n. -/theorem multiqubit_dof_inequality_fails (n : ℕ) (hn : 4 ≤ n) : 4 * n < 2^n + n := by  have h : 3 * n < 2^n := by    induction n, hn using Nat.le_induction with    | base => norm_num    | succ m hm ih =>      have h2 : (2:ℕ)^m ≥ 3 := by        calc (3:ℕ) ≤ 4 := by norm_num          _ ≤ 2^4 := by norm_num          _ ≤ 2^m := Nat.pow_le_pow_right (by norm_num) hm      rw [Nat.pow_succ]      nlinarith  omega
See it in the graphDiscuss this resultChallenge it