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

No bigeodesics in planar first-passage percolation

Planar first-passage percolation on Z2\mathbb{Z}^2 with independent identically distributed nonnegative nonatomic edge weights tet_e of common Borel law GG has almost surely no bigeodesic, provided E[min⁡{X1,X2,X3,X4}2]<∞\mathbb{E}[\min\{X_1, X_2, X_3, X_4\}^2] < \infty for independent X1,X2,X3,X4X_1, X_2, X_3, X_4 with law GG.

Almost surely there is a finite H(z)≥1H(z) \ge 1 for every z∈Z2z \in \mathbb{Z}^2 such that every upper ray from zz lies in Q+(z,H(z))Q^+(z, H(z)) and every lower ray from zz lies in Q−(z,H(z))Q^-(z, H(z)), and for every fixed L<∞L < \infty, max⁡∣z∣≤LnH(z)=o(n)\max_{|z|\le Ln} H(z) = o(n) as n→∞n \to \infty.

Almost surely, simultaneously for all ρ∈EI(U)\rho \in \mathcal{E}_I(U), every two UU-rays of label −ρ-\rho coalesce, and the same statement holds with upper and lower sectors exchanged, simultaneously for the countable collection of charts.

Almost surely EI(ω)\mathcal{E}_I(\omega) is at most countable, and the same conclusion holds with II replaced by −I-I.

For a fixed bin (α,β)I(\alpha, \beta)_I, integer spacing l≥1l \ge 1, and gain b>0b > 0, if sites on the horizontal grid kj=(jl,0)k_j = (jl, 0) are marked with common marginal probability qα,βq_{\alpha,\beta} and successive marks k<yk < y in the bin satisfy b≤Bα(y,k)+B−β(y,k)b \le B_\alpha(y, k) + B_{-\beta}(y, k), then blqα,β≤r(β)−r(α)\frac{b}{l} q_{\alpha,\beta} \le r(\beta) - r(\alpha).

Almost surely there is no upper or lower fork in any of the countably many charts under consideration.

There is a finite constant CC, depending only on the chart and the weight law, such that for every lattice edge ee and every H≥1H \ge 1, ENe(H)≤C(H+1)\mathbb{E} N_e(H) \le C(H+1).

On one event of probability one, whenever two oriented bigeodesics p,qp, q in any fixed chart have the same upper label, their two Busemann functions agree: Bp+=Bq+B_{p^+} = B_{q^+} and Bp−=Bq−B_{p^-} = B_{q^-}. This assertion is simultaneous over the bigeodesics and their possibly random labels, and also holds almost surely in every environment whose law is absolutely continuous with respect to the iid law.

With R0R_0 fixed, for every positive integer MM the common coupling defines marks JM(k)∈{0,1}J_M(k) \in \{0, 1\} at all horizontal sites with common marginal probability P(JM(k)=1)≥p/4\mathbb{P}(J_M(k) = 1) \ge p/4, selecting a bigeodesic pkp_k in Tk,R(M)T^{k, R(M)} through kk with upper label ρk∈I\rho_k \in I avoiding all partition endpoints, arms in Q±(k,H0)Q^\pm(k, H_0), total increase at least MM on its first R(M)R(M) upper-arm edges, and increase at least gg on one of its first R0R_0 upper-arm edges.

Almost surely, for each positive integer MM, the selected upper labels at distinct marked sites of Λ\Lambda are distinct.

Two random coalescing geodesics with the same full-plane Busemann linear functional agree almost surely under the assumptions of Theorem 1.1, without assuming integrability of restricted boundary passage times.

Methods

Half-plane transfer coupling (V_n, W_n) resampling complementary half-planes across horizontal cuts H_n = {z in Z^2 : z_2 = -n} along a deterministic subsequence n_k -> infinity to preserve finite collections of upper rays and lower-ray tails with their exact labels.

Source excerpts

“Take independent iid replacement arrays A(n), D(n), all independent of U, and define (24) (Vn)e = Ue if e in E+n, A(n)e if e not in E+n; (Wn)e = D(n)e if e in E+n, Ue if e not in E+n.” · Show in paper

Spatially varying low-to-high Bernoulli edge-weight perturbation X_hat_e with replacement scale delta_h = eta / ((h+2) log(h+2)) at height h, keeping the total variation distance from the iid law uniformly small while achieving divergent gain along a selected path.

Source excerpts

“For an edge e with endpoints w, w', put h(e) = max{|w2|, |w'2|}, delta_h = eta / ((h+2) log(h+2)), h >= 0, where eta > 0 will be chosen shortly, independently of M. Require delta_0 <= pa/2, and define (60) xi_e = 1{Xe <= a0, Ue <= delta_{h(e)}/pa}, X_hat_e = Ze if xi_e = 1, Xe if xi_e = 0.” · Show in paper

Conditioning on an individual modified environment Yk,RY^{k,R} and a Borel version of a path selector to obtain an explicit independent Bernoulli product law for the latent raise indicators xi_e along any finite prefix in A_k(R).

Source excerpts

“Lemma 7.2 (Conditioning on an individual output). Fix k, R. Conditional on the entire individual environment Yk,RY^{k,R}, the variables (xi_e : e in Ak(R)) are independent Bernoulli variables with respective success probabilities (66) theta_e(Yk,RY^{k,R}_e) = 1_{[b0,infty)}(Yk,RY^{k,R}_e) delta_{h(e)} / (pb + delta_{h(e)}).” · Show in paper

Shared-sample union metrics Tk,y,RT^{k,y,R} using the same raised samples X_hat_e on A_k(R) union A_y(R) without applying the replacement operation twice, preserving both selected bigeodesics and their labels.

Source excerpts

“For two horizontal sites k, y, let Yk,y,RY^{k,y,R} instead use X_hat_e on Ak(R) union Ay(R), with metric Tk,y,RT^{k,y,R}. In an overlap there is one use of the same sample X_hat_e. We never apply the replacement operation twice to an edge.” · Show in paper

Finite stationary boundary correction D_G(x) = lim_{j->infinity} (T_H(x, v_j) - T(x, v_j)) combined with bounded truncation X_k = min{Delta(k, k+1), 1} to compare restricted half-plane Busemann functions without boundary integrability.

Source excerpts

“Lemma A.1 (Finite boundary correction). For x in H intersect Z^2, the limit D_G(x) = lim_{j->infinity} (TH(x, vj) - T(x, vj)) exists and is finite and nonnegative, where (vj) is any ray of G and the targets are sufficiently far along its H-contained tail.” · Show in paper