It was recently shown using techniques inspired by algebraic geometry (by Huh and Adiprasito-Huh-Katz) that the chromatic polynomial of a graph (or matroid) has coefficients that satisfy log-concavity. Since the coefficients are integers, we can also ask if they satisfy any p-adic identities or inequalities. Are there any conjectures or results in this direction?
-
2$\begingroup$ Small nitpick: the AHK result uses algebraic geometry only by way of analogy. $\endgroup$– Sam HopkinsJan 20, 2021 at 23:15
-
$\begingroup$ Thanks, edited! $\endgroup$– AsvinJan 21, 2021 at 1:12
-
1$\begingroup$ The question sounds interesting, but I am not too used to p-adic things. Do you have an example of a graph and it's chromatic polynomial that exhibits some type of relation you have in mind? Also, as @SamHopkins says AHK does not have actually algebraic geometry, but if I understand correct Huh's earlier work for chromatic polynomials (and matroids representable over char 0) does actually have algebraic geometry. Not sure if that is relevant/helpful to the p-adic story. $\endgroup$– John MachacekJan 22, 2021 at 2:52
-
$\begingroup$ I don't have anything concrete in mind! I guess maybe a place to start would be for chromatic polynomials that look like $\prod_i (t-n_i)$ for positive integers $n_i$? $\endgroup$– AsvinJan 22, 2021 at 2:55
-
2$\begingroup$ Not really answering your question but here's one connection between the characteristic polynomials of matroids and "mod p" stuff: if we have a $n$-dimensional hyperplane arrangement defined over $\mathbb{Z}$ then the evaluation of its matroid's characteristic polynomial at a prime $p$ counts the number of points of $\mathbb{F}_p^n$ in the complement of the hyperplane arrangement (with maybe finitely many bad primes $p$ as exceptions). Of course for a graph this is just saying evaluating its chromatic polynomial at $p$ counts ways to color it with $p$ colors. $\endgroup$– Sam HopkinsJan 22, 2021 at 3:07
1 Answer
I am not aware of any conjectures or results in this direction, and I am not so optimistic because it seems to be a hard question even for binomial coefficients. So I think your suggestion of studying coefficients of polynomials of the form $\prod_i (t - n_i)$ is good, but I don't know what to expect.
Some references on $p$-adic properties of binomial coefficients:
Wikipedia, divisibility properties of binomial coefficients.
Erdos, Graham, Ruzsa, Straus, On the prime factors of $\binom{2n}{n}$.
Spiegelhofer and Wallner, Divisibility of binomial coefficients by powers of 2.
We get binomial coefficients from taking the chromatic polynomial of a tree with $n$ edges, which is $$ \chi_\text{tree}(t) = t(t-1)^n = \sum_{k=0}^n (-1)^k \binom{n}{k} t^{n-k+1} . $$ The binomial coefficients are unimodal in the archimedean norm, but are far from unimodal $p$-adically. In fact, if $n$ is even, then the $2$-valuation of the sequence $\binom{n}{0}, \binom{n}{1}, \binom{n}{2},\ldots$ will alternate between getting larger and smaller, so in a sense behaves completely "opposite" to being unimodal. At another extreme, if $n = 2^m - 1$, then the binomial coefficients $\binom{n}{k}$ are all odd, so have the same size $2$-adically.
The binomial coefficients have a nice archimedean limit as $n \to \infty$, up to an appropriate rescaling, but the $p$-adic limit seems more complicated.
For instance, in the paper above Spiegelhofer and Wallner show that the 2-valuations of the binomial coefficients do obey a close-to normal distribution, but in the sense where we ignore the order of the sequence $\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \ldots$ and only count how many times numbers of a given $p$-adic size appear.
Another reason it seems challenging to find a proper $p$-adic analogue:
Adiprasito-Huh-Katz showed that the log-concavity in the archimedean norm comes from the Hodge-Riemann relation in degrees 0 and 1 (applied to the Chow ring of a graph / matroid), which says a certain matrix with integer entries must have indefinite signature. Namely, log concavity of $a_{i-1}, a_i, a_{i+1}$ is equivalent to $$ a_{i-1}a_{i+1} \leq a_i^2 \quad\Leftrightarrow\quad \det \begin{pmatrix} a_{i-1} & a_i \\ a_i & a_{i+1} \end{pmatrix} \leq 0. $$ So what's important is not exactly the valuation $x \mapsto |x|$ that measures the size of a number, but the fact that the integers (and reals) are totally ordered so that it makes sense to distinguish positive and negative numbers. So one approach may be to ask: Is there any reason to expect a $p$-adic version of the Hodge-Riemann relation? (I have no idea..) Generally, is there a $p$-adic analogue of the signature of a bilinear form?
-
$\begingroup$ This question struck me while listening to your talk in the Washington seminar, so it's very nice to hear from you :) $\endgroup$– AsvinFeb 7, 2021 at 16:05
-
1$\begingroup$ Reading your answer, it strikes me that we perhaps shouldn't look for a relation between consecutive indices (ie, close in archimedean sense) but rather between coefficients corresponding to indices that are close in a p-adic sense. Do you know of a relation for binomial numbers in this sense? That is, between numbers of the form ${n}\choose{r + p^k}$ for varying $k$? I am sure(?) they satisfy some congruence but how about something like convexity? $\endgroup$– AsvinFeb 7, 2021 at 16:09
-
1$\begingroup$ As for a p-adic analogue of the signature, bilinear forms over local fields are classified by their rank, determinant (upto squares which lands in a 4 element set) and a product over Hilbert symbols. I don't know if there is a p-adic version of the Hodge-Riemann relation... $\endgroup$– AsvinFeb 7, 2021 at 16:16