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

A Torsion-Free Group Algebra with Zero Divisors

There exist a finitely presented torsion-free group GG and nonzero elements α,β∈F2[G]\alpha, \beta \in \mathbb{F}_2[G] such that αβ=0\alpha\beta = 0, disproving Kaplansky's zero-divisor conjecture; moreover, GG admits a finite two-dimensional classifying space.

There is a constant δ>0\delta > 0 (for example, δ=1/600\delta = 1/600) such that for every sufficiently large hh, ∑W∈ThP(W)2≤e−2δh\sum_{W \in T^h} P(W)^2 \le e^{-2\delta h}.

For all sufficiently large admissible nn, there is a tuple of matchings with girth(Γ)≥L=⌊clog⁡n⌋\mathrm{girth}(\Gamma) \ge L = \lfloor c \log n \rfloor, and in the uniform distribution on such tuples conditioned on any feasible set of ss prescribed matching pairs, the probability of an additional specified pair not already prescribed in either direction is at most 1np−s−rn\frac{1}{np - s - r_n} with rn=O(d∗2L+2)=o(n)r_n = O(d_*^{2L+2}) = o(n) uniform over all prescriptions.

With conditional probability tending to one, every connected component of Γ\Gamma has diameter at most D0LD_0 L, for a fixed constant D0D_0.

There is a constant ε>0\varepsilon > 0, depending only on the fixed types and turn weights, such that for every fixed K≥1K \ge 1, C≥1C \ge 1, and I≥0I \ge 0, the conditional probability tends to zero that Γ\Gamma contains a system of at most KK paths (all cyclically immersed and closed except possibly one immersed interval path starting at xAx_A or xBx_B), total length HH with L≤H≤CLL \le H \le CL, at most II interval pairs satisfying (3.1), and b≤εHb \le \varepsilon H unpaired occurrences.

With probability 1−o(1)1 - o(1), Γ\Gamma admits no reduced spherical arrangement; in particular, for all sufficiently large admissible nn there exist graphs of the prescribed types, with girth at least LL and the diameter bound of Lemma 2.3, admitting no such arrangement.

The complex XX satisfies π2(X)=0\pi_2(X) = 0; moreover, if a path in Γ\Gamma starts at xAx_A or xBx_B and ends at a different vertex, its label is nontrivial in G=π1(X)G = \pi_1(X).

The universal cover of XX is contractible, and GG is torsion-free.

Methods

Prescribing outgoing signed-label sets on two disjoint vertex sets A,BA, B using lines in the finite projective plane over F128\mathbb{F}_{128} together with three extra letters so that ∣Sx∩Sy∣|S_x \cap S_y| is odd for every x∈A,y∈Bx \in A, y \in B, and sampling random bijections for each inverse pair.

Source excerpts

“For each vertex x, prescribe a set S_x \subset T of outgoing labels as follows: 1. On either side the ordinary part of S_x is a line, with every line represented equally often. 2. Within each line class on A, the extra part is each of the three two-element subsets with proportion p/2 apiece, and is otherwise empty. 3. Within each line class on B, the extra part is all three extras with proportion p, and is otherwise empty.” · Show in paper

Girth conditioning and edge-switching (transposing bad edges with distant non-bad edges) to bound conditional edge-prescription probabilities in the random matching model.

Source excerpts

“Transpose the two matches, replacing xy, uz by xz, uy. ... Thus the map from a tuple containing xy, together with an admissible transposition, to its output tuple is injective.” · Show in paper

Multiplicity-stage decomposition, simultaneous pigeonhole alignment of comparison offsets into blocks, and squared-word-weight binning to bound the expected number of realizations of bounded path systems.

Source excerpts

“The simultaneous pigeonhole principle gives an integer 1 \le u \le N^d such that dist(ua/L, \mathbb{Z}) \le 1/N for every offset a. ... On each chain use the full grid intervals [ks, (k+1)s) contained in [0, \ell], for integers k \ge 0.” · Show in paper

Recursive Lipton-Tarjan planar separation combined with short non-cancelling path closures and planar gap counting to reduce arbitrary reduced spherical arrangements to bounded patterns.

Source excerpts

“The planar separator theorem of Lipton and Tarjan [14, Corollary 2, p. 183] supplies, in any simple planar graph with s vertices, at most 2\sqrt{2s} vertices whose deletion leaves components with at most 2s/3 vertices. Apply this theorem recursively to each component with more than K vertices.” · Show in paper

Cone-picture representation of sphere and disk maps into XX and minimal-boundary-length band-cancellation surgery to establish asphericity and root separation.

Source excerpts

“Suppose an arc joins occurrences of the same underlying unoriented edge in \Gamma. A sufficiently narrow band around that arc maps into the corresponding open rose edge. ... Join the incident disks along the band. ... Total new boundary length is smaller by two before any further tightening.” · Show in paper