An official website of the United States government
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
A TOPOLOGICAL APPROACH TO UNDEFINABILITY IN ALGEBRAIC EXTENSIONS OF Q
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
- PAR ID:
- 10502706
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- The Bulletin of Symbolic Logic
- Volume:
- 29
- Issue:
- 4
- ISSN:
- 1079-8986
- Page Range / eLocation ID:
- 626 to 655
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract LetKbe an imaginary quadratic field and$$p\geq 5$$a rational prime inert inK. For a$$\mathbb {Q}$$-curveEwith complex multiplication by$$\mathcal {O}_K$$and good reduction atp, K. Rubin introduced ap-adicL-function$$\mathscr {L}_{E}$$which interpolates special values ofL-functions ofEtwisted by anticyclotomic characters ofK. In this paper, we prove a formula which links certain values of$$\mathscr {L}_{E}$$outside its defining range of interpolation with rational points onE. Arithmetic consequences includep-converse to the Gross–Zagier and Kolyvagin theorem forE. A key tool of the proof is the recent resolution of Rubin’s conjecture on the structure of local units in the anticyclotomic$${\mathbb {Z}}_p$$-extension$$\Psi _\infty $$of the unramified quadratic extension of$${\mathbb {Q}}_p$$. Along the way, we present a theory of local points over$$\Psi _\infty $$of the Lubin–Tate formal group of height$$2$$for the uniformizing parameter$$-p$$.more » « less
-
Abstract We prove that the rational cohomology group$$H^{11}(\overline {\mathcal {M}}_{g,n})$$vanishes unless$$g = 1$$and$$n \geq 11$$. We show furthermore that$$H^k(\overline {\mathcal {M}}_{g,n})$$is pure Hodge–Tate for all even$$k \leq 12$$and deduce that$$\# \overline {\mathcal {M}}_{g,n}(\mathbb {F}_q)$$is surprisingly well approximated by a polynomial inq. In addition, we use$$H^{11}(\overline {\mathcal {M}}_{1,11})$$and its image under Gysin push-forward for tautological maps to produce many new examples of moduli spaces of stable curves with nonvanishing odd cohomology and nontautological algebraic cycle classes in Chow cohomology.more » « less
-
Abstract Let$$P_1, \ldots , P_m \in \mathbb {K}[\mathrm {y}]$$be polynomials with distinct degrees, no constant terms and coefficients in a general local field$$\mathbb {K}$$. We give a quantitative count of the number of polynomial progressions$$x, x+P_1(y), \ldots , x + P_m(y)$$lying in a set$$S\subseteq \mathbb {K}$$of positive density. The proof relies on a general$$L^{\infty }$$inverse theorem which is of independent interest. This inverse theorem implies a Sobolev improving estimate for multilinear polynomial averaging operators which in turn implies our quantitative estimate for polynomial progressions. This general Sobolev inequality has the potential to be applied in a number of problems in real, complex andp-adic analysis.more » « less
-
Abstract Let$$\mathrm {R}$$be a real closed field. Given a closed and bounded semialgebraic set$$A \subset \mathrm {R}^n$$and semialgebraic continuous functions$$f,g:A \rightarrow \mathrm {R}$$such that$$f^{-1}(0) \subset g^{-1}(0)$$, there exist an integer$$N> 0$$and$$c \in \mathrm {R}$$such that the inequality (Łojasiewicz inequality)$$|g(x)|^N \le c \cdot |f(x)|$$holds for all$$x \in A$$. In this paper, we consider the case whenAis defined by a quantifier-free formula with atoms of the form$$P = 0, P>0, P \in \mathcal {P}$$for some finite subset of polynomials$$\mathcal {P} \subset \mathrm {R}[X_1,\ldots ,X_n]_{\leq d}$$, and the graphs of$$f,g$$are also defined by quantifier-free formulas with atoms of the form$$Q = 0, Q>0, Q \in \mathcal {Q}$$, for some finite set$$\mathcal {Q} \subset \mathrm {R}[X_1,\ldots ,X_n,Y]_{\leq d}$$. We prove that the Łojasiewicz exponent in this case is bounded by$$(8 d)^{2(n+7)}$$. Our bound depends ondandnbut is independent of the combinatorial parameters, namely the cardinalities of$$\mathcal {P}$$and$$\mathcal {Q}$$. The previous best-known upper bound in this generality appeared inP. Solernó, Effective Łojasiewicz Inequalities in Semi-Algebraic Geometry, Applicable Algebra in Engineering, Communication and Computing (1991)and depended on the sum of degrees of the polynomials defining$$A,f,g$$and thus implicitly on the cardinalities of$$\mathcal {P}$$and$$\mathcal {Q}$$. As a consequence, we improve the current best error bounds for polynomial systems under some conditions. Finally, we prove a version of Łojasiewicz inequality in polynomially bounded o-minimal structures. We prove the existence of a common upper bound on the Łojasiewicz exponent for certain combinatorially defined infinite (but not necessarily definable) families of pairs of functions. This improves a prior result of Chris Miller (C. Miller, Expansions of the real field with power functions, Ann. Pure Appl. Logic (1994)).more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/bsl.2023.37
