10
$\begingroup$

As mentioned in the post on Stanley's 25 positivity problems, Tatsuyuki Hikita posted a preprint on October 16, 2024 purporting to prove Problem 21, the Stanley–Stembridge conjecture about e-positivity of chromatic symmetric functions of (3+1)-free posets. The argument is essentially elementary and, at least to me, seems plausible. The key new formula (6) in particular strikes me as either true and provable or false.

My questions:

  1. Has anybody coded Hikita's (6) and checked it computationally?
  2. Has anybody checked the details of the proof, or found a flaw in the argument? That is, has the Stanley–Stembridge Conjecture been settled in the affirmative?

If this post is not deemed appropriate for MO, I'm sure it will be swiftly removed. Normally I would simply wait, but the argument is sufficiently elementary that it seems quickly checkable for those with the time and inclination, and the conjecture is very well-known. I'm also considering including the proof in an upcoming graduate course, if it holds up, and would like to know if I should invest time in it. Nobody I've asked has gotten further into the details than myself, so I thought I would ask more widely here.

$\endgroup$
8
  • $\begingroup$ While I see nothing wrong with this post, I wonder, why won't you yourself be the change you want to see in this world and do 1 and/or 2? Especially since (sorry, I looked at your profile) you seem to be a combinatorialist, it should be right up your alley! And if you include it in your course I sure hope you at least understand the proof before presenting it to the students, so if the answer is yes you would anyway have to do this... $\endgroup$ Commented Nov 5 at 22:29
  • 5
    $\begingroup$ It is long established policy that questions about the correctness of preprints (especially ones claiming to prove well known conjectures) are off-topic. I have voted to close. $\endgroup$ Commented Nov 6 at 11:42
  • 2
    $\begingroup$ I'm more accepting than many of questions on MO that ask about the status of big conjectures, because I think in some areas it can be known among experts that a claimed proof from 20 years ago is wrong and a grad student might not have this insider info. But in this case I have to side with @AndyPutman: the preprint has only been out for a month, there is no consensus, for an answer you're at most going to get one person's opinion. $\endgroup$ Commented Nov 6 at 14:37
  • 3
    $\begingroup$ @JoshuaP.Swanson see meta.mathoverflow.net/questions/927 and other linked questions on meta. $\endgroup$ Commented Nov 6 at 21:05
  • 1
    $\begingroup$ I’m voting to close this question because I support the general policy against asking about correctness of preprints, although this particular case is not so bad. $\endgroup$ Commented Dec 5 at 19:28

2 Answers 2

11
$\begingroup$

Regarding question (1), I coded Hikita's (6) this evening. It checks out through $n \leq 7$ and, for connected graphs, $n=8$. Here's my Jupyter notebook, which I ran with SageMath 10.2.rc4.

Personally I'm convinced. I don't see how Hikita's (6) could possibly fail for higher $n$ for this particular problem, and I don't see how a proof could fail to follow from Hikita's (6). We may have to wait for the usual referee process to officially settle my question (2), though I've heard through the grapevine others are in the process of checking proof details. For my own part, I at least will act as if the Stanley–Stembridge conjecture has been settled in the affirmative.

Hopefully the above is useful to someone, particularly students who must carefully decide where to invest their precious time.

