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 algebraic envelopes and the Boone–Higman conjecture

For every finitely generated group GG, GG has decidable word problem if and only if GG embeds in a finitely presented simple group.

Every finitely generated group with decidable word problem embeds in a finitely presented group Γ\Gamma admitting a faithful two-transitive action on a countably infinite set, such that every point stabilizer of this action is finitely generated.

For every finitely generated group LL with decidable word problem, there exist over k=F2k = \mathbb{F}_2 a nonzero finitely presented unital algebra BB, a simple subalgebra A⊆BA \subseteq B with identity ee, an embedding L↪A×L \hookrightarrow A^\times, an injective nonunital algebra homomorphism ϕ:B→B\phi: B \to B with ϕ(B)⊆A\phi(B) \subseteq A and p=ϕ(1B)≠1Bp = \phi(1_B) \neq 1_B, elements s0,s1,t0,t1∈pBps_0, s_1, t_0, t_1 \in pBp commuting with ϕ(B)\phi(B) satisfying tisj=δijpt_i s_j = \delta_{ij} p and s0t0+s1t1=ps_0 t_0 + s_1 t_1 = p, and an element b∗∈Bb_* \in B such that r≠0  ⟹  ψ(r)⋅b∗≠0r \neq 0 \implies \psi(r) \cdot b_* \neq 0 for r∈R=B⊗kBopr \in R = B \otimes_k B^{\mathrm{op}} and ψ=ϕ⊗ϕop\psi = \phi \otimes \phi^{\mathrm{op}}.

Let RR be a unital associative ring, ψ:R→R\psi: R \to R an additive multiplicative map with P=ψ(1)P = \psi(1), and suppose U0,U1,V0,V1∈PRPU_0, U_1, V_0, V_1 \in PRP commute with ψ(R)\psi(R) and satisfy ViUj=δijPV_i U_j = \delta_{ij} P and U0V0+U1V1=PU_0 V_0 + U_1 V_1 = P. Then the homomorphism θ:St6(R)→St6(R)\theta: \mathrm{St}_6(R) \to \mathrm{St}_6(R) given by xij(a)↦xij(ψ(a))x_{ij}(a) \mapsto x_{ij}(\psi(a)) satisfies θ(ker⁡π)=1\theta(\ker \pi) = 1.

For any finitely generated group G^\widehat{G} with decidable word problem, there exist a finitely presented monoid KK with zero Ω≠1K\Omega \neq 1_K and a finitely generated monoid HH with decidable word problem and zero ζ≠1H\zeta \neq 1_H satisfying: (i) an injective group homomorphism G^→H×\widehat{G} \to H^\times; (ii) an injective unital monoid homomorphism κ:T→H\kappa: T \to H with κ(0T)=ζ\kappa(0_T) = \zeta where T=(K∖{Ω})×P⊔{0T}T = (K \setminus \{\Omega\}) \times \mathcal{P} \sqcup \{0_T\}; (iii) finite-tuple selectors L,R∈HL, R \in H isolating h1h_1 from h2,…,hdh_2, \dots, h_d; (iv) an injective multiplicative map c:H→Kc: H \to K disjoint from {1K,Ω}\{1_K, \Omega\}; and (v) a separator z∈Hz \in H injecting (T∖{0T})2(T \setminus \{0_T\})^2 into H∖{ζ}H \setminus \{\zeta\} via (τ,τ′)↦κ(τ)zκ(τ′)(\tau, \tau') \mapsto \kappa(\tau)z\kappa(\tau').

For a finitely generated group GG with decidable word problem, the HNN extension G^=⟨G×G,s∣s(g,g)s−1=(1,g) (g∈G)⟩\widehat{G} = \langle G \times G, s \mid s(g,g)s^{-1} = (1,g) \ (g \in G) \rangle is finitely generated, has decidable word problem, contains G×GG \times G, and satisfies [(g,g),s]=(g,1)[(g,g), s] = (g,1) for all g∈Gg \in G.

For the algebra BB in Theorem 2.2 and R=B⊗kBopR = B \otimes_k B^{\mathrm{op}}, the affine Steinberg group Γ0=B6⋊St6(R)\Gamma_0 = B^6 \rtimes \mathrm{St}_6(R) is finitely presented.

From a program index η\eta one can compute a finite monoid presentation KηK_\eta with zero Ω\Omega, an additive grade γ\gamma with 0≤γ(x)≤20 \le \gamma(x) \le 2, and a partial word algorithm NηN_\eta that, whenever fηf_\eta is defined, length-nonincreasing, and context-compatible up to length mm, terminates on all words of grade at most mm with grade-nonincreasing derivations, preserves outputs under single presentation equations of grade at most mm, and if this holds for all mm, decides equality in KηK_\eta with Nη(raw(u)raw(v))=raw(fη(uv))N_\eta(\mathrm{raw}(u)\mathrm{raw}(v)) = \mathrm{raw}(f_\eta(uv)).

