skip to main content


The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Thursday, May 23 until 2:00 AM ET on Friday, May 24 due to maintenance. We apologize for the inconvenience.

Title: Spherical convex hull of random points on a wedge

Consider two half-spaces$$H_1^+$$H1+and$$H_2^+$$H2+in$${\mathbb {R}}^{d+1}$$Rd+1whose bounding hyperplanes$$H_1$$H1and$$H_2$$H2are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$S2,+d:=SdH1+H2+is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$Sd, which contains a great subsphere of dimension$$d-2$$d-2and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$S2,+dand consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$$\log n$$logn. A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {S}}_{2,+}^d$$S2,+d. The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a half-sphere.

more » « less
Author(s) / Creator(s):
; ; ; ; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Mathematische Annalen
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Approximate integer programming is the following: For a given convex body$$K \subseteq {\mathbb {R}}^n$$KRn, either determine whether$$K \cap {\mathbb {Z}}^n$$KZnis empty, or find an integer point in the convex body$$2\cdot (K - c) +c$$2·(K-c)+cwhich isK, scaled by 2 from its center of gravityc. Approximate integer programming can be solved in time$$2^{O(n)}$$2O(n)while the fastest known methods for exact integer programming run in time$$2^{O(n)} \cdot n^n$$2O(n)·nn. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$x^* \in (K \cap {\mathbb {Z}}^n)$$x(KZn)can be found in time$$2^{O(n)}$$2O(n), provided that theremaindersof each component$$x_i^* \mod \ell $$ximodfor some arbitrarily fixed$$\ell \ge 5(n+1)$$5(n+1)of$$x^*$$xare given. The algorithm is based on acutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a$$2^{O(n)}n^n$$2O(n)nnalgorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a newasymmetric approximate Carathéodory theoremthat might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$Ax=b,0xu,xZn. Such a problem can be reduced to the solution of$$\prod _i O(\log u_i +1)$$iO(logui+1)approximate integer programming problems. This implies, for example thatknapsackorsubset-sumproblems withpolynomial variable range$$0 \le x_i \le p(n)$$0xip(n)can be solved in time$$(\log n)^{O(n)}$$(logn)O(n). For these problems, the best running time so far was$$n^n \cdot 2^{O(n)}$$nn·2O(n).

    more » « less
  2. Abstract

    The repeating fast radio burst FRB 20190520B is localized to a galaxy atz= 0.241, much closer than expected given its dispersion measure DM = 1205 ± 4 pc cm−3. Here we assess implications of the large DM and scattering observed from FRB 20190520B for the host galaxy’s plasma properties. A sample of 75 bursts detected with the Five-hundred-meter Aperture Spherical radio Telescope shows scattering on two scales: a mean temporal delayτ(1.41 GHz) = 10.9 ± 1.5 ms, which is attributed to the host galaxy, and a mean scintillation bandwidth Δνd(1.41 GHz) = 0.21 ± 0.01 MHz, which is attributed to the Milky Way. Balmer line measurements for the host imply an Hαemission measure (galaxy frame) EMs= 620 pc cm−6× (T/104K)0.9, implying DMHαof order the value inferred from the FRB DM budget,DMh=1121138+89pc cm−3for plasma temperatures greater than the typical value 104K. Combiningτand DMhyields a nominal constraint on the scattering amplification from the host galaxyF˜G=1.50.3+0.8(pc2km)1/3, whereF˜describes turbulent density fluctuations andGrepresents the geometric leverage to scattering that depends on the location of the scattering material. For a two-screen scattering geometry whereτarises from the host galaxy and Δνdfrom the Milky Way, the implied distance between the FRB source and dominant scattering material is ≲100 pc. The host galaxy scattering and DM contributions support a novel technique for estimating FRB redshifts using theτ–DM relation, and are consistent with previous findings that scattering of localized FRBs is largely dominated by plasma within host galaxies and the Milky Way.

    more » « less
  3. Abstract

    A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$(a1,a2,,an)whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$b1b2bnsatisfies$$b_i \le i$$bii. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$Rn, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$x-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$x=(a,b,,b), which we refer to as$${\textbf{x}}$$x-parking function polytopes. We explore connections between these$${\textbf{x}}$$x-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$x-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary.

    more » « less
  4. Abstract

    Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$aj,1x1++aj,kxk=0for$$j=1,\dots ,m$$j=1,,mwith coefficients$$a_{j,i}\in \mathbb {F}_p$$aj,iFp. Suppose that$$k\ge 3m$$k3m, that$$a_{j,1}+\dots +a_{j,k}=0$$aj,1++aj,k=0for$$j=1,\dots ,m$$j=1,,mand that every$$m\times m$$m×mminor of the$$m\times k$$m×kmatrix$$(a_{j,i})_{j,i}$$(aj,i)j,iis non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$AFpnof size$$|A|> C\cdot \Gamma ^n$$|A|>C·Γncontains a solution$$(x_1,\dots ,x_k)\in A^k$$(x1,,xk)Akto the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$x1,,xkAare all distinct. Here,Cand$$\Gamma $$Γare constants only depending onp,mandksuch that$$\Gamma Γ<p. The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$x1,,xkin the solution$$(x_1,\dots ,x_k)\in A^k$$(x1,,xk)Akto be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$x1,,xkare not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments.

    more » « less
  5. Abstract

    We present a Keck/MOSFIRE rest-optical composite spectrum of 16 typical gravitationally lensed star-forming dwarf galaxies at 1.7 ≲z≲ 2.6 (zmean= 2.30), all chosen independent of emission-line strength. These galaxies have a median stellar mass oflog(M*/M)med=8.290.43+0.51and a median star formation rate ofSFRHαmed=2.251.26+2.15Myr1. We measure the faint electron-temperature-sensitive [Oiii]λ4363 emission line at 2.5σ(4.1σ) significance when considering a bootstrapped (statistical-only) uncertainty spectrum. This yields a direct-method oxygen abundance of12+log(O/H)direct=7.880.22+0.25(0.150.06+0.12Z). We investigate the applicability at highzof locally calibrated oxygen-based strong-line metallicity relations, finding that the local reference calibrations of Bian et al. best reproduce (≲0.12 dex) our composite metallicity at fixed strong-line ratio. At fixedM*, our composite is well represented by thez∼ 2.3 direct-method stellar mass—gas-phase metallicity relation (MZR) of Sanders et al. When comparing to predicted MZRs from the IllustrisTNG and FIRE simulations, having recalculated our stellar masses with more realistic nonparametric star formation histories(log(M*/M)med=8.920.22+0.31), we find excellent agreement with the FIRE MZR. Our composite is consistent with no metallicity evolution, at fixedM*and SFR, of the locally defined fundamental metallicity relation. We measure the doublet ratio [Oii]λ3729/[Oii]λ3726 = 1.56 ± 0.32 (1.51 ± 0.12) and a corresponding electron density ofne=10+215cm3(ne=10+74cm3) when considering the bootstrapped (statistical-only) error spectrum. This result suggests that lower-mass galaxies have lower densities than higher-mass galaxies atz∼ 2.

    more » « less