7
\$\begingroup\$

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 . Shortest answer in bytes wins.

\$\endgroup\$
16
  • \$\begingroup\$ Would you mind making your first test case a worked example? The second polynomial only has imaginary roots, and I'm not sure what implications this has wrt your challenge. \$\endgroup\$
    – Dennis
    May 15, 2017 at 15:13
  • \$\begingroup\$ @LuisMendo what should the answer be? \$\endgroup\$
    – Leaky Nun
    May 15, 2017 at 15:16
  • \$\begingroup\$ @Dennis I already have a worked example... \$\endgroup\$
    – Leaky Nun
    May 15, 2017 at 15:17
  • \$\begingroup\$ I'm aware of that. You don't mention complex roots anywhere though. \$\endgroup\$
    – Dennis
    May 15, 2017 at 15:17
  • \$\begingroup\$ @LeakyNun I get 4*x^2 - 4*x - 9, but I'm not sure \$\endgroup\$
    – Luis Mendo
    May 15, 2017 at 15:18

4 Answers 4

7
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can shave off a number of bytes by using an anonymous function instead: @(a,b){[~,d]=rat(x=poly((roots(a)+roots(b)')(:)')),round(x*prod(d))}{2} \$\endgroup\$
    – Suever
    May 16, 2017 at 11:27
  • \$\begingroup\$ @Suever Thanks! I forgot that indexing trick \$\endgroup\$
    – Luis Mendo
    May 16, 2017 at 12:24
2
\$\begingroup\$

Pari/GP, 50 49 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Ær - get roots of input polynomial How do you beat Jelly if it can solve polynomials in 2 bytes... :( \$\endgroup\$ May 16, 2017 at 1:23
  • 1
    \$\begingroup\$ @JungHwanMin Write a Mathematica package that redefines the verbose function names to one letter and call it your Mathematica golf language. It's as simple as that. The get roots of polynomial is actually lambda z: listify(numpy.roots(z[::-1])). It's no criticism since I like the idea of creating a golfing language, but it misses the point. When I see this right JungHwan you were the first with the Im[I^#]& solution for the triangle signal. This is what I call creativity! \$\endgroup\$
    – halirutan
    May 16, 2017 at 1:52

Your Answer

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

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