More Like this

1. 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
2. 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
3. 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)

   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
4. Steady Radiating Gravity waves: An Exponential Asymptotics Approach

   https://doi.org/10.1007/s42286-023-00081-z  

   Kataoka, Takeshi; Akylas, T. R. (January 2024, Water Waves)

   Abstract The radiation of steady surface gravity waves by a uniform stream$$U_{0}$$ $U_0$over locally confined (width$$L$$ $L$) smooth topography is analyzed based on potential flow theory. The linear solution to this classical problem is readily found by Fourier transforms, and the nonlinear response has been studied extensively by numerical methods. Here, an asymptotic analysis is made for subcritical flow$$D/\lambda > 1$$ $D/\lambda >1$in the low-Froude-number ($$F^{2} \equiv \lambda /L \ll 1$$ $F^2\equiv \lambda /L\ll 1$) limit, where$$\lambda = U_{0}^{2} /g$$ $\lambda =U_0^2/g$is the lengthscale of radiating gravity waves and$$D$$ $D$is the uniform water depth. In this regime, the downstream wave amplitude, although formally exponentially small with respect to$$F$$ $F$, is determined by a fully nonlinear mechanism even for small topography amplitude. It is argued that this mechanism controls the wave response for a broad range of flow conditions, in contrast to linear theory which has very limited validity. 

   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