Re: nfbasis with complete list of factors of field discriminant

Thanks for the detailed info.

For your reference, the linked docs still contain:

"We obtain the maximal order and its discriminant if the field discriminant factors completely over the primes less than B (together with the primes contained in the addprimes table)."

in the example text.

In any case, though I would vote for eventually adding the auxiliary ability to get maximal orders by specifying the factorization of the field discriminant, I imagine it is considerable work.

In the mean time, would the best way to obtain the desired outcome of improving the performance of nfbasis be (assuming a case where the primes are actually large rather than this toy case...)

addprimes([13,73,89]);

nfbasis(x^4 - x^3 + 10558*x^2 - 2169592*x + 195873967);

removeprimes([13,73,89]);

because this at least ensures it should quickly find the most important prime factors of the polynomial discriminant?

Thanks again,

Andrew

On Wed, Apr 3, 2019 at 9:53 AM Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:

* 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]
`