Let $n$ be a positive integer, and $\zeta_n$ a primitive $n$-root of unity.

I consider the polynomial $P(X) = \sum_{k=0}^{\phi(n)-1} \left[ \sum_{l \in \mathbb{Z}_n^*}^n \zeta_n^{kl} \right]X^k$ whose coefficients are the sums of fixed power of the primitive $n$-roots.
 Notice that a little bit of counting shows that these coefficients are in fact equals to $\mu\left( \frac{n}{gcd(k,n)}\right)\frac{\phi(n)}{\phi\left( \frac{n}{gcd(k,n)}\right)}$, so that the polynomial $P$ is integral.

I want to find an expression of the evaluation of $P$ on the $\phi(n)$-roots of unity, a.k.a. computing its discrete Fourrier coefficients. If no close form is reachable a lower bound on the smallest coefficient would be great too (experimentally it seems to be not too far from 1, so I think a polynomial lower bound might exists )

Something quite clear is that all the DFT coefficients are **positive reals**. Indeed, the DFT evaluation can be obtain as the eigenvalues of the circulant matrix associated to the coefficients of $P$, manipulating a bit shows that one can factorise this matrix as $V.V^\dagger$ where $V$ is the Vandermonde matrix associated to the primitive roots of order $n$. This ensures that the circulant matrix is positive-definite.

Hence, my guess is that the coefficients can be expressed as some (nice?) sums of cosines. I tried to manipulates the sum $P(\zeta_{\phi(n)})$ but nothing fancy really appeared. In the case where $n$ is prime, one can easily shows that everything collapses to obtain $(1, n+1, \cdots, n+1)$ as DFT (corroborating the intuition that the smallest values is "close to 1").