A binomial representation of the 3x + 1 problem

DOI10.4064/AA-91-4-367-378MaRDI QIDQ4719663zbMATH OpenOpenAlexFDO

Authors M. Margenstern, Yu. Matiyasevich

Publication date 6 January 2000

Published in Acta Arithmetica (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/207362

zbMATH Keywords

\(3n+1\) conjecture\(3x+1\) problembinomial representationCollatz problemKummer's theoremsums of products of binomial coefficientsSyracuse algorithmUlam's problem

Mathematics Subject Classification ID

Factorials, binomial coefficients, combinatorial functions (05A10) Recurrences (11B37) Binomial coefficients; factorials; (q)-identities (11B65) Special sequences and polynomials (11B83)

Review text

Let \(f(x)=(3x+1)/2\) if \(x\) is odd, and \(f(x)=x/2\) if \(x\) is even, and define \(g\) recursively by \(g(a,0)=a\) and \(g(a,k+1)=f(g(a,k))\). Then the \(3x+1\) problem is to prove that, for any positive integer \(a\), there is some \(k\) such that \(g(a,k)=1\). The relation \(\text{Syr}(a,b)\) is defined to hold when there is some \(m\) satisfying \(g(a,m)=b\). Starting with a lemma based on a theorem of Kummer, the authors prove a theorem asserting that, given positive integers \(a,b\), the relation \(\text{Syr}(a,b)\) is equivalent to the existence of integers \(w,p,r,s,t\) satisfying \(a\leq w\), \(b\leq w\), and the condition that a product of seven binomial coefficients whose entries are polynomials of \(a,b,w,p,r,s,t\) of degree \(\leq 3\) gives an odd number. Using that the \(3x+1\) conjecture is true if and only if \(\text{Syr}(a,1)\) is true for any positive integer \(a\), they derive three restatements of the \(3x+1\) conjecture in terms involving products of binomial coefficients. The last corollary asserts that \(\text{Syr}(a,1)\) is true if and only if there exists positive integers \(w,v\) with \(a\leq w\) such that a triple sum of products of binomial coefficients gives an odd number. In principle, this could make it possible to attack the Collatz problem by sophisticated algorithms searching closed forms for sums of products of binomial coefficients [cf. \textit{H. S. Wilf} and \textit{D. Zeilberger}, Invent. Math. 108, 575-633 (1992; Zbl 0739.05007)].

Recommendations

• scientific article; zbMATH DE number 2236594
• scientific article; zbMATH DE number 3889900
• scientific article; zbMATH DE number 3310994
• On the resolution of the equations U_n= x3 and V_n= x3
• scientific article; zbMATH DE number 3910471
• scientific article; zbMATH DE number 5263433
• Functional equations connected with the Collatz problem
• The inverse of a finite series and a third-order recurrent sequence
• scientific article; zbMATH DE number 1934404
• Studies on the coefficients of the analytic faculty.

Cited in

(5)

• Integral Representation and Algorithms for Closed Form Summation
• scientific article; zbMATH DE number 3871450 (Why is no real title available?)
• Some arithmetical restatements of the four color conjecture
• The Riemann hypothesis as the parity of special binomial coefficients
• Representing the integers with powers of 2 and 3.

This page was built for publication: A binomial representation of the 3x + 1 problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4719663)