3
$\begingroup$

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.

Thanks for your help.

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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/… . $\endgroup$
    – Qiaochu Yuan
    May 13, 2010 at 15:53
  • $\begingroup$ That's a much better answer than mine. You should post it. $\endgroup$
    – Kevin Buzzard
    May 13, 2010 at 18:21
  • $\begingroup$ 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 $\endgroup$
    – Randall
    May 14, 2010 at 1:21
  • $\begingroup$ 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. $\endgroup$
    – Junkie
    May 14, 2010 at 2:10
  • $\begingroup$ typical coefficients in the polynomials I am using are around 10^33, so I think the calculation in Magma will slow considerably. $\endgroup$
    – Randall
    May 14, 2010 at 5:18

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Randall
    May 14, 2010 at 5:22
  • $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    May 14, 2010 at 7:04
  • $\begingroup$ I should have said; I hope from the example given you can infer the general form. My TeX isn't up to the challenge. $\endgroup$
    – Gerry Myerson
    May 14, 2010 at 7:06
  • $\begingroup$ 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. $\endgroup$
    – Randall
    May 14, 2010 at 16:48
  • $\begingroup$ 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. $\endgroup$
    – Randall
    May 14, 2010 at 18:43
1
$\begingroup$

Here's a suggestion. Use polcompositum(FA,FC) (with FA the min poly of A, FC the min poly of C) to find a number field K=Q(alpha) containing roots of both your polynomials, and then use lindep() to find a relation between 1,alpha,alpha^2,...,alpha^{d-1} and B. That will probably be much more efficient, because somehow you are using the knowledge of FA and FC this way, rather than just using algdep, which is throwing it away completely.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.