Trac #16894: bug in is_square over number fields

A bug in pari 2.7.1 causes this:
{{{
sage: K.<a> = QuadraticField(22)
sage: u = 42*a - 197 # fundamental unit
sage: D = u^14
sage: D.is_square()
MemoryError: Unable to allocate 327680000000 bytes for the PARI stack
(instead, allocated 262144000000 bytes)
}}}
This was reported upstream: [http://pari.math.u-bordeaux.fr/archives
/pari-users-1406/msg00006.html]

Upstream fixed this in their git master:
{{{
Not a memory issue indeed. The low-level function from the polroots
module that (sharply) estimates the largest modulus of a polynomial
T can't handle the case T(0) = 0 (nor the case where T is constant,
but that's not the issue here...).

It never occurs in the original context of polroots(), but it can occur
in the context of nfroots / nffactor that call it with T := the image
through the successive complex embeddings of our algebraic polynomial.

Fixed in master (2.8.*). Thanks for your report !
}}}

URL: http://trac.sagemath.org/16894
Reported by: cremona
Ticket author(s): Jeroen Demeyer
Reviewer(s): John Cremona
Trac #16910: Get rid of mpz_t_offset hacks in integer.pyx

The comment "Accessing the `.value` attribute of an `Integer` object
causes Cython to refcount it." is no longer true, so we don't need this
hack anymore.

URL: http://trac.sagemath.org/16910
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer
Reviewer(s): Volker Braun
Trac #16913: Error in prev()

There is a flaw in the prev() method in combinat/permutation.py.
Here is an example.
{{{
sage: Permutation([1,4,3,2]).prev()
[1, 2, 4, 3]
}}}

The output should be [1, 4, 2, 3].

URL: http://trac.sagemath.org/16913
Reported by: ayyer
Ticket author(s): André Apitzsch
Reviewer(s): Arvind Ayyer
Trac #16927: Add Sage interface for PARI functions ffprimroot, fflog, fforder

This ticket deals only with adding these functions to
`src/sage/libs/pari/gen.pyx`.

Applications:
* #8373: add `modulus=primitive` argument for finite field constructor.

URL: http://trac.sagemath.org/16927
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer
Reviewer(s): Peter Bruin
Trac #16043: Hilbert Symbol introduces bugs from Pari

