26
$\begingroup$

Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or maybe this is false?

This problem was proposed long ago on some Russian high school competition, but nobody managed to solve, including jury.

$\endgroup$
7
  • 2
    $\begingroup$ Was the proposer of the problem on the jury? :-) $\endgroup$
    – Seva
    Mar 13, 2011 at 13:37
  • 2
    $\begingroup$ Well, I know who proposed it, he was in the jury and his solution was wrong. Maybe, he is not the author. I may tell you in some non-public place, who is he (you may know him personally), but MO is not for discussing personalities (except Euler or like that) in any sense. $\endgroup$ Mar 13, 2011 at 15:20
  • 2
    $\begingroup$ @Mikhail. Sure, I did. Does it help immediately, do I miss something? :) $\endgroup$ Mar 13, 2011 at 18:39
  • 11
    $\begingroup$ www-math.mit.edu/~rstan/algcomb.pdf Note after the proof of Theorem 6.14. $\endgroup$ Mar 13, 2011 at 20:51
  • 2
    $\begingroup$ This is an exercise in Kac's inf dim lie algs book. You consider the spin rep in type B, restrict to action of principal sl2 and consider weight space decomposition. Alternatively (and equivalently, via Geometric Satake), apply Hard Lefschetz to the variety of Lagrangian subspaces in a symplectic complex vector space. $\endgroup$ Mar 14, 2011 at 2:18

2 Answers 2

34
$\begingroup$

In fact, you cannot prove unimodality of the coefficients of $P_n(x)=(1+x)\cdots (1+x^n)$ using the result about $B_m/G$ mentioned by Qiaochu. The $P_n(x)$ result is implicit in work of Dynkin on the principal sl(2) subalgebra of a complex semisimple Lie algebra. Hughes was the first to realize that a special case of Dynkin's result implied the unimodality of $P_n(x)$. Proctor removed all the Lie algebra theory from the proof, yielding a proof involving only elementary linear algebra. See http://math.mit.edu/~rstan/pubs/pubfiles/72.pdf, esp. equation (23). See also http://math.mit.edu/~rstan/algcomb/algcomb.pdf, beginning on page 90. It is a long-standing open problem to find a combinatorial proof of this unimodality result. I would be extremely impressed if a high school student could prove unimodality by any method.

$\endgroup$
0
4
$\begingroup$

This was originally an answer, but didn't work out; consider it a suggestion. The following is taken from a set of notes on combinatorics by Stanley I can no longer find online.

Let $B_m$ denote the poset of subsets of $\{ 1, 2, ... m \}$. Given a group $G$ acting on $\{ 1, 2, ... m \}$, let $B_m/G$ denote the quotient poset whose elements are orbits of the action of $G$ and where $x \le y$ if some element in the orbit $x$ is contained in some element of the orbit $y$. It is not hard to see that like $B_m$, the quotient $B_m/G$ is graded and rank-symmetric, with rank given by the size of the corresponding subset.

Theorem: $B_m/G$ is unimodal (the size of the ranks increase, then decrease).

The proof is somewhat involved; one defines certain linear operators between the free vector spaces on each rank. According to Stanley there is no known proof without linear algebra.

It seems plausible that the poset of distinct partitions into parts of size at most $n$ might be of the form $B_m/G$ for some $G$, but I have not been able to find such a construction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.