More Like this

1. Spherical convex hull of random points on a wedge

   https://doi.org/10.1007/s00208-023-02704-9  

   Besau, Florian ; Gusakova, Anna ; Reitzner, Matthias ; Schütt, Carsten ; Thäle, Christoph ; Werner, Elisabeth_M ( August 2023 , Mathematische Annalen)

   Consider two half-spaces$$H_1^+$$$H_1^{+}$and$$H_2^+$$$H_2^{+}$in$${\mathbb {R}}^{d+1}$$$R^{d+1}$whose bounding hyperplanes$$H_1$$$H_1$and$$H_2$$$H_2$are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$$S_{2,+}^d:=S^d\cap H_1^{+}\cap H_2^{+}$is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$$S^d$, which contains a great subsphere of dimension$$d-2$$$d-2$and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$$S_{2,+}^d$and 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$$$S_{2,+}^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
2. Undecidable Translational Tilings with Only Two Tiles, or One Nonabelian Tile

   https://doi.org/10.1007/s00454-022-00426-4  

   Greenfeld, Rachel ; Tao, Terence ( January 2023 , Discrete & Computational Geometry)

   We construct an example of a group$$G = \mathbb {Z}^2 \times G_0$$$G=Z^2\times G_0$for a finite abelian group $$G_0$$$G_0$, a subsetEof $$G_0$$$G_0$, and two finite subsets$$F_1,F_2$$$F_1,F_2$of G, such that it is undecidable in ZFC whether$$\mathbb {Z}^2\times E$$$Z^2\times E$can be tiled by translations of$$F_1,F_2$$$F_1,F_2$. In particular, this implies that this tiling problem isaperiodic, in the sense that (in the standard universe of ZFC) there exist translational tilings ofEby the tiles$$F_1,F_2$$$F_1,F_2$, but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in $$\mathbb {Z}^2$$$Z^2$). A similar construction also applies for$$G=\mathbb {Z}^d$$$G=Z^d$for sufficiently large d. If one allows the group$$G_0$$$G_0$to be non-abelian, a variant of the construction produces an undecidable translational tiling with only one tile F. The argument proceeds by first observing that a single tiling equation is able to encode an arbitrary system of tiling equations, which in turn can encode an arbitrary system of certain functional equations once one has two or more tiles. In particular, one can use two tiles to encode tiling problems for an arbitrary number of tiles.

    

   more » « less
3. Sparse representation of vectors in lattices and semigroups

   https://doi.org/10.1007/s10107-021-01657-8  

   Aliev, Iskander ; Averkov, Gennadiy ; De_Loera, Jesús_A ; Oertel, Timm ( May 2021 , Mathematical Programming)

   We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the$$\ell _0$$${\ell }_0$-norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$${\ell }_0$-norm of solutions to systems$$A\varvec{x}=\varvec{b}$$$Ax=b$, where$$A\in \mathbb {Z}^{m\times n}$$$A\in Z^{m\times n}$,$${\varvec{b}}\in \mathbb {Z}^m$$$b\in Z^m$and$$\varvec{x}$$$x$is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\ell _0$$${\ell }_0$-norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\mathbb {R}$$$R$, to other subdomains such as$$\mathbb {Z}$$$Z$. We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.

    

   more » « less
4. Geometric Representation of Classes of Concave Functions and Duality

   https://doi.org/10.1007/s12220-024-01703-9  

   Ivanov, Grigory ; Werner, Elisabeth_M ( June 2024 , The Journal of Geometric Analysis)

   Using a natural representation of a 1/s-concave function on$${\mathbb {R}}^d$$$R^d$as a convex set in$${\mathbb {R}}^{d+1},$$$R^{d+1},$we derive a simple formula for the integral of itss-polar. This leads to convexity properties of the integral of thes-polar function with respect to the center of polarity. In particular, we prove that the reciprocal of the integral of the polar function of a log-concave function is log-concave as a function of the center of polarity. Also, we define the Santaló regions fors-concave and log-concave functions and generalize the Santaló inequality for them in the case the origin is not the Santaló point.

    

   more » « less
5. The Hanson–Wright inequality for random tensors

   https://doi.org/10.1007/s43670-022-00028-4  

   Bamberger, Stefan ; Krahmer, Felix ; Ward, Rachel ( August 2022 , Sampling Theory, Signal Processing, and Data Analysis)

   We provide moment bounds for expressions of the type$$(X^{(1)} \otimes \cdots \otimes X^{(d)})^T A (X^{(1)} \otimes \cdots \otimes X^{(d)})$$${(X^{\left(1\right)}\otimes \cdots \otimes X^{\left(d\right)})}^{T}A(X^{\left(1\right)}\otimes \cdots \otimes X^{\left(d\right)})$where$$\otimes $$$\otimes$denotes the Kronecker product and$$X^{(1)}, \ldots , X^{(d)}$$$X^{\left(1\right)},\dots ,X^{\left(d\right)}$are random vectors with independent, mean 0, variance 1, subgaussian entries. The bounds are tight up to constants depending ondfor the case of Gaussian random vectors. Our proof also provides a decoupling inequality for expressions of this type. Using these bounds, we obtain new, improved concentration inequalities for expressions of the form$$\Vert B (X^{(1)} \otimes \cdots \otimes X^{(d)})\Vert _2$$$\Vert B(X^{\left(1\right)}\otimes \cdots \otimes X^{\left(d\right)}){\Vert }_2$.

    

   more » « less