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

Translative covering densities of order n log n

There are absolute constants c>0c > 0 and n0n_0 such that, for every integer n≥n0n \ge n_0, some centrally symmetric convex body Kn⊂RnK_n \subset \mathbb{R}^n satisfies θT(Kn)>cnlog⁡n\theta_T(K_n) > c n \log n.

As n→∞n \to \infty, each of the four quantities sup⁡K∈KnθT(K)\sup_{K \in \mathcal{K}^n} \theta_T(K), sup⁡K∈KsymnθT(K)\sup_{K \in \mathcal{K}_{\text{sym}}^n} \theta_T(K), sup⁡K∈KnθL(K)\sup_{K \in \mathcal{K}^n} \theta_L(K), and sup⁡K∈KsymnθL(K)\sup_{K \in \mathcal{K}_{\text{sym}}^n} \theta_L(K) has order nlog⁡nn \log n, with absolute comparison constants.

With the same cc and n0n_0 as in Theorem 1.1, for every n≥n0n \ge n_0 there is a centrally symmetric polytope Pn⊂RnP_n \subset \mathbb{R}^n with rational vertices such that θT(Pn)>cnlog⁡n\theta_T(P_n) > c n \log n.

The bodies in Theorem 1.1 can be chosen in the form K=bB∩⋂j=1m{x:∣uj⋅x∣≤1}K = bB \cap \bigcap_{j=1}^m \{x : |u_j \cdot x| \le 1\}, uj∈Qn∩Sn−1u_j \in \mathbb{Q}^n \cap S^{n-1}, with m<∞m < \infty.

The random body KK in (2.5) satisfies P{∣K∣>2vωnan}≥exp⁡(−1)−2v3−2v>0\mathbb{P}\{|K| > 2v \omega_n a^n\} \ge \frac{\exp(-1) - 2v}{3 - 2v} > 0.

For all sufficiently large nn and uniformly for 1≤R≤n21 \le R \le n^2, the deterministic finite family Fn\mathcal{F}_n satisfies Nn≤nC1exp⁡(λ0n)N_n \le n^{C_1} \exp(\lambda_0 n) and log⁡∣Fn∣≤exp⁡(λ0n+O(log⁡n))\log |\mathcal{F}_n| \le \exp(\lambda_0 n + O(\log n)), and if K+Λ+T=RnK + \Lambda + T = \mathbb{R}^n with ∣T∣/det⁡Λ≤ρ0|T|/\det\Lambda \le \rho_0, there is a list P∈FnP \in \mathcal{F}_n such that BD⊆⋃j=1m(pj+K+)B_D \subseteq \bigcup_{j=1}^m (p_j + K^+).

There are constants c0,Ctail>0c_0, C_{\text{tail}} > 0 and n0n_0 such that, whenever n≥n0n \ge n_0 and 1≤R≤c0nlog⁡n1 \le R \le c_0 n \log n, every retained pattern P∈FnP \in \mathcal{F}_n satisfies P(BD⊆⋃p∈P(p+K+))≤exp⁡[−exp⁡(γn−Ctaillog⁡n)]\mathbb{P}(B_D \subseteq \bigcup_{p \in P} (p + K^+)) \le \exp[-\exp(\gamma n - C_{\text{tail}} \log n)].

For every convex body K⊂RnK \subset \mathbb{R}^n, θT(K)=θper(K)\theta_T(K) = \theta_{\text{per}}(K).

Methods

Constructing a random centrally symmetric convex body by intersecting a slightly enlarged Euclidean ball with symmetric slabs whose unit normals are sampled from a Poisson point process on the unit sphere.

Source excerpts

“and let Π be a Poisson process on Sn−1S^{n−1} with intensity µ. Equivalently, sample a Poisson random integer of mean M, then that many independent σ-distributed unit normals. Define K = bB ∩ ⋂_{u∈Π} {x : |u · x| ≤ 1}, K+ = (b + 3η)B ∩ ⋂_{u∈Π} {x : |u · x| ≤ 1 + 3η}.” · Show in paper

Deterministic localization and rounding of arbitrary periodic coverings by averaging over a fundamental domain and rounding centers in a translated window to a finite grid.

Source excerpts

“Translate this window and the retained centers by −z, and round every center coordinatewise to the nearest point of hnZ^n, using a fixed rule for ties.” · Show in paper

Grouping spherical cap conditions into blocks with controlled common intersections and mutual overlaps, combined with a continuous indexed Janson lower-tail inequality for Poisson processes on measurable slots.

Source excerpts

“We next group the cap conditions into blocks and choose a measurable set inside each common intersection. A point in this set meets every cap condition in its block.” · Show in paper

“Proposition 6.2 (Poisson lower tail). Let Π be a Poisson process on a finite nonatomic standard Borel measure space. For each member of a finite nonempty family, take a finite nonempty labeled list of measurable slots of positive intensity.” · Show in paper

Two-scale angular target selection using cylinder volume estimates to ensure fine projective separation for all target pairs and coarse separation for all but an exponentially small fraction of pairs.

Source excerpts

“Lemma 7.1 (Cylinder estimate). Let n ≥ 2, let D, L > 0, and let G ⊂ BD be measurable with |G| ≥ ωnD^n/4.” · Show in paper

“(i) no pair with distinct indices is H sqrt(log n/n)-bad; (ii) at most a fraction 10fn of the unordered pairs with distinct indices is 4 sqrt(ε)-bad” · Show in paper