2
$\begingroup$

Let $[n]:=\{1,\dots,n\}$. Fix a set partition $\rho$ of $[n]$, with an abuse of notation we shall use $\rho\vdash [n]$.

I would like to estimate the following alternating sum.

QUESTION. Is this true? $$\left\vert\sum_{\sigma\, \vdash \rho}(-1)^{\vert\sigma\vert}(\vert\sigma\vert-1)! \left(\prod_{C\in\sigma} \left(1-\frac1N\right)\cdots \left(1-\frac{(\sum_{D\in C}\vert D\vert)-1}N\right)\right)\right\vert\lesssim_n N^{1-\vert\rho\vert},$$ where the sum is over all set partitions of $\rho$ and $\vert\cdot\vert$ indicates the number of blocks.

$\endgroup$
9
  • 1
    $\begingroup$ What are you summing over here? $\endgroup$ Commented Oct 16 at 18:48
  • 2
    $\begingroup$ I believe the sum is over partitions $\sigma$ which are finer than $\rho$. There are lots of problems with the current formulation though. Is $N$ the same as $n$? Should the product be over blocks $C$ of $\rho$ instead of $\sigma$ so then the sum over $D$ is over $\sigma$ blocks inside the block $C$ of $\rho$? Is $|D|$ the number of points in $D$? For the estimate to make sense are we taking the max of the left-hand side over $\rho$?... $\endgroup$ Commented Oct 16 at 20:07
  • 2
    $\begingroup$ BTW the question (even in need of clarification) looks very interesting to me, because lots of estimates of this kind occur in rigorous statistical mechanics. The main topic here is Moebius inversion in the partition lattice, following Rota, Groeneveld, Penrose,... $\endgroup$ Commented Oct 16 at 20:08
  • $\begingroup$ Also, is $D\in C$ a typo? $\endgroup$ Commented Oct 16 at 20:50
  • 1
    $\begingroup$ @T.Amdeberhan: Ok I think I understand, except what is $N$. It is nowhere defined. I also have eyes to see an absolute value is taken on the LHS. $\endgroup$ Commented Oct 16 at 22:29

1 Answer 1

7
$\begingroup$

First I will rephrase the question, and then I will solve the rephrased problem.

Let ${\rm Part}_n$ denote the set of set partitions of $[n]=\{1,2,\ldots,n\}$. For $\Theta,\Pi\in {\rm Part}_n$, we will say that $\Theta$ is finer than $\Pi$ and write $\Theta\le \Pi$, when $$ \forall A\in\Theta, \exists B\in\Pi, A\subset B\ . $$ The $\subset$ notation here allows equality. This defines the well-known partition lattice $({\rm Part}_n,\le)$. The smallest element denoted by $\hat{0}$ is the partition made of singletons. The largest element denoted by $\hat{1}$ is the single block partition. We will use $\vee$ to denote the join or supremum of two partitions in ${\rm Part}_n$.

The lattice has a Möbius function $\mu(\Theta,\Pi)$ given by the entries of the matrix $(\mu(\Theta,\Pi))_{\Theta,\Pi\in{\rm Part}_n}$ which by definition is the inverse of the matrix $(\mathbf{1}\{\Theta\le \Pi\})_{\Theta,\Pi\in{\rm Part}_n}$. We used the notation $\mathbf{1}\{\cdots\}$ for the indicator function equal to $1$ if the enclosed condition is true, and equal to $0$ if the condition is false. An explicit formula for the Möbius function is given by $$ \mu(\Theta,\Pi)=\prod_{A\in\Pi}\left[(-1)^{s(\Theta,A)-1}(s(\Theta,A)-1)!\right] $$ where $s(\Theta,A)$ is the number of blocks of $\Theta$ contained in $A$.

The following lemma reflects the graded/ranked property of the partition lattice.

Lemma: If $\Theta_1,\Theta_2\in{\rm Part}_n$, then $|\Theta_1\vee\Theta_2|\ge|\Theta_1|+|\Theta_2|-n$.

Proof: For $i=1,2$, pick $F_i$ a forest (subgraph of the complete graph with no circuit) whose partition of connected components is $\Theta_i$. We have $|\Theta_i|=n-|F_i|$. By eliminating redundant edges which create circuits instead of new connections, pick a forest $F_3\subset F_1\cup F_2$ such that the partition of connected components of $F_3$ is exactly $\Theta_1\vee\Theta_2$. Since $|F_3|\le |F_1|+|F_2|$, the wanted inequality follows.

The notation $(x)_k:=x(x-1)\cdots(x-k+1)$ is for the falling factorial. We now define $$ K_{\Pi}(N):=\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left[\prod_{j=1}^{|A|-1}\left(1-\frac{j}{N}\right)\right] $$ $$ =\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left(\frac{(N-1)_{|A|-1}}{N^{|A|-1}}\right) $$ $$ =\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left(\frac{(N)_{|A|}}{N^{|A|}}\right) $$ $$ =-N^{-n}\ P_{\Pi}(N) $$ where we introduced the polynomial, in $N$, $$ P_{\Pi}(N):=\sum_{\Theta\ge \Pi}\mu(\Theta,\hat{1}) \prod_{A\in\Theta} (N)_{|A|}\ . $$ If I understood correctly, the question is to show the existence of a constant $C_n$, only depending on $n$, such that for all $N>0$ $$ |K_{\Pi}(N)|\le C_n N^{1-|\Pi|}\ , $$ i.e., $$ |P_{\Pi}(N)|\le C_n N^{n-|\Pi|+1}\ . $$ The means the degree of the polynomial $P_{\Pi}$ is at most $n-|\Pi|+1$.

