Expansion of polytabloids in the standard basis I would like to know the most efficient way to write a polytabloid in terms of standard ones.
I know the Garnir elements, but using them to do calculations is hard. I also read about "quadratic elements" in Fulton's Young Tableaux, but I hope a better construction exists.
The thing I would like to have is, in a perfect world, an algorithm that has a random polytabloid and a standard one as input, and the coefficient of the standard polytabloid in the expansion of the random polytabloid as an output. I don't think such algorithm exists, but it can help figure out what kind of algorithm I am looking for.
 A: One algorithm that you were looking for is the following.
Consider an arbitrary polytabloid $e_T$ corresponding to a tableau T. Let this tableau be related to a standard tableau $T_1$ by a permutation $\pi$, i.e. $T=\pi T_1$. Furthermore
$$
e_{T} = e_{\pi T_1} = \pi \, e_{T_1}
$$
so what we need is the matrix of Young's natural representation in the basis of standard polytabloids $e_{T_j}$. In particular we need the matrix $\mathcal{A} (\pi)$ corresponding to permutation $\pi$. The coefficients we are looking for are in the first column of this matrix. So what we need is an efficient way to find this matrix. Such a way was described in A.M.Garsia,T.J. McLarnan, Advances in Mathematics 69 p.32 (1988).
This uses the concept of an intersection of two tableaux. I will summarise what they say, in which I use a bit of useful notation of my own. Let $T_1$ and $T_2$ be two tableaux (not necessarily standard) of the same shape and we define the intersection
$$
T = T_1 \sqcap T_2
$$
where tableau $T$ contains element $a$ in row-column position $(i,j)$ if $a$ occurs in row $i$ of $T_1$ and also in column $j$ of $T_2$. In the case that there is only one element in each box of $T$ we say that the intersection is good, otherwise we say that the intersection is bad and we write $T_1 \sqcap T_2 = 0$. If the intersection is good then clearly there is a column permutation $\varkappa$ on $T_2$ such that $T=\varkappa T_2$. We then define the intersection function $\mathcal{I} (T_1,T_2)$ to be
$$
\mathcal{I} (T_1,T_2) = \left\{ \begin{array}{cc} \text{sgn} (\varkappa) & \text{if } T_1 \sqcap T_2 = \varkappa \, T_2 \\ 0 & \text{otherwise} 
\end{array} \right.
$$
We then define for an arbitrary permutation $\sigma$ the intersection matrix
$$
I_{ij} (\sigma) = \mathcal{I}(T_i, \sigma T_j)
$$
where $T_i$ are now our standard tableaux ordered in any order you prefer (for example dictionary ordering). Let $\imath$ be the identity element of $S_n$.
Then the matrix
$$
\mathcal{A} (\sigma) = I (\imath)^{-1} I(\sigma)
$$
is the matrix of Young's natural representation in the basis of standard polytabloids $e_{T_j}$. For $S_n$ with $n<5$ the matrix $I(\imath)$ is the identity matrix as follows by explicit check.
As an example we take $S_3$ and the standard tableaux of shape $(2,1)$:
$$
T_1 = \begin{array}{cc} 1 & 2 \\ 3 \end{array} \quad \text{  and  } \quad 
T_2 = \begin{array}{cc} 1 & 3 \\ 2 \end{array}
$$
Then we take, for instance, the permutation $\sigma=(132)$ such that
$$
\sigma \,T_1 = \begin{array}{cc} 3 & 1 \\ 2 \end{array} \quad \text{  and  } \quad 
\sigma \,T_2 = \begin{array}{cc} 3 & 2 \\ 1 \end{array}
$$
Then we can make a table for the intersection matrix where we put $T_1$ and $T_2$ in a column on the left and put $\sigma T_1$ and $\sigma T_2$ on the top row. The elements of the table are the intersections $T_i \sqcap \sigma T_j$:
$$
\begin{array}{ccccccccc} & & & 3 & 1 & & 3 & 2\\
& & & 2 & & & 1 & \\
& & & & & & & & \\
1 & 2 & & 2 & 1 &  & 1 & 2 \\
3 & & & 3 & & & 3 & & \\
& & & & & &  & & \\
1 & 3 & & 3 & 1 & & & &\\
2 & & & 2
\end{array}
\quad \quad \Rightarrow \quad I ( \,(132) \,) =
\begin{pmatrix} -1 & -1 \\
1 & 0
\end{pmatrix}
$$
in the top two of the matrix we have $-1$'s as the permutations $(23)$ and $(13)$ are odd and in the bottom row we have one even permutation ($\imath$) and a bad intersection in the bottom right corner as the elements 1 and 3 need to be put in the same box. Since we can directly verify the same way that $I (\imath)$ is the identity matrix, the matrix $I (\, (132) \,)$ coincides with $\mathcal{A} ( \, (132) \, )$.
Let now, for example, $e_T$ be a polytabloid for $S_3$ and $T=(132) T_1$. Then since
the column elements of the first column of the matrix $\mathcal{A} ( \, (132) \,)$ are $(-1,1)$ we must have that
$$
e_{T} = - e_{T_1} + e_{T_2}
$$
This can be checked by an explicit calculation. We have
$$
\begin{align}
e_{T_1} &= \begin{array}{cc} \hline 1 & 2 \\ \hline  \underline{3} \\ 
\end{array}
\quad - \quad 
\begin{array}{cc} \hline 3 & 2 \\ \hline  \underline{1}
\end{array} \\
e_{T_2} &= \begin{array}{cc} \hline 1 & 3 \\ \hline  \underline{2} \\ 
\end{array}
\quad - \quad 
\begin{array}{cc} \hline 2 & 3 \\ \hline  \underline{1}
\end{array}\\
e_{T} &= \begin{array}{cc} \hline 3 & 1 \\ \hline  \underline{2} \\ 
\end{array}
\quad - \quad 
\begin{array}{cc} \hline 2 & 1 \\ \hline  \underline{3} 
\end{array} \quad = \quad - e_{T_1} + e_{T_2}
\end{align}
$$
as was to be expected. The way of calculating the matrices of Young's natural representation is rather simple but does not seem to be known widely. The first reference I found to this was the paper of J.M.Clifton, Proceedings of the American Mathematical Society, 83, p.248, (1981), but the paper by Garsia and McLarnan I find nicer to read.
There are also some lecture notes by Garsia online that are useful.
