MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.