Implement Key polynomials

[trevorkarn]

Implement the Key polynomials as an algebra with basis indexed by compositions.

Depends on #34435
Depends on #34510
Depends on #34527
Depends on #34535
Depends on #34581

CC: @trevorkarn @tscrim

Component: combinatorics

Keywords: gsoc2022 key-polynomial

Author: Trevor K. Karn

Branch/Commit: u/tscrim/key_polynomials-34414 @ 124900f

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/34414

[trevorkarn]

Last 10 new commits:

cfee8e8	Speed up sliding by skipping classcall
62c7b5f	Remove unneeded creation of skew tableaux
8b6ef8a	First round of reviewer suggestions
e973f7d	Assertion -> ValueError
a57b2d0	Add tests and remove Stanley s.f.
28286da	Add methods to interact with polyominos/compositions
75ce24e	Change to list
8c3cb4e	Add type-A algorithm
4a6b2f9	Rewrite to pass to Permutations
9c2a107	Initial commit of KeyPolynomial

[trevorkarn]

Branch: u/tkarn/key-poly-34414

[trevorkarn]

Commit: 9c2a107

[sagetrac-git]

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

5899abf

Fix divided difference

[sagetrac-git]

Changed commit from 9c2a107 to 5899abf

[sagetrac-git]

Changed commit from 5899abf to 24098b5

[sagetrac-git]

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

24098b5

Fix expand

[trevorkarn]

Dependencies: #34435

[sagetrac-git]

Changed commit from 24098b5 to 3266d1e

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

2f439a6	Add tests and remove Stanley s.f.
b5f7f90	Add methods to interact with polyominos/compositions
7e5e4d9	Change to list
e9e9c2b	Add type-A algorithm
22be18c	Rewrite to pass to Permutations
cd33943	Initial commit of KeyPolynomial
7835f13	Fix divided difference
9b683f1	Fix expand
e0bbdbd	Add some examples
3266d1e	Add many examples and fix _sorting_permutation logic bug

[sagetrac-git]

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

fe87df5

All tests pass and PEP8 compliance

[sagetrac-git]

Changed commit from 3266d1e to fe87df5

[trevorkarn]

comment:8

There are probably things to do to extend this in the future, but here is a working implementation for the basic computations.

[tscrim]

comment:9

Some quick comments:

