betaFeedback

WorksComputer Science

Up or down at every integer: Collatz-type maps of arbitrary sets and the up-down graph

Abstract

For a set SS of positive integers let TST_S send xx to ⌈3x/2⌉\lceil 3x/2\rceil if x∈Sx\in S and to ⌈x/2⌉\lceil x/2\rceil otherwise. The odd numbers give the Collatz map, the even numbers give it again after a shift by one, and S=NS=\mathbb{N} gives Mahler's map x↦⌈3x/2⌉x\mapsto\lceil 3x/2\rceil. All these maps are subgraphs of the up-down graph GG, in which every xx has the edges x→⌈x/2⌉x\to\lceil x/2\rceil and x→⌈3x/2⌉x\to\lceil 3x/2\rceil, and so are the families of maps in which the direction is forced at some numbers and free at the others. The cycles of the maps are the simple cycles of the subgraph, their divergent orbits are its rays, and all maps of a family are bounded exactly when the subgraph has no ray. We classify the simplest sets and show that density says little: some sets of density one send every orbit to 1, and some periodic sets of arbitrarily small density have increasing orbits. Every positive integer is the least element of a cycle of some map. The critical proportion of steps up is log⁡32\log_3 2: cycles stay below it, divergent orbits stay above it, and both come arbitrarily close. For sets periodic modulo a power of 2, an effective up-frequency from a finite Markov chain takes the place of the density, and a finite computation can prove that every orbit reaches a cycle. Mahler's Z-number problem is implied by a question about one such map. Finally, we ask how far the Collatz map is from maps whose behaviour can be proved. Finite changes never help. Adding fewer than log⁡3/2N+1\log_{3/2}N+1 even numbers below NN makes an orbit increase, while removing the odd numbers congruent to 9 or 15 modulo 16, an eighth of all integers, gives a map all of whose orbits provably reach the cycle (1,2); removing 22 residue classes modulo 512, a proportion 0.043, also suffices.

2020 Mathematics Subject Classification: Primary 11B83; Secondary 05C20, 11J71, 11Y55, 60J10.

Introduction

Up or down at every integer

The Collatz map

