GitLab

Includes a Cython function specifically targeted to fixing the sqlite3
issue, and adds a monkey-patching at sage import time which wraps
sqlite3.connect (the first place where the issue that causes this
is invoked) to call the workaround function.

Inspired by [https://ask.sagemath.org/question/42685/translation-errors-
from-fricas-to-sage/ this] ask.sagemath question.

{{{
sage: var("a")
a
sage: foo=integrate(1/(1+a*cos(x)),x, algorithm="sympy")
sage: view(foo)
\begin{cases}{-\frac{1}{\tan\left(\frac{1}{2} \, x\right)}} & {a =
\left(-1\right)}\\{\tan\left(\frac{1}{2} \, x\right)} & {a =
1}\\{\frac{\log\left(\sqrt{\frac{a}{a - 1} + \frac{1}{a - 1}} +
\tan\left(\frac{1}{2} \, x\right)\right)}{a \sqrt{\frac{a}{a - 1} +
\frac{1}{a - 1}} - \sqrt{\frac{a}{a - 1} + \frac{1}{a - 1}}} -
\frac{\log\left(-\sqrt{\frac{a}{a - 1} + \frac{1}{a - 1}} +
\tan\left(\frac{1}{2} \, x\right)\right)}{a \sqrt{\frac{a}{a - 1} +
\frac{1}{a - 1}} - \sqrt{\frac{a}{a - 1} + \frac{1}{a - 1}}}} &
{1}\end{cases}
An error occurred.
This is pdfTeX, Version 3.14159265-2.6-1.40.19 (TeX Live 2018/Debian)
(preloaded format=pdflatex 2018.6.6)  21 JUN 2018 00:39
entering extended mode
 restricted \write18 enabled.
 %&-line parsing enabled.
**\nonstopmode \input{sage.tex} %% EC, for better readibility : **
(./sage.tex (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls
Document Class: article 2014/09/29 v1.4h Standard LaTeX document class
(/usr/share/texlive/texmf-dist/tex/latex/base/size10.clo
File: size10.clo 2014/09/29 v1.4h Standard LaTeX file (size option)
)
\c@part=\count80
\c@section=\count81
\c@subsection=\count82
\c@subsubsection=\count83
\c@paragraph=\count84
\c@subparagraph=\count85
\c@figure=\count86
\c@table=\count87
\abovecaptionskip=\skip41
\belowcaptionskip=\skip42
\bibindent=\dimen102
)
(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty
Package: amsmath 2017/09/02 v2.17a AMS math features
\@mathmargin=\skip43

For additional information on amsmath, use the `?' option.
(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty
Package: amstext 2000/06/29 v2.01 AMS text

(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty
File: amsgen.sty 1999/11/30 v2.0 generic functions
\@emptytoks=\toks14
\ex@=\dimen103
))
(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty
Package: amsbsy 1999/11/29 v1.2d Bold Symbols
\pmbraise@=\dimen104
)
(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty
Package: amsopn 2016/03/08 v2.02 operator names
)
\inf@bad=\count88
LaTeX Info: Redefining \frac on input line 213.
\uproot@=\count89
\leftroot@=\count90
LaTeX Info: Redefining \overline on input line 375.
\classnum@=\count91
\DOTSCASE@=\count92
LaTeX Info: Redefining \ldots on input line 472.
LaTeX Info: Redefining \dots on input line 475.
LaTeX Info: Redefining \cdots on input line 596.
\Mathstrutbox@=\box26
\strutbox@=\box27
\big@size=\dimen105
LaTeX Font Info:    Redeclaring font encoding OML on input line 712.
LaTeX Font Info:    Redeclaring font encoding OMS on input line 713.
\macc@depth=\count93
\c@MaxMatrixCols=\count94
\dotsspace@=\muskip10
\c@parentequation=\count95
\dspbrk@lvl=\count96
\tag@help=\toks15
\row@=\count97
\column@=\count98
\maxfields@=\count99
\andhelp@=\toks16
\eqnshift@=\dimen106
\alignsep@=\dimen107
\tagshift@=\dimen108
\tagwidth@=\dimen109
\totwidth@=\dimen110
\lineht@=\dimen111
\@envbody=\toks17
\multlinegap=\skip44
\multlinetaggap=\skip45
\mathdisplay@stack=\toks18
LaTeX Info: Redefining \[ on input line 2817.
LaTeX Info: Redefining \] on input line 2818.
)
(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty
Package: amssymb 2013/01/14 v3.01 AMS font symbols

(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty
Package: amsfonts 2013/01/14 v3.01 Basic AMSFonts support
\symAMSa=\mathgroup4
\symAMSb=\mathgroup5
LaTeX Font Info:    Overwriting math alphabet `\mathfrak' in version
`bold'
(Font)                  U/euf/m/n --> U/euf/b/n on input line 106.
))
(/usr/share/texlive/texmf-dist/tex/latex/graphics/graphicx.sty
Package: graphicx 2017/06/01 v1.1a Enhanced LaTeX Graphics (DPC,SPQR)

(/usr/share/texlive/texmf-dist/tex/latex/graphics/keyval.sty
Package: keyval 2014/10/28 v1.15 key=value parser (DPC)
\KV@toks@=\toks19
)
(/usr/share/texlive/texmf-dist/tex/latex/graphics/graphics.sty
Package: graphics 2017/06/25 v1.2c Standard LaTeX Graphics (DPC,SPQR)

(/usr/share/texlive/texmf-dist/tex/latex/graphics/trig.sty
Package: trig 2016/01/03 v1.10 sin cos tan (DPC)
)
(/usr/share/texlive/texmf-dist/tex/latex/graphics-cfg/graphics.cfg
File: graphics.cfg 2016/06/04 v1.11 sample graphics configuration
)
Package graphics Info: Driver file: pdftex.def on input line 99.

(/usr/share/texlive/texmf-dist/tex/latex/graphics-def/pdftex.def
File: pdftex.def 2018/01/08 v1.0l Graphics/color driver for pdftex
))
\Gin@req@height=\dimen112
\Gin@req@width=\dimen113
)
(/usr/share/texlive/texmf-dist/tex/latex/jknapltx/mathrsfs.sty
Package: mathrsfs 1996/01/01 Math RSFS package v1.0 (jk)
\symrsfs=\mathgroup6
)
(/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty
Package: inputenc 2018/04/06 v1.3b Input encoding file
\inpenc@prehook=\toks20
\inpenc@posthook=\toks21
)
(/usr/share/texlive/texmf-dist/tex/latex/base/fontenc.sty
Package: fontenc 2017/04/05 v2.0i Standard LaTeX package

(/usr/share/texlive/texmf-dist/tex/latex/base/t1enc.def
File: t1enc.def 2017/04/05 v2.0i Standard LaTeX file
LaTeX Font Info:    Redeclaring font encoding T1 on input line 48.
))
(/usr/share/texmf/tex/latex/preview/preview.sty
Package: preview 2017/04/24 11.91 (AUCTeX/preview-latex)

(/usr/share/texlive/texmf-dist/tex/generic/luatex85/luatex85.sty
Package: luatex85 2016/06/15 v1.4 pdftex aliases for luatex
)
(/usr/share/texmf/tex/latex/preview/prtightpage.def
\PreviewBorder=\dimen114
)
\pr@snippet=\count100
\pr@box=\box28
\pr@output=\toks22
)
No file sage.aux.
\openout1 = `sage.aux'.

LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 38.
LaTeX Font Info:    ... okay on input line 38.
LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 38.
LaTeX Font Info:    ... okay on input line 38.
LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 38.
LaTeX Font Info:    ... okay on input line 38.
LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 38.
LaTeX Font Info:    ... okay on input line 38.
LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 38.
LaTeX Font Info:    ... okay on input line 38.
LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 38.
LaTeX Font Info:    ... okay on input line 38.
(/usr/share/texlive/texmf-dist/tex/context/base/mkii/supp-pdf.mkii
[Loading MPS to PDF converter (version 2006.09.02).]
\scratchcounter=\count101
\scratchdimen=\dimen115
\scratchbox=\box29
\nofMPsegments=\count102
\nofMParguments=\count103
\everyMPshowfont=\toks23
\MPscratchCnt=\count104
\MPscratchDim=\dimen116
\MPnumerator=\count105
\makeMPintoPDFobject=\count106
\everyMPtoPDFconversion=\toks24
) (/usr/share/texlive/texmf-dist/tex/latex/oberdiek/epstopdf-base.sty
Package: epstopdf-base 2016/05/15 v2.6 Base part for package epstopdf

(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/infwarerr.sty
Package: infwarerr 2016/05/16 v1.4 Providing info/warning/error messages
(HO)
)
(/usr/share/texlive/texmf-dist/tex/latex/oberdiek/grfext.sty
Package: grfext 2016/05/16 v1.2 Manage graphics extensions (HO)

(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/kvdefinekeys.sty
Package: kvdefinekeys 2016/05/16 v1.4 Define keys (HO)

(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/ltxcmds.sty
Package: ltxcmds 2016/05/16 v1.23 LaTeX kernel commands for general use
(HO)
)))
(/usr/share/texlive/texmf-dist/tex/latex/oberdiek/kvoptions.sty
Package: kvoptions 2016/05/16 v3.12 Key value format for package options
(HO)

(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/kvsetkeys.sty
Package: kvsetkeys 2016/05/16 v1.17 Key value parser (HO)

(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/etexcmds.sty
Package: etexcmds 2016/05/16 v1.6 Avoid name clashes with e-TeX commands
(HO)

(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/ifluatex.sty
Package: ifluatex 2016/05/16 v1.4 Provides the ifluatex switch (HO)
Package ifluatex Info: LuaTeX not detected.
))))
(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/pdftexcmds.sty
Package: pdftexcmds 2018/01/30 v0.27 Utility functions of pdfTeX for
LuaTeX (HO
)

(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/ifpdf.sty
Package: ifpdf 2017/03/15 v3.2 Provides the ifpdf switch
)
Package pdftexcmds Info: LuaTeX not detected.
Package pdftexcmds Info: \pdf@primitive is available.
Package pdftexcmds Info: \pdf@ifprimitive is available.
Package pdftexcmds Info: \pdfdraftmode found.
)
Package epstopdf-base Info: Redefining graphics rule for `.eps' on input
line 4
38.
Package grfext Info: Graphics extension search list:
(grfext)
[.pdf,.png,.jpg,.mps,.jpeg,.jbig2,.jb2,.PDF,.PNG,.JPG,.JPE
G,.JBIG2,.JB2,.eps]
(grfext)             \AppendGraphicsExtensions on input line 456.

(/usr/share/texlive/texmf-dist/tex/latex/latexconfig/epstopdf-sys.cfg
File: epstopdf-sys.cfg 2010/07/13 v1.3 Configuration of (r)epstopdf for
TeX Liv
e
))
Preview: Fontsize 10pt
Preview: PDFoutput 1
LaTeX Font Info:    Try loading font information for U+msa on input line
38.
(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd
File: umsa.fd 2013/01/14 v3.01 AMS symbols A
)
LaTeX Font Info:    Try loading font information for U+msb on input line
38.

(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd
File: umsb.fd 2013/01/14 v3.01 AMS symbols B
)
LaTeX Font Info:    Try loading font information for U+rsfs on input
line 38.

(/usr/share/texlive/texmf-dist/tex/latex/jknapltx/ursfs.fd
File: ursfs.fd 1998/03/24 rsfs font definition file (jk)
)
! Missing $ inserted.
<inserted text>
                $
l.38 \begin{document}\begin{page}$$\end{page}

I've inserted something that you may have forgotten.
(See the <inserted text> above.)
With luck, this will get me unwedged. But if you
really didn't forget anything, try typing `2' now; then
my insertion and my current dilemma will both disappear.

! Display math should end with $$.
<to be read again>
                   \endgroup
l.38 \begin{document}\begin{page}$$\end{page}

The `$' that I just saw supposedly matches a previous `$$'.
So I shall assume that you typed `$$' both times.

Preview: Tightpage -32891 -32891 32891 32891
[1] (./sage.aux) )
Here is how much of TeX's memory you used:
 2692 strings out of 492648
 34454 string characters out of 6132024
 94188 words of memory out of 5000000
 6533 multiletter control sequences out of 15000+600000
 6597 words of font info for 26 fonts, out of 8000000 for 9000
 1141 hyphenation exceptions out of 8191
 42i,3n,27p,316b,130s stack positions out of
5000i,500n,10000p,200000b,80000s

Output written on sage.pdf (1 page, 914 bytes).
PDF statistics:
 8 PDF objects out of 1000 (max. 8388607)
 4 compressed objects within 1 object stream
 0 named destinations out of 1000 (max. 500000)
 1 words of extra memory for PDF output out of 10000 (max. 10000000)

Latex error
}}}

and nothing is displayed, whereas :
{{{
sage: bar=sympy.integrate(sympy.sympify(1/(1+a*cos(x))),[x])
sage: view(LatexExpr(sympy.latex(bar)))
sage:
}}}
correctly displays the result (which may or may not be sensible. Another
question...).

Bonus question : how to get a copy of the file generated by {{{view}}}?

URL: https://trac.sagemath.org/25624
Reported by: charpent
Ticket author(s): Dave Morris
Reviewer(s): Matthias Koeppe

Since the switch to Python3, we don't need to have both doctests for py2
and py3. We remove py2 tests in the graphs module.

URL: https://trac.sagemath.org/30110
Reported by: dcoudert
Ticket author(s): David Coudert
Reviewer(s): Markus Wageringel

The method `designs.difference_family` doesn't handle `k in [0,1]`
properly leading to exceptions.
{{{
sage: designs.difference_family(1,1,1)
...
ZeroDivisionError: Integer modulo by zero
}}}

Also negative parameters are not properly handled.
{{{
sage: designs.difference_family(3,-2,-1,existence=True)
Unknown
}}}

The code added fixes these issues:
{{{
sage: designs.difference_family(1,1,1)
(Ring of integers modulo 1, [[0]])
sage: designs.difference_family(3,-2,-1,existence=True)
False
}}}

URL: https://trac.sagemath.org/30102
Reported by: gh-Ivo-Maffei
Ticket author(s): Ivo Maffei
Reviewer(s): Dima Pasechnik

The !PoTe and !VaPoTe algorithms may hang forever when we compute a
Gröbner basis at a precision higher than the cap of the parent.

URL: https://trac.sagemath.org/30101
Reported by: caruso
Ticket author(s): Xavier Caruso
Reviewer(s): Travis Scrimshaw

They are not needed since python 2 is no longer supported

URL: https://trac.sagemath.org/30098
Reported by: arojas
Ticket author(s): Antonio Rojas
Reviewer(s): Dima Pasechnik

URL: https://trac.sagemath.org/30089
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): Travis Scrimshaw

This ticket aims to improve consistency in distance computation methods
such as `shortest_path`, `shortest_path_length`,
`shortest_path_all_pairs` etc.

URL: https://trac.sagemath.org/30081
Reported by: gh-vipul79321
Ticket author(s): Vipul Gupta
Reviewer(s): David Coudert

as another step towards removal of {{{_cmp_}}}

URL: https://trac.sagemath.org/30077
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): Travis Scrimshaw

* remove some unused imports
* make a better assert
* tweak ur .lgtm to ignore one more file

URL: https://trac.sagemath.org/30072
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): Travis Scrimshaw

The following two snippets demonstrate two bugs when working with
`GeneralizedReedSolomonCode`:

{{{
sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSErrorErasureDecoder(C)
sage: y = (vector(F, [0, 0, 10, 0, 0, 22, 0, 0, 38, 8, 34, 14, 33, 0, 0,
39, 0, 0, 0, 0, 17, 36, 43, 30, 10, 15, 0, 0, 21, 10, 37, 0, 0, 0, 0, 0,
0, 0, 0, 42]),
sage:      vector(GF(2), [1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1,
0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
0]))
sage: D.decode_to_code(y)
<BOOM>
}}}

Decoding to message works, but produces a vector of incorrect length
(should equal the dimension, i.e. 12):

{{{
sage: m = D.decode_to_message(y)
sage: len(m)
11
}}}

(The bugs were found by introducing random seeding in #29945)

URL: https://trac.sagemath.org/30045
Reported by: jsrn
Ticket author(s): Johan Rosenkilde
Reviewer(s): Jonathan Kliem

Built `designs.biplane` which given a number `n` it returns a biplane of
such order.

For more on biplanes see
https://en.wikipedia.org/wiki/Block_design#Biplanes

URL: https://trac.sagemath.org/30016
Reported by: gh-Ivo-Maffei
Ticket author(s): Ivo Maffei
Reviewer(s): Dima Pasechnik

The "simple verbosity system" in `sage.misc.misc` has 2 global
variables, `LEVEL` and `verbose_files`, which are meant to be internal.

- Access is through functions `verbose`, `set_verbose`,
`set_verbose_files`, `get_verbose_files`, `unset_verbose_files`,
`get_verbose`, all of which are imported by `sage.misc.all`.

- Only `verbose` and `get_verbose` are used in sagelib.

- Additionally, `set_verbose` is used in doctests of sagelib.

We move the functions to a new module `sage.misc.verbose`, with
`lazy_import` and deprecation.  This is preparation for #21349, and is
also helpful for #29865 (modularization).

We also add some documentation taken from #21349.

We also deprecate the import of `verbose` into `sage.misc.all` as
proposed in #17815.

See also:
 - #21349: build verbose upon Python's logging module
 - #17815: Remove verbose from the global namespace

URL: https://trac.sagemath.org/29895
Reported by: mkoeppe
Ticket author(s): Daniel Krenn, Matthias Koeppe
Reviewer(s): Travis Scrimshaw, Markus Wageringel

This ticket changes the implementation of `FreeAbelianMonoidElement` to
store its exponents as `mpz_t*` array (copied in part from
`vector_integer_dense`). The file is cythonized for this. This makes
multiplication much faster (from comment:10):

{{{
M = FreeAbelianMonoid('x', 5)
L = [M(list(v)) for d in (0..7) for v in IntegerVectors(d, 5)]
%timeit _ = [a * b for a in L for b in L]
1 loop, best of 5: 1.7 s per loop  -- (before)
1 loop, best of 5: 282 ms per loop  -- (after)
}}}

Another motivation for this change is to facilitate viewing free abelian
monoids as the indexing set of polynomial rings.

URL: https://trac.sagemath.org/29638
Reported by: gh-mwageringel
Ticket author(s): Markus Wageringel, Travis Scrimshaw
Reviewer(s): Frédéric Chapoton, Markus Wageringel

We implement general univariate Ore polynomials (allowing for
derivations and twisted derivations)

URL: https://trac.sagemath.org/29629
Reported by: caruso
Ticket author(s): Xavier Caruso
Reviewer(s): Travis Scrimshaw

This was broken in #29702 (Move all code from `src/setup.py`,
`src/fpickle_setup.py` to `sage_setup`). On compilation errors, we see:
{{{
Error in sys.excepthook:
TypeError: 'module' object is not callable
}}}

This ticket fixes it.

URL: https://trac.sagemath.org/30113
Reported by: mkoeppe
Ticket author(s): Matthias Koeppe
Reviewer(s): John Palmieri

Given a symmetric `(v, k, lambd)`-BIBD one can build a `(v-k, k-lambd,
lambd)`-BIBD by removing a block from the former.

For more on BIBDs see https://en.wikipedia.org/wiki/Block_design#Definit
ion_of_a_BIBD_(or_2-design)

URL: https://trac.sagemath.org/30037
Reported by: gh-Ivo-Maffei
Ticket author(s): Ivo Maffei
Reviewer(s): Dima Pasechnik

Implemented a nonexistence check based on the Bruck–Ryser–Chowla
theorem.
Before generating a BIBD for some given parameters, we check if the
theorem holds for the parameters. If it does not, then no such BIBD
exists.

See https://en.wikipedia.org/wiki/Bruck–Ryser–Chowla_theorem

URL: https://trac.sagemath.org/30029
Reported by: gh-Ivo-Maffei
Ticket author(s): Ivo Maffei
Reviewer(s): Dima Pasechnik

With `SageMath version 9.2.beta2, Release Date: 2020-06-26`, the command

{{{
sage -t --optional=sage,internet src/sage/combinat/species/library.py
src/sage/combinat/tutorial.py
}}}

gives

{{{
Doctesting 2 files.
sage -t src/sage/combinat/species/library.py
**********************************************************************
File "src/sage/combinat/species/library.py", line 104, in
sage.combinat.species.library.BinaryTreeSpecies
Failed example:
    oeis(seq)[0]                              # optional -- internet
Expected:
    A000108: Catalan numbers: C(n) = binomial(2n,n)/(n+1) =
(2n)!/(n!(n+1)!). Also called Segner numbers.
Got:
    A000108: Catalan numbers: C(n) = binomial(2n,n)/(n+1) =
(2n)!/(n!(n+1)!).
**********************************************************************
1 item had failures:
   1 of  10 in sage.combinat.species.library.BinaryTreeSpecies
    [23 tests, 1 failure, 3.88 s]
sage -t src/sage/combinat/tutorial.py
**********************************************************************
File "src/sage/combinat/tutorial.py", line 224, in
sage.combinat.tutorial
Failed example:
    oeis([1,1,2,5,14])                            # optional -- internet
Expected:
    0: A000108: Catalan numbers: C(n) = binomial(2n,n)/(n+1) =
(2n)!/(n!(n+1)!). Also called Segner numbers.
    1: ...
    2: ...
Got:
    0: A000108: Catalan numbers: C(n) = binomial(2n,n)/(n+1) =
(2n)!/(n!(n+1)!).
    1: A022562: Number of connected claw-free unlabeled graphs on n
nodes.
    2: A124302: Number of set partitions with at most 3 blocks; number
of Dyck paths of height at most 4; dimension of space of symmetric
polynomials in 3 noncommuting variables.
**********************************************************************
1 item had failures:
   1 of 245 in sage.combinat.tutorial
    [244 tests, 1 failure, 6.98 s]
----------------------------------------------------------------------
sage -t src/sage/combinat/species/library.py  # 1 doctest failed
sage -t src/sage/combinat/tutorial.py  # 1 doctest failed
----------------------------------------------------------------------
}}}

URL: https://trac.sagemath.org/30020
Reported by: slabbe
Ticket author(s): Sébastien Labbé
Reviewer(s): Travis Scrimshaw

The file `sage_setup/fpickle_setup.py` does not seem to be needed
anymore, so remove it. This also removes some uses of `six` in
`sage/setup.py`.

URL: https://trac.sagemath.org/30011
Reported by: mkoeppe
Ticket author(s): John Palmieri
Reviewer(s): Matthias Koeppe

This breaks doc build again, the 'modules' dict values are now
namedtuples instead of tuples.

URL: https://trac.sagemath.org/30001
Reported by: arojas
Ticket author(s): Antonio Rojas
Reviewer(s): John Palmieri

This is so we have better control over the library dependencies.

This is for #29912: Modularization of sagelib: Break out a separate
package `sage-ntl`

URL: https://trac.sagemath.org/29999
Reported by: mkoeppe
Ticket author(s): Matthias Koeppe
Reviewer(s): Travis Scrimshaw

This is a doctest from `src/sage/graphs/connectivity.pyx` with a
different random seed:
{{{
sage: set_random_seed(151058820726654196682836430928254760259)
sage: from sage.graphs.connectivity import strong_articulation_points
sage: def sap_naive(G):
....:     nscc = len(G.strongly_connected_components())
....:     S = []
....:     for u in G:
....:         H = copy(G)
....:         H.delete_vertex(u)
....:         if len(H.strongly_connected_components()) > nscc:
....:             S.append(u)
....:     return S
....:
sage: D = digraphs.RandomDirectedGNP(20, 0.1)
sage: X = sap_naive(D)
sage: SAP = strong_articulation_points(D)
sage: set(X) == set(SAP)
False
}}}

An indeed the vertex `10` is in `SAP`, but it appears not to be a strong
articulation point:
{{{
sage: SAP
[17, 4, 1, 18, 2, 7, 10]
sage: len(D.strongly_connected_components())
13
sage: D.delete_vertex(10)
sage: len(D.strongly_connected_components())
13
}}}

Before this ticket, all vertices in strongly connected components of
size 2 where returned as strong articulation points. But a graph with 2
vertices always has zero articulation points.

URL: https://trac.sagemath.org/29958
Reported by: gh-kliem
Ticket author(s): David Coudert
Reviewer(s): Jonathan Kliem

The [https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/p
ermutation.html#sage.combinat.permutation.Permutations_mset
Permutations_mset]
`rank` and `unrank` methods inherit a generic implementation from
`EnumeratedSets`
[https://doc.sagemath.org/html/en/reference/categories/sage/categories/e
numerated_sets.html#sage.categories.enumerated_sets.EnumeratedSets.Paren
tMethods.rank rank] and
[https://doc.sagemath.org/html/en/reference/categories/sage/categories/e
numerated_sets.html#sage.categories.enumerated_sets.EnumeratedSets.Paren
tMethods.unrank unrank],
which have running time proportional to the rank:

{{{
sage: mset = list(range(10)) * 3
sage: p = Permutations(mset)
sage: for e in range(8): timeit('p.unrank({})'.format(10^e), number=1,
repeat=5)
1 loop, best of 5: 24.2 μs per loop
1 loop, best of 5: 39.1 μs per loop
1 loop, best of 5: 191 μs per loop
1 loop, best of 5: 1.28 ms per loop
1 loop, best of 5: 12.7 ms per loop
1 loop, best of 5: 126 ms per loop
1 loop, best of 5: 1.27 s per loop
1 loop, best of 5: 13 s per loop
sage: p.rank(list(reversed(sorted(mset))))
... never finishes ...
}}}

This branch makes the running time roughly proportional to the size of
the multiset:

{{{
sage: mset = list(range(10)) * 3
sage: p = Permutations(mset)
sage: for e in range(8): timeit('p.unrank({})'.format(10^e), number=1,
repeat=5)
1 loop, best of 5: 1.35 ms per loop
1 loop, best of 5: 1.43 ms per loop
1 loop, best of 5: 1.37 ms per loop
1 loop, best of 5: 1.37 ms per loop
1 loop, best of 5: 2.23 ms per loop
1 loop, best of 5: 2.12 ms per loop
1 loop, best of 5: 1.46 ms per loop
1 loop, best of 5: 1.44 ms per loop
sage: timeit('p.rank(list(reversed(sorted(mset))))', number=1, repeat=5)
1 loop, best of 5: 1.51 ms per loop
}}}

== Algorithm

The `rank` algorithm is a straightforward application of the solution to
exercise 7.2.1.2–4 in
''The Art of Computer Programming'', Volume 4A.
I will quote the exercise:

> Q. Generalizing exercise 3, explain how to compute the rank of
>    ''a'',,1,,…''a'',,''n'',,
>    with respect to Algorithm L [lexicographic permutation generation]
>    when {''a'',,1,,, …, ''a'',,''n'',,} is the multiset
{''n'',,1,,·''x'',,1,,, …, ''n'',,''t'',,·''x'',,''t'',,};
>    here ''n'',,1,, + … + ''n'',,''t'',, = ''n'' and
>    ''x'',,1,, < … < ''x'',,''t'',,. (The total number of permutations
is, of course, the multinomial coefficient
>        multinomial(''n'',,1,,, …, ''n'',,''t'',,) = ''n''! /
(''n'',,1,,! … ''n'',,''t'',,!);
>    see Eq. 5.1.2–(3).) What is the rank of 314159265?

> A. Use the recurrence rank(''a'',,1,, … ''a'',,''n'',,) =
>    1/''n'' Σ,,j=1…''t'',, ''n'',,''j'',, [''x'',,''j'',, < ''a'',,1,,]
multinomial(''n'',,1,,, …, ''n'',,''t'',,) + rank(''a'',,2,, …
''a'',,''n'',,).
>    For example, rank(314159265) is
>        3/9 multinomial(2, 1, 1, 1, 2, 1, 1)
>        + 0
>        + 2/7 multinomial(1, 1, 1, 2, 1, 1)
>        + 0
>        + 1/5 multinomial(1, 2, 1, 1)
>        + 3/4 multinomial(1, 1, 1, 1)
>        + 0
>        + 1/2 multinomial(1, 1) = 30991.

The `unrank` algorithm is also based on this recurrence;
however the application is not so straightforward.
I did not find an explicit statement of an unranking algorithm
elsewhere,
and the algorithm I came up with isn't particularly elegant.
I'd appreciate having another opinion on it or a pointer to some other
reference.
The main idea is that given a rank ''r'' and a multiset
''m'' = {''n'',,1,,·''x'',,1,,, …, ''n'',,''t'',,·''x'',,''t'',,},
we know that
''r'' = ''c''/''n'' multinomial(''n'',,1,,, …, ''n'',,''t'',,) +
rank(''m''\''c''),
where ''c'' is the number of elements in ''m'' that are strictly less
than
the first element of the output sequence, and ''m''\''c'' stands for
''m'' with one instance of the ''c''th smallest element removed.

== Notes/caveats

The `rank` method is actually independent of the `Permutations_mset`
object
it is attached to.
Other than the `self(p).check()` line,
it never refers to `self`.
It could be defined in terms of a standalone function,
as [https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/pe
rmutation.html#sage.combinat.permutation.StandardPermutations_n.unrank
StandardPermutations_n.unrank]
is defined in terms of [https://doc.sagemath.org/html/en/reference/combi
nat/sage/combinat/permutation.html#sage.combinat.permutation.from_rank
from_rank].

I am aware of two ways in which this branch differs in behavior from
what is there now.
They both seem to me to be because of bugs in the `EnumeratedSets`
fallback implementations,
but I'll document them here in case complete compatibility is needed.

The first is that the existing
[https://git.sagemath.org/sage.git/tree/src/sage/categories/enumerated_s
ets.py?h=9.1#n668 rank]
method returns `None` when passed a list or a tuple,
because it uses `==` comparison with an `element_class` type
(I'm not sure how that works exactly, but at any rate it doesn't compare
equal.)
To get `rank` to return something other than `None`, you have to pass in
a permutation produced by the `Permutations_mset` object itself.

{{{
sage: mset = [1, 1, 2, 3, 4, 5, 5, 6, 9]
sage: p = Permutations(mset)
sage: p.rank(mset)
sage: p.rank([1, 1, 2, 3, 4, 5, 5, 6, 9])
sage: p.unrank(3)
[1, 1, 2, 3, 4, 5, 6, 9, 5]
sage: type(p.unrank(3))
<class 'sage.combinat.permutation.Permutations_mset_with_category.elemen
t_class'>
sage: p.rank(p.unrank(3))
3
}}}

In this branch, the value passed to `rank` doesn't have to be an
`element_class`.

{{{
sage: mset = [1, 1, 2, 3, 4, 5, 5, 6, 9]
sage: p = Permutations(mset)
sage: p.rank(mset)
0
sage: p.rank([1, 1, 2, 3, 4, 5, 5, 6, 9])
0
sage: p.unrank(3)
[1, 1, 2, 3, 4, 5, 6, 9, 5]
sage: type(p.unrank(3))
<class 'list'>
sage: p.rank(p.unrank(3))
3
}}}

The other way in which this branch changes behavior
is that the current code does not canonicalize the multiset
used to create the `Permutations_mset` object.
`Permutations([1, 1, 2, 3, 4])` and `Permutations([3, 2, 1, 4, 1])`
visit the same permutations but in a different order;
the latter acts like an already partially enumerated version of the
former:

{{{
sage: Permutations([1, 1, 2, 3, 4]).unrank(0)
[1, 1, 2, 3, 4]
sage: Permutations([3, 2, 1, 4, 1]).unrank(0)
[3, 2, 1, 1, 4]
}}}

In this branch, the order of the input multiset does not make a
difference:

{{{
sage: Permutations([1, 1, 2, 3, 4]).unrank(0)
[1, 1, 2, 3, 4]
sage: Permutations([3, 2, 1, 4, 1]).unrank(0)
[1, 1, 2, 3, 4]
}}}

It would be possible to work around this canonicalization, if necessary,
by computing the rank of the input multiset on creation,
and using it as an offset for future calls to `unrank`.

I was working on a project that needed fast unranking of a multiset,
when I found that Sage could not handle a multiset of the size I needed.
I came up with
[https://www.bamsoftware.com/comicrando/seed.html#algorithm an
algorithm]
that worked well enough for my purposes, however its ranking order is
not lexicographic.
The algorithms in this branch are the result of a little more research
to find a lexicographic algorithm.

URL: https://trac.sagemath.org/29942
Reported by: dcfifield
Ticket author(s): David Fifield
Reviewer(s): Frédéric Chapoton, Travis Scrimshaw

Trac #29923: Deprecate deprecated sage-cython script harder, remove use of it in the main sage script

The script `sage-cython` has been deprecated for about 18 months, so
let's remove its use within sage.

URL: https://trac.sagemath.org/29923
Reported by: jhpalmieri
Ticket author(s): John Palmieri
Reviewer(s): Matthias Koeppe

We add a method that tests basic properties, when the `TestSuite` is
run.

URL: https://trac.sagemath.org/29905
Reported by: gh-kliem
Ticket author(s): Jonathan Kliem
Reviewer(s): Matthias Koeppe

The vertex facet graph of `CombinatorialPolyhedron` only works for
polyhedra of dimension at least one. With #29188 this makes it fail with
for `Polyhedron_base` as well.

We fix this to return
- the `Digraph` on 0 vertices for the empty polyhedron and
- the `Digraph` on 1 vertex for the 0-dimensional polyhedron (it was
misbehaved even before #29188).

We also "fix" the definition of facets to correspond to inequalities.
The `0`-dimensional polyhedron does not have facets in this case
anymore.
(Before this ticket `n_facets` and `facets` would use different
definitions of facets.)b

URL: https://trac.sagemath.org/29898
Reported by: gh-kliem
Ticket author(s): Jonathan Kliem
Reviewer(s): Matthias Koeppe

Merge branch 'u/tscrim/ore_polynomials-29629' of git://trac.sagemath.org/sage into u/caruso/ore_polynomials-29629