Opened 7 years ago
Closed 7 years ago
#15552 closed defect (fixed)
enumerate_totallyreal_fields_prim does not return polynomial as elements of a polynomial ring
Reported by:  ppurka  Owned by:  

Priority:  major  Milestone:  sage6.2 
Component:  algebra  Keywords:  
Cc:  Merged in:  
Authors:  Punarbasu Purkayastha  Reviewers:  Francis Clarke 
Report Upstream:  N/A  Work issues:  
Branch:  7e86783 (Commits)  Commit:  7e86783229f55e02a208c767747219d73261cdb0 
Dependencies:  Stopgaps: 
Description (last modified by )
The function enumerate_totallyreal_fields_prim
is supposed to return, according to its description,
OUTPUT: the list of fields with entries "[d,f]", where "d" is the discriminant and "f" is a defining polynomial, sorted by discriminant.
Let us look at an output:
sage: E = enumerate_totallyreal_fields_prim(2, 10); E [[5, x^2  x  1], [8, x^2  2]] sage: E[0][1].parent() Interface to the PARI C library
We notice from here that the polynomial does not actually belong to the polynomial ring of QQ
. In fact, there is no nice way to directly get the polynomial, as in an element of PolynomialRing(QQ)
from E[0][1]
, which can be then used to construct the number field.
The only way to do this is this lengthy and tedious procedure:
sage: Ecoef = [QQ(_) for _ in E[0][1].list()] sage: x = polygen(QQ) sage: Epol = sum(x**i * _ for i,_ in enumerate(Ecoef)) sage: Epol, Epol.parent() (x^2  x  1, Univariate Polynomial Ring in x over Rational Field)
The output of the function itself should give back elements of the polynomial ring, instead of giving us elements which are simply output of pari.
Additionally,
 the first entry of each list should belong to Sage's
Integer
ring instead of being just a pythonint
.  the functions
enumerate_totallyreal_fields_all
andenumerate_totallyreal_fields_rel
should get the same fix.
Change History (22)
comment:1 in reply to: ↑ description ; followup: ↓ 2 Changed 7 years ago by
comment:2 in reply to: ↑ 1 Changed 7 years ago by
 Description modified (diff)
Replying to fwclarke:
Yes, this should certainly be changed. And it would also be better if the integer returned was a Sage
Integer
. At the momentE[0][0].factor()
fails.
Indeed.
This is also a problem with all the other enumerate_totallyreal_*
functions.
comment:3 Changed 7 years ago by
 Created changed from 12/20/13 08:44:48 to 12/20/13 08:44:48
 Modified changed from 12/20/13 11:32:33 to 12/20/13 11:32:33
Adding some patches to fix this. I introduce a new keyword that can be set to False to give Sage objects. By default, the new keyword does not change the current behavior of these functions. This is needed because the functions are used internally, and possibly by others to.
comment:4 Changed 7 years ago by
 Branch set to u/ppurka/ticket/15552
comment:5 Changed 7 years ago by
 Modified changed from 12/20/13 14:05:15 to 12/20/13 14:05:15
 Status changed from new to needs_review
comment:6 Changed 7 years ago by
 Commit set to a31f831bfd92e4fa139d12f951b7b12be9a41c55
 Reviewers set to Francis Clarke
 Status changed from needs_review to needs_work
The patches do not deal with the trivial n=1
case ofenumerate_totallyreal_fields_prim
. However, the code for this trivial case has never worked. It needs to be moved earlier, before the line
T = tr_data(n_int,B,a)
which causes an error when n==1
(because of a call to hermite_constant(0)
). Similar remarks apply to enumerate_totallyreal_fields_rel
when m=1
.
There are many other problems with these functions:
 poor documentation (e.g., the meaning of the four integers
counts
which are output whenreturn_seqs=True
is not explained);  other features not standard in Sage (e.g., builtin file output);
 too few doctests;
 overdependence on PARI (e.g., the following works, as in the doctest:
sage: enumerate_totallyreal_fields_rel(NumberField(x^2  2, 't'), 2, 2000) [[1600, x^4  6*x^2 + 4, xF^2 + xF  1]]
but
sage: enumerate_totallyreal_fields_rel(NumberField(x^2  2, 'a'), 2, 2000) Traceback (most recent call last) ... PariError: incorrect type in gsigne
In Sage, unlike PARI, the names of variable/generators should not matter.)
But I suppose these are for a different ticket.
New commits:
a31f831  add more fixes for enumerate_totallyreal_*

aa82d85  fix output of enumerate_totallyreal_*

