## 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 2010 at 15:53
That's a much better answer than mine. You should post it. – Kevin Buzzard May 13 2010 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 2010 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 2010 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 2010 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.
 Could you explain a bit more? This is new to me, sorry to say. Or point me to "Resultants for Dummies" I would like to see exactly how the matrix was shortened from 864 x 864 for the tensor product to just 60 x 60, which is significant. – Randall May 14 2010 at 5:22 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 2010 at 7:04 I should have said; I hope from the example given you can infer the general form. My TeX isn't up to the challenge. – Gerry Myerson May 14 2010 at 7:06 After some tricky programming inside a function call which required killed variables in order to implement symbolic variables inside that function, I was able to finally create a function which implements the resultant method. The 60x60 matrix is much smaller than the 864x864 Kronecker product, and computable with available memory space. Thanks, this helps a lot. – Randall May 14 2010 at 16:48 I finally was able to successfully recover the 864th degree polynomial using the resultant method. It was factorable into 3 polynomials, two 144th degree and one 576th degree. The root that I sought was in the 2nd 144th polynomial. polroots() command in GP-Pari for 864th deg polynomials uses up memory, it bombed out at 1 gig and asked for more. I appreciate this answer, it has saved me a lot of time. – Randall May 14 2010 at 18:43