For a field F and for a prime p, ( , )_p denotes the Hilbert Symbol over
F localized at p.  It is well known that (a,b)_p*(a,c)_p=(a,bc)_p for
any a, b in F (cf O'meara 63:12).  But I'm getting:

{{{
sage: K.<a>=NumberField(x^2+5)
sage: p=K.primes_above(2)[0];p
Fractional ideal (2, a + 1)
sage: K.hilbert_symbol(2*a,-1,p)
1
sage: K.hilbert_symbol(2*a,2,p)
1
sage: K.hilbert_symbol(2*a,-2,p)
-1
}}}

This is an upstream problem: [http://pari.math.u-bordeaux.fr/cgi-
bin/bugreport.cgi?bug=1561] and the follow-up
[http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1569]

URL: http://trac.sagemath.org/16043
Reported by: annahaensch
Ticket author(s): Anna Haensch, Peter Bruin
Reviewer(s): Peter Bruin, Jeroen Demeyer
Trac #16799: clique polynomial of a graph

Add a method for computing the
[http://mathworld.wolfram.com/CliquePolynomial.html clique polynomial]
of a graph.

URL: http://trac.sagemath.org/16799
Reported by: amri
Ticket author(s): Amritanshu Prasad
Reviewer(s): Frédéric Chapoton, Nathann Cohen
Trac #16838: make affine and projective dehomogenize and homogenize work together

There are a number of issues currently with the `homogenization` and
`dehomogenization` functionality. Essentially, what I'd like to see is
that dehomogenizing and then homogenizing returns basically the same
object. Currently dehomogenization is using `AffinePatch`, but
homogenization is creating a new projective space every time. This
causes a number of funny behaviors so should instead be using projective
embedding. I'd like to see tests of the following form return `True`:

{{{
P.<x,y,z>=ProjectiveSpace(QQ,2)
H=End(P)
f=H([x*y,y^2,z^2])
n=1
f.dehomogenize(n).homogenize(n)==f
}}}

{{{
A.<x,y>=AffineSpace(QQ,2)
H=End(A)
f=H([x*y,y^2])
n=0
f.homogenize(n).dehomogenize(n)==f
}}}

This also requires having the `affine_patch` and `projective_embedding`
play nicely together. Fixing this would also allow objects homogenized
or dehomogenized from the same space to then live in the same new space.
The same for points and currently there is no homogenization function at
all for affine points.

I've started working on this and just need to fix a couple more things.

URL: http://trac.sagemath.org/16838
Reported by: bhutz
Ticket author(s): Ben Hutz
Reviewer(s): Joao de Faria
Trac #16881: Rename number field __pari_* attributes to _pari_*

The method `NumberField_generic.pari_bnf()` does not detect if the PARI
`bnf` has already been certified and therefore always calls
`bnfcertify()`.  This is due to name-mangling of double-underscore
attributes; more precisely, in
{{{
getattr(self, "__pari_bnf_certified", False)
}}}
This can be solved by renaming all `__pari_*` attributes to `_pari_*`
(`*` = `bnf`, `bnf_certified`, `nf`, `polynomial`).

URL: http://trac.sagemath.org/16881
Reported by: pbruin
Ticket author(s): Peter Bruin
Reviewer(s): Jeroen Demeyer
Trac #16903: bugfix for database_cremona_ellcurve optional spkg

The following (requires optional database_cremona_ellcurve) reveals a
problem:
{{{
sage: CremonaDatabase().largest_conductor()
349999
sage: E = EllipticCurve([0,1,0,-141083,-20443787])
sage: E.conductor()
246400
sage: E.label()
...
RuntimeError: Cremona label not known for Elliptic Curve defined by y^2
= x^3 + x^2 - 141083*x - 20443787 over Rational Field.
sage: E = EllipticCurve([0,-1,0,-16,421])
sage: E.conductor()
252840
sage: E.label()
RuntimeError: Cremona label not known for Elliptic Curve defined by y^2
= x^3 - x^2 - 16*x + 421 over Rational Field.
}}}
which was reported by Benjamin Matschke and Rafael von Kanel on
2014-08-28.  The database files are missing all curves with conductors
in the ranges 246400-246499 and 252800-252899, in total 1455 elliptic
curves in 962 isogeny classes.  I am making an update to the
database_cremona_ellcurve option spkg.

New tarball :
* http://boxen.math.washington.edu/home/cremona/database_cremona_ellcurv
e-20140829.tar.bz2

URL: http://trac.sagemath.org/16903
Reported by: cremona
Ticket author(s): John Cremona
Reviewer(s): Volker Braun
Trac #16906: Fix trivial docstring indendation error in misc.decorators.decorator_keywords

Removed one blank in order to fix indentation error introduced in #15657
and visible at http://www.sagemath.org/doc/reference/misc/sage/misc/deco
rators.html#sage.misc.decorators.decorator_keywords

URL: http://trac.sagemath.org/16906
Reported by: cheuberg
Ticket author(s): Clemens Heuberger
Reviewer(s): Travis Scrimshaw
Trac #16914: Generic graphs / is_subgraph, documentation typo

Examples for `is_subgraph` are not formatted correctly: http://www.sagem
ath.org/doc/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.
generic_graph.GenericGraph.is_subgraph

URL: http://trac.sagemath.org/16914
Reported by: jmantysalo
Ticket author(s): Jori Mäntysalo
Reviewer(s): Nathann Cohen
Trac #16879: OA caching in C

Caching of OA constructions in C. Less space, and a bit faster.

Nathann

URL: http://trac.sagemath.org/16879
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Vincent Delecroix
Trac #16884: Quasi-difference matrices (database+is_QDM)

A new database entry for quasi-difference matrices. As a result:

- The Vmt vectors are added to the quasi-difference matrices database
entry, and not anymore to `OA_constructions`

- The old OA constructions based on QDM are converted to QDM
constructors.

- The OA constructor now queries the QDM database entry (and so it gets
the QDM+Vmt)

Two notes:

- There is no `is_quasi_difference_matrix` right now, so the QDM are
tested through the OA they generate.

- There is no `designs.quasi_difference_matrix` because I did not know
how to write it in such a way that it would be easy to find a QDM that
builds an OA. The problem is that a QDM is defined with 5 parameters
`(n,_,_,_,u)` and that the `n` of an `OA(k,n)` is the sum `n+u`.
Consequently, if you want to build an `OA(k,n)` from a QDM you must try
all pairs `n'+u = n` and that's a waste of time.

- Right now the DM are not added to the dictionary of QDM. I did not see
the point, given that the DM are already queried by
`orthogonal_arrays()` through their constructor (which will also contain
additional constructions of DM).

URL: http://trac.sagemath.org/16884
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Vincent Delecroix
Trac #16887: Wider MOLS table plus better interface

With this patch the MOLS table can be printed for values n>1000 with a
correct alignment, and you can also pick an interval of values of n you
are interested in.

Nathann

URL: http://trac.sagemath.org/16887
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Vincent Delecroix
Trac #15946: Cython warnings about mpz_t ("... referenced before assignment")

Similar to #16583, we should fix the declarations for `mpz_t` (and
related types). This also involves fixing:
* various bad usages of `mpz_t` (it was `ctypedef`'ed as `void*`,
meaning you could do with it what you wanted and Cython wouldn't
complain)
* changing many functions to pass an `mpz_t` instead of an `mpz_t*`. For
example the NTL interface functions `mpz_to_ZZ` and `ZZ_to_mpz` and the
`pow_computer` functions from p-adics.

See also [https://groups.google.com/forum/#!msg/sage-
devel/bs4lnNwbINs/B2iVgxK7pCYJ]

URL: http://trac.sagemath.org/15946
Reported by: mmezzarobba
Ticket author(s): Jeroen Demeyer
Reviewer(s): Volker Braun
Trac #16851: Implement direct sum and tensor products for chain complexes and Koszul complexes

There is a natural way to construct a chain complex from the direct sum
(Cartesian product) and tensor product of chain complexes. This also
implements Koszul complexes.

URL: http://trac.sagemath.org/16851
Reported by: tscrim
Ticket author(s): Travis Scrimshaw
Reviewer(s): John Palmieri
Trac #8373: Construct finite fields with primitive defining polynomial

Add an argument `modulus="primitive"` to the finite field generator
`GF()` such that the chosen generator is guaranteed to be a generator of
the multiplicative group.

URL: http://trac.sagemath.org/8373
Reported by: rkirov
Ticket author(s): Jeroen Demeyer
Reviewer(s): Peter Bruin
Trac #16902: Advertise sig_check() better in the developers manual

URL: http://trac.sagemath.org/16902
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer
Reviewer(s): Vincent Delecroix, Dima Pasechnik
Trac #16930: Deprecate non-polynomial modulus argument in constructor of implementations of finite fields

The "modulus" parameter for finite fields is handled by the fancy new
`src/sage/rings/finite_rings/constructor.py` and the implementations of
finite fields should only take a polynomial as modulus.

Also improve creating prime finite fields with the non-default
implementation.

URL: http://trac.sagemath.org/16930
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer
Reviewer(s): Peter Bruin
Trac #16245: Compose isogenies

As listed in #7368, we should be able to compose isogenies.
See also discussions in #12880, comments 20 and 21.

URL: http://trac.sagemath.org/16245
Reported by: sbesnier
Ticket author(s): Sébastien Besnier
Reviewer(s): Peter Bruin