comment:7 followup: ↓ 8 Changed 7 years ago by
Number theory is not my area at all. I just fixed what I could! I will have to ask a friend or colleague to understand the output.
If you have a ready explanation for the variables/output, please go ahead and add them to the documentation. These functions themselves are very old and poorly documented, as you have noticed.
comment:8 in reply to: ↑ 7 Changed 7 years ago by
Replying to ppurka:
If you have a ready explanation for the variables/output, please go ahead and add them to the documentation. These functions themselves are very old and poorly documented, as you have noticed.
I see that with verbose=True
a brief description, but not one that I can fully understand, is given of the four counts.
I would suggest making just the minimal changes required to allow Sage output and to cover the trivial cases and leaving it to someone who understands the algorithm (which I don't) to do the rewrite needed to modernise the functions.
comment:9 Changed 7 years ago by
Ok. I will do this next week, when my colleague will be back. :)
comment:10 Changed 7 years ago by
 Commit changed from a31f831bfd92e4fa139d12f951b7b12be9a41c55 to d67b6c35baf378c3362f38b8b8c8c8dcc661602f
Branch pushed to git repo; I updated commit sha1. New commits:
7ee1896  merge develop on to ticket #15552

0cc8d70  stop counting polynomials twice

f78fa37  Ensure that value of n=1, m=1 works.

d1767f9  fix the documentation for the enumerate_totally_real*

980d38f  make sure the output for n=1, or m=1 is a sage object

a4ec8a2  doctest for _rel was incorrect

d67b6c3  the doctstring syntax is not latex syntax!

comment:11 Changed 7 years ago by
This is still not completely ready for review  need to verify that the outputs are fine. But you can look into the changes if you want.
I am actually not confident that the functions give the output corresponding to the documentation! The statements that we get with verbose=True
do not match the output (for example the discriminant bound). I guess we can just fix the output here and leave the actual program to someone who knows this stuff inside out.
Here is a sample run after my patches.
sage: ZZx = ZZ['x'] sage: F.<t> = NumberField(x^22) sage: enumerate_totallyreal_fields_rel(F, 2, 2000, verbose=True) # m=2 ==> [t  1, t + 1, 1] has discriminant 2624 > B ==> [1, t + 1, 1] has discriminant 2624 > B ==> [2, 1, 1] is not absolutely irreducible ==> [1, t, 1] has discriminant 2304 > B ==> [t  1, t, 1] is not squarefree ==> [t  1, t, 1] is not squarefree ==> [2, 0, 1] is not squarefree ==> [t  2, 0, 1] has discriminant 2048 > B ==> [t  2, 0, 1] has discriminant 2048 > B ================================================================================ Polynomials tested: 9 Polynomials with discriminant with large enough square divisior: 6 Irreducible polynomials: 5 Polynomials with nfdisc <= B: 0 [1600, x^4  6*x^2 + 4, xF^2 + xF  1] [[1600, x^4  6*x^2 + 4, xF^2 + xF  1]] # return_seqs returns four numbers corresponding to the numbers above sage: enumerate_totallyreal_fields_rel(F, 2, 2000, return_seqs=True) [[9, 6, 5, 0], [[1600, [4, 0, 6, 0, 1], [1, 1, 1]]]] # Testing m=1 which wasn't working before sage: enumerate_totallyreal_fields_rel(F, 1, 2000, verbose=True) # m=1 [[1, x  1, [2, 0, 1]]]  SECOND FUNCTION  Let us try the _all function which calls _rel sage: enumerate_totallyreal_fields_all(2, 10, return_seqs=True) [[0, 0, 0, 0], [[5, [1, 1, 1]], [8, [2, 0, 1]]]] sage: enumerate_totallyreal_fields_all(2, 10) [[5, x^2  x  1], [8, x^2  2]] # the verbose output sage: enumerate_totallyreal_fields_all(2, 10, verbose=True) ================================================================================ Polynomials tested: 0 Polynomials with sssd poldisc: 0 Irreducible polynomials: 0 Polynomials with nfdisc <= B: 0 [5, x^2  x  1] [8, x^2  2] ================================================================================ Polynomials tested: 0 Polynomials with discriminant with large enough square divisior: 0 Irreducible polynomials: 0 Polynomials with nfdisc <= B: 0 [5, x^2  x  1] [8, x^2  2] [[5, x^2  x  1], [8, x^2  2]] # the case n=1 sage: enumerate_totallyreal_fields_all(1, 10, verbose=True) ================================================================================ Polynomials tested: 0 Polynomials with discriminant with large enough square divisior: 0 Irreducible polynomials: 0 Polynomials with nfdisc <= B: 0 [1, x  1] [[1, x  1]]  THIRD FUNCTION  # the third function sage: enumerate_totallyreal_fields_prim(5,5**7) [[14641, x^5  x^4  4*x^3 + 3*x^2 + 3*x  1], [24217, x^5  5*x^3  x^2 + 3*x + 1], [36497, x^5  2*x^4  3*x^3 + 5*x^2 + x  1], [38569, x^5  5*x^3 + 4*x  1], [65657, x^5  x^4  5*x^3 + 2*x^2 + 5*x + 1], [70601, x^5  x^4  5*x^3 + 2*x^2 + 3*x  1]] sage: enumerate_totallyreal_fields_prim(5,5**7,verbose=True) ================================================================================ Polynomials tested: 953 Polynomials with sssd poldisc: 359 Irreducible polynomials: 191 Polynomials with nfdisc <= B: 38 [14641, x^5  x^4  4*x^3 + 3*x^2 + 3*x  1] [24217, x^5  5*x^3  x^2 + 3*x + 1] [36497, x^5  2*x^4  3*x^3 + 5*x^2 + x  1] [38569, x^5  5*x^3 + 4*x  1] [65657, x^5  x^4  5*x^3 + 2*x^2 + 5*x + 1] [70601, x^5  x^4  5*x^3 + 2*x^2 + 3*x  1] [[14641, x^5  x^4  4*x^3 + 3*x^2 + 3*x  1], [24217, x^5  5*x^3  x^2 + 3*x + 1], [36497, x^5  2*x^4  3*x^3 + 5*x^2 + x  1], [38569, x^5  5*x^3 + 4*x  1], [65657, x^5  x^4  5*x^3 + 2*x^2 + 5*x + 1], [70601, x^5  x^4  5*x^3 + 2*x^2 + 3*x  1]] # the case n = 1 sage: enumerate_totallyreal_fields_prim(1,7, verbose=True) [[1, x  1]]
comment:12 Changed 7 years ago by
 Commit changed from d67b6c35baf378c3362f38b8b8c8c8dcc661602f to f66afcc9a249d951ca839bb58fc8d3faee766cfb