$\endgroup$
8
  • $\begingroup$ I have seen guesses for Schur expansion of unicellular LLT polynomials that works for n in that range. I have seen conjectures for Macdonald polynomials fail for n=9. But if you could please run the code for n up to 10 (enough for connected graphs which reduces it a bit), then I'd be much more confident. There is also the Symmetric functions and algebraic combinatorics group on Facebook who also discuss this recent breakthrough. $\endgroup$ Commented Nov 13 at 8:02
  • $\begingroup$ @PerAlexandersson I'm certainly familiar with conjectured formulas which only fail after a while, though somehow my sense is this is not one of them. Speculation aside, the method I've used for the q-chromatic quasisymmetric functions (just Sage's generic method) is too slow to reasonably run beyond $n=8$, and that would probably take all night. You're certainly welcome to improve the code though! I'd love a more robust stress test. I included a couple of little examples at the end. I am not on Facebook, (un?)fortunately. $\endgroup$ Commented Nov 13 at 8:13
  • 1
    $\begingroup$ (continued) The definition is in some sense designed to make the induction argument work. It's not concocted to fit empirical data. If the theorem (or definition) is wrong then one would expect to quickly detect a mismatch with empirical data. $\endgroup$ Commented Nov 16 at 16:42
  • 1
    $\begingroup$ @TimothyChow Yes, that's essentially my intuition here too. For the record, I actually think the recursion defining the RHS of (6) is fairly straightforward as far as the tableau combinatorics is concerned, though the weights are technical. It isn't even as complicated as pipe dreams, say. I could potentially imagine guessing the formula, if one had the audacity to look for it in the first place. The rational functions and normalization certainly obscure matters. $\endgroup$ Commented Nov 16 at 23:43
  • 1
    $\begingroup$ @JoshuaP.Swanson Yes, I suspect that Hikita, motivated by the fact that the modified coefficients of $X_G(q)$ sum to 1, came to suspect that something like (6) was true, and "reverse engineered" the definition of $p_T$ using the modular law. By the way, as early as October 2022, Logan Crew and Sophie Spirkl told me that they had noticed that replacing $e_i$ with $e_i/i!$ in $X_G$ caused the coefficients to sum to 1, but Logan said, "I am certain we are not the first people to notice this, although I couldn't say for sure anything more." So I don't think this fact is published anywhere. $\endgroup$ Commented Nov 17 at 13:01
7
$\begingroup$

This is not really an answer to the question, but I thought it might be helpful to restate Hikita's main result (at least for $q=1$) in a way that may make it easier for people to quickly understand what it is saying, and then write their own code to verify it computationally for small examples.

As a preliminary step, given positive real parameters $a_1,b_1,a_2,b_2,\ldots,a_m,b_m$, let us describe a random variable $X(a_1,b_1,\ldots,a_m,b_m)$ whose value lies in the set $\{1,2,\ldots,m+1\}$. Arrange $2m+1$ real numbers $$ A_0 < B_1 < A_1 < B_2 < A_2 < B_2 < \cdots < A_m < B_m $$ on the real line, such that for all $i$, $a_i = B_i - A_{i-1}$ and $b_i = A_i - B_i$. We throw $m$ darts at certain subintervals of the real line. The first dart is thrown at $[A_0,A_1]$, meaning that we pick a uniformly random number in the interval $[A_0,A_1]$. The parameters for the second dart throw depend on the outcome of the first dart throw. If the first dart lands on the Left (or $L$ for short), meaning in $[A_0,B_1)$, then we Leave the left endpoint alone, and throw the second dart at the interval $[A_0,A_2]$. If the first dart lands on the Right (or $R$ for short), meaning in $[B_1,A_1]$, then we Ratchet up the left endpoint, and throw the second dart at the interval $[A_1,A_2]$. In general, the $i$th dart is thrown at an interval whose right-hand endpoint is $A_i$ and whose left-hand endpoint is either the same as it was for the previous throw (if the outcome of the previous throw was $L$) or is $A_{i-1}$ (if the outcome of the previous throw was $R$). If the $i$th dart lands in $[B_i,A_i]$ then we declare that the $i$th outcome is $R$; otherwise we declare that the $i$th outcome is $L$. In this way we obtain a sequence of $m$ letters, each of which is either $L$ or $R$. Finally, we let $X(a_1,b_1,\ldots,a_m,b_m)$ be 1 plus the index of the rightmost $R$ (if there is no such index then we let $X(a_1,b_1,\ldots,a_m,b_m) = 1$).

As an example, the reader can check that for $m=2$, $$\eqalign{ \Pr(X=1) &= \biggl( {a_1\over a_1+b_1}\biggr) \biggl({a_1+b_1+a_2\over a_1 + b_1 + a_2 + b_2}\biggr)\cr \Pr(X=2) &= \biggl({b_1\over a_1+b_1}\biggr) \biggl({a_2\over a_2+b_2}\biggr) \cr \Pr(X=3) &= \biggl({b_2\over a_2+b_2}\biggr) \biggl({a_2 + b_1+b_2\over a_1+a_2+b_1 + b_2}\biggr)\cr }$$ The formula for $\Pr(X=3)$ is not so obvious, but it is correct; this is the content of Hikita's Lemma 6.

[EDIT: In the important special case where the $a_i$ and $b_i$ are all positive integers, my colleague Doug Jungreis came up with an equivalent but simpler definition of $X(a_1,b_1,\ldots,a_m,b_m)$. For all $i$, let $s_i := \sum_{j=1}^i (a_j + b_j)$, and let $M := s_m$. Generate a uniformly random permutation $\pi \in \mathfrak{S}_M$. Then let $X$ be the smallest $i\ge 1$ such that the largest element of $\{\pi_{s_{i-1}+1}, \pi_{s_{i}+2}, \ldots, \pi_{s_j}\}$ lies in the subset $\{\pi_{s_{i-1}+1}, \pi_{s_{i}+2}, \ldots, \pi_{s_{j-1}+a_j}\}$ for all $j\ge i$. If there is no such $i$, then let $X = m+1$. The proof that this description is equivalent is not too difficult; the main subtle point to check is that generating a single random permutation can simulate all $m$ dart throws, even though we are "reusing randomness" when intervals overlap.]

Now suppose we are given a (naturally labeled) unit interval graph $G$ on the vertex set $\{1,2,\ldots,n\}$. For $i=1,2,\ldots,n$, let $h'_i$ be the number of vertices less than $i$ that are not adjacent to $i$. (Hikita uses the notation $e_i$ rather than $h'_i$, but I want to reserve the notation $e_i$ for the $i$th elementary symmetric function.) For example, if $G$ is the path on four vertices, with edges $\{1,2\}$ and $\{2,3\}$ and $\{3,4\}$, then $h'_1=0$, $h'_2 = 0$, $h'_3 = 1$, and $h'_4 = 2$. We now describe a random process (depending on $G$) for generating a standard Young tableau with $n$ boxes, one box at a time.

