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

The sharp logarithmic exponent of r(5,t)

There is an absolute constant C>0C > 0 such that, for every ε>0\varepsilon > 0, all sufficiently large integers tt satisfy t4(log⁡t)3+ε≤r(5,t)≤Ct4(log⁡t)3\frac{t^4}{(\log t)^{3+\varepsilon}} \le r(5, t) \le C \frac{t^4}{(\log t)^3}, where the threshold for tt may depend on ε\varepsilon; consequently, lim⁡t→∞4log⁡t−log⁡r(5,t)log⁡log⁡t=3\lim_{t\to\infty} \frac{4 \log t - \log r(5, t)}{\log \log t} = 3.

There is an absolute constant CC such that, for every integer t≥2t \ge 2, r(5,t)≤Ct4(log⁡t)3r(5, t) \le C \frac{t^4}{(\log t)^3}.

For every fixed 0<η<1/100 < \eta < 1/10 and every sufficiently large prime qq, there is a stream of N=⌊q4log⁡q⌋N = \lfloor q^4 \log q \rfloor flags whose ordered flag graph is K5K_5-free and has independence number less than k=⌊q(log⁡q)1+η⌋k = \lfloor q (\log q)^{1+\eta} \rfloor.

Suppose a selected consistent tuple and context satisfy (5)–(7) with deterministic ℓ=Θ(k)\ell = \Theta(k), bounded stream-marginal density, and the rectangle-occupancy event of Lemma 3.3 almost surely. Then either the high-rank argument contradicts Lemma 3.4, or a constant-probability extraction produces another such tuple of deterministic length Θ(k)\Theta(k) and a new context satisfying (26) with w≤Cσ1+η/2/Dw \le C \sigma^{1+\eta/2} / D, whose decoder is independent of the old context.

Under the parameter conditions σβ≤D≤σ1−η/2\sigma^\beta \le D \le \sigma^{1-\eta/2}, L=Dσ8βL = D\sigma^{8\beta}, R∈[σβ,2σβ+2]∩2NR \in [\sigma^\beta, 2\sigma^\beta + 2] \cap 2\mathbb{N}, P=LRP = LR, and for 2≤d≤42 \le d \le 4 and nonempty S⊆US⊆PdS \subseteq U_S \subseteq \mathcal{P}_d, T⊆UT⊆Pd∗T \subseteq U_T \subseteq \mathcal{P}_d^* with ∣S∣∣T∣≥qd+1e−b|S||T| \ge q^{d+1}e^{-b} (0≤b≤CbDσ6β0 \le b \le C_b D\sigma^{6\beta}) and e(S,T)/(∣S∣∣T∣)≤τ/qe(S, T)/(|S||T|) \le \tau/q (0<τ≤σ−200⋅2d−2β0 < \tau \le \sigma^{-200 \cdot 2^{d-2} \beta}), oriented so ∣S∣≤∣T∣|S| \le |T|, there is a public-table scheme for which, except with probability O(e−cq)O(e^{-cq}), the encoder can send a message of length at most CqP(dS+dT+P)C q P (d_S + d_T + P) bits describing a set W⊆USW \subseteq U_S such that ∣W∣≤∣S∣eCP|W| \le |S|e^{CP} and ∣W∩S∣≥c∣S∣|W \cap S| \ge c|S|.

Suppose n=q1+vn = q^{1+v}, v≤3/2+O(1/σ)v \le 3/2 + O(1/\sigma), n/4≤n′≤nn/4 \le n' \le n, g0>χ0g_0 > \chi_0, and e−g0/20<a≤2e^{-g_0/20} < a \le 2, with M=n′a/qM = n'a/q and K=n4/3q−1e−g0/5K = n^{4/3}q^{-1}e^{-g_0/5}. If XX is a set of at most nn points of PG(d,q)\mathrm{PG}(d, q) (3≤d≤43 \le d \le 4) such that every projective plane contains at most KK points of XX, then the number of lines containing at least MM points of XX is at most Cn/MCn/M.

Under the small-cell conclusions of Lemma 7.1 and (for d≥3d \ge 3) Lemma 8.2, together with ∣S∣∣T∣≥qd+1e−b|S||T| \ge q^{d+1}e^{-b} and e(S,T)/(∣S∣∣T∣)≤τ/qe(S, T)/(|S||T|) \le \tau/q, the Poisson score procedure using RR independent Poisson batches of mean LqLq sampled uniformly from S′S' computes a set WW such that, with probability at least exp⁡[−C(Pτ+1)]\exp[-C(P\tau + 1)], the row has at most 2qP2qP samples, ∣W∣≤neCP|W| \le n e^{CP}, and ∣W∩S′∣≥cn′|W \cap S'| \ge c n'.

Methods

Uniform-independent-set method and random vertex sampling to prove the classical upper bound r(5, t) <= C t^4 / (log t)^3.

Source excerpts

“Our proof uses the uniform-independent-set method of Alon [2]; see also Shearer [20] for the triangle-free independence bound and Davies, Jenssen, Perkins, and Roberts [8] for sharp occupancy estimates.” · Show in paper

Ordered projective-flag graph construction on PG(4, q) where positions i < j are adjacent if a_i is incident to b_j and a_j is not incident to b_i.

Source excerpts

“A flag is a pair (a, b) ∈ P_4 × P_4^* with a ⊥ b. ... Choose a stream X_1, ..., X_N of independent uniform flags. Its graph has vertex set {1, ..., N}; writing X_i = (a_i, b_i), its edge rule for i < j is i ~ j ⇐⇒ a_i ⊥ b_j and a_j ̸⊥ b_i.” · Show in paper

Entropy compression along a balanced binary tree of windows using two marking scans, pre-round decoupling, and fresh incidence tests.

Source excerpts

“Build a balanced binary tree on it from Section 5: its root is the middle window, and recurse on the earlier and later halves. Each node has its original supports A, B from Lemma 5.5.” · Show in paper

Greedy removal of hyperplanes and planes (peeling) to either reduce the projective dimension via a large cell or obtain a small-cell training set.

Source excerpts

“If d = 4 and g_1 > χ_0, repeatedly choose a hyperplane containing the largest number of remaining points of S. Remove its remaining points whenever this number is at least q^2.” · Show in paper

Polynomial method over the algebraic closure of F_q with degree D_0 < q, using Hessian polynomials and resultants, to bound rich lines under a plane cap.

Source excerpts

“Counting monomials in three variables produces a nonzero polynomial vanishing on that sample, of degree D_0 ≤ C A1/3A^{1/3} √(n/M). ... D_0 = o(M), D_0 = O(q21/40q^{21/40}) < q” · Show in paper

Poisson score procedure using R independent Poisson batches of mean Lq and public random tables to describe a capturing set W for sparse point-hyperplane pairs.

Source excerpts

“Take R independent Poisson batches, each of mean Lq, whose points are independent and uniform in S'.” · Show in paper