comment:13 Changed 7 years ago by
 Modified changed from 01/19/14 05:38:40 to 01/19/14 05:38:40
Final fix is the output for m=1
. Thanks to my friend Xiaolu Hou for
pointing out the error. The doctest contains the corrected output now.
comment:14 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:15 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:16 Changed 7 years ago by
 Status changed from needs_review to positive_review
All looks good.
comment:17 Changed 7 years ago by
comment:18 Changed 7 years ago by
Documentation does not build
[number_fi] /home/release/Sage/local/lib/python2.7/sitepackages/sage/rings/number_field/totallyreal_rel.py:docstring of sage.rings.number_field.totallyreal_rel:37: WARNING: Bullet list ends without a blank line; unexpected unindent. Traceback (most recent call last): File "/home/release/Sage/src/doc/common/builder.py", line 83, in f execfile(sys.argv[0]) File "/home/release/Sage/src/doc/common/customsphinxbuild.py", line 185, in <module> sphinx.cmdline.main(sys.argv) File "/home/release/Sage/local/lib/python2.7/sitepackages/Sphinx1.1.2py2.7.egg/sphinx/cmdline.py", line 206, in main print >>error File "/home/release/Sage/src/doc/common/customsphinxbuild.py", line 165, in write self._write(str) File "/home/release/Sage/src/doc/common/customsphinxbuild.py", line 139, in _write self._log_line(line) File "/home/release/Sage/src/doc/common/customsphinxbuild.py", line 108, in _log_line raise OSError(line) OSError: [number_fi] /home/release/Sage/local/lib/python2.7/sitepackages/sage/rings/number_field/totallyreal_rel.py:docstring of sage.rings.number_field.totallyreal_rel:37: WARNING: Bullet list ends without a blank line; unexpected unindent.
comment:19 Changed 7 years ago by
That's strange.
I don't have the latest dev version on my laptop. Will take me a day to fix this.
comment:20 Changed 7 years ago by
 Commit changed from f66afcc9a249d951ca839bb58fc8d3faee766cfb to 7e86783229f55e02a208c767747219d73261cdb0
 Status changed from positive_review to needs_review
comment:21 Changed 7 years ago by
 Status changed from needs_review to positive_review
This should be fixed now.
comment:22 Changed 7 years ago by
 Branch changed from u/ppurka/ticket/15552 to 7e86783229f55e02a208c767747219d73261cdb0
 Resolution set to fixed
 Status changed from positive_review to closed
Replying to ppurka:
[...]
It's not that lengthy, but rather simpler is to relace the line
by
Yes, this should certainly be changed. And it would also be better if the integer returned was a Sage
Integer
. At the momentE[0][0].factor()
fails.