• I might call it KeyPolynomialBasis or something like this to indicate that it is a choice of basis for the ring of polynomials in infinitely many variables.
• No need to declare the metaclass. It comes from UniqueRepresentation.
• In the doc, you should specify that it is indexed by integer vectors with no trailing zeros. (Ideally I would want this for the actual basis elements, but this is not worth the trouble of actually programming it.)
• You should not need to implement one(). That should come from the category.
• expand() should take a number of variables (optional) argument.
• The divided difference operators are acting on polynomials and only involve polynomials. They should not be methods of the class.
• A good check would be to show the divided difference operators on the polynomials simply swaps two indices in the weak composition (when in order) of the key polynomial basis index. (Hopefully that makes sense, I don't think I explained it too well.)
• It would be better to implement product instead of product_on_basis as doing (K[A] + K[B]) * (K[C] + K[D]) would go back and forth on each of the 4 products rather than just once on the pair.
• You seem to be doing a lot of work in expand(). I would just do the appropriate divided difference operator as you start sorting. At the end of the day, you're having to do the classical bubble sort algorithm and not gaining anything by first using a smarter sorting algorithm.
• It might be good to have coercions from the (infinte) polynomial rings over the same base ring implemented using _coerce_map_from_. Although I am not yet 100% sold on this because it neglects the name of the polynomials and it might mean dealing with subtleties when the base ring is a polynomial ring.

[trevorkarn]

comment:10

Thanks for the comments!

Replying to @tscrim:

• expand() should take a number of variables (optional) argument.

This one I think I disagree with. The expansion is always going to be into the infinite variable polynomial ring, and the variable with largest index occuring in the expansion is implied by the composition. The only reason I see to have a number of variables argument is to have a fewer number of variables. Is that a thing that one would ever want to do mathematically? I know there is sometimes a reason to do that for expanding Schur polynomials as GLn characters, which is in my head as an analogous thing.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

de2931a	Change to list
4928f81	Add type-A algorithm
8cbbba6	Rewrite to pass to Permutations
84e9719	Initial commit of KeyPolynomial
5909497	Fix divided difference
29250d5	Fix expand
67afb32	Add some examples
2755072	Add many examples and fix _sorting_permutation logic bug
f1096fc	All tests pass and PEP8 compliance
8244c59	Incorporate comments from reviewer

[sagetrac-git]

Changed commit from fe87df5 to 8244c59

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f97afef

Remove unneeded dependencies

[sagetrac-git]

Changed commit from 8244c59 to f97afef

[tscrim]

comment:14

Replying to @trevorkarn:

Replying to @tscrim:

• expand() should take a number of variables (optional) argument.

This one I think I disagree with. The expansion is always going to be into the infinite variable polynomial ring, and the variable with largest index occuring in the expansion is implied by the composition.

I might want to do the expansion in a finite polynomial ring of my choosing. You will probably have to do something slightly special when the number of variables is less than the natural minimal number.

The only reason I see to have a number of variables argument is to have a fewer number of variables. Is that a thing that one would ever want to do mathematically? I know there is sometimes a reason to do that for expanding Schur polynomials as GLn characters, which is in my head as an analogous thing.

On the contrary, you might want it to be living in a larger polynomial ring. You are equating the weak compositions up to trailing zeros, but what if I want to look at all key polynomials in, say, a 4 variable polynomial ring only? This can matter for coercion and substitution purposes.

Actually, that makes me think we probably should also implement a true finite number of variables version. Mathematically, you are secretly implementing the projective limit coming from a tower of polynomial rings under the natural projections (which when precomposed with the natural inclusions give the identity map on each component). The key basis with n variables is naturally a subset of the key basis of n + k variables. The integer vectors are already available:

sage: IV3 = IntegerVectors(k=3)
sage: IV3
Integer vectors of length 3

This might also give some speedups for some of the computations.

Lastly, instead of modifying _element_constructor_, you are probably better off implementing a new _monomial function to strip trailing 0s in the infinite variable case. The infinite polynomial ring would then be handled by the coercion mentioned above. This would make other construction methods more uniform.

[sagetrac-git]

Changed commit from f97afef to a5848c9

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

01d065f	Add trim to integer vector
a71be31	Fix parent
915c87f	Remove unneeded dependencies
df9175e	Add test
a5848c9	Use bubble sort/refactor _pi

[sagetrac-git]

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

d277654	Remove duplicated code
0ab036a	Add `_mul_` and remove .product()
70e4687	Add test for rational division and try with coefficients in GF(5)

[sagetrac-git]

Changed commit from cd7d6b5 to 70e4687

[trevorkarn]

comment:50

Replying to Travis Scrimshaw:

I don't quite understand why that code works for the infinite case. I think depending on #34581 is the right way to go. We should be able to fix that one fairly quickly.

Some more comments on this:

• Rename poly_gen() -> poly_gens() as it returns all of the generators.

• while f.monomials(): seems wasteful; you can simply check while f: (is not 0).

• In from_polynomial(), I would separate out the self._indices(m).trim() into a separate helper method

  if self._k:
      def build_index(m):
          return self._indices(m)
  else:
      def build_index(m):
          return self._indices(m).trim()

Done

Furthermore I am not certain that the monomials and exponents will always be given in lex order. While it is a bit more computationally intensive, I think you should call max(f.exponents()). You can then use that to build the monomial and/or get the coefficient. This allows you to remove the code duplication.

I avoided this by picking the monomial and then getting the exponent from the original polynomial instead getting it from the monomial itself. I think this shores up the weak point in my previous approach.

• Since you have an element class, you are better implementing _mul_ there as that avoids some indirection.

Done.

[sagetrac-git]

Changed commit from 70e4687 to 197b53e

[sagetrac-git]

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

197b53e

PEP8 compliance

[sagetrac-git]

Changed commit from 197b53e to 4855ece

[sagetrac-git]

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

4855ece

Fix pyflakes issues

[tscrim]

Changed branch from u/tkarn/key-poly-34414 to u/tscrim/key_polynomials-34414

[tscrim]

Changed commit from 4855ece to 2e2c4f2

[tscrim]

comment:54

I (finally) got around to doing the review changes I wanted. The biggest change is I made everything 1-based, which will avoid a lot of confusion from users. I also made the divided difference operators more usable by general polynomials and minimized some of the function calls (at the expense of some 1-line code duplication). If my changes are good, then this can be set to a positive review.

---

New commits:

710cfbb	Reviewer changes: refactored some of the divided difference code, doc changes, orther misc changes.
5e8977f	Add reviewer suggestions to docs and change behavior of conflicting subs
a56e345	Doc change
2e2c4f2	Merge branch 'u/tkarn/inf-poly-subs-34581' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/key_polynomials-34414

[trevorkarn]

comment:55

Thanks! These all look good to me. Especially implementing __getitem__. Setting to positive review.

[sagetrac-git]

Changed commit from 2e2c4f2 to 124900f

[sagetrac-git]

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

34bbd61	Merge branch 'u/tscrim/key_polynomials-34414' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/key_polynomials-34414
124900f	Removed unused copy for pyflakes.

[tscrim]

comment:58

Trivial change to make pyflakes happy.

[mkoeppe]

Merged in 10.0.beta0