klpoly -- Kazhdan-Lusztig polynomials of the symmetric group
============================================================

kltab computes every Kazhdan-Lusztig polynomial P_{x,w} of S_n and writes them
to a compact table; klread looks one up.  There is no limit in the program
beyond memory: n = 12 has been done on a machine with a terabyte.  n = 10 takes about two minutes and
well under a gigabyte, and the whole of S_10 -- 981,173 distinct polynomials
over 18,646,043 stored pairs -- comes to 68 MB.  n = 11 has been run too: a
little over three hours, and 58,051,912 polynomials in 3.9 GB.

LICENCE
MIT; see the file LICENSE.  Copyright (c) 2017-2026 Erez Lapid.
An independent implementation, written from the recursion of Kazhdan and
Lusztig; it shares no code with any other package.

QUICK START
  make
  make tables                 # kl4..kl10 ; n=10 takes about two minutes
  ./kltab 7                   # or any single n from 4 to 11
  ./check.sh
  ./klread 5 02314 23401      ->  02314 23401  1,2
Read a list of pairs instead by giving only n:
  printf '02314 23401\n03214 34201\n' | ./klread 5
Permutations are in one-line notation over the letters 0..n-1.  The output is
x, w and the coefficients of P_{x,w} from the constant term up; 0 means x is
not below w in the Bruhat order.

  ./klread -m 5 03214 34201   ->  03214 34201  1
-m prints mu(x,w) instead: the coefficient of q^{(l(w)-l(x)-1)/2}, which is
the leading coefficient exactly when the degree attains that bound, and 0
otherwise.  It is not held in the tables but read off the polynomial -- note
that the lengths used are those of the pair asked about, since the reductions
preserve P_{x,w} but not l(w)-l(x).

THE TABLES
kltab n writes two files.  Both are streams of unsigned LEB128 varints after a
20-byte header, with the pairs grouped by w and, inside a block, sorted by x;
x and w are held as Lehmer ranks.  Nothing is byte-order dependent.

  kl<n>.pol   x and an index into a dictionary of the distinct polynomials,
              each stored as  deg, a_1, ..., a_deg   for  P = 1 + a_1 q + ...
              The constant term is always 1 and is not stored.
  kl<n>.p1    x and the single number P_{x,w}(1), for uses that need no more.

         n          4    5    6     7      8       9        10        11
         pairs      2    6    72    879    18828   512094   18646043  835990207
         polys      1    4    16    97     1117    24360    981173    58051912
         kl<n>.pol  30   54   309   3063   58 kB   1.62 MB  67.5 MB   3.90 GB
         kl<n>.p1   24   40   257   2678   48 kB   1.18 MB  43.7 MB   2.23 GB
         time            --  instant --            2 s      2 min     3 h 14

Set KLRAW=1 to get, in addition, the older uncompressed layout: KLP<n> (one
64-bit word per pair), Polytab<n>, Polylen<n> and KLMU<n> (the pairs with
mu > 0).  KLP10 alone is 149 MB.

WHICH PAIRS ARE STORED
Only those with P != 1, and only one representative of each class under four
invariances of the Kazhdan-Lusztig polynomials:

  (S)  P_{x,w} = P_{x^-1,w^-1} = P_{w0 x w0, w0 w w0};
  (R1) x may be replaced by the longest element of W_{D_L(w)} x W_{D_R(w)};
  (R2) if x(i)=w(i)=v and #{j<i: x(j)<v} = #{j<i: w(j)<v}, position i and
       value v may be deleted from both;
  (C)  if ws<w, xs<x and x is not <= ws then P_{x,w} = P_{xs,ws}  (s simple;
       likewise on the left).  This one shortens w.

klread applies the same reductions to a query and reports 1 when the reduced
pair is absent.  Concretely a pair is stored iff w is the least of
{w, w^-1, w0ww0, (w0ww0)^-1}, D_R(x) contains D_R(w), D_L(x) contains D_L(w),
x is non-cancelable in the sense of (R2), and x <= ws, x <= sw for every
descent s of w.  The four together are worth a great deal: at n = 10 there are
122,345,174 pairs with P != 1 reduced by (R1) and (R2) alone, 31,627,371 after
the symmetry as well, and 18,646,043 after (C).

LIMITS
n <= 10 is comfortable: two minutes and a few hundred megabytes.

n = 11 works but is a different proposition.  The allocations come to about
13 GB -- the tables for every m from 4 to 11 are held at once and none is
freed -- so 16 GB of memory is the floor and 32 GB is where it will not fight
the page file.  One measured run took 3 hours 14 minutes (11,623 seconds of
mainloop) and wrote 6.1 GB.  Note that nothing is written until the whole
computation is over, so a run that exhausts memory late leaves nothing behind,
and that only the top n is written: "kltab 11" does not leave kl4..kl10, which
"make tables" supplies in two minutes.

"kltab 11" is the way to build it, since "make tables" stops at 10.  While it
runs it prints a line giving the fraction of the pairs computed, roughly every
362880 values of w; the counts and the timing come only at the end.

n = 12 is a question of memory rather than of the program: the indices are
64-bit throughout and the packing still fits (29 bits for the permutation and
33 for the polynomial, in a 64-bit word).  What it needs is of the order of
700 GB -- 340 for the pairs, 224 for the coefficients, 45 for the search tree,
22 for the offsets, plus the tables on S_12 -- so it has been done, but on a
machine with a terabyte of memory.  For anything smaller, the batched variant
KL3.c, which splits the tables and keeps each batch inside 32 bits, is the
way.

WHAT IS VERIFIED
  - the counts of stored pairs, distinct polynomials and mu entries agree with
    the published values for n = 4..9 (check.sh);
  - klread agrees with an independent brute-force computation of the
    recursion on every pair of S_5 and of S_6 -- 14,400 and 518,400 pairs,
    no disagreement -- and on separately computed tables for S_7 and S_8;
  - klread -m reproduces every one of the 6030 records of a separately
    computed table of the pairs with mu > 0 in S_9, and returns 0 on 30,000
    random pairs absent from it;
  - the tables reproduce, byte for byte, ones computed in 2017 by an earlier
    version of the same program, for n = 6, 7, 8, 9 and 10;
  - at n = 11 the run reproduced six independently recorded figures:
    835,990,207 pairs stored, 1,581,103,501 non-cancelable, 58,051,912
    distinct polynomials, 525,741,267 coefficients, 2,345,604 pairs with
    mu > 0, and a longest z-list of 12,469.

REFERENCE
  D. Kazhdan, G. Lusztig, Representations of Coxeter groups and Hecke
    algebras, Invent. Math. 53 (1979), 165-184.
The polynomials and the recursion computed here are those of that paper.
CITATION.cff carries the reference in machine-readable form.
