Testing Properties of Functions on Finite Groups

arXiv:1509.00930v1 [cs.DS] 3 Sep 2015

Kenta Oono
Preferred Networks, Inc.
oono@preferred.jp

Yuichi Yoshida∗
National Institute of Informatics, and
Preferred Infrastructure, Inc.
yyoshida@nii.ac.jp
September 4, 2015

Abstract
We study testing properties of functions on finite groups. First we consider functions of the
form f : G → 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 → Md (C), where d is a fixed constant and Md (C) is the family of d
by d matrices with each element in C. For a function g : G → Md (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) = U g(x)U −1 for any
x ∈ G.

1

Introduction

In property testing [27, 14], we want to decide whether the input function f satisfies a predetermined
property P or “far” from it. More specifically, an algorithm is called a tester for a property P if,
given a query access to the input function f and a parameter ǫ > 0, it accepts with probability at
least 2/3 when f satisfies P, and rejects with probability at least 2/3 when f is ǫ-far from P. If
a tester accepts with probability one when f satisfies P, then it is called a one-sided error tester.
The definition of ǫ-farness depends on the model, but for the case of Boolean functions, we say that
a function f : Fn2 → {−1, 1} is ǫ-far from P if the distance dist(f, g) := Prx [f (x) 6= g(x)] of f and
g is at least ǫ for any function g : Fn2 → {−1, 1} satisfying P. Here −1 and 1 are corresponding
to true and false, respectively. The efficiency of the tester is measured by the number of queries
to f , called the query complexity. We say that a property P is constant-query testable if there is a
tester with query complexity depending only on ǫ (and not on n at all).
The study of testing properties of Boolean functions, or more generally, functions on finite fields
was initiated by Rubinfeld and Sudan [27], and then subsequently many properties have been shown
to be constant-query testable [14, 11, 16, 13]. To incorporate the algebraic structure of the finite
field, Kaufman and Sudan [20] asked to study affine-invariant properties, that is, properties P such
that, if f : Fnp → {0, 1} satisfies P, then f ◦ A also satisfies P for any bijective affine transformation
∗

Supported by JSPS Grant-in-Aid for Young Scientists (B) (No. 26730009), MEXT Grant-in-Aid for Scientific
Research on Innovative Areas (No. 24106001), and JST, ERATO, Kawarabayashi Large Graph Project.

1

A. A lot of progress has been made on the study of the constant-query testability of affine-invariant
properties [10, 17], and finally (almost) complete characterizations of constant-query testability were
achieved [9, 33]. For further details on function property testing, refer to [8, 25] for surveys.
Besides finite fields, functions over finite groups such as the cyclic group and the permutation group are also objects that naturally appear in various contexts, e.g., circuit complexity [1],
computational learning [32], and machine learning [18]. Despite its importance, there are only a
few works on testing properties on functions over finite groups [5, 14], and extending this line of
research is the main focus of the present paper. More specifically, we consider testing properties of
functions f of the form f : G → D, and more generally, f : G → D(d), where G is a finite group,
D = {z ∈ C | |z| ≤ 1} is the unit disk, and D(d) = {A ∈ Md (C) | kAkF ≤ 1} is the set of d by d
matrices with Frobenius norm at most one. Note that D(1) = D. We regard d as a constant. The
reason that we use D and D(d) is that they are maximal sets closed under multiplication. Below,
we get into the details of these two settings.
Testing properties of functions of the form f : G → D: We define
the distance between two
p
functions f, g : G → D as dist(f, g) = 12 kf − gk2 , where kf k2 := Ex∈G |f (x)|2 is the L2 norm.
Note that dist(f, g) is always in [0, 1]. We say that a function f : G → D is ǫ-far from a property P
if dist(f, g) ≥ ǫ for any function g : G → D satisfying P. We note that, for {−1, 1}-valued functions
√
f, g : G → {−1, 1}, we have Pr[f (x) 6= g(x)] = ǫ if and only if dist(f, g) = ǫ holds. Hence, we have
a quadratic gap between our definition and the standard definition using the Hamming distance.
However, we adopt the L2 norm as it is more friendly with our analysis.
We first show the following:
• Conjugate invariance, that is, f (yxy −1 ) = f (x) for any x, y ∈ G, is one-sided error testable
with O(1/ǫ2 ) queries.
• Homomorphism, that is, f (x)f (y) = f (xy) for any x, y ∈ G, is one-sided error testable with
O(1/ǫ2 log(1/ǫ)) queries.
We show the constant-query testability of conjugate invariance by a simple combinatorial argument.
When G = Fn2 , then homomorphism is often called linearity and intensively studied in the area
of property testing [4, 6, 14, 28]. PIndeed in this case, a function f : Fn2 → D is homomorphism if
and only if f (x) = χS (x) := (−1) i∈S xi for some S ⊆ {1, . . . , n}.
The case G = Sn , the permutation group of order n, is easy to understand. Let f : Sn → D
be a function on the permutation group. If f is conjugate invariant, then the value of f (π) only
depends on the cycle pattern of π. If f is homomorphism, then f is the all-zero function, the all-one
function, or the function that returns the sign of the input permutation.
We note that Ben-Or et al. [5] studied the constant-query testability of homomorphism from a
finite group to another finite group. The query complexity of their algorithm is O(1/ǫ), where the
distance is measured by the Hamming distance. Their algorithm and analysis by a combinatorial
argument extends to our setting, in which the range is D and the distance is measured by the
L2 norm, with query complexity O(1/ǫ2 ). In this sense, our result on homomorphism is not new.
Nevertheless, we prove it again using harmonic analysis over finite groups. By doing so, we can
generalize it for testing other properties.
To describe our next result, we need to introduce the basic of representation theory. A representation of a group G is a homomorphism ϕ of the form ϕ : G → Md (C) for some integer d.
In particular, we study the family of irreducible representations, where any representation can be
2

described as the direct sum of irreducible representations. We mention that irreducible representations ϕ : G → Md (C) can be chosen as unitary, that is, ϕ(x) is unitary for all x ∈ G. The character
of a representation ϕ is the function χϕ (x) = tr(ϕ(x)), where tr(·) denotes the trace of a matrix. The character carries the essential information about the representation in a more condensed
form and is intensively studied in character theory. The character of an irreducible representation
is called an irreducible
character. For example, every irreducible character of Fn2 is of the form
P
χS (x) = (−1) i∈S xi for some S ⊆ {1, . . . , n}, which is often called a character in Fourier analysis
of Boolean functions. If G is abelian, that is, commutative, then representations of G always map
to one-dimensional matrices, and hence a representation and its corresponding character coincide.
However, this is not the case when G is not abelian, which makes the analysis more involved. We
show the following:
• The property of being proportional to an irreducible character, that is, f = cχϕ for some
c ∈ C and irreducible representation ϕ, is testable with O(1/ǫ8 log2 (1/ǫ)) queries.
The reason that we do not consider irreducible characters themselves is that irreducible characters
may take values outside of D. In particular, χϕ (1) = d holds for the identity element 1 ∈ G and
the dimension d of ϕ.
When G = Fn2 , then irreducible characters coincide with linear functions, that is, χS for some
S ⊆ {1, . . . , n}. Hence, testing the property of being proportional to an irreducible character can
be seen as another generalization of linearity testing.
The form of irreducible characters is quite complicated in general. When G = Sn , however, its
combinatorial interpretation via Young Tableau is well studied [12, 21, 29] (though still complicated
to state here).
Testing properties of functions of the form f : G → D(d): Since the representations of
a group G are matrix-valued, it is natural to consider testing properties of q
functions of the form

