Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello mathematicians, i'm looking for explicit computations of expressions like $$ \sum_{\substack{0\leq i,j,k<n\\i\neq j\neq k \neq i}}\zeta_n^{ip^{k_1}+jp^{k_2}+kp^{k_3}} $$ 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$. The above expression is also, up to a factor, equal to the Schur polynomial $s_\lambda$ (of algebraic combinatoric fame) with partition $\lambda=(p^{k_1},p^{k_2},p^{k_3})$ evaluated in $1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{n-1}$.(this is not true, but as was pointed out by Emmanuel the above sum is rather a monomial symmetric function $m_\lambda$)

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!

share|improve this question
1  
1. I do not immediately see why this is related to a Schur polynomial. But for the Schur polynomial evaluated at a geometric sequence, there is a nice product formula (e.g., see this MO question mathoverflow.net/questions/549/…) 2. Also, note that a Schur polynomial $s_{\lambda}$ in $n$ variables is zero if the number of parts in $\lambda$ is bigger than $n$. –  Leonid Petrov Jun 12 '11 at 21:35
1  
Your sum is (up to a nonzero factor) the monomial symmetric function $m_{\lambda}$ evaluated at the roots of the unity. It does not seem to coincide in general with the evaluation of $s_{\lambda}$ at the roots of unity, except maybe under stronger hypotheses. For instance, take $n=5$ and $\lambda=(9,3,3)$, that is $p=3$ and $k_1=2$, $k_2=1$, $k_3=1$. Then the evaluation of $s_{\lambda}$ at the $5$-th roots of unity is zero, but the evaluation of $m_{\lambda}$ is different from zero (it is 5, and your sum is $2 m_{\lambda}$). –  Emmanuel Briand Jun 15 '11 at 10:54
1  
The reason that i was thinking of it is because $det(\zeta^{j(\lambda_i+n-i)})$ (which is $s_\lambda(1,\zeta,\zeta^2,\dots)$ up to the Vandermonde factor) can be expanded in the sum over the permutations $w\in S_n$ of terms $\epsilon(w)\cdot \prod_i \zeta^{w(i)\lambda_i} \cdot \prod_i \zeta^{w(i)(n-i)}$, and for some reason i was thinking that $\prod_i \zeta^{w(i)(n-i)}=\epsilon(w)$, which is certainly not true. Sorry for the misleading statement in the post. –  Maurizio Monge Jun 15 '11 at 12:46
add comment

1 Answer

up vote 10 down vote accepted

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

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]]. $$

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|$.

For any particular computation of the $d(\lambda,(k),n)$ you may use SAGE or John Stembridge's SF package for Maple.

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.

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.

About the evaluation of the monomial functions, 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.

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.

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.

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\}$.

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.

share|improve this answer
    
Great answer, even if as you pointed out my question was rather about monomial symmetric functions rather than about Schur functions. I was always intrigued by the plethysm of symmetric functions, and i look forward to give a look at the references you pointed out, time permitting! –  Maurizio Monge Jun 15 '11 at 12:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.