/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilGeneric and maximal rank of 3-tensors
The rank of a tensor $T \in \mathbb{C}^{m_1} \otimes \mathbb{C}^{m_2} \otimes \mathbb{C}^{m_3}$ is
the least $r$ such that $T$ is a sum of $r$ decomposable tensors $a \otimes b \otimes c$. Mathlib
records such a tensor as a Holor ℂ [m₁, m₂, m₃] and its rank as Holor.cprank.
Two basic invariants of the format $(m_1, m_2, m_3)$ are the generic rank $\operatorname{grank}(m_1, m_2, m_3)$, the rank of a generic tensor, and the maximal rank $\operatorname{mrank}(m_1, m_2, m_3)$, the largest rank attained by a tensor of that format.
Counting parameters gives the lower bound
$\operatorname{grank}(m_1, m_2, m_3) \geq r_0(m_1, m_2, m_3) :=
\lceil m_1m_2m_3 / (m_1 + m_2 + m_3 - 2) \rceil$. Once $m_3$ exceeds $(m_1-1)(m_2-1)$ the generic
rank is known to be $\min(m_3, m_1m_2)$, so the interesting case is the critical range
$3 \leq m_1 \leq m_2 \leq m_3 \leq (m_1-1)(m_2-1)$ [Fri12, Conjecture 5.1; BFZ24, (4.14)]. There
the bound $r_0$ is attained in every case that has been settled, except for the formats
$(3, 2p+1, 2p+1)$, where the generic rank is $r_0 + 1$. Friedland's conjecture, stated here as
isGenericRank_of_le_critical, is that these are the only exceptions. The boundary case
$m_3 = (m_1-1)(m_2-1)$ is settled in [Fri12, Corollary 6.4(2)] and recorded as
isGenericRank_of_eq_critical.
The maximal rank is much less well understood. It is known for the formats $2 \times m \times n$ and for a range of small formats, but no formula is known even for $(n, n, n)$, and $\operatorname{mrank}(3, 3, 5)$ is undetermined.
Tensor rank is invariant under permuting the three factors, but Holor ℂ [m₁, m₂, m₃] and its
permutations are different types and Mathlib has no transport lemma between them. Each statement
below therefore writes the format in the order its own source uses.
References:
[Fri12] S. Friedland, On the generic and typical ranks of 3-tensors, Linear Algebra Appl. 436 (2012), 478-497, https://doi.org/10.1016/j.laa.2011.05.008 (arxiv/0805.3777). Conjecture 5.1, and the survey of known values in Section 5.
[BFZ24] W. Bruzda, S. Friedland, K. Życzkowski, Rank of a tensor and quantum entanglement, Linear Multilinear Algebra 72 (2024), 1796-1859, https://doi.org/10.1080/03081087.2023.2211717 (arxiv/1912.06854v4). A survey; the numbering used below is that of the arXiv v4 PDF. Conjecture 4.12 restates [Fri12, Conjecture 5.1], and Sections 4.5 and 4.6 collect the current status.
[CGG02] M. V. Catalisano, A. V. Geramita, A. Gimigliano, Ranks of tensors, secant varieties of
Segre varieties and fat points, Linear Algebra Appl. 355 (2002), 263-285,
https://doi.org/10.1016/S0024-3795(02)00352-X. Used for isGenericRank_of_gt_critical.
[Str83] V. Strassen, Rank and optimal computation of generic tensors, Linear Algebra Appl.
52/53 (1983), 645-685, https://doi.org/10.1016/0024-3795(83)80041-X. Used for
isGenericRank_three_even and isGenericRank_three_odd.
[AOP09] H. Abo, G. Ottaviani, C. Peterson, Induction for secant varieties of Segre varieties,
Trans. Amer. Math. Soc. 361 (2009), 767-792, https://doi.org/10.1090/S0002-9947-08-04725-9.
Used for isGenericRank_four.
[Lic85] T. Lickteig, Typical tensorial rank, Linear Algebra Appl. 69 (1985), 95-120,
https://doi.org/10.1016/0024-3795(85)90070-9. Used for isGenericRank_cube.
[AS79] M. D. Atkinson, N. M. Stephens, On the maximal multiplicative complexity of a family of
bilinear forms, Linear Algebra Appl. 27 (1979), 1-8,
https://doi.org/10.1016/0024-3795(79)90026-0. Used for isMaxRank_two,
cprank_le_of_three_slices, cprank_le_of_square_slices, isMaxRank_of_le_min and
isMaxRank_three_three_five_bounds.
[JaJa79] J. JáJá, Optimal evaluation of pairs of bilinear forms, SIAM J. Comput. 8 (1979),
443-462, https://doi.org/10.1137/0208037, and J. B. Kruskal, Rank, decomposition, and
uniqueness for 3-way and N-way arrays, in Multiway Data Analysis, North-Holland (1989), 7-18.
Cited by [Fri12] for isMaxRank_two.
[SMS10] T. Sumi, M. Miyazaki, T. Sakata, About the maximal rank of 3-tensors over the real and
the complex number field, Ann. Inst. Statist. Math. 62 (2010), 807-822,
https://doi.org/10.1007/s10463-010-0294-5 (arxiv/0806.4048).
Theorem 4.5 proves the first of the two bounds that [AS79] states without proof; Proposition
4.9(1) is the special case used for isMaxRank_three.
[Ki26] K. Kitamura, A Lean proof that the maximal rank of complex $3 \times 3 \times 5$
tensors is 6, GitHub repository (2026), https://github.com/KitaKen1/mrank-3-3-5-lean. Used
for isMaxRank_three_three_five.
[BT15] G. Blekherman, Z. Teitler, On maximum, typical and generic ranks, Math. Ann. 362
(2015), 1021-1031, https://doi.org/10.1007/s00208-014-1150-3
(arxiv/1402.2371), Theorem 1. Used for
isMaxRank_le_two_mul_isGenericRank.
@[expose] public sectionnamespace Arxiv.«0805.3777»The space of complex tensors of a fixed format, topologised as the finite-dimensional complex vector space that it is.
noncomputable scoped instance instTopologicalSpaceHolor {ds : List ℕ} :
TopologicalSpace (Holor ℂ ds) :=
inferInstanceAs <| TopologicalSpace (HolorIndex ds → ℂ)
IsGenericRank ds r says that r is the generic rank of complex tensors of format ds: the
tensors of rank r contain a dense open set.
This is the form the sources establish: the tensors of rank other than the generic rank lie in a
proper algebraic subset [Fri12, Theorem 3.4]. It determines r uniquely, by
IsGenericRank.unique.
def IsGenericRank (ds : List ℕ) (r : ℕ) : Prop :=
∃ U : Set (Holor ℂ ds), IsOpen U ∧ Dense U ∧ ∀ T ∈ U, T.cprank = r
IsMaxRank ds r says that r is the maximal rank of a complex tensor of format ds: every such
tensor has rank at most r, and some tensor has rank r.
def IsMaxRank (ds : List ℕ) (r : ℕ) : Prop :=
IsGreatest (Set.range fun T : Holor ℂ ds => T.cprank) r
A tensor has rank 0 exactly when it is zero.
mpr ds:List ℕthis:Holor.cprank 0 ≤ 0⊢ Holor.cprank 0 = 0
omega All goals completed! 🐙
The maximal rank of a tensor of format ds is at most ds.prod.
@[category API, AMS 15]
theorem IsMaxRank.le_prod {ds : List ℕ} {r : ℕ} (hr : IsMaxRank ds r) : r ≤ ds.prod := by ds:List ℕr:ℕhr:IsMaxRank ds r⊢ r ≤ ds.prod
obtain ⟨T, hT⟩ := hr.1 ds:List ℕr:ℕhr:IsMaxRank ds rT:Holor ℂ dshT:(fun T ↦ T.cprank) T = r⊢ r ≤ ds.prod
exact hT ▸ Holor.cprank_upper_bound T All goals completed! 🐙There is at most one generic rank.
@[category API, AMS 15]
theorem IsGenericRank.unique {ds : List ℕ} {r r' : ℕ} (hr : IsGenericRank ds r)
(hr' : IsGenericRank ds r') : r = r' := by ds:List ℕr:ℕr':ℕhr:IsGenericRank ds rhr':IsGenericRank ds r'⊢ r = r'
obtain ⟨U, hU, hUd, hUr⟩ := hr ds:List ℕr:ℕr':ℕhr':IsGenericRank ds r'U:Set (Holor ℂ ds)hU:IsOpen UhUd:Dense UhUr:∀ T ∈ U, T.cprank = r⊢ r = r'
obtain ⟨V, hV, hVd, hVr⟩ := hr' ds:List ℕr:ℕr':ℕU:Set (Holor ℂ ds)hU:IsOpen UhUd:Dense UhUr:∀ T ∈ U, T.cprank = rV:Set (Holor ℂ ds)hV:IsOpen VhVd:Dense VhVr:∀ T ∈ V, T.cprank = r'⊢ r = r'
obtain ⟨T, hTU, hTV⟩ := hVd.inter_open_nonempty U hU hUd.nonempty ds:List ℕr:ℕr':ℕU:Set (Holor ℂ ds)hU:IsOpen UhUd:Dense UhUr:∀ T ∈ U, T.cprank = rV:Set (Holor ℂ ds)hV:IsOpen VhVd:Dense VhVr:∀ T ∈ V, T.cprank = r'T:Holor ℂ dshTU:T ∈ UhTV:T ∈ V⊢ r = r'
rw [← hUr T hTU, ds:List ℕr:ℕr':ℕU:Set (Holor ℂ ds)hU:IsOpen UhUd:Dense UhUr:∀ T ∈ U, T.cprank = rV:Set (Holor ℂ ds)hV:IsOpen VhVd:Dense VhVr:∀ T ∈ V, T.cprank = r'T:Holor ℂ dshTU:T ∈ UhTV:T ∈ V⊢ T.cprank = r' All goals completed! 🐙 hVr T hTV ds:List ℕr:ℕr':ℕU:Set (Holor ℂ ds)hU:IsOpen UhUd:Dense UhUr:∀ T ∈ U, T.cprank = rV:Set (Holor ℂ ds)hV:IsOpen VhVd:Dense VhVr:∀ T ∈ V, T.cprank = r'T:Holor ℂ dshTU:T ∈ UhTV:T ∈ V⊢ r' = r' All goals completed! 🐙] All goals completed! 🐙The generic rank is at most the maximal rank [Fri12, (4.3)].
@[category API, AMS 15]
theorem IsGenericRank.le_of_isMaxRank {ds : List ℕ} {r R : ℕ} (hr : IsGenericRank ds r)
(hR : IsMaxRank ds R) : r ≤ R := by ds:List ℕr:ℕR:ℕhr:IsGenericRank ds rhR:IsMaxRank ds R⊢ r ≤ R
obtain ⟨U, hU, hUd, hUr⟩ := hr ds:List ℕr:ℕR:ℕhR:IsMaxRank ds RU:Set (Holor ℂ ds)hU:IsOpen UhUd:Dense UhUr:∀ T ∈ U, T.cprank = r⊢ r ≤ R
obtain ⟨T, hT⟩ := hUd.nonempty ds:List ℕr:ℕR:ℕhR:IsMaxRank ds RU:Set (Holor ℂ ds)hU:IsOpen UhUd:Dense UhUr:∀ T ∈ U, T.cprank = rT:Holor ℂ dshT:T ∈ U⊢ r ≤ R
exact hUr T hT ▸ hR.2 ⟨T, rfl⟩ All goals completed! 🐙
The maximal rank of a $1 \times 1 \times 1$ tensor is 1.
@[category test, AMS 15]
theorem isMaxRank_one : IsMaxRank [1, 1, 1] 1 := by ⊢ IsMaxRank [1, 1, 1] 1
set S : Holor ℂ [1, 1, 1] := fun _ => 1 with hS S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1⊢ IsMaxRank [1, 1, 1] 1
refine ⟨⟨S, ?_⟩, ?_⟩ refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1⊢ (fun T ↦ T.cprank) S = 1refine_2 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1⊢ 1 ∈ upperBounds (Set.range fun T ↦ T.cprank)
· refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1⊢ (fun T ↦ T.cprank) S = 1 show S.cprank = 1 refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1⊢ S.cprank = 1
have hle : S.cprank ≤ 1 := by ⊢ IsMaxRank [1, 1, 1] 1 refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1⊢ S.cprank = 1 simpa using Holor.cprank_upper_bound S refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1⊢ S.cprank = 1refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1⊢ S.cprank = 1
have hne : S.cprank ≠ 0 := by ⊢ IsMaxRank [1, 1, 1] 1 refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1hne:S.cprank ≠ 0⊢ S.cprank = 1
rw [Ne, S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1⊢ ¬S.cprank = 0 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1⊢ ¬S = 0refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1hne:S.cprank ≠ 0⊢ S.cprank = 1 cprank_eq_zero_iff S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1⊢ ¬S = 0 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1⊢ ¬S = 0refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1hne:S.cprank ≠ 0⊢ S.cprank = 1] S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1⊢ ¬S = 0refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1hne:S.cprank ≠ 0⊢ S.cprank = 1
intro h S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1h:S = 0⊢ Falserefine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1hne:S.cprank ≠ 0⊢ S.cprank = 1
exact one_ne_zero (congrFun h ⟨[0, 0, 0], by S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1h:S = 0⊢ List.Forall₂ (fun x1 x2 ↦ x1 < x2) [0, 0, 0] [1, 1, 1]refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1hne:S.cprank ≠ 0⊢ S.cprank = 1 simp All goals completed! 🐙refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1hne:S.cprank ≠ 0⊢ S.cprank = 1⟩)refine_1 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1hle:S.cprank ≤ 1hne:S.cprank ≠ 0⊢ S.cprank = 1
omega All goals completed! 🐙
· refine_2 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1⊢ 1 ∈ upperBounds (Set.range fun T ↦ T.cprank) rintro y ⟨T, rfl⟩ refine_2 S:Holor ℂ [1, 1, 1] := fun x ↦ 1hS:S = fun x ↦ 1T:Holor ℂ [1, 1, 1]⊢ (fun T ↦ T.cprank) T ≤ 1
simpa using Holor.cprank_upper_bound T All goals completed! 🐙The generic rank of an $m \times n$ matrix is $\min(m, n)$: the 2-tensor case.
@[category textbook, AMS 15]
theorem isGenericRank_matrix (m n : ℕ) : IsGenericRank [m, n] (min m n) := by m:ℕn:ℕ⊢ IsGenericRank [m, n] (min m n)
sorry All goals completed! 🐙Above the critical range, a generic tensor of format $(m_1, m_2, m_3)$ has rank $\min(m_3, m_1m_2)$ [Fri12, (5.1)].
@[category research solved, AMS 14 15]
theorem isGenericRank_of_gt_critical {m₁ m₂ m₃ : ℕ} (h₁ : 1 ≤ m₁) (h₁₂ : m₁ ≤ m₂) (h₂₃ : m₂ ≤ m₃)
(h : (m₁ - 1) * (m₂ - 1) < m₃) :
IsGenericRank [m₁, m₂, m₃] (min m₃ (m₁ * m₂)) := by m₁:ℕm₂:ℕm₃:ℕh₁:1 ≤ m₁h₁₂:m₁ ≤ m₂h₂₃:m₂ ≤ m₃h:(m₁ - 1) * (m₂ - 1) < m₃⊢ IsGenericRank [m₁, m₂, m₃] (min m₃ (m₁ * m₂))
sorry All goals completed! 🐙The generic rank of a $3 \times 2p \times 2p$ tensor is $\lceil 12p^2 / (4p + 1) \rceil$, the value $r_0$ predicted by a dimension count [Fri12, (5.3)]. The hypothesis $2 \leq p$ is the ordering $3 \leq 2p$ of the format.
@[category research solved, AMS 14 15]
theorem isGenericRank_three_even {p : ℕ} (hp : 2 ≤ p) :
IsGenericRank [3, 2 * p, 2 * p] (12 * p ^ 2 ⌈/⌉ (4 * p + 1)) := by p:ℕhp:2 ≤ p⊢ IsGenericRank [3, 2 * p, 2 * p] (12 * p ^ 2 ⌈/⌉ (4 * p + 1))
sorry All goals completed! 🐙
The generic rank of a $3 \times (2p+1) \times (2p+1)$ tensor is
$\lceil 3(2p+1)^2 / (4p + 3) \rceil + 1$, one more than the value $r_0$ predicted by a dimension
count [Fri12, (5.4)]. These are the only formats in the critical range known to exceed $r_0$. The
case $p = 1$ says that the generic rank of a $3 \times 3 \times 3$ tensor is 5, not 4.
@[category research solved, AMS 14 15]
theorem isGenericRank_three_odd {p : ℕ} (hp : 1 ≤ p) :
IsGenericRank [3, 2 * p + 1, 2 * p + 1] (3 * (2 * p + 1) ^ 2 ⌈/⌉ (4 * p + 3) + 1) := by p:ℕhp:1 ≤ p⊢ IsGenericRank [3, 2 * p + 1, 2 * p + 1] (3 * (2 * p + 1) ^ 2 ⌈/⌉ (4 * p + 3) + 1)
sorry All goals completed! 🐙
The generic rank of a $4 \times m \times m$ tensor is $\lceil 4m^2 / (2m + 2) \rceil$
[Fri12, (5.7)]. This is the case $(4, m, m)$ of isGenericRank_of_le_critical, settled in
[AOP09]; see [BFZ24, Section 4.5].
@[category research solved, AMS 14 15]
theorem isGenericRank_four {m : ℕ} (hm : 3 ≤ m) :
IsGenericRank [4, m, m] (4 * m ^ 2 ⌈/⌉ (2 * m + 2)) := by m:ℕhm:3 ≤ m⊢ IsGenericRank [4, m, m] (4 * m ^ 2 ⌈/⌉ (2 * m + 2))
sorry All goals completed! 🐙For $n \neq 3$ the generic rank of an $n \times n \times n$ tensor is $\lceil n^3 / (3n - 2) \rceil$ [Fri12, (5.8)].
@[category research solved, AMS 14 15]
theorem isGenericRank_cube {n : ℕ} (hn : 1 ≤ n) (hn3 : n ≠ 3) :
IsGenericRank [n, n, n] (n ^ 3 ⌈/⌉ (3 * n - 2)) := by n:ℕhn:1 ≤ nhn3:n ≠ 3⊢ IsGenericRank [n, n, n] (n ^ 3 ⌈/⌉ (3 * n - 2))
sorry All goals completed! 🐙At the boundary $m_3 = (m_1-1)(m_2-1)$, the dimension-count ceiling is $m_3+1$. This is the arithmetic identity in [Fri12, (5.11)].
@[category API, AMS 14 15]
theorem critical_ceilDiv {m₁ m₂ : ℕ} (h₁ : 3 ≤ m₁) (h₂ : 3 ≤ m₂) :
m₁ * m₂ * ((m₁ - 1) * (m₂ - 1)) ⌈/⌉
(m₁ + m₂ + (m₁ - 1) * (m₂ - 1) - 2) = (m₁ - 1) * (m₂ - 1) + 1 := by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂⊢ m₁ * m₂ * ((m₁ - 1) * (m₂ - 1)) ⌈/⌉ (m₁ + m₂ + (m₁ - 1) * (m₂ - 1) - 2) = (m₁ - 1) * (m₂ - 1) + 1
set b := (m₁ - 1) * (m₂ - 1) m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)⊢ m₁ * m₂ * b ⌈/⌉ (m₁ + m₂ + b - 2) = b + 1
set d := m₁ + m₂ + b - 2 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
have hb : 0 < b := Nat.mul_pos (by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2⊢ 0 < m₁ - 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < b⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 omega All goals completed! 🐙 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < b⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1) (by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2⊢ 0 < m₂ - 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < b⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 omega All goals completed! 🐙 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < b⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1) m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < b⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
have hbd : b < d := by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂⊢ m₁ * m₂ * ((m₁ - 1) * (m₂ - 1)) ⌈/⌉ (m₁ + m₂ + (m₁ - 1) * (m₂ - 1) - 2) = (m₁ - 1) * (m₂ - 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < d⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 omega m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < d⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < d⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
have hd : d + 1 = m₁ * m₂ := by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂⊢ m₁ * m₂ * ((m₁ - 1) * (m₂ - 1)) ⌈/⌉ (m₁ + m₂ + (m₁ - 1) * (m₂ - 1) - 2) = (m₁ - 1) * (m₂ - 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
have hdadd : d + 2 = m₁ + m₂ + b := by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂⊢ m₁ * m₂ * ((m₁ - 1) * (m₂ - 1)) ⌈/⌉ (m₁ + m₂ + (m₁ - 1) * (m₂ - 1) - 2) = (m₁ - 1) * (m₂ - 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + b⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 omega m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + b⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + b⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
have hsub₁ : m₁ - 1 + 1 = m₁ := by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂⊢ m₁ * m₂ * ((m₁ - 1) * (m₂ - 1)) ⌈/⌉ (m₁ + m₂ + (m₁ - 1) * (m₂ - 1) - 2) = (m₁ - 1) * (m₂ - 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 omega m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
have hsub₂ : m₂ - 1 + 1 = m₂ := by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂⊢ m₁ * m₂ * ((m₁ - 1) * (m₂ - 1)) ⌈/⌉ (m₁ + m₂ + (m₁ - 1) * (m₂ - 1) - 2) = (m₁ - 1) * (m₂ - 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 omega m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
have hmul : b + m₁ + m₂ = m₁ * m₂ + 1 := by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂⊢ m₁ * m₂ * ((m₁ - 1) * (m₂ - 1)) ⌈/⌉ (m₁ + m₂ + (m₁ - 1) * (m₂ - 1) - 2) = (m₁ - 1) * (m₂ - 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂hmul:b + m₁ + m₂ = m₁ * m₂ + 1⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
dsimp [b] m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂⊢ (m₁ - 1) * (m₂ - 1) + m₁ + m₂ = m₁ * m₂ + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂hmul:b + m₁ + m₂ = m₁ * m₂ + 1⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
rw [← hsub₁, m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂⊢ (m₁ - 1 + 1 - 1) * (m₂ - 1) + (m₁ - 1 + 1) + m₂ = (m₁ - 1 + 1) * m₂ + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂⊢ (m₁ - 1 + 1 - 1) * (m₂ - 1 + 1 - 1) + (m₁ - 1 + 1) + (m₂ - 1 + 1) = (m₁ - 1 + 1) * (m₂ - 1 + 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂hmul:b + m₁ + m₂ = m₁ * m₂ + 1⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 ← hsub₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂⊢ (m₁ - 1 + 1 - 1) * (m₂ - 1 + 1 - 1) + (m₁ - 1 + 1) + (m₂ - 1 + 1) = (m₁ - 1 + 1) * (m₂ - 1 + 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂⊢ (m₁ - 1 + 1 - 1) * (m₂ - 1 + 1 - 1) + (m₁ - 1 + 1) + (m₂ - 1 + 1) = (m₁ - 1 + 1) * (m₂ - 1 + 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂hmul:b + m₁ + m₂ = m₁ * m₂ + 1⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1] m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂⊢ (m₁ - 1 + 1 - 1) * (m₂ - 1 + 1 - 1) + (m₁ - 1 + 1) + (m₂ - 1 + 1) = (m₁ - 1 + 1) * (m₂ - 1 + 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂hmul:b + m₁ + m₂ = m₁ * m₂ + 1⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
simp only [Nat.add_sub_cancel] m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂⊢ (m₁ - 1) * (m₂ - 1) + (m₁ - 1 + 1) + (m₂ - 1 + 1) = (m₁ - 1 + 1) * (m₂ - 1 + 1) + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂hmul:b + m₁ + m₂ = m₁ * m₂ + 1⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
ring m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂hmul:b + m₁ + m₂ = m₁ * m₂ + 1⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhdadd:d + 2 = m₁ + m₂ + bhsub₁:m₁ - 1 + 1 = m₁hsub₂:m₂ - 1 + 1 = m₂hmul:b + m₁ + m₂ = m₁ * m₂ + 1⊢ d + 1 = m₁ * m₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
omega m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1 m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d = b + 1
apply Nat.le_antisymm h₁ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d ≤ b + 1h₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ b + 1 ≤ m₁ * m₂ * b ⌈/⌉ d
· h₁ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ m₁ * m₂ * b ⌈/⌉ d ≤ b + 1 apply (ceilDiv_le_iff_le_mul (by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ 0 < d omega All goals completed! 🐙 : 0 < d)).2
nlinarith All goals completed! 🐙
· h₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ b + 1 ≤ m₁ * m₂ * b ⌈/⌉ d have hle := le_smul_ceilDiv (by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂⊢ 0 < d h₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂hle:m₁ * m₂ * b ≤ d • (m₁ * m₂ * b ⌈/⌉ d)⊢ b + 1 ≤ m₁ * m₂ * b ⌈/⌉ d omega All goals completed! 🐙h₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂hle:m₁ * m₂ * b ≤ d • (m₁ * m₂ * b ⌈/⌉ d)⊢ b + 1 ≤ m₁ * m₂ * b ⌈/⌉ d : 0 < d) (b := m₁ * m₂ * b)h₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂hle:m₁ * m₂ * b ≤ d • (m₁ * m₂ * b ⌈/⌉ d)⊢ b + 1 ≤ m₁ * m₂ * b ⌈/⌉ d
change m₁ * m₂ * b ≤ d * (m₁ * m₂ * b ⌈/⌉ d) at hle h₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂hle:m₁ * m₂ * b ≤ d * (m₁ * m₂ * b ⌈/⌉ d)⊢ b + 1 ≤ m₁ * m₂ * b ⌈/⌉ d
by_contra h h₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂hle:m₁ * m₂ * b ≤ d * (m₁ * m₂ * b ⌈/⌉ d)h:¬b + 1 ≤ m₁ * m₂ * b ⌈/⌉ d⊢ False
have : m₁ * m₂ * b ⌈/⌉ d ≤ b := by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂⊢ m₁ * m₂ * ((m₁ - 1) * (m₂ - 1)) ⌈/⌉ (m₁ + m₂ + (m₁ - 1) * (m₂ - 1) - 2) = (m₁ - 1) * (m₂ - 1) + 1 h₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂hle:m₁ * m₂ * b ≤ d * (m₁ * m₂ * b ⌈/⌉ d)h:¬b + 1 ≤ m₁ * m₂ * b ⌈/⌉ dthis:m₁ * m₂ * b ⌈/⌉ d ≤ b⊢ False omegah₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂hle:m₁ * m₂ * b ≤ d * (m₁ * m₂ * b ⌈/⌉ d)h:¬b + 1 ≤ m₁ * m₂ * b ⌈/⌉ dthis:m₁ * m₂ * b ⌈/⌉ d ≤ b⊢ Falseh₂ m₁:ℕm₂:ℕh₁:3 ≤ m₁h₂:3 ≤ m₂b:ℕ := (m₁ - 1) * (m₂ - 1)d:ℕ := m₁ + m₂ + b - 2hb:0 < bhbd:b < dhd:d + 1 = m₁ * m₂hle:m₁ * m₂ * b ≤ d * (m₁ * m₂ * b ⌈/⌉ d)h:¬b + 1 ≤ m₁ * m₂ * b ⌈/⌉ dthis:m₁ * m₂ * b ⌈/⌉ d ≤ b⊢ False
nlinarith All goals completed! 🐙
The generic rank at the critical boundary is $(m_1-1)(m_2-1)+1$
[Fri12, Corollary 6.4(2)]. By critical_ceilDiv, this is the dimension-count value in
isGenericRank_of_le_critical.
@[category research solved, AMS 14 15]
theorem isGenericRank_of_eq_critical {m₁ m₂ : ℕ} (h₁ : 3 ≤ m₁) (h₁₂ : m₁ ≤ m₂) :
IsGenericRank [m₁, m₂, (m₁ - 1) * (m₂ - 1)] ((m₁ - 1) * (m₂ - 1) + 1) := by m₁:ℕm₂:ℕh₁:3 ≤ m₁h₁₂:m₁ ≤ m₂⊢ IsGenericRank [m₁, m₂, (m₁ - 1) * (m₂ - 1)] ((m₁ - 1) * (m₂ - 1) + 1)
sorry All goals completed! 🐙
Friedland's conjecture. In the critical range $m_3 \leq (m_1 - 1)(m_2 - 1)$, and away from the
formats $(3, 2p+1, 2p+1)$, the generic rank of a tensor of format $(m_1, m_2, m_3)$ is the value
$\lceil m_1m_2m_3 / (m_1 + m_2 + m_3 - 2) \rceil$ predicted by a dimension count
[Fri12, Conjecture 5.1]. The boundary $m_3 = (m_1-1)(m_2-1)$ is settled by
isGenericRank_of_eq_critical [Fri12, (5.11)]. It is known for $m_1 \leq 4$ and for $(n, n, n)$,
and has been verified numerically throughout the critical range for $m_3 \leq 20$
[BFZ24, Section 4.5].
@[category research open, AMS 14 15]
theorem isGenericRank_of_le_critical {m₁ m₂ m₃ : ℕ} (h₁ : 3 ≤ m₁) (h₁₂ : m₁ ≤ m₂) (h₂₃ : m₂ ≤ m₃)
(h : m₃ ≤ (m₁ - 1) * (m₂ - 1)) (hexc : ∀ p : ℕ, (m₁, m₂, m₃) ≠ (3, 2 * p + 1, 2 * p + 1)) :
IsGenericRank [m₁, m₂, m₃] (m₁ * m₂ * m₃ ⌈/⌉ (m₁ + m₂ + m₃ - 2)) := by m₁:ℕm₂:ℕm₃:ℕh₁:3 ≤ m₁h₁₂:m₁ ≤ m₂h₂₃:m₂ ≤ m₃h:m₃ ≤ (m₁ - 1) * (m₂ - 1)hexc:∀ (p : ℕ), (m₁, m₂, m₃) ≠ (3, 2 * p + 1, 2 * p + 1)⊢ IsGenericRank [m₁, m₂, m₃] (m₁ * m₂ * m₃ ⌈/⌉ (m₁ + m₂ + m₃ - 2))
sorry All goals completed! 🐙The maximal rank of a $2 \times m \times n$ tensor is $m + \min(m, \lfloor n/2 \rfloor)$ [Fri12, (5.13)]; equivalently [BFZ24, (4.9)].
@[category research solved, AMS 15]
theorem isMaxRank_two {m n : ℕ} (hm : 2 ≤ m) (hmn : m ≤ n) :
IsMaxRank [2, m, n] (m + min m (n / 2)) := by m:ℕn:ℕhm:2 ≤ mhmn:m ≤ n⊢ IsMaxRank [2, m, n] (m + min m (n / 2))
sorry All goals completed! 🐙Every $n \times n \times 3$ tensor has rank at most $2n - 1$ [SMS10, Theorem 4.5].
@[category research solved, AMS 15]
theorem cprank_le_of_three_slices {n : ℕ} (hn : 1 ≤ n) (T : Holor ℂ [n, n, 3]) :
T.cprank ≤ 2 * n - 1 := by n:ℕhn:1 ≤ nT:Holor ℂ [n, n, 3]⊢ T.cprank ≤ 2 * n - 1
sorry All goals completed! 🐙
The maximal rank of a $3 \times 3 \times 3$ tensor is 5. The upper bound is
[SMS10, Proposition 4.9(1)], a special case of cprank_le_of_three_slices; the lower bound is the
generic rank isGenericRank_three_odd at $p = 1$.
@[category research solved, AMS 14 15]
theorem isMaxRank_three : IsMaxRank [3, 3, 3] 5 := by ⊢ IsMaxRank [3, 3, 3] 5
sorry All goals completed! 🐙For $u \leq \min(4, m)$ the maximal rank of an $m \times n \times (mn - u)$ tensor is $mn - \lceil u/2 \rceil$ [BFZ24, (4.24)].
@[category research solved, AMS 15]
theorem isMaxRank_of_le_min {m n u : ℕ} (hm : 3 ≤ m) (hmn : m ≤ n) (hu : u ≤ min 4 m) :
IsMaxRank [m, n, m * n - u] (m * n - u ⌈/⌉ 2) := by m:ℕn:ℕu:ℕhm:3 ≤ mhmn:m ≤ nhu:u ≤ min 4 m⊢ IsMaxRank [m, n, m * n - u] (m * n - u ⌈/⌉ 2)
sorry All goals completed! 🐙
The maximal rank of a $3 \times 3 \times 5$ tensor is 6 or 7 [BFZ24, (4.20)].
@[category research solved, AMS 15]
theorem isMaxRank_three_three_five_bounds {R : ℕ} (hR : IsMaxRank [3, 3, 5] R) :
6 ≤ R ∧ R ≤ 7 := by R:ℕhR:IsMaxRank [3, 3, 5] R⊢ 6 ≤ R ∧ R ≤ 7
sorry All goals completed! 🐙def isMaxRank_three_three_five.answer : ℕ := 6set_option linter.style.formal_proof_palomar false in
Determine the maximal rank of a $3 \times 3 \times 5$ tensor. It was the one
undetermined entry of the table of $\operatorname{mrank}(3, 3, p)$ for $p \leq 9$
[BFZ24, (4.20)]. The answer is 6. A Lean proof is given in [Ki26].
@[category research solved, question value, AMS 15,
formal_proof using lean4 at
"https://github.com/KitaKen1/mrank-3-3-5-lean/blob/fbec93aa021bd994380cd27eb60e444e7cc85e93/lean/TensorRank335FC.lean#L3365-L3367"]
theorem isMaxRank_three_three_five : IsMaxRank [3, 3, 5] isMaxRank_three_three_five.answer := by ⊢ IsMaxRank [3, 3, 5] isMaxRank_three_three_five.answer
sorry All goals completed! 🐙The maximal rank is at most twice the generic rank [BT15, Theorem 1].
@[category research solved, AMS 14 15]
theorem isMaxRank_le_two_mul_isGenericRank {ds : List ℕ} {r R : ℕ} (hr : IsGenericRank ds r)
(hR : IsMaxRank ds R) : R ≤ 2 * r := by ds:List ℕr:ℕR:ℕhr:IsGenericRank ds rhR:IsMaxRank ds R⊢ R ≤ 2 * r
sorry All goals completed! 🐙Every complex $m \times n \times n$ tensor has rank at most $\lfloor (m+1)n/2 \rfloor$ for $m,n \geq 3$ [BFZ24, (4.22)].
@[category research solved, AMS 15]
theorem cprank_le_of_square_slices {m n : ℕ} (hm : 3 ≤ m) (hn : 3 ≤ n)
(T : Holor ℂ [m, n, n]) : T.cprank ≤ (m + 1) * n / 2 := by m:ℕn:ℕhm:3 ≤ mhn:3 ≤ nT:Holor ℂ [m, n, n]⊢ T.cprank ≤ (m + 1) * n / 2
sorry All goals completed! 🐙For $n \geq 4$, the maximal rank $R$ of a complex cubic tensor satisfies $\lceil n^3/(3n-2) \rceil \leq R \leq n(n+1)/2$ [BFZ24, (4.22), (4.25)-(4.28)]. The lower bound is the generic rank; the upper bound is the square-slice estimate.
@[category research solved, AMS 14 15]
theorem isMaxRank_cube_bounds {n R : ℕ} (hn : 4 ≤ n) (hR : IsMaxRank [n, n, n] R) :
n ^ 3 ⌈/⌉ (3 * n - 2) ≤ R ∧ R ≤ n * (n + 1) / 2 := by n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] R⊢ n ^ 3 ⌈/⌉ (3 * n - 2) ≤ R ∧ R ≤ n * (n + 1) / 2
constructor left n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] R⊢ n ^ 3 ⌈/⌉ (3 * n - 2) ≤ Rright n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] R⊢ R ≤ n * (n + 1) / 2
· left n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] R⊢ n ^ 3 ⌈/⌉ (3 * n - 2) ≤ R exact (isGenericRank_cube (by n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] R⊢ 1 ≤ n omega All goals completed! 🐙) (by n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] R⊢ n ≠ 3 omega All goals completed! 🐙)).le_of_isMaxRank hR
· right n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] R⊢ R ≤ n * (n + 1) / 2 obtain ⟨T, hT⟩ := hR.1 right n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] RT:Holor ℂ [n, n, n]hT:(fun T ↦ T.cprank) T = R⊢ R ≤ n * (n + 1) / 2
rw [← hT right n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] RT:Holor ℂ [n, n, n]hT:(fun T ↦ T.cprank) T = R⊢ (fun T ↦ T.cprank) T ≤ n * (n + 1) / 2 right n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] RT:Holor ℂ [n, n, n]hT:(fun T ↦ T.cprank) T = R⊢ (fun T ↦ T.cprank) T ≤ n * (n + 1) / 2] right n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] RT:Holor ℂ [n, n, n]hT:(fun T ↦ T.cprank) T = R⊢ (fun T ↦ T.cprank) T ≤ n * (n + 1) / 2
simpa [Nat.mul_comm] using cprank_le_of_square_slices (by n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] RT:Holor ℂ [n, n, n]hT:(fun T ↦ T.cprank) T = R⊢ 3 ≤ n omega All goals completed! 🐙) (by n:ℕR:ℕhn:4 ≤ nhR:IsMaxRank [n, n, n] RT:Holor ℂ [n, n, n]hT:(fun T ↦ T.cprank) T = R⊢ 3 ≤ n omega All goals completed! 🐙) Tdef isMaxRank_cube.answer : ℕ → ℕ := sorry
Open problem. Determine the maximal rank of a complex $n \times n \times n$ tensor. No formula
is known: for $n = 1, 2, 3$ the values are 1, 3 and 5, while for $4 \leq n \leq 7$ only
the bounds in isMaxRank_cube_bounds, such as $7 \leq \operatorname{mrank}(4,4,4) \leq 10$,
are available [BFZ24, (4.25)-(4.28)].
@[category research open, question value, AMS 15]
theorem isMaxRank_cube {n : ℕ} (hn : 1 ≤ n) :
IsMaxRank [n, n, n] (isMaxRank_cube.answer n) := by n:ℕhn:1 ≤ n⊢ IsMaxRank [n, n, n] (isMaxRank_cube.answer n)
sorry All goals completed! 🐙end Arxiv.«0805.3777»