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

Conditional coordinate sweeps and analytic transfer

There are absolute constants g>0g > 0 and d0d_0 such that for d≥d0d \ge d_0 and every λ⊢2d\lambda \vdash 2^d, the binary coordinate sweep operator satisfies ∥Kλ∥op≤Dλ−g\|K_\lambda\|_{\mathrm{op}} \le D_\lambda^{-g} with the sign representation annihilated, and there is an absolute positive integer ww such that the law after ww independent sweeps converges to uniform in total variation as d→∞d \to \infty uniformly over deterministic initial decks, giving tmix(d)=Θ(d)t_{\mathrm{mix}}(d) = \Theta(d) physical Thorp shuffle steps.

For every integer t≥0t \ge 0, ∥qd∗t−UN∥TV≥1−2tN/2N!\|q_d^{*t} - U_N\|_{\mathrm{TV}} \ge 1 - \frac{2^{tN/2}}{N!}, and consequently tmix(d)≥⌈2Nlog⁡2(3N!4)⌉=2d−O(1)t_{\mathrm{mix}}(d) \ge \lceil \frac{2}{N} \log_2(\frac{3N!}{4}) \rceil = 2d - O(1).

There are a power of two R≥2R \ge 2, a positive integer qq, and z∗>0z_* > 0 such that every allowed grid and every family H\mathcal{H} of hh prescribed disjoint trajectories satisfy log⁡TλH≤−c(s)F(λ)+e(s)hlog⁡s−C(H)\log T_\lambda^{\mathcal{H}} \le -c(s)F(\lambda) + e(s)h \log s - C(\mathcal{H}) for every z∈[0,z∗]z \in [0, z_*] and every λ⊢s−h\lambda \vdash s - h, where c(s)=c0+1/log⁡sc(s) = c_0 + 1/\sqrt{\log s} and e(s)=e0−1/log⁡se(s) = e_0 - 1/\sqrt{\log s} with c0=e0=1/10000c_0 = e_0 = 1/10000.

For every 0<θ<10 < \theta < 1 and K0≥1K_0 \ge 1, there are ρ>0\rho > 0 and R0R_0 such that for each power of two R≥R0R \ge R_0, one can choose zsp(R)>0z_{\mathrm{sp}}(R) > 0 so that for every allowed grid, prescribed family H\mathcal{H}, integer k≥1k \ge 1 with h≤K0kh \le K_0 k and h+k≤s1−θh + k \le s^{1-\theta}, and λ⊢M=s−h\lambda \vdash M = s - h with λ1=M−k\lambda_1 = M - k or λ1′=M−k\lambda_1' = M - k, we have ∥KλH∥op≤s−ρk\|K_\lambda^{\mathcal{H}}\|_{\mathrm{op}} \le s^{-\rho k} for all z∈[0,zsp(R)]z \in [0, z_{\mathrm{sp}}(R)].

In the signed tensor representation of SlS_l on V⊗lV^{\otimes l} with V=E⊕OV = E \oplus O (dim⁡E=dim⁡O=p\dim E = \dim O = p), the isotypic types present are precisely those in the (p,p)(p,p)-hook, and for every such type α⊢l\alpha \vdash l there is a probability distribution μα\mu_\alpha on even densities such that Pα⪯exp⁡{F(α)+O(p2log⁡(s+1))}Er∼μαr⊗lP_\alpha \preceq \exp\{F(\alpha) + O(p^2 \log(s+1))\} \mathbb{E}_{r \sim \mu_\alpha} r^{\otimes l}, with multiplicity at most exp⁡(O(p2log⁡(s+1)))\exp(O(p^2 \log(s+1))) and at most (s+1)2p(s+1)^{2p} types present.

Under the induction hypothesis for fewer than bb coordinates, every family H′\mathcal{H}' of h′h' prescribed trajectories on the current grid and every (p,p)(p,p)-hook diagram γ⊢s−h′\gamma \vdash s - h' satisfy log⁡TγH′≤−c^F(γ)+e^h′log⁡s−C(H′)+s9/10\log T_\gamma^{\mathcal{H}'} \le -\widehat{c} F(\gamma) + \widehat{e} h' \log s - C(\mathcal{H}') + s^{9/10}.

