Can you compute the operator norm?
HTML articles powered by AMS MathViewer
- by Tobias Fritz, Tim Netzer and Andreas Thom PDF
- Proc. Amer. Math. Soc. 142 (2014), 4265-4276 Request permission
Abstract:
In this note we address various algorithmic problems that arise in the computation of the operator norm in unitary representations of a group on a Hilbert space. We show that the operator norm in the universal unitary representation is computable if the group is residually finite-dimensional or amenable with a decidable word problem. Moreover, we relate the computability of the operator norm on the group $F_2 \times F_2$ to Kirchberg’s QWEP Conjecture, a fundamental open problem in the theory of operator algebras.References
- Charles A. Akemann and Phillip A. Ostrand, Computing norms in group $C^*$-algebras, Amer. J. Math. 98 (1976), no. 4, 1015–1047. MR 442698, DOI 10.2307/2374039
- N. I. Akhiezer, The classical moment problem and some related questions in analysis, Hafner Publishing Co., New York, 1965. Translated by N. Kemmer. MR 0184042
- Gilbert Baumslag and Donald Solitar, Some two-generator one-relator non-Hopfian groups, Bull. Amer. Math. Soc. 68 (1962), 199–201. MR 142635, DOI 10.1090/S0002-9904-1962-10745-9
- Bachir Bekka, Operator-algebraic superridigity for $\textrm {SL}_n(\Bbb Z)$, $n\geq 3$, Invent. Math. 169 (2007), no. 2, 401–425. MR 2318561, DOI 10.1007/s00222-007-0050-5
- Bachir Bekka, Pierre de la Harpe, and Alain Valette, Kazhdan’s property (T), New Mathematical Monographs, vol. 11, Cambridge University Press, Cambridge, 2008. MR 2415834, DOI 10.1017/CBO9780511542749
- William W. Boone, The word problem, Ann. of Math. (2) 70 (1959), 207–265. MR 179237, DOI 10.2307/1970103
- V. V. Borisov, Simple examples of groups with unsolvable word problem, Mat. Zametki 6 (1969), 521–532 (Russian). MR 260851
- F. Brandão and A.W. Harrow, Quantum de Finetti theorems under local measurements with applications, 2012. arXiv:1210.6367.
- Nathanial P. Brown and Narutaka Ozawa, $C^*$-algebras and finite-dimensional approximations, Graduate Studies in Mathematics, vol. 88, American Mathematical Society, Providence, RI, 2008. MR 2391387, DOI 10.1090/gsm/088
- Man Duen Choi, The full $C^{\ast }$-algebra of the free group on two generators, Pacific J. Math. 87 (1980), no. 1, 41–48. MR 590864
- Jakob Cimprič, A representation theorem for Archimedean quadratic modules on $*$-rings, Canad. Math. Bull. 52 (2009), no. 1, 39–52. MR 2494309, DOI 10.4153/CMB-2009-005-4
- A. Doherty and S. Wehner, Convergence of SDP hierarchies for polynomial optimization on the hypersphere, 2012. arXiv:1210.5048.
- T. Fritz, Operator system structures on the unital direct sum of $C^*$-algebras, 2010. arXiv:1011.1247. To appear in Rocky Mountain J. Math.
- Tobias Fritz, Tsirelson’s problem and Kirchberg’s conjecture, Rev. Math. Phys. 24 (2012), no. 5, 1250012, 67. MR 2928100, DOI 10.1142/S0129055X12500122
- Harry Kesten, Symmetric random walks on groups, Trans. Amer. Math. Soc. 92 (1959), 336–354. MR 109367, DOI 10.1090/S0002-9947-1959-0109367-6
- O. G. Harlampovič, A finitely presented solvable group with unsolvable word problem, Izv. Akad. Nauk SSSR Ser. Mat. 45 (1981), no. 4, 852–873, 928 (Russian). MR 631441
- Eberhard Kirchberg, On nonsemisplit extensions, tensor products and exactness of group $C^*$-algebras, Invent. Math. 112 (1993), no. 3, 449–489. MR 1218321, DOI 10.1007/BF01232444
- Jean B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2000/01), no. 3, 796–817. MR 1814045, DOI 10.1137/S1052623400366802
- Franz Lehner, Computing norms of free operators with matrix coefficients, Amer. J. Math. 121 (1999), no. 3, 453–486. MR 1738412
- Alexander Lubotzky and Yehuda Shalom, Finite representations in the unitary dual and Ramanujan groups, Discrete geometric analysis, Contemp. Math., vol. 347, Amer. Math. Soc., Providence, RI, 2004, pp. 173–189. MR 2077037, DOI 10.1090/conm/347/06272
- W. Magnus, Das Identitätsproblem für Gruppen mit einer definierenden Relation, Math. Ann. 106 (1932), no. 1, 295–307 (German). MR 1512760, DOI 10.1007/BF01455888
- A. Malcev, On isomorphic matrix representations of infinite groups, Rec. Math. [Mat. Sbornik] N.S. 8 (50) (1940), 405–422 (Russian, with English summary). MR 0003420
- J. C. C. McKinsey, The decision problem for some classes of sentences without quantifiers, J. Symbolic Logic 8 (1943), 61–76. MR 8991, DOI 10.2307/2268172
- K. A. Mihaĭlova, The occurrence problem for free products of groups, Mat. Sb. (N.S.) 75 (117) (1968), 199–210 (Russian). MR 0222179
- A. Włodzimierz Mostowski, On the decidability of some problems in special classes of groups, Fund. Math. 59 (1966), 123–135. MR 224693, DOI 10.4064/fm-59-2-123-135
- P. S. Novikov, On algorithmic unsolvability of the problem of identity, Doklady Akad. Nauk SSSR (N.S.) 85 (1952), 709–712 (Russian). MR 0052436
- P. S. Novikov, On the algorithmic insolvability of the word problem in group theory, American Mathematical Society Translations, Ser. 2, Vol. 9, American Mathematical Society, Providence, R.I., 1958, pp. 1–122. MR 0092784
- M. Navascués, S. Pironio, and A. Acín, A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations, New Journal of Physics 10 (2008), no. 7, 073013.
- S. Pironio, M. Navascués, and A. Acín, Convergent relaxations of polynomial optimization problems with noncommuting variables, SIAM J. Optim. 20 (2010), no. 5, 2157–2180. MR 2650843, DOI 10.1137/090760155
- Narutaka Ozawa, About the QWEP conjecture, Internat. J. Math. 15 (2004), no. 5, 501–530. MR 2072092, DOI 10.1142/S0129167X04002417
- Konrad Schmüdgen, Noncommutative real algebraic geometry—some basic concepts and first ideas, Emerging applications of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York, 2009, pp. 325–350. MR 2500470, DOI 10.1007/978-0-387-09686-5_{9}
- Alfred Tarski, A decision method for elementary algebra and geometry, University of California Press, Berkeley-Los Angeles, Calif., 1951. 2nd ed. MR 0044472
- 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
- Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe (eds.), Handbook of semidefinite programming, International Series in Operations Research & Management Science, vol. 27, Kluwer Academic Publishers, Boston, MA, 2000. Theory, algorithms, and applications. MR 1778223, DOI 10.1007/978-1-4615-4381-7
Additional Information
- Tobias Fritz
- Affiliation: Perimeter Institute for Theoretical Physics, 31 Caroline Street North, Waterloo, Ontario, Canada N2L 2Y5
- Email: tfritz@perimeterinstitute.ca
- Tim Netzer
- Affiliation: University of Leipzig, PF 100920, 04009 Leipzig, Germany
- Email: tim.netzer@math.uni-leipzig.de
- Andreas Thom
- Affiliation: University of Leipzig, PF 100920, 04009 Leipzig, Germany
- MR Author ID: 780176
- ORCID: 0000-0002-7245-2861
- Email: andreas.thom@math.uni-leipzig.de
- Received by editor(s): July 12, 2012
- Received by editor(s) in revised form: January 15, 2013
- Published electronically: August 7, 2014
- Communicated by: Marius Junge
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 142 (2014), 4265-4276
- MSC (2010): Primary 43A20
- DOI: https://doi.org/10.1090/S0002-9939-2014-12170-8
- MathSciNet review: 3266994