×

Erdős, Klarner, and the \(3x+1\) problem. (English) Zbl 1391.11020

Summary: This paper describes work of Erdős, Klarner, and Rado on semigroups of integer affine maps and on sets of integers they generate. It gives the history of problems they studied, some solutions, and new unsolved problems that arose from them.

MSC:

11B05 Density, gaps, topology
05B15 Orthogonal arrays, Latin squares, Room squares
11B75 Other combinatorial number theory
11B83 Special sequences and polynomials
20M20 Semigroups of transformations, relations, partitions, etc.
PDFBibTeX XMLCite

References:

[1] J.-P. Allouche, J. Shallit, Automatic Sequences. Theory, Applications, Generalizations.Cambridge Univ. Press, Cambridge, 2003. · Zbl 1086.11015
[2] R. C. Bose, S. S. Shrikande, On the falsity of Euler’s conjecture about the non-existence of two orthogonal Latin squares of order 4t + 2, Proc. Natl. Acad. Sci. USA 45 (1959) 734-737. · Zbl 0085.00902
[3] R. C. Bose, S. S. Shrikande, On the construction of sets of mutually orthogonal Latin squares and the falsity of a conjecture of Euler, Latin squares of order 4t + 2, Trans. Amer. Math. Soc. 95 (1960) 191-209. · Zbl 0093.31904
[4] R. C. Bose, S.S. Shrikande, E. T. Parker, Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture, Canad. J. Math. 12 (1960) 189-203. · Zbl 0093.31905
[5] R. K. Brayton, D. Coppersmith, A. J. Hoffman, Self-orthogonal Latin squares of all orders n ≠ 2, 3, 6, Bull. Amer. Math. Soc. 80 (1974) 116-118. · Zbl 0277.05011
[6] R. K. Brayton, D. Coppersmith, A. J. Hoffman, Self-orthogonal Latin squares, in Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, pp. 509-517. Atti dei Convegni Lincei No. 17, Accad. Naz. Lincei, Rome 1976. · Zbl 0363.05018
[7] J. Cassaigne, T. Harju, J. Karhumäki, On the undecidability of freeness of matrix semigroups, Int. J. Algebra Comput. 9 no. 3-4 (1999) 295-305. · Zbl 1029.20027
[8] J. Cassaigne, F. Nicolas, On the decidability of semigroup freeness, RAIRO Theor. Inform. Appl. 46 no. 3 (2012) 355-399. · Zbl 1252.20050
[9] V. Chvatal, D. Klarner, D. E. Knuth, Selected combinatorial research problems, Stanford Computer Science Dept. Technical Report STAN-CS-72-292, June 1972, 31 pages.
[10] L. Collatz, On the motivation and origin of the 3x + 1 problem (Chinese), J. Qufu Normal Univ., Natural Sci. Ed. [Qufu shi fan da xue xue bao. Zi ran ke xue ban], 12 no. 3 (1986) 9-11. (English translation in [40, 241-247].) · Zbl 1230.11028
[11] J. H. Conway, Unpredictable iterations, in Proc. 1972 Number Theory Conference. Univ. of Colorado, Boulder, CO. 1972. 49-52. [Reprinted in [40].] · Zbl 0337.10041
[12] J. H. Conway, On unsettleable arithmetical problems, Amer. Math. Monthly 120 no. 3 (2013) 192-198. · Zbl 1297.11013
[13] D. Coppersmith, The complement of certain recursively defined sets, J. Combin. Theory Ser. A 18 no. 3 (1975) 243-251. (MR 51 #5477). · Zbl 0302.05004
[14] H. S. M. Coxeter, Cyclic Sequences and Frieze Patterns, (The Fourth Felix Behrend Memorial Lecture), Vinculum 8 (1971) 4-7. [Reprinted in [40].]
[15] D. J. Crampin, A. J. W. Hilton, Remarks on Sade’s disproof of the Euler conjecture with an application to Latin squares orthogonal to their transpose, J. Comb. Theory Ser. A 18 (1975), 47-59. · Zbl 0325.05011
[16] P. Erdős, My joint work with Richard Rado, in Surveys in combinatorics 1987 (New Cross 1987), London Math. Soc. Lecture Notes No. 123. Cambridge Univ. Press, Cambridge, 1987. 53-80. · Zbl 0623.01010
[17] P. Erdős, R. L. Graham, Old and new problems and results in combinatorial number theory: van der Waerden’s theorem and related topics, Enseign. Math. 25 no. 3-4 (1979) 325-344. (MR 81f:10005). · Zbl 0434.10002
[18] P. Erdős, R. L. Graham, Old and new problems and results in combinatorial number theory, Monographie No. 28 de L’Enseignement Mathématique. Kundig, Geneva 1980. · Zbl 0434.10001
[19] L. Euler, Recherches sure une nouvelle espace de quarres magiques, Verhandelingern uitgegeven door het zeeuwch Genootschap der Wetenschappen te Vissingen 9 Middelburg 1782, 85-239. (E530 in Enëstrom index of Euler’s works) (Opera Omnia: Series 1, Volume 7, 291-392.)
[20] L. Euler, Investigations of a new type of magic square, trans. of [19], by Audie Ho and Dominic Klyve. (Available at Euler archive.)
[21] M. L. Fredman, Growth properties of a class of recursively defined functions, Ph.D. Thesis, Stanford Computer Science Department, June 1972. (Also issued as Stanford Computer Science Dept. Technical Report STAN-CS-72-296.)
[22] M. L. Fredman, D. E. Knuth, Recurrence relations based on minimization, J. Math. Anal. Appl. 48 (1974) 534-559. · Zbl 0312.65091
[23] R. K. Guy, Don’t try to solve these problems!, Amer. Math. Monthly 90 (1983) 35-41. · Zbl 0505.10007
[24] R. K. Guy, Unsolved Problems in Number Theory.Third ed. Problem Books in Mathematics, Springer-Verlag, New York, 2004. · Zbl 1058.11001
[25] A. J. W. Hilton, Private communications, 2010 and 2014.
[26] D. G. Hoffman, Sets of integers closed under affine operators, Ph.D. thesis, University of Waterloo, 1976.
[27] D. G. Hoffman, D. A. Klarner, Sets of integers closed under affine operators—The closure of finite sets, Pacific J. Math. 78 no. 2 (1978) 337-344. · Zbl 0418.10054
[28] D. G. Hoffman, D. A. Klarner, Sets of integers closed under affine operators—The finite basis theorem, Pacific J. Math. 83 no. 1 (1979) 135-144. · Zbl 0437.10030
[29] D. A. Klarner, Sets generated by iteration of a linear operation, Stanford Computer Science Department report STAN-CS-72-275, March 1972.
[30] D. A. Klarner, An algorithm to determine when certain sets have 0 density, J. Algorithms 2 (1981) 31-43. · Zbl 0464.10046
[31] D. A. Klarner, A sufficient condition for certain semigroups to be free, J. Algebra 74 (1982) 140-148. · Zbl 0472.10055
[32] D. A. Klarner, m-recognizability of sets closed under certain affine functions, Discrete Appl. Math. 21 no. 3 (1988) 207-214. · Zbl 0682.68084
[33] D. A. Klarner, J.-C. Birget, W. Satterfield, On the undecidability of the freeness of integer matrix semigroups, Int. J. Algebra Comput. 1 no. 2 (1991) 223-226. · Zbl 0724.20036
[34] D. A. Klarner, K. Post, Some fascinating integer sequences, Discrete Math. 106/107 (1992) 303-309. · Zbl 0780.11009
[35] D. A. Klarner, R. Rado, Arithmetic properties of certain recursively defined sets, Stanford Computer Science Dept. Technical Report, STAN-CS-72-269, Stanford University, March 1972, 31 pages. [Published as [37].]
[36] D. A. Klarner, R. Rado, Linear combinations of sets of consecutive integers, Amer. Math. Monthly 80 no. 9 (1973) 985-989. · Zbl 0278.10014
[37] D. A. Klarner, R. Rado, Arithmetic properties of certain recursively defined sets, Pacific J. Math. 53 no. 2 (1974) 445-463. · Zbl 0321.05004
[38] D. Klyve, L. Stemkowski, Graeco-Latin squares and a mistaken conjecture of Euler, College Math. J. 37 no. 1 (2006) 2-15.
[39] J. C. Lagarias, The 3x + 1 problem and its generalizations, Amer. Math. Monthly 92 (1985) 3-23. [Reprinted with corrections in [40].] · Zbl 0566.10007
[40] J. C. Lagarias (Editor), The Ultimate Challenge: The 3x + 1 Problem.American Mathematical Society, Providence, RI, 2010. · Zbl 1253.11003
[41] A. Sade, Contribution à la théorie des quasi-groupes: Diviseurs singuliers. C. R. Acad. Sci. Paris 237 (1953) 272-274. · Zbl 0051.25401
[42] A. Sade, Produit direct-singulier de quasigroupes orthogonaux et anti-abéliens. Ann. Soc. Sci. Bruxelles Sér. I 74 (1960) 91-99. · Zbl 0100.02204
[43] G. Tarry, Le probléme des 36 officiers. C. R. Assoc. France Av. Sci. 29 part 2 (1900) 170-203. · JFM 32.0219.04
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.