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 Sharp Threshold Bound for Monotone Graph Properties

For every integer n≥2n \ge 2, every nontrivial increasing family P\mathcal{P} of graphs on nn vertices invariant under all vertex permutations, and every 0<ε<1/20 < \varepsilon < 1/2, p1−ε(P)−pε(P)≤219(log⁡n)2log⁡12εp_{1-\varepsilon}(\mathcal{P}) - p_{\varepsilon}(\mathcal{P}) \le \frac{2^{19}}{(\log n)^2} \log \frac{1}{2\varepsilon}.

For every integer n≥2n \ge 2, every Boolean function ff on EnE_n invariant under vertex permutations, and every 0<p<10 < p < 1, Var⁡p(f)≤217(log⁡n)2Ip(f)\operatorname{Var}_p(f) \le \frac{2^{17}}{(\log n)^2} I_p(f), with no monotonicity assumption needed.

Let m≥2m \ge 2 be real and let h:{0,1}J→{0,1}h : \{0,1\}^J \to \{0,1\} satisfy Ii(h)≤I(h)/mI_i(h) \le I(h)/m for every i∈Ji \in J. If k=σlog⁡m64k = \frac{\sigma \log m}{64}, then ∑1≤∣S∣≤kh^(S)2≤m−1/4I(h)\sum_{1 \le |S| \le k} \widehat{h}(S)^2 \le m^{-1/4} I(h).

Let 3≤m≤n3 \le m \le n be an integer, let BB be uniform among the mm-element subsets of [n][n], and set FB={e∈En:e∩B≠∅}F_B = \{e \in E_n : e \cap B \neq \emptyset\} and k=σlog⁡m64k = \frac{\sigma \log m}{64}. Then ∑S⊆EnPr⁡B{1≤∣S∩FB∣≤k}f^(S)2≤2mnm−1/4I(f)\sum_{S \subseteq E_n} \Pr_B \{1 \le |S \cap F_B| \le k\} \widehat{f}(S)^2 \le \frac{2m}{n} m^{-1/4} I(f).

Suppose t=log⁡n≥16t = \log n \ge 16, and put m=⌊n⌋m = \lfloor \sqrt{n} \rfloor and k=σlog⁡m64k = \frac{\sigma \log m}{64}. Then ∑S⊆En,1≤∣S∣≤k2/2f^(S)2≤4m−1/4I(f)\sum_{S \subseteq E_n, 1 \le |S| \le k^2/2} \widehat{f}(S)^2 \le 4m^{-1/4} I(f).

Methods

Biased (4,2)(4,2)-hypercontractivity via direct two-point inequality and tensorization on product spaces {0,1}J\{0,1\}^J with ρ=p(1−p)4\rho = \frac{\sqrt{p(1-p)}}{4}.

Source excerpts

“Put rho = sigma/4, so 0 < rho <= 1/8, and define the linear operator T_rho by T_rho chi_S = rho^{|S|} chi_S. ... We have proved ||T_rho g||_4 <= ||g||_2 (2.4) on every finite product.” · Show in paper

Random vertex-block restriction leaving free all edges FBF_B incident with a uniform mm-element vertex subset B⊆[n]B \subseteq [n] while conditioning on exterior edges HB=En∖FBH_B = E_n \setminus F_B, combined with exact Fourier averaging.

Source excerpts

“Lemma 3.1 (Exact averaging over a restriction). Let F subseteq E_n, put H = E_n \ F, and, for y in {0,1}^H, let f_y(x) = f(x,y) for x in {0,1}^F.” · Show in paper

“Fix B, and fix an arbitrary assignment y to H_B = E_n \ F_B. The free set F_B contains all edges with at least one endpoint in B: both edges within B and edges from B to its complement. Every permutation supported on B fixes each edge of H_B individually, and hence fixes y.” · Show in paper

Integration of the Russo-Margulis probability-derivative differential inequality ddplog⁡μ(p)1−μ(p)≥(log⁡n)2C0\frac{d}{dp} \log \frac{\mu(p)}{1-\mu(p)} \ge \frac{(\log n)^2}{C_0} over the transition interval [pε,p1−ε][p_\varepsilon, p_{1-\varepsilon}].

Source excerpts

“On the interval [p_epsilon, p1−epsilonp_{1-epsilon}], division in (4.2) is legitimate and gives d/dp log(mu(p)/(1 - mu(p))) = mu'(p) / (mu(p)(1 - mu(p))) >= (log n)^2 / C_0.” · Show in paper