enumerate_totallyreal_fields_prim does not return polynomial as elements of a polynomial ring

[ppurka]

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,

1. the first entry of each list should belong to Sage's Integer ring instead of being just a python int.
2. the functions enumerate_totallyreal_fields_all and enumerate_totallyreal_fields_rel should get the same fix.

Component: algebra

Author: Punarbasu Purkayastha

Branch/Commit: 7e86783

Reviewer: Francis Clarke

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

[sagetrac-fwclarke]

Replying to @ppurka:

[...]
In fact, there is no nice way to directly get the polynomial, as in an element of PolynomialRing(QQ) [...]

The only way to do this is this lengthy and tedious procedure:

[...]

It's not that lengthy, but rather simpler is to relace the line

sage: Epol = sum(x**i * _ for i,_ in enumerate(Ecoef)) 

by

sage: Epol = x.parent()(Ecoef)

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.

Yes, this should certainly be changed. And it would also be better if the integer returned was a Sage Integer. At the moment E[0][0].factor() fails.

[ppurka]

comment:2

Replying to @sagetrac-fwclarke:

Yes, this should certainly be changed. And it would also be better if the integer returned was a Sage Integer. At the moment E[0][0].factor() fails.

Indeed.

This is also a problem with all the other enumerate_totallyreal_* functions.

[ppurka]

comment:3

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.

[ppurka]

Branch: u/ppurka/ticket/15552

[sagetrac-fwclarke]

comment:6

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 when return_seqs=True is not explained);
• other features not standard in Sage (e.g., built-in file output);
• too few doctests;
• over-dependence 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_*

[sagetrac-fwclarke]

Commit: a31f831

[sagetrac-fwclarke]

Reviewer: Francis Clarke

[ppurka]

comment:7

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.

[sagetrac-fwclarke]

comment:8

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.

[ppurka]

comment:9

Ok. I will do this next week, when my colleague will be back. :-)

[sagetrac-git]

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!

[sagetrac-git]

Changed commit from a31f831 to d67b6c3

[ppurka]

comment:11

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^2-2)
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]]

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

550bce7	Merge remote-tracking branch 'origin/develop' into ticket/15552
f66afcc	Fix order of output for m=1

[sagetrac-git]

Changed commit from d67b6c3 to f66afcc

[ppurka]

comment:13

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.

[sagetrac-fwclarke]

comment:16

All looks good.

[vbraun]

Author: Punarbasu Purkayastha

[vbraun]

comment:18

Documentation does not build

[number_fi] /home/release/Sage/local/lib/python2.7/site-packages/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/custom-sphinx-build.py", line 185, in <module>
    sphinx.cmdline.main(sys.argv)
  File "/home/release/Sage/local/lib/python2.7/site-packages/Sphinx-1.1.2-py2.7.egg/sphinx/cmdline.py", line 206, in main
    print >>error
  File "/home/release/Sage/src/doc/common/custom-sphinx-build.py", line 165, in write
    self._write(str)
  File "/home/release/Sage/src/doc/common/custom-sphinx-build.py", line 139, in _write
    self._log_line(line)
  File "/home/release/Sage/src/doc/common/custom-sphinx-build.py", line 108, in _log_line
    raise OSError(line)
OSError: [number_fi] /home/release/Sage/local/lib/python2.7/site-packages/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.

[ppurka]

comment:19

That's strange.

I don't have the latest dev version on my laptop. Will take me a day to fix this.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

026336a	Merge branch 'develop' into ticket/15552
7e86783	fix broken documentation build.

[sagetrac-git]

Changed commit from f66afcc to 7e86783

[ppurka]

comment:21

This should be fixed now.

[vbraun]

Changed branch from u/ppurka/ticket/15552 to 7e86783