Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

mme_laser_per_N_witness

Disproved

by Shuze Chen · Jun 1, 2026 · Mathlib 777aaa6 (Lean v4.29.0-rc3)

asymptoticlaser-methodmatrix-multiplication-exponenttensor-rank

Per-(N, ε\varepsilonε) polynomial-bounded laser-method witness at a fixed probability distribution π\piπ. For a ttt-way mode-graded 3-tensor T:TensorObj K 3T : \mathrm{TensorObj}\,K\,3T:TensorObjK3 with cyclic-symmetric laser support S⊆(Fin t)3S \subseteq (\mathrm{Fin}\,t)^3S⊆(Fint)3, laser-aligned grading GGG, and probability distribution π\piπ supported on SSS, let V(π):=exp⁡(log⁡2⋅(H(π)+13∑σπ(σ)log⁡2(d0 d1 d2)))V(\pi) := \exp(\log 2 \cdot (H(\pi) + \frac{1}{3} \sum_\sigma \pi(\sigma) \log_2(d_0\,d_1\,d_2)))V(π):=exp(log2⋅(H(π)+31​∑σ​π(σ)log2​(d0​d1​d2​))) be the closed-form Wigderson--Zuiddam laser value at π\piπ. Then V(π)≥1V(\pi) \ge 1V(π)≥1 and there exists a polynomial degree ccc such that for every ε>0\varepsilon > 0ε>0, frequently many N∈NN \in \mathbb{N}N∈N admit (k,a,b,c′)(k, a, b, c')(k,a,b,c′) with k≤(N+1)ck \le (N+1)^ck≤(N+1)c, a Restrict\mathrm{Restrict}Restrict from ⨁iMMObj K (ai,bi,ci′)\bigoplus_i \mathrm{MMObj}\,K\,(a_i, b_i, c'_i)⨁i​MMObjK(ai​,bi​,ci′​) into T⊗NT^{\otimes N}T⊗N, and the H"older lower bound V(π)N(1−ε)≤∑i(aibici′)1/3V(\pi)^N (1-\varepsilon) \le \sum_i (a_i b_i c'_i)^{1/3}V(π)N(1−ε)≤∑i​(ai​bi​ci′​)1/3. This is the per-NNN analytic-combinatorial core of the WZ §6 / CW 1990 §5--§7 construction at a single π\piπ, absorbing the six Layer-4 leaves (3AP-free, Salem--Spencer, graded tensor power decomposition, independent direct-sum restriction, block-tensor MM identification, dimension count) plus the Stirling/H"older final optimization.

Preamble
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Analysis.SpecialFunctions.Log.Basic
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.LinearAlgebra.FiniteDimensional.Basic
import Mathlib.Order.Filter.AtTopBot.Defs
import Definitions.Def_mme_laser_pattern
import Definitions.Def_mme_subrank_capacity_poly
import Definitions.Def_mme_tensor_type_grading
import Definitions.Def_mme_tensor_rank

open MME BigOperators Filter

universe u
Formal statement
/-- **Per-(N, ε) polynomial-bounded laser-method witness at a fixed
probability distribution π.**

For a `t`-way mode-graded 3-tensor `T : TensorObj K 3` with cyclic-symmetric
laser support `S ⊆ (Fin t)^3`, laser-aligned grading `G`, and a probability
distribution `π : (Fin t × Fin t × Fin t) → ℝ` supported on `S`: the
closed-form Wigderson–Zuiddam laser value at `π`,

  `V(π) = exp(log 2 · ( H(π) + (1/3) · Σ_σ π(σ) · log₂(d₀(σ)·d₁(σ)·d₂(σ)) ))`

admits the polynomial-bounded witness construction defining
`subrankCapacityPoly T`. Concretely:

* `V(π) ≥ 1` (since `H(π) ≥ 0` and the type-dimensions are positive
  integers, so the log-arg is `≥ 1`); and
* there is a polynomial degree `c` (depending on `π, G, S`) such that for
  every `ε > 0` and frequently many `N`, one can exhibit `(k, a, b, c')`
  with `k ≤ (N+1)^c`, a `Restrict` from `⨁ᵢ MMObj K (aᵢ bᵢ c'ᵢ)` into
  `T^{⊗N}`, and the Hölder-controlled lower bound
  `V(π)^N · (1 - ε) ≤ ∑ᵢ (aᵢ·bᵢ·c'ᵢ)^{1/3}`.

This is the **direct unwrapping** of the WZ §6 / CW 1990 §5–§7 construction
at a single `π`. Conceptually it bundles the six Layer-4 leaves
(`mme_3AP_free_no_collision`, `mme_salem_spencer_eps_form`,
`mme_graded_tensor_pow_block_decomp`,
`mme_independent_blocks_form_direct_sum_restrict_enum`,
`mme_laser_block_dimension_count_refined`,
`mme_block_tensor_is_matMul_kronPow_balanced`) plus the Stirling / Hölder
final optimization step.

**Status.** Open. Decomposes the value bound at one π into the per-N
construction, which is the deep analytic core.

**Reduction role.** Together with the paper-agnostic abstract bridge
`mme_subrankCapacityPoly_ge_of_witnesses`, this leaf proves the parent
`mme_laser_witness_at_prob_dist`. -/
theorem mme_laser_per_N_witness
    {K : Type u} [Field K] {T : TensorObj K 3} {t : ℕ}
    (G : T.TypeGrading t) (S : Finset (Fin t × Fin t × Fin t))
    (_hSym : LaserSymmetric S)
    (_hsupport : TensorObj.LaserAlignedSupport G S)
    (π : (Fin t × Fin t × Fin t) → ℝ)
    (_hπ_supp : ∀ σ, σ ∉ S → π σ = 0)
    (_hπ_nn : ∀ σ, 0 ≤ π σ)
    (_hπ_sum : (∑ σ ∈ S, π σ) = 1) :
    let V : ℝ :=
      Real.exp (Real.log 2 *
        ( (-(∑ σ ∈ S, π σ * (Real.log (π σ) / Real.log 2)))
        + (1 / 3) *
            (∑ σ ∈ S, π σ *
              (Real.log
                  (((Module.finrank K (G.classOf 0 σ.1) : ℕ) : ℝ) *
                   ((Module.finrank K (G.classOf 1 σ.2.1) : ℕ) : ℝ) *
                   ((Module.finrank K (G.classOf 2 σ.2.2) : ℕ) : ℝ))
                / Real.log 2)) ) )
    (1 ≤ V) ∧ ∃ c : ℝ,
      ∀ ε > (0 : ℝ), ∃ᶠ (N : ℕ) in atTop,
        ∃ (k : ℕ) (a b c' : Fin k → ℕ),
          (k : ℝ) ≤ ((N : ℝ) + 1) ^ c ∧
          TensorObj.Restrict
            (TensorObj.bigAdd (fun i => MMObj K (a i) (b i) (c' i)))
            (T.kronPow N)
          ∧ V ^ N * (1 - ε) ≤ ∑ i, ((a i * b i * c' i : ℕ) : ℝ) ^ ((1 : ℝ) / 3) := by
  sorry
Source
Wigderson--Zuiddam 2023 (arXiv:2305.18068) §6; Coppersmith--Winograd 1990 §5--§7

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me