Invariant Polynomials under Rotations Consider a real polynomial $P(x, y)$ in two variables. It is called invariant with respect to the rotation by an angle $\alpha$ if
$$
P (x \cos(\alpha) − y \sin(\alpha), x \sin(\alpha) + y \cos(\alpha)) = P (x, y)
$$
for all real $x$ and $y$. 
How do we find the dimension of the real vector space formed by all polynomials in 
two variables of total degree not greater than $d$ invariant with respect to the 
rotation by $2\pi/n$? 
 A: First fix an $n \geq 0$, and define the rotation map
$$ R: \mathbb{R}^2 \to \mathbb{R}^2, \quad R = \begin{pmatrix} \cos(2 \pi / n) & -\sin(2 \pi / n) \\ \sin(2 \pi / n) & \cos(2 \pi / n) \end{pmatrix}$$
Now, denote the space of all two-variable real polynomials by $\mathbb{R}[x, y]$, and thinking of a polynomial $P \in \mathbb{R}[x, y]$ as a function $P: \mathbb{R}^2 \to \mathbb{R}$, define a linear map $L$ to be precomposition with the rotation $R$:
$$ L: \mathbb{R}[x, y] \to \mathbb{R}[x, y], \quad LP = P \circ R$$
An invariant polynomial $Q$ is precisely one satisfying $LQ = Q$, i.e. an eigenvector of $L$ with eigenvalue $1$. So the question is essentially to examine the $1$-eigenspace of $L$.
Now, let $\mathbb{R}[x, y]_d$ denote the subspace of all homogeneous degree-$d$ polynomials, for example $\mathbb{R}[x, y]_3 = \operatorname{span}\{x^3, x^2y, xy^2, y^3\}$. As noticed in the comments, we have $L(\mathbb{R}[x, y]_d) \subseteq \mathbb{R}[x, y]_d$, meaning that we can examine what $L$ does on each degree-$d$ subspace individually. Denote this restricted operator by $L_d: \mathbb{R}[x, y]_d \to \mathbb{R}[x, y]_d$.
What are the eigenvalues of $L_d$? If $\lambda, \mu$ denote the two eigenvalues of $R$, then the eigenvalues of $L_d$ must be precisely $\lambda^d, \lambda^{d-1} \mu, \ldots, \lambda \mu^{d-1}, \mu^d$. (Short justification: if we go up to the complex numbers, $R$ diagonalises, with some eigenvectors $u$, $v$ corresponding to $
\lambda$ and $\mu$. After changing coordinates from $(x, y)$ to $(u, v)$, we have $L$ acting by $L(u^a v^b) = \lambda^a \mu^b u^a v^b$, and so on). Of course, we know exactly what the eigenvalues of $R$ are: they are $\omega$ and $\omega^{-1}$, where $\omega = \exp(2 \pi i / n)$ is a primitive $n$th root of unity. Hence the eigenvalues of $L_d$ are $\omega^{-d}, \omega^{-d+2}, \ldots, \omega^{d-2}, \omega^d$. Then dimension of the $1$-eigenspace of $L_d$ is the number of these eigenvalues which are equal to $1$, and $\omega^i = 1$ precisely when $n$ divides $i$.
So finally, to answer the original question, what is the dimension of the subspace of polynomials of degree at most $d$ which are invariant under $L$? We tabulate the eigenvalues of the operators $L_0, L_1, \ldots, L_d$, where the first row is the eigenvalue of $L_0$, the second are the eigenvalues of $L_1$, and so on:
$$ \begin{matrix}
&&&&&\omega^0&&&&& \\
&&&&\omega^{-1}&&\omega^1&&&& \\
&&&\omega^{-2}&&\omega^0&&\omega^2&&& \\
&&\omega^{-3}&&\omega^{-1}&&\omega^1&&\omega^{3}&& \\
&\omega^{-4}&&\omega^{-2}&&\omega^0&&\omega^2&&\omega^4& \\
\omega^{-5}&&\omega^{-3}&&\omega^{-1}&&\omega^1&&\omega^{3}&&\omega^5 \\
\end{matrix}$$
So for $n = 3$ and $d \leq 5$, the answer will be the number of $\omega^i$ in the above table where $3$ divides $i$. There are 7 of them: $\omega^0$ for $L_0, L_2, L_4$, then the $\omega^3$ and $\omega^{-3}$ for both $L_3$ and $L_5$.

It's also interesting to point out some of the actual invariant functions in the table. The $L_0$ entry always refers to a constant function. After that the middle column could be identified with the functions $x^2 + y^2, x^4 + 2x^2 y^2 + y^4$ and so on, which are all rotationally symmetric since they are powers of the length function $\sqrt{x^2 + y^2}$. The $\omega^3, \omega^{-3}$ functions in the $L_3$ row could mean the third-of-a-turn symmetric functions $x^3 + 3xy^2$ and $-3y^2 x + y^3$.

