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