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

Computing the Random 3-SAT Threshold

There is a real number α3∈(0,∞)\alpha_3 \in (0, \infty) such that lim⁡n→∞p(n,⌊an⌋)=1\lim_{n\to\infty} p(n, \lfloor an \rfloor) = 1 for a<α3a < \alpha_3 and 00 for a>α3a > \alpha_3, and there is one finite deterministic Turing machine which, on input 1r1^r for any integer r≥1r \ge 1, halts with a rational number qrq_r satisfying ∣qr−α3∣≤2−r|q_r - \alpha_3| \le 2^{-r}, using no oracle, advice, or noncomputable real constant.

For α∈[0,20]\alpha \in [0, 20], given a computable sequence of rationals (ℓk)k≥1(\ell_k)_{k\ge 1} with ℓk≤α\ell_k \le \alpha and ℓk→α\ell_k \to \alpha, an effectively enumerable class of finite descriptions QQ, and a uniformly computable real G(a,β;Q)G(a, \beta; Q) such that G(a,β;Q)<0G(a, \beta; Q) < 0 implies α≤a\alpha \le a and every rational a>αa > \alpha has some (β,Q)( \beta, Q ) with G(a,β;Q)<0G(a, \beta; Q) < 0, one finite deterministic Turing machine on unary input 1r1^r (r≥1r \ge 1) returns a rational within 2−r2^{-r} of α\alpha.

The limit α\alpha in Proposition 4.3 lies in [1/200,10][1/200, 10], and for every fixed real a≥0a \ge 0, the relaxed Poisson model satisfies Pn(an)→1P_n(an) \to 1 for 0≤a<α0 \le a < \alpha and Pn(an)→0P_n(an) \to 0 for a>αa > \alpha; the same limits hold for p(n,⌊an⌋)p(n, \lfloor an \rfloor) in the proper-clause model, so α3=α\alpha_3 = \alpha.

The real fnf_n is computable uniformly in the integer nn, and there is a computable rational sequence (ℓn)n≥1(\ell_n)_{n\ge 1} with ℓn<α\ell_n < \alpha and ℓn→α\ell_n \to \alpha.

For every fixed real 0≤a<α0 \le a < \alpha and every fixed β>0\beta > 0, lim inf⁡n→∞1nElog⁡Zn(a,β)≥0\liminf_{n\to\infty} \frac{1}{n} \mathbb{E}\log Z_n(a, \beta) \ge 0; for every fixed real a>αa > \alpha, some positive integer β\beta satisfies lim sup⁡n→∞1nElog⁡Zn(a,β)<0\limsup_{n\to\infty} \frac{1}{n} \mathbb{E}\log Z_n(a, \beta) < 0.

For rational a>0a > 0, positive integer β\beta, and a finite description Q∈QQ \in \mathcal{Q}, the value G1(a,β;Q)G_1(a, \beta; Q) is uniformly computable, and strict negativity of this value is semidecidable by certified rational upper bounds.

For every a>0a > 0 and finite β>0\beta > 0, the pressure limit P(a,β)=lim⁡n→∞Ln/n=sup⁡n≥1Ln/nP(a, \beta) = \lim_{n\to\infty} L_n/n = \sup_{n\ge 1} L_n/n exists, and every finite-depth strict site-only trial satisfies Ln≤nG1L_n \le n G_1 (n≥1n \ge 1) and P(a,β)≤G1P(a, \beta) \le G_1.

For every a>0a > 0 and finite β>0\beta > 0, P(a,β)=inf⁡Q∈QG1(a,β;Q)P(a, \beta) = \inf_{Q\in\mathcal{Q}} G_1(a, \beta; Q), where Q\mathcal{Q} is the countable, effectively enumerable class of rational trials.

For positive rational aa, positive integer β\beta, and a rational trial QQ, the inequality G1(a,β;Q)<0G_1(a, \beta; Q) < 0 certifies α≤a\alpha \le a; every rational a>αa > \alpha has such a certificate; and the class of certified densities is effectively enumerable.

For all integers n≥1n \ge 1 and 0≤r≤n0 \le r \le n, and every v∈[n]v \in [n], E[(Fr+v−Fr)p]≤260\mathbb{E}[(F_r^{+v} - F_r)^p] \le 2^{60} for p=6/5p = 6/5, and uniformly in rr, E∣Fr−EFr∣p≤262n\mathbb{E}|F_r - \mathbb{E}F_r|^p \le 2^{62} n.

The sequence fn/nf_n/n converges to a real number α\alpha, and for every integer k≥1k \ge 1, α≥fk/k−267k−1/6\alpha \ge f_k/k - 2^{67} k^{-1/6}.

