Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Was the proposer of the problem on the jury? :-) –  Seva Mar 13 '11 at 13:37
1  
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. –  Fedor Petrov Mar 13 '11 at 15:20
    
Did you try to multiply this by $(1-x)$?:) –  Mikhail Bondarko Mar 13 '11 at 16:48
1  
@Mikhail. Sure, I did. Does it help immediately, do I miss something? :) –  Fedor Petrov Mar 13 '11 at 18:39
11  
www-math.mit.edu/~rstan/algcomb.pdf Note after the proof of Theorem 6.14. –  darij grinberg Mar 13 '11 at 20:51
show 3 more comments

2 Answers 2

up vote 25 down vote accepted

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.pdf, beginning on page 50. 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.

share|improve this answer
2  
Wow, that's cool. –  GH from MO Mar 13 '11 at 22:45
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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