Testing properties of functions on finite groups1. Issue 3 (16th February 2016)

• Record Type: Journal Article
• Authors: Oono, Kenta; Yoshida, Yuichi
• Is Part Of: Random structures & algorithms. Volume 49:Issue 3(2016)
• Page Start: 579
• Page End: 598
• Publication Date: 2016-02-16
• Subjects: property testing -- homomorphism -- finite groups; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20639
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We study testing properties of functions on finite groups. First we consider functions of the form f : G → ℂ, where G is a finite group. We show that conjugate invariance, homomorphism, and the property of being proportional to an irreducible character is testable with a constant number of queries to f, where a character is a crucial notion in representation theory. Our proof relies on representation theory and harmonic analysis on finite groups. Next we consider functions of the form f : G → M d ( ℂ ), where d is a fixed constant and M d ( ℂ ) is the family of d by d matrices with each element in ℂ . For a function g : G → M d ( ℂ ), we show that the unitary isomorphism to g is testable with a constant number of queries to f, where we say that f and g are unitary isomorphic if there exists a unitary matrix U such that f ( x ) = U g ( x ) U − 1 for any x ∈ G . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 579–598, 2016