Can you compute the operator norm?

Fritz, Tobias; Netzer, Tim; Thom, Andreas

doi:10.1090/S0002-9939-2014-12170-8

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