← All papers
First page of An extended Demazure product on integer permutations via min-plus matrix multiplication

An extended Demazure product on integer permutations via min-plus matrix multiplication

Nathan Pflueger

math.CO Jun 28, 2022 · v2
The main theorems on the extended Demazure product and slipface functions are formally verified in Lean 4, with Lean declaration names attached to the results.
Coxeter groups possess an associative operation, called variously the Demazure, greedy, or 0-Hecke product. For symmetric groups, this product has an amusing formulation, due to Tiskin, as matrix multiplication in the min-plus (tropical) semiring of two matrices associated to the permutations. We prove that this min-plus formulation extends to furnish a Demazure product on a much larger group of integer permutations, consisting of all permutations that change the sign of finitely many integers. We prove several alternative descriptions of this product and some useful properties. These results were developed in service of Brill–Noether theory of algebraic and tropical curves; the connection is surveyed in an appendix. The main theorems of this paper have been fully formalized in Lean 4.

Tiskin showed that the Demazure (0-Hecke) product on symmetric groups can be computed as min-plus matrix multiplication of rank-type matrices. The question is whether this extends to a larger group of integer permutations, namely those that change the sign of only finitely many integers.

The author introduces slipface functions Z^2 -> N as a general setting. Submodular slipfaces are characterized as exactly those arising from almost-sign-preserving permutations, and the image is shown to be closed under min-plus product and related operations. Greedy and stingy characterizations, a reduction theorem, essential-set criteria, and closed subgroups are then developed. The main theorems are formalized in Lean 4.

The min-plus formulation gives an associative Demazure product on almost-sign-preserving permutations, along with several equivalent descriptions and properties. The main theorems and many auxiliary results are machine-checked in Lean 4. The connection to Brill–Noether theory of algebraic and tropical curves is surveyed in an appendix.