f : G → D(d). For two functions f, g : G → D(d), we define dist(f, g) = 21 Ex kf (x) − g(x)k2F .
Note that this is indeed a metric and matches the previous definition of distance when d = 1.
Let U (d) be the set of d by d unitary matrices with each element in C. We show the following:
• Unitary equivalence to g : G → D(d), that is, f = U gU −1 for some unitary matrix U ∈ U (d),
2
is testable with (d3/2 /ǫ)O(d ) queries.
Here g is a parameter of the problem and not a part of the input. Unitary equivalence is an
important notion when studying representations since the irreducibility of a representation ϕ is
preserved by the transformation ϕ 7→ U ϕU −1 for a unitary matrix U .
Our tester samples unitary matrices from the Haar measure, a fundamental tool in the representation theory of Lie Groups, and then checks whether g becomes close to f by applying these
unitary matrices.
Arguably the simplest property of matrix-valued functions is again homomorphism. However,
homomorphism is known to be constant-query testable by a combinatorial argument [5], and the
harmonic analysis does not facilitate the analysis. Therefore we do not study homomorphism of
matrix-valued functions in this paper.

3

Related work: There are a number of works on testing whether a function on a finite group is a
homomorphism. Blum et al. [14] gave a tester (the BLR tester ) for homomorphism of functions on
a finite group. However, the number of queries depends on the number of generators of the group,
which may depend on the size of the group in general. Ben-Or et al. [5] gave another algorithm
without this dependency. Bellare et al. [4] gave a Fourier-analytic proof of the BLR tester when
the domain and the range are Fn2 and F2 , respectively. Our tester for homomorphism can be seen
as a generalization of their analysis to general groups. There has been an interest in improving
various parameters of homomorphism testing results, due to their applications in the construction
of probabilistically checkable proof (PCP) [3]. Bellare et al. [4] gave an almost tight connection
between the distance to homomorphism and the rejection probability of the BLR tester. BenSasson et al. [6] and Shpilka and Wigderson [28] reduced the number of random bits required by
the test as it affects the efficiency of the proof system and in turn the hardness of approximation
results that one can achieve using the proof system. Rubinfeld [26] studied properties of a function
on a finite group that are defined by functional equations and gave a sufficient condition of constantquery testability.
Using the Lp norm for p ≥ 1 as a distance measure in property testing is recently systematically
studied by Berman et al. [7]. One of their motivations is exploring the connection of property
testing with learning theory and approximation theory. For this purpose, the Lp norm is more
favorable than the Hamming distance because, in learning theory and approximation theory, we
typically measure errors in the Lp norm for p = 1 or 2. Indeed, several lower bounds and upper
bounds for property testing in the Lp norm were shown using this connection. See [7] for more
details.
Representation theory is one of the most important areas in modern mathematics. Representation theory itself is intensively studied and it is also used as an analytical tool in harmonic analysis,
invariant theories, and modular theory. Representation theory have been used in various problems
of theoretical computer science such as constructing pseudorandom objects [2, 19], circuit complexity [1], communication complexity [24], computational learning [32], machine learning [18], and
quantum property testing [23].
Organization: In Section 2, we introduce representation theory, harmonic analysis on finite
groups, and the Haar measure in more detail. We discuss the testability of conjugacy invariance in
Section 3. We show that homomorphism and the property of a being proportional to an irreducible
character are constant-query testable in Sections 4 and 5, respectively. Section 6 is devoted to
testing unitary equivalence.

2

Preliminaries

For an integer n ≥ 1, [n] denotes the set {1, 2, . . . , n}. Let δij be Kronecker’s delta, that is, δij = 1
if i = j and δij = 0 if i 6= j. For a matrix M , we denote its (i, j)-th element by Mij . We √
write the
real and imginary part of a complex number z as ℜz and ℑz, respectively (hence z = ℜz + −1ℑz).
For a complex number z, z denotes its conjugate.
We frequently use the following lemma.
Lemma 2.1. Let f : G → D be a function for some finite group G. For any ǫ > 0, with probability
at least 1 − δ, we can compute an estimate z of Ex∈G [f (x)] such that |z − Ex∈G [f (x)]| ≤ ǫ . The
number of queries to f is O(1/ǫ2 log 1/δ).
4

x1 , . . . , xs uniformly at random from G,
Proof. Let c = Ex∈G [f (x)]. To estimate c, we sample
1P
2
where s = Θ(1/ǫ log 1/δ). Then, we output e
c := s i∈[s] f (xx ). Clearly, the query complexity is
O(1/ǫ2 log 1/δ).
We now show that e
c is indeed a good approximation to c. Since |ℜ(f (x))| ≤ 1, from Hoeffding’s
inequality, we have |ℜ(c) − ℜ(e
c)| ≤ ǫ/2 with probability at least 1 − δ/2 by choosing the hidden
constant in s large enough. Similarly, we have |ℑ(c) − ℑ(e
c)| ≤ ǫ/2 with probability at least 1 − δ/2.
By the union bound, we have |c − e
c| ≤ |ℜ(c) − ℜ(e
c)| + |ℑ(c) − ℑ(e
c)| ≤ ǫ with probability at least
1 − δ.

2.1

Representation theory

We introduce basic notions and facts in representation theory. See, e.g., [30] for more details.
For a vector space V over a field F, GLF (V ) denotes the set of invertible linear transformations.
We only consider the case F = C in this paper, and hence we omit the subscript for simplicity.
A representation of G is a pair (ϕ, V ) of a finite-dimensional vector space V and a homomorphism ϕ : G → GL(V ), that is, ϕ(xy) = ϕ(x)ϕ(y) for every x, y ∈ G and ϕ(1) is the identity
transformation for the identity element 1 ∈ G. For a representation (ϕ, V ), V is called the representation space of it. When V is clear from the context, we simply call ϕ a representation. The
dimension of a representation (ϕ, V ) is the dimension of V . When V is a finite-dimensional vector
space, then we say that (ϕ, V ) is finite-dimensional representation. In our argument, we only need
finite-dimensional representations.
We describe the decomposition of a representation into irreducible representations, which is a
fundamental tool used in representation theory. For a representation (ϕ, V ) and a subspace W of
V , we say that W is G-invariant if ϕ(G)W ⊆ W . If W is a G-invariant space, then we can regard
the range of ϕ as GL(W ), and hence we obtain a representation (ϕ, W ). Note that {0} and V are
G-invariant from the definition. A representation (ϕ, V ) is called irreducible if {0} and V are the
only G-invariant spaces. Note that a one-dimensional representation is always irreducible. When G
is abelian, then we have the converse from Schur’s Lemma, that is, any irreducible representation
is one-dimensional. When G is non-abelian, however, an irreducible representation might have
dimension more than one. This fact makes the analysis of algorithms for functions on a non-abelian
group more involved.
Two representations (ϕ, V ) and (ψ, W ) of G are equivalent if there exists an invertible linear
transformation T : V → W such that, for every x ∈ G, it holds that ψ(x)◦T = T ◦ϕ(x) . We identify
b the family of equivalence classes of irreducible
equivalent representations, and we denote by G
representations. It is known that there is a one-to-one correspondence between conjugacy classes
b
of G and G.
A representation (ϕ, V ) is unitary if, for all x ∈ G, ϕ(x) is a unitary transformation. For any
representation of G, there is an equivalent unitary representation. Hence, we can take unitary
b and we identify it with G.
b Since
representations as a complete system of representatives of G,
b
b
G is finite, so is G. For ϕ ∈ G, we denote the dimension of its representation space by dϕ . In
what follows, we fix a basis of the vector space of each representation (ϕ, V ), and we regard it as
a homomorphism from G to Mdϕ (C), where dϕ is the dimension of V .

