Pitman's transform
pitman_transform root_system robinson_schensted haskell
Recall that the Robinson-Schensted algorithm (with column or row insertion) can be rewritten as the Pitman's transform of type A. In this note we study the general version of the Pitman's transform as in [{biane-bougerol-oconnell05}], which is the primary source of this note. We describe what it is and show a Haskell implementation using the longest elements of root systems calculated before.
We fix a root system \(R\) with simple roots \(\Delta\) and longest element \(\sigma_0\). Recall from Root systems the Dynkin index \(a_{\alpha\beta}\) and the vector space \(E = \real^q\) where the roots live.
Let \(A\) be the space of \(q\)-dimensional functions on nonnegative integers with zero initial conditions: \(A = \{f:\pint \to E, f(0) = 0\}\). We call any \(f\) in \(A\) a path.
Like the derivation of root systems which starts from simple reflections \(s_\alpha\) for \(\alpha \in \Delta\), the Pitman's transform is also built from operators \(S_\alpha: A \to A\) for \(\alpha \in \Delta\), which are defined in a similar way to the reflections as follows:
\[ S_\alpha f (n) = f (n) - \min_{k = 0 : n} a_{\alpha, f(k)} \alpha. \]Let \(\sigma_0 = s_{\alpha_{i_N}} s_{\alpha_{i_{N - 1}}} ... s_{\alpha_{i_2}} s_{\alpha_{i_1}}\) be a reduced decomposition of the longest element. Then the Pitman's transform \(P: A \to A\) is defined as
\[ P = S_{\alpha_{i_N}} S_{\alpha_{i_{N - 1}}} ... S_{\alpha_{i_2}} S_{\alpha_{i_1}} \]
Here is the Haskell implementation (the complete source code can be found here, also recall the longestElement
function discussed in root_system):
-- |pitman t n xs is the Pitman's transform of type t_n acting on path xs. -- |It pre-processes xs by prepending a row of zeros to the input -- |and post-processes by removing the first row of the output pitman :: Type -> Int -> [[Q]] -> [[Q]] pitman t n xs = tail $ foldr s (prependWithZero xs) (longestElement $ simpleSystem t n) prependWithZero :: [[Q]] -> [[Q]] prependWithZero [] = [] prependWithZero xs = (replicate (length $ head xs) 0) : xs -- |s alpha f: the cumulative infimum of twice the projection of path f on root alpha s :: [Q] -> [[Q]] -> [[Q]] s alpha f = f <<->> fmap (*> alpha) (cumMin $ dynkinIndex alpha <$> f) cumMin :: [Q] -> [Q] cumMin = scanl1 min
We can test its agreement with the Robinson-Schensted algorithm (with column insertion) when \(R\) is of type \(A_n\) and the input path is converted from a word (namely the \(S_{1 : q}\) defined in (1.3) of RS algorithms as Pitman's Transform of type A).
-- |QuickCheck property that the Pitman's transform of type A coincides with RS algorithm -- |robinsonSchensted' is implemented here: -- |https://github.com/ycpei/mathkell/blob/master/Math/Combinatorics/RobinsonSchensted.hs prop_Pitman_RobinsonSchensted :: [Int] -> Bool prop_Pitman_RobinsonSchensted xs = let w = prop_Pitman_RobinsonSchensted_sanitise xs in (pitmanAGTP $ word2Path w) == (gTPFromInt $ sSYT2GTP $ robinsonSchensted' w) prop_Pitman_RobinsonSchensted_sanitise :: [Int] -> Word Int prop_Pitman_RobinsonSchensted_sanitise = W . (fmap (\t -> abs t + 1)) -- |Pitman's transform of type A pitmanA :: [[Q]] -> [[Q]] pitmanA [] = [] pitmanA xs = let n = length $ head xs in if n == 1 then xs else pitman A (n - 1) xs pitmanAShape :: [[Q]] -> [Q] pitmanAShape = last . pitmanA -- |RS via Pitman's transform of type A pitmanAGTP :: [[Q]] -> GTP Q pitmanAGTP = GTP . (pitmanAGTP' []) where pitmanAGTP' :: [[Q]] -> [[Q]] -> [[Q]] pitmanAGTP' xs [] = xs pitmanAGTP' xs ys = pitmanAGTP' ((pitmanAShape ys):xs) (L.transpose $ init $ L.transpose ys) *Main Test.QuickCheck> quickCheck prop_Pitman_RobinsonSchensted +++ OK, passed 100 tests.
The definition of \(P\) does not depend on the choice of the reduced decomposition. Let \(C = \{x \in E: \braket{x, \alpha} \ge 0 \forall \alpha \in \Delta\}\) be the (closed) Weyl chamber of \(R\) (with respect to \(\Delta\), to be more pedantic). Another nice property of \(P\) is that \(P f(n) \in C\) for any \(f \in A\) and \(n \ge 0\). We can check this property, too.
-- |QuickCheck property that the output of the Pitman's transform is in the Weyl Chamber, for any type. prop_Pitman_WeylChamber :: Int -> Property prop_Pitman_WeylChamber m = let (t, n) = int2TypeInt m in forAll (randomQMatrix $ dimensionOfHostSpace t n) (\xs -> isInWeylChamber (simpleSystem t n) (last $ pitman t n xs)) -- |QuickCheck generator that generates rational numbers with small numerators and denominators smallRational :: Gen Q smallRational = do x <- smallInt y <- smallInt return $ (toInteger x) % (toInteger (abs y + 1)) smallInt :: Gen Int smallInt = getSmall <$> (arbitrary :: Gen (Small Int)) randomQMatrix :: Int -> Gen [[Q]] randomQMatrix n = vectorOf 20 $ vectorOf n smallRational *Main Test.QuickCheck> quickCheck prop_Pitman_WeylChamber +++ OK, passed 100 tests.
References
- [biane-bougerol-oconnell05] Littelmann paths and Brownian paths, , Duke Mathematical Journal, Vol. 130, No. 1, p.127–167 2005.