For all integers n≥1n \ge 1 and 0≤r≤n0 \le r \le n, EFr/n≤fn/n+253(r/n)1/6\mathbb{E}F_r/n \le f_n/n + 2^{53}(r/n)^{1/6}, and for every fixed real a>αa > \alpha, there exists ϵ>0\epsilon > 0 such that with probability tending to one, every assignment violates more than ⌊ϵn⌋\lfloor \epsilon n \rfloor clauses.

For ∣X∣≤C|X| \le C almost surely, any two nondecreasing vectors t,t′∈(0,1]d\mathbf{t}, \mathbf{t}' \in (0, 1]^d satisfy ∣TtX−Tt′X∣≤52C2e4C∥t−t′∥∞|\mathcal{T}_{\mathbf{t}}X - \mathcal{T}_{\mathbf{t}'}X| \le \frac{5}{2}C^2 e^{4C} \|\mathbf{t} - \mathbf{t}'\|_\infty, and for a single operation and 0≤t≤10 \le t \le 1, 0≤TtX−EX≤12C2e2Ct0 \le T_t X - \mathbb{E}X \le \frac{1}{2}C^2 e^{2C} t, with constants independent of the depth dd.

For U>P(a,β)U > P(a, \beta), 0<η,m0<10 < \eta, m_0 < 1, (1−η)J<m0(1-\eta)^J < m_0, chosen finite test sets, structural tolerance δ>0\delta > 0, and ρ>0\rho > 0, there is a terminal one-packet trial with G1≤U+ρG_1 \le U + \rho, at most JJ processed blocks, and depth at most 2J+12J+1, satisfying the structural records.

Methods

Staged fair search through computable lower certificates and semidecidable upper-certificate intervals to approximate a threshold without a convergence modulus.

Source excerpts

“Start with [l, u] = [0, 20]. Fix an effective enumerator of the triples (a, β, Q) in the statement. At stage s, run it for s computation steps from its start. For every triple emitted during those steps, compute its value intervals at all accuracy indices at most s, and compute ℓ1, . . . , ℓs. ... Replace l by the maximum of its old value and the lower certificates just computed. Whenever a value interval has a strictly negative upper endpoint, replace u by min{u, a}. After each update, if u − l ≤ 2^{1−r}, output (u + l)/2 and halt.” · Show in paper

Residual-set conditioning and dyadic binning of two-literal elimination probabilities to bound the 6/56/5 moment of the free-deletion survival delay, combined with a Doob martingale over variable-index buckets.

Source excerpts

“Clauses containing the free variable once become two-literal tests after that variable is fixed. A batch of relaxed three-literal tests can replace each such test at controlled loss. This is the residual-set conditioning principle used in Friedgut’s half-cube lemma [9, Lemma 5.7] and in Carenini’s sequential clause replacement [5, Theorem 4.3 and Lemma 6.1].” · Show in paper

Weighted satisfiability interpolation between local and global Poisson clauses, variable-weight balancing via parity characters, and dyadic block merging.

Source excerpts

“Interpolate between independent Poisson counts of local and weighted global clauses, with respective means (1 − s)t and st, for 0 ≤ s ≤ 1.” · Show in paper

Diluted three-literal interpolation against a Ruelle probability cascade to obtain sound upper bounds on the soft pressure.

Source excerpts

“Use the cascade of Lemma 5.4. For each reservoir occurrence, attach a fresh tree of site marks and a fresh root site uniform. ... Poisson differentiation and Equation (5.12) now give d/ds E log Zs = an sum_{l>=1} w^l/l E<x^3 + 2y^3 - 3xy^2> >= 0, because x^3 + 2y^3 - 3xy^2 = (x - y)^2(x + 2y) >= 0.” · Show in paper

Conditional Gaussian probing, ultrametric cut partitioning, and Austin-Panchenko product-tree representation to reorganize shared nonroot variables while recording conditional site laws.

Source excerpts

“In Subsections 7.3–7.4, we perturb the law at the initial level by a compensated Gaussian field. After selecting one conditional law, this perturbation gives identities for inner products of conditional site-test means. ... Subsection 7.5 uses these identities to organize the samples into a nested partition at at most two thresholds. An exchangeability theorem then represents the partitioned array using independent variables along a sample tree and a site tree, including the variables shared by all sites.” · Show in paper

Collapsing shared nonroot variables by independent site sampling from recorded Wasserstein-1 kernels and discretizing to rational step functions on dyadic grids.

Source excerpts

“Approximate this pair in L^1 by rational-valued step functions on finite dyadic rectangular grids. For example, conditional expectations on the successive dyadic grids converge in L^1, and subsequent rational quantization preserves the range [0, 1]^2 and the convergence.” · Show in paper