search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.37k stars 462 forks source link

Errors when computing norms of padic elements #32085

Open kliem opened 3 years ago

kliem commented 3 years ago 
sage -t --long --random-seed=3 src/sage/rings/padics/padic_generic_element.pyx
**********************************************************************
File "src/sage/rings/padics/padic_generic_element.pyx", line 1076, in sage.rings.padics.padic_generic_element.pAdicGenericElement.norm
Failed example:
    (x*y).norm() == x.norm() * y.norm()
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   1 of  11 in sage.rings.padics.padic_generic_element.pAdicGenericElement.norm
    [827 tests, 1 failure, 8.44 s]
----------------------------------------------------------------------
sage -t --long --random-seed=3 src/sage/rings/padics/padic_generic_element.pyx  # 1 doctest failed

Computing the norm of x*y can also give an arithmetic error:

sage: x                                                                                                                                                                             
(a + 1)*pi^-4 + 1 + (a + 1)*pi + a*pi^4 + a*pi^5 + (a^2 + 1)*pi^6 + (a^2 + a + 1)*pi^8 + (a^2 + a + 1)*pi^9 + pi^11 + (a^2 + a + 1)*pi^12 + (a + 1)*pi^13 + (a^2 + 1)*pi^14 + O(pi^15)
sage: y                                                                                                                                                                             
a^2*pi^-310 + (a + 1)*pi^-306 + a*pi^-302 + (a^2 + a + 1)*pi^-298 + O(pi^-294)
sage: (x*y).norm()                                                                                                                                                                  
---------------------------------------------------------------------------
ArithmeticError                           Traceback (most recent call last)
<ipython-input-283-587819ce911b> in <module>
----> 1 (x*y).norm()

/srv/public/kliem/sage/local/lib/python3.7/site-packages/sage/rings/padics/padic_generic_element.pyx in sage.rings.padics.padic_generic_element.pAdicGenericElement.norm (build/cythonized/sage/rings/padics/padic_generic_element.c:12066)()
   1079         if base is None:
   1080             base = parent.base_ring()
-> 1081         poly = self.minimal_polynomial(base=base)
   1082         polydeg = poly.degree()
   1083         extdeg = parent.absolute_degree() // (base.absolute_degree() * polydeg)

/srv/public/kliem/sage/local/lib/python3.7/site-packages/sage/rings/padics/padic_generic_element.pyx in sage.rings.padics.padic_generic_element.pAdicGenericElement.minimal_polynomial (build/cythonized/sage/rings/padics/padic_generic_element.c:11718)()
   1026                 elt *= self
   1027             W = V.span_of_basis(vectors)
-> 1028             coeffs = [ -c for c in W.coordinate_vector(vector) ] + [K(1)]
   1029             return polring(coeffs)
   1030         else:

/srv/public/kliem/sage/local/lib/python3.7/site-packages/sage/modules/free_module.py in coordinate_vector(self, v, check)
   6572         """
   6573         # First find the coordinates of v wrt echelon basis.
-> 6574         w = self.echelon_coordinate_vector(v, check=check)
   6575         # Next use transformation matrix from echelon basis to
   6576         # user basis.

/srv/public/kliem/sage/local/lib/python3.7/site-packages/sage/modules/free_module.py in echelon_coordinate_vector(self, v, check)
   6634             (1, 18)
   6635         """
-> 6636         return FreeModule(self.base_ring().fraction_field(), self.rank())(self.echelon_coordinates(v, check=check))
   6637 
   6638     def has_user_basis(self):

/srv/public/kliem/sage/local/lib/python3.7/site-packages/sage/modules/free_module.py in echelon_coordinates(self, v, check)
   6170         lc = E.linear_combination_of_rows(x)
   6171         if list(lc) != list(v):
-> 6172             raise ArithmeticError("vector is not in free module")
   6173         return x
   6174 

ArithmeticError: vector is not in free module

Same problem with trace:

sage -t --long --random-seed=6545647 src/sage/rings/padics/padic_generic_element.pyx
**********************************************************************
File "src/sage/rings/padics/padic_generic_element.pyx", line 1118, in sage.rings.padics.padic_generic_element.pAdicGenericElement.trace
Failed example:
    (x+y).trace() == x.trace() + y.trace()
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   1 of  10 in sage.rings.padics.padic_generic_element.pAdicGenericElement.trace
    [826 tests, 1 failure, 8.23 s]

In #29979, a doctest was marked not tested because of this.

Component: padics

Keywords: norm

Branch/Commit: u/caruso/padic_norm @ 2ef2a5f

