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: sage-6.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 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.

Change History (22)

comment:1 in reply to: ↑ description ; follow-up: Changed 7 years ago by 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.

comment:2 in reply to: ↑ 1 Changed 7 years ago by ppurka

  • 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 moment E[0][0].factor() fails.

Indeed.

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

comment:3 Changed 7 years ago by ppurka

  • 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 ppurka

  • Branch set to u/ppurka/ticket/15552

comment:5 Changed 7 years ago by ppurka

  • 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 fwclarke

  • 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 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:

a31f831add more fixes for enumerate_totallyreal_*
aa82d85fix output of enumerate_totallyreal_*

comment:7 follow-up: Changed 7 years ago by ppurka

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 fwclarke

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 ppurka

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

comment:10 Changed 7 years ago by git

  • Commit changed from a31f831bfd92e4fa139d12f951b7b12be9a41c55 to d67b6c35baf378c3362f38b8b8c8c8dcc661602f

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

7ee1896merge develop on to ticket #15552
0cc8d70stop counting polynomials twice
f78fa37Ensure that value of n=1, m=1 works.
d1767f9fix the documentation for the enumerate_totally_real*
980d38fmake sure the output for n=1, or m=1 is a sage object
a4ec8a2doctest for _rel was incorrect
d67b6c3the doctstring syntax is not latex syntax!

comment:11 Changed 7 years ago by ppurka

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]]

comment:12 Changed 7 years ago by git

  • Commit changed from d67b6c35baf378c3362f38b8b8c8c8dcc661602f to f66afcc9a249d951ca839bb58fc8d3faee766cfb

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

550bce7Merge remote-tracking branch 'origin/develop' into ticket/15552
f66afccFix order of output for m=1

comment:13 Changed 7 years ago by ppurka

  • 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 ppurka

  • Status changed from needs_work to needs_review

comment:15 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:16 Changed 7 years ago by fwclarke

  • Status changed from needs_review to positive_review

All looks good.

comment:17 Changed 7 years ago by vbraun

  • Authors set to Punarbasu Purkayastha

comment:18 Changed 7 years ago by vbraun

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.

comment:19 Changed 7 years ago by ppurka

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 git

  • Commit changed from f66afcc9a249d951ca839bb58fc8d3faee766cfb to 7e86783229f55e02a208c767747219d73261cdb0
  • Status changed from positive_review to needs_review

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

026336aMerge branch 'develop' into ticket/15552
7e86783fix broken documentation build.

comment:21 Changed 7 years ago by ppurka

  • Status changed from needs_review to positive_review

This should be fixed now.

comment:22 Changed 7 years ago by vbraun

  • Branch changed from u/ppurka/ticket/15552 to 7e86783229f55e02a208c767747219d73261cdb0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.