The Construction of G-Invariant Finite Tight Frames

Abstract

We give a complete classification of the finite tight frames which are G-invariant, i.e., invariant under the unitary action of a group G. This result is constructive, and we use it to consider a number of examples. In particular, we determine the minimum number of generators for a tight frame for the orthogonal polynomials on an n-gon or cube, which is invariant under the symmetries of the weight.

1 Introduction

A finite sequence of vectors $(f_j)_{j\in J}$ is a tight frame for a d-dimensional Hilbert space $\mathcal{H}$ if it gives the “redundant orthogonal expansion”

$$\begin{aligned} f = {1\over A}\sum _{j\in J} \langle f,f_j\rangle f_j, \qquad \forall f\in \mathcal{H}, \end{aligned}$$

(1.1)

where $A={1\over d}\sum _{j\in J}\Vert f_j\Vert ^2$. Tight frames (for finite dimensional spaces) have been studied extensively over the last decade (cf. [4, 8, 22]). Many applications, such as signal analysis [6] and quantum measurements [14], use tight frames which are the orbit of a single vector under the unitary action of a finite group G. These so-called G-frames [21] include the harmonic frames (abelian groups) [7], and SIC-POVMs (discrete Heisenberg group) [15].

Here, we consider finite tight frames which are the G-orbit of one or more vectors, equivalently, G-invariant frames. By way of motivation, we first outline the case of the orbit of a single nonzero vector, which was studied extensively in [19]. If the unitary action of a finite group G on $\mathcal{H}$ is irreducible, i.e., every G-orbit of a nonzero vector is a spanning set, then every such orbit is a tight frame (see Lemma 2.3). If the action is not irreducible, then there are two cases:

• 1. No G-orbit spans $\mathcal{H}$, and hence there are no tight G-frames for $\mathcal{H}$.

• 2. Some G-orbit spans $\mathcal{H}$, in which case there is a tight G-frame for $\mathcal{H}$.

In the first case (or the second for that matter) one might seek a G-orbit of more than one vector which is a spanning set, and then find a tight frame. Of course this can always be done: take a basis and then the canonical tight frame of its G-orbit.

We give a more precise answer. Namely, a complete characterisation of when the G-orbit of vectors $w_1,\ldots ,w_r$ is a tight frame for $\mathcal{H}$. This is first given for a complex space which is easily stated, and then the real case is considered separately. This very general result is constructive, and contains many known results as special cases, e.g., harmonic frames (one generator, and G abelian). From it, one can determine the minimal number of generators for a G-invariant tight frame. We do this calculation for the spaces of orthogonal polynomials of fixed degree on an n-gon and on a cube. Another application considered is the construction of G-invariant fusion frames.

2 The Characterisation of G-Invariant Frames

Our results involve the representation theory of finite groups (cf. [11]). Throughout, G is a finite group. Denote the general linear group of invertible linear transformations on V by $\mathcal{GL}(V)$. A representation or linear action of G on a vector space V over a field $\mathbb {F}$ is a map $\rho :G\rightarrow \mathcal{GL}(V)$, which is an action, i.e.,

$$\begin{aligned} g(h v)=(gh)v, \quad 1 v=v, \qquad gv:=\rho (g)v. \end{aligned}$$

We say V is a representation of G, or an $\mathbb {F}G$-module, or just a G-module if the field $\mathbb {F}$ and action of G is clear from the context. The reason for this name is that an $\mathbb {F}G$-module is a module over the group algebra $\mathbb {F}G$, which is the $\mathbb {F}$-vector space with a basis given by the elements of G and multiplication given by extending the multiplication of G linearly.

When $\mathbb {F}= \mathbb {R}$ or $\mathbb {C}$, a representation is said to be unitary (or a unitary action) if V is a Hilbert space, and each $\rho (g)$, $g\in G$, is unitary. If an action is not unitary, then the inner product can be changed so that it is (see [2]). Hence, for simplicity, we usually suppose that our actions are unitary.

A subset of V is said to be G-invariant if it is closed under the action of G. We call a finite spanning set for a Hilbert space a frame.

Definition 2.1

The number of generators of a G-invariant frame is the number of orbits under the action of G on the set of its vectors.

Example 2.2

A frame given by the G-orbit of a single nonzero vector, i.e., $(gv)_{g\in G}$, is called a G -frame or group frame. (cf. [10, 20]). Clearly, a G-frame is a G-invariant frame with one generator. Conversely, every one generator G-invariant frame is a G-frame repeated a fixed number of times.

More generally, every G-invariant (tight) frame with r generators can be viewed as a union of the G-orbits of r vectors. For example, if $G=C_2=\langle g\rangle$ acts on $\mathbb {R}^2$ via $ge_1=e_2$, $ge_2=e_1$, $ge_3=e_3$ then $\Phi =(e_1,e_2,e_3)$ is a G-invariant tight frame with two generators $e_1$ and $e_3$. The corresponding tight frame which is a union of G-orbits is

$$\begin{aligned} \left( \begin{pmatrix}1\\ 0\\ 0\end{pmatrix},\begin{pmatrix}0\\ 1\\ 0\end{pmatrix}, \begin{pmatrix}0\\ 0\\ {1\over \sqrt{2}}\end{pmatrix}, \begin{pmatrix}0\\ 0\\ {1\over \sqrt{2}}\end{pmatrix} \right) . \end{aligned}$$

Here the generator $e_3$ (which is fixed by G) is scaled to maintain the tightness of the frame.

A representation V of G is said to be irreducible if every G-orbit of a nonzero vector is a spanning set for V. In this case, we have (cf. [18])

Lemma 2.3

(Irreducible G-frames). Suppose that a unitary action of a finite group G on a Hilbert space $\mathcal{H}$ is irreducible. Then $(gv)_{g\in G}$ is a tight G-frame for $\mathcal{H}$ for any $v\ne 0$, i.e.,

$$\begin{aligned} f = {\dim (\mathcal{H})\over |G|} {1\over \Vert v\Vert ^2} \sum _{g\in G}\langle f,gv\rangle gv, \qquad \forall f\in \mathcal{H}. \end{aligned}$$

When the action is not irreducible, or there is more than one generator, we need the theory for decomposing a space into its G-invariant subspaces. This is often presented in the language of $\mathbb {F}G$-modules

Definition 2.4

Suppose V and W are $\mathbb {F}G$-modules. Then a linear map $\sigma :V\rightarrow W$ is an $\mathbb {F}G$ -homomorphism if it commutes with the action of G, i.e.,

$$\begin{aligned} \sigma g = g\sigma , \qquad \forall g\in G. \end{aligned}$$

An $\mathbb {F}G$-homomorphism is also often called a G -morphism, a G -map or a G -equivariant map, where the field $\mathbb {F}$ is understood from the context.

A bijective $\mathbb {F}G$-homomorphism is called an $\mathbb {F}G$ -isomorphism. We say V and W are isomorphic, written $V\cong W$, if there exists an $\mathbb {F}G$-isomorphism $\sigma :V \rightarrow W$. Usually, we only consider $\mathbb {F}G$-modules up to isomorphism.

If $\mathbb {F}$ is a field of characteristic zero, e.g., $\mathbb {R}$ or $\mathbb {C}$, then Maschke’s Theorem (cf. [11]) says that every submodule of an $\mathbb {F}G$-module has a complement. That is, if $V \subset W$ is an inclusion of $\mathbb {F}G$-modules then there exists $V' \subset W$ with $W = V \oplus V'$ (algebraic direct sum). This implies that a $\mathbb {F}G$-module V is (isomorphic to) a quotient of W if and only if V is (isomorphic to) a submodule of W. It also implies that any finite-dimensional $\mathbb {F}G$-module V can be decomposed into a direct sum of irreducible $\mathbb {F}G$-modules, and the summands are unique up to isomorphism.

Lemma 2.5

(Decomposition) Let G be a finite group, and V be an $\mathbb {F}G$-module over a field $\mathbb {F}$ of characteristic zero. Then G can be written as a direct sum

$$\begin{aligned} V = V_1 \oplus V_2 \oplus \cdots \oplus V_m, \end{aligned}$$

(2.2)

where each $V_j$ is an irreducible $\mathbb {F}G$-module, and the $V_j$ are unique up to $\mathbb {F}G$-isomorphism and reordering. Furthermore, if $V=\mathcal{H}$ is a Hilbert space and the action of G on $\mathcal{H}$ is unitary, then (2.2) can be taken to be an orthogonal direct sum.

Proof

The algebraic complement of Maschke’s theorem can be taken to be an orthogonal complement (see [19] for details). $\square$

We also need the following lemma.

Lemma 2.6

Suppose that there is a unitary action of G on $\mathcal{H}$. If $V_j$ and $V_k$ are irreducible G-invariant subspaces of $\mathcal{H}$, which are not $\mathbb {F}G$-isomorphic, then for $v_j\in V_j$, $v_k\in V_k$, we have

