Trac #15622: Immutable graphs must not be relabeled

Now
{{{
sage: Graph(graphs.PetersenGraph(), immutable=True).relabel({})
...
ValueError: Thou shalt not relabel an immutable graph
}}}

Before, the following happened
{{{
sage: Graph(graphs.PetersenGraph(),
data_structure="static_sparse").relabel({})
...
AttributeError: 'StaticSparseBackend' object has no attribute
'vertex_ints'
}}}

This is actually another bug, as there should be a `vertex_ints`
variable in static sparse graphs. But that's another problem to be
addressed in another ticket `:-P`

Nathann

URL: http://trac.sagemath.org/15622
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Simon King
Trac #15626: Further improvements to splitting_field()

1. Implement an "early abort" option to stop if it's clear that the
degree will be huge.
1. Add some more examples (more indirect examples will be added by
#11905)

URL: http://trac.sagemath.org/15626
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer
Reviewer(s): John Cremona
Trac #10963: More functorial constructions

This ticket implements:

- Support for full subcategories defined by an axiom (Finite,
  Infinite, Facade, Commutative, Associative, Unital,
  Inverse, NoZeroDivisors, Division, FiniteDimensional, Connected,
  WithBasis, Irreducible), and joins thereof:

{{{
    sage: Groups() & Sets().Finite()
    Category of finite groups
    sage: Algebras(QQ).Finite() & Monoids().Commutative()
    Join of Category of commutative algebras over Rational Field and
Category of finite monoids
    sage: Rings().Division() & Sets().Finite()
    Category of finite fields
}}}

- New categories:
  - AdditiveSemigroups, AdditiveMonoids, AdditiveGroups
  - DistributiveMagmasAndAdditiveMagmas
  - MagmaticAlgebras (will replace Algebras in #15043)
  - AssociativeAlgebras
  - UnitalAlgebras
  - Algebras of additive semigroups and monoids

- More mathematical rules:
  - A subquotient of a finite set is a finite set
  - The algebra of a finite set is finite dimensional
  - The algebra of a commutative magma is commutative
  - A finite division ring is a field
  - ...

- Documentation:
  - More documentation for IsomorphicObjects
  - Complete revamping of sage.categories.primer
  - Misc

- Use SubcategoryMethods to put the functorial constructions where
  they belong. E.g. DualObjects, TensorProducts, and Graded are now
  only defined for subcategories of Modules.

- More lazy imports, removed a bunch of unused imports, ...

Patch developed on:
http://combinat.sagemath.org/patches/file/tip/trac_10963
-more_functorial_constructions-nt.patch.

This ticket is dedicated to the town of Megantic where I was so warmly
welcomed and a good chunk of this ticket got implemented!

Apply:

* [attachment:trac_10963-more_functorial_constructions-nt.patch]
* [attachment:trac_10963_doctest_correction-fc.patch]
* [attachment:trac_10963-more_functorial_constructions-graded-modules-
fix-nt.patch]

URL: http://trac.sagemath.org/10963
Reported by: nthiery
Ticket author(s): Nicolas M. Thiéry
Reviewer(s): Simon King, Frédéric Chapoton
Trac #15408: corrections and improvements to `inner_plethysm` method in symmetric functions

The current documentation for `inner_plethysm` reads
{{{
f.inner_plethysm(g + h) == f.inner_plethysm(g) + f.inner_plethysm(h).
}}}
This is false (see an example below), and in fact
{{{
(f+g).inner_plethysm(h) == f.inner_plethysm(h) + g.inner_plethysm(h)
}}}
and it is only true that
{{{
p[k].inner_plethysm(f+g) == p[k].inner_plethysm(f) +
p[k].inner_plethysm(g).
}}}
It is also true that
{{{
(f*g).inner_plethsym(h) ==
(f.inner_plethsym(h)).itensor(g.inner_plethsym(h)).
}}}
In fact these three statements and the definition for
`p[k].inner_plethysm(p(mu))` is how inner plethysm is defined.

For example
{{{
sage: s[3].inner_plethysm(s[2,1]+s[3])-s[3].inner_plethysm(s[2,1])-s[3].
inner_plethysm(s[3])
2*s[2, 1] + s[3]
sage: (s[3]+s[2,1]).inner_plethysm(s[2,1])-s[3].inner_plethysm(s[2,1])-s
[2,1].inner_plethysm(s[2,1])
0
sage: p[5].inner_plethysm(s[2,1]+s[3])-p[5].inner_plethysm(s[2,1])-p[5].
inner_plethysm(s[3])
0
sage: p[3,2].inner_plethysm(s[2,1])-p[3].inner_plethysm(s[2,1]).itensor(
p[2].inner_plethysm(s[2,1]))
0
}}}
Moreover the doc tests don't catch errors that were (probably?)
introduced in edits since #3244.
{{{
sage: p[4,3].inner_plethysm(p[2,2,1])
------------------------------------------------------------------------
---
AttributeError                            Traceback (most recent call
last)
...
AttributeError: 'int' object has no attribute 'itensor'
sage: p[3].inner_plethysm(p[3])
------------------------------------------------------------------------
---
ValueError                                Traceback (most recent call
last)
...
ValueError: Codomain could not be determined
}}}

URL: http://trac.sagemath.org/15408
Reported by: zabrocki
Ticket author(s): Mike Zabrocki
Reviewer(s): Darij Grinberg, Franco Saliola
Trac #15439: sage/combinat/matrices/latin.py: isotopism method uses product of permutations

From `sage/combinat/matrices/latin.py`:
{{{
def isotopism(p):
    """
    Returns a Permutation object that represents an isotopism (for
    rows, columns or symbols of a partial latin square). Since matrices
    in Sage are indexed from 0, this function translates +1 to agree
    with the Permutation class. We also handle
    PermutationGroupElements.
[...]
                x = x * isotopism(p[i])
[...]
}}}
This uses the syntax `a * b` for the product of two permutations. This
syntax is bad because its semantics depends on the state of a global
variable (`mult` in `Permutation.global_options()`), which decides which
of the factors is to be applied first when multiplying two permutations.
I don't know if it matters for this particular method, but such things
have been causing subtle bugs in two other places, so this should be
looked at (unfortunately I don't know much about Latin squares;
Nathann?). Even if the result doesn't depend on the order of
multiplication, it is better to use the
`_left_to_right_multiply_on_left` and `_left_to_right_multiply_on_right`
methods of class `sage.combinat.permutation.Permutation` for speed
reasons (they don't waste time looking up the state of that global
variable).

See also #15174.

URL: http://trac.sagemath.org/15439
Reported by: darij
Ticket author(s): Nathann Cohen
Reviewer(s): Darij Grinberg
Trac #15471: sage/graphs/generators/intersection.py multiplies a permutation by id

and no, it's not even a poor man's coercion, because they have the same
size already. My bet is someone was confused. The attached patch (split
out of #15174) removes this exercise in futility.

URL: http://trac.sagemath.org/15471
Reported by: darij
Ticket author(s): Darij Grinberg
Reviewer(s): Nathann Cohen
Trac #15476: Involutions on NSym and QSym part I

This got much longer than I expected it to be because there are three
"classical" involution on each of NSym and QSym and each can be computed
on various bases. I ended up implementing only two of the involutions
(star=rho and psi), leaving out omega (which is just a rescaled
antipode) for part II.

The patch also speeds up NSym's Verschiebung on certain bases, fixes
some doc, moves a reference, and changes various invocations of
`Composition(spam)` to `Compositions()(spam)` for speed reasons (when
`spam` really is just a list). Could a `_Compositions` (akin to
`_Partitions`) be of use?

URL: http://trac.sagemath.org/15476
Reported by: darij
Ticket author(s): Darij Grinberg
Reviewer(s): Travis Scrimshaw
Trac #15495: Flip graph of pure simplicial complex

For a pure simplicial complex (i.e., a simplicial complex with all
maximal faces (facets) having the same dimension), one can compute the
flip graph. This is the undirected graph with vertices being the facets,
where two facets are jointed by an edge if they meet in a codimension 1
face.

URL: http://trac.sagemath.org/15495
Reported by: stumpc5
Ticket author(s): Christian Stump
Reviewer(s): Nathann Cohen
Trac #15613: Implementation for check of perfectness for CrystalOfProjectedLevelZeroLSPaths

This ticket implements a check for perfectness of
CrystalOfProjectedLevelZeroLSPaths.

URL: http://trac.sagemath.org/15613
Reported by: aschilling
Ticket author(s): Anne Schilling
Reviewer(s): Travis Scrimshaw