By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

An Upper Bound of 9/4 for the Matrix Multiplication Exponent

For every ε>0\varepsilon > 0, two n×nn \times n complex matrices can be multiplied using Oε(n9/4+ε)O_\varepsilon(n^{9/4+\varepsilon}) scalar arithmetic operations, and in particular the matrix multiplication exponent ω\omega over C\mathbb{C} satisfies ω≤9/4\omega \le 9/4.

Let M≥1M \ge 1 and A=∑h=1MAhA = \sum_{h=1}^M A_h with Ah∈X⊗Yh⊗ZhA_h \in X \otimes Y_h \otimes Z_h, where the YhY_h are disjoint coordinate spaces and so are the ZhZ_h, with no terms between unmatched second- and third-leg sectors. Then A⊕5M⇝⨁h=1M(Ah⊗BX(M))A^{\oplus 5M} \rightsquigarrow \bigoplus_{h=1}^M (A_h \otimes B_X(M)), where each AhA_h on the right has its own copy of XX.

Let T=∑i=1sTiT = \sum_{i=1}^s T_i be a sum of nonzero tensors with a common first space and matched, pairwise disjoint sectors on the other two legs. For every tensor character λ\lambda and every probability vector q=(q1,…,qs)q = (q_1, \dots, q_s), λ(T)≥epXH(q)∏i=1sλ(Ti)qi\lambda(T) \ge e^{p_X H(q)} \prod_{i=1}^s \lambda(T_i)^{q_i}, where H(q)=−∑i=1sqilog⁡qiH(q) = -\sum_{i=1}^s q_i \log q_i.

For a≥1a \ge 1 and b≥2b \ge 2, the symmetrized profile P(a,b)P(a, b) of polynomial multiplication satisfies discrete concavity 2P(a,b)≥P(a,b+1)+P(a,b−1)2P(a, b) \ge P(a, b+1) + P(a, b-1), and by symmetry the analogous inequality holds in the first argument.

For all positive integers a,ha, h, the symmetrized profile P(a,b)P(a, b) satisfies shifted tripling P(a,3h+a−1)≥3P(a,h)P(a, 3h + a - 1) \ge 3P(a, h).

Let P:N>02→R>0P : \mathbb{N}_{>0}^2 \to \mathbb{R}_{>0} be symmetric with P(1,b)=bP(1, b) = b, satisfying discrete concavity (4.6) for a≥1,b≥2a \ge 1, b \ge 2 and shifted tripling (4.9) for a,h≥1a, h \ge 1. Then P(a,a)≥a4/3P(a, a) \ge a^{4/3} for every a≥1a \ge 1.

Let d≥2d \ge 2 and k≥0k \ge 0 be integers with k<dνk < d^\nu, where ν=inf⁡n≥2log⁡nR(Tn)\nu = \inf_{n \ge 2} \log_n R(T_n). There is a tensor character λ\lambda with λ(Td)≥k\lambda(T_d) \ge k.

Methods

Finite separation of a shared tensor leg using a primitive L-th root of unity (L = 5M) for Fourier projection on L copies combined with a quadratic-mismatch variable weighting (g - h)^2 to degenerate into independent blocks carrying an auxiliary dot product B_X(M).

Source excerpts

“Set L = 5M, and choose a primitive Lth root of unity ζ. Index the L source copies by r = 0, . . . , L − 1.” · Show in paper

“On every surviving term, (3.2) gives g 2 + hu − h 2 − hv = (g − h) 2 ≥ 0.” · Show in paper

Determinant filtration (degree-one Clebsch-Gordan exact sequence) applied to C(a, b) tensor B_X(2) to obtain a block lower-triangular multiplication representation and degenerate to C(a, b+1) + C(a, b-1) with a shared first leg.

Source excerpts

“Put D = uw − vs. For e ≥ 1, diagonal substitution (s, w) = (u, v) gives the exact sequence 0 −→ DVe−1 −→ Ve ⊗ W1 −→ Ve+1 −→ 0. (4.7)” · Show in paper

Three-sector index partitioning and linear weighting of polynomial multiplication C(a, 3h+a-1) to degenerate into three matched branches sharing the first leg.

Source excerpts

“Give weight +1 to middle Y -coordinates, weight −1 to middle Z-coordinates, and zero to all other coordinates.” · Show in paper

Symmetrized profile P(a, b) defined as the normalized geometric mean of character values of C(a, b) over all six leg permutations in S_3.

Source excerpts

“Define the symmetrized profile P(a, b) =   Y π∈S3 λπ(C(a, b))   1/(6t) . (4.4)” · Show in paper

Constructing detecting tensor characters via cone separation, Grothendieck-group catalytic comparisons, and the Schauder-Tychonoff fixed-point theorem.

Source excerpts

“The space R S is Hausdorff and locally convex, so the Schauder–Tychonoff fixed-point theorem [17] applies: a continuous self-map of a nonempty compact convex subset of such a space has a fixed point.” · Show in paper

“Map this identity to the additive Grothendieck group of S by sending es to [s].” · Show in paper