$$\begin{aligned} \sum _{g\in G}\langle f_j,gv_j\rangle gv_k=0, \qquad \forall f_j\in V_j. \end{aligned}$$

(2.3)

Proof

The map $A:V_j\rightarrow V_k$ given by

$$\begin{aligned} A f_j : = \sum _{g\in G}\langle f_j,gv_j\rangle gv_k \end{aligned}$$

is an $\mathbb {F}G$-homomorphism, by the calculation

$$\begin{aligned} h (Af_j) = h\sum _{g\in G}\langle f_j,gv_j\rangle gv_k = \sum _{g\in G}\langle hf_j,hgv_j\rangle hgv_k = A(hf_j). \end{aligned}$$

In particular, its image $A(V_j)$ is a G-invariant subspace of $V_k$. Since $V_k$ is irreducible, this subspace must be either 0 or $V_k$. If $A(V_j) = V_k$ then A is an $\mathbb {F}G$-isomorphism because $\mathrm{ker}(A)$ is a proper G-invariant subspace of $V_j$ and so $\mathrm{ker}(A)=0$. Since $V_j$ and $V_k$ are not isomorphic, $A(V_j)$ must be 0, i.e., (2.3) holds. $\square$

An irreducible representation V of a finite group G over $\mathbb {F}= \mathbb {R}$ is said to be absolutely irreducible if its complexification $V^\mathbb {C}=\mathbb {C}\otimes V$ is an irreducible $\mathbb {C}G$-module. An irreducible representation over $\mathbb {F}=\mathbb {C}$ is also said to be absolutely irreducible.

We recall Schur’s lemma (cf. [11]).

Lemma 2.7

(Schur) Let $\mathbb {F}= \mathbb {C}$. Suppose that $V_j$ and $V_k$ are irreducible G-modules, which are $\mathbb {F}G$-isomorphic via $\sigma :V_j\rightarrow V_k$. If $S:V_j\rightarrow V_k$ is an $\mathbb {F}G$-homomorphism, then $S=c\sigma$ for some $c\in \mathbb {C}$.

We now prove the main result: a characterisation of which G-orbits of vectors $w_1,\ldots ,w_r$ give tight frames.

Theorem 2.8

(Characterisation) Let $\mathcal{H}$ be a Hilbert space over $\mathbb {F}=\mathbb {C}$ or $\mathbb {R}$. Suppose that there is a unitary action of a finite group G on $\mathcal{H}$, and

$$\begin{aligned} \mathcal{H}=V_1\oplus V_2\oplus \cdots \oplus V_m, \end{aligned}$$

an orthogonal direct sum of absolutely irreducible G-invariant subspaces. Let $P_j$ be the orthogonal projection of $\mathcal{H}$ onto $V_j$. Then

$$\begin{aligned} \Phi =(gw_s)_{g\in G,1\le s\le r}, \qquad w_1,\ldots ,w_r\in \mathcal{H}, \end{aligned}$$

is a tight G-invariant frame for $\mathcal{H}$ if and only if

$$\begin{aligned} \sum _{s=1}^r \Vert P_j w_s\Vert ^2 \ne 0, \quad \forall j, \qquad { \sum _{s=1}^r \Vert P_j w_s\Vert ^2\over \sum _{s=1}^r \Vert P_k w_s\Vert ^2} = {\dim (V_j)\over \dim (V_k)}, \quad j\ne k, \end{aligned}$$

(2.4)

and when $V_j\ne V_k$ are $\mathbb {F}G$-isomorphic

$$\begin{aligned} \sum _{s=1}^r \langle \sigma P_j w_s,P_kw_s\rangle =0, \end{aligned}$$

(2.5)

where $\sigma :V_j\rightarrow V_k$ is any choice of $\mathbb {F}G$-isomorphism.

Proof

$\Phi$ is a tight frame for $\mathcal{H}$ if and only if there exists a $\lambda >0$ with

$$\begin{aligned} S_\Phi (f)=\sum _s \sum _{g\in G}\langle f,gw_s\rangle gw_s = \lambda f, \qquad \forall f\in \mathcal{H}. \end{aligned}$$

By linearity, it suffices to show this for $f_j\in V_j$, $1\le j\le m$, i.e. to show that there exists $\lambda$ (independent of j) such that,

$$\begin{aligned} \sum _s\sum _{g\in G}\langle f_j,gw_s\rangle g w_s = \sum _s\sum _{g\in G}\sum _{k}\langle f_j,gP_j w_s\rangle g P_k w_s = \lambda f_j, \end{aligned}$$

(2.6)

since $w_s = \sum _k P_k w_s$. By equating the $V_k$ components, (2.6) holds if and only if

$$\begin{aligned} \sum _s\sum _{g\in G}\langle f_j,g P_j w_s\rangle g P_j w_s = \lambda f_j, \qquad \sum _s\sum _{g\in G}\langle f_j,g P_j w_s\rangle g P_k w_s = 0, \quad k\ne j. \end{aligned}$$

(2.7)

By Lemma 2.3, the first part of (2.7) will hold for all $f_j\in V_j$ provided that some $w_s$ has a nonzero $V_j$-component, i.e., $\sum _s \Vert P_jw_s\Vert ^2\ne 0$, with a $\lambda =\lambda _j>0$, which depends on j, given by

$$\begin{aligned} \lambda _j = {|G|\over \dim (V_j)} \sum _s\Vert P_j w_ s\Vert ^2. \end{aligned}$$

This $\lambda _j$ is independent of j if and only if (2.4) holds. By Lemma 2.6, the second part of (2.7) automatically holds if $V_j\ncong V_k$, and so reduces to

$$\begin{aligned} \sum _s\sum _{g\in G}\langle f_j,g P_j w_s\rangle g P_k w_s = 0, \quad \forall f_j\in V_j, \qquad k\ne j, \quad V_j\cong V_k. \end{aligned}$$

(2.8)

We now seek to simplify (2.8) in the case that $V_j$ is absolutely irreducible. Let $\tau :V_j\rightarrow V_k$ be the $\mathbb {F}G$-homomorphism

$$\begin{aligned} \tau f := \sum _s\sum _g \langle f,gP_j w_s\rangle gP_kw_s. \end{aligned}$$

Then for $\sigma :V_j\rightarrow V_k$ an $\mathbb {F}G$-isomorphism, we calculate

$$\begin{aligned} \langle \tau v_j,\sigma v_j\rangle&= \Big \langle \sum _s\sum _g \big \langle v_j,gP_j w_s \big \rangle gP_kw_s,\sigma v_j \Big \rangle \\&= \sum _s\sum _g \big \langle v_j,gP_j w_s \big \rangle \big \langle gP_kw_s,\sigma v_j \big \rangle \\&= \sum _s\sum _g \big \langle g^{-1}v_j,P_j w_s \big \rangle \big \langle P_kw_s,\sigma g^{-1} v_j \big \rangle \\&= \sum _s \Big \langle P_kw_s, \sigma \sum _g \big \langle P_j w_s , g^{-1}v_j \big \rangle g^{-1} v_j \Big \rangle \\&= \sum _s \Big \langle P_kw_s, \sigma {\Vert v_j\Vert ^2|G|\over \dim (V_j)}P_j w_s \Big \rangle , \end{aligned}$$

with the last equality given by Lemma 2.3. Since $V_j$ is absolutely irreducible, Lemma 2.7 implies that $\tau =c\sigma$, for some $c\in \mathbb {F}$ (possibly zero). Substituting $\tau =c\sigma$ into the above gives

$$\begin{aligned} \tau = {|G|\,\Vert v_j\Vert ^2\over \dim (V_j)\Vert \sigma v_j\Vert ^2} \sum _s \big \langle P_kw_s, \sigma P_j w_s \big \rangle \sigma . \end{aligned}$$

Thus (2.8), which is equivalent to $\tau =0$, holds if and only if (2.5) does. $\square$

We conclude this section with some special cases.

2.1 One Generator

The special case $r=1$ gives Theorem 6.18 of [19].

Corollary 2.9

(One generator [19]) Let $\mathcal{H}=V_1\oplus \cdots \oplus V_m$ be an orthogonal direct sum of absolutely irreducible G-invariant subspaces, and $v=\sum _j v_j$, $v_j\in V_j$. Then $(gv)_{g\in G}$, is a tight G-frame for $\mathcal{H}$ if and only if

$$\begin{aligned} v_j \ne 0, \quad \forall j, \qquad { \Vert v_j\Vert ^2\over \Vert v_k\Vert ^2} = {\dim (V_j)\over \dim (V_k)}, \quad j\ne k, \end{aligned}$$

and when $V_j\ne V_k$ are $\mathbb {F}G$-isomorphic via $\sigma :V_j\rightarrow V_k$ that

$$\begin{aligned} \langle \sigma v_j,v_k\rangle =0. \end{aligned}$$

2.2 G is Abelian