Issue created by migration from https://trac.sagemath.org/ticket/32085

kliem commented 3 years ago
comment:1

I'm just going to add the trace problem here.

Maybe it is a seperate problem. I don't know.

kliem commented 3 years ago

Description changed:

--- 
+++ 
@@ -67,3 +67,21 @@

 ArithmeticError: vector is not in free module

+ +Same problem with trace: + +``` +sage -t --long --random-seed=6545647 src/sage/rings/padics/padic_generic_element.pyx +** +File "src/sage/rings/padics/padic_generic_element.pyx", line 1118, in sage.rings.padics.padic_generic_element.pAdicGenericElement.trace +Failed example:

mwageringel commented 3 years ago

Description changed:

--- 
+++ 
@@ -85,3 +85,5 @@
    1 of  10 in sage.rings.padics.padic_generic_element.pAdicGenericElement.trace
     [826 tests, 1 failure, 8.23 s]

+ +In #29979, a doctest was marked not tested because of this.

xcaruso commented 2 years ago
comment:6

I cannot reproduce your errors:

xcaruso@azerite ~/sage $ sage -t --long --random-seed=3 src/sage/rings/padics/padic_generic_element.pyx
too few successful tests, not using stored timings
Running doctests with ID 2022-06-02-22-20-21-8ee40493.
Git branch: trace_of_zero
Using --optional=debian,pip,sage,sage_spkg
Features to be detected: 4ti2,benzene,bliss,buckygen,conway_polynomials,csdp,database_cremona_ellcurve,database_cremona_mini_ellcurve,database_jones_numfield,database_knotinfo,dvipng,gfan,graphviz,imagemagick,jupymake,kenzo,latte_int,lrslib,mcqd,meataxe,nauty,palp,pandoc,pdf2svg,pdftocairo,phitigra,plantri,polytopes_db,polytopes_db_4d,pynormaliz,python_igraph,rubiks,sage.combinat,sage.geometry.polyhedron,sage.graphs,sage.groups,sage.plot,sage.rings.number_field,sage.rings.padics,sage.rings.real_double,sage.symbolic,sage_numerical_backends_coin,sagemath_doc_html,sphinx,tdlib
Doctesting 1 file.
sage -t --long --random-seed=3 src/sage/rings/padics/padic_generic_element.pyx
    [823 tests, 10.95 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 11.1 seconds
    cpu time: 10.8 seconds
    cumulative wall time: 11.0 seconds
Features detected for doctesting: 
pytest is not installed in the venv, skip checking tests that rely on it
xcaruso@azerite ~/sage $ sage -t --long --random-seed=6545647 src/sage/rings/padics/padic_generic_element.pyx
too few successful tests, not using stored timings
Running doctests with ID 2022-06-02-22-20-52-9e1c50df.
Git branch: trace_of_zero
Using --optional=debian,pip,sage,sage_spkg
Features to be detected: 4ti2,benzene,bliss,buckygen,conway_polynomials,csdp,database_cremona_ellcurve,database_cremona_mini_ellcurve,database_jones_numfield,database_knotinfo,dvipng,gfan,graphviz,imagemagick,jupymake,kenzo,latte_int,lrslib,mcqd,meataxe,nauty,palp,pandoc,pdf2svg,pdftocairo,phitigra,plantri,polytopes_db,polytopes_db_4d,pynormaliz,python_igraph,rubiks,sage.combinat,sage.geometry.polyhedron,sage.graphs,sage.groups,sage.plot,sage.rings.number_field,sage.rings.padics,sage.rings.real_double,sage.symbolic,sage_numerical_backends_coin,sagemath_doc_html,sphinx,tdlib
Doctesting 1 file.
sage -t --long --random-seed=6545647 src/sage/rings/padics/padic_generic_element.pyx
    [823 tests, 10.79 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 10.9 seconds
    cpu time: 10.8 seconds
    cumulative wall time: 10.8 seconds
Features detected for doctesting: 
pytest is not installed in the venv, skip checking tests that rely on it
mwageringel commented 2 years ago
comment:7

The doctests are marked as not tested. After enabling them, I can still reproduce the errors.

xcaruso commented 2 years ago

Branch: u/caruso/padic_norm

xcaruso commented 2 years ago
comment:9

OK. I understand the problem.

Splitting the computation of the norm into two parts (valuation and unit) seems to fix the bug.

New commits:

2ef2a5fseparate val and unit in the computation of the norm
xcaruso commented 2 years ago

Commit: 2ef2a5f