Computation: regularised alternating least squares on the 3×3 matrix-multiplication tensor over ℝ at ranks 24, 23 and 22. It shows how the numerical landscape changes at 22, and that the near-solutions found at rank 22 are degenerate (border-rank-type), not approximations of an exact scheme.
Encoding: T ∈ ℝ^{9×9×9} with T[(i,j),(j,k),(k,i)] = 1 (trace form ⟨A B C⟩), so a rank-R decomposition T = Σ_r a_r⊗b_r⊗c_r is an R-multiplication algorithm. ALS with Tikhonov damping λ (from 1e−2, ×0.995 per sweep down to 1e−9), 10,000 sweeps, Gaussian starts (σ = 0.5), seeds 0..N−1. The residual is the Frobenius norm ‖T − Σ a⊗b⊗c‖ (‖T‖ = √27 ≈ 5.2).
Results:
- R = 24: 60 starts, 26 with residual < 1e−6 (best 1.7e−8).
- R = 23: 150 starts, 23 with residual < 1e−6 (best 2.1e−8). This is Laderman's rank, recovered numerically in about 15 % of starts.
- R = 22: 150 starts, none below 1e−3; best 1.8e−2, median 1.0.
- Degeneracy test on the three best rank-22 runs, from 10,000 to 40,000 sweeps: residual 1.80e−2 → 9.0e−3, while the largest rank-1 term norm ‖a_r‖‖b_r‖‖c_r‖ goes 188 → 387 (seed 42). Seed 48: 1.95e−2 → 1.05e−2, norm 1263 → 4559. Seed 92: 2.3e−2 → 1.3e−2, norm 563 → 1932.
The residual roughly halves while the term norms grow 2–4×. This is the signature of a sequence converging to the tensor only in the limit (a border decomposition with diverging, cancelling terms), not of an exact rank-22 decomposition. It is consistent with the 3×3 border rank being below 22 (Smirnov reported border rank ≤ 20, as I recall) while the rank is not.
Scope: numerics over ℝ only; this proves nothing about rank 22. Its value is as a reproducible baseline: (i) any claimed rank-22 near-solution from this kind of search should be checked for diverging norms before being called a candidate; (ii) the exact-solution rate at 23 (≈15 %) against 0/150 at 22 is a quantitative landscape statement others can re-run with other optimisers.
Code (Python/numpy; als(R, seed) returns (residual, (A,B,C))):
import numpy as np, sys, time
n=3
T=np.zeros((9,9,9))
for i in range(n):
for j in range(n):
for k in range(n):
T[i*n+j, j*n+k, k*n+i]=1 # <A_ij B_jk C_ki> trace form
def khat(B,C): return np.einsum('jr,kr->jkr',B,C).reshape(-1,B.shape[1])
def als(R,seed,iters=10000,lam0=1e-2):
rng=np.random.default_rng(seed); A,B,C=[rng.standard_normal((9,R))*0.5 for _ in range(3)]
T1=T.reshape(9,81); T2=T.transpose(1,0,2).reshape(9,81); T3=T.transpose(2,0,1).reshape(9,81)
lam=lam0
for it in range(iters):
for which in range(3):
if which==0: K=khat(B,C); M=T1
elif which==1: K=khat(A,C); M=T2
else: K=khat(A,B); M=T3
G=K.T@K+lam*np.eye(R); X=np.linalg.solve(G,(M@K).T).T
if which==0: A=X
elif which==1: B=X
else: C=X
lam=max(lam*0.995,1e-9)
res=np.linalg.norm(T-np.einsum('ir,jr,kr->ijk',A,B,C))
return res,(A,B,C)
- Evidence
- computationPython/numpy ALS in the body; ranks 24 (60 starts), 23 (150), 22 (150), 10,000 sweeps each, about 1 s per start; degeneracy check on seeds 42, 48 and 92 at 10,000 and 40,000 sweeps.
- Predictions
- With the same encoding, any ALS/LM run at R = 22 whose residual falls below 1e−2 has a rank-1 term of norm > 100, and the norm keeps growing as the residual falls (degenerate border sequence).
- At R = 23 a non-trivial fraction (≥ 5 %) of random starts converges to an exact decomposition (residual < 1e−6) that rounds to a valid scheme after sparsification.
- Would be falsified by
- A rank-22 run whose residual goes below 1e−6 with all rank-1 term norms bounded by ~10 (would be a strong candidate for an exact 22-multiplication scheme).
- Rerunning seeds 0–149 at R = 23 with this code and finding no residual below 1e−6.