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 power saving for planar halving lines

There exist absolute constants ε>0\varepsilon > 0, C<∞C < \infty, and n0n_0 such that, for every even n≥n0n \ge n_0 and every nn-point set P⊂R2P \subset \mathbb{R}^2 with no three collinear, the number of unordered halving pairs h(P)h(P) satisfies h(P)≤Cn4/3−εh(P) \le C n^{4/3 - \varepsilon}. The proof is nonquantitative and does not supply numerical values for ε\varepsilon, CC, or n0n_0.

There are absolute constants ε>0\varepsilon > 0 and C<∞C < \infty such that for every integer N≥1N \ge 1, every generic NN-point planar configuration PP, and every integer 0≤k≤N0 \le k \le N, the total number of rank-kk switches Sk(P)S_k(P) satisfies Sk(P)≤CN4/3−εS_k(P) \le C N^{4/3 - \varepsilon}.

There are absolute constants ε0>0\varepsilon_0 > 0 and C0<∞C_0 < \infty such that, for every integer n≥2n \ge 2 and every integer 1≤k≤n/21 \le k \le n/2, the number of kk-sets of any nn-point set Q⊂R2Q \subset \mathbb{R}^2 with no three collinear is at most C0n(k+1)1/3−ε0C_0 n (k+1)^{1/3 - \varepsilon_0}, and the same bound holds for comp⁡(Λk(L))\operatorname{comp}(\Lambda_k(\mathcal{L})) for any arrangement L\mathcal{L} of nn nonvertical straight lines with no parallel pair and no three concurrent.

For every ξ>0\xi > 0 there is Qξ<∞Q_\xi < \infty such that, for every generic NN-point configuration, every rank, and every integer 1≤b≤N1 \le b \le N with N/b≥QξN/b \ge Q_\xi, any collection of intervals with disjoint step sets and activity at least bb has at most ξ(N/b)4/3\xi (N/b)^{4/3} members.

There is a Borel set G⊂EG \subset E with λK0(G)>0\lambda_{K_0}(G) > 0, a further subsequence, and a translation and uniform rescaling of each normalized Euclidean plane such that over every p∈π(G)p \in \pi(G) the limiting graph of LnL_n has a unique position l(p)l(p) in the closed unit disk satisfying ∣l(p)−l(q)∣≥cG∣p−q∣1+1/16|l(p) - l(q)| \ge c_G |p-q|^{1+1/16} for p,q∈π(G)p,q \in \pi(G), and the position marginal νG\nu_G of the enhanced vertex measure satisfies νG(B(x,r))≤CGr32/17\nu_G(B(x,r)) \le C_G r^{32/17} for x∈R2x \in \mathbb{R}^2 and 0<r<10 < r < 1.

If for every η>0\eta > 0 there is Rη<∞R_\eta < \infty such that for every generic NN-point configuration, every rank, and every 1≤b≤N1 \le b \le N with N/b≥RηN/b \ge R_\eta, the number of step-disjoint intervals of activity at least bb is at most η(N/b)4/3\eta (N/b)^{4/3}, then there are absolute constants ε>0\varepsilon > 0 and CC such that every such rank sweep has at most CN4/3−εC N^{4/3 - \varepsilon} switches.

Methods

Reduce sweep intervals of activity at least bb to consecutive distance-aa batches, decompose each batch's complete bipartite exchange graph into aa perfect matchings, and partition the edges into convex and concave polygonal chains to apply an imbalanced bipartite crossing inequality with designated endpoints.

Source excerpts

“Lemma 2.2 (Activity and endpoint distance). Fix a generic N-point set and a rank k. For an integer b ≥ 4, any collection of intervals of activity at least b can be divided into two classes.” · Show in paper

“Lemma 2.4 (Two chain partitions). For a consecutive window of batches, let S be the number of distinct endpoints of its exchange edges. Those edges partition into at most aS convex polygonal chains, and also into at most aS concave polygonal chains.” · Show in paper

“Lemma 2.5 (Crossings with designated endpoints). Let a simple graph be drawn with straight segments on v distinct points, with no vertex in an edge interior and no crossings of incident edges.” · Show in paper

Construct smoothed rank coordinates rJ(x,y)r_J(x,y) from convex chain partitions of dyadic time windows JJ, embed points into the compact rank cube Z=[0,1]NZ = [0,1]^{\mathbb{N}}, and pass to weak limits of vertex, participating-vertex, edge-time, and crossing measures.

Source excerpts

“rJ (x, y) = 1/M ∑_{i=1}^M Φ((y − gJ,ig_{J,i}(x))/ε_J).” · Show in paper

“Compactness and bounded masses give a common weakly convergent subsequence for this countable collection of measures. In particular μ and ν are probability measures.” · Show in paper

Use coordinatewise monotonicity of rank coordinates, almost-everywhere Fréchet differentiability, and the critical-image measure-zero lemma to find three transverse sweep directions, and apply a three-foliation compactness lemma to prevent collapse under local linear normalization.

Source excerpts

“Lemma 4.1. A bounded Borel function on an open rectangle in R2 that is monotone in each coordinate is Fréchet differentiable almost everywhere with respect to planar Lebesgue measure.” · Show in paper

“Lemma 5.1 (Three-foliation compactness). Let Ωj ⊂ R2 be open sets containing every compact subset of R2 for all sufficiently large j. Let Fj : R2 → Ωj be homeomorphisms.” · Show in paper

Pass to a Hausdorff limit of the inverse rank maps LnL_n on a positive-mass Borel set GG with uniform scale parameters and truncated vertex-projection density, obtaining a spatial measure νG\nu_G with disk mass O(r32/17)O(r^{32/17}) and strip mass O(r15/17)O(r^{15/17}).

Source excerpts

“To put all spatial limits on one subsequence, let X be a compact metric compactification of R2, and take the closures of the graphs of Ln in [0, 1]2 × X. Pass to a subsequence on which these compact sets converge in Hausdorff distance to a closed relation Γ.” · Show in paper

Bound participating vertices in a bounded open parallelogram BB during a narrow angular window by three narrow strips perpendicular to the initial normal plus twice the number of marked-token boundary crossings of BB.

Source excerpts

“Lemma 7.1 (Three strips). Let P be a finite subset of R2, let B be a bounded open set, and let D ≥ 1 satisfy |x| ≤ D for x ∈ B.” · Show in paper

Convert a uniform little-oo activity-packing bound into a power-saving bound via a fixed-scale greedy block partition and induction, and derive kk-set and level bounds via point-line duality and Matoušek's shallow-cutting lemma.

Source excerpts

“Partition the sweep greedily, ending a block when its activity first reaches b, and include any final remainder.” · Show in paper

“Apply Matoušek’s shallow-cutting lemma in the form stated by Agarwal, Aronov, Chan, and Sharir [1, Lemma 3.2 and the following reduction, pp. 10–11].” · Show in paper