More Like this

1. Undecidable Translational Tilings with Only Two Tiles, or One Nonabelian Tile

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

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

   Abstract 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
2. VC-Dimension of Hyperplanes Over Finite Fields

   https://doi.org/10.1007/s00373-025-02909-6  

   Ascoli, Ruben; Betti, Livia; Cheigh, Justin; Iosevich, Alex; Jeong, Ryan; Liu, Xuyan; McDonald, Brian; Milgrim, Wyatt; Miller, Steven J; Romero_Acosta, Francisco; et al (April 2025, Graphs and Combinatorics)

   Abstract Let$$\mathbb {F}_q^d$$ $F_q^d$be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$and a fixed nonzero$$t\in \mathbb {F}_q$$ $t\in F_q$, let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ $H_t\left(E\right)=\{h_y:y\in E\}$, where$$h_y:E\rightarrow \{0,1\}$$ $h_y:E\to \{0,1\}$is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ $\{x\in E:x·y=t\}$. Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ $d=3$that if$$|E|\ge Cq^{\frac{11}{4}}$$ $\left|E\right|\ge C{q}^{\frac{11}{4}}$andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$isdwhenever$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ $\left|E\right|\ge C_d{q}^{d-\frac{1}{d-1}}$. 

   more » « less
3. Hardness and approximation of submodular minimum linear ordering problems

   https://doi.org/10.1007/s10107-023-02038-z  

   Farhadi, Majid; Gupta, Swati; Sun, Shengding; Tetali, Prasad; Wigal, Michael C (December 2023, Mathematical Programming)

   Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ $f(·)$due to an ordering$$\sigma $$ $\sigma$of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ ${min}_{\sigma }{\sum }_{i\in \left[n\right]}f\left(E_{i,\sigma }\right)$, where$$E_{i,\sigma }$$ $E_{i,\sigma }$is the set of items mapped by$$\sigma $$ $\sigma$to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ $(2-\frac{1+{\ell }_f}{1+\left|E\right|})$-approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ${\ell }_f=\frac{f\left(E\right)}{{max}_{x\in E}f\left(\left\{x\right\}\right)}$satisfies$$1 \le \ell _f \le |E|$$ $1\le {\ell }_f\le \left|E\right|$. Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ $(2-\frac{1+r\left(E\right)}{1+\left|E\right|})$-approximation for the matroid MLOP, where$$f = r$$ $f=r$is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ $\frac{4}{3}$-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest. 

   more » « less
4. Abelian varieties of prescribed order over finite fields

   https://doi.org/10.1007/s00208-024-03084-4  

   van_Bommel, Raymond; Costa, Edgar; Li, Wanlin; Poonen, Bjorn; Smith, Alexander (May 2025, Mathematische Annalen)

   Abstract Given a prime powerqand$$n \gg 1$$ $n\gg 1$, we prove that every integer in a large subinterval of the Hasse–Weil interval$$[(\sqrt{q}-1)^{2n},(\sqrt{q}+1)^{2n}]$$ $[{(\sqrt{q}-1)}^{2n},{(\sqrt{q}+1)}^{2n}]$is$$\#A({\mathbb {F}}_q)$$ $\#A\left(F_q\right)$for some ordinary geometrically simple principally polarized abelian varietyAof dimensionnover$${\mathbb {F}}_q$$ $F_q$. As a consequence, we generalize a result of Howe and Kedlaya for$${\mathbb {F}}_2$$ $F_2$to show that for each prime powerq, every sufficiently large positive integer is realizable, i.e.,$$\#A({\mathbb {F}}_q)$$ $\#A\left(F_q\right)$for some abelian varietyAover$${\mathbb {F}}_q$$ $F_q$. Our result also improves upon the best known constructions of sequences of simple abelian varieties with point counts towards the extremes of the Hasse–Weil interval. A separate argument determines, for fixedn, the largest subinterval of the Hasse–Weil interval consisting of realizable integers, asymptotically as$$q \rightarrow \infty $$ $q\to \infty$; this gives an asymptotically optimal improvement of a 1998 theorem of DiPippo and Howe. Our methods are effective: We prove that if$$q \le 5$$ $q\le 5$, then every positive integer is realizable, and for arbitraryq, every positive integer$$\ge q^{3 \sqrt{q} \log q}$$ $\ge q^{3\sqrt{q}logq}$is realizable. 

   more » « less
5. The $$L^p$$-Fisher–Rao metric and Amari–C̆encov $$\alpha $$-Connections

   https://doi.org/10.1007/s00526-024-02660-5  

   Bauer, Martin; Le_Brigant, Alice; Lu, Yuxiu; Maor, Cy (March 2024, Calculus of Variations and Partial Differential Equations)

   Abstract We introduce a family of Finsler metrics, called the$$L^p$$ $L^p$-Fisher–Rao metrics$$F_p$$ $F_p$, for$$p\in (1,\infty )$$ $p\in (1,\infty )$, which generalizes the classical Fisher–Rao metric$$F_2$$ $F_2$, both on the space of densities$${\text {Dens}}_+(M)$$ ${\text{Dens}}_{+}\left(M\right)$and probability densities$${\text {Prob}}(M)$$ $\text{Prob}\left(M\right)$. We then study their relations to the Amari–C̆encov$$\alpha $$ $\alpha$-connections$$\nabla ^{(\alpha )}$$ ${\nabla }^{\left(\alpha \right)}$from information geometry: on$${\text {Dens}}_+(M)$$ ${\text{Dens}}_{+}\left(M\right)$, the geodesic equations of$$F_p$$ $F_p$and$$\nabla ^{(\alpha )}$$ ${\nabla }^{\left(\alpha \right)}$coincide, for$$p = 2/(1-\alpha )$$ $p=2/(1-\alpha )$. Both are pullbacks of canonical constructions on$$L^p(M)$$ $L^p\left(M\right)$, in which geodesics are simply straight lines. In particular, this gives a new variational interpretation of$$\alpha $$ $\alpha$-geodesics as being energy minimizing curves. On$${\text {Prob}}(M)$$ $\text{Prob}\left(M\right)$, the$$F_p$$ $F_p$and$$\nabla ^{(\alpha )}$$ ${\nabla }^{\left(\alpha \right)}$geodesics can still be thought as pullbacks of natural operations on the unit sphere in$$L^p(M)$$ $L^p\left(M\right)$, but in this case they no longer coincide unless$$p=2$$ $p=2$. Using this transformation, we solve the geodesic equation of the$$\alpha $$ $\alpha$-connection by showing that the geodesic are pullbacks of projections of straight lines onto the unit sphere, and they always cease to exists after finite time when they leave the positive part of the sphere. This unveils the geometric structure of solutions to the generalized Proudman–Johnson equations, and generalizes them to higher dimensions. In addition, we calculate the associate tensors of$$F_p$$ $F_p$, and study their relation to$$\nabla ^{(\alpha )}$$ ${\nabla }^{\left(\alpha \right)}$. 

   more » « less