Re: nfbasis with complete list of factors of field discriminant

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Fiori, Andrew [2019-03-15 23:08]:
> I am unsure if I am misreading the documentation, if this is a bug in the
> documentation or a bug in the code. In any case the documentation for
> nfbasis suggests that if I call:
>    nfbasis([x^4 - x^3 + 10558*x^2 - 2169592*x + 195873967, [13,73,89]])
> I should obtain a global integral basis because:
>      "The result is actually a global integral basis if all prime divisors
>      of the field discriminant are included!"

This was a bug in the documentation: this behaviour would be achievable 
(in polynomial time) but is no longer implemented.

I have fixed the documentation in the 'master' branch, see

http://pari.math.u-bordeaux.fr/dochtml/html/General_number_fields.html#nfbasis

(this describes features that are only available in 'master', not in 2.11.1)

> However, even though the discriminant of the field in this case is
> (13*73*89)^3, the basis returned has index (103*499), so is not globally
> maximal.

Indeed. This contradicts the old documentation. But is consistent with the
current documentation (and expected behaviour).

Thanks for your report !

    K.B.

P.S. There are a few underlying technical problems:

1) we are overloading the single function nfbasis with two different
specifications:
  - actually computing the maximal order given some hints [ the single
    integer radical(disc(K)) would be enough to guarantee we obtain the
    maximal order, in polynomial time in the input size ]
  - computing an order which is maximal at a given list of primes.
Only the second one is actually implemented, the user has no way to specify,
e.g., "and no other primes divide the field discriminant".

2) I can't implement both specifications efficiently at the same time, i.e.
if in doubt about maximality of the resulting order, it is costly to
ascertain the fact because we must switch from efficient polynomial
algorithms (Dedekind criterion, Round 4) to slow linear algebra algorithms
(Round 2). So I can't really decide "let's assume that no other primes divide
the field discriminant and that the user actually cares about a maximal
order", because acting on that assumption increases the running time by an
order of magnitude (and *will* improve the result only under specific
assumptions).

3) The precise problem here is as follows. The genuine Buchmann-Lenstra
strategy iteratively computes the radical Ip of O/pO then O <- (Ip:Ip)
starting from the order O = Z[X]/(T) until we stabilize (iff O is p-maximal).

  * if p is a prime, this is Zassenhaus's Round 2 and is guaranteed to work

  * if p is not a prime, then (B.-L.) the above either produces an order which
  is maximal at all prime divisors of p, or a proper divisor of p [and we can
  recurse with proper factors]

  * if p is prime, then Round 2's first step boils down to Dedekind criterion
  based on the computation of (T,T') in Fp[X] and a simple computation mod p^2

  * if p is not a prime, then this is not true and applying Euclid's algorithm
  in (Z/pZ)[X] to (T, T') in an attempt to compute a "gcd" fails miserably.
  In you case, it immediately (and wrongly) states that Z[X]/(T) is
  "p-maximal", for p = 103*499.

  * if p is not a prime there can be other failures in later stages of
  PARI's implementation due to our using Round 4 ("p-adic" polynomial
  factorization) instead of Round 2. This tends to work in practice, just
  like Round 2 would (find correct results or factorize p) but without formal
  guarantees.

See ??nfbasis [current documentation !] for ways to check whether the result
is actually maximal under various assumptions; we may someday
include a *new* function that would correctly implement the true
Buchmann-Lenstra algorithm (same input as nfbasis, except that this time
we would assume that the user wants the maximal ideal, and go for the
expensive final checks if in doubt).

--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`