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.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Was the proposer of the problem on the jury? :-) $\endgroup$
    – Seva
    Commented 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$
    – Fedor Petrov
    Commented Mar 13, 2011 at 15:20
  • 2
    $\begingroup$ @Mikhail. Sure, I did. Does it help immediately, do I miss something? :) $\endgroup$
    – Fedor Petrov
    Commented Mar 13, 2011 at 18:39
  • 11
    $\begingroup$ www-math.mit.edu/~rstan/algcomb.pdf Note after the proof of Theorem 6.14. $\endgroup$
    – darij grinberg
    Commented 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$
    – Peter McNamara
    Commented Mar 14, 2011 at 2:18

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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