NuMathWiki beta

Here we can discuss half-baked ideas that aren't yet in good enough shape to write in the main page.

[ELIA]:

What Dan wrote about jeu de taquin and LPP reminded me of this: applying RSK and then the Schützenberger involution (to both the lower and upper trapezoidal parts of the matrix) is the same thing as reversing rows and columns of the input matrix and then applying RSK. Namely, we have that $SK = KRC$, defining the following operators on (rectangular) matrices: $S$ is the Schützenberger involution, $K$ is the RSK, $R$ is the row reversion, and $C$ is the column reversion.

The above is related to what Dan wrote in two (related, I think) ways:

1. The Schützenberger involution is intimately related to the jeu de taquin. More precisely, it can be obtained by applying several jeu de taquin operations.
2. Reversing rows and columns of a matrix of exponential random variables with a zero in the bottom right corner gives exactly what Dan has called $(X'_{i,j})$.

Let's consider, as an example, a matrix with i.i.d. Exp(1) entries except a zero in the bottom-right corner, like \[ X= \begin{bmatrix} X_{1,1} &X_{1,2} &X_{1,3} \\ X_{2,1} &X_{2,2} &X_{2,3} \\ X_{3,1} &X_{3,2} &0 \end{bmatrix} \, . \] If we apply RSK to this matrix, we will obtain something of the form \[ Z= \begin{bmatrix} Z_{1,1} &Z_{1,2} &Z_{1,3} \\ Z_{2,1} &Z_{2,2} &Z_{2,3} \\ Z_{3,1} &Z_{3,2} &Z_{3,2}\vee Z_{2,3} \end{bmatrix} \, , \] where $Z_{2,3}$ and $Z_{3,2}$ are the LPP times for paths starting from $(1,1)$ and ending at $(2,3)$ and $(3,2)$ respectively. Notice, however, that not all $Z_{i,j}$'s are the LPP times from $(1,1)$ to $(i,j)$! The bottom right corner is the LPP time on the whole array, i.e. the maximum of $Z_{2,3}$ and $Z_{3,2}$.

Let us now consider the input matrix with rows and columns reversed: \[ X' = (X'_{i,j})_{1\leq i,j\leq 3} =\begin{bmatrix} 0 &X_{3,2} &X_{3,1} \\ X_{2,3} &X_{2,2} &X_{2,1} \\ X_{1,3} &X_{1,2} &X_{1,1} \end{bmatrix} \, . \] If we apply RSK to this matrix, we will obtain a certain matrix $Z'=(Z'_{i,j})_{1\leq i,j\leq 3}$.

For the property of the Schützenberger involution mentioned above, we have that $S(Z') = Z$. In words:

1. Take a matrix, like $X'$, of i.i.d. Exp(1) variables, except for the top-left corner which is a zero.
2. Apply the RSK correspondence.
3. Apply the Schützenberger involution.
4. What you get in positions $(2,3)$ and $(3,2)$ are the two LPP times we're looking for, i.e. $T_{2,3}$ and $T_{3,2}$.

There is a clear analogy – which is probably not a coincidence – with what Dan does, i.e.:

1. Take a matrix, like $X'$, of i.i.d. Exp(1) variables, except for the top-left corner which is a zero.
2. Compute the matrix of LPP times $T'=(T'_{i,j})_{1\leq i,j\leq 3}$. Notice that $T_{1,1}=0$, as $X'_{1,1}=0$.
3. Perform a jeu de taquin sliding operation, more precisely an inward slide into cell $(1,1)$, obtaining $T''=(T''_{i,j})_{1\leq i,j\leq 3, (i,j)\neq (3,3)}$.
4. What you get in positions $(2,3)$ and $(3,2)$, i.e. $T''_{2,3}$ and $T''_{3,2}$, are equal in distribution to the two block finishing times $V^5_2$ and $V^5_3$.