Using Stirling numbers of the first kind, and their definition in terms of permutations in the symmetric group $\mathfrak{S}_k$, we have $$ (x)_k=\sum_{\rho\in\mathfrak{S}_k}{\rm sgn}(\rho) x^{c(\rho)} $$ where $c(\rho)$ is the number of cycles of the permutation $\rho$. Grouping permutations according to the set partition corresponding to their cycles we have $$ (x)_k=\sum_{\Theta\in{\rm Part}_k}(-1)^{k-|\Theta|}x^{|\Theta|} \prod_{A\in\Theta}(|A|-1)! $$ $$ =\sum_{\Theta\in{\rm Part}_k}\mu(\hat{0},\Theta)x^{|\Theta|} $$ where the Möbius function is that of ${\rm Part}_k$. By taking the product of the previous identity over the blocks of some partition $\Theta\in{\rm Part}_n$, and expanding, we have $$ \prod_{A\in\Theta} (N)_{|A|}=\sum_{\Gamma\le\Theta}\mu(\hat{0},\Gamma)N^{|\Gamma|} $$ where the Möbius function is that of ${\rm Part}_n$.

As a result, $$ P_{\Pi}(N)=\sum_{\Theta\ge\Pi}\mu(\Theta,\hat{1}) \left(\sum_{\Gamma\le \Theta}\mu(\hat{0},\Gamma)N^{|\Gamma|}\right) $$ $$ =\sum_{\Gamma\in{\rm Part}_n}\mu(\hat{0},\Gamma)N^{|\Gamma|} \left(\sum_{\Theta\ge \Pi\vee\Gamma}\mu(\Theta,\hat{1})\right) $$ $$ =\sum_{\Gamma\in{\rm Part}_n}\mu(\hat{0},\Gamma)N^{|\Gamma|}\mathbf{1}\{\Pi\vee\Gamma=\hat{1}\} $$ and the degree bound immediately follows from the Lemma.

As an aside, here are two more ways to write the polynomial $P_{\Pi}(N)$. $$ P_{\Pi}(N)=\sum_{\rho\in\mathfrak{S}_n}\mathbf{1}\{\langle\tau,\rho\rangle\ {\rm transitive}\} {\rm sgn}(\rho)N^{c(\rho)}\ . $$ Here $\tau$ is a fixed permutation whose cycle partition is $\Pi$. The sum is over permutations $\rho$ such that the subgroup of the symmetric group, generated by $\tau$ and $\rho$, acts transitively on $[n]$. $$ P_{\Pi}(N)=\sum_G \mathbf{1}\{G\ \Pi-{\rm connects}\ [n]\} (-1)^{|G|}N^{C(G)} $$ where the sum is over subgraphs $G$ of the complete graph $K_n$, seen as a set of edges, with the condition that $G$ together with a forest that has $\Pi$ as partition of connected components, connects the entire set $[n]$. Here $C(G)$ is the number of connected components of $G$. The last formula is related to the Whitney-Tutte-Fortuin-Kasteleyn representation of the chromatic polynomial (for the complete graph). See this article by Sokal, in particular for the relation to rigorous statistical mechanics.


Addendum: One has the more precise result that the degree of $P_{\Pi}(N)$ is exactly $n+1-|\Pi|$, because the sign of $\mu(\hat{0},\Gamma)$ is $(-1)^{n-|\Gamma|}$. The coefficient of $N^{n+1-|\Pi|}$ is $$ (-1)^{|\Pi|-1}\sum_{\Gamma\in{\rm Part}_n} \mathbf{1}\{|\Gamma|=n+1-|\Pi|,\Pi\vee\Gamma=\hat{1}\} \prod_{A\in\Gamma}(|A|-1)! $$ which is easily seen to be nonzero. I don't know if one can actually compute its value.

$\endgroup$
6
  • $\begingroup$ This is fascinating. Need to check. $\endgroup$ Commented Oct 17 at 21:00
  • $\begingroup$ To connect with your notation: my $\Pi$ is your $\rho$. Then one goes from your $\sigma$ to my $\Theta$ by flattening in the sense of Mathematica, i.e., removing some $\{\}$. More precisely, the blocks of $\Theta$ are the subsets of $[n]$ of the form $\cup_{D\in C}D$ where $C\in\sigma$. $\endgroup$ Commented Oct 17 at 21:10
  • $\begingroup$ BTW my proof does the $t_i=1$ case of your older question mathoverflow.net/questions/256572/… $\endgroup$ Commented Oct 17 at 21:15
  • $\begingroup$ These kind of Moebius inversion formulas for set partition lattices are also related to the transformation between moments and cumulants of probability distributions. Any chance what you’ve written here has some interpretation in that probabilistic language? $\endgroup$ Commented Oct 17 at 22:57
  • $\begingroup$ @SamHopkins: I am not sure about "interpretation". The relation between moments and cumulants in probability is a particular case of a problem in statistical mechanics which is the Mayer/cluster expansion for the polymer gas. See the three notes (under "additional material") I wrote for a course mabdesselam.github.io/Math845S09.html This is also related to an answer I gave to a question on physics stackexchange physics.stackexchange.com/questions/829848/… $\endgroup$ Commented Oct 17 at 23:19

You must log in to answer this question.

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