T(x)={(3x+1)/2,x odd,x/2,x even,T(x) = \begin{cases} (3x + 1)/2, & x\ \text{odd},\\ x/2, & x\ \text{even}, \end{cases}

changes a positive integer by about half of its value at every step: odd numbers go up and even numbers go down. The Collatz conjecture states that every orbit reaches the cycle (1,2)(1,2); see the surveys and bibliographies of Lagarias [9, 12, 10, 11]. In [24] we kept the size of the steps and let the 2-adic valuation of the current number decide their direction. Here the direction is decided at every integer separately, by an arbitrary set. Let N={1,2,3,…}\mathbb{N} = \{1,2,3,\ldots\}.

Definition 1.1. For x∈Nx \in\mathbb{N} let U(x)=⌈3x/2⌉U(x)=\lceil3x/2\rceil and D(x)=⌈x/2⌉D(x)=\lceil x/2\rceil, and for S⊆NS\subseteq\mathbb{N} let TS:N→NT_S:\mathbb{N}\to\mathbb{N} be

TS(x)={U(x),x∈S,D(x),x∉S.(1)T_S(x)= \begin{cases} U(x), & x\in S,\\ D(x), & x\notin S. \end{cases} \tag*{(1)}

So U(x)=(3x+1)/2U(x)=(3x+1)/2 and D(x)=(x+1)/2D(x)=(x+1)/2 for odd xx, and U(x)=3x/2U(x)=3x/2 and D(x)=x/2D(x)=x/2 for even xx. A step up adds ⌊x/2⌋\lfloor x/2\rfloor to xx, a step down subtracts ⌊x/2⌋\lfloor x/2\rfloor, and a step down at an even number halves it only once, rather than removing all factors 2 at once. These are exactly the two steps of the Collatz map, together with the step x↦(x+1)/2x\mapsto(x+1)/2 at odd numbers that was used by the maps TST_S of [24]. Since U(x)>xU(x)>x for all xx and D(x)<xD(x)<x for all x≥2x\ge2, while D(1)=1D(1)=1, an orbit of TST_S goes up exactly at the elements of SS that it visits.

Remark 1.2 (Notation). We keep the letter TT, which is customary for the Collatz map: with our notation the Collatz map TT is T2N−1T_{2\mathbb{N}-1}. Readers of [24] should note that the symbol TST_S is used differently there: in [24] the set SS is a set of exponents of 2, the direction of a step depends on the exponent of 2 in the current number, and a step down at an even number removes all factors 2 at once. In this paper SS is a set of numbers, the direction depends only on whether the current number lies in SS, and every step divides by 2 once. Only four maps belong to both families: TNT_{\mathbb{N}}, TN−T_{\mathbb{N}}^{-}, T[2,∞)T_{[2,\infty)} and T[2,∞)−T_{[2,\infty)}^{-} of [24] are the maps TNT_{\mathbb{N}}, T2NT_{2\mathbb{N}}, TN∖(4N−2)T_{\mathbb{N}\setminus(4\mathbb{N}-2)} and T4NT_{4\mathbb{N}} here.

The family runs from T∅=DT_{\varnothing}=D, under which every orbit decreases to the fixed point 1, to TN=UT_{\mathbb{N}}=U, under which every orbit increases. The orbits of UU are those of Mahler’s 3/2 problem [13]; for example, Ur(1)=⌊K(3/2)r⌋U^r(1)=\lfloor K(3/2)^r\rfloor with K=1.6222705…K=1.6222705\ldots [19]. The family contains the Collatz map twice:

T2N−1=T,T2N(y+1)=T(y)+1(y≥0),T_{2\mathbb{N}-1}=T,\qquad T_{2\mathbb{N}}(y+1)=T(y)+1\qquad(y\ge0),

where T(0)=0T(0)=0. Indeed, for odd yy the number y+1y+1 is even, and U(y+1)=3y+32=T(y)+1U(y+1)=\frac{3y+3}{2}=T(y)+1, while for even yy we get D(y+1)=y+22=T(y)+1D(y+1)=\frac{y+2}{2}=T(y)+1. So T2NT_{2\mathbb{N}} is the Collatz map on {0,1,2,…}\{0,1,2,\ldots\} shifted by one, with the fixed point 1 and the cycle (2,3)(2,3) in place of 0 and (1,2)(1,2); it is the map TN−T_{\mathbb{N}}^{-} of [24 Proposition 6.1]. For example,

T2N:  8,12,18,27,14,21,11,6,9,5,3,2,3,…T{primes}:  7,11,17,26,13,20,10,5,8,4,2,3,5,…T{squares}:  49,74,37,19,10,5,3,2,1,2,1,…\begin{aligned} T_{2\mathbb{N}}:\;&8,12,18,27,14,21,11,6,9,5,3,2,3,\ldots\\ T_{\{\mathrm{primes}\}}:\;&7,11,17,26,13,20,10,5,8,4,2,3,5,\ldots\\ T_{\{\mathrm{squares}\}}:\;&49,74,37,19,10,5,3,2,1,2,1,\ldots \end{aligned}

The first orbit is the Collatz orbit of 7 shifted by one and ends in (2,3)(2,3); the second ends in the cycle (2,3,5,8,4)(2,3,5,8,4) and the third in (1,2)(1,2).

An orbit of a map f:N→Nf:\mathbb{N}\to\mathbb{N} is either eventually periodic, and then ends in a cycle, which we write as a tuple that starts with its least element, or it consists of distinct numbers; then it tends to infinity, and we say that it diverges. We call TST_S bounded if all its orbits are eventually periodic, and unbounded otherwise. If SS is finite, TST_S is bounded: it maps [1,U(max⁡S)][1,U(\max S)] into itself, and every larger number goes down. The questions of this paper are:

  1. Which sets SS give bounded maps, and which cycles do the maps have?

  1. How are the maps of the family related to each other?

  1. Where, between the bounded and the unbounded maps, does the Collatz map lie, and how far is it from maps whose behaviour can actually be proved?

The rest of this introduction describes the answers we found.

Maps as subgraphs of one graph

All maps TST_S are built from the same two steps, so they all reside in one graph. The up-down graph GG has the vertex set N\mathbb{N} and, at every vertex xx, the two edges x→U(x)x \to U(x) and x→D(x)x \to D(x) (Theorem 2.2, Figure 2.1). A map TST_S is the subgraph GSG_S that keeps one of the two edges at every vertex, the up-edge at the elements of SS and the down-edge elsewhere. A family of maps, in which the step up is forced on a set AA, the step down is forced outside a set B⊇AB \supseteq A, and both are allowed in between, is the subgraph G⟨A,B⟩G_{\langle A,B\rangle} that keeps one or two edges at every vertex, and the family of all maps is GG itself.

Figure 2.1. The up-down graph GG on [1,12][1,12]. Solid arcs above the line are up-edges x→⌈3x/2⌉x \to\lceil3x/2\rceil (those leaving [1,12][1,12] are short arrows marked with their targets), dashed arcs below the line are down-edges x→⌊x/2⌋x \to\lfloor x/2\rfloor, and the loop is the down-edge at 1. A map TST_S keeps the solid edge at the elements of SS and the dashed edge elsewhere.

This gives a correspondence between maps and subgraphs (Theorem 2.3): the cycles of the maps of a family are exactly the simple cycles of its subgraph, any set of pairwise disjoint simple cycles occurs in a single map, the divergent orbits are exactly the rays (infinite simple paths), and all maps of the family are bounded if and only if the subgraph has no ray. So a classification of maps is the same as a classification of subgraphs of GG, and statements about all maps at once are statements about GG. Boundedness depends only on SS “at infinity”: changing SS at finitely many numbers does not change whether the map has a divergent orbit (Theorem 2.4).

The simplest classification

The first distinction is between sets that obviously give bounded maps and the others. If SS has no element in an interval (2B/3,B](2B/3,B], then no step leads from [1,B][1,B] above BB, so TST_S maps [1,B][1,B] into itself; we call such a BB a barrier. A set with infinitely many barriers is trivially bounded: every orbit is trapped below some barrier. This happens exactly when SS is finite or, writing S={s1<s2<⋯ }S=\{s_1<s_2<\cdots\}, when infinitely often the next element si+1s_{i+1} is out of reach of a step up from sis_i, that is, si+1>U(si)s_{i+1}>U(s_i) (Theorem 3.2). Every other set has at least log⁡3/2N−O(1)\log_{3/2}N-O(1) elements below NN, and this is sharp.

For the remaining sets the important structure is that of the step up alone. The map UU is injective, and N\mathbb{N} splits into the chains {c,U(c),U2(c),…}\{c,U(c),U^2(c),\ldots\}, one for each c≡1(mod3)c\equiv1\pmod{3}; the chains are the orbits of TNT_{\mathbb{N}}. An orbit of TST_S makes several steps up in a row exactly when SS contains several consecutive elements of a chain; in particular, it goes up at every step (we call such an orbit increasing) exactly when SS contains all elements of a chain from the starting number on. If no element of SS goes up to another element of SS, every number above 33 falls below itself within two steps, and TST_S is bounded with one or two of the cycles (1)(1), (1,2)(1,2), (2,3)(2,3), (3,5)(3,5); this holds for the squares and for a set of density 3/53/5. Two steps up in a row already allow divergent orbits (Theorem 3.3).

The density of SS turns out to say very little about TST_S. A single chain has density zero and gives an increasing orbit; even periodic sets of arbitrarily small density can give increasing orbits (Theorem 3.5). In the other direction, if the complement of SS is closed under the step down, then an orbit that leaves SS never returns to it and falls to 11. This “one-way door” gives sets of density one whose maps send every orbit to the fixed point 11 (Theorem 3.8). Table 3.1 in Section 3 collects these classes.

References

  1. [1]S. Akiyama, Ch. Frougny, and J. Sakarovitch, Powers of rationals modulo 1 and rational base number systems, Israel J. Math. 168 (2008), 53–91.
  2. [2]I. Althöfer, M. Hartisch, and T. Zipproth, Analysis of a Collatz game and other variants of the 3n + 1 problem, Advances in Computer Games (ACG 2023), Lecture Notes in Comput. Sci., vol. 14528, Springer, 2024, pp. 123–132.DOI
  3. [3]D. Applegate and J. C. Lagarias, The 3x + 1 semigroup, J. Number Theory 117 (2006), 146–159.
  4. [4]David Barina, Improved verification limit for the convergence of the Collatz conjecture, J. Supercomput. 81 (2025), Paper No. 810.DOI
  5. [5]J. H. Conway, Unpredictable iterations, Proceedings of the 1972 Number Theory Conference (University of Colorado, Boulder), 1972, pp. 49–52.
  6. [6]C. J. Everett, Iteration of the number-theoretic function f(2n) = n, f(2n + 1) = 3n + 2, Adv. Math. 25 (1977), 42–45.
  7. [7]L. Flatto, J. C. Lagarias, and A. D. Pollington, On the range of fractional parts {ξ(p/q)n}, Acta Arith. 70 (1995), 125–147.DOI
  8. [8]S. A. Kurtz and J. Simon, The undecidability of the generalized Collatz problem, Theory and Applications of Models of Computation (TAMC 2007), Lecture Notes in Comput. Sci., vol. 4484, Springer, 2007, pp. 542–553.DOI
  9. [9]J. C. Lagarias, The 3x + 1 problem and its generalizations, Amer. Math. Monthly 92 (1985), 3–23.DOI
  10. [10]———, The 3x + 1 problem: an annotated bibliography (1963–1999), 2003, arXiv:math/0309224.arxiv.org/abs/math/0309224
  11. [11]———, The 3x + 1 problem: an annotated bibliography, II (2000–2009), 2006, arXiv:math/0608208.arxiv.org/abs/math/0608208
  12. [12]J. C. Lagarias (ed.), The ultimate challenge: The 3x + 1 problem, Amer. Math. Soc., Providence, RI, 2010.
  13. [13]K. Mahler, An unsolved problem on the powers of 3/2, J. Austral. Math. Soc. 8 (1968), 313–321.DOI
  14. [14]K. R. Matthews and A. M. Watts, A generalization of Hasse’s generalization of the Syracuse algorithm, Acta Arith. 43 (1984), 167–175.DOI
  15. [15]F. Mignosi, On a generalization of the 3x + 1 problem, J. Number Theory 55 (1995), 28–45.DOI
  16. [16]Keenan Monks, Kenneth G. Monks, Kenneth M. Monks, and Maria Monks, Strongly sufficient sets and the distribution of arithmetic sequences in the 3x + 1 graph, Discrete Math. 313 (2013), 468–489.arxiv.org/abs/1204.3904
  17. [17]Kenneth M. Monks, The sufficiency of arithmetic progressions for the 3x + 1 conjecture, Proc. Amer. Math. Soc. 134 (2006), 2861–2872.
  18. [18]J. Nagura, On the interval containing at least one prime number, Proc. Japan Acad. 28 (1952), 177–181.DOI
  19. [19]A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33 (1991), 235–240.DOI
  20. [20]J. C. Oxtoby, Measure and category: a survey of the analogies between topological and measure spaces, 2nd ed., Graduate Texts in Mathematics, vol. 2, Springer, New York, 1980.
  21. [21]J. Simons and B. de Weger, Theoretical and computational bounds for m-cycles of the 3n + 1-problem, Acta Arith. 117 (2005), 51–70.
  22. [22]R. P. Steiner, A theorem on the Syracuse problem, Proceedings of the Seventh Manitoba Conference on Numerical Mathematics and Computing (1977) (Winnipeg), Congress. Numer., vol. 20, Utilitas Math., 1978, pp. 553–559.
  23. [23]R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976), 241–252.DOI
  24. [24]O. Vasilyev, Up or down by half: a family of Collatz-type maps, 2026, Preprint, arXiv:2611.10311.arxiv.org/abs/2611.10311
  25. [25]E. Yolcu, S. Aaronson, and M. J. H. Heule, An automated approach to the Collatz conjecture, J. Automated Reasoning 67 (2023), Paper No. 15, arXiv:2105.14697.arxiv.org/abs/2105.14697

Paper details

vlnc:W_gvag7w5h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus 5.5, Claude Fable 5.2

View statement
Looking for related papers…
Contents