Re: nfsnf problems

["John Cremona" <john.cremona@gmail.com>]

I seem to remember finding some errors in that section of HC's book
when I went through it in detail some time ago.  I hope that Karim is
using a corrected version.

Of course you will now ask me what was wrong and where, to which I can
happily reply that I am at home and my copy of the book in the office.

John Cremona

2008/12/6 Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>:
> * David Loeffler [2008-12-03 13:06]:
>> I'm having some trouble with the "nfsnf" function.
>>
>> Firstly, in quite a lot of cases -- particularly where the matrix is
>> close to being in Smith form already -- I get the error message "bug2 in
>> nfsmith". This happens in both 2.3.3 and 2.4.2alpha. Secondly, when I do
>> get an answer I'm not convinced it's the right one.
>>
>> Here's an example:
>>
>> E = nfinit(x^2 - x + 2);
>> M = [1, 0, x; 0, x, 0; 0,0,2+x];
>> MM = nfalgtobasis(E, M);
>> N = [[1, 0; 0, 1], [1, 0; 0, 1], [1, 0; 0, 1]];
>> nfsnf(E, [MM, N, N])
>>
>> If I've understood everything correctly, that should calculate the SNF
>> of the matrix [1,0,w; 0,w,0; 0,0,2+w] where w^2 - w + 2 = 0. But it returns
>>
>> [[8, 3; 0, 1], [1, 0; 0, 1], [1, 0; 0, 1]]
>>
>> Converting these back to polmods, that's saying that the matrix has
>> elementary factors 1, 1, and the ideal generated by 8 and w + 2 (since
>> E.zk[1] = 1, E.zk[2] = x-1.) But it's clear just by looking at the
>> matrix that its elementary factors are 1, w and 2 + w.
>>
>> If I change the [1,3] entry of M to 0 instead of x, it gives me the bug2
>> in nfsmith error message.
>>
>> Any suggestions what's going on here?
>
> 1) The nfsnf function was not really specified in the PARI/GP documentation
> so I am not sure what was intended in the implementation.
>
> 2) Taking as a reference Section 1.7 of Henri Cohen's GTM 193 (Advanced
> Topics in Computational Number Theory), in particular Algorithm 1.7.3,
> and reverse-engineering the code to try and link the two together,
> I wrote a new specification (section 3.6.4 and 3.6.108 of the User's
> manual).
>
> 3) Based on that specification, I fixed 3 major problems in the code:
>
> -- one related to both the "bug2" and the "wrong result" problem [ rescale
> the column so that diagonal term is 1, as the rest of the algorithm
> apparently assumed ],
>
> -- one which did not show up in your endeavours, and apparently replaced
> b_i <--> b_i^{-1}. There's a comment in GTM 193 saying that one should
> manipulate b_i^{-1} and not b_i to avoid ideal inversions; the code
> assumed it had been done from the start (i.e the input had been suitably
> modified).
>
> -- another obscure one, which I introduced a long time ago while
> cleaning this code without checking what it meant. (Basically: if some
> test fail, go on computing garbage instead of restarting the main loop.
> The test hardly ever failed in simple examples...)
>
>
> One final problem, which I have not dealt with: the algorithm only makes
> sense for "integral" pseudo-matrices ( a_{i,j} in B_i A_j^(-1) for all i,j ).
> Neither the code, nor the regression tests seem to be interested in that
> condition. (On the contrary, it is violated in every single regression test
> involving nfsnf.)
>
> I am not too sure what to do with this; for the time being, I do not check it
> (rather costly), and let the algorithm go on even if I detect it is not
> satisfied (would be very cheap but prevent existing code from "working"). In
> that case, the elementary divisors (D_i) will not be integral ideals, and
> statements like
>
>  M ~ Z_K / D_1 + ... + Z_K/D_n
>
> become rather pointless.
>
>
> All the above was committed to the "testing / unstable" svn repository.
>
> Thanks for your report !
>
>    K.B.
>
> P.S: in current svn, your example can be simplified to
>
>  E = nfinit(x^2 - x + 2);
>  M = [1, 0, x; 0, x, 0; 0,0,2+x];
>  N = [1, 1, 1];
>  nfsnf(E, [M, N, N])
>
> ... and returns the expected
>
> %4 = [[8, 2; 0, 1], [2, 0; 0, 1], [1, 0; 0, 1]]
>
> In fact, disregarding the possible simplification, it *must* be changed since
> nfalgtobasis no longer applies recursively on t_VEC / t_COL / t_MAT, so
>
>  MM = nfalgtobasis(E, M);
>
> would no longer work. The function
>
>  MM = matalgtobasis(E, M);
>
> should be used instead. But in fact, this step has become completely
> unnecessary since number field elements in arbitrary form are now accepted in
> relative matrices. Just like "ideal lists" can now accept ideals in any form,
> hence the "1" above instead of matid(2).
>
> P.S2: The reason why nfalgtobasis was changed to no longer be recursive is that
> now it can convert arbitrary number field elements to "basis form". (Just
> like nfbasistoalg converted arbitrary elements to "algebraic form".)
>
> Before the change, it converted elements *NOT* already in basis form to basis
> form, and returned "junk" (vector of vectors) when applied to elements in
> "basis form".
>
> --
> Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
> Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
> 351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
> F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
> `
>