Making the fundamental theorem of Galois theory explicit I encountered the present question when investigating that other recent question of mine.

Let $x_1,x_2, \ldots, x_8$ be indeterminates. Let $s_1,s_2, \ldots s_n$ denote the elementary symmetric polynomials (so that $s_1=\sum x_i, s_2=\sum_{i<j}x_ix_j$ etc. Let us consider also 
$$
\begin{align}
g_1 &= x_1x_2+x_3x_4+x_5x_6+x_7x_8 \\
g_2 &= x_1x_3+x_1x_7+x_2x_4+x_2x_8+x_3x_5+x_5x_7+x_4x_6+x_6x_8 \\
g_3 &= x_1x_4+x_1x_8+x_2x_3+x_2x_7+x_4x_5+x_5x_8+x_3x_6+x_6x_7 \\
g_4 &= x_1x_5+x_2x_6+x_3x_7+x_4x_8 \\
g_5 &= x_1x_6+x_2x_5+x_3x_8+x_4x_7
\end{align}
$$
If we make act the group $S$ of permutations of $\lbrace x_1,x_2, \ldots, x_8\rbrace$ on polynomials in the usual way, one can compute the subgroup $T$ of permutations fixing $g_1$ and $g_2$ (in particular, it has 16 elements). One can also check that any element of $T$ fixes $g_3$. So by the Galois correspondence, we have a polynomial $A$ with rational coefficients such that 
$$
g_3=A(s_1,s_2, \ldots ,s_n,g_1,g_2)
$$
How can we compute $A$ ?
 A: A short useless answer : try to write $g_3 = P/Q$ with $P$ homogeneous of degree $d+2$ and $Q$ of degree $d$ for $d=1$. If that fails, try again with $d=2$, and so on.
Or you can try to directly guess a good degree so that it will be solvable.
Let $R = K[x_1 \ldots x_8]$, denote $R_d$ the subspace of $R$ of homogeneous polynomials of degree $d$, let $R^G$ the subring of $R$ of elements fixed by a subgroup of $S_8$, $R^G_d = R^G \cap R_d$, and $R^G[y]$ be the subring generated by $R^G$ and $y$, and $R^G[y]_d = R^G[y] \cap R_d$.
Let $G$ be the subgroup of order $16$ fixing $g_1$ and $g_2$. Then $R^{S_8}[g_1,g_2] \subset R^G$. For small $d$, the inclusion is strict but Galois theory implies that for some $d$ large enough you will have $R^{S_8}[g_1,g_2]_d = R^G_d$.
The goal is to find two nonzero elements $P \in R^{S_8}[g_1,g_2]_d, Q \in R^{S_8}[g_1,g_2]_{d+2}$ such that $P g_3 = Q$. We know $g_3 \in R^G_2$ thus $P g_3 \in R^G_{d+2}$.
The multiplication by $g_3$ map $R^{S_8}[g_1,g_2]_d \to R^G_{d+2}$ is always injective, so its image is a subspace of dimension $\dim_K(R^{S_8}[g_1,g_2]_d)$.
If $\dim_K(R^{S_8}[g_1,g_2]_d) + \dim_K(R^{S_8}[g_1,g_2]_{d+2}) > dim_K(R^G_{d+2})$, the intersection of those two is guaranteed to be nonzero, so you will obtain nonzero elements $P,Q$ as wanted.
So first you have to compute all the numbers $\dim_K (R^G_d)$ and $\dim_K (R^{S_8}[g_1,g_2]_d)$, find the smallest integer $d$ such that the inequality holds, then solve an extremely big system of linear equations. Since those dimensions grow like $d^8/8!16$ you should try to pick the smallest $d$ possible.
Of course you may not get the smallest polynomials possible, it may happen that there was a linear combination for a smaller degree, but you can't know a priori that it exists.
Finding $\dim_K (R^G_d)$ is a combinatorics problem. It shouldn't be too difficult here, just count the orbits of $R_d$. For $\dim_K (R^{S_8}_d)$ since it is generated by $n$ polynomials, you get it easily with generating functions. For $\dim_K (R^{S_8}[g_1,g_2]_d)$, I'm not certain what the best way is, it doesn't seem too friendly. You don't need to compute it exactly, a good enough lower bound will work too.
You can compute $\dim_K (R^{S_8}[g_1]_d)$.
$g_1$ is the root of a degree $105$ polynomial with coefficients in $R^{S_8}$, thus $\dim_K (R^{S_8}[g_1]_d) = \sum_{0 \le i < 105} \dim_K (R^{S_8}_{d-i})$.
Next, $g_2$ is a root of a degree $24$ polynomial with coefficients in the fraction field of $R^{S_8}[g_1]$, which gives you a nice enough lower bound for $\dim_K (R^{S_8}[g_1,g_2]_d)$ (you should obtain something equivalent to $d^8/8! 16$)
