# Question on determining the minimal polynomial for an algebraic quotient

I need to determine the minimal polynomial for a quotient in (1).

(1) B = C / A

C is known as a root of a 36th degree polynomial and A is known as a root of a 24th degree polynomial.

However I have not been able to succeed in recovering the coefficients nor the degree of the polynomial for B.

Any suggestions? I have tried to use GP-Pari's algdep(number,power) command, but so far with little success, even though I know the decimal value of B to 10,018 digits.

Randall

P.S. This is a repost after a suggestion

After working with the resultant method, I was able to successfully recover a 144th degree polynomial whose highest power term has the expected square coefficient. This polynomial was one of 3 polynomials factored from a 864th degree polynomial originally obtained.

I guessed 72nd degree, but it would have taken too long using GP-Pari's algdep(number,144) to recover the polynomial.

Thanks for your suggestions, I now have a valuable tool to help me work with algebraic vectors in R3.

-
You can reverse the coefficients of the polynomial for A to get the polynomial for A^{-1}. After that it is straightforward to write down a matrix whose characteristic polynomial has B = C * A^{-1} as a root by taking the Kronecker product of the appropriate companion matrices (en.wikipedia.org/wiki/Companion_matrix). Good algorithms are known for computing the characteristic polynomial; see, for example, modular.math.washington.edu/books/modform/modform/… . –  Qiaochu Yuan May 13 '10 at 15:53
That's a much better answer than mine. You should post it. –  Kevin Buzzard May 13 '10 at 18:21
I followed Qiaochu's method and implemented an algorithm in GP-Pari. I took advantage of the charpoly() command to find the characteristic polynomial. Too bad the multiple precision 925x925 Kronecker product is chewing up all the system memory, so this might put a stop to finding an answer. Thanks for the solution. Randall –  Randall May 14 '10 at 1:21
It was 500-750MB in Magma for a random short polynomial choice, taking 100-200s to find the CharacteristicPolynomial. f:=Polynomial([Random([-100..100]) : i in [0..36]]); g:=Polynomial([Random([-100..100]) : i in [0..24]]); g:=Polynomial(Reverse(Coefficients(g))); f:=PolynomialRing(Rationals())!f/LeadingCoefficient(f); g:=PolynomialRing(Rationals())!g/LeadingCoefficient(g); P:=KroneckerProduct(CompanionMatrix(f),CompanionMatrix(g)); time char_poly:=CharacteristicPolynomial(P); But if you have larger coefficients it might explode. –  Junkie May 14 '10 at 2:10
typical coefficients in the polynomials I am using are around 10^33, so I think the calculation in Magma will slow considerably. –  Randall May 14 '10 at 5:18

Let $F$ be the polynomial for $A$, let $G$ be the polynomial for $C$. Consider the resultant of $x^{24}F(y/x)$ and $G(y)$. This will be a polynomial whose roots are all the numbers of the form $\gamma/\alpha$, where $\gamma$ (resp., $\alpha$) runs through the roots of $G$ (resp., $F$). The resultant is the determinant of a $60\times60$ matrix.
The resultant of $p(y)=ay^2+by+c$ and $q(y)=dy^3+ey^2+fy+g$ is the determinant of $$\pmatrix{a&b&c&0&0\cr0&a&b&c&0\cr0&0&a&b&c\cr d&e&f&g&0\cr0&d&e&f&g\cr}$$ It is also $a^3d^2\prod(\alpha-\beta)$, where $\alpha$ and $\beta$ run through the roots of $p$ and $q$, respectively. I think there's a good article on resultants at Wikipedia. It's also a semi-standard topic in more applied treatments of abstract algebra and in discussions of computer algebra systems. –  Gerry Myerson May 14 '10 at 7:04