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

Single-fold Diophantine representations

For every integer n≥1n \ge 1 and every recursively enumerable set S⊆NnS \subseteq \mathbb{N}^n, there are an integer m≥1m \ge 1 and a polynomial P∈Z[A1,…,An,W1,…,Wm]P \in \mathbb{Z}[A_1, \dots, A_n, W_1, \dots, W_m] such that, for every a∈Nna \in \mathbb{N}^n, #{w∈Nm:P(a,w)=0}=1\#\{w \in \mathbb{N}^m : P(a, w) = 0\} = 1 if a∈Sa \in S and 00 if a∉Sa \notin S.

There exist integers m,D≥1m, D \ge 1 for which no algorithm halts and correctly decides, on every input polynomial F∈Z[W1,…,Wm]F \in \mathbb{Z}[W_1, \dots, W_m] of total degree at most DD satisfying the promise #{w∈Nm:F(w)=0}≤1\#\{w \in \mathbb{N}^m : F(w) = 0\} \le 1, whether this set is nonempty.

The group E(Q)E(\mathbb{Q}) for E:y2=x3−25xE : y^2 = x^3 - 25x has rank one and torsion subgroup T={O,(0,0),(5,0),(−5,0)}\mathcal{T} = \{O, (0, 0), (5, 0), (-5, 0)\}, so there exists P∈E(Q)P \in E(\mathbb{Q}) such that every rational point has a unique expression nP+tnP + t with n∈Zn \in \mathbb{Z} and t∈Tt \in \mathcal{T}.

There are a total function g:N→Ng : \mathbb{N} \to \mathbb{N}, a real constant δ>0\delta > 0, and an integer u0≥4u_0 \ge 4 such that the graph of gg has a single-fold Diophantine representation (with unique output and auxiliary coordinates for each input) and δ(log⁡u)2<log⁡g(u)<ulog⁡u\delta (\log u)^2 < \log g(u) < u \log u for all u≥u0u \ge u_0.

Given a total function g:N→Ng : \mathbb{N} \to \mathbb{N} with a complete single-fold graph satisfying δ(log⁡u)2<log⁡g(u)<ulog⁡u\delta (\log u)^2 < \log g(u) < u \log u for u≥u0≥4u \ge u_0 \ge 4, the relation Pow(b,n,c)  ⟺  b≥2 and c=bn\mathrm{Pow}(b, n, c) \iff b \ge 2 \text{ and } c = b^n has a complete single-fold representation.

The binary-digit containment relation x≼yx \preccurlyeq y on N2\mathbb{N}^2 has a complete single-fold Diophantine representation.

For any fixed n≥1n \ge 1 and deterministic counter machine with finitely many states and counters, instructions INC and TESTDEC, and one halt state, there is a finite system of integer polynomial equations in a∈Nna \in \mathbb{N}^n and natural auxiliary variables such that the complete auxiliary tuple has exactly one solution when the initialized machine halts and no solution when it does not halt.

Finite conjunctions of single-fold polynomial systems (with separate auxiliary tuples), compositions of single-fold graphs, and finite unions of single-fold relations with pairwise disjoint argument sets preserve the single-fold property.

Every rational number has exactly one code (p,n,d,t,s,q)∈N6(p, n, d, t, s, q) \in \mathbb{N}^6 satisfying pn=0pn = 0, d=1+t+sd = 1 + t + s, and (p+n)t+d=1+qd(p + n)t + d = 1 + qd, and any fixed finite sequence of rational arithmetic operations and comparisons on valid codes has a single-fold polynomial implementation.

Given valid codes for Q1,Q2∈E(Q)Q_1, Q_2 \in E(\mathbb{Q}), addition has a polynomial implementation with a unique output code for Q1+Q2Q_1 + Q_2 and a unique complete tuple of auxiliary coordinates, and the same holds for any fixed finite chain of additions and multiplication by any fixed positive integer.

For each integer j≥1j \ge 1, exactly one point in (jP+T)∪(−jP+T)(jP + \mathcal{T}) \cup (-jP + \mathcal{T}) satisfies the representative conditions (6), and these are all the representatives.

For any n≥1n \ge 1 and recursively enumerable set S⊆NnS \subseteq \mathbb{N}^n, there is a deterministic counter machine that, when initialized with a1,…,ana_1, \dots, a_n in its first nn counters and zero in its remaining counters, reaches its halt state if and only if a∈Sa \in S.

Methods

Polynomial system conventions for single-fold representations: expressing inequalities F >= G via unique slack variables s in N, representing integers via unique sign codes z = z+ - z- with z+ z- = 0, and gating disjoint cases with Boolean selectors e_i and (1 - e_i)z = 0 for all local variables.

Source excerpts

“In particular, a displayed inequality F ≥ G means F − G = s with a new variable s ∈ N, and F > G means F − G = 1 + s.” · Show in paper

“Write every equation in case i, including its guard and all equations inside nested calls, in the form F = 0, and replace it by eiF = 0. For each variable z local to this case, also impose (1 − ei)z = 0.” · Show in paper

Unique natural-number coding of rational numbers via six-tuples (p, n, d, t, s, q) satisfying pn = 0, d = 1 + t + s, and (p + n)t + d = 1 + qd, and coding of elliptic curve points using two rational codes and an infinity flag o in {0, 1}.

Source excerpts

“A rational number is represented by six natural numbers (p, n, d, t, s, q) satisfying pn = 0, d = 1 + t + s, (p + n)t + d = 1 + qd.” · Show in paper

Height-based index selection and squaring on the rank-one elliptic curve E: y^2 = x^3 - 25x using the Néron-Tate canonical height comparison and a fixed multiplicative window L_0 <= kappa D_0, D_0 <= kappa L_0 to obtain a total single-fold function g(u) with intermediate growth.

Source excerpts

“On input u ∈ N, require a representative Q satisfying W(Q) ≤ u + W1 < max{W(Q + P), W(Q − P)}.” · Show in paper

“and impose L0 ≤ κD0, D0 ≤ κL0.” · Show in paper

Paired Pell equations with polynomial parameter u = (c+1)^l (n+1)(b+1) + u_0 and growth cutoff F, H < g(u) to obtain a complete single-fold definition of exponentiation c = b^n.

Source excerpts

“b ≥ 2, u = (c + 1)^ℓ (n + 1)(b + 1) + u0, v = g(u), X^2 − ((bu)^2 − 1)F^2 = 1, Y^2 − (u^2 − 1)H^2 = 1, 0 < F < v, 0 < H < v” · Show in paper

Binary-digit containment testing x <= y in binary via three exponentiation calls B = 2^{y+1}, H = B^x, N = (B+1)^y, two divisions to extract the x-th base-B digit d, and parity testing d = 2t + 1.

Source excerpts

“Require x ≤ y and use three calls to Proposition 5.2 to specify B = 2^{y+1}, H = B^x, N = (B + 1)^y. ... Introduce natural variables s, d, r, t and impose N = sBH + dH + r, d < B, r < H, d = 2t + 1.” · Show in paper

Clocked bit-masking encoding of deterministic counter-machine computations in base B = 2^w, where a clock R_0 with final value rho_0 in [B/4, B/2) uniquely determines the power-of-two base B from the halting time.

Source excerpts

“Finally introduce R0, ρ0, η0 for a clock and impose R0 ≼ (2b − 1)M, R0 = ρ0J + η0, η0 < J, R0 = C + B(R0 − ρ0J + M − J), b ≤ ρ0, 2ρ0 < B.” · Show in paper