More Like this

1. On a Traveling Salesman Problem for Points in the Unit Cube

   https://doi.org/10.1007/s00453-024-01257-w  

   Balogh, József; Clemen, Felix Christian; Dumitrescu, Adrian (September 2024, Algorithmica)

   Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ ${[0,1]}^k$where$$k \ge 2$$ $k\ge 2$. According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$ $x_1,x_2,\dots ,x_n$through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ ${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}\le c_k$, where$$|x-y|$$ $|x-y|$is the Euclidean distance betweenxandy, and$$c_k$$ $c_k$is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$ $x_{n+1}\equiv x_1$. From the other direction, for every$$k \ge 2$$ $k\ge 2$and$$n \ge 2$$ $n\ge 2$, there existnpoints in$$[0,1]^k$$ ${[0,1]}^k$, such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ ${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}=2^{1/k}·\sqrt{k}$. For the plane, the best constant is$$c_2=2$$ $c_2=2$and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ $c_k=9{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$for every$$k \ge 3$$ $k\ge 3$and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ $c_k=2^{1/k}·\sqrt{k}$, for every$$k \ge 2$$ $k\ge 2$. Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ $c_k=3\sqrt{5}{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ $c_k=2.91\sqrt{k}(1+o_k\left(1\right))$. Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ $c_3\ge 2^{7/6}$, which disproves the conjecture for$$k=3$$ $k=3$. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed. 

   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 (March 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. Curvature and sharp growth rates of log-quasimodes on compact manifolds

   https://doi.org/10.1007/s00222-025-01315-2  

   Huang, Xiaoqi; Sogge, Christopher D (March 2025, Inventiones mathematicae)

   Abstract We obtain new optimal estimates for the$$L^{2}(M)\to L^{q}(M)$$ $L^2\left(M\right)\to L^q\left(M\right)$,$$q\in (2,q_{c}]$$ $q\in (2,q_c]$,$$q_{c}=2(n+1)/(n-1)$$ $q_c=2(n+1)/(n-1)$, operator norms of spectral projection operators associated with spectral windows$$[\lambda ,\lambda +\delta (\lambda )]$$ $[\lambda ,\lambda +\delta (\lambda \left)\right]$, with$$\delta (\lambda )=O((\log \lambda )^{-1})$$ $\delta \left(\lambda \right)=O\left({(log\lambda )}^{-1}\right)$on compact Riemannian manifolds$$(M,g)$$ $(M,g)$of dimension$$n\ge 2$$ $n\ge 2$all of whose sectional curvatures are nonpositive or negative. We show that these two different types of estimates are saturated on flat manifolds or manifolds all of whose sectional curvatures are negative. This allows us to classify compact space forms in terms of the size of$$L^{q}$$ $L^q$-norms of quasimodes for each Lebesgue exponent$$q\in (2,q_{c}]$$ $q\in (2,q_c]$, even though it is impossible to distinguish between ones of negative or zero curvature sectional curvature for any$$q>q_{c}$$ $q>q_c$. 

   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 (March 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. Evidence of a liquid–liquid phase transition in H$$_2$$O and D$$_2$$O from path-integral molecular dynamics simulations

   https://doi.org/10.1038/s41598-022-09525-x  

   Eltareb, Ali; Lopez, Gustavo E.; Giovambattista, Nicolas (April 2022, Scientific Reports)

   Abstract We perform path-integral molecular dynamics (PIMD), ring-polymer MD (RPMD), and classical MD simulations of H$$_2$$ ${}_2$O and D$$_2$$ ${}_2$O using the q-TIP4P/F water model over a wide range of temperatures and pressures. The density$$\rho (T)$$ $\rho \left(T\right)$, isothermal compressibility$$\kappa _T(T)$$ ${\kappa }_T\left(T\right)$, and self-diffusion coefficientsD(T) of H$$_2$$ ${}_2$O and D$$_2$$ ${}_2$O are in excellent agreement with available experimental data; the isobaric heat capacity$$C_P(T)$$ $C_P\left(T\right)$obtained from PIMD and MD simulations agree qualitatively well with the experiments. Some of these thermodynamic properties exhibit anomalous maxima upon isobaric cooling, consistent with recent experiments and with the possibility that H$$_2$$ ${}_2$O and D$$_2$$ ${}_2$O exhibit a liquid-liquid critical point (LLCP) at low temperatures and positive pressures. The data from PIMD/MD for H$$_2$$ ${}_2$O and D$$_2$$ ${}_2$O can be fitted remarkably well using the Two-State-Equation-of-State (TSEOS). Using the TSEOS, we estimate that the LLCP for q-TIP4P/F H$$_2$$ ${}_2$O, from PIMD simulations, is located at$$P_c = 167 \pm 9$$ $P_c=167\pm 9$ MPa,$$T_c = 159 \pm 6$$ $T_c=159\pm 6$ K, and$$\rho _c = 1.02 \pm 0.01$$ ${\rho }_c=1.02\pm 0.01$ g/cm$$^3$$ ${}^3$. Isotope substitution effects are important; the LLCP location in q-TIP4P/F D$$_2$$ ${}_2$O is estimated to be$$P_c = 176 \pm 4$$ $P_c=176\pm 4$ MPa,$$T_c = 177 \pm 2$$ $T_c=177\pm 2$ K, and$$\rho _c = 1.13 \pm 0.01$$ ${\rho }_c=1.13\pm 0.01$ g/cm$$^3$$ ${}^3$. Interestingly, for the water model studied, differences in the LLCP location from PIMD and MD simulations suggest that nuclear quantum effects (i.e., atoms delocalization) play an important role in the thermodynamics of water around the LLCP (from the MD simulations of q-TIP4P/F water,$$P_c = 203 \pm 4$$ $P_c=203\pm 4$ MPa,$$T_c = 175 \pm 2$$ $T_c=175\pm 2$ K, and$$\rho _c = 1.03 \pm 0.01$$ ${\rho }_c=1.03\pm 0.01$ g/cm$$^3$$ ${}^3$). Overall, our results strongly support the LLPT scenario to explain water anomalous behavior, independently of the fundamental differences between classical MD and PIMD techniques. The reported values of$$T_c$$ $T_c$for D$$_2$$ ${}_2$O and, particularly, H$$_2$$ ${}_2$O suggest that improved water models are needed for the study of supercooled water. 

   more » « less