math.CO — Combinatorics

Analytic q-inequalities and a proof of Bergeron's conjecture

Contributed by Veronica Phan

For integers $1\le a\le b\le c\le d$ with $ad=bc$, Bergeron asked whether the difference of Gaussian binomial coefficients $\binom{b+c}{b}_q-\binom{a+d}{a}_q$ has nonnegative coefficients. We prove that it does, and more generally that $\binom{b+c}{b}_q-\binom{a+d}{a}_q$ has nonnegative coefficients whenever $a\le b\le c$ and $ad\le bc$, a strengthening proposed by Troyka. The proof is analytic rather than bijective. We develop a toolkit for coefficientwise inequalities, including a coefficientwise local limit theorem for Gaussian polynomials based on Irwin--Hall densities, and use it in a Pascal-type induction that proves the case $a\le 20$. For general $a$ the problem reduces to a two-parameter inequality between linearly interpolated Gaussian polynomials. Near its base case this inequality reduces exactly to the monotonicity of rational $q$-Catalan numbers. Using the circle method with explicit error terms, we prove the conjecture of Chen, Wang and Wang that the coefficients of MacMahon's $q$-Catalan numbers $C_n(q)$ are unimodal for every $n\ge16$, and an analogue for the rational $q$-Catalan numbers $C_{x,N+1}(q)$ with $x\le N\le 2x$. Beyond this range the difference splits into two nonnegative parts, which we compare degree by degree using local limit bounds for Gaussian polynomials that are uniform in both parameters. The proof is computer-assisted: it uses exact integer and rational arithmetic, ball arithmetic, and one floating-point computation with a proved error bound. The scripts and the logs of their runs are provided as ancillary files.