Addressing some questions from the comments:
It is enough to check only the algebraic multiplicities of the eigenvalues of $L_d$. This is because $L_d$ is a linear transformation of a finite-dimensional vector space of finite order ($L_d^n = 1$), and so it must be a semisimple operator. (The minimal polynomial of $L_d$ must divide $x^n - 1$, but $x^n - 1$ splits into distinct linear and quadratic factors over the real numbers, hence the minimal polynomial is $x^n - 1$.) Semisimple operators always have geometric and algebraic multiplicities matching up. Equivalently, if you prefer complex matrices, when we change up to the complex numbers then $L_d$ is diagonalisable.
Secondly, how do you find the invariant functions? Lets follow through the change of coordinates I alluded to but never worked out. Let's back up a bit: we have a rotation matrix
$$ R = \begin{pmatrix} \cos(2 \pi / n) & -\sin(2 \pi / n) \\ \sin(2 \pi / n) & \cos(2 \pi / n) \end{pmatrix}$$
acting on functions $x = \begin{pmatrix} 1 & 0\end{pmatrix}$ and $y = \begin{pmatrix} 0 & 1\end{pmatrix}$. We can see that
$$ \begin{pmatrix} 1 & i \end{pmatrix} R = \begin{pmatrix} \omega & i\omega \end{pmatrix}, \quad  \begin{pmatrix} 1 & -i \end{pmatrix} R = \begin{pmatrix} \omega^{-1} & i\omega^{-1} \end{pmatrix}$$
and hence $u = \begin{pmatrix} 1 & i \end{pmatrix} = x + iy$ and $v = \begin{pmatrix} 1 & -i \end{pmatrix} = x-iy$ are complex eigenvectors of $R$ with eigenvalues $\omega$ and $\omega^{-1}$.
Finding which of the monomials $u^a v^b$ are invariant is easy, since $L(u^a v^b) = \omega^{a - b} u^a v^b$, and so we only need $a - b$ to be divisible by $n$. Continuing the $n = 3$ example, this will be the two monomials $u^3, v^3$. We can't immediately just expand $u^3$ and $v^3$ in terms of $(x+iy)^3$ and $(x - iy)^3$, since this would have imaginary numbers hanging around. Instead, since $u$ and $v$ are kind of like complex conjugates, we can "take a real part"
$$ \frac{u^3 + v^3}{2} = \frac{(x + iy)^3 + (x - iy)^3}{2} = x^3 - x y^2$$
and "take an imaginary part"
$$ \frac{u^3 - v^3}{2i} = \frac{(x + iy)^3 - (x - iy)^3}{2i} = 3x^2 y - y^3$$
to recover the two linearly independent real symmetric polynomials.
A: It helps to briefly step into complex space, where rotation by $2\pi/n$ corresponds to multiplication by $\omega=e^{i2\pi/n}$. Let $z=x+iy$, with conjugate $\newcommand{\z}{{\overline z}}\z=x-iy$. We can write $P(x,y)$ as a polynomial in $z,\z$, call it $Q(z,\z)$. Then $Q(\omega z,\omega^{-1}\z)$ corresponds to the rotation of $P$ by $2\pi/n$. If we write
$$
Q(z,\z)=\sum_{i,j\ge 0,i+j\le n}a_{i,j}\;z^i\,\z^j,
$$
then the rotation is given by
$$
Q(\omega \,z, \omega^{-1}\,\z)=\sum_{i,j\ge 0,i+j\le n}a_{i,j}\omega^{i-j}\;z^i\,\z^j,
$$
It is now clear that in order for these two expressions to be equal, we need to have $a_{i,j}=0$ whenever $i-j$ is not a multiple of $n$. One the other hand, the monomials of the form 
$$
z^m\; \z^{\;(m-kn)}
$$
are rotation invariant, and a basis for rotation invariant polynomials. For example, we can always have $k=0$, in which case the polynomial is $z^m \z^{m}=(x^2+y^2)^m$. For nonzero $k$, these will in general be complex polynomials, and we want real ones. This is fixed by pairing up the monomials in conjugate pairs, and either averaging to cancel the imaginary parts, or canceling the real parts and dividing by $i$. The result is that the basis polynomials are all of the form
$$
(x^2+y^2)^m\cdot \frac{(x+iy)^{kd}+(x-iy)^{kd}}{2},\quad m,k\ge 0,2m+kn\le d\qquad\\
(x^2+y^2)^m\cdot \frac{(x+iy)^{kd}-(x-iy)^{kd}}{2i},\quad m\ge 0,k\ge 1,2m+kn\le d.
$$
These appear to be complex polynomials in $x$ and $y$, but all complex numbers cancel out. You can find the dimensions by counting the number of integral values of $m$ and $k$ which satisfy the inequalities. You can probably get some messy closed form involving floor functions.
