10
$\begingroup$

Inspired by this question, I was wondering about the following problem.

$\alpha,\beta,\gamma,\ldots$ are the roots of an irreducible polynomial over $\mathbb{Q}$. How to compute the coefficients of $$ (x-\alpha\beta)(x-\alpha\gamma)\cdot \ldots\cdot (x-\beta\gamma)\cdot\ldots, $$ i.e. the candidate minimal polynomial of $\alpha\beta$, in the most efficient way?

My approach is based on a simple lemma and a general fact. If $p_m$ is the power sum $\alpha^m+\beta^m+\gamma^m+\ldots$ and $e_i$ is the $i$-th elementary symmetric polynomial, the identity $$ \exp\left(-\sum_{m\geq 1}\frac{p_m}{m}x^m\right) = \sum_{r\geq 0}(-1)^r e_r\,x^r$$ gives a way to compute $p_1,p_2,p_3,\ldots$ from $e_1,e_2,e_3,\ldots$ through the Taylor series of a logarithm ($\text{LOG}$) as well as $e_1,e_2,e_3,\ldots$ from $p_1,p_2,p_3,\ldots$ through the Taylor series of an exponential ($\text{EXP}$). Moreover, the characteristic polynomial of the sequence $\{p_k\}_{k\geq 0}$ is exactly the minimal polynomial of $\alpha$, hence we may compute $p_{n+1},p_{n+2},\ldots,p_{n+m}$ from $p_1,p_2,\ldots,p_n$ with a simple recursive approach (I will call this procedure $\text{CH}$, from Cayley-Hamilton). $\text{L}$ will be my previously mentioned lemma, i.e. $$ p_k(\alpha\beta,\alpha\gamma,\ldots) = \frac{1}{2}\left(p_k^2-p_{2k}\right).$$ Now my algorithm goes as follows:

(1). $$ e_i(\alpha,\beta,\gamma,\ldots)_{i\leq n}\quad\xrightarrow{\text{LOG}}\quad p_i(\alpha,\beta,\gamma,\ldots)_{i\leq n}$$ (2). $$ p_i(\alpha,\beta,\gamma,\ldots)_{i\leq n}\quad\xrightarrow{\text{CH}}\quad p_i(\alpha,\beta,\gamma,\ldots)_{i\leq n(n-1)}$$ (3). $$ p_i(\alpha,\beta,\gamma,\ldots)_{i\leq n(n-1)}\quad\xrightarrow{\text{L}}\quad p_i(\alpha\beta,\alpha\gamma,\ldots)_{i\leq \binom{n}{2}}$$ (4). $$ p_i(\alpha\beta,\alpha\gamma,\ldots)_{i\leq \binom{n}{2}}\quad\xrightarrow{\text{EXP}}\quad e_i(\alpha\beta,\alpha\gamma,\ldots)_{i\leq \binom{n}{2}}.$$

$\endgroup$
2
$\begingroup$

I don't see that the assumption that $\alpha$ and $\beta$ are roots of the same polynomial is particularly helpful. Suppose they have minimal polynomials $f(\alpha), g(\beta)$. Write down the companion matrices of these polynomials, then the Kronecker product of these matrices, then compute the characteristic polynomial of the Kronecker product. This polynomial isn't guaranteed to be irreducible, but from here you can factor it.

$\endgroup$
  • 1
    $\begingroup$ (+1) interesting approach, but I am not sure that computing a characteristic polynomial of a huge (even if sparse) matrix is more efficient than my approach :/ $\endgroup$ – Jack D'Aurizio May 17 '16 at 17:58

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.