Sum of products of p-th powers of roots of 1 and monomial symmetric functions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T06:10:29Z http://mathoverflow.net/feeds/question/67600 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/67600/sum-of-products-of-p-th-powers-of-roots-of-1-and-monomial-symmetric-functions Sum of products of p-th powers of roots of 1 and monomial symmetric functions Maurizio Monge 2011-06-12T20:16:15Z 2011-06-28T10:08:27Z <p>Hello mathematicians, i'm looking for explicit computations of expressions like <code>$$\sum_{\substack{0\leq i,j,k&lt;n\\i\neq j\neq k \neq i}}\zeta_n^{ip^{k_1}+jp^{k_2}+kp^{k_3}}$$</code> and its generalizations, where $p$ is a prime, $n$ an integer (not assumed prime with $p$) and $\zeta_n$ is a primitive $n$-th root of the unity, and the sum is over all distinct $i,j,k$ from $0$ to $n-1$. <strike>The above expression is also, up to a factor, equal to the <a href="http://en.wikipedia.org/wiki/Schur_polynomial" rel="nofollow">Schur polynomial</a> $s_\lambda$ (of algebraic combinatoric fame) with partition <code>$\lambda=(p^{k_1},p^{k_2},p^{k_3})$</code> evaluated in <code>$1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{n-1}$</code>.</strike>(this is not true, but as was pointed out by Emmanuel the above sum is rather a <a href="http://en.wikipedia.org/wiki/Symmetric_polynomial#Monomial_symmetric_polynomials" rel="nofollow">monomial symmetric function</a> $m_\lambda$)</p> <p>While i just need the expression for small sums (up to $3$ or $4$ terms) which can also be easily worked out by hand (writing the sum without the condition $i\neq j\neq k\neq i$ and using inclusion-exclusion on the set of indices such that $i=j$, $i=k$, etc), i'm almost sure that this computation has been done before and that it i may just refer to some (more or less) well known result. Thanks for your attention!</p> http://mathoverflow.net/questions/67600/sum-of-products-of-p-th-powers-of-roots-of-1-and-monomial-symmetric-functions/67607#67607 Answer by Emmanuel Briand for Sum of products of p-th powers of roots of 1 and monomial symmetric functions Emmanuel Briand 2011-06-12T21:41:59Z 2011-06-28T10:08:27Z <p>The evaluation of the Schur function $s_{\lambda}$ at the $n$th-roots of unity is the coefficient of $s_{\lambda}$ in the expansion in the Schur basis of the plethysm $h_k[p_n]=p_n[h_k]$ of the complete sum $h_k$ with the power sum $p_n$, when $k\cdot n=|\lambda|$ (and $0$ if $|\lambda|$ is not a multiple of $n$).</p> <p>Indeed, consider the Cauchy identity, $$\prod_{i,j} \frac{1}{1-x_i y_j}=\sum_{\lambda} s_{\lambda}[X] s_{\lambda}[Y].$$ Take for the $x_i$ the $n$th-roots of unity $\zeta_i$. Therefore the evaluation of $s_{\lambda}$ that you are looking for will be the coefficient of $s_{\lambda}[Y]$ in the expansion in the Schur basis of $$\prod_{i,j} \frac{1}{1-\zeta_i y_j}.$$ On the other hand, $$\prod_{i,j} \frac{1}{1-\zeta_i y_j}=\prod_{j}\frac{1}{1-y_j^n}.$$ This is the generating series for the complete sums $h_k$ evaluated at $y_1^n$, $y_2^n\ldots$ , that are exactly the plethysms $h_k[p_n]$: $$\prod_{j}\frac{1}{1-y_j^n}=\sum_k h_k[p_n[Y]].$$</p> <p>These plethysms expand in the Schur basis: $$h_k[p_n[Y]]=\sum_{\lambda} d(\lambda,(k),n) s_{\lambda}[Y].$$ The coefficient $d(\lambda,(k),n)$ is the evaluation you are looking for, for $k \cdot n = |\lambda|$.</p> <p>For any particular computation of the $d(\lambda,(k),n)$ you may use SAGE or John Stembridge's SF package for Maple.</p> <p>For a general study, you should find at least some examples of such plethysms in Macdonald's classical book. You will find more recent results by googling "plethysms power sums complete sums in Schur", for instance by William Doran, or Carbonara+Remmel+Yang. </p> <p>EDIT: Actually it is easy to evaluate the Schur polynomials at the $n$-the roots of unity, from the definition of the Schur polynomials as "bialternants". One gets that the evaluation of the Schur polynomial is nonzero if and only if the classes modulo $n$ of $\lambda_n$, $\lambda_{n-1}+1, \ldots, \lambda_1+{n-1}$ are a permutation of the classes of $0,1,\ldots,n-1$. Then this evaluation is the sign of the permutation.</p> <p><b> About the evaluation of the monomial functions,</b> since this is what you are really interested in. A method for evaluating the monomial functions at the roots of unity is presented in Alain Lascoux and Marcel-Paul Schutzenberger's "Formulaire raisonné de fonctions symétriques", ex. 5.14, with a reference to a paper of 1881 by E. West. I think it generalizes indeed your computations by inclusion-exclusion.</p> <p>The method consists in expanding the monomial functions in the power sum basis. Note that the power sum $p_r$ at the $n$-th roots of unity is $n$ if $n$ divides $k$, and $0$ else. </p> <p>The expansion of monomial functions in the power sum basis is explained in Example 2.7 of the "Formulaire raisonné de fonctions symétriques". It is also explained in "On the Foundations of Combinatorial Theory. VII: Symmetric Functions through the theory of distribution and occupancy". Peter Doubilet. Studies in Applied Mathematics 51 (4), 1972.</p> <p>Say you want to expand $m_{(\lambda_1,\ldots,\lambda_k)}$ in the power sum basis. Consider rather the "augmented monomial function" (which is, by the way, the function you are really interested in): $$M_{(\lambda_1,\ldots,\lambda_k)}=\sum x_{i_1}^{\lambda_1} x_{i_2}^{\lambda_2} \cdots x_{i_k}^{\lambda_k}$$ where the sum is carried over all arrangements $x_{i_1},x_{i_2},\ldots,x_{i_k}$ of $k$ variables. The expansion of $M_{\lambda}$ in the power sum basis involves the set partitions $\Pi$ of ${1,2,\ldots,k}$. They form a lattice under refinement, whose smallest element is the partition $\hat{0}$ in $k$ singletons. This lattice admits a Möbius function. Let $B_1$, $B_2,\ldots,B_{\ell}$ be the blocks of $\Pi$. The Möbius function on the interval $[\hat{0},\Pi]$ is: $$\mu(\hat{0},\Pi)=(-1)^{k-\ell} \prod_i \left( \text{card} B_i -1\right)!$$ Set $\lambda(\Pi)$ for the partition whose parts are the $\sum_{i \in B} \lambda_i$ for $B$ block of $\Pi$. Then the formula is: $$M_{\lambda}=\sum_{\Pi} \mu([\hat{0},\Pi]) p_{\lambda(\Pi)}$$ where the sum is over all set partitions $\Pi$ of ${1,\ldots,k}$. </p> <p>When evaluating at the $n$-th roots of unity you obtain: $$\sum_{\Pi} \mu([\hat{0},\Pi]) n^{\ell(\Pi)}$$ where the sum is over all partitions $\Pi$ such that all parts of $\lambda(\Pi)$ are multiple of $n$, and $\ell(\Pi)$ is the number of blocks.</p>