As part of working with dot products of vectors in an algebraic field, having previously solved the algebraic quotient, I need to find the algebraic square root as shown in (1)

Let $r_i$ be a root of polynomial P and $s_j$ be a root of polynomial Q i.e., P($r_i$)=0, Q($s_j$)=0.

I seek to find a third polynomial R and its root $t_k$, such that R($t_k$)=0, so that

(1) $t_k$ = $\sqrt{1 - r_i^2 - s_j^2}$

is satisfied. How can R be found, knowing $t_k$?

  • 1
    $\begingroup$ r = P(i) and s = Q(j) isn't abusing notation; that's just bad notation. $\endgroup$ – Qiaochu Yuan May 14 '10 at 19:05

Lemma 1: If $P(x)$ is an integer polynomial with root $r$, then $P(x^2)$ is an integer polynomial with root $\sqrt{r}$.

Lemma 2: If $P(x)$ is an integer polynomial with root $r$, then $P(\sqrt{x})P(-\sqrt{x})$ is an integer polynomial with root $r^2$.

Lemma 3: If $P(x)$ is an integer polynomial with root $r$, then $P(x - t)$ is an integer polynomial with root $r + t$, for $t$ an integer.

Lemma 4: If $P, Q$ are integer polynomials with roots $r, s$, then an integer polynomial with root $r + s$ is given by the characteristic polynomial of $A \otimes I + I \otimes B$ where $A, B$ are the companion matrices of $P, Q$ and $\otimes$ denotes the Kronecker product. Multiplication by $r + s$ defines a $\mathbb{Q}$-linear transformation on $\mathbb{Q}[r, s]$, which has $\mathbb{Q}$-basis $r^i s^j$ where $i, j$ range from $0$ to one less than the degrees of $P$ and $q$, and the matrix above is the matrix of this linear transformation in that basis.

So apply Lemma 2 twice, then Lemma 3, then Lemma 4, then Lemma 1.

| cite | improve this answer | |
  • $\begingroup$ Considering that I am working with 864 degree polynomials, and that there doesn't appear to be an easy way of implementing Lemma 2 in GP-Pari, this will take awhile, but I accept your answer. $\endgroup$ – Randall May 14 '10 at 19:23
  • $\begingroup$ I am having problems with Lemma 4, in general the Kronecker product of A,I is not the same size matrix as I,B, so I cannot add the matrices. Furthermore, working with the Kronecker product of 864th degree polynomials is proving impractical in GP-Pari, due to both time and memory constraints, so is there a resultant method which might work better? I do need to keep the matrices with multiple precision entries down to a reasonable size. $\endgroup$ – Randall May 14 '10 at 21:15
  • $\begingroup$ Can you not just give the smaller polynomial 0 coefficients to make the matrices the same size? $\endgroup$ – Pádraig Ó Conbhuí May 14 '10 at 21:50
  • $\begingroup$ Sorry, that was ambiguous. The first I is of dimension deg Q and the second I is of dimension deg P. Anyway, maybe you should just use Wiedemann's algorithm (modular.math.washington.edu/books/modform/modform/…) on the action of r+s on Q[r, s] directly instead. $\endgroup$ – Qiaochu Yuan May 14 '10 at 21:57
  • $\begingroup$ I actually took the time to implement the resultant method, see en.wikipedia.org/wiki/Resultant on this, particularly their paragraph under the heading Applications which states: If x and y are algebraic numbers such that P(x) = Q(y) = 0 (with degree of Q=n), we see that z = x + y is a root of the resultant (in x) of P(x) and Q(z − x) and that t = xy is a root of the resultant of P(x) and xnQ(t / x) ; combined with the fact that 1 / y is a root of ynQ(1 / y), this shows that the set of algebraic numbers is a field. It is much easy to work with matrices size m+n than size m*n. $\endgroup$ – Randall May 14 '10 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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