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").

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 = \sum_{k=0}^{\phi(n)-1} c_n(k) X^k$ whose coefficients are the sums of fixed power of the primitive $n$-roots, the Ramanujan's sums associated to $n$. 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").

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").

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").

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^l \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").

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").