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

Suppose $f \colon S_n \rightarrow \mathbb{R}$ is some weighted collection of permutations. We want to understand how "well-spread" $f$ is. Our first test is its actions on singletons - are the statistics of how many permutations send $i$ to $j$ "random"?

To make this question more precise, define $|f| = \sum_\pi f(\pi)$ to be the total number of permutations in $f$ (i.e. their total weight), $A_{ij}$ to be the number of permutations in $f$ sending $i$ to $j$, and $B_{ij} = A_{ij} - |f|/n$. The matrix $B$ is just a normalized form of $A$ - its row and column sums are zero. A measure of spread is the Frobenius norm of $B$, i.e. $\sum_{i,j} B_{ij}^2$.

Consider now the Fourier transform of $f$. For each partition $\rho$, there is some Fourier coefficient $\hat{f}(\rho)$ which is some (square) matrix. We know that the coefficient of $(n)$ characterizes $|f|$, and the coefficients of $(n)$ and $(n-1,1)$ together characterize the action on singletons. Since we have erased the effects of $\hat{f}((n))$ by moving from $A$ to $B$, it should not come as a surprise that the Frobenius norms of $B$ and of $\hat{f}((n-1,1))$ are linearly related - that's what I seem to get.

Is it correct that the Frobenius norm of $B(f)$ is equal to some constant multiple (depending on $n$) of $\hat{f}((n-1,1))$?

Can the result be extended to other Fourier coefficients? What data corresponds to a partition $\rho$? In particular, what partitions capture the effect of $f$ on $k$-tuples? (the answer should be something like all partitions whose first part is $n-k$)

share|improve this question
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.