Proof involving polynomial roots

Question

From USAMO 1977: "If $a$ and $b$ are two roots of $x^4+x^3-1=0$, prove that $ab$ is a root of $x^6+x^4+x^3-x^2-1=0$."

The solutions I've seen for this problem all involve manipulating Vieta's equations relating polynomial roots and coefficients. In particular, the solutions feel a bit like they've been plucked out of thin air, in that I don't understand their motivation. So I'd be interested to see some alternate solutions/extra explanation.

I instead tried to construct $(ab)^6+(ab)^4+(ab)^3-(ab)^2-1=0$ using $a^4+a^3-1=0$ and $b^4+b^3-1=0$, but was unsuccessful.

Answer 1

Considering

\begin{align} x^4+x^3-1 &= (x-a)(x-b)(x-c)(x-d) \\ S_1 &= a+b+c+d \\ &= -1 \\ S_2 &= ab+ac+ad+bc+bd+cd \\ &= 0 \\ S_3 &= bcd+acd+abd+abc \\ &= 0 \\ S_4 &= abcd \\ &= -1 \end{align}

The sextic has a nice symmetry so that all the roots are $ab$, $ac$, $ad$, $bc$, $bd$ and $cd$.

Now, using SymmetricReduction[(x-a b)(x-a c)(x-a d)(x-b c)(x-b d)(x-c d),{a,b,c,d}] in Wolfram Alpha or so, we have:

\begin{align} f(x) &= (x-\color{red}{ab})(x-\color{red}{ac})(x-\color{red}{ad}) (x-\color{red}{bc})(x-\color{red}{bd})(x-\color{red}{cd}) \\ &= x^6-S_2 x^{5}+(S_1 S_3-S_4)x^{4}+(2S_2 S_4-S_3^2-S_1^2 S_4)x^{3} \\ & \quad +(S_1 S_3 S_4-S_4^2)x^{2}-S_2 S_4^2 x+S_4^3 \\ &= x^6+x^4+x^3-x^2-1 \end{align}

Answer 2

I think that the problem is wrong as written, because if $a=b$, then $ab=a^2$ has minimal polynomial $x^{4} - x^{3} - 2 x^{2} + 1$, which doesn't divide $x^6+x^4+x^3-x^2-1$ (the reminder is $7 x^{3} + 6 x^{2} - x - 5$).

I guess that it was meant that $a\neq b$. Then, one may apply Galois theory to get a more straightforward way to compute the minimal polynomial of $ab$ and then to check whether or not it divides $x^6+x^4+x^3-x^2-1$ (it is a root iff the minimal polynomial divides...)

Here is a sketch how to do so: You prove that $\mathbb{Q}(a,b)$ has degree $12$ and a basis $\{a^{i}b^{j}\}$ with $i=0,1,2,3$ and $j=0,1,2$. Then you write a matrix AB for multiplication by $ab$ in this basis (usually it is easier to write a matrix $A$ for $a$, a matrix $B$ for $b$, and to multiply them). The minimal polynomial polynomial will be that of the matrix $AB$.

The downside is that one needs to work with $12\times 12$ matrices. But it is not too bad, since those matrices are essentially block-matrices.

Answer 3

I instead tried to construct $(ab)^6+(ab)^4+(ab)^3-(ab)^2-1=0$ using $\,\ldots$

Following up on OP's approach, let $\,ab=p\,$ and, for symmetry, $\,a+b=s\,$. To begin with:

$$ \begin{cases} \begin{align} a^4 + a^3 - 1 &= 0 \\ b^4 + b^3 - 1 &= 0 \end{align} \end{cases} \tag{1} $$

Subtracting the two equations in $\,(1)\,$, and using that $\,a \ne b\,$:

$$\require{cancel} \begin{align} a^4-b^4+a^3-b^3 = 0 \;\;&\implies\;\; \cancel{(a-b)}(a+b)(a^2+b^2) + \cancel{(a-b)}(a^2+ab+b^2) = 0 \\ &\implies\;\; s(s^2-2p) + s^2 - p = 0 \\ &\implies\;\; s^3 + s^2 - (2s+1)p = 0 \tag{2} \end{align} $$

Adding the two equations in $\,(1)\,$:

$$ \begin{align} a^4+b^4+a^3+b^3 - 2 = 0 \;\;&\implies\;\; \big((a+b)^4 - 4ab(a^2+b^2)-6a^2b^2\big) \\ &\quad\quad\quad\quad+\big((a+b)^3-3ab(a+b)\big)-2=0 \\ &\implies\;\; s^4 - 4p(s^2-2p)-6p^2+s^3-3ps-2 = 0 \\ &\implies\;\; s^4 + s^3 -4ps^2-3ps+2p^2-2=0 \tag{3} \end{align} $$

At this point, the equation satisfied by $\,p\,$ can be derived by eliminating $\,s\,$ between $\,(2)\,$ and $\,(3)\,$. This is usually better left to a CAS since the calculations can be tedious, and e.g. WA gives resultant[$s^3 + s^2 - (2s+1)p$, $s^4 + s^3 - 4ps^2 - 3ps + 2p^2 - 2, s$] = $8 (p^6 + p^4 + p^3 - p^2 - 1)$.

It can still be done by hand, though. Substituting $\,s^4+s^3=s \cdot (2s+1)p\,$ from $\,(2)\,$ into $\,(3)\,$:

$$ \begin{align} s(2s+1)p -4ps^2-3ps+2p^2-2=0 \;\;&\implies\;\; -2ps^2 - 2ps+ 2p^2 - 2 = 0 \\ &\implies\;\; ps^2+ps-p^2+1 = 0 \tag{4} \end{align} $$

Eliminating once again $\,s(s+1)\,$ between $\,(2)\,$ and $\,(4)\,$ by $\,s \cdot (4) - p \cdot (2)\,$ gives:

$$ \begin{align} 0 &= s \cdot \big(\cancel{ps(s+1)}-p^2+1\big) - p \cdot \big(\cancel{s^2(s+1)} - (2s+1)p\big) = (p^2+1)s+p^2 \tag{5} \end{align} $$

Then, substituting $\,s = \frac{-p^2}{p^2+1}\,$ back in $\,(4)\,$ gives in the end the sextic $\,p^6 + p^4 + p^3 - p^2 - 1 = 0\,$.