Re: factorization of Gaussian integers

[William Stein]

On Wed, Feb 24, 2010 at 1:21 PM, Paul Zimmermann
<Paul.Zi...@loria.fr> wrote:
>       William, David,
>
> Matjaz Kovse here at SD20 asked how to factor Gaussian integers in Sage.
> I found an example in rings/number_field/number_field.py around line 13753,
> and told him.
>
> However the following seems strange to me, but maybe it is because I don't
> know enough about number fields:
>
> sage: K.<I> = NumberField(x^2 + 1)
> sage: a=K.factor(2); a
> (Fractional ideal (I + 1))^2
>
> What is strange is that (I+1)^2 gives 2I and not 2! However a.expand() gives
> the correct result:

For better or worse, the factor method on a number field is a general
function that factors a number as a product of prime *ideals*.

Here i = sqrt(-1) is a *unit* in the ring Z[i], and is only up to units.

-- William

>
> sage: a.expand()
> Fractional ideal (2)
>
> Now consider the following:
>
> sage: b=K.factor(2*I); b
> (Fractional ideal (I + 1))^2
>
> Here (I+1)^2 gives 2I which is ok, but:
>
> sage: b.expand()
> Fractional ideal (2)
>
> Why don't we get 2I here? If this is not the right way to factor Gaussian
> integers, then number_field.py should be updated, and what is the right way?
>
> Paul
>

--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

[Chris Wuthrich]

I started to implement the factorisation of Gaussian Integers (because
I needed it for my number theory course), but I never decided if it
would be a good idea to actually change it in sage. The patch at

http://trac.sagemath.org/sage_trac/ticket/7545

may not apply any more to the current version. (And it is certainly
not the intended as such to be included). But the question remains, if
we should, like pari, treat "I" as an element of the euclidian ring
Z[i].

Chris.

[David R. Kohel]

Dear Paul (and sage-nt),

It would be nice to have factorization in Euclidean domains, but the hard
issues concern not the algorithm but the syntax (for the various possible
factorizations one might expect or request).

I'm not convinced that factorization of an element should return the ideal
factorization. In fields of fractions of Euclidean domains (e.g. QQ, k[x])
one might want or expect the unique factorization into prime elements.

I define this for myself in my Magma shell:

sage: magma.eval("Factorization(2/3);")
'[ <2, 1>, <3, -1> ]'

In that case, one would expect Sage to extend the nice syntax of polynomial
factorizaton:

sage: fac = factor(-x); fac
(-1) * x
sage: fac[0]
(x, 1)
sage: fac.un
fac.unit fac.universe
sage: fac.unit()
-1

On the other hand, such a convenient syntax would conflict with the global
definition of factorization in fields. For field elements, one needs a
coherent syntax for:

1. Factorization of field elements: factor(u) returns (u) * 1 when u != 0:

sage: factor(QQ(2))
2
sage: fac = factor(QQ(2))
sage: len(fac)
1
sage: fac.unit()
1

Here this is already not consistent with integer or polynomial factorization,
where the unit part is stored separately:

sage: P.<x> = PolynomialRing(QQ)
sage: fac = factor(-x); fac
(-1) * x
sage: len(fac)
1
sage: fac = factor(P(-1)); fac
-1
sage: len(fac)
0

2. Factorization of u in a field of fractions of a Euclidean domain [or PID]
into prime elements (with unit), as Paul and Matjaz expected.

3. Factorization in the field of fractions of a Dedekind domain into prime
ideals.

This aside, I note that this should be the corrent syntax for factorization
of a Gaussian INTEGER:

sage: O = K.maximal_order()
sage: t = O(2)
sage: t.factor()

which isn't implemented (but see Chris Wuthrich's message).

Cheers,

David (also here at Sage Days 20)