flatsurf / e-antic

Embedded algebraic number fields
https://flatsurf.github.io/e-antic/libeantic/
GNU Lesser General Public License v3.0
12 stars 11 forks source link

Implement operator== for elements in different number fields #254

Open saraedum opened 1 year ago

saraedum commented 1 year ago

Currently, elements in different number fields cannot be compared. As a consequence, we cannot compare equivalence classes of surfaces in libflatsurf if the surfaces are defined over different number fields.

There are several ways to solve this. All of which are quite a bit of work:

First we should of course compare the Arb approximations of elements up to some precision and special case for when the elements are actually rational.

We could embed one element in the other parent by determining a root of its minpoly.

Or, more generally but less efficient, compute the compositum of the parents, lift the elements and compare them.

videlec commented 1 year ago

The most efficient way is probably to

  1. special case rationals
  2. try to match the already computed arb ball
  3. compute minimal polynomials
  4. if minimal polynomials are the same, compute their real roots and see whether all others are enough isolated to conclude that the two elements are the same. If not refine until we get to a conclusion.

The missing routine is the computation of the minimal polynomial. Looking at sage source code for number_field_element.pyx it seems that this is just the square free part of the characteristic polynomial of the multiplication by the element in the number field seen as a Q-vector space.

saraedum commented 1 year ago
  1. is already implemented,
  2. is very easy to do of course,
  3. should be implemented in antic: there's already nf_elem_rep_mat so we only have to compute a minpoly, i.e., a charpoly and take its squarefree part which is all implemented in FLINT

However, our use case for this is a bit artifical so we might want to wait with this until we run into this problem in practice.