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

Integer multiplication below n log n

There is one deterministic Turing machine AA, with a fixed finite alphabet and a fixed finite number of one-dimensional tapes, that computes the exact 2n2n-bit product of any two nn-bit integers for every n≥1n \ge 1 in worst-case time TA(n)=O(n(lg⁡n)1−κ)T_A(n) = O(n(\lg n)^{1-\kappa}) with κ=2−182\kappa = 2^{-182}, refuting an eventual Ω(nlog⁡n)\Omega(n \log n) lower bound in this model.

The bit network has WbW_{\mathrm{b}} wires, uses only pointwise XOR gates, sends its input vector to the permutation ρ\rho of that vector, obeys Msink(ρ(w))−Msource(w)=ImM_{\mathrm{sink}(\rho(w))} - M_{\mathrm{source}(w)} = I_m for every input role ww, and has rational rank sum sb=Wbm−N+2Lb<Wbms_{\mathrm{b}} = W_{\mathrm{b}}m - N + 2L_{\mathrm{b}} < W_{\mathrm{b}}m, with sb/Wb<mτs_{\mathrm{b}}/W_{\mathrm{b}} < m^\tau for τ=1−2−50\tau = 1 - 2^{-50}.

For each edge of the complex network, the phase-frame difference CVCU−1\mathcal{C}_V \mathcal{C}_U^{-1} is a product of one translation kernel aI+bXvaI + bX_v, or its inverse, per vector in an orthonormal basis of the edge residual, with total basis length sc=Wcm−2N+2Lc<Wcms_{\mathrm{c}} = W_{\mathrm{c}}m - 2N + 2L_{\mathrm{c}} < W_{\mathrm{c}}m and sc/Wc<mσs_{\mathrm{c}}/W_{\mathrm{c}} < m^\sigma for σ=1−2−50\sigma = 1 - 2^{-50}.

There exist fixed 0<τ<10 < \tau < 1 and one fixed finite-alphabet multitape procedure that transforms an arbitrary bit array on [P]×[2u]×[G]×[2u]×[B][P] \times [2^u] \times [G] \times [2^u] \times [B] by the address permutation (p,h,g,d,z)↦(p,d,g,h,z)(p, h, g, d, z) \mapsto (p, d, g, h, z) in O(Vuτ)O(Vu^\tau) steps, where V=PGB22uV = PGB2^{2u}.

Under the parameter conditions of Proposition 14, a simultaneous normalized butterfly layer H0⊗DH_0^{\otimes D} on DD selected bits of KK-bit chunks can be approximated on a fixed-tape machine in O(Vdλ′)O(Vd^{\lambda'}) time (with λ′<1\lambda' < 1) and maximum coefficient error less than 22−p\sqrt{2} 2^{-p}.

Under the hypotheses of Lemma 16, normalized cyclic convolution Mr\mathcal{M}_r on disk grid operands over Rr=C[y]/(yr+1)\mathcal{R}_r = \mathbb{C}[y]/(y^r+1) has an approximation with error less than 2M(3ℓ+1)2−p\sqrt{2} M(3\ell + 1)2^{-p} and cost O(Tp[dK+pKτ−1+ℓdλ′+log⁡(rp)])O(Tp[dK + pK^{\tau-1} + \ell d^{\lambda'} + \log(rp)]).

Tensor Gaussian resampling RFs=2γB0QFtAR F_{\mathbf{s}} = 2^\gamma \mathcal{B}_0 Q F_{\mathbf{t}} \mathcal{A} can be approximated without executing the permutations R,QR, Q with error less than dp22−pdp^2 2^{-p} in O(dTp3/2+δα+Tpd2(1+ℓτ))O(dTp^{3/2+\delta}\alpha + Tpd^2(1+\ell^\tau)) time.

There are deterministic Turing machines with fixed finite alphabets and fixed finite numbers of one-dimensional tapes that compute exact integer division with remainder and integer square root for nn-bit inputs in O(n(lg⁡n)1−κ)O(n(\lg n)^{1-\kappa}) worst-case time, with κ=2−182\kappa = 2^{-182}.

A row-major n1×n2n_1 \times n_2 array of bb-bit strings (with m=n1n2bm = n_1 n_2 b) can be transposed on a fixed multitape Turing machine in O(m(lg⁡m)1−κ)O(m(\lg m)^{1-\kappa}) time; in particular, an n×nn \times n binary matrix can be transposed in O(n2(lg⁡n)1−κ)O(n^2(\lg n)^{1-\kappa}) time.

Methods

Finite linear networks with subspace labels and endpoint frames (a bit network with rational subspaces for address shears, and a complex network with binary subspaces for phase layers) that restore arbitrary initial scratch values.

Source excerpts

“We construct two fixed linear networks that exchange two banks of values while restoring every auxiliary value. When the values are replaced by arrays, a common representation on all wires at a gate lets that gate act pointwise without disturbing the representation.” · Show in paper

Lower-triangular Bruhat matrix factorization (A=E1ΠE2A = E_1 \Pi E_2) adapted to tape order to implement rational matrix shears via recursive field interchanges.

Source excerpts

“Lemma 9 (Lower triangular factorization). Every rational m × m matrix A of rank a has a factorization A = E1ΠE2, where E1, E2 are invertible lower triangular rational matrices and Π has exactly a entries equal to one, with at most one in each row and column, and all remaining entries zero.” · Show in paper

Packed selected-bit addition on rectangles using cyclic shifts of whole chunk ranges and deterministic radix-sort repair of an explicitly bounded exceptional address set.

Source excerpts

“The construction first uses a constant number of cyclic shifts of whole chunk ranges, then corrects an explicitly bounded set of addresses. The correction depends only on addresses, so the time bound is worst-case over all payloads.” · Show in paper

Synthetic polynomial transforms over C[y]/(yr+1)\mathbb{C}[y]/(y^r+1) with retained frequency order (LBFt−LB F_{\mathbf{t}}^-) and signed Kronecker packing.

Source excerpts

“Pointwise multiplication commutes with applying the same record permutation LB to both operands. We may therefore multiply the forward outputs in their retained order and pass that order directly to the opposite procedure.” · Show in paper

Gaussian resampling with source and target coordinate permutations (R,QR, Q) retained in the transform identity, combined with Bluestein's chirp identity and Chinese-remainder-theorem cyclic-convolution layout.

Source excerpts

“Gaussian resampling connects these two shapes. Its usual implementation sorts twice on each coordinate. We retain both permutations in the transform formula and compute that formula directly.” · Show in paper

Classical Newton reductions for reciprocal and square root at geometrically increasing precisions, followed by exact remainder and square tests.

Source excerpts

“We use the classical Newton reductions as presented by Brent [5, Lemmas 2.1–2.4], with their tape costs made explicit.” · Show in paper