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

Finite tensor savings and exact Fourier circuits

In the unrestricted nonuniform complex linear-circuit model, lim inf⁡n→∞L(n)nlog⁡2n=0\liminf_{n\to\infty} \frac{L(n)}{n \log_2 n} = 0; equivalently, for every c>0c > 0 and every integer N0≥2N_0 \ge 2, there is an integer n≥N0n \ge N_0 and an exact circuit for FnF_n with fewer than cnlog⁡2ncn \log_2 n gates.

If a finite win exists, there are integers nm→∞n_m \to \infty and exact linear circuits for FnmF_{n_m} whose scalar gate counts satisfy L(nm)=o(nmlog⁡2nm)L(n_m) = o(n_m \log_2 n_m).

There exist an invertible nonmonomial matrix AA of a finite width qq, an integer b≥2b \ge 2, and a word on exactly qbq^b coordinates implementing A⊗bA^{\otimes b} with monomials and fewer than bqb−1bq^{b-1} calls to AA.

If (A,b,g)(A, b, g) and a specified winning word form a finite win, then there are constants C<∞C < \infty and 0<α<10 < \alpha < 1 such that A⊗kA^{\otimes k} has an exact scalar linear circuit with at most Cqk(k+1)αC q^k (k+1)^\alpha gates for every integer k≥0k \ge 0.

For every integer r≥1r \ge 1, the unnormalized Fourier matrix FrF_r has a factorization on exactly rr coordinates into O(1+log⁡4r)O(1 + \log^4 r) monomial and pair layers, with an absolute implied constant.

Under the no-win assumption, there is a function p:⋃n≥1GLn(C)→[0,∞)p : \bigcup_{n \ge 1} \mathrm{GL}_n(\mathbb{C}) \to [0, \infty) vanishing exactly on monomial matrices, satisfying monomial invariance, product subadditivity, exact tensor and direct-sum laws, inverse and transpose symmetry, and p(U)=1p(U) = 1 for U=(1011)U = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}.

Under the no-win assumption, if an invertible matrix KK has an invertible square submatrix MM, then p(M)≤p(K)p(M) \le p(K).

Under the no-win assumption, for K=(MCBD)∈GLn+r(C)K = \begin{pmatrix} M & C \\ B & D \end{pmatrix} \in \mathrm{GL}_{n+r}(\mathbb{C}) with M∈GLn(C)M \in \mathrm{GL}_n(\mathbb{C}) and H(z)=M+zC(Ir−zD)−1BH(z) = M + zC(I_r - zD)^{-1}B, if s0∈Cs_0 \in \mathbb{C} satisfies det⁡(Ir−s0D)≠0\det(I_r - s_0 D) \ne 0 and det⁡H(s0)≠0\det H(s_0) \ne 0, then p(H(s0))≤p(K)p(H(s_0)) \le p(K).

Under the no-win assumption, if X(z)∈Matn(C(z))X(z) \in \mathrm{Mat}_n(\mathbb{C}(z)) is regular and invertible at z0∈Cz_0 \in \mathbb{C}, and there exist a finite set E⊂CE \subset \mathbb{C} and a real constant C0C_0 such that X(s)X(s) is defined, invertible, and satisfies p(X(s))≤C0p(X(s)) \le C_0 for every s∉Es \notin E, then p(X(z0))≤C0p(X(z_0)) \le C_0.

Under the no-win assumption, every invertible 2×22 \times 2 matrix all of whose entries are nonzero has price at most 3/23/2.

Under the no-win assumption, if AA is a real symmetric w×ww \times w matrix with hh supported unordered off-diagonal pairs and RR acts as +I+I on ker⁡A\ker A and −I-I on (ker⁡A)⊥(\ker A)^\perp, then p(R)≤32h+2wp(R) \le \frac{3}{2}h + 2w.

Methods

Unrestricted nonuniform complex linear-circuit model counting every addition, subtraction, and scalar multiplication by arbitrary prechosen complex constants.

Source excerpts

“A linear circuit has inputs x_0, ..., xn−1x_{n-1}, 0 and a finite directed acyclic graph of scalar gates. Each gate computes u + v, u - v, or lambda u from previously available values, with a fixed lambda in C. Each such gate costs one operation, including every scalar multiplication.” · Show in paper

Tensor amplification of a finite win by tensoring a winning word for A⊗bA^{\otimes b} over j=⌊k/b⌋j = \lfloor k/b \rfloor groups and decomposing into direct sums of smaller tensor powers.

Source excerpts

“Tensor the winning word with itself over j groups, multiplying the corresponding slots together. The product of these slots is (A⊗bA^{\otimes b})^{\otimes j} = A⊗bjA^{\otimes bj}.” · Show in paper

Dirty-coordinate replay (uncomputation with arbitrary scratch) to realize (x,y,z)↦(x,y+Mx,z)(x, y, z) \mapsto (x, y + Mx, z) on existing coordinates carrying arbitrary initial values.

Source excerpts

“On disjoint source coordinates x, target coordinates y, and l further coordinates z, there is a word of coordinate shears realizing (x, y, z) |-> (x, y + Mx, z). It uses at most 8l + 2a shears and O((delta + 1)(H + 1)) pair layers. The initial values of z are arbitrary, and may depend on x, y or other data.” · Show in paper

Exact-width Fourier-to-Toeplitz factorization using Newton-polynomial LDLTLDL^{\mathsf{T}} decomposition and displacement-rank chunking.

Source excerpts

“The Fourier-to-Toeplitz identity used next is the geometric-Vandermonde LDL^T factorization of Kuznetsov [13, Theorem 1], specialized to a primitive root of unity.” · Show in paper

Comparison packing into a block-diagonal matrix JJ with random start times and cyclic dummy identity words, combined with finite-dimensional separation and Tychonov compactness to construct a global price function.

Source excerpts

“We will choose a block-diagonal matrix J containing many copies of every A_i and many identity blocks, and compute J⊗bJ^{\otimes b} in fewer than the usual b|J|^{b-1} calls to J.” · Show in paper

Time-cascade and coefficient-boundary comparison for data-state cells to prove invertible corner contraction, feedback laws, and algebraic specialization.

Source excerpts

“At each tick, apply the cell along each of the k spatial tensor axes in order, using nk−1n^{k-1} disjoint fibers per axis. Axis j has its own persistent state space W_j = (C^n)^{\otimes(j-1)} \otimes C^r \otimes (C^n)^{\otimes(k-j)}.” · Show in paper

Signed bit-operator reflection contradiction comparing sparse polynomial-perturbation upper bounds and eigenspace-graph lower bounds on an orthogonal reflection RR.

Source excerpts

“We construct a real involution with a large price and then use the orthogonal reflection in its positive eigenspace to obtain incompatible price bounds.” · Show in paper