Add up two algebraic numbers

Question

Definitions

• An algebraic number is a number that is a zero of a non-zero polynomial with integer coefficients. For example, the square root of 2 is algebraic, because it is a zero of x^2 - 2.
• The corresponding polynomial is called the minimal polynomial of the algebraic number, provided that the polynomial is irreducible over ℚ.

Task

Given the minimal polynomials of two algebraic numbers, construct a set of numbers that are the sum of two numbers, one from the root of one polynomial, and one from the other. Then, construct a polynomial having those numbers as roots. Output the polynomial. Note that all roots are to be used, including complex roots.

Example

• The two roots of x^2-2 are √2 and -√2.
• The two roots of x^2-3 are √3 and -√3.
• Pick one from a polynomial, one from the other, and form 4 sums: √2+√3, √2-√3, -√2+√3, -√2-√3.
• A polynomial containing those four roots is x^4-10x^2+1

Input

Two polynomials in any reasonable format (e.g. list of coefficients). They will have degree at least 1.

Output

One polynomial in the same format, with integer coefficients.

You are not required to output an irreducible polynomial over ℚ.

Testcases

Format: input, input, output.

x^4 - 10 x^2 + 1
x^2 + 1
x^8 - 16 x^6 + 88 x^4 + 192 x^2 + 144

x^3 - 3 x^2 + 3 x - 4
x^2 - 2
x^6 - 6 x^5 + 9 x^4 - 2 x^3 + 9 x^2 - 60 x + 50

4x^2 - 5
2x - 1
x^2 - x - 1

2x^2 - 5
2x - 1
4x^2 - 4 x - 9

x^2 - 2
x^2 - 2
x^3 - 8 x

The outputs are irreducible over ℚ here. However, as stated above, you do not need to output irreducible polynomials over ℚ.

Scoring

This is code-golf. Shortest answer in bytes wins.

Answer 1

Mathematica, 32 bytes

Resultant[#,#2/.x->z-x,x]/.z->x&

Or the same length:

Resultant[#/.x->y,#2/.x->x-y,y]&

Example:

In[1]:= Resultant[#,#2/.x->z-x,x]/.z->x&[x^4 - 10 x^2 + 1, x^2 + 1]

Out[1]= 144 + 192 x^2 + 88 x^4 - 16 x^6 + x^8

In[2]:= Resultant[#/.x->y,#2/.x->x-y,y]&[x^2 - 2, x^2 - 2]

Out[2]= -8 x^2 + x^4

Explanation:

If x is a root of f(x), y is a root of g(y), and let z = x + y, then (x, z) is a root of the simultaneous equations f(x) = 0, g(z - x) = 0. Then we can eliminate the variable x using the resultant.

Answer 2

Octave, 81 71 bytes

10 bytes off thanks to Suever!

@(a,b){[~,d]=rat(x=poly((roots(a)+roots(b)')(:)')),round(x*prod(d))}{2}

Try it online!

Explanation

The code defines an anonymous function which uses a straightforward approach. It obtains the roots of each polynomial, computes all pairwise sums, and converts back from roots to polynomial. Since the resulting coefficients may not be integer, each is converted to a rational approximation and then they are all multiplied by the product of denominators.

Answer 3

Pari/GP, 50 49 bytes

p->q->polresultant(subst(p,x,y),subst(q,x,x-y),y)

Try it online!

Answer 4

Jelly, 16 bytes

Ærp/S€Æṛær9µ÷g/Ḟ

Try it online! (runs the last test case)

Takes input as list of coefficients with lowest value exponent first, e.g. [-5,0,2],[-1,2] would be 2x^2-5,2x-1

Explanation

Ærp/S€Æṛær5µ÷g/Ḟ
Ær                 - get roots of input polynomial
  p/               - Cartesian product (all pairs) of roots
    S€             - sum of each pair
      Æṛ           - find a polynomial given the sums as the roots
        ær9        - round to 10^(-9), used for output
           µ÷      - divide by ... 
             g/    - the gcd of the coefficients of the output polynomial
               Ḟ   - take the floor to get integers.