# Algebraic square root question

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$?

• r = P(i) and s = Q(j) isn't abusing notation; that's just bad notation. – 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.

• 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. – Randall May 14 '10 at 19:23
• 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. – Randall May 14 '10 at 21:15
• Can you not just give the smaller polynomial 0 coefficients to make the matrices the same size? – Pádraig Ó Conbhuí May 14 '10 at 21:50
• 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. – Qiaochu Yuan May 14 '10 at 21:57
• 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. – Randall May 14 '10 at 22:04