Skip to main content
1 of 3
Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279

I can prove a related result. Perhaps someone can modify the proof to solve Dominic's problem.

I use multivariate notation such as $x^\alpha=x_1^{\alpha_1}\cdots x_n^{\alpha_m}$, where $\alpha=(\alpha_1,\dots,\alpha_m)$. Let $\alpha\in \{0,1,2,\dots\}^m$ and $\beta\in\{0,1,2,\dots,n\}$. Let $f(\alpha,\beta)$ be the number of $m\times n$ matrices with entries $0,1,2$, and with each entry equal to 1 colored either red or blue, with row sum vector $\alpha$ and column sum vector $\beta$.

Theorem. $$ f(\alpha,\beta) \leq f((n,n,\dots,n),(m,m,\dots,m)). $$

Proof. Let $g(\alpha,\beta)$ be the number of $m\times n$ matrices with entries $-2,0,2$, and with each entry equal to 0 colored either red or blue, with row sum vector $\alpha$ and column sum vector $\beta$. By dividing each entry of such a matrix by 2 and then adding 1, it is clear that $$ f(\alpha,\beta)=g\left(2\alpha-2(n,\dots,n), 2\beta-2(m,\dots,m)\right). $$ Hence we want to show that $$ g(\alpha,\beta) \leq g((0,0,\dots,0),(0,0,\dots,0)). $$

We have for fixed $m,n$ that $$ \sum_{\alpha,\beta} g(\alpha,\beta)x^\alpha y^\beta = \prod_{r=1}^m\prod_{s=1}^n (x_r^{-1}y_s^{-1}+x_ry_s)^2. $$ Since for any integer $k$ we have $\int_0^{2\pi}e^{ikx}dx = 1$ if $k= 0$ and otherwise is $0$, it follows that $$ g(\alpha,\beta) = \frac{1}{(2\pi)^{m+n}} \int_0^{2\pi}\cdots \int_0^{2\pi} e^{-i(\alpha_1 \theta_1+\cdots+ \alpha_m\theta_m+\beta_1\psi_1+\cdots+\beta_n\psi_n)}\\ \prod_{r=1}^m\prod_{s=1}^n (e^{-i(\theta_r+\psi_s)} +e^{i(\theta_r+\psi_s)})^2\,d\theta\,d\psi. $$ Now $(e^{-i(\theta_r+\psi_s)}+e^{i(\theta_r+\psi_s)})^2$ is a nonnegative real number. Hence by the triangle inequality, \begin{eqnarray*} g(\alpha,\beta) & \leq & \frac{1}{(2\pi)^{m+n}} \int_0^{2\pi}\cdots \int_0^{2\pi} \prod_{r,s=1}^n (e^{-i(\theta_r+\psi_s)} +e^{i(\theta_r+\psi_s)})^2\,d\theta\,d\psi\\ & = & g((0,\dots,0),(0,\dots,0)).\ \Box \end{eqnarray*}

Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279