We now consider the special case when G is abelian. In this case, all the absolutely irreducible G-invariant subspaces $V_j$ are 1-dimensional, with the action of G given by

$$\begin{aligned} g v = \xi (g) v, \qquad v\in V_j, \end{aligned}$$

where $\xi$ is a (linear) character of G, i.e., a homomorphism $G\rightarrow \mathbb {C}$. The characters of G form a group $\hat{G}$ (under pointwise multiplication) which is isomorphic to G. In particular, there are |G| different characters.

For one generator, it is known that there is a finite number of G-frames for $\mathbb {C}^d$ (up to unitary equivalence), the so-called harmonic frames (cf. [7]). It is therefore natural to ask if this situation extends to two or more generators. We now answer this question.

Corollary 2.10

(Abelian groups) Suppose there is a unitary action of a finite abelian group G on $\mathbb {C}^d$, and, without loss of generality, that the irreducible G-invariant subspaces are $V_j=\mathrm{span}\{e_j\}$, with the action on $V_j$ given by $ge_j=\xi _j(g)e_j$, where $\xi _j:G\rightarrow \mathbb {C}$ is a character of G. Let $w_1, \ldots , w_r \in \mathbb {C}^d$. Then

$$\begin{aligned} \Phi =(gw_s)_{1 \le s \le r, g \in G} \end{aligned}$$

is a tight frame for $\mathbb {C}^d$ if and only if

• (a) The matrix $W=[w_1,\ldots ,w_r]$ has rows of equal norm.

• (b) The rows of W corresponding to the same character are orthogonal.

In particular, there is a G-invariant tight frame for $\mathbb {C}^d$ with r generators if and only if $d\le r|G|$.

Proof

Since ${P_j w_s}=(w_s)_j e_j$, we have

$$\begin{aligned} \sum _s\Vert P_j w_s\Vert ^2 = \sum _s |(w_s)_j|^2 = (\hbox {norm of the { j}th row of { W}})^2, \end{aligned}$$

and so (2.4) reduces to (a). If $V_j$ and $V_k$ are $\mathbb {C}G$-isomorphic, i.e., correspond to the same character, then $\sigma :V_j\rightarrow V_k: e_j\mapsto e_k$ is a $\mathbb {C}G$-isomorphism, since

$$\begin{aligned} \sigma ( g e_j) =\sigma (\xi _j(g)e_j) =\xi _j(g)\sigma (e_j) =\xi _k(g) e_k = g (\sigma e_j). \end{aligned}$$

In this case, $\sigma P_j w_s=\sigma (w_s)_j e_j= e(w_s)_j e_k$, and so (2.5) becomes

$$\begin{aligned} \sum _s \big \langle \sigma P_j w_s,P_kw_s \big \rangle =\sum _s \big \langle (w_s)_je_k,(w_s)_ke_k \big \rangle =\sum _s (w_s)_j\overline{(w_s)_k}=0, \end{aligned}$$

i.e., the j and k rows of W are orthogonal, which is (b). $\square$

Example 2.11