5

2.2

Fourier analysis on non-abelian finite groups

We regard the space of C-valued functions of G as an inner product space by defining hf, gi =
Ex∈G [f (x)g(x)] for f, g : G → C. The following fact is known.
p
b i, j ∈ [dϕ ] forms an orthonordϕ ϕij | ϕ ∈ G,
Lemma 2.2 ([30]). For a finite group G, the set
mal basis of the space of C-valued functions of G.
Hence, we can decompose f : G → C as
X
X
X
X
fb(ϕ)ij ϕij (x),
hf, ϕij iϕij (x) =
dϕ
f (x) =
dϕ
i,j∈[dϕ ]

b
ϕ∈G

i,j∈[dϕ ]

b
ϕ∈G

where fb(ϕ) ∈ Mdϕ (C) is defined as fb(ϕ) = Ex∈G [f (x)ϕ(x)] and called the Fourier coefficient of
ϕ. This decomposition is called the Fourier expansion of f . Note that Fourier coefficients are
matrix-valued functions. The following is well known.
Lemma 2.3 ([30]). Let f, g : G → C be functions. Then, we have
X
X
fb(ϕ)ij gb(ϕ)ij ,
hf, gi =
dϕ
ϕ

kf k22 =

2.3

X
ϕ

(Plancherel’s identity)

i,j∈[dϕ ]

dϕ

X

i,j∈[dϕ ]

|fb(ϕ)ij |2 .

(Parseval’s identity)

Class functions and characters

For a representation ϕ : G → Mdϕ (C), the character χϕ : G → C of ϕ is defined as χϕ (x) = tr(ϕ(x))
for x ∈ G. We say that a function f : G → C is conjugate invariant if f (x) = f (yxy −1 ) for all
x, y ∈ G. A conjugate invariant function is sometimes called a class function. It is not hard to
check that characters are conjugate invariant. Indeed, the following fact is known.

b forms an orthonormal basis of the space
Lemma 2.4. For a finite group G, the set χϕ | ϕ ∈ G
of C-valued class functions of G.

Note that if a representation is one-dimensional, its character is identical to the original representation, hence is a homomorphism. This is not the case in general.
The following lemma says that Fourier coefficients of a class function are always diagonal.
Lemma 2.5. For any class function f : G → C, it holds that fb(ϕ) =

hf,χϕ i
dϕ Idϕ .

In order to prove Lemma 2.5, we need the following two auxiliary lemmas:

Lemma 2.6. For a function f : G → C and an irreducible representation ϕ, we have
Proof.
hf, χϕ i = E
x

=

X

X
k

ρ

dρ

X
i,j

hf, χϕ i = tr(fb(ϕ)).
fb(ρ)ij ρij (x)

fb(ϕ)kk = tr(fb(ϕ)).

X

ϕkk (x) =

X
ρ

k

6

dρ

X
i,j

fb(ρ)ij

X
hρij , ϕkk i
k

