Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions

In this paper, we study two questions related to the problem of testing whether a function is close to a homomorphism. For two finite groups G , H (not necessarily Abelian), an arbitrary map f : G , H , and a parameter 0 < ε < 1, say that f is ε ‐close to a homomorphism if there is some homomorphism g such that g and f differ on at most ε | G | elements of G , and say that f is ε ‐far otherwise. For a given f and ε , a homomorphism tester should distinguish whether f is a homomorphism, or if f is ε ‐far from a homomorphism. When G is Abelian, it was known that the test which picks O (1/ ε ) random pairs x , y and tests that f ( x ) + f ( y ) = f ( x + y ) gives a homomorphism tester. Our first result shows that such a test works for all groups G . Next, we consider functions that are close to their self‐convolutions. Let A = { a g | g ε G } be a distribution on G . The self‐convolution of A , A ′ = { a | g ε G }, is defined by It is known that A = A ′ exactly when A is the uniform distribution over a subgroup of G . We show that there is a sense in which this characterization is robust—that is, if A is close in statistical distance to A ′ , then A must be close to uniform over some subgroup of G . Finally, we show a relationship between the question of testing whether a function is close to a homomorphism via the above test and the question of characterizing functions that are close to their self‐convolutions.