Opened 7 years ago

Closed 7 years ago

# enumerate_totallyreal_fields_prim does not return polynomial as elements of a polynomial ring

Reported by: Owned by: ppurka major sage-6.2 algebra Punarbasu Purkayastha Francis Clarke N/A 7e86783 (Commits) 7e86783229f55e02a208c767747219d73261cdb0

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.

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.

### comment:1 in reply to: ↑ description ; follow-up: ↓ 2 Changed 7 years ago by fwclarke

[...] 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)

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 of`enumerate_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_*`

### comment:7 follow-up: ↓ 8 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

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:

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

 ​550bce7 `Merge remote-tracking branch 'origin/develop' into ticket/15552` ​f66afcc `Fix 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:

 ​026336a `Merge branch 'develop' into ticket/15552` ​7e86783 `fix 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.