×

Bounds for the \(3x+1\) problem using difference inequalities. (English) Zbl 1069.11011

The “Collatz”-problem (or “3x+1”- or “Hasse”- or “Syracuse”- or “Kakutani”- problem) is to prove that for every \(n \in \mathbb N\) there exists a \(k\) with \(T^{(k)}(n)=1\) where the function \(T(n)\) takes odd numbers \(n\) to \((3n+1)/2\) and even numbers \(n\) to \(n/2\). Let \(\pi_1(x)\) count the number of integers below \(x\) that eventually reach \(1\) under this iteration. There are a number of estimates of the form \(\pi_1(x)>x^\gamma\) for a positive constant \(\gamma\) and sufficiently large \(x\). In the note under review the authors improve \(\gamma=0.81\), found by D. Applegate and J. C. Lagarias [see Math. Comput. 64, 411–426, 427–438 (1995; Zbl 0820.11006)], to \(\gamma=0.84\). They are able to establish that the nonlinear lower bounds from the difference inequalities introduced by the first author [see Int. J. Math. Math. Sci. 12, No. 4, 791–796 (1989; Zbl 0685.10008)] do give lower bounds for the \(3x+1\) function. Their main result uses a refined linear program family and relies on heavy computations.

MSC:

11B83 Special sequences and polynomials
26A18 Iteration of real functions in one variable
11B37 Recurrences
PDFBibTeX XMLCite
Full Text: DOI arXiv