文章基本信息

标题：Computing Haar Measures
本地全文：下载
作者：Arno Pauly ; Dongseong Seon ; Martin Ziegler 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：152
页码：1-17
DOI：10.4230/LIPIcs.CSL.2020.34
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：According to Haarâs Theorem, every compact topological group G admits a unique (regular, right and) left-invariant Borel probability measure Î¼_G. Let the Haar integral (of G) denote the functional â^«_G:?(G)â^< f â¦ â^« f d Î¼_G integrating any continuous function f:G â' â" with respect to Î¼_G. This generalizes, and recovers for the additive group G=[0;1)mod 1, the usual Riemann integral: computable (cmp. Weihrauch 2000, Theorem 6.4.1), and of computational cost characterizing complexity class #P_1 (cmp. Ko 1991, Theorem 5.32). We establish that in fact, every computably compact computable metric group renders the Haar measure/integral computable: once using an elegant synthetic argument, exploiting uniqueness in a computably compact space of probability measures; and once presenting and analyzing an explicit, imperative algorithm based on "maximum packings" with rigorous error bounds and guaranteed convergence. Regarding computational complexity, for the groups SO(3) and SU(2), we reduce the Haar integral to and from Euclidean/Riemann integration. In particular both also characterize #P_1.
关键词：Computable analysis; topological groups; exact real arithmetic; Haar measure