Step 1 is the same in both procedures. Step 2 is not exactly the same, but it's similar, in the sense that $Z'_{i,j} = T'_{i,j}$ for $i=3$ or $j=3$ (however, the other $Z'_{i,j}$'s do not coincide with the $T_{i,j}$'s: the latter are just LPP times on $X'$, while the former can be interpreted as “LPP on non-intersecting paths” on $X'$). Step 3, again, is not the same, but the analogy is evident: the Schützenberger involution can be obtained by applying several jeu de taquin operations. If one can make sense of steps 2 and 3 by concluding that what you obtain in positions $(2,3)$ and $(3,2)$ in both procedures is the same (or at least distributed in the same way), then this would prove the weakened version of the conjecture.

Page/line numbers refer to the version of 10/9/19.

Pending comments:

1. Page 5, definitions in the bottom half of the page: the notation $\widehat{\mathbb{Z}}_{\ge 0}^\lambda$ is another example of uninformative, clunky notation that I think can be improved. I suggest changing it, for example to something like $\operatorname{Tab}_{\mathbb{N}_0}(\lambda)$, $\operatorname{Tab}(\lambda,\mathbb{N}_0)$, $\operatorname{Int}_{\mathbb{N}_0}(\lambda)$, $\operatorname{Int}(\lambda,\mathbb{N}_0)$, etc. (But if you prefer keeping it that's also fine.) [F: I like $\operatorname{Tab}_{\mathbb{N}_0}(\lambda)$] [D: I changed it to $\textrm{IntTab}_{\mathbb{N}_0}(\lambda)$, and changed the notation for general tableaux to $\textrm{Tab}_{\mathbb{N}_0}(\lambda)$ (on second thought the earlier set-theoretic notation was still kind of confusing). Both are defined using the latex macros \tab and \interlacingtab, so it would be easy to change if we decide to do something else later.]
2. Page 6, proof of Lemma 6: the formula for the geometric distribution with parameter $p$ is wrong, it should be $P(X_{i,j}=m)=p(1-p)^{m-1}$, for all integers $m\ge1$ (not for all $m\ge0$ as currently written). Then the two-line display needs to be adjusted to account for this (swap the roles of $p$ and $1-p$ and replace $p^{|\lambda|}$ with $\left(\frac{p}{1-p}\right)^{|\lambda|}$). [F: It is true that this is not the standard definition of geometric r.v. but maybe we want to include 0 in the range of the weights. So perhaps, we can “define” $P(X_{i,j}=m)=p(1-p)^{m}$ for all $m\in\mathbb{N}_0$, closer to the standard definition (modulo a shift).] [D: you're right, I think it's better to start from 0 just because RSK and Bur are set up as bijections from tableaux with entries in $\mathbb{N}_0$. Edited to make that clear.][F: OK. I suggest deleting “(assuming WLOG… $0$)”. ]
3. Page 7, beginning of section 3.1: maybe change the notation “corn” to “corners” (if there is space to make this change)?[F: Done, but it looks too long in formulae and figures. Perhaps we can go back to the original notation diag. (It is informative and I don't think it can cause confusion…)] [D: changed it to “cor”, I think that looks pretty good and isn't weird-sounding like “corn”. We can still change it to something else if anyone wants to.] [F: This is OK for me.]
4. Page 11: “… by the vectors of the discrete finishing times …”: given that we are no longer using the term “finishing times”, I suggest deleting this and just saying “the vectors $\overline{\textrm{cor}}_t$ and $\overline{\textrm{last}}_s$”. [F: this part is only descriptive and I would keep “discrete finishing time” if this helps the reader. If you think it causes confusion than we can remove.]

Comments that were addressed and don't require more discussion: [F: These can be removed now.]

1. Page 1, lines 2-3 of abstract: it's generally a bad idea to have parenthetical remarks in an abstract, I suggest rephrasing using commas. [F: OK, I removed the parenthetical remarks. Feel free to rephrase.] [D: Looks good.]
2. Page 1, line 1 of abstract: LPP is not a Markov process [F: Changed into “random processes”.]
3. Page 1, line -3 of abstract: “C S_{n-1}-valued” is incorrect, I'll fix this when I get editing control of the file. [F: “C S_{n-1}-valued” removed.]
4. Page 1 line -3: delete “i.e.” [F: OK..]
5. Page 1, line 5 of abstract: are we using the term “block finishing times” anywhere else? Probably should rename to “last swap times”. [F: Sure.]
6. Page 1, line -1 of abstract: “cannot be directly deduced from Edelman-Greene” seems like a strong statement that I'm not sure we can stand behind. In any case the abstract doesn't seem to be a useful place to explain subtleties like this since no reader would understand at this point what point we're trying to make. I suggest removing this and discussing it later at an appropriate place. [F: removed.]
7. - Page 2, first lines of section 1.2: for a FPSAC paper I feel it is really necessary to say, “where $\stackrel{D}{=}$ denotes equality in distribution” instead of just using the notation and having its meaning be conveyed implicitly . (For a paper aimed at a probability journal this would be unnecessary.) [F: OK]
8. Page 3, “The last passage percolation model”: the phrase “the waiting times” in parentheses is unclear, I suggest removing it. [F: OK]
9. Page 3, same paragraph: after “of minimal length” I suggest adding “$|c-a|+|d-b|$” to clarify what that means. [F: Added.]
10. Page 3, numbering of Theorem 1 and Conjecture 1 at the bottom: we currently use different numbering for theorems and conjectures, but the numbering for examples and lemmas uses the theorem counter. This is inconsistent, we should either use one counter for all environments, or separate counters for different environments.
11. Page 2 line 3: delete “new” (repetitve). [F: removed]
12. Page 2 line 7: “such as” suggests there are additional correspondences our analaysis relies on, which is incorrect. Also it's grammatically incorrect to use “RSK”, “Burge” and “Edelman-Greene” as stand-alone nouns. Suggest restoring to something along the lines of the previous version: “well-known notions of algebraic combinatoric, namely the RSK, Burge and Edelman-Greene correspondences” (or a compressed version of this that's more correct than the current version). [F: corrected]
13. Page 2, line 3 of section 1.2: LPP is not a Markov process. [F: OK]
14. Page 2, line -5: the word “therefore” is illogical. The claim that the total absorbing time is the maximum of all the last swap times is immediate without having to know the statement in the preceding sentence. [F: corrected]
15. Page 4, last sentence in section 1.2: maybe find a way to mention that this fluctuation result solves the open problem from [3], modulo conjecture 1? [F: slightly rephrased sentence. Check that this is OK.] [D: rephrased slightly, I think it's good now.]
16. Page 5, definition of $L_{i,j}^*$. In the current version the definitions of $L^*(a,b;c,d)$ and $L^*(a,b;c,d)$ seem to be both wrapped up in equation (1.1), should we then remove the $*$ superscript from $L^*(i,1;1,j)$? [F: Right. * removed.]
17. Page 5, definitions in the bottom half of the page: the notation $\mathbb{Z}_{\ge 0}$ seems clunky (it's a pet peeve of mine that it's commonly used by probabilists), maybe we can replace it by $\mathbb{N}_0$ everywhere? If you like the idea, then in line 9 from the bottom we can write: “We denote by $\mathbb{N}_0^\lambda$ the set of tableaux with entries from $\mathbb{N}_0=\mathbb{N}\cup\{0\}$”, and then use $\mathbb{N}_0$ without additional explanation thereafter. [F: I agree. Changed.]
18. Page 6, 2-line math display after “It then follows from (2.4) that”: maybe add “$=(1-p)^{|\lambda|} p^{\sum_{(i,j)\in\lambda} \omega_{i,j}t_{i,j}}$” at the end of the first row? That seems to be a missing step in the calculation and it looks like there is enough space to add it. [F: Added.]
19. Page 7, first sentence of section 3.1: this sentence is unclear, I suggest rephrasing to “Let $\delta_n$ denote the partition $(n-1,n-2,\ldots,1)$ of $N=n(n-1)/2$.” [F: OK]
20. Page 6, lines 8-9: “a crucial fact for our purposes:” is ungrammatical, rephrase (“a fact crucial for our purposes:”, “an important fact:”, “a crucial fact:” would all be correct). [F: Rephrased.]
21. Page 5, lines 4: it is ungrammatical to say “we call tableau of shape lambda any array …”. This pattern “we call [X] any [Y]” (which appears in several other places in later sections, for example line 5 of section 3.1) needs to be rephrased to “We refer to any [Y] as [X]”, or “We define an [X] to be any [Y]”, or “An [X] is a any [Y]” (or possibly other variations that make sense). (By contrast, “We call $x$ an interlacing tableau if …” in the next line is correct.) [F: OK]
22. Page 9: replace the existing Figure 2 with a new version new-fig2.pdf I added in the figures subfolder. [F: Done. ]
23. Page 7, definition of $f_t$, and page 9, definition of $g_s$: I suggest adding an equation number to the definition of $f_t$ and then writing in the line above the definition of $g_s$: “Finally, the generating factor $g_s$ of $s$ is defined, analogously to (insert eq. #), as the rational function”. [F: Done.]
24. Page 10, beginning of section 3.3: improve the inaccurate description involving the group algebra of $S_{n-1}$ [Dan: done]
25. Page 5, we can put Eq. (2.1) in the text if we need to save space. [D: done.]
26. Page 2 line 3: “relating to last passage percolation” is unclear and fails to mention the connection to random sorting networks. I'll work on rephrasing this without making the paragraph longer. [D: fixed this.]
27. Page 7, beginning of section 3.1: “corners' vector” and “corners' permutation” (and “last swaps' vector”, “last swaps' permutation” on the next page) are ungrammatical. What would perhaps make sense is “corner entries vector/permutation”. For the last swaps I can't think of anything more concise than “vector of last swap times”, so maybe we should just give up and not refer to these things by any official name, or have something vague and semi-descriptive like “completion vector”. [F: changed/rephrased]
28. Page 8, before Example 2, in the definition of degree sequence we use the notation #{…}. Maybe replace with |{…}| as above and in Sec. 3.3. [D: fixed.]
29. - Page 3, lines 7-9: this informal description of LPP sounds incorrect to me. I think first passage percolation might have a description along those lines but with LPP there isn't really a “walker” one can speak of in any meaningful sense. [D: rephrased this to avoid mention of a walker.][F: OK.]
30. - Page 2, line -1: the terms “corner growth process”, “corner growth model” refer to the infinite-time process of randomly growing a Young diagram without restrictions on the shape it can fill. If you want to describe a process of growing specifically a staircase-shape Young diagram of order $n$, we should use different terminology (e.g., “staircase corner growth process” or some such variation) or make a comment to clarify the inconsistency with the existing literature. (Also, the corner growth process is a single process with no parameter $n$ which I think makes it more pleasant to use as the basis for our definitions, and is a well-known process, whereas what we are describing in the current version is a family of processes indexed by $n$ that hasn't been defined by anyone. So personally I would stick with the definition from the older version, but I'm fine with any choice as long as the terminology is clear.) [D: I rewrote this slightly to avoid inconsistent terminology, think it's good now.][F: OK.]
31. Page 11: “a realizations” → “a realization” [F: done.]
32. Page 9, line -3: “a symbolic algebra software” → “symbolic algebra software”. [F: done.]
33. Page 11: “clorrespond” → “correspond” [F: done.]
34. Page 5, line -11: “the so-called Greene's theorem” is clunky, and “so-called” is unnecessary for a FPSAC audience. I suggest changing this to “we first recall Greene's theorem”. [F: done.]
35. Page 3, after Eq. (1.1): replaced “described in detail in [15, Ch. 4]” → “see [15, Ch. 4]”.
36. Page 7, Example 1 (and Example 2 later): I removed the \mathbf and changed a couple of colours. Feel free go reverse / modify. [D: looks good]
37. Page 2, last sentence of 1.1: replaced “additional…additional” → “additional…the”.
38. The abstract needs to be improved. [D: I rewrote it.]
39. Page 5, lines 8-9 from the bottom: I see I forgot to make the change in the definition of $\Pi_{m,n}^{(k)}$ (to a disjoint union of paths instead of a $k$-tuple) and only applied it to $\Pi_{m,n}^{*(k)}$. [D: fixed.]
40. Page 7, before Eq. (3.2): replaced “when performing a simple random walk … the probability of observing the sequence” → “in a simple random walk … the probability of the sequence”.