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

Talagrand’s discrete-convexity conjecture

Set k=275k = 2^{75}. For every integer N≥1N \ge 1, every p∈(0,1)p \in (0, 1), and every family D⊆2[N]\mathcal{D} \subseteq 2^{[N]}, if μp(D)≥1−1/k\mu_p(\mathcal{D}) \ge 1 - 1/k, then Ek(D)E_k(\mathcal{D}) is pp-small.

Let L=270L = 2^{70}. For every integer N≥1N \ge 1, every q∈(0,1)q \in (0, 1), and every F⊆2[N]\mathcal{F} \subseteq 2^{[N]} satisfying μq(F)≥1/2\mu_q(\mathcal{F}) \ge 1/2, the family E32(F)E_{32}(\mathcal{F}) is (q/L)(q/L)-small.

Let XX be a finite set, let 0<ρ<10 < \rho < 1, and let r,hr, h be integers with 1≤r≤h1 \le r \le h and h≥64h \ge 64. If H⊆(Xr)\mathcal{H} \subseteq \binom{X}{r} satisfies ∣H∣ρr≤2h+1|\mathcal{H}|\rho^r \le 2^{h+1}, then {S⊆X:∣{e∈H:e⊆S}∣≥212h}\{S \subseteq X : |\{e \in \mathcal{H} : e \subseteq S\}| \ge 2^{12h}\} has a cover G⊆2X\mathcal{G} \subseteq 2^X with cρ(G)≤3⋅2−hc_\rho(\mathcal{G}) \le 3 \cdot 2^{-h}.

There is a universal constant C≥1C \ge 1 (specifically C=50⋅5124C = 50 \cdot 512^4) such that, for every integer N≥1N \ge 1, every p∈(0,1)p \in (0, 1), and every family D⊆2[N]\mathcal{D} \subseteq 2^{[N]}, if μp(D)>1/2\mu_p(\mathcal{D}) > 1/2, then E2(D)E_2(\mathcal{D}) is (p/C)(p/C)-small.

Methods

Elementary covering lemma for uniform hypergraphs via weighted-degree thresholding, independent random sampling of ordered pairs of regular edges, and enumeration of residual tuples.

Source excerpts

“An elementary covering lemma handles each such class: it selects subsets of large weighted degree, independently samples unions of pairs of the remaining edges, and adds the residual configurations.” · Show in paper

Biased Fourier expansion combined with a 32-row signed product measure on binary arrays to convert union-cover obstructions into sixteenth-power weight lower bounds.

Source excerpts

“An orthogonal expansion gives nonnegative weights on subsets with a global bound on their weighted sum. A signed product on an array of 32 rows turns the failure of a union cover into a lower bound on the sixteenth powers of those same weights.” · Show in paper

Coordinate-wise dependent row coupling that preserves marginal Bernoulli product laws μp\mu_p while amplifying the union density to μLp\mu_{Lp} (for Lp<1Lp < 1) or covering [N][N] (for Lp≥1Lp \ge 1).

Source excerpts

“We couple dependent rows so that each entire row has the original Bernoulli product law and their union has an exactly prescribed larger density.” · Show in paper