Computable topological groups and Pontryagin duality

Melnikov, Alexander

doi:10.1090/tran/7355

Computable topological groups and Pontryagin duality
HTML articles powered by AMS MathViewer

by Alexander Melnikov PDF

Trans. Amer. Math. Soc. 370 (2018), 8709-8737 Request permission

Abstract:

The well-known Pontryagin Duality (classically) reduces the study of compact abelian groups to the algebraic theory of discrete abelian groups. At first glance, Pontryagin Duality seems to be “algorithmic” in nature. Quite unexpectedly, the situation is more intricate. Nonetheless, using methods of computable analysis from the work of Weihrauch and modern techniques of computable algebra (e.g., the recent metatheorem), we establish a partial algorithmic analogy of Pontryagin Duality and use it to derive a handful of corollaries. We believe that most of these consequences are fundamental to the emerging systematic theory of computable Polish groups. We also apply our techniques to measure the complexity of the classification problem for profinite and connected compact Polish groups.

References

C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842
Ewan J. Barker, Back and forth relations for reduced abelian $p$-groups, Ann. Pure Appl. Logic 75 (1995), no. 3, 223–249. MR 1355134, DOI 10.1016/0168-0072(94)00045-5
Vasco Brattka, Peter Hertling, and Klaus Weihrauch, A tutorial on computable analysis, New computational paradigms, Springer, New York, 2008, pp. 425–491. MR 2762094, DOI 10.1007/978-0-387-68546-5_{1}8
William W. Boone, The word problem, Ann. of Math. (2) 70 (1959), 207–265. MR 179237, DOI 10.2307/1970103
R. G. Downey and Stuart A. Kurtz, Recursion theory and ordered groups, Ann. Pure Appl. Logic 32 (1986), no. 2, 137–151. MR 863331, DOI 10.1016/0168-0072(86)90049-7
Rod Downey and Antonio Montalbán, The isomorphism problem for torsion-free abelian groups is analytic complete, J. Algebra 320 (2008), no. 6, 2291–2300. MR 2437501, DOI 10.1016/j.jalgebra.2008.06.007
V. P. Dobrica, Constructivizable abelian groups, Sibirsk. Mat. Zh. 22 (1981), no. 3, 208–213, 239 (Russian). MR 621475
V. P. Dobritsa, Some constructivizations of abelian groups, Sibirsk. Mat. Zh. 24 (1983), no. 2, 18–25 (Russian). MR 695289
Rodney G. Downey, On presentations of algebraic structures, Complexity, logic, and recursion theory, Lecture Notes in Pure and Appl. Math., vol. 187, Dekker, New York, 1997, pp. 157–205. MR 1455136
R. G. Downey, Computability theory and linear orderings, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 823–976. MR 1673590, DOI 10.1016/S0049-237X(98)80047-5
Yuri L. Ershov and Sergei S. Goncharov, Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000. MR 1749622, DOI 10.1007/978-1-4615-4305-3
Yu. Ershov, Problems of solubility and constructive models [in Russian], Nauka, Moscow (1980).
Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles McCoy, and Antonio Montalbán, Isomorphism relations on computable structures, J. Symbolic Logic 77 (2012), no. 1, 122–132. MR 2951633, DOI 10.2178/jsl/1327068695
Gerald B. Folland, A course in abstract harmonic analysis, 2nd ed., Textbooks in Mathematics, CRC Press, Boca Raton, FL, 2016. MR 3444405
László Fuchs, Infinite abelian groups. Vol. I, Pure and Applied Mathematics, Vol. 36, Academic Press, New York-London, 1970. MR 0255673
László Fuchs, Infinite abelian groups. Vol. II, Pure and Applied Mathematics. Vol. 36-II, Academic Press, New York-London, 1973. MR 0349869
S. S. Goncharov and Dzh. Naĭt, Computable structure and antistructure theorems, Algebra Logika 41 (2002), no. 6, 639–681, 757 (Russian, with Russian summary); English transl., Algebra Logic 41 (2002), no. 6, 351–373. MR 1967769, DOI 10.1023/A:1021758312697
Noam Greenberg, Alexander G. Melnikov, Julia F. Knight, and Daniel Turetsky, Uniform procedures in uncountable structures, To appear.
S. S. Gončarov, Autostability of models and abelian groups, Algebra i Logika 19 (1980), no. 1, 23–44, 132 (Russian). MR 604656
S. S. Gončarov, Groups with a finite number of constructivizations, Dokl. Akad. Nauk SSSR 256 (1981), no. 2, 269–272 (Russian). MR 600943
Sergei S. Goncharov, Countable Boolean algebras and decidability, Siberian School of Algebra and Logic, Consultants Bureau, New York, 1997. MR 1444819
Xiaolin Ge and J. Ian Richards, Computability in unitary representations of compact groups, Logical methods (Ithaca, NY, 1992) Progr. Comput. Sci. Appl. Logic, vol. 12, Birkhäuser Boston, Boston, MA, 1993, pp. 386–421. MR 1281158
G. Higman, Subgroups of finitely presented groups, Proc. Roy. Soc. London Ser. A 262 (1961), 455–475. MR 130286, DOI 10.1098/rspa.1961.0132
Matthew Harrison-Trainor, Alexander Melnikov, and Antonio Montalbán, Independence in computable algebra, J. Algebra 443 (2015), 441–468. MR 3400410, DOI 10.1016/j.jalgebra.2015.06.004
N. G. Khisamiev, Constructive abelian groups, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 1177–1231. MR 1673602, DOI 10.1016/S0049-237X(98)80050-5
Iskander Kalimullin, Bakhadyr Khoussainov, and Alexander Melnikov, Limitwise monotonic sequences and degree spectra of structures, Proc. Amer. Math. Soc. 141 (2013), no. 9, 3275–3289. MR 3068980, DOI 10.1090/S0002-9939-2013-11586-8
Charlotte Lin, Recursively presented abelian groups: effective $p$-group theory. I, J. Symbolic Logic 46 (1981), no. 3, 617–624. MR 627909, DOI 10.2307/2273759
Peter Loth, Classifications of abelian groups and Pontrjagin duality, Algebra, Logic and Applications, vol. 10, Gordon and Breach Science Publishers, Amsterdam, 1998. MR 1741074
Peter La Roche, Effective Galois theory, J. Symbolic Logic 46 (1981), no. 2, 385–392. MR 613291, DOI 10.2307/2273630
Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Classics in Mathematics, Springer-Verlag, Berlin, 2001. Reprint of the 1977 edition. MR 1812024, DOI 10.1007/978-3-642-61896-3
A. I. Mal′cev, Constructive algebras. I, Uspehi Mat. Nauk 16 (1961), no. 3 (99), 3–60 (Russian). MR 0151377
A. I. Mal′cev, On recursive Abelian groups, Dokl. Akad. Nauk SSSR 146 (1962), 1009–1012 (Russian). MR 0151378
David Marker, Model theory, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, 2002. An introduction. MR 1924282
Timothy H. McNicholl, A note on the computable categoricity of $\ell ^p$ spaces, Evolving computability, Lecture Notes in Comput. Sci., vol. 9136, Springer, Cham, 2015, pp. 268–275. MR 3382366, DOI 10.1007/978-3-319-20028-6_{2}7
Alexander G. Melnikov, Computably isometric spaces, J. Symbolic Logic 78 (2013), no. 4, 1055–1085. MR 3156512
Alexander G. Melnikov, Computable abelian groups, Bull. Symb. Log. 20 (2014), no. 3, 315–356. MR 3271281, DOI 10.1017/bsl.2014.32
Alexander G. Melnikov and Antonio Montalb$\rm \acute {a}$n, Computable Polish group actions, To appear.
Alexander G. Melnikov and Keng Meng Ng, Computable torsion abelian groups, Adv. Math. 325 (2018), 864–907. MR 3742605, DOI 10.1016/j.aim.2017.12.011
G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289–320. MR 556895, DOI 10.1016/0003-4843(79)90011-1
Alexander G. Melnikov and André Nies, The classification problem for compact computable metric spaces, The nature of computation, Lecture Notes in Comput. Sci., vol. 7921, Springer, Heidelberg, 2013, pp. 320–328. MR 3102033, DOI 10.1007/978-3-642-39053-1_{3}7
Alexander G. Melnikov and Keng Meng Ng, Computable structures and operations on the space of continuous functions, Fund. Math. 233 (2016), no. 2, 101–141. MR 3466002, DOI 10.4064/fm36-12-2015
Sidney A. Morris, Pontryagin duality and the structure of locally compact abelian groups, London Mathematical Society Lecture Note Series, No. 29, Cambridge University Press, Cambridge-New York-Melbourne, 1977. MR 0442141
Timothy H. McNicholl and D. M. Stull, The isometry degree of a computable copy of $l^p$, To appear.
P. S. Novikov, Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp, Izdat. Akad. Nauk SSSR, Moscow, 1955 (Russian). Trudy Mat. Inst. Steklov. no. 44. MR 0075197
A. Nurtazin, Computable classes and algebraic criteria of autostability, Summary of Scientific Schools, Math. Inst. SB USSRAS, Novosibirsk, 1974.
Marian B. Pour-El and J. Ian Richards, Computability in analysis and physics, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989. MR 1005942, DOI 10.1007/978-3-662-21717-7
L. S. Pontryagin, Topological groups, Gordon and Breach Science Publishers, Inc., New York-London-Paris, 1966. Translated from the second Russian edition by Arlen Brown. MR 0201557
Hartley Rogers Jr., Theory of recursive functions and effective computability, 2nd ed., MIT Press, Cambridge, MA, 1987. MR 886890
Rick L. Smith, Two theorems on autostability in $p$-groups, Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80) Lecture Notes in Math., vol. 859, Springer, Berlin-New York, 1981, pp. 302–311. MR 619876
Rick L. Smith, Effective aspects of profinite groups, J. Symbolic Logic 46 (1981), no. 4, 851–863. MR 641497, DOI 10.2307/2273233
A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. London Math. Soc. (2) 42 (1936), no. 3, 230–265. MR 1577030, DOI 10.1112/plms/s2-42.1.230
A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction, Proc. London Math. Soc. (2) 43 (1937), no. 7, 544–546. MR 1575661, DOI 10.1112/plms/s2-43.6.544
Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407, DOI 10.1007/978-3-642-56999-9
Klaus Weihrauch, On computable metric spaces Tietze-Urysohn extension is computable, Computability and complexity in analysis (Swansea, 2000) Lecture Notes in Comput. Sci., vol. 2064, Springer, Berlin, 2001, pp. 357–368. MR 1893086, DOI 10.1007/3-540-45335-0_{2}1