multiqubit_dof_inequality_fails
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
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.
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.
uses
Nat.le_inductionhave h : 3 * n < 2^n := by induction n, hn using Nat.le_induction with | base => norm_num
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.
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) hmThe 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`).
uses
Nat.pow_succrw [Nat.pow_succ] nlinarith
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.
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
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.
/-- 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