Methods

Twisted Brin–Thompson embedding criterion (Zaremsky): embedding a finitely presented group acting faithfully and two-transitively on a countably infinite set with finitely generated point stabilizers into a nontrivial finitely presented simple group.

Source excerpts

“Theorem 2.3 (Zaremsky). Suppose a finitely presented group Λ acts faithfully on a nonempty countable set X. If the point stabilizers are finitely generated and there are finitely many orbits on the unordered two-element subsets of X, then Λ embeds in a nontrivial finitely presented simple group.” · Show in paper

Affine Steinberg group and mapping torus construction: forming the finitely presented group Γ0=B6⋊St6(R)\Gamma_0 = B^6 \rtimes \mathrm{St}_6(R) and taking its mapping torus Γ\Gamma along a nonunital coefficient endomorphism Θ=(ϕ(6),θ)\Theta = (\phi^{(6)}, \theta) to pass to the direct limit (M∞6⋊E∞)⋊Z(M_\infty^6 \rtimes E_\infty) \rtimes \mathbb{Z}.

Source excerpts

“Proposition 3.3. For the algebra B in Theorem 2.2, the group Γ0 = B6 ⋊ St6(R), R = B ⊗k Bop, is finitely presented.” · Show in paper

“Lemma 5.2. There are compatible isomorphisms lim−→(Γ0, Θ) ∼= M6∞ ⋊ E∞, Γ ∼= (M6∞ ⋊ E∞) ⋊ Z.” · Show in paper

Four-corner splitting in St6(R)\mathrm{St}_6(R): using two splitting pairs Ui,Vi∈PRPU_i, V_i \in PRP commuting with ψ(R)\psi(R) to decompose P=E0+E1P = E_0 + E_1 and E0=E00+E01E_0 = E_{00} + E_{01} into equivalent orthogonal corners, annihilating ker⁡π\ker \pi in one step.

Source excerpts

“Define four idempotents by Ei = UiVi (i = 0, 1), E0i = U0UiViV0 (i = 0, 1). They commute with ψ(R), and the pair relations give the orthogonal decompositions P = E0 + E1, E0 = E00 + E01.” · Show in paper

Contracted monoid algebras and partial affine maps: constructing A0=k0[H]A_0 = k_0[H] and B=k0[K]B = k_0[K] over k=F2k = \mathbb{F}_2, embedding A0A_0 into BB via i(h)=ch−cζi(h) = c_h - c_\zeta, and using the partial affine monoid P\mathcal{P} to produce a nonunital self-embedding ϕ\phi with splitting pairs and a separating vector b∗=i(z)b_* = i(z).

Source excerpts

“To prove Theorem 2.2 for a given group L, apply Theorem 6.2 with Gb = L and set A0 = k0[H], B = k0[K].” · Show in paper

“Lemma 6.4. There is a nonzero idempotent q ∈ k[P] and elements s′0, s′1, t′0, t′1 ∈ qk[P]q such that t′is′j = δijq, s′0t′0 + s′1t′1 = q.” · Show in paper

Bounded compiler and Kleene fixed-point coding: compiling a finite monoid presentation KηK_\eta and partial evaluator NηN_\eta with an additive grade γ\gamma from a program index η\eta, then using Kleene's Recursion Theorem and a decreasing dependency bound m=M⌊n/D0⌋<nm = M\lfloor n/D_0 \rfloor < n to prove totality, stability, and confluence by length induction.

Source excerpts

“The program index determines the presentation without running the program. The evaluator is also fixed independently of a length bound; its termination and compatibility with equations will be proved from the program’s behavior within that bound.” · Show in paper

“Kleene’s Recursion Theorem [12] supplies an index with fη(w) = F(η, w) (36) as partial functions.” · Show in paper

HNN commutator reduction and balanced diagonal embedding: embedding GG into G^\widehat{G} so (g,1)=[(g,g),s](g,1) = [(g,g),s] and realizing (g,1)(g,1) in E6(R)\mathrm{E}_6(R) as a commutator [D12(ag),D13(b)][D_{12}(a_g), D_{13}(b)] of balanced diagonal matrices.

Source excerpts

“Taking the commutator of balanced diagonal matrices on two different pairs of coordinates gives [D12(ag), D13(b)] = diag(ν¯((g, 1)), 1, 1, 1, 1, 1).” · Show in paper