There is no choice about where to put box 1. When it comes time to place box $i$ (for $i>1$), we define (for all $j\ge 1$) $\delta_j$ to be 1 if the partial tableau constructed so far has a box in column $j$ whose entry is greater than $h'_i$. Otherwise, we let $\delta_j = 0$. The sequence $(\delta_j)$ consists of alternating segments of 0's and 1's, so we can write it uniquely in "compressed form" as $1^{b_0}0^{a_1}1^{b_1}0^{a_2}1^{b_2} \cdots 0^{a_m}1^{b_m}0^\infty$ for some nonnegative integer $m$ and some nonnegative integers $b_0, \ldots, b_m$ and $a_1,\ldots, a_m$ (where $b_0$ may be zero but all the rest are strictly positive). Now we generate a random number $X(a_1,b_1,\ldots,a_m,b_m)$ as described earlier (if $m=0$ then we set $X=1$). Finally, we put the box with entry $i$ in the column corresponding to the first $0$ of $0^{a_X}$ (if $X=m+1$ then we interpret $0^{a_X}$ as the $0^\infty$ at the end).

Continuing our example of the path with four vertices, at step 2, the delta sequence is $1^10^\infty$, so $m=0$ and we have no choice but to put box 2 at the start of $0^\infty$, i.e., in column 2 of the standard Young tableau we are building. At step 3, the delta sequence is $1^00^11^10^\infty$, so $m=1$ and with probability 1/2 we put box 3 in column 1 (call this Case A) and with probability 1/2 we put box 3 in column 3 (call this Case B). At step 4, if we are in Case A, then the delta sequence is $1^10^\infty$ and we are forced to put box 4 in column 2; if we are in Case B then the delta sequence is $1^00^21^10^\infty$, so we put box 4 in column 1 with probability 2/3 and in column 4 with probability 1/3. All told, three of the SYT with four boxes have a positive probability of being generated, and their probabilities are 1/2, 1/3, and 1/6 respectively.

Let $p_T(G)$ denote the probability that SYT $T$ is generated. Then Hikita's main theorem (for $q=1$) is that for all partitions $\lambda = (\lambda_1, \lambda_2, \ldots)$, $${c_\lambda\over \prod_i \lambda_i!} = \sum_{T\colon {\text{shape}}(T)=\lambda} p_T(G),$$ where $c_\lambda$ is the coefficient of $e_\lambda$ in the elementary symmetric function expansion of the chromatic symmetric function $X_G$.

$\endgroup$
2
  • 2
    $\begingroup$ Thanks for this reformulation. Is it possible to restate it in purely enumerative terms? $\endgroup$ Commented Nov 28 at 2:09
  • 3
    $\begingroup$ @RichardStanley An excellent question. I don't know. Part of the problem is that if we multiply both sides by the denominator of the LHS, there remain denominators on the RHS, e.g., if $h'=(0,0,0,1,2,3)$ and $\lambda=(5,1)$ and $T$ has a 4 or a 5 in the second row. I suspect, though I don't have a proof, that if we multiply both sides by $n!$, then all denominators are cleared on the right-hand side, but even if that's true, I'm not sure how much that helps. Ideally, I'd like to translate the "dart game" into marking up the SYT in some way, but I don't see a (natural) way to do that. $\endgroup$ Commented Nov 29 at 14:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .