Theorem 5 — Spectrum of single-bit approximations
OpenAddXnor.Supplement.theorem_5add-xnorcryptographylinear-algebrap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix , let on states, and put
The bit- correlation factors over addition runs as ; is diagonalizable with the displayed eigenvalues; and
Finally , , and , with the stated equality case at and .
Differences from the source:
- encoding: diagonalizable with indexed eigenvalues → existence of an eigenvector matrix with nonzero determinant whose columns have exactly those indexed eigenvalues; reason: this is the finite-dimensional complex definition of the same claim
- encoding: uniform random operands and signed correlations → exact finite averages over
BitVecoperands; reason: finite-type encoding with identical uniform weights
Preamble
import Mathlib import Definitions.Def_AddXnor_Supplement_core set_option autoImplicit false
Formal statement
namespace AddXnor.Supplement
/-- **Theorem 5 (Spectrum of single-bit approximations)** (Wang, Lv, Shen, Zhang,
*Add/XNOR Chains*, manuscript, sha256 405d6dda..., Theorem 5, pp.17--18
(PDF pp.17--18)).
All four printed clauses are retained: run-factorization, the indexed eigenbasis and exact
spectral sum, the `ρ_j` bound, and the strict decay-rate comparison with its limit and equality
case. Bit indices are least-significant first. -/
theorem theorem_5 (m j : ℕ) (hj : 1 ≤ j) (hjm : j ≤ m - 1) :
(∀ (q : ℕ), 1 ≤ q → ∀ x : Fin q → Bool,
correlationAt (m := m) x j =
((additionRuns x).map (carryCorrelation j)).prod) ∧
HasIndexedEigenbasis (transferMatrix j) (eigenvalue j) ∧
(∀ z : ℕ,
(carryCorrelation j z : ℂ) =
(Real.rpow 2 (-((j * (z + 2) : ℕ) : ℝ)) : ℂ) *
∑ k : Fin (2 ^ j),
((‖eigenvalue j k‖ : ℝ) ^ 2) * (eigenvalue j k) ^ z) ∧
(∀ z : ℕ, |carryCorrelation j z| ≤ (rho j) ^ z) ∧
rho 1 = Real.rpow 2 (-(1 : ℝ) / 2) ∧
(∀ a : ℕ, 1 ≤ a → rho (a + 1) < rho a) ∧
Filter.Tendsto rho Filter.atTop (nhds (2 / Real.pi)) ∧
(∀ (a z : ℕ), 1 ≤ a →
|carryCorrelation a z| ≤ Real.rpow 2 (-(z : ℝ) / 2)) ∧
(∀ z : ℕ, z % 4 = 0 →
|carryCorrelation 1 z| = Real.rpow 2 (-(z : ℝ) / 2)) := by sorry
end AddXnor.Supplement
Source
Wang, Lv, Shen, Zhang, manuscript (sha256 405d6dda…), Theorem 5, pp.17–18 (PDF pp.17–18)