An official website of the United States government
Abstract For any subset$$Z \subseteq {\mathbb {Q}}$$, consider the set$$S_Z$$of subfields$$L\subseteq {\overline {\mathbb {Q}}}$$which contain a co-infinite subset$$C \subseteq L$$that is universally definable inLsuch that$$C \cap {\mathbb {Q}}=Z$$. Placing a natural topology on the set$${\operatorname {Sub}({\overline {\mathbb {Q}}})}$$of subfields of$${\overline {\mathbb {Q}}}$$, we show that ifZis not thin in$${\mathbb {Q}}$$, then$$S_Z$$is meager in$${\operatorname {Sub}({\overline {\mathbb {Q}}})}$$. Here,thinandmeagerboth mean “small”, in terms of arithmetic geometry and topology, respectively. For example, this implies that only a meager set of fieldsLhave the property that the ring of algebraic integers$$\mathcal {O}_L$$is universally definable inL. The main tools are Hilbert’s Irreducibility Theorem and a new normal form theorem for existential definitions. The normal form theorem, which may be of independent interest, says roughly that every$$\exists $$-definable subset of an algebraic extension of$${\mathbb Q}$$is a finite union of single points and projections of hypersurfaces defined by absolutely irreducible polynomials.
more »
« less
This content will become publicly available on May 1, 2026
Intersective sets for sparse sets of integers
Abstract For$$E \subset \mathbb {N}$$, a subset$$R \subset \mathbb {N}$$isE-intersectiveif for every$$A \subset E$$having positive relative density,$$R \cap (A - A) \neq \varnothing $$. We say thatRischromatically E-intersectiveif for every finite partition$$E=\bigcup _{i=1}^k E_i$$, there existsisuch that$$R\cap (E_i-E_i)\neq \varnothing $$. When$$E=\mathbb {N}$$, we recover the usual notions of intersectivity and chromatic intersectivity. We investigate to what extent the known intersectivity results hold in the relative setting when$$E = \mathbb {P}$$, the set of primes, or other sparse subsets of$$\mathbb {N}$$. Among other things, we prove the following: (1) the set of shifted Chen primes$$\mathbb {P}_{\mathrm {Chen}} + 1$$is both intersective and$$\mathbb {P}$$-intersective; (2) there exists an intersective set that is not$$\mathbb {P}$$-intersective; (3) every$$\mathbb {P}$$-intersective set is intersective; (4) there exists a chromatically$$\mathbb {P}$$-intersective set which is not intersective (and therefore not$$\mathbb {P}$$-intersective).
more »
« less
- Award ID(s):
- 2246921
- PAR ID:
- 10600430
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Ergodic Theory and Dynamical Systems
- Volume:
- 45
- Issue:
- 5
- ISSN:
- 0143-3857
- Page Range / eLocation ID:
- 1370 to 1402
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract A result of Gyárfás [12] exactly determines the size of a largest monochromatic component in an arbitrary$$r$$-colouring of the complete$$k$$-uniform hypergraph$$K_n^k$$when$$k\geq 2$$and$$k\in \{r-1,r\}$$. We prove a result which says that if one replaces$$K_n^k$$in Gyárfás’ theorem by any ‘expansive’$$k$$-uniform hypergraph on$$n$$vertices (that is, a$$k$$-uniform hypergraph$$G$$on$$n$$vertices in which$$e(V_1, \ldots, V_k)\gt 0$$for all disjoint sets$$V_1, \ldots, V_k\subseteq V(G)$$with$$|V_i|\gt \alpha$$for all$$i\in [k]$$), then one gets a largest monochromatic component of essentially the same size (within a small error term depending on$$r$$and$$\alpha$$). As corollaries we recover a number of known results about large monochromatic components in random hypergraphs and random Steiner triple systems, often with drastically improved bounds on the error terms. Gyárfás’ result is equivalent to the dual problem of determining the smallest possible maximum degree of an arbitrary$$r$$-partite$$r$$-uniform hypergraph$$H$$with$$n$$edges in which every set of$$k$$edges has a common intersection. In this language, our result says that if one replaces the condition that every set of$$k$$edges has a common intersection with the condition that for every collection of$$k$$disjoint sets$$E_1, \ldots, E_k\subseteq E(H)$$with$$|E_i|\gt \alpha$$, there exists$$(e_1, \ldots, e_k)\in E_1\times \cdots \times E_k$$such that$$e_1\cap \cdots \cap e_k\neq \emptyset$$, then the smallest possible maximum degree of$$H$$is essentially the same (within a small error term depending on$$r$$and$$\alpha$$). We prove our results in this dual setting.more » « less
-
Abstract Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set$$S \subset \mathbb {R}^k$$by a first-order quantifier-free formula in the language of the reals, the goal is to output a simplicial complex$$\Delta $$, whose geometric realization,$$|\Delta |$$, is semialgebraically homeomorphic toS. In this paper, we consider a weaker version of this question. We prove that for any$$\ell \geq 0$$, there exists an algorithm which takes as input a description of a semialgebraic subset$$S \subset \mathbb {R}^k$$given by a quantifier-free first-order formula$$\phi $$in the language of the reals and produces as output a simplicial complex$$\Delta $$, whose geometric realization,$$|\Delta |$$is$$\ell $$-equivalent toS. The complexity of our algorithm is bounded by$$(sd)^{k^{O(\ell )}}$$, wheresis the number of polynomials appearing in the formula$$\phi $$, andda bound on their degrees. For fixed$$\ell $$, this bound issingly exponentialink. In particular, since$$\ell $$-equivalence implies that thehomotopy groupsup to dimension$$\ell $$of$$|\Delta |$$are isomorphic to those ofS, we obtain a reduction (having singly exponential complexity) of the problem of computing the first$$\ell $$homotopy groups ofSto the combinatorial problem of computing the first$$\ell $$homotopy groups of a finite simplicial complex of size bounded by$$(sd)^{k^{O(\ell )}}$$.more » « less
-
Abstract We prove three results concerning the existence of Bohr sets in threefold sumsets. More precisely, lettingGbe a countable discrete abelian group and$$\phi _1, \phi _2, \phi _3: G \to G$$be commuting endomorphisms whose images have finite indices, we show that(1)If$$A \subset G$$has positive upper Banach density and$$\phi _1 + \phi _2 + \phi _3 = 0$$, then$$\phi _1(A) + \phi _2(A) + \phi _3(A)$$contains a Bohr set. This generalizes a theorem of Bergelson and Ruzsa in$$\mathbb {Z}$$and a recent result of the first author.(2)For any partition$$G = \bigcup _{i=1}^r A_i$$, there exists an$$i \in \{1, \ldots , r\}$$such that$$\phi _1(A_i) + \phi _2(A_i) - \phi _2(A_i)$$contains a Bohr set. This generalizes a result of the second and third authors from$$\mathbb {Z}$$to countable abelian groups.(3)If$$B, C \subset G$$have positive upper Banach density and$$G = \bigcup _{i=1}^r A_i$$is a partition,$$B + C + A_i$$contains a Bohr set for some$$i \in \{1, \ldots , r\}$$. This is a strengthening of a theorem of Bergelson, Furstenberg and Weiss. All results are quantitative in the sense that the radius and rank of the Bohr set obtained depends only on the indices$$[G:\phi _j(G)]$$, the upper Banach density ofA(in (1)), or the number of sets in the given partition (in (2) and (3)).more » « less
-
Abstract Define theCollatz map$${\operatorname {Col}} \colon \mathbb {N}+1 \to \mathbb {N}+1$$on the positive integers$$\mathbb {N}+1 = \{1,2,3,\dots \}$$by setting$${\operatorname {Col}}(N)$$equal to$$3N+1$$whenNis odd and$$N/2$$whenNis even, and let$${\operatorname {Col}}_{\min }(N) := \inf _{n \in \mathbb {N}} {\operatorname {Col}}^n(N)$$denote the minimal element of the Collatz orbit$$N, {\operatorname {Col}}(N), {\operatorname {Col}}^2(N), \dots $$. The infamousCollatz conjectureasserts that$${\operatorname {Col}}_{\min }(N)=1$$for all$$N \in \mathbb {N}+1$$. Previously, it was shown by Korec that for any$$\theta> \frac {\log 3}{\log 4} \approx 0.7924$$, one has$${\operatorname {Col}}_{\min }(N) \leq N^\theta $$for almost all$$N \in \mathbb {N}+1$$(in the sense of natural density). In this paper, we show that foranyfunction$$f \colon \mathbb {N}+1 \to \mathbb {R}$$with$$\lim _{N \to \infty } f(N)=+\infty $$, one has$${\operatorname {Col}}_{\min }(N) \leq f(N)$$for almost all$$N \in \mathbb {N}+1$$(in the sense of logarithmic density). Our proof proceeds by establishing a stabilisation property for a certain first passage random variable associated with the Collatz iteration (or more precisely, the closely related Syracuse iteration), which in turn follows from estimation of the characteristic function of a certain skew random walk on a$$3$$-adic cyclic group$$\mathbb {Z}/3^n\mathbb {Z}$$at high frequencies. This estimation is achieved by studying how a certain two-dimensional renewal process interacts with a union of triangles associated to a given frequency.more » « less