Methods

Alternating placement kernel Q(x,y)=s−k∑A⊆[k](−1)k−∣A∣s∣A∣pA(xA,yA)Q(x,y) = s^{-k} \sum_{A \subseteq [k]} (-1)^{k-|A|} s^{|A|} p_A(x_A, y_A) extended by zero outside endpoint injections to isolate a sparse irreducible block and bound its operator norm by ∥Q∥HS\|Q\|_{\mathrm{HS}}.

Source excerpts

“Define a kernel from input placements to output placements by Q(x, y) = s−ks^{-k} sum_{A subseteq [k]} (-1)^{k-|A|} s∣A∣s^{|A|} p_A(x_A, y_A). ... Consequently ||K_lambda^H||_op <= ||Q||_HS.” · Show in paper

Inverse-gamma moment identity EZ−v=Γ(α−v)/Γ(α)\mathbb{E} Z^{-v} = \Gamma(\alpha - v)/\Gamma(\alpha) for Z∼Gamma(α,1)Z \sim \mathrm{Gamma}(\alpha, 1) combined with density tilting to express falling-factorial line factors as expectations over independent line variables WL=m/ZLW_L = m/Z_L.

Source excerpts

“At each light line introduce W_L = m/Z_L, where the Z_L are independent gamma variables with shape m - h_L + 1 and unit rate. The elementary identity E Z−vZ^{-v} = Gamma(alpha - v)/Gamma(alpha) for Z ~ Gamma(alpha, 1), 0 <= v < alpha, follows by integrating the gamma density.” · Show in paper

Signed tensor representation on V⊗lV^{\otimes l} with V=E⊕OV = E \oplus O and Haar-averaged even density domination Pα⪯exp⁡{F(α)+O(p2log⁡(s+1))}Er∼μαr⊗lP_\alpha \preceq \exp\{F(\alpha) + O(p^2 \log(s+1))\} \mathbb{E}_{r \sim \mu_\alpha} r^{\otimes l} for (p,p)(p,p)-hook isotypic projections.

Source excerpts

“Let p in [1, s] be an integer and let V = E oplus O, where E and O each have dimension p. On VotimeslV^{otimes l}, l <= s, let S_l permute the slots with signs ... For every such type there is a probability distribution mu_alpha on even densities such that, in positive semidefinite order, P_alpha <= exp{F(alpha) + O(p^2 log(s + 1))} Er mualphaE_{r ~ mu_alpha} rotimeslr^{otimes l}.” · Show in paper

Boundary-limsup maximum principle for subharmonic functions applied to H=log⁡∣f∣+AGH = \log|f| + AG on the slit disk Ω={z∈C:∣z∣<r}∖[u,v]\Omega = \{z \in \mathbb{C} : |z| < r\} \setminus [u, v] to transfer operator norm bounds from a small real segment [u,v][u, v] to z=1z = 1.

Source excerpts

“The function H = log|f| + AG is subharmonic on Omega. ... The boundary-limsup maximum principle for subharmonic functions [5, Chapter I, Section 4.C.1, Theorem (4.14)] gives H <= 0 on Omega. Since 1 in Omega, it follows that log|f(1)| <= -AG(1).” · Show in paper

Finite-group Fourier analysis (Diaconis-Shahshahani upper bound combining Cauchy-Schwarz with matrix Plancherel) to bound total variation distance ∥μw−UN∥TV\|\mu_w - U_N\|_{\mathrm{TV}} from operator norm bounds on Kλ(1)K_\lambda(1).

Source excerpts

“The classical finite-group Fourier argument of Diaconis and Shahshahani [6, Section 2, Lemma 2, and the proof of Lemma 14] combines Cauchy-Schwarz with matrix Plancherel to give ||mu_w - U_N||_TV^2 <= (1/4) sum_{lambda != (N)} D_lambda ||K_lambda(1)^w||_2^2 <= (1/4) sum_{lambda not in {(N), (1^N)}} D_lambda^{2-2gw}.” · Show in paper