Re: bnfisintnorm() is eager for memory

[Max Alekseyev <maxale@gmail.com>]

Hi Karim,

Thank you for the analysis.

What if I look for solutions where at least one of the coefficients is below 10^16 by absolute value? Is there a shortcut to get those or establish that there are none?

Regards,

Max

On Fri, Feb 23, 2024 at 4:52 AM Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:

* Max Alekseyev [2024-02-23 02:21]:
> In the following example, bnfisintnorm() runs out of memory even with a
> 32GB stack. Is there a way to overcome this?
>
> ? b = bnfinit('x^2-2305843005992468481,1)
> ? bnfisintnorm(b,2305843008139952128)

Not really with the current specification for the function. One could
easily obtain the solutions as "algebraic numbers in factored form", but have
a look at the simplest such solution 'y', attached to this mail:

? nfeltnorm(b, y)
%1 = 2305843008139952128

y is given by a factorization matrix, corresponding to an _expression_
\prod_i {y_i}^{e_i}, where the y_i are small algebraic integers and the
e_i are (positive or negative) integers.

Check the exponents y[,2]: its a vector with length 151 and sup-norm
5345503542932135311077290.

It's (relatively) easy to get all solutions in this form, with exponents
e_i of that magnitude. It's a completely explicit and well defined
_expression_, but no hope of expanding that as the expected t_POLMOD.

A related difficulty: b.fu has a hard time finishing as well, about 2
minutes. The result has coefficients about exp(b.reg) ~ 10^6103581
and requires about 5 MB of storage (more than 5 times the size of the
original full bnf, which contains the same data in factored form and is
computed in 0.1 s).

Cheers,

    K.B.
--
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/