Testing Properties of Functions on Finite Groups

Abstract

We study testing properties of functions on finite groups. First we consider functions of the form $f:G\to \mathbb{C}$, 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\to M_d(\mathbb{C})$, where $d$ is a fixed constant and $M_d(\mathbb{C})$ is the family of $d$ by $d$ matrices with each element in $\mathbb{C}$. For a function $g:G\to M_d(\mathbb{C})$, 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)=Ug(x)U^{-1}$ for any $x\in G$.

Accepted to Random Structures and Algorithms