Lemma 2.7. Let f : G → C be a function and g : G → C be a class function. Then,
X
g (ϕ)).
hf, gi =
tr(fb(ϕ))tr(b
ϕ

Proof. Since g is a class function, we can represent g(x) =
X X
fb(ϕ)ij hg, χ′ϕ i E[ϕij (x)χϕ′ (x)]
hf, gi =
dϕ
=

X

X

dϕ

i,j

ϕ,ϕ′

=

X

dϕ

ϕ

i

X

ϕ,ϕ′

=
=

XX

X
ϕ

Proof of Lemma 2.5.

ϕ

≤

i,j

ϕ

fb(ϕ)ij

fb(ϕ)ij

fb(ϕ)ii

X
ϕ

X X

X

Now we have

X

X

X
i′

i′

i′

gb(ϕ′ )i′ i′
gb(ϕ′ )i′ i′

X
j′

X
j′

E[ϕij (x)ϕ′j ′ j ′ (x)]
x

(from Lemma 2.6)

hϕij , ϕ′j ′ j ′ i

gb(ϕ)i′ i′

g (ϕ)).
tr(fb(ϕ))tr(b

kf k22 =
=

ϕ hg, χϕ iχϕ (x).

x

i,j

ϕ,ϕ′

P

i∈[dϕ ]

dϕ

tr(fb(ϕ))

fb(ϕ)ii

X

i,j∈[dϕ ]

2

≤

fb(ϕ)ij

2

(from Lemma 2.7)

X
ϕ

2

dϕ

X

i∈[dϕ ]

= kf k22 .

fb(ϕ)ii

2

(by Cauchy-Schwarz)
(by Parseval’s identity)

Therefore, the equality holds for both inequalities in the formula above. In particular, fb(ϕ) is
proportional to the identity matrix cIdϕ for some c ∈ C. By Lemma 2.6, hf, χϕ i = tr(fb(ϕ)) = cdϕ .
Hence, c = hf, χϕ i/dϕ , and we have the lemma.

2.4

Introduction to the Haar measure

In this section, we introduce Haar measure briefly. See, e.g., a textbook [22] for more details.
A topological group is a group equipped with a topology and whose group operations are continuous in its topology. A finite group is a topological group if it is endowed with a discrete topology.
2
Any subgroup of Md (C) is a topological group, in which we identify Md (C) with Cd and introduce
2
the topology induced by Cd .
We call a measure µ on a topological group G left invariant (resp., right invariant) if µ(xS) =
µ(S) (resp., µ(S) = µ(Sx)) for any x ∈ G and Borel set S ⊆ G. Similarly, We call µ invariant
under taking inverse if µ(S −1 ) = µ(S) for any Borel set S ⊆ G where S −1 = {x−1 | x ∈ S}.
For any compact topological group G, there exists a measure on G which is left invariant, right
invariant, and invariant under taking inverse. Such a measure is unique up to scalar multiplication
and called the Haar measure on G. For example, the Haar measure µ of a finite group G is (a
scalar multiplication of) the counting measure, that is, µ(S) = |S|/|G| for subset S ⊆ G.
We regard U (d) as a closed subgroup of Md (C) and regard it as a compact topological group.
Hence, the Haar measure of U (d) exists.
7

Algorithm 1 (Tester for conjugate invariance)
1: for s := O(1/ǫ2 ) times do
2:
Sample x and y ∈ G uniformly at random.
3:
if f (x) 6= f (yxy −1 ) then reject.
4: Accept.

3

Conjugate Invariance

In this section, we first show that conjugate-invariance is constant-query testable.
Theorem 3.1. Conjugate invariance is one-sided error testable with O(1/ǫ2 ) queries.
Then, we show the following lemma, which simplifies testing properties that imply conjugate
invariance.
Lemma 3.2. Let P be a property such that every f satisfying P is a class function. Suppose that
there is a tester A for P with query complexity q(ǫ) if the input is restricted to be a class function.
Then there is a tester A′ for P with query complexity O(1/ǫ2 + q(ǫ/2) log q(ǫ/2)). Moreover, if A
is a one-sided error tester, then A′ is also a one-sided error tester.

3.1

Proof of Theorem 3.1

Our algorithm for testing conjugate invariance is described in Algorithm 1. It is easy to see that
the query complexity of Algorithm 1 is O(1/ǫ2 ) and the tester always accepts when f is conjugate
invariant. Thus, it suffices to show that Algorithm 1 rejects with probability at least 2/3 when f
is ǫ-far from class functions.
It is well known that conjugacy classes of G form a partition of G. We define G♯ as the set of
conjugacy classes of G. Also, for an element x ∈ G, we define x♯ as the unique conjugacy class x
belongs to.
′
♯
−1
′
For y ∈ x♯ , we define Nx,y =
F {z ∈ G | zxz = y}. Since we have Nx,y ∩ Nx,y = ∅ for y, y ∈ x
′
with y 6= y , it holds that G = y∈x♯ Nx,y . Therefore, the following lemma guarantees that uniform
sampling from a conjugacy class is executed by uniformly sampling from the whole group.
Lemma 3.3. The number of elements in Nx,y depends only on the conjugacy class to which y
belongs.
Proof. For y, y ′ ∈ x♯ , fix z0 , z0′ ∈ G so that z0 xz0−1 = y and z0′ xz0′ −1 = y ′ hold. We construct
mappings Φy,y′ : Nx,y → Nx,y′ by z 7→ z0′ z −1 z0 and Φy′ ,y : Nx,y′ → Nx,y by z 7→ z0 z −1 z0′ . By a
direct calculation, we can check that Φy,y′ ◦ Φy′ ,y = idNx,y , and Φy′ ,y ◦ Φy,y′ = idNx,y′ . Therefore
|Nx,y | = |Nx,y′ | holds.
Fix a function f : G → D. For a conjugacy class C ∈ G♯ and z ∈ C, define pC (z) := ♯{x ∈
C | f (x) = z}/|C| as the probability that f (x) = z if we sample x ∈ C uniformly at random. We
define pC := maxz∈C pC (z) and zC := arg maxz∈C pC (z). Then, we define fe as fe(x) = zx♯ . Note
that fe is a class function such that fe(x) ∈ D for any x ∈ G.

Lemma 3.4.

Pr [f (x) 6= f (yxy −1 )] ≥ dist(f, fe)2 .

x,y∈G

8

Proof. Since |x − y| ≤ 2 for any x, y ∈ D, we have
1 X
1
|C|(1 − pC ).
dist(f, fe)2 = E |f (x) − fe(x)|2 ≤ Pr[f (x) 6= fe(x)] =
x
4 x
|G|
♯
C∈G

By Lemma 3.3, if we fix x ∈ G and sample y ∈ G uniformly at random, then yxy −1 forms a
uniform distribution over elements in x♯ . Thus,
Z
1 X
Pr [f (x) 6= f (yxy −1 )] ≥
|C| pC (z)(1 − pC (z))dz
x,y∈G
|G|
C∈G♯
Z
X
1 X
1
|C| pC (z)(1 − pC )dz =
|C|(1 − pC ) ≥ dist(f, fe)2 .
≥
|G|
|G|
♯
♯
C∈G

C∈G

Lemma 3.5. If f is ǫ-far from being conjugate invariant, then Algorithm 1 rejects with probability
at least 2/3.
Proof. Since fe : G → D is a class function, we have dist(f, fe) ≥ ǫ. Hence, the probability we reject
at Line 3 in each trial is at least ǫ2 by Lemma 3.4. Hence the tester rejects with probability 2/3
by choosing the hidden constant in s large enough.
We establish Theorem 3.1 by Lemma 3.5.

3.2

Proof of Lemma 3.2

The following lemma shows that we can obtain a query access to a class function that is close to f .
Lemma 3.6. Let f : G → D be a function that is ǫ-close to a class function. There exists a class
function f ′ : G → D with the following property.
• For any x ∈ G, with O(log 1/δ) queries to f , we can correctly compute f ′ (x) or find a witness
that f is not a class function with probability at least 1 − δ. Moreover, if f itself is a class
function, then we can always compute f ′ (x) correctly.
• dist(f ′ , f ) ≤ 3ǫ. In particular, f ′ = f when f itself is a class function.

P
∗ ∈ D be the unique value that minimizes
∗ 2
Proof. For a conjugacy class C, let zC
x∈C |f (x) − zC | .
∗
∗
∗
∗
We define f : G → D as f (x) = zx♯ . Note that f is the class function closest to f .
We define f ′ : G → D as follows:
(
zx∗♯ if px♯ ≤ 21 ,
f ′ (x) =
zx♯ otherwise.
We first show the first claim. Our algorithm for computing f ′ (x) is as follows. Given x ∈ G,
we pick y1 , . . . , ys ∈ G for s := O(log 1/δ) uniformly at random, and compute f (yi xyi−1 ) for each
i ∈ [s]. If f (yi xyi−1 ) 6= f (yj xyj−1 ) for some i 6= j, then we reject f and output the pair as the
witness that f is not a class function. If all of them are the same, we output the value as f ′ (x).

9

Now we analyze the correctness of the algorithm above. If px♯ ≤ 1/2, then with probability
at least 1 − δ, we have f (yi xyi−1 ) 6= f (yj xyj−1 ) for some i 6= j, and we reject. If px♯ > 1/2, with
probability at least 1 − δ, the majority of {f (yi xyi−1 )}i∈[s] is equal to zC . Hence, with probability
at least 1 − δ, either we output zC or reject.
Moreover, if f itself is a class function, then we have f ′ (x) = f (x) for any x ∈ G, and our
algorithm always outputs f (x) as f ′ (x).
We turn to the second
pP claim. For two functions g, h : G → C and a conjugacy class C,
♯
2
define distC (g, h) :=
x∈C |g(x) − h(x)| . We will show that, for each conjugacy class C ∈ G ,
distC (f, f ′ ) ≤ 3distC (f, f ∗ ), which implies dist(f, f ′ ) ≤ 3ǫ.
If C satisfies pC ≤ 1/2, we have nothing to show. Thus suppose pC > 1/2. Then, we have
sX
q
′
∗
∗ ′
∗ − z |2 .
|f (x) − f ∗ (x)|2 + |C||zC
distC (f, f ) ≤ distC (f, f ) + distC (f , f ) =
C
x∈C

∗ when constructing f ∗ from f , we have
Since a pC -fractionP
of values has moved from zC to zC
P
∗
2
∗ − z |2 ≤ 2
∗
2
pC |C||zC − zC | ≤ x∈C |f (x) − f (x)| . By pC > 1/2, we have |C||zC
C
x∈C |f (x) −
√
∗
2
′
f (x)| . Combining this with the previous inequality, we have distC (f, f ) ≤ (1 + 2)distC (f, f ∗ ) ≤
3distC (f, f ∗ ).

Proof of Lemma 3.2. We first apply the ǫ/6-tester for conjugate invariance (Algorithm 1). If the
tester rejects, we immediately reject f as it implies that f does not satisfy P . Otherwise, using
Lemma 3.6, we construct a query access to a class function f ′ with δ = O(1/q(ǫ/2)). Then we
apply the tester A to f ′ with the error parameter ǫ/2. The query complexity is clearly as stated.
Suppose that f satisfies the property P . Then, we never reject when testing conjugate invariance. Also f ′ (x) = f (x) holds for every x ∈ G and it follows that f ′ satisfies the property P .
Hence, the tester A accepts f ′ with probability at least 2/3. Moreover if A is a one-sided error
tester, then A accepts f ′ with probability one.
Suppose that f is ǫ-far from the property P . If f is ǫ/6-far from conjugate invariance, then we
reject f with probability at least 2/3. Thus assume that f is ǫ/6-close to conjugate invariance. In
this case f ′ is a class function that is ǫ/2-close to f . Hence f ′ is still ǫ/2-far from the property P .
Then the tester A on f ′ should reject with probability 2/3.

4

Testing Homomorphism

In this section, we show the following:
Theorem 4.1. Homomorphism is one-sided error testable with O(1/ǫ2 log(1/ǫ)) queries.
We note that, if f : G → C is a homomorphism, then it is a one-dimensional representation
and hence an irreducible representation. First we observe that homomorphism implies conjugate
invariance.
Lemma 4.2. If f : G → C is a homomorphism, then f is conjugate invariant.
Proof. Since f is a homomorphism, we have for any x, y ∈ G, f (yxy −1 ) = f (y)f (x)f (y −1 ) =
f (y)f (y −1 )f (x) = f (yy −1 )f (x) = f (1)f (x). By setting y = 1, we have f (x) = f (1)f (x), which
means f (x) = 0 or f (1) = 1.
10

Algorithm 2 (Tester for homomorphism)
Input: A class function f : G → D.
1: for s = O(1/ǫ2 ) times do
2:
Sample x, y ∈ G uniformly at random.
3:
if f (x)f (y) 6= f (xy) then reject.
4: Accept.
If f (x) = 0 for all x ∈ G, then f is clearly conjugate invariant. If f (x) 6= 0 for some x ∈ G, then
f (1) = 1. In this case, we have f (yxy −1 ) = f (1)f (x) = f (x) and f is again conjugate invariant.
From Lemmas 3.2 and 4.2, to test homomorphism, it suffices to show that homomorphism is
one-sided error testable with O(1/ǫ2 ) queries when the input function is a class function. Our
tester is given in Algorithm 2. It is clear that the query complexity is O(1/ǫ2 ). We next see that
Algorithm 2 always accepts homomorphisms:
Lemma 4.3. If a class function f : G → D is a homomorphism, then Algorithm 2 always accepts.
Proof. We always accept because f (x)f (y) = f (xy) for any x, y ∈ G
Now we turn to the case that f is ǫ-far from homomorphisms. To show that Pr[f (x)f (y) 6=
f (xy)] is much smaller than 1, we analyze the term f (x)f (y)f (xy).
Lemma 4.4. For any function f : G → C, we have
E [f (x)f (y)f (xy)] =

x,y

X

dϕ

ϕ

X

i,j,k∈[dϕ ]

Proof. The left hand side is equal to
X

dϕ dϕ′ dϕ′′

ϕ,ϕ′ ,ϕ′′

X

X

X

fb(ϕ)ij fb(ϕ′ )i′ j ′ fb(ϕ′′ )i′′ j ′′ E [ϕij (x)ϕ′i′ j ′ (y)ϕ′′i′′ j ′′ (xy)].
x,y

i,j∈[dϕ ] i′ ,j ′ ∈[dϕ′ ] i′′ ,j ′′ ∈[dϕ′′ ]

Now we analyze the expectation in (1).
h
′
′
E [ϕij (x)ϕi′ j ′ (y)ϕ′′i′′ j ′′ (xy)] = E ϕij (x)ϕi′ j ′ (y)
x,y

x,y

=

X

k ′′ ∈[dϕ′′ ]

Hence (1) =

hϕij , ϕ′′i′′ k′′ ihϕ′i′ j ′ ϕ′′k′′ j ′′ i

P

ϕ dϕ

P

b

=

b

fb(ϕ)ij fb(ϕ)jk fb(ϕ)ik .

(

X

ϕ′′i′′ k′′ (x)ϕ′′k′′ j ′′ (y)

k ′′ ∈[dϕ′′ ]

1
d2ϕ

if ϕ = ϕ′ = ϕ′′ , i = i′′ , j = i′ = k′′ , and j ′ = j ′′ ,

0

otherwise.
b

i,j,j ′ ∈[dϕ ] f (ϕ)ij f (ϕ)jj ′ f (ϕ)ij ′ .

Corollary 4.5. For any class function f : G → C, we have
X
X
fb(ϕ)ii |fb(ϕ)ii |2 .
dϕ
E [f (x)f (y)f (xy)] =
x,y

i

ϕ

11

i∈[dϕ ]

(1)

b and i 6= j ∈ [dϕ ] by Lemma 2.5.
Proof. If f is a class function, then fb(ϕ)ij = 0 for any ϕ ∈ G
Hence, we have the corollary from Lemma 4.4.
The following lemma completes the proof of Theorem 4.1.

Lemma 4.6. If a class function f : G → D is ǫ-far from homomorphism, then Algorithm 2 rejects
with probability at least 2/3.
Proof. From Corollary 4.5, we have
ℜ E [f (x)f (y)f (x + y)] = ℜ
x,y

≤
=

max

b
ϕ∈G,i∈[d
ϕ]

max

b
ϕ∈G,i∈[d
ϕ]

ℜfb(ϕ)ii ·

X

X
ϕ

dϕ

ϕ

dϕ

X

i∈[dϕ ]

ℜfb(ϕ)ii · kf k22

≤

X

i∈[dϕ ]

fb(ϕ)ii |fb(ϕ)ii |2

|fb(ϕ)ii |2

max

b
ϕ∈G,i∈[d
ϕ]

ℜfb(ϕ)ii .

For any ϕ with dimension more than one, |fb(ϕ)ii | ≤ 1/2 and hence ℜfb(ϕ)ii ≤ 1/2 (see Lemma 2.5).
Now consider a one-dimensional irreducible representation ϕ. Since f is ǫ-far from homomorphism,
we have
q
q
1
1
2
2
ǫ ≤ dist(f, ϕ) =
kf k2 + kϕk2 − 2ℜhf, ϕi ≤
2 − 2ℜfb(ϕ).
2
2
Note that kf k22 ≤ 1 and kϕk22 = 1 as ϕ is a (non-zero) homomorphism. Hence, ℜfb(ϕ) ≤ 1 − 2ǫ2 .
We have shown that ℜ Ex,y [f (x)f (y)f (x + y)] ≤ 1 − 2ǫ2 . Since |f (x)f (y)f (x + y)| ≤ 1, at least
an Ω(ǫ2 )-fraction of pairs (x, y) satisfy f (x)f (y)f (x + y) 6= 1. Hence we have Prx,y [f (x)f (y) =
f (x+ y)] ≤ 1− Ω(ǫ2 ). By choosing the hidden constant in s large enough, we reject with probability
at least 2/3.

5

Testing the Property of Being Proportional to an Irreducible
Character

In this section, we show the following:
Theorem 5.1. The property of being proportional to an irreducible character is testable with
O(1/ǫ8 log2 (1/ǫ)) queries.
As any character is a class function, by Lemma 3.2, it suffices to give a tester with query
complexity O(1/ǫ8 log(1/ǫ)) that works when the input function is a class function. The following
fact is crucial for our algorithm.
Lemma 5.2 ([31]). For a function f : G → C, the following are equivalent.
1. f (x) = f (1)e
χϕ (x) for some irreducible representation ϕ, where χ
eϕ = χϕ /dϕ .

2. f (x)f (y) = f (1) Ez∈G [f (yzxz −1 )] for any x, y ∈ G.

12

Algorithm 3 (Tester for being proportional to an irreducible character)
Input: A function f : G → D.
1: Let e1 be the estimation to kf k22 obtained by applying Lemma 2.1 with the error parameter
ǫ2 /100 and the confidence parameter 1/100.
2: if e1 < ǫ2 /2 then accept.
3: for each i = 1 to s := O(1/ǫ4 ) do
4:
Sample x, y ∈ G uniformly at random.
5:
Let ei5 be the estimation to Ez [f (yzxz −1 )] obtained by applying Lemma 2.1 with the error
parameter ǫ2 /10 and the confidence parameter 1/100s.
6:
Let ei6 = |f (x)f (y) − f (1)e5i |2 .
7:
if ei6 > ǫ4 /100 then reject.
8: accept.
As we can freely change the value of f (1) by multiplying a constant, the second condition is a
necesary and sufficient condition of being proportional to an irreducible character.
The most simple test based on Lemma 5.2 is checking whether f (x)f (y) ≈ f (1) Ez [f (yzxz −1 )]
(by estimating the latter by sampling z ∈ G a constant number of times). However, we were unable
to handle the term Ex,y,z [f (x)f (y)f (yzxz −1 )f (1)] that naturally arises when analyzing this test.
Instead, we estimate |f (x)f (y) − f (1) Ez [f (xyzxz −1 )]| and check whether it is small. The detail is
given in Algorithm 3. It is clear that the query complexity of Algorithm 3 is O(1/ǫ8 log 1/ǫ).
Lemma 5.3. If a function f : G → C is proportional to an irreducible character, then Algorithm 3
accepts with probability at least 2/3.
Proof. By the union bound, all the estimations succeed with probability at least 2/3. Below we
assume this indeed happens.
Recall that f (x)f (y) − f (1) Ez [f (yzxz −1 )] = 0 for any x, y ∈ G by Lemma 5.2. Then for each
i
i, e6 = |f (x)f (y) − f (1)ei5 |2 = |f (1) Ez [f (yzxz −1 )] − f (1)ei5 |2 ≤ ǫ4 /100 holds for every i ∈ [s].
Hence, we accept with probability at least 2/3.
Now we turn to the case that f is ǫ-far from being proportional to an irreducible character. We
need the following auxiliary lemma.
Lemma 5.4. For any function f : G → C, we have
h
i
2
≥ kf k22 min kf − f (1)e
χϕ k22 .
E f (x)f (y) − f (1) E[f (yzxz −1 )]
x,y

ϕ

z

13

Proof. We have
i
hX
i
X
−1
−1
b
f
(ϕ)
ϕ
(yzxz
)
d
f
(yzxz
)
=
E
E
ij ij
ϕ
z

=E
z

=

h

z

hX
dϕ

ϕ

=
=

dϕ

ϕ

X

X

X

i,j∈[dϕ ]

X

i,j∈[dϕ ]

dϕ

X

ϕ

i,j∈[dϕ ]

X

X

dϕ

ϕ

i,j∈[dϕ ]

ϕ

fb(ϕ)ij

fb(ϕ)ij

fb(ϕ)ij

i,j∈[dϕ ]

X

k,l,m∈[dϕ ]

X

k,l,m∈[dϕ ]

X

i
ϕik (y)ϕkl (z)ϕlm (x)ϕmj (z −1 )

h
i
ϕik (y)ϕlm (x) E ϕkl (z)ϕjm (z)
z

ϕik (y)ϕlm (x)

k,l,m∈[dϕ ]

fb(ϕ)ij ϕij (y)

δkj δlm
dϕ

X ϕkk (x) X
X
fb(ϕ)ij ϕij (y)
=
dϕ χ
eϕ (x)
dϕ
ϕ

k∈[dϕ ]

i,j∈[dϕ ]

In the third equality, we used the fact that ϕmj (z −1 ) = ϕjm (z). This follows from the fact that
ϕ(z −1 )ϕ(z) = ϕ(1) = I and ϕ(z) is unitary.
Therefore,
X
X
X
X
fb(ϕ)ij ϕij (y)
fb(ϕ)ij ϕij (y) − f (1)
dϕ χ
eϕ
dϕ
f (x)f (y) − f (1) E[f (yzxz −1 )] = f (x)
z

=

X
ϕ

dϕ (f (x) − f (1)e
χϕ (x))

X

i,j∈[dϕ ]

ϕ

ϕ

i,j∈[dϕ ]

i,j∈[dϕ ]

fb(ϕ)ij ϕij (y)

It follows that
i
hX
i
h
X
2
−1 2
fb(ϕ)ij ϕ(y)ij
dϕ (f (x) − f (1)e
χϕ (x))
= E
E f (x)f (y) − f (1) E[f (yzxz )]

=

X

ϕ,ϕ′

=

X
ϕ

x,y

z

x,y



ϕ

dϕ dϕ′ E (f (x) − f (1)e
χϕ′ (x))
χϕ (x))(f (x) − f (1)e
x

dϕ kf − f (1)e
χϕ k22

≥kf k22 min kf
ϕ

−

X

i,j∈[dϕ ]

f (1)e
χϕ k22

fb(ϕ)ij

2

 X

i,j∈[dϕ ]

i,j∈[dϕ ] i′ ,j ′ ∈[dϕ′ ]

≥ min kf − f (1)e
χϕ k22
ϕ

X

X
ϕ

dϕ



fb(ϕ)ij fb(ϕ′ )i′ j ′ E ϕij (y)ϕ′i′ j ′ (y)

X

i,j∈[dϕ ]

y

fb(ϕ)ij

2



In the third equality, we used the fact that Ey ϕij (y)ϕ′i′ j ′ (y) is equal to 1/dϕ if ϕ = ϕ′ , i = i′ , and
j = j ′ , and is equal to zero otherwise.
Lemma 5.5. If a function f : G → C with f (1) = 1 is ǫ-far from being proportional to an
irreducible character, then Algorithm 3 rejects with probability at least 2/3.
Proof. By the union bound, with probability at least 5/6, all the estimations succeed. Below we
assume it indeed happens.
From Lemma 5.4, when f is ǫ-far, the expectation of e6i is at least
i
h
2ǫ2
ǫ4
ǫ2 ǫ2
ǫ4
ǫ4
i 2
≥ (1 −
)kf k22 min kf − f (1)e
χϕ k22 −
≥ (1 − ) · kf k22 −
≥ .
E f (x)f (y) − f (1)e5
ϕ
10
100
5 4
100
25
x,y
14

Algorithm 4 (Tester for unitary equivalence)
Input: Functions f, g : G → D(d)
Θ(d2 )
times do
1: for s := d3/2 /ǫ
2:
Sample U ∈ U (d) with respect to the (normalized) Haar measure of U (d).
3:
Let e be the estimation of dist(f, U gU ∗ ) obtained by applying Lemma 2.1 with the error
parameter ǫ2 /100 and the confidence parameter 1/6s.
4:
if e < ǫ2 /10 then accept.
5: Reject.
We also note that ei6 ≤ (1 + ǫ2 /100)2 ≤ 2. Let p = Prx,y [e6i > ǫ4 /100]. Then, we have 2 · p + ǫ4 /100 ·
(1 − p) ≥ ǫ4 /25, and it follows that p ≥ ǫ4 /100. By choosing the hidden constant in s large enough,
we reject f with probability at least 2/3.

6

Testing Unitary Equivalence

In this section, we prove the following:
Theorem 6.1. The unitary equivalence to g : G → D(d) is testable with d3/2 /ǫ

O(d2 )

queries.

Our algorithm is described in Algorithm 4. We use the Haar measure on U (d) to sample
unitary matrices. We do not need the detailed definition of the Haar measure, and we only have to
understand that it defines a probability distribution on U (d). See Section 2.4 for a brief introduction
to the Haar measure.
The basic idea of our algorithm and analysis is the following. Suppose that functions f, g :
G → D(d) are unitary equivalent, that is, f = U0 gU0∗ for some unitary matrix U0 ∈ U (d). Then,
by sampling a sufficient number of unitary matrices from the Haar measure, we get a unitary
matrix U that is sufficiently close to U0 in the sense that the Frobenius norm of U − U0 is small
(Lemma 6.3). Then, we can show that the Frobenius norm of f (x) − U g(x)U ∗ is also small for
any x ∈ G (Lemma 6.5). On the other hand, if f and g are ǫ-far from being unitary equivalent,
then the average Frobenius norm of f (x) − U g(x)U ∗ over x ∈ G is large for any unitary matrix
U . Hence, by checking whether there is a unitary matrix U (in the sample) such that the average
Frobenius norm is small, we can distinguish the case that f and g are unitary equivalent from the
case that f and g are ǫ-far from being unitary equivalent.
Let U ∈ U (d) be a random matrix sampled with respect to the Haar measure. We diagonalize
U as U = W ΛW ∗ where W ∈ U (d) and Λ = diag(λ1 , . . . λd ). By the
√ unitarity of U , the absolute
value of each eigenvalue of U is 1. Therefore we can write λi = exp( −1θi ) for some θi ∈ [−π, π),
which we call the phase of λi . We use the following proposition, which is Weyl’s integral formula
applied to U (d).
Q
Proposition 6.2 ([15]). The distribution µ of the phases θ = (θ1 , . . . , θd ) is dµ(θ) = Z1d i>j |λi −
λj |2 dθ, where Zd := (2π)d d! is a normalization constant and dθ is a standard Euclid measure.
For ǫ > 0, we write BU (d) (ǫ) = {U ∈ U (d) | kU − Id kF ≤ ǫ}. We need the following auxiliary
lemma, which says that the set of a sufficiently large number of randomly chosen unitary matrices
forms an “ǫ-net” of unitary matrices with respect to the Frobenius norm.
15

Lemma 6.3. Let U0 ∈ U (d) and U be a random matrix sampled with respect to the Haar measure
of U (d). For sufficiently small ǫ > 0, the probability Pr[kU − U0 kF ≤ ǫ] ≥ δ6.3 (ǫ, d), where
O(d2 )
ǫ
δ6.3 (ǫ, d) = d3/2
.

Proof. Since the Haar measure is invariant under left multiplication, we can assume U0 = Id without
loss of generality. Hence, we want to bound Pr[U ∈ BU (d) (ǫ)]. Let λ1 , . . . , λd be eigenvalues of U and
θ1 , . . . , θd be corresponding phases. By the conjugate invariance of Frobenius norm, U ∈ BU (d) (ǫ)
P
iff di=1 |λi − 1|2 ≤ ǫ2 .
√
Suppose kθk2 ≤ 3ǫ/4. Since θi ’s are sufficiently small, we can expand as λi = 1+ −1θi +O(θi2 ).
P
P
Then di=1 |λi − 1|2 = kθk22 + O( di=1 θRi3 ) = kθk22 + kθk22 maxi |θi | < ǫ2 . It implies the probability is
bounded below by Pr[U ∈ BU (d) (ǫ)] ≥ Bd (3ǫ/4) dµ where Bd (r) is the ball in Rd of radius r centered
at the origin.
ǫ
, θ0 = [0, ǫ̃, . . . , (d − 1)ǫ̃], and θ1 = [ǫ̃/3, 4ǫ̃/3, . . . , (d − 2/3)ǫ̃]. Note that kθ0 k22 ≤
Let ǫ̃ = d3/2
ǫ2 /3 and kθ1 k22 = ǫ2 (6d2 − d + 2)/18d3 < ǫ2 /2. Therefore, Bd (3ǫ/4) contains the d-dimensional
hypercube V = {θ ∈ Rd | θ0 ≤ θ ≤ θ1 }, where we write x ≤ y if xi ≤ yi for each i. Note that if
θ ∈ V , |θi − θj | ≥ ǫ̃/3 for any i 6= j. Therefore, we have
Z
Z
Z Y
Z Y
1
1
dµ ≥
dµ ≥
|λi − λj |2 dθ ∼
|θi − θj |2 dθ
Z
Z
d V
d V
V
Bd (3ǫ/4)
i>j

i>j

(By the fact that ǫ is small enough)
Z
Z Y 2


1  ǫ̃ d2
ǫ̃
1 ǫ̃ d(d−1)
1
dθ =
.
dθ =
≥
Zd V
3
Zd 3
Zd 3
V
i>j

Let Skew(d) be the set of d-dimensional skew-Hermitian matrices, i.e., Skew(d) = {X ∈ Md (C) |
= −X}. Although the following lemma is an almost immediate consequence of the fact that
Skew(d) is the Lie algebra of U (d), we prove it for completeness.
X∗

Lemma 6.4. If ǫ > 0 is small enough, then the image of the exponential map exp : Skew(d) → U (d)
contains BU (d) (ǫ). Furthermore, if U ∈ BU (d) (ǫ), then we can choose X ∈ Skew(d) such that
exp(X) = U and kXkF ≤ 2ǫ.
∗
Proof.
1 , . . . , λd ). Let λi =
√ We diagonalize U as W ΛW , where W ∈ U (d) and Λ = diag(λ
P∞
n+1 z n /n. This
exp( −1θi ) for θi ∈ R and µi = 1 − λi . For z ∈ C, we define
√ log(1 + z) = i=1 (−1)
Taylor expansion converges for |z| ≤ 1. Note that log λi = −1(θi + 2πmi ) for some mi ∈ Z.
Since kU − Id kF ≤ ǫ, we can define X = log U . Note that U = exp(X) as z = exp(log z). We
have the following formulas:

X = log U = log W ΛW ∗ = W (log Λ)W ∗ ,
log Λ = diag(log λ1 , . . . , log λd ),
√
√
log λi = −1(θi + 2πmi ) = − −1(θi + 2πmi ) = − log λi ,

(log Λ)∗ = diag(log λ1 , . . . , log λd ) = −diag(log λ1 , . . . , log λd ) = − log Λ.
Combining these formulas, X ∗ = W (log Λ)∗ W ∗ = −W (log Λ)W ∗ = −X, that is, X ∈ Skew(d).
16

P
Next, we estimate the Frobenius norm of X. The condition kU − Id kF ≤ ǫ implies di=1 |µi |2 ≤
ǫ2 . It implies µi is small enough. So we can expand log λi = log(1 + µi ) = µi + O(µ2i ). Therefore | log λi |2 = |µi |2 + O(µ3i ) and we can conclude kXk2F = kW (log Λ)W ∗ k2F = k log Λk2F =
Pd
Pd
2
2
3
2
i=1 | log λi | =
i=1 |µi | + O(µi ) ≤ 2ǫ .
Lemma 6.5. Let A ∈ D(d) be a matrix and U, V ∈ U (d) be unitary matrices. If kU − V kF ≤ ǫ for
sufficiently small ǫ > 0, then kU AU ∗ − V AV ∗ kF ≤ 3ǫ.

Proof. Let U0 = V ∗ U . By a direct calculation, kU − V kF = kU0 − Id kF and kU AU ∗ − V AV ∗ kF =
kU0 AU0∗ − AkF . Therefore, we can assume that V = Id . By Lemma 6.4, there exists X ∈ Skew(d)
such that kXkF ≤ 1 and U = exp(2ǫX). Note that U ∗ = exp(−2ǫX). Then,
U ∗ AU − A = exp(−2ǫX)A exp(2ǫX) − A = (Id − 2ǫX + O(ǫ2 )J)A(Id + 2ǫX + O(ǫ2 )J)
= 2ǫ(AX − XA) + O(ǫ2 )J,

where O(ǫ2 )J denotes a matrix with each entry having absolute value O(ǫ2 ). We evaluate the
Frobenius norm of the commutator as
kAX − XAkF ≤ kAXkF + kXAkF = 2kXkF ≤ 2,
where we use the triangle inequality of the Frobenius norm, and the assumption kAkF ≤ 1. Therefore,
kU AU ∗ − Ak2F ≤ 4ǫ2 kAX − XAk2F + O(ǫ3 ) ≤ 8ǫ2 + O(ǫ3 ) < 9ǫ2 .
Now, we prove Theorem 6.1.
Proof of Theorem 6.1. We assume that the all the estimations have succeeded, which happens with
probability at least 5/6 by the union bound.
Suppose that f and g are unitary equivalent and U0 ∈ U (d) be the unitary matrix with f (x) =
U0 g(x)U0∗ for any x ∈ G. From Lemma 6.3, we sample U such that kU0 − U kF ≤ ǫ/10 with
probability at least 5/6. From Lemma 6.5, we have Ex∈G [kf (x) − U g(x)U ∗ k2F ] ≤ 9ǫ2 /100. For such
U , we obtain the estimation e satisfies e < ǫ2 /10. By the union bound, we accept with probability
at least 2/3.
Suppose that f and g are ǫ-far from being unitary equivalent. For every U we sample, we have
Ex∈G [kf (x) − U g(x)U ∗ k2F ] ≥ 4ǫ2 . Hence, the estimation e satisfies e > ǫ2 /10 and we accept. To
summarize, we reject with probability at least 5/6 > 2/3.

Acknowledgements
We thank Mitsuru Kusumoto and anonymous referees for comments that greatly improved the
manuscript.

17

References
[1] E. Allender, J. Jiao, M. Mahajan, and V. Vinay. Non-commutative arithmetic circuits: depth
reduction and size lower bounds. Theoretical Computer Science, 209(1-2):47–86, 1998.
[2] N. Alon and S. Lovett. Almost k-wise vs. k-wise independent permutations, and uniformity
for general group actions. Theory of Computing, 9(1):559–577, 2013.
[3] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness
of approximation problems. Journal of the ACM, 45(3):501–555, 1998.
[4] M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi, and M. Sudan. Linearity testing in characteristic two. IEEE Transactions on Information Theory, 42(6):1781–1795, 1996.
[5] M. Ben-Or, D. Coppersmith, M. Luby, and R. Rubinfeld. Non-abelian homomorphism testing,
and distributions close to their self-convolutions. Random Structures & Algorithms, 32(1):49–
70, 2007.
[6] E. Ben-Sasson, M. Sudan, S. Vadhan, and A. Wigderson. Randomness-efficient low degree tests
and short PCPs via epsilon-biased sets. In Proceedings of the 35th annual ACM symposium
on Theory of computing (STOC), pages 612–621, 2003.
[7] P. Berman, S. Raskhodnikova, and G. Yaroslavtsev. Lp -testing. In Proceedings of the 46th
Annual ACM Symposium on Theory of Computing (STOC), pages 164–173, 2014.
[8] A. Bhattacharyya. Guest column: on testing affine-invariant properties over finite fields. ACM
SIGACT News, 44(4):53–72, 2013.
[9] A. Bhattacharyya, E. Fischer, H. Hatami, P. Hatami, and S. Lovett. Every locally characterized
affine-invariant property is testable. In Proceedings of the 45th Annual ACM Symposium on
Theory of Computing (STOC), pages 429–436, 2013.
[10] A. Bhattacharyya, E. Fischer, and S. Lovett. Testing low complexity affine-invariant properties.
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
1337–1355, 2012.
[11] A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, and D. Zuckerman. Optimal testing of Reed-Muller codes. In Proceedings of the 51st Annual IEEE Symposium on Foundations
of Computer Science (FOCS), pages 488–497, 2010.
[12] P. Biane. Characters of symmetric groups and free cumulants. Asymptotic Combinatorics with
Applications to Mathematical Physics, 1815:185–200, 2003.
[13] E. Blais, A. Weinstein, and Y. Yoshida. Partially symmetric functions are efficiently
isomorphism-testable. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of
Computer Science (FOCS), pages 551–560, 2012.
[14] M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical
problems. Journal of Computer and System Sciences, 47(3):549–595, 1993.

18

[15] T. Bröcker and T. Dieck. Representations of Compact Lie Groups. Graduate Texts in Mathematics. Springer, 1985.
[16] B. Green. A Szemerédi-type regularity lemma in abelian groups, with applications. Geometric
and Functional Analysis, 15(2):340–376, 2005.
[17] H. Hatami and S. Lovett. Estimating the distance from testable affine-invariant properties.
In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science
(FOCS), pages 237–242, 2013.
[18] J. Huang, C. Guestrin, and L. Guibas. Fourier theoretic probabilistic inference over permutations. The Journal of Machine Learning Research, 10:997–1070, 2009.
[19] M. Kassabov. Symmetric groups and expander graphs. Inventiones Mathematicae, 170(2):327–
354, 2007.
[20] T. Kaufman and M. Sudan. Algebraic property testing: the role of invariance. In Proceedings
of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 403–412, 2008.
[21] S. V. Kerov. Talk at IHP conference. 2000.
[22] A. Kirillov. Introduction to Lie groups and Lie algebras. Cambridge University Press, 2008.
[23] R. O’Donnell and J. Wright. Quantum spectrum testing. In Proceedings of the 47th ACM
Symposium on Theory of Computing (STOC), 2015.
[24] R. Raz and B. Spieker. On the “log rank”-conjecture in communication complexity. Combinatorica, 15(4):567–588, 1995.
[25] D. Ron. Algorithmic and analysis techniques in property testing. Foundations and Trends R
in Theoretical Computer Science, 5(2):73–205, 2009.
[26] R. Rubinfeld. On the robustness of functional equations. SIAM Journal on Computing,
28(6):1972–1997, 2006.
[27] R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to
program testing. SIAM Journal on Computing, 25(2):252–271, 1996.
[28] A. Shpilka and A. Wigderson. Derandomizing homomorphism testing in general groups. SIAM
Journal on Computing, 36(4):1215–1230, 2006.
[29] R. P. Stanley. Irreducible symmetric group characters of rectangular shape.
Lotharingien de Combinatoire, 50, 2003.

Séminaire

[30] B. Steinberg. Representation Theory of Finite Groups: An Introductory Approach. Springer,
2011.
[31] H. Weyl. Quantenmechanik und gruppentheorie. Zeitschrift für Physik, 46(1-2):1–46, 1927.
[32] K. Wimmer. Agnostically learning under permutation invariant distributions. In Proceedings
of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages
113–122, 2010.
19

[33] Y. Yoshida. A characterization of locally testable affine-invariant properties via decomposition theorems. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing
(STOC), pages 154–163, 2014.

20

