An official website of the United States government
Abstract Let$$\mathbb {F}_q^d$$ be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ and a fixed nonzero$$t\in \mathbb {F}_q$$ , let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ , where$$h_y:E\rightarrow \{0,1\}$$ is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ . Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ that if$$|E|\ge Cq^{\frac{11}{4}}$$ andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ isdwhenever$$E\subseteq \mathbb {F}_q^d$$ with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ .
more »
« less
Undecidable Translational Tilings with Only Two Tiles, or One Nonabelian Tile
Abstract We construct an example of a group$$G = \mathbb {Z}^2 \times G_0$$ for a finite abelian group $$G_0$$ , a subsetEof $$G_0$$ , and two finite subsets$$F_1,F_2$$ of G, such that it is undecidable in ZFC whether$$\mathbb {Z}^2\times E$$ can be tiled by translations of$$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$$ , 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$$ ). A similar construction also applies for$$G=\mathbb {Z}^d$$ for sufficiently large d. If one allows the group$$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
- Award ID(s):
- 1764034
- PAR ID:
- 10389611
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Discrete & Computational Geometry
- Volume:
- 70
- Issue:
- 4
- ISSN:
- 0179-5376
- Format(s):
- Medium: X Size: p. 1652-1706
- Size(s):
- p. 1652-1706
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The amplituhedron is a mathematical object which was introduced to provide a geometric origin of scattering amplitudes in$$\mathcal {N}=4$$ super Yang–Mills theory. It generalizescyclic polytopesand thepositive Grassmannianand has a very rich combinatorics with connections to cluster algebras. In this article, we provide a series of results about tiles and tilings of the$$m=4$$ amplituhedron. Firstly, we provide a full characterization of facets of BCFW tiles in terms of cluster variables for$$\text{ Gr}_{4,n}$$ . Secondly, we exhibit a tiling of the$$m=4$$ amplituhedron which involves a tile which does not come from the BCFW recurrence—thespuriontile, which also satisfies all cluster properties. Finally, strengthening the connection with cluster algebras, we show that each standard BCFW tile is the positive part of a cluster variety, which allows us to compute the canonical form of each such tile explicitly in terms of cluster variables for$$\text{ Gr}_{4,n}$$ . This paper is a companion to our previous paper “Cluster algebras and tilings for the$$m=4$$ amplituhedron.”more » « less
-
Abstract Fix an integer$$d\ge 2$$ . The parameters$$c_0\in \overline{\mathbb {Q}}$$ for which the unicritical polynomial$$f_{d,c}(z)=z^d+c\in \mathbb {C}[z]$$ has finite postcritical orbit, also known asMisiurewiczparameters, play a significant role in complex dynamics. Recent work of Buff, Epstein, and Koch proved the first known cases of a long-standing dynamical conjecture of Milnor using their arithmetic properties, about which relatively little is otherwise known. Continuing our work from a companion paper, we address further arithmetic properties of Misiurewicz parameters, especially the nature of the algebraic integers obtained by evaluating the polynomial defining one such parameter at a different Misiurewicz parameter. In the most challenging such combinations, we describe a connection between such algebraic integers and the multipliers of associated periodic points. As part of our considerations, we also introduce a new class of polynomials we callp-special, which may be of independent number theoretic interest.more » « less
-
Abstract Consider two half-spaces$$H_1^+$$ and$$H_2^+$$ in$${\mathbb {R}}^{d+1}$$ whose bounding hyperplanes$$H_1$$ and$$H_2$$ are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$ is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$ , which contains a great subsphere of dimension$$d-2$$ and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {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$$ . A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {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
-
Abstract We perform path-integral molecular dynamics (PIMD), ring-polymer MD (RPMD), and classical MD simulations of H$$_2$$ O and D$$_2$$ O using the q-TIP4P/F water model over a wide range of temperatures and pressures. The density$$\rho (T)$$ , isothermal compressibility$$\kappa _T(T)$$ , and self-diffusion coefficientsD(T) of H$$_2$$ O and D$$_2$$ O are in excellent agreement with available experimental data; the isobaric heat capacity$$C_P(T)$$ 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$$ O and D$$_2$$ O exhibit a liquid-liquid critical point (LLCP) at low temperatures and positive pressures. The data from PIMD/MD for H$$_2$$ O and D$$_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$$ O, from PIMD simulations, is located at$$P_c = 167 \pm 9$$ MPa,$$T_c = 159 \pm 6$$ K, and$$\rho _c = 1.02 \pm 0.01$$ g/cm$$^3$$ . Isotope substitution effects are important; the LLCP location in q-TIP4P/F D$$_2$$ O is estimated to be$$P_c = 176 \pm 4$$ MPa,$$T_c = 177 \pm 2$$ K, and$$\rho _c = 1.13 \pm 0.01$$ g/cm$$^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$$ MPa,$$T_c = 175 \pm 2$$ K, and$$\rho _c = 1.03 \pm 0.01$$ g/cm$$^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$$ for D$$_2$$ O and, particularly, H$$_2$$ O suggest that improved water models are needed for the study of supercooled water.more » « less
