Source-linked AI summary
Maximal rank of $4\times 4\times 4$ and $k\times 4\times 3$ tensors over $\mathbb{F}_2$
Jason Yang
TL;DR
Maximum tensor rank is difficult to analyze, and finite-field cases are especially sparse. This paper develops a method for enumerating non-isomorphic tensors over F2 and uses it to determine maximum ranks for 4×4×4 and k×4×3 shapes.
Problem
Maximum rank for a given tensor shape is difficult to analyze, and finite-field research is especially sparse because algebraic-geometry tools are less readily available.
Source: §1 · p. 1Method
The paper uses canonical-prefix enumeration and unified matching searches to enumerate non-isomorphic tensors and address the target shapes.
Source: §1 · p. 1, §2.1 · p. 3, §2.1.2 · p. 5Results
Takeaways & Limitations
The maximum-rank questions for the stated 4×4×4 and k×4×3 shapes over F2 are solved.
Source: §1 · p. 1
Abstract
from arXiv · showhide
We determine the maximum rank of $4\times 4\times 4$ and $k\times 4\times 3$ multidimensional arrays over the finite field $\mathbb{F}_2$. These results are made possible by a new method of enumerating non-isomorphic tensors.
1 Introduction
The paper targets maximum tensor rank over F2, where finite-field cases are sparse and even maximum rank for a fixed shape is difficult to analyze. It introduces the target shapes and establishes the rank and notation used in the paper.
1 Introduction
- The paper solves maximum-rank questions for 4×4×4 and all remaining k×4×3 shapes over F2.Computing arbitrary tensor rank is NP-hard, and maximum rank for a given shape is also difficult to analyze.Source: §1 · p. 1
1.1 Definitions
- Tensor rank is the minimum number of vector outer products in a decomposition, while axis-d rank measures the span dimension of the axis-d slices.A tensor is concise when its axis rank equals its dimension along every axis.Source: §1.1 · p. 1
1.1.1 Notation
- The notation section defines outer products and mode-wise matrix products, and uses [[A0, …, AD−1]] as shorthand for a decomposition with factor matrices.A row-vector mode product discards that axis; a 1-hot vector is denoted e_i.Source: §1.1.1 · pp. 1–2
- Indices are zero-based; a:b denotes indices from a through b−1, and an ellipsis spans all remaining axes.The paper also uses O* to denote asymptotic complexity while ignoring polynomial factors.Source: §1.1.1 · p. 2
2 Tensor enumeration
Tensor enumeration reduces the search to canonical representatives of isomorphism classes. The method builds tensors from canonical prefixes and uses matching searches to avoid repeated work when checking canonicity.
2 Tensor enumeration
- Canonicalization chooses the lexically minimum tensor in an isomorphism class, and the canonical representative has a zero-slice structure determined by its axis rank.For matrices, canonicalization depends only on rank and lower rank gives lower lexical order.Source: §2 · p. 2
2.1 Enumeration
- The enumeration builds axis-0-concise canonical tensors by prefixing a canonical tensor with a slice, then filters candidates for canonicity and isomorphism.It can generate concise tensors of smaller first-axis sizes and pad them with zero slices.Source: §2.1 · p. 3
2.1.1 Tensor matching
- Tensor matching tests whether invertible operations on the other axes and a full-row-rank map on axis 0 transform a tensor into a canonical prefix.The depth-first search fixes axis-0 rows; repeated targets and prefix matching can reduce the number of isomorphism checks in practice.Source: §2.1 · p. 3, §2.1.1 · p. 4
2.1.2 Combined matching
- Combined matching unifies checks for canonical prefixes that share search states, avoiding repeated traversal and eliminating the ≥0 relation.The procedure tracks possible axis-0 operations while seeking a non-strictly lexically smaller canonical prefix.Source: §2.1.2 · p. 5
2.1.3 Axis-0 canonicalization
- Before the full canonicity test, the algorithm checks canonicity along axis 0 by greedily selecting lexically ordered linearly independent vectors.The stated running time for can0(T) is O*(|F|^n0).Source: §2.1.3 · p. 5
3 Tensor rank
The rank-threshold test searches for a decomposition using fixed factors and checks whether the resulting vectors span the required dimension. Depth-first search pruning uses partial assignments to reject branches that cannot satisfy a chosen sufficiency check, with compressed maps and fallback tests helping control memory and computation.
3 Tensor rank
- The rank-threshold test fixes factors and checks whether the vectors in S span dimension n0, using either rank-1 enumeration or linear-system bases.The two methods have different costs; the first takes O*(|F|^R) time.Source: §3 · p. 6
3.1 Depth-first search pruning
- Depth-first search fixes columns of the B_d matrices incrementally, allowing branches that fail a chosen sufficiency check to be pruned.The method is applied after fixing the leftmost p columns of each B_d while the corresponding columns of B_0 remain unknown.Source: §3.1 · p. 6
- The pruning implementation stores g_C0 maps in a bit-array or prefix tree, and compresses the f and g maps to reduce memory and computation.The bit-array uses suffix ORs; the prefix tree processes pointwise-membership queries by depth-first search with pruning.Source: §3.1 · pp. 6–7
- For 4 × 4 × 4 at rank threshold R=9 over F2, pruning improves bit-array memory from O(1016) to O(415).The general bound changes from O((R + 1)|F|^n0) to O(min(R, M)|F|^(n0−1)).Source: §3.1 · p. 7
- When the two main checks are too costly, the algorithm falls back to looser pruning methods, conditional on an admissible C0.The first two fallback methods are from prior work [4], while the remaining methods are new.Source: §3.1 · p. 7
4 Maximum rank
The section establishes bounds for maximum tensor rank and uses them with computed cases to determine maximum ranks for additional shapes over F2. In particular, it derives rank 11 for k × 4 × 3 when 0 ≤ k ≤ 11, reducing the needed computation to k ≤ 8.
4 Maximum rank
- The substitution method lowers a tensor's rank by at least one after an appropriate contraction along an axis.Repeated subbing out gives a rank lower bound that increases by one each time.Source: §4 · pp. 7–8
- For every m,n ≥ 1, the maximum rank ℛ(mn−1,m,n) equals mn−1.The section also gives a padding construction that raises a known maximum rank by p when the enlarged dimensions allow p additional positions.Source: §4 · p. 8
- For m,n ≥ 2 except (2,2), the maximum rank ℛ_F2(mn−3,m,n) equals mn−1.The result follows after establishing rank 5 for the 3 × 3 × 2 tensor over F2.Source: §4 · p. 8
- ℛ(k, 4, 3) = 11 for 0 ≤ k ≤ 11, so the algorithm need only run on k × 4 × 3 for k ≤ 8.The section also concludes that ℛ(k, 3, 3) = 8 for all k ≥ 6, completing the maximum-rank results for k × 3 × 3 shapes with prior work.Source: §4 · p. 8
5 Results
The results section reports computational searches across tensor shapes, including maximum-rank tensors and elapsed times. It also gives a Kronecker-product description for the max-rank 4×4×4 tensor and derives lower bounds for k×4×4 shapes.
5 Results
- The results tables report canonical-tensor counts, maximum ranks, example maximum-rank tensors, and elapsed times for enumeration and rank computation.Elapsed times are listed only for n0 because canonical tensors of a given shape include smaller n0 shapes up to zero-padding.Source: §5 · p. 8, Table 2 · p. 9, Table 1 · p. 9
- Remark 10 represents the max-rank 4×4×4 tensor as a Kronecker product, with factors related to rank-3 2×2×2 tensors.The passage identifies those factors as precisely all non-isomorphic tensors of shape 2×2×2 and rank 3.Source: §5 · p. 10
- The max-rank 6×4×3 and 8×4×3 tensors are constructed by augmenting the max-rank 3×3×3 and 5×3×3 tensors, respectively.The augmentations are to ∗×4×3 via Lemma 7.Source: §5 · p. 10
- The section gives explicit optimal decompositions for listed 3×4×4 and 4×4×4 tensors, using two and three copies of the shown term, respectively.The authors provide decompositions for tensors whose rank is below their number of nonzero elements.Source: §5 · p. 10
5.1 Lower bounds for 𝑘× 4 × 4
- Results for ℛ(k, 4, 3), combined with Lemmas 7 and 9, yield lower bounds for ℛ(k, 4, 4).Table 3 lists the best known lower bounds to the authors’ knowledge alongside maximum ranks for other analyzed shapes.Source: §5.1 · p. 10