Re: Reuse of data in rnfkummer/computing order of galois elements without it

[Loïc Grenié <loic.grenie@gmail.com>]

On 2017-04-03 at 8:06 GMT+02:00 Karim Belabas wrote:

* Watson Ladd [2017-04-03 06:53]:
> Dear all,
> I have a program which computes many rnfkummer's over the same base
> field K. All the rnfkummers are quadratic extensions. This ends up
> taking a very, very long time, particularly as many of the extensions
> have galois groups which contain elements of orders which are two
> large and are thus thrown out, so the time spent computing the
> extensions is wasted.
>
> My questions are as follows:
>
> 1: Can anything be done to accelerate the repeated rnfkummers?

Not for quadratic extensions. (In general, to compute a Kummer extension
of exponent p we need to p-th roots of unity to the base field; this
could be re-used. Useless for p = 2...)

> 2: Is there a way to determine the maximal order of an element of the
> Galois group of the resulting field without computing the field via
> rnfkummer? I know about bnrgaloismat, but it doesn't seem as though
> the resulting representation of the galois group can be used to find
> the order of elements easily.

By "Galois group" I understand the Galois group of (class field) over K.
(If you meant Gal(class field/Q), modify the following with the maximal
order allowed in the quotient.)

I don't see a fast if-and-only-if algorithm. There's a quick early abort
though : pick prime ideals in the base field not dividing the conductor
and compute their order in the ray class group (see below); if this
order is too large, stop. Under GRH, a suitable effective Chebotarev
bound would turn this into a fast rigorous algorithm.

    With Giuseppe Molteni we have proved a result analogous to Oesterlé's

  Theorème 2 of "Versions effectives du théorème de Chebotarev sous
  l'hypothèse de Riemann généralisée", with better constants for the log's.

  We have proved that

  \forall x\geq 100,

\left|\psi_C(x) - \frac{|C|}{|G|}x \right|\leq \frac{|C|}{|G|} \sqrt{x}\left[
    \log d_E \left(\frac{\log x}{2\pi} + 2\right)

    + n_E\left(\frac{\log^2 x}{8\pi} + 2\right)\right]

  (there are a few quirks if G is not cyclic of prime order, but for quadratic

  extensions there are no problems).

  The paper is not yet in publishable form, but we expect to publish it on

  Arxiv in a few days or weeks.

     Cheers,

          Loïc