(Harmonic frames) For $r=1$, $W=[v]$, $v\in \mathbb {C}^d$. Thus the conditions (a), (b) become v has entries of equal modulus which correspond to different characters. Since the action of G on $\mathbb {C}^d$ is via diagonal matrices, we can suppose, without loss of generality, that $v=(1,1,\ldots ,1)$, and so $(gv)_{g\in G}=((\xi _j(g)_{j=1}^d)_{g\in G}$, where $\xi _1,\ldots ,\xi _d$ distinct characters. This is the usual construction for harmonic frames, i.e., the d by |G| matrix $[gv]_{g\in G}$ is obtained by taking rows of the character table (Fourier matrix) of G.

Example 2.12

Let $G=\langle a\rangle$ be the cyclic group of order 2. Define a unitary action of G on $\mathbb {C}^3$ by

$$\begin{aligned} a v := \begin{pmatrix}1&{}0&{}0\\ 0&{}1&{}0\\ 0&{}0&{}-1\end{pmatrix} v =\begin{pmatrix}v_1\\ v_2 \\ -v_3\end{pmatrix}. \end{aligned}$$

Here the action on $\mathbb {C}e_1$, $\mathbb {C}e_2$ is the trivial representation, and on $\mathbb {C}e_3$ it is the sign representation. There is no G-frame $(gv)_{g\in G}$ for $\mathbb {C}^3$. However, there are many choices for $w_1,w_2$ so that $(gv_j)_{1\le j \le 2, g\in G}$ is a tight G-invariant frame, e.g.,

$$\begin{aligned} W =[w_1,w_2] = \begin{pmatrix}1&{}0\\ 0&{}1\\ u&{}\sqrt{1-|u|^2}\end{pmatrix}, \qquad |u|\le 1. \end{aligned}$$

Here $\langle w_1,w_2\rangle = u\sqrt{1-|u|^2}$, and so infinitely many unitarily inequivalent G-invariant tight frames for $\mathbb {C}^3$ can be constructed in this way.

Given $w_1=(x,y,z)$, a suitable $w_2$ can be chosen provided $|z|^2\le |x|^2+|y|^2$, since we can take $w_2= (\overline{y}, -\overline{x}, u)$ where $|u|^2=|x|^2+|y|^2-|z|^2$. For example, if $w_1=(1,2,2)$, then $w_2=(2,-1,1)$ gives the G-invariant tight frame

$$\begin{aligned} \{w_1,w_2,aw_1,a w_2\}= \left\{ \begin{pmatrix}1\\ 2\\ 2\end{pmatrix}, \begin{pmatrix}2\\ -1\\ 1\end{pmatrix}, \begin{pmatrix}1\\ 2\\ -2\end{pmatrix}, \begin{pmatrix}2\\ -1\\ -1\end{pmatrix} \right\} . \end{aligned}$$

2.3 Fusion Frames

The tight frame expansion (1.1) can be generalised to

$$\begin{aligned} f = \sum _{j\in J} c_jP_{W_j} f, \qquad \forall f\in \mathcal{H}, \end{aligned}$$

where $c_j\ge 0$ and $P_{W_j}$ is the orthogonal projection onto the subspace $W_j\subset \mathcal{H}$.

Definition 2.13

The nonnegative weights $(c_j)_{j\in J}$ and subspaces $(W_j)_{j\in J}$ of $\mathcal{H}$ are a tight fusion frame for $\mathcal{H}$ if for some $A>0$

$$\begin{aligned} f = {1\over A}\sum _{j\in J} c_jP_{W_j} f, \qquad \forall f\in \mathcal{H}. \end{aligned}$$

Tight frames $(f_j)$ for $\mathcal{H}$ correspond to tight fusion frames with each $W_j$ one-dimensional (or 0) via $c_j=\Vert f_j\Vert ^2$, $W_j=\mathrm{span}\{f_j\}$. At the other extreme, the single subspace $W_1=\mathcal{H}$ gives a tight fusion frame.

Fusion frames have found many applications: coding theory, distributed sensing, neurology, parallel processing, sparse representations (see the short essays at http://www.fusionframe.org and the section on fusion frames at http://www.framerc.org). So far, the main constructions are via the frame potential (see [1, 3]) and spectral tetris [5]. We now show how they can be constructed as group orbits of a collection of subspaces.

Denote the Frobenius inner product on linear maps $\mathcal{H}\rightarrow \mathcal{H}$ by

$$\begin{aligned} \langle A,B\rangle :=\mathrm{trace}(AB^*). \end{aligned}$$

Corollary 2.14

(Fusion frames) Suppose that there is a unitary action of G on $\mathcal{H}$, and $\mathcal{H}=\oplus _j V_j$ an orthogonal direct sum of absolutely irreducible subspaces. Let $P_j$ be the orthogonal projection onto $V_j$, and $W_1,\ldots ,W_r\in \mathcal{H}$ be subspaces. Then $(gW_s)_{g\in G,1\le s\le r}$ with the weights $c_{g,s}=c_s$ is a tight fusion frame for $\mathcal{H}$ if and only if

$$\begin{aligned} \langle P_j, Q \rangle \ne 0, \quad \forall j, \qquad {\langle P_j,Q\rangle \over \langle P_k,Q\rangle } ={\dim (V_j)\over \dim (V_k)}, \quad j\ne k, \end{aligned}$$

(2.9)

where $Q:= \sum _s c_s P_{W_s}$, and when $V_j\ne V_k$ are $\mathbb {F}G$-isomorphic via $\sigma :V_j\rightarrow V_k$

$$\begin{aligned} \langle \sigma P_j,P_k Q\rangle =0. \end{aligned}$$

(2.10)

Proof

Let $(w_\ell ^{(s)})_{\ell =1}^{d_s}$, $d_s:=\dim (W_s)$, be an orthonormal basis for $W_s$. If $g\in G$ then $(gw_\ell ^{(s)})_{\ell =1}^{d_s}$ is an orthonormal basis for $W_s$, and so $(gW_s)_{g\in G,1\le s\le r}$ is a tight fusion frame for $\mathcal{H}$ with weights $c_s$ (not depending on $g\in G$) if and only if

$$\begin{aligned} \sum _{g\in G}\sum _{s=1}^r \sum _{\ell =1}^{d_s} c_s \langle f,gw_\ell ^{(s)}\rangle gw_\ell ^{(s)} = Af, \qquad \forall f\in \mathcal{H}, \end{aligned}$$

i.e., the G-orbit of $(\sqrt{c_s}w_\ell ^{(s)})_{1\le s\le r,1\le \ell \le d_s}$ is a tight frame. By Theorem 2.8, the necessary and sufficient conditions for this are

$$\begin{aligned} \alpha _j:=\sum _{s=1}^r \sum _{\ell =1}^{d_s} c_s\Vert P_j w_\ell ^{(s)}\Vert ^2\ne 0, \quad \forall j, \qquad {\alpha _j\over \alpha _k} = {\dim (V_j)\over \dim (V_k)}, \quad j\ne k, \end{aligned}$$

and when $\sigma :V_j\rightarrow V_k$ is an $\mathbb {F}G$-isomorphism

$$\begin{aligned} \beta _{jk}:=\sum _s\sum _\ell c_s \Big \langle \sigma P_jw_\ell ^{(s)},P_kw_\ell ^{(s)}\Big \rangle =0. \end{aligned}$$

Since $\sum _\ell w_\ell ^{(s)}(w_\ell ^{(s)})^*=P_{W_s}$, these simplify to (2.9) and (2.10), by the calculations

$$\begin{aligned} \alpha _j&= \sum _s\sum _\ell c_s\mathrm{trace}\Big (P_jw_\ell ^{(s)} (w_\ell ^{(s)})^* P_j\Big ) = \sum _s c_s\mathrm{trace}(P_j P_{W_s}) \\&= \sum _s c_s \big \langle P_j,P_{W_s}\big \rangle = \big \langle P_j, Q\big \rangle , \end{aligned}$$

$$\begin{aligned} \beta _{jk}&= \sum _s\sum _\ell c_s\mathrm{trace}\Big (\sigma P_jw_\ell ^{(s)} (w_\ell ^{(s)})^* P_k\Big ) = \sum _s c_s\mathrm{trace}(\sigma P_j P_{W_s} P_k) \\&= \sum _s c_s \big \langle \sigma P_j, P_k P_{W_s}\big \rangle = \big \langle \sigma P_j, P_k Q\big \rangle . \end{aligned}$$

$\square$

We observe that the condition above depends only on $Q=\sum _s c_s P_{W_s}$, a semipositive definite (Hermitian) operator. By considering its spectral structure, such a Q could be decomposed in different ways to obtain various fusion frames, with the minimal number of subspaces being the number of nonzero eigenvalues.

2.4 The Real Case

For $\mathbb {F}=\mathbb {R}$, our characterisation (Theorem 2.8) applies if $\mathcal{H}$ is the orthogonal direct sum of absolutely irreducible G-invariant subspaces. If not, i.e., some irreducible subspace is not absolutely irreducible, then it can be applied to the complexification of $\mathcal{H}$. However, this does not guarantee that the tight frames constructed are real. A careful reading of the proof of Theorem 2.8 gives the following version for $\mathbb {F}=\mathbb {R}$.

Theorem 2.15

(Real case) Suppose that there is a unitary action of a finite group G on real space

$$\begin{aligned} \mathcal{H}=V_1\oplus V_2\oplus \cdots \oplus V_m, \end{aligned}$$

an orthogonal direct sum of irreducible G-invariant subspaces. Let $P_j$ be the orthogonal projection of $\mathcal{H}$ onto $V_j$. Then

$$\begin{aligned} \Phi =(gw_s)_{g\in G,1\le s\le r}, \qquad w_1,\ldots ,w_r\in \mathcal{H}\end{aligned}$$

is a tight G-invariant frame for $\mathcal{H}$ if and only if

$$\begin{aligned} \sum _{s=1}^r \Vert P_j w_s\Vert ^2 \ne 0, \quad \forall j, \qquad { \sum _{s=1}^r \Vert P_j w_s\Vert ^2\over \sum _{s=1}^r \Vert P_k w_s\Vert ^2} = {\dim (V_j)\over \dim (V_k)}, \quad j\ne k, \end{aligned}$$

(2.11)

and when $V_j\ne V_k$ are $\mathbb {R}G$-isomorphic

$$\begin{aligned} \sum _{s=1}^r\sum _{g\in G}\big \langle f_j,gP_jw_s \big \rangle gP_kw_s=0, \qquad \forall f_j\in V_j, \end{aligned}$$

(2.12)

which need only be checked for one $f_j\ne 0$. For $V_j$ absolutely irreducible, (2.12) can be replaced by

$$\begin{aligned} \sum _{s=1}^r \big \langle \sigma P_j w_s,P_kw_s \big \rangle =0, \end{aligned}$$

(2.13)

where $\sigma :V_j\rightarrow V_k$ is any $\mathbb {R}G$-isomorphism.

Example 2.16

Let $G=\langle a\rangle$ be the cyclic group of order n. An irreducible unitary action of G on $\mathbb {R}^2$ is given by

$$\begin{aligned} a v = Av, \qquad A=\begin{pmatrix}c&{}-s\\ s&{}c\end{pmatrix}, \quad c=\cos {2\pi \over n},\quad s=\sin {2\pi \over n}. \end{aligned}$$

Suppose G acts on $\mathbb {R}^4=\mathbb {R}^2\times \mathbb {R}^2$ componentwise, i.e., $a(v,w)=(Av,Aw)$. Then the conditions for the G-orbit of (v, w) to be a tight frame for $\mathbb {R}^4$ are

$$\begin{aligned} \Vert v\Vert =\Vert w\Vert \ne 0, \qquad \sum _{j=1}^n \big \langle f_1,A^jv\big \rangle A^jw= \Bigg (\sum _{j=1}^n A^jwv^*A^{-j} \Bigg ) f_1 =0, \quad \forall f_1\in \mathbb {R}^2. \end{aligned}$$

A calculation shows this is not possible, and so no G-orbit is a tight frame. This can also be seen by appealing to Theorem 2.8, as follows. The action of G on $\mathbb {R}^2$ given by $a v =Av$ is not absolutely irreducible. On the complexification $\mathbb {C}^2$ there are two orthogonal G-invariant subspaces: the eigenspaces of A corresponding to the eigenvalues $\lambda =\omega ,\overline{\omega }$, $\omega :=e^{2\pi i\over n}$. For $n>2$, $\omega \ne \overline{\omega }$, and so these subspaces are not $\mathbb {C}G$-isomorphic. Thus the complexification $\mathbb {C}^4$ of $\mathbb {R}^2\times \mathbb {R}^2$ decomposes as the sum of four 1-dimensional G-invariant subspaces, with two pairs $\mathbb {C}G$-isomorphic to each other. By Theorem 2.8, it is therefore not possible to find a G-frame for $\mathbb {C}^4$, and hence neither for $\mathbb {R}^4$.

Similarly, Corollary 2.14 for fusion frames can be modified for the real case. Here, if $V_j$ is not absolutely irreducible, then (2.10) is replaced by

$$\begin{aligned} \sum _{g\in G} gP_k P_W P_jg^{-1} v_j =0. \end{aligned}$$

(2.14)

3 The Minimal Number of Generators

Suppose that there is a unitary action of a finite group G on a complex Hilbert space $\mathcal{H}$. The following is a simple consequence of Corollary 2.9.

Proposition 3.1

The following are equivalent.

• 1. There exists $v \in \mathcal{H}$ such that $(gv)_{g \in G}$ is a tight frame.

• 2. There exists $v \in \mathcal{H}$ such that $(gv)_{g \in G}$ is a frame (spanning set).

• 3. As a G-module, $\mathcal{H}$ is isomorphic to a submodule of $\mathbb {C}G$.

Wedderburn’s Theorem states that $\mathbb {C}G$ is isomorphic as a G-module to $\bigoplus _W W^{\dim (W)}$, where the sum is over the set of all irreducible representations W of G. Thus, condition 3 above is equivalent to:

• 4. $[\mathcal{H}:W ] \le \dim (W)$ for all irreducible representations W of G.

Here $[\mathcal{H}:W]$ is the number of times the irreducible W appears in a direct sum decomposition of $\mathcal{H}$ into irreducible modules. Note that this condition depends only on the structure of $\mathcal{H}$ as a G-module and is independent of the inner product on $\mathcal{H}$.

We wish to generalise Proposition 3.1 to the case of tight frames with multiple generators. It is convenient to give the following lemma.

Lemma 3.2

There exist $v_1, \ldots , v_k \in \mathcal{H}$ such that $(gv_i)_{1 \le i \le k, g \in G}$ is a tight frame if and only if there exist $v_1, \ldots , v_k \in \mathcal{H}$ such that $(gv_i)_{1 \le i \le k, g \in G}$ spans $\mathcal{H}$.

Proof

This is a standard argument. If $\Phi =(gv_i)_{1 \le i \le k, g \in G}$ spans $\mathcal{H}$ then we can replace $v_i$ by $S_\Phi ^{-1/2}v_i$ where $S_\Phi$ is the frame operator of $\Phi$. $\square$

We denote the direct sum of k copies of a representation V of G by $V^k$. We now show that the minimal number of generators is determined by the G-module structure of $\mathcal{H}$.

Theorem 3.3

(Minimal number of generators) The following are equivalent.

• 1. There exist $v_1, \ldots , v_k \in \mathcal{H}$ such that $(gv_j)_{1 \le j \le k, g \in G}$ is a tight frame.

• 2. There exist $v_1, \ldots , v_k \in \mathcal{H}$ such that $(gv_j)_{1 \le j \le k, g \in G}$ is a frame (spanning set).

• 3. As a G-module, $\mathcal{H}$ is isomorphic to a submodule of $\mathbb {C}G^k$. Equivalently,

  $$\begin{aligned}{}[\mathcal{H}: W] \le k \dim (W), \end{aligned}$$

  for every irreducible G-module W.

Proof

By Lemma 3.2, we need only check that the last two conditions are equivalent.

First, suppose that $(gv_j)_{1 \le j \le k, g \in G}$ spans $\mathcal{H}$. Then $\mathcal{H}$ is a quotient of $\bigoplus _j \mathrm{span}\{gv_j\}$. For each j, $\mathrm{span}\{g v_j\} = \mathbb {C}Gv_j$ is a quotient of $\mathbb {C}G$, and hence is isomorphic to a submodule of $\mathbb {C}G$. Thus, $\mathcal{H}$ is a quotient of $\mathbb {C}G^k$, hence is a submodule of $\mathbb {C}G^k$.

Conversely, suppose that $[\mathcal{H}: W] \le k \dim (W)$, for every irreducible representation W of G. Then we can write $\mathcal{H}= Z_1 \oplus \cdots \oplus Z_k$, where each $Z_j$ contains at most one copy of each irreducible W. Thus, each $Z_j$ is a submodule of $\mathbb {C}G$, so we can find $v_j \in Z_j$ with $(gv_j)_{g \in G}$ a spanning set for $Z_j$, by Proposition 3.1. Therefore, $(gv_j)_{1 \le j \le k, g \in G}$ spans $\mathcal{H}$. $\square$

4 Multivariate Orthogonal Polynomials

Here we use Theorem 3.3 to determine the minimum number of generators for a tight frame for the orthogonal polynomials on the n-gon and on the cube, which is invariant under the symmetries of the weight.

4.1 Generalities

Let V be a finite-dimensional complex vector space. Let $S = \mathbb {C}[V]$ be the ring of polynomial functions on V, and suppose that S is equipped with an inner product $\langle \cdot ,\cdot \rangle$. Suppose further that a finite group G acts on S by unitary transformations which preserve polynomial degree. A typical example is $S= \mathbb {C}[x,y]$ with $\langle \cdot ,\cdot \rangle$ given by

$$\begin{aligned} \langle f,g\rangle := \int _A f\overline{g}\, d\mu \end{aligned}$$

where $\mu$ is the Lebesgue measure on $\mathbb {R}^2$, and $A \subset \mathbb {R}^2$ is some measurable region with $\mu (A) >0$. The inner product $\langle \cdot ,\cdot \rangle$ is to be understood as the sesquilinear extension of

$$\begin{aligned} \langle x^{j_1}y^{k_1},x^{j_2}y^{k_1}\rangle = \int _A x^{j_1+j_2} y^{k_1+k_2}\, d\mu . \end{aligned}$$

We write $S_j$ for the space of homogeneous polynomials of degree j, so that

$$\begin{aligned} S = \bigoplus _{j=0}^\infty S_j \end{aligned}$$

is a graded ring, and let $\Pi _N = \bigoplus _{j=0}^N S_j$ be the polynomials of degree up to N. The space of orthogonal polynomials of degree N is

$$\begin{aligned} Q_N = \Pi _N \cap \Pi _{N-1}^\perp , \end{aligned}$$

where $\perp$ denotes the orthogonal complement.

In [19] the problem of constructing one-generator G-invariant tight frames for $Q_N$, was considered. Since the dimension of $Q_N$ is soon larger than |G| (the size of a G-orbit), these techniques only apply to orthogonal polynomials of small degree. In this section, we use our results to consider the case of several generators. The natural question is:

Question 4.1

What is the minimum number of generators that a G-invariant tight frame for $Q_N$ can have? In other words, what is the smallest k, such that there exist $w_1, \ldots , w_k \in Q_N$ for which $(gw_i)_{g \in G, 1 \le i \le k}$ is a tight frame for $Q_N$?

Note that the map

$$\begin{aligned} S_N \rightarrow Q_N : f \mapsto f-P_{\Pi _{N-1}}(f) = P_{\Pi _{N-1}^\perp \cap \Pi _N}(f) \end{aligned}$$

is an orthogonal projection onto a G-invariant subspace, and so commutes with the action of G. It is also a linear isomorphism. Therefore, $S_N$ and $Q_N$ are isomorphic G-modules, and so Question 4.1 is equivalent to

Question 4.2

What is the minimum number of generators for a G-invariant tight frame for $S_N$?

In order to answer Question 4.2, we need to know the structure of $S_N$ as a G-module. We can then apply Theorem 3.3. In general, it is very hard to decompose $S_N$ into irreducibles. However, for one class of group actions, the complex reflection groups, this problem can be addressed. In the next subsection, we analyse the action of a complex reflection group to get a bound on the number of generators for a tight frame. We then consider the case of the action of the dihedral group on an n-gon in the plane, and calculate the minimum number of generators exactly. Finally, we consider the orthogonal polynomials on the cube.

4.2 Complex Reflection Groups

Let V be a finite-dimensional complex vector space. A linear transformation $s: V \rightarrow V$ is called a complex reflection if s has finite multiplicative order and fixes a hyperplane pointwise [13]. That is, $s = P\mathrm {diag}(\xi , 1,1, \ldots , 1)P^{-1}$ for some invertible P and some root of unity $\xi$. A finite group G generated by complex reflections is called a complex reflection group [13]. Note that being a complex reflection group is a property of the set of matrices G, not the abstract group G. The number $\dim (V)$ is called the rank of the complex reflection group. We will assume that V is an irreducible G-module. A complete classification of the irreducible complex reflection groups was given by Shephard and Todd [17].

One important fact about complex reflection groups is that their invariant theory is well-understood [12] (Chapter 23). The group G acts on the polynomial ring $S=\mathbb {C}[V]$ by

$$\begin{aligned} g \cdot f = f \circ g^{-1}. \end{aligned}$$

This action preserves the degree of a homogeneous f, and so we can ask how the module $S_N$ of homogeneous polynomials of degree N decomposes as a sum of irreducible representations of G.

Let $S^G$ denote the invariant polynomials, that is,

$$\begin{aligned} S^G = \{f \in S: g \cdot f = f, \forall g \in G\}. \end{aligned}$$

Let $S_G^+$ denote the invariant polynomials with zero constant term and let $I_+$ denote the ideal generated by $S_G^+$ in S, that is

$$\begin{aligned} I_+ = \left\{ \sum _{i=1}^k f_i h_i : f_i \in S_G^+, h_i \in S\right\} \subset S. \end{aligned}$$

The ring of coinvariants is the quotient ring

$$\begin{aligned} S_G := \frac{S}{I_+} \end{aligned}$$

and there is a decomposition of S as a tensor product of graded G-modules

$$\begin{aligned} S \cong S^G \otimes _\mathbb {C}S_G. \end{aligned}$$

(4.15)

For readers who are unfamiliar with invariant theory, the following example may help. Let V be one-dimensional and let $G=\{1,g\}$ be a group of order 2 with g acting by $-1$. Then $S=\mathbb {C}[z]$, a polynomial ring in one variable, and $g \cdot z = -z$. The ring of invariants is $S^G=\mathbb {C}[z^2]$ and the ideal $I_+ = z^2\mathbb {C}[z]$ consists of the polynomials of degree $\ge$2. The ring of coinvariants is $S_G = \mathrm {span}\{[1],[z] \}$, a two-dimensional vector space spanned by the images $[1]=1+I_+$ and $[z]=z+I_+$ of 1 and z in the quotient ring $S/I_+$, with the multiplication given by $[z][z] =0$. As a G-module, this can be naturally identified with $\mathrm {span}\{1,z\} \subset S$. We have the tensor product decomposition

$$\begin{aligned} S \cong S^G \otimes _\mathbb {C}\mathrm {span}\{1,z\}, \end{aligned}$$

meaning that for each N, we have

$$\begin{aligned} S_N = \bigoplus _{i=0}^N S^G_i \otimes _\mathbb {C}\mathrm {span}\{1,z\}_{N-i} = S_N^G \otimes \mathrm {span}\{1\} \oplus S_{N-1}^G \otimes \mathrm {span}\{z\} \end{aligned}$$

where the subscript denotes the homogeneous polynomials of degree i. This is just another way of saying that a homogeneous polynomial of degree N can be written as a linear combination of an invariant times z plus another invariant times 1. Since the only homogeneous polynomial of degree N is $z^N$, this is just saying that $z^N= z^N\cdot 1$ if N is even and $z^N = z^{N-1} z$ if N is odd.

Returning to the case of a general complex reflection group G, equation (4.15) describes how $S_N$ decomposes as a sum of irreducible representations of G. From (4.15), we have

$$\begin{aligned} S_N = \bigoplus _{i=0}^N S^G_i \otimes _\mathbb {C}(S_G)_{N-i} \end{aligned}$$

as G-modules. But, by definition, $S_i^G$ consists of $\mathrm {dim}(S_i^G)$ copies of the trivial module. Therefore, if V is an irreducible G-module then

$$\begin{aligned}{}[S_N:V] = \sum _{i=0}^N \mathrm {dim}\big (S_i^G\big ) \big [(S_G)_{N-i}:V\big ]. \end{aligned}$$

The ring $S_G$ is very well-understood. It happens that as G-modules, $S_G \cong \mathbb {C}G$. Therefore, $[S_G : V] = \mathrm {dim}(V)$ for every irreducible G-module V, and so we have

$$\begin{aligned}{}[S_N :V] \le \max _{0 \le i \le N} \mathrm {dim}(S_i^G) \cdot \mathrm {dim}(V). \end{aligned}$$

Applying Theorem 3.3 gives a partial answer to Question 4.2 for a complex reflection group.

Theorem 4.3

Let G be a complex reflection group acting on the irreducible G-module V. Let $S=\mathbb {C}[V]$ and let $S_N \subset S$ denote the space of homogeneous polynomials of degree N. Let c be the minimum number of generators for a tight frame of $S_N$. Then

$$\begin{aligned} c \le \max _{0 \le i \le N} \mathrm {dim}(S_i^G). \end{aligned}$$

The bound in Theorem 4.3 is not sharp in general, see Proposition 4.5 (to follow).

4.3 Orthogonal Polynomials on a Regular Polygon in the Plane

Dunkl [9] considers orthogonal polynomials on the hexagon (to be used for the analysis of optical properties of hexagonal lenses).

Let $n \ge 3$. We consider the regular n-gon $T=T_n$ with vertices $(v_j)$ on the unit circle

$$\begin{aligned} v_j:=\begin{pmatrix}\cos {2\pi \over n} j\\ \sin {2\pi \over n} j\end{pmatrix}, \qquad j\in \mathbb {Z}_n. \end{aligned}$$

These correspond to the n-roots of unity $\omega ^j=e^{2\pi i{j\over n}}$.

Define $\sigma : \mathbb {R}^2 \rightarrow \mathbb {R}^2$ by $\sigma : (x,y) \mapsto (x,-y)$ and define $\rho : \mathbb {R}^2 \rightarrow \mathbb {R}^2$ to be anticlockwise rotation through an angle of $2\pi /n$. Then $\sigma$ and $\rho$ generate a subgroup of $\mathcal{GL}(\mathbb {R}^2)$ of order 2n, called the dihedral group $G=D_{n}$. The group G consists of all the linear transformations which leave the regular n-gon invariant. When considering polynomials on the regular n-gon, it is convenient to complexify the problem and regard G as a subgroup of $\mathcal{GL}(\mathbb {C}^2)$. Let $S=\mathbb {C}[x,y]$ be the ring of polynomial functions on $\mathbb {C}^2$. It is convenient to define

$$\begin{aligned} z&= x+iy, \\ \overline{z}&= x-iy. \end{aligned}$$

Then $S=\mathbb {C}[x,y] = \mathbb {C}[z,\overline{z}]$, and $\sigma$ acts on this ring by $\sigma : z \mapsto \overline{z}$, $\sigma : \overline{z} \mapsto z$ and $\rho$ acts by $\rho : z \mapsto \omega ^{-1}z$, $\rho : \overline{z} \mapsto \omega \overline{z}$. The ring of invariants $S^G$ is generated by $z^n+\overline{z}^n$ and $z\overline{z}$ (called the fundamental invariants of G). It is isomorphic to a polynomial ring in these variables. Therefore, the number $r_i := \mathrm {dim}(S^G_i)$ is the coefficient of $q^i$ in the power series

$$\begin{aligned} \frac{1}{(1-q^2)(1-q^n)} = \sum _{i=0}^\infty r_i q^i, \end{aligned}$$

where q is an indeterminate. We now calculate the numbers $r_i$ in order to apply Theorem 4.3. We observe that

$$\begin{aligned} r_i = \# \Sigma _i, \end{aligned}$$

where

$$\begin{aligned} \Sigma _i = \{(k,\ell ): k, \ell \ge 0, k, \ell \in \mathbb {Z}, 2k + n \ell = i\}. \end{aligned}$$

It is clear that the value of $r_i$ depends on whether n is odd or even, so we must consider these cases separately.

4.3.1 The Case of Odd n

Suppose that n is odd. Then if $2 \not \mid i$, there is a bijection between $S_i$ and $S_{i-n}$ given by $(k,\ell ) \mapsto (k, \ell -1)$, so $r_i = r_{i-n}$.

Similarly, if $n \not \mid i$ then $r_i = r_{i-2}$.

Next, for $t \ge 1$, we have $\Sigma _{2nt} = \Sigma _{2nt-n} \cup \{ (0,2t) \}$, so $r_{2nt}=r_{2nt-n}+1$. But $2 \not \mid 2nt-n$ because n is odd, so $r_{2nt-n}=r_{2nt-2n}.$ By induction on t, we see that

$$\begin{aligned} r_{2nt} = t+1. \end{aligned}$$

Using these facts, the reader may now verify that if $i = 2nt + \ell$ with $0 \le \ell \le 2n-1$ then

$$\begin{aligned} r_i = {\left\{ \begin{array}{ll}t, &{}\ell < n, \ell \text { odd}\\ t+1, &{}\text {otherwise.} \end{array}\right. } \end{aligned}$$

Therefore, if $N = 2nt + \ell$, $0 \le \ell \le 2n-1$ then

$$\begin{aligned} \max _{0 \le i \le N} r_i = t + 1 = \left\lceil \frac{N+1}{2n}\right\rceil . \end{aligned}$$

Therefore, from Theorem 4.3, the minimum number of generators for a G-invariant tight frame of $S_i$ is at most $\lceil \frac{N+1}{2n}\rceil$. But notice that $|G| = 2n$, so the span of a G-orbit can have dimension at most 2n. Also, $\mathrm {dim}(S_i)=N+1$. So the number of generators of a spanning set of $S_i$ must be at least $(N+1)/2n$. Therefore, the minimum number of generators for a tight frame of $S_i$ is exactly $\left\lceil (N+1)/2n \right\rceil$.

4.3.2 The Case of Even n

Suppose that n is even. Then $\Sigma _i = \varnothing$ for i odd, so $r_i=0$ for odd i. For i even, we can do a similar analysis to the odd case. If $n \not \mid i$ then $r_i = r_{i-2}$. Otherwise, $r_{tn} = r_{tn-n}+1$. By induction on t we have $r_{tn}=t+1$. Overall, if $i = tn + \ell$, $0 \le \ell \le n-1$, then

$$\begin{aligned} r_i = {\left\{ \begin{array}{ll} t +1, &{}\ell \text { even}\\ 0, &{}\ell \text { odd.} \end{array}\right. } \end{aligned}$$

So if $N = nt +\ell$, $0 \le \ell \le n-1$, we have

$$\begin{aligned} \max _{0 \le i \le N} r_i = t + 1 = \left\lceil \frac{N+1}{n}\right\rceil . \end{aligned}$$

Therefore, from Theorem 4.3, the minimum number of generators for a G-invariant tight frame of $S_i$ is at most $\lceil \frac{N+1}{n}\rceil$. But notice that $|G| = 2n$ and $-1 =\rho ^{n/2} \in G$. The element $-1$ acts by 1 or $-1$ on $S_i$, so the span of a G-orbit can have dimension at most n. Also, $\mathrm {dim}(S_i)=N+1$. So the number of generators of a spanning set of $S_i$ must be at least $(N+1)/n$. Therefore, the minimum number of generators for a tight frame of $S_i$ is exactly $\lceil (N+1)/n \rceil$.

The above observations can be summarised in the following way.

Theorem 4.4

Let $G=D_{2n}$ be the dihedral group of order 2n acting on $V=\mathbb {C}^2$ and let $S=\mathbb {C}[V]=\bigoplus _{N=0}^\infty S_N$ be the ring of polynomial functions on V. Regardless of the inner product, the minimum number of generators for a G-invariant tight frame of $S_N$ is given by

$$\begin{aligned} \left\lceil \frac{N+1}{2n} \right\rceil \text { if } n \text { is odd, and } \left\lceil \frac{N+1}{n} \right\rceil \text { if } n \text { is even.} \end{aligned}$$

4.4 Example: The Triangle

Let us consider Theorem 4.4 in the simplest case $n=3$. Then $G=D_3$, the symmetry group of a triangle T in the plane with vertices $1, \omega ,\omega ^2$ where $\omega = e^{2 \pi i/3}$. This example was previously considered in [19]. The inner product on $S=\mathbb {C}[z,\overline{z}]$ is given by $\langle f,g \rangle = \int _T f \overline{g}$ where $\int _T h(z)$ is shorthand for $\int _T \mathrm {Re} (h(z))\, d\mu + i \int _T \mathrm {Im} (h(z))\, d\mu$ where $\mu$ is the Lebesgue measure on $\mathbb {R}^2$.

The group $G=D_3$ has three irreducible representations: the trivial representation $\texttt {triv}$, the one-dimensional “sign” representation $\texttt {sgn}$, which is isomorphic to $\mathrm {span} \{ z^3-\overline{z}^3\}$, and a two-dimensional representation V, which is isomorphic to $\mathrm {span}\{z,\overline{z}\}$.

Let us study the action of G on the space of homogeneous polynomials $S_N$ of degree N. For each N, we can decompose $S_N$ into a direct sum of irreducibles by inspection, using the basis $\{ z^i \overline{z}^{N-i} | 0 \le i \le N\}$. We see by inspection that

$$\begin{aligned} S_1&\cong V\\ S_2&\cong \mathrm {span}\{z\overline{z}\}\oplus \mathrm {span}\{z^2,\overline{z}^2\} \cong \texttt {triv} \oplus V\\ S_3&\cong \mathrm {span}\{z^3+\overline{z}^3\}\oplus \mathrm {span}\{z^3-\overline{z}^3\}\oplus \mathrm {span}\{z^2\overline{z}, \overline{z}^2z\}\cong \texttt {triv}\oplus \texttt {sgn}\oplus V\\ S_4&\cong V\oplus V \oplus \texttt {triv}\\ S_5&\cong V \oplus V \oplus \texttt {sgn}\oplus \texttt {triv} \cong \mathbb {C}G\\ S_6&\cong V \oplus V \oplus \texttt {sgn} \oplus \texttt {triv} \oplus \texttt {triv} \end{aligned}$$

The smallest N for which there is an irreducible W with $[S_N:W] > \mathrm {dim}(W)$ is $N=6$. This is in agreement with Theorem 4.4, because the smallest N for which $\left\lceil \frac{N+1}{6}\right\rceil \ge 2$ is $N=6$, and so there exists a G-invariant tight frame for $S_N$ for $N \le 5$. Incidentally, this corrects a false claim in [19].

As an example, let us show how to construct a G-invariant tight frame for $S_6$. Following Dunkl [9], we observe that

$$\begin{aligned} \int _T z^a \overline{z}^b = 0 \end{aligned}$$

if $a \not \equiv b \, \mathrm {mod} \, 3$ because $\rho : z \mapsto \omega ^{-1}z, \overline{z} \mapsto \omega \overline{z}$ leaves the triangle T invariant. Let us write

$$\begin{aligned} \alpha = \int _T z^6\overline{z}^6 = {425\over 28028} \qquad \beta = \int _T z^9 \overline{z}^3 ={137\over 10010} \qquad \gamma = \int _T z^{12} ={1\over 91} \end{aligned}$$

These values are for normalised Lebesgue measure. and note that $\alpha , \beta ,\gamma \in \mathbb {R}$ because T is invariant under $z \mapsto \overline{z}$. We get the following table of inner products among elements of a basis of $S_6$.

	$z^6$	$z^5\overline{z}$	$z^4\overline{z}^2$	$z^3\overline{z}^3$	$z^2\overline{z}^4$	$z\overline{z}^5$	$\overline{z}^6$
$z^6$	$\alpha$	0	0	$\beta$	0	0	$\gamma$
$z^5\overline{z}$	0	$\alpha$	0	0	$\beta$	0	0
$z^4\overline{z}^2$	0	0	$\alpha$	0	0	$\beta$	0
$z^3\overline{z}^3$	$\beta$	0	0	$\alpha$	0	0	$\beta$
$z^2\overline{z}^4$	0	$\beta$	0	0	$\alpha$	0	0
$z\overline{z}^5$	0	0	$\beta$	0	0	$\alpha$	0
$\overline{z}^6$	$\gamma$	0	0	$\beta$	0	0	$\alpha$

Using this, we observe that $z^6-\overline{z}^6$ is orthogonal to all basis elements except $z^6, \overline{z}^6$. Next, $z^6+\overline{z}^6$ is orthogonal to everything except $z^3\overline{z}^3$, and therefore

$$\begin{aligned} z^6+\overline{z}^6-\frac{\langle z^6+\overline{z}^6, z^3\overline{z}^3\rangle }{||z^3\overline{z}^3||^2}z^3\overline{z}^3=z^6+\overline{z}^6-\frac{2\beta }{\alpha } z^3\overline{z}^3 \end{aligned}$$

is orthogonal to all the other basis elements, so that

$$\begin{aligned} S_6= & {} \mathrm {span}\big \{z^6-\overline{z}^6\big \}\oplus \mathrm {span}\big \{z^3\overline{z}^3\big \}\oplus \mathrm {span}\Big \{z^6+\overline{z}^6-\frac{2\beta }{\alpha }z^3\overline{z}^3\Big \}\\&\oplus \, \mathrm {span}\big \{z^4\overline{z}^2, z^2\overline{z}^4, z\overline{z}^5, \overline{z}z^5\big \} \end{aligned}$$

is an orthogonal direct sum. In a similar way, we can decompose $\mathrm {span}\{z^4\overline{z}^2, z^2\overline{z}^4, z\overline{z}^5, \overline{z}z^5\}$ into two orthogonal copies of V, yielding the following decomposition of $S_6$ into an orthogonal direct sum of irreducibles.

$$\begin{aligned} S_6= & {} \mathrm {span}\big \{z^6-\overline{z}^6\big \}\oplus \mathrm {span}\big \{z^3\overline{z}^3\big \}\oplus \mathrm {span}\Big \{z^6+\overline{z}^6-\frac{2\beta }{\alpha }z^3\overline{z}^3\Big \}\\&\oplus \,\mathrm {span}\big \{z^4\overline{z}^2, \overline{z}^4 z^2\big \}\oplus \mathrm {span}\Big \{z^5\overline{z}-\frac{\beta }{\alpha }\overline{z}^4 z^2, \overline{z}^5 z -\frac{\beta }{\alpha } z^4 \overline{z}^2\Big \}. \end{aligned}$$

We can now use Theorem 2.8 to construct a G-invariant tight frame consisting of the orbits of two vectors in $S_6$. For this, we need the norms of the basis elements. We have $||z^6-\overline{z}^6||^2 = 2\alpha - 2\gamma$, $||z^3\overline{z}^3||^2=\alpha$, $||z^6+\overline{z}^6-\frac{2\beta }{\alpha }z^3\overline{z}^3||^2= 2\alpha +2\gamma -\frac{4\beta ^2}{\alpha }$, $||z^4\overline{z}^2||^2=||\overline{z}^4 z^2||^2=\alpha$, and $||z^5\overline{z}- \frac{\beta }{\alpha } \overline{z}^4 z^2||^2 = \alpha -\frac{\beta ^2}{\alpha }$. We can take

$$\begin{aligned} w_1 = \frac{1}{\sqrt{\alpha }}\big (z^3 \overline{z}^3\big ) \end{aligned}$$

and

$$\begin{aligned} w_2= & {} \frac{1}{\sqrt{2\alpha -2\gamma }}\big (z^6 - \overline{z}^6\big )+\frac{1}{\sqrt{2\alpha +2\gamma -4\beta ^2/\alpha }}\Big (z^6+\overline{z}^6-\frac{2\beta }{\alpha }z^3\overline{z}^3\Big )\\&+\frac{\sqrt{2}}{\sqrt{\alpha }}z^4 \overline{z}^2 +\frac{\sqrt{2}}{\sqrt{\alpha -\beta ^2/\alpha }}\Big (z^5 \overline{z}- \frac{\beta }{\alpha } \overline{z}^4 z^2\Big ). \end{aligned}$$

In other words, we just take a unit vector in each irreducible component, with the two-dimensional components having a factor of $\sqrt{2}$. This guarantees that the conditions of Theorem 2.8 are satisfied and we conclude that

$$\begin{aligned} \big (w_1, w_1,w_1,w_1,w_1,w_1,w_2, \rho \cdot w_2 ,\rho ^2\cdot w_2 \sigma \cdot w_2, \rho \sigma \cdot w_2, \sigma \rho \cdot w_2\big ) \end{aligned}$$

is a G-invariant tight frame for $S_6$. We may as well replace the six copies of $w_1$ by a single copy of $\sqrt{6}w_1$. Rescaling, we see that

$$\begin{aligned} \Phi = \left( w_1, \frac{1}{\sqrt{6}}w_2, \frac{1}{\sqrt{6}}\rho \cdot w_2 ,\frac{1}{\sqrt{6}}\rho ^2\cdot w_2, \frac{1}{\sqrt{6}}\sigma \cdot w_2, \frac{1}{\sqrt{6}}\rho \sigma \cdot w_2, \frac{1}{\sqrt{6}}\sigma \rho \cdot w_2\right) \end{aligned}$$

is a G-invariant orthonormal basis for $S_6$. This basis could not be constructed by the methods of [19] because it does not arise as a single orbit of the group G. A basis for the space $Q_6$ of orthogonal polynomials of degree 6 can be constructed by applying the isomorphism $S_6 \rightarrow Q_6$ to $\Phi$. This basis is orthonormal because it is a tight frame (being the image of a tight frame under an orthogonal projection) and has exactly $\mathrm {dim}(Q_6)$ elements.

In general, the question of for which N there exists a G-invariant orthonormal basis for $S_N$ is quite delicate. For example, there is no such basis for $S_7$.

4.5 Orthogonal Polynomials on the Cube

Let us consider a complex reflection group of rank 3 in order to demonstrate that some of the phenomena from the dihedral case do not carry over to the case of a general complex reflection group.

Consider the cube $X = [-1,1]^3 \subset \mathbb {R}^3$ with vertices $(\pm 1,\pm 1, \pm 1)$. The group G of symmetries of the cube consists of those $3 \times 3$ matrices with exactly one entry in each row and column, such that all the nonzero entries are $\pm 1$. An arbitrary element $x \in G$ can be written uniquely as $x =\lambda \sigma$ where $\lambda$ is a diagonal matrix whose entries are $\pm 1$ and $\sigma$ is a permutation matrix. The group G has order $2^3 3!$ and is the Coxeter group of type $B_3$. It is a complex reflection group and is labelled G(2, 1, 3) in the Shepherd-Todd classification. Let $S = \mathbb {C}[x,y,z]$ with the inner product

$$\begin{aligned} \langle f,g \rangle = \int _X f\overline{g} \end{aligned}$$

and let $S_N$ denote the subspace of homogeneous polynomials of degree N. Then $S_N$ is a Hilbert space of dimension $\frac{(N+1)(N+2)}{2}$. We consider the minimal number of generators for a tight frame of $S_N$. Using Theorem 4.3, an upper bound for the minimal number of generators is given by

$$\begin{aligned} \max _{0 \le i \le N} \mathrm {dim}(S^G_i). \end{aligned}$$

As for all complex reflection groups, the ring $S^G$ has been written down explicitly. It is a polynomial ring with generators in degrees 2, 4, 6. Therefore, if $r_i = \mathrm {dim}(S_i^G)$ then

$$\begin{aligned} \sum _{i=0}^\infty r_i q^i = \frac{1}{(1-q^2)(1-q^4)(1-q^6)} \end{aligned}$$

from which we see that $r_k =0$ for k odd. The sequence $\{r_{2k}\}$ is a well-known sequence; it is Sloane’s A001399 [16].

By an explicit computation of the coinvariant ring of G, it is possible to verify the following proposition.

Proposition 4.5

Let $c_N$ be the minimum number of generators for a tight frame of $S_N$. Then

$$\begin{aligned} c_N = {\left\{ \begin{array}{ll} r_N &{}N \text { even}\\ \left\lceil \frac{r_{N-1}+r_{N-3}+r_{N-5}}{3}\right\rceil &{}N \text { odd}. \end{array}\right. } \end{aligned}$$

Proposition 4.5 is interesting because it shows that the upper bound of Theorem 4.3 is not sharp. Indeed, for N odd we have $\max _{0 \le i \le N} \mathrm {dim}(S^G_i) = \max _{0 \le i \le N} r_i = r_{N-1}$. But there exist N for which $r_{N-1} > \left\lceil \frac{r_{N-1}+r_{N-3}+r_{N-5}}{3}\right\rceil$. For example, for $N=7$ the minimal number of generators is $\left\lceil \frac{r_{6}+r_{4}+r_{2}}{3}\right\rceil = 2$ but $r_{N-1}=r_6=3$.

The proof of Proposition 4.5 involves quite a lengthy analysis of the coinvariant ring of G, so we omit it. However, let us explicitly show that the minimal number of generators for a tight frame of $S_7$ is 2, as claimed. This is equivalent to saying that no irreducible X appears more than $2 \dim (X)$ times in $S_7$. This can be verified by writing $S_7$ as a direct sum of irreducible G-modules and counting how many times each occurs.

Let $\{x,y,z\}$ be the dual basis to the standard basis of $\mathbb {R}^3$. We will require the following irreducible representations of G, given for convenience as linear subspaces of $S=\mathbb {C}[x,y,z]$.

$$\begin{aligned} V&= \mathrm{span}\{ x,y,z \} \\ V'&= \mathrm{span}\{ (x^2-y^2)z, (y^2-z^2)x, (z^2-x^2)y \} \\ U&= \mathrm{span}\{ xyz \} \\ W&= \mathrm{span}\{ x^2,y^2,z^2\}/\mathrm{span}\{ x^2+y^2+z^2\} \cong \mathrm{span}\{ x^2-y^2, x^2-z^2 \} \\ W'&= \mathrm{span}\{ x^3yz,xy^3z,xyz^3\}/\mathrm{span}\{ x^3yz+xy^3z+xyz^3\} \\&\cong \mathrm{span}\{ x^3yz-xy^3z, x^3yz-xyz^3 \} \cong U \otimes W \end{aligned}$$

These are irreducible representations of G with $\dim (V)=\dim (V')=3$, $\dim (W)=\dim (W')=2$, and $\dim (U)=1$. Since the monomials $x^iy^jz^k$ form a basis for $S_7$, we see that $S_7$ can be split into the following (non-orthogonal) direct sum of linear subspaces.

$$\begin{aligned} S_7 =&\, \mathrm{span}\big \{ x^7,y^7,z^7 \big \} \oplus \mathrm{span}\big \{ (x^6+y^6)z, (y^6+z^6)x, (z^6+x^6)y\big \} \\&\oplus \mathrm{span}\big \{ (x^6-y^6)z, (y^6-z^6)x, (z^6-x^6)y\big \}\\&\oplus \mathrm{span}\big \{ (x^2+y^2)z^5, (y^2+z^2)x^5, (z^2+x^2)y^5\big \} \\&\oplus \mathrm{span}\big \{ (x^2-y^2)z^5, (y^2-z^2)x^5, (z^2-x^2)y^5\big \}\\&\oplus \mathrm{span}\big \{ (x^4+y^4)z^3, (y^4+z^4)x^3, (z^4+x^4)y^3\big \} \\&\oplus \mathrm{span}\big \{ (x^4-y^4)z^3, (y^4-z^4)x^3, (z^4-x^4)y^3\big \} \oplus xyz \mathrm{span}\big \{ x^4 +y^4 +z^4 \big \} \\&\oplus xyz \mathrm{span}\big \{ x^4-y^4, x^4-z^4\big \} \oplus xyz \mathrm{span}\big \{ (x^2+y^2)xy, (y^2+z^2)yz,\\&\quad (z^2+x^2)zx \big \} \\&\oplus xyz \mathrm{span}\big \{ (x^2-y^2)xy, (y^2-z^2)yz, (z^2-x^2)zx \big \} \oplus x^2y^2z^2 \mathrm{span}\{ x,y,z\} \\&\oplus xyz \mathrm{span}\big \{ x^2y^2+x^2z^2+y^2z^2 \big \} \oplus xyz \mathrm{span}\big \{ x^2y^2-x^2z^2, x^2y^2-y^2z^2 \big \}. \end{aligned}$$

Comparing these with the representations listed above, we see that

$$\begin{aligned} S_7 \cong V\oplus V\oplus V' \oplus V \oplus V' \oplus V \oplus V' \oplus U \oplus W'\oplus V \oplus V' \oplus V \oplus U \oplus W' \end{aligned}$$

from which $[S_7:X]\le 2\dim (X)$ for all irreducibles X, as claimed. Therefore, by Theorem 3.3, the minimal number of generators is 2, regardless of the choice of inner product on $S_7$. This verifies that the bound of Theorem 4.3 is not sharp in general.