Factoring x^2 + O(3^20)

[David Roe]

Jeroen and I have been having a discussion on #15422 that I wanted to get more feedback on.  The question there is how f = x^2 + O(3^20) should factor.  Note that with infinite precision, f could be
1) x^2 = x*x
2) x^2 - 3^20 = (x - 3^10)*(x + 3^10)
3) x^2 - 3^21, which is irreducible over Q_3.

I think there are three reasonable answers.

1) f.factor() should return (x + O(3^10))^2.

2) f.factor() should raise a PrecisionError

3) f.factor() should raise a PrecisionError but f.factor(squares_ok = True) should return (x + O(3^10))^2

On #15422, we compromised on option 3, leaving the implementation of the squares_ok keyword to another ticket.  The reason that I'm a bit unhappy with this answer is due to an analogy with linear algebra.

Consider the matrices

A = matrix(Qp(3),2,2,[1,0,0,1])

B = matrix(Qp(3),2,2,[1,0,0,0])

C = matrix(Qp(3),2,2,[0,0,0,0])

The kernel of A is well defined and zero.  The kernel of B could be dimension 0 or 1, but if it is dimension 1 then we can give a reasonable answer: it's spanned by [O(3^20), 1+O(3^20)].  The kernel of C could be dimension 0, 1 or 2.

For linear algebra, I don't think we should raise a PrecisionError whenever we ask for the kernel of a possibly-positive-rank matrix.  Instead, I think that the documentation should make it clear that we return the largest-dimensional kernel possible given the known entries of the matrix.  This subspace is well defined, with a reasonable notion of precision.

In the polynomial case, such PrecisionErrors don't arise as frequently, so I'm not unhappy with the compromise option (3).  On the other hand, the lack of consistency does make me a bit uncomfortable.  Thoughts?

Also, let us know if you have any suggestions for what the keyword should be.
David

[Maarten Derickx]

Just a short reaction.

I agree with the keyword solution, but i think it should not be called
"squares_ok" since you have the same problem also with all other
powers. Maybe "factor_possible_powers" or "factor_powers".

Thanks,
Maarten

2013/12/4 David Roe <roed...@gmail.com>:

> --
> You received this message because you are subscribed to the Google Groups
> "sage-padics" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-padics...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.

[Kiran Kedlaya]

I vote for #1, on the grounds of the analogy with linear algebra: given that the shape of the factorization is not uniquely determined, one should return the finest factorization that is consistent with the data, on the grounds that this is most likely to be what the user wants. But the documentation needs to be precise enough so that the user can predict this behavior!

Kiran

[John Cremona]

This discussion reminds me of the one very long ago amongst pari
developers justifying why

(1+O(4))^2 returned 1+O(8)

while

(1+O(4))*(1+O(4)) returned 1+O(4).

Now they both return 1+O(4). The justification for the difference was
to compare (1+4x)^2 to (1+4x)*(1+4y).

John

[Xavier Caruso]

Le jeudi 5 d�cembre 2013, Kiran Kedlaya a �crit�:

> I vote for #1, on the grounds of the analogy with linear algebra:
> given that the shape of the factorization is not uniquely determined,
> one should return the finest factorization that is consistent with the
> data, on the grounds that this is most likely to be what the user
> wants. But the documentation needs to be precise enough so that the
> user can predict this behavior!

I rather agree with Kiran.

I would suggest to add an option secure such that:
. if secure is True, one raises PrecisionError if one cannot
determine certainly the number of irreducible factors
. if secure is False, one returns the finest possible factorization
and the default should be secure=False.

I have a related question: is the set of monic irreducible polynomials
of degree d over Q_p open in the set of all monic polynomials of degree
d over Q_p (for the ultrametric topology)?

--Xavier

[Xavier Caruso]

Le jeudi 5 d�cembre 2013, John Cremona a �crit�:

> This discussion reminds me of the one very long ago amongst pari
> developers justifying why
>
> (1+O(4))^2 returned 1+O(8)
>
> while
>
> (1+O(4))*(1+O(4)) returned 1+O(4).

Well, I would say that it is the correct behaviour :-)

--Xavier

[Xavier Caruso]

Le jeudi 5 d�cembre 2013, Xavier Caruso a �crit�:

> I have a related question: is the set of monic irreducible polynomials
> of degree d over Q_p open in the set of all monic polynomials of degree
> d over Q_p (for the ultrametric topology)?

I think that the picture is the following. In the set of all monic
polynomials of degree d:
. there is a closed Zariski subset Z consistinf of non squarefree
polynomial
. on the complement, the function mapping a polynomial P to the
number of its irreducible factors and their degrees is locally
constant

So I think that, by default, if some polynomial P given with finite
precision can belong to Z, then one consider that it is actually in
Z. (Compare with matrices: it a matrix given with finite precision
can be singular, then we consider that it is.)

Now, if you can be sure that the input polynomial is squarefree, it
is not completely obvious to me how to choose the shape (i.e. their
number and their degrees) of the irreducible factors if there are
several possibilities.
But, actually, I'm even not quite sure that this problem may happen.
Could you please exhibit for me (or prove that there is no) affine
lattice H in the affine space of all monic polynomials such that:
. H does not meet Z, and
. the shape function is not constant on H

--Xavier