Computing Haar Measures
share
According to Haar's Theorem, every compact group G admits a unique left-invariant Borel probability measure μ_G. Let the Haar integral (of G) denote the functional ∫_G:C(G)∋ f∫ f dμ_G integrating any continuous function f:G→R with respect to μ_G. This generalizes, and recovers for the additive group G=[0;1) 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 integral computable: once using an elegant synthetic argument; and once presenting and analyzing an explicit, imperative algorithm. 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.
READ FULL TEXT