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

Quasipolynomial Bounds for Arithmetic Progressions

For every fixed integer k≥3k \ge 3, there exist constants Ck,ck,εk>0C_k, c_k, \varepsilon_k > 0 such that for every N≥2N \ge 2, rk(N)≤CkNexp⁡(−ck(log⁡N)εk)r_k(N) \le C_k N \exp(-c_k (\log N)^{\varepsilon_k}), where rk(N)r_k(N) is the largest size of a subset of {1,…,N}\{1, \dots, N\} with no nonconstant kk-term arithmetic progression.

Every set A⊆NA \subseteq \mathbb{N} with ∑a∈Aa−1=∞\sum_{a \in A} a^{-1} = \infty contains nonconstant arithmetic progressions of every finite length (Erdős's conjecture).

For fixed k≥3k \ge 3, the rr-color van der Waerden number Wr(k)W_r(k) satisfies Wr(k)≤⌈exp⁡(Ak(2+log⁡r)Ak)⌉W_r(k) \le \lceil \exp(A_k (2 + \log r)^{A_k}) \rceil for all r≥1r \ge 1.

Given a progression-free input on a positive-dimensional integer box with a two-box density certificate at threshold a≥e−pa \ge e^{-p} (p≥2p \ge 2) and width logs Qh=log⁡(2/wh)Q_h = \log(2/w_h), if every root side has logarithmic cutoff polynomial in pp, dimension data, and all QhQ_h, then either the hypotheses are impossible or a root slice carries a new certificate at threshold (1+η)a(1+\eta)a with di′−di≤d0+Pi(p,di+1,…,dD)d'_i - d_i \le d_0 + P_i(p, d_{i+1}, \dots, d_D) and Qi′−Qi≤Pi′(p,dimension forecasts,Qi+1,…,QD)Q'_i - Q_i \le P'_i(p, \text{dimension forecasts}, Q_{i+1}, \dots, Q_D).

A progression-free [0,1][0, 1]-valued function of mean at least a≥e−pa \ge e^{-p} (p≥2p \ge 2) on a box of positive dimension nn with sufficiently large sides (logarithmic cutoff polynomial in 2+p+n2+p+n) either has impossible hypotheses or admits a degree-ss polynomial patch on a slice with positive score at target (1+ξ)a(1+\xi)a and at most d0=(2+p)Cd_0 = (2+p)^C slots, independent of nn.

For every fixed B≥0B \ge 0, if A⊆NA \subseteq \mathbb{N} satisfies ∑a∈A(log⁡(2+a))Ba=∞\sum_{a \in A} \frac{(\log(2+a))^B}{a} = \infty, then AA contains nonconstant arithmetic progressions of every finite length; moreover, for each fixed B>0B > 0, rk(N)≤Ck,BN(log⁡N)−Br_k(N) \le C_{k,B} N (\log N)^{-B} for N≥3N \ge 3.

Every kk-term-progression-free set A⊆NA \subseteq \mathbb{N} has a uniformly bounded harmonic sum ∑a∈A1a≤Hk\sum_{a \in A} \frac{1}{a} \le H_k and uniform harmonic tail ∑a∈A,a>x1a≤Ck′(log⁡x)1−εke−ck(log⁡x)εk\sum_{a \in A, a > x} \frac{1}{a} \le C'_k (\log x)^{1-\varepsilon_k} e^{-c_k (\log x)^{\varepsilon_k}} for all sufficiently large real xx.

Methods

Triangular polynomial cells with descending precision budgets: representing density-increment regions by successively determined integer blocks bhb_h satisfying ∥bh−Ch(u,b<h)−lh∥∞≤wh\|b_h - C_h(u, b_{<h}) - l_h\|_\infty \le w_h with deg⁡wtCh≤h\deg_{\mathrm{wt}} C_h \le h, where relative width losses at weight hh depend only on dimensions and strictly higher-weight precisions Q>hQ_{>h}.

Source excerpts

“A triangular cell is specified by polynomials Ch(u, b<h) ∈ RdhR^{dh}, deg_wt Ch ≤ h, bounded centers lh, and widths 0 < wh ≤ 1/32.” · Show in paper

“Definition 2.3 (Descending budgets). At layer j, the warm data consist of p, forecasts for all dimensions and structural variable counts, gap parameters depending only on these data, and the widths and numerical budgets already chosen at layers strictly above j.” · Show in paper

Constrained affine sampling with a coefficient tilt: sampling integer-affine maps ψ(t)=x+Vt\psi(t) = x + Vt tilted by an independent product density D\mathcal{D} on an abstract coefficient torus W/ΛW/\Lambda, producing exact polynomial lift identities C(ψ(t))−c=y(ψ(t))+β(ψ(t))C(\psi(t)) - c = y(\psi(t)) + \beta(\psi(t)) without bounding the coefficients of CC.

Source excerpts

“The actual law of the affine maps is dPc(ψ) = ρ(x, V) Dc(coeff C(x + V t)) / Zc, ψ(t) = x + V t.” · Show in paper

“An independent reference law on coefficient arrays describes the desired lifts. Evaluating its density on the coefficients of Ch(x + V t) then tilts the spatial law of (x, V).” · Show in paper

Rank-cut cell preparation: removing low-rank linear relations from rational value spaces WhW_h by backward rank transfer (Lemma 4.2) and relative rank-cut transactions (Lemma 4.3) that preserve the two-box certificate and old determining equations.

Source excerpts

“If a failure probability exceeds its prescribed bound, we obtain a relation at the root and use it to remove one dimension from a rational value space. The modification must retain the old integer tuple, since every higher determining polynomial is evaluated on that tuple and can have arbitrarily large coefficients.” · Show in paper

Width-independent pathwise detection via Conlon–Fox–Zhao cube densification: using high rank to control bounded-grid moments of a pseudorandom chart weight ν(u)=χ(C(u)−c)/aχ\nu(u) = \chi(C(u)-c)/a_\chi and replacing sparse factors by bounded conditional averages before applying the inverse theorem.

Source excerpts

“We instead use high rank to control products of the chart weight, replace all but one of the sparse factors by bounded functions, and apply the inverse theorem to bounded conditional averages. The resulting detector and approximation have costs independent of Qj.” · Show in paper

Shift comparison for positive progression counting: lowering the testing degree of a positive comparison against a translated nonnegative function outside a small exceptional set of shifts, using Bohr-set almost-periodicity (Schoen–Sisask) in degree 1 and finite-list modeling with a common anchor in higher degrees.

Source excerpts

“Shift comparison lowers the degree of a positive test after multiplying by a translate of an arbitrary nonnegative function. The degree-one case uses Bohr-set almost-periodicity. At higher degree we recover the test from two fixed finite lists and apply the induction outside one exceptional set of shifts.” · Show in paper

Active globalization with exact marked projections and affine-plane sections: replacing local polynomial orbits by a stochastic ambient polynomial preserving π0g=PY\pi^0 g = P_Y formally, and solving large modular matching conditions identically via affine-plane sections over Z/MZ\mathbb{Z}/M\mathbb{Z} without charging log⁡M\log M to the width budget.

Source excerpts

“The local orbit includes the higher active determining slots, so its replacement must retain the formal identity π^0 g = PY from Lemma 7.5. This identity will restore the old integer arguments exactly in Section 9.” · Show in paper

“At an active step the full modulus M = M may not have affordable log cost. The following exact finite-ring identity is the reason it need not be imposed on the parent.” · Show in paper