\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{amsthm,amsmath,amssymb}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\sloppy



\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Prob}{\text{\bf{P}}}
\newcommand{\tilG}{\widetilde{\Gamma}_{\ell,k}}
\newcommand{\tilC}{\widetilde{C}_\ell}
\newcommand{\blam}[1][]{\mbox{\boldmath{$\lambda_{#1}$}\unboldmath}}
\newcommand{\brho}[1][]{\mbox{\boldmath{$\rho_{#1}$}\unboldmath}}
\newcommand{\blamprime}[1][]{\mbox{\boldmath{$\lambda'_{#1}$}\unboldmath}}
\newcommand{\brhoprime}[1][]{\mbox{\boldmath{$\rho'_{#1}$}\unboldmath}}
\newcommand{\x}{\mbox{\boldmath{$x$}\unboldmath}}
\newcommand{\z}{\mbox{\boldmath{$z$}\unboldmath}}
\newcommand{\e}[1][]{\mbox{\boldmath{$e_{#1}$}\unboldmath}}
\newcommand{\cbold}[1][]{\mbox{\boldmath{$c$}\unboldmath}}
\newcommand{\y}{\text{\bf{y}}}
\newcommand\calA{\mathcal{A}}
\newcommand\calG{\mathcal{G}}
\newcommand\calM{\mathcal{M}}
\newcommand\calL{\mathcal{L}}
\newcommand\calR{\mathcal{R}}
\newcommand\calS{\mathcal{S}}
\newcommand\Z{\mathbb{Z}}

\renewcommand\phi{\varphi}
\renewcommand\emptyset{\varnothing}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{theorem*}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\numberwithin{equation}{section}

\theoremstyle{definition}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{procedure}[theorem]{Procedure}

\theoremstyle{remark}
\newtheorem*{remark*}{Remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\newtheorem*{example*}{Example}



\title{Symmetric polynomials and symmetric mean inequalities}


\author{Karl Mahlburg
\thanks{Partially supported by an NSF Postdoctoral Fellowship
administered by the Mathematical Sciences Research Institute through
its core grant DMS-0441170 and by NSF Grant DMS-1201435..} \\
\small Department of Mathematics \\[-0.8ex]
\small Louisiana State University \\[-0.8ex]
\small Baton Rouge, LA 70803 \\[-0.8ex]
\small\tt mahlburg@math.lsu.edu
\and
Clifford Smyth 
%\thanks{Partially supported by an NSF Postdoctoral Fellowshipadministered by the Mathematical Sciences Research Institute throughits core grant DMS-0441170 and by NSF Grant DMS-1201435..}
\\
\small Department of Mathematics and Statistics \\[-0.8ex]
\small University of North Carolina Greensboro \\[-0.8ex]
\small Greensboro, NC 27402 \\ [-0.8ex]
\small\tt cdsmyth@uncg.edu
}

\date{\dateline{XX}{XX}\\
\small Mathematics Subject Classifications: 05E05, 26E60, 60C05}

\begin{document}


\maketitle

\begin{abstract}
We prove generalized arithmetic-geometric mean inequalities for quasi-means arising from symmetric polynomials.  The inequalities are satisfied by all positive, homogeneous symmetric polynomials, as well as a certain family of non-homogeneous polynomials; this family allows us to prove the following combinatorial result for marked square grids.

Suppose that the cells of a $n \times n$ checkerboard are each independently filled or empty, where the probability that a cell is filled depends only on its column.  We prove that for any $0 \leq \ell \leq n$, the probability that each column has at most $\ell$ filled sites is less than or equal to the probability that each row has at most $\ell$ filled sites.

\bigskip\noindent \textbf{Keywords:} symmetric means; symmetric polynomials; arithmetic-geometric mean inequality

\bigskip\noindent \textbf{MSC: 60C05,05E05,26E60,05C80}
\end{abstract}


\section{Introduction}

Let $n$ be a positive integer.  We define an $n$-variable {\it orthant function} to be a continuous function $F : \R_{\geq 0}^n \rightarrow \R_{\geq 0}$ such that $F(\x) = F(x_1, \dots, x_n)$ is monotonically increasing in each $x_i$ and that also has a strictly increasing {\it diagonal restriction}, $f_F(y) = F(y, \dots, y)$.  Given an $n$-variable orthant function $F$, we define the following $n$-variable orthant functions associated with $F$: the {\it quasi-arithmetic mean},  the {\it quasi-geometric mean}, and the {\it quasi-mean}; respectively, they are \begin{align}
\calA_F(\x) &:= f_F^{-1} \left(\frac{f_F(x_1) + \dots + f_F(x_n)}{n}\right), \\
\calG_F(\x) &:= f_F^{-1} \left( \prod_{j = 1}^n f_F(x_j)^{\frac{1}{n}}\right), \notag \\
\calM_F(\x) &:= f_F^{-1} \left( F(x)\right). \notag
\end{align}
Note that these means have been studied classically (see \cite{HLP52}, Chapter III).

Some care is needed to verify that these definitions are well-defined.  One must note that since $f_F(y)$ is strictly increasing and continuous, its range $R := f_F(\R_{\geq 0})$ is of the form $R = [f_F(0), M)$ or $[f_F(0),+\infty)$,  according to the value $M = \lim_{y \to +\infty} f_F(y)$.  Furthermore, $f_F$ is a bijection and $f_F^{-1}$ is strictly increasing and continuous.  Since $R$ is closed under taking arithmetic and geometric means of its elements, $\calA_F(x)$ and $\calG_F(x)$ are well-defined.  Since $F$ is monotonically increasing in each variable, it also satisfies 
\begin{equation*}
f_F(\underline{\x}) \leq F(\x) \leq f_F(\overline{\x}) 
\end{equation*} 
where $\underline{\x} := \min\{x_i: 1 \leq i \leq n\}$ and $\overline{\x} := \max\{x_i: 1 \leq i \leq n\}$.  This implies that $F(\R_{\geq 0}^n) = R$ and so $\calM_F(x)$ is well-defined also.

If $M = \calA_F, \calG_F,$ or $\calM_F$, we therefore have that $M$ is a {\it quasi-mean}.  In particular,  $M$ satisfies the following usual properties of a mean: it is continuous and monotonically increasing in each variable, $\underline{\x} \leq M(\x) \leq \overline{\x}$ for all $\x \in \R_{\geq 0}$, and $M(y, \ldots, y) = y$ for all $y \geq 0$.  Note that the $f_F^{-1}$ in the definition of $M$ ensures the final ``identity'' property, $M(y, \ldots, y) = y$.  However, $M$ is not necessarily linearly homogeneous, i.e. we do not necessarily have $M(\lambda \x) = \lambda M(\x)$ for all $\lambda \geq 0$ and $\x \in \R_{\geq 0}^n$.  The function $F(\x) = (1 + x_1)(1+x_2)$ provides a simple counterexample for each type of $M$.

Since $f_F$ and hence $f_F^{-1}$ are strictly increasing, $\calA_F$ and $\calG_F$ are strictly increasing in each variable. An arithmetic-geometric mean inequality between $\calG_F$ and $\calA_F$ also easily follows: for all $\x \in \R_{\geq 0}^n$,
\begin{equation*}
\calG_F(\x) \leq \calA_F(\x),
\end{equation*}
with equality if and only if all $x_i$ are equal.  This is also Theorem 85 of \cite{HLP52}, with $\psi = \log f_F$, $\chi = f_F$, and $q \equiv 1/n$.  Note that the classical arithmetic-geometric mean inequality can be recovered from this by setting $F(\x) = (x_1 \cdots x_n)^{1/n}$.

In this paper we study functions whose quasi-means provide a refinement of the preceding arithmetic-geometric mean inequality.  Namely, we are interested in $\calS$, which we define to be the set of all orthant functions $F$ for which
\begin{equation}
\label{E:G<M<A}
\calG_F(\x) \leq \calM_F(x) \leq \calA_F(\x), \qquad \text{ for all $\x \in \R_{\geq 0 }^n$}.
\end{equation}

\begin{proposition}
\label{P:S}
The set $\calS$ satisfies the following properties.
\begin{enumerate}
\item
\label{P:S:symm}
If $F(x_1, \dots, x_n)$ is a homogeneous symmetric polynomial with positive coefficients, then $F \in \calS$.
\item
\label{P:S:add}
If $F_i(x_1, \dots, x_n) \in \calS$ for $i = 1,2$, then $F_1 \cdot F_2 \in \calS$.
\end{enumerate}
\end{proposition}
\begin{remark}
The set $\calS$ is not closed under addition.  For example, $F(\x) = 1 + x_1x_2$ is the sum of two homogeneous functions but $\calG_F \leq \calM_F$ fails to hold when $x_1 \neq x_2$.
\end{remark}

For integers $\ell$ and $n$ with $0 \leq \ell \leq n$ we define
\begin{equation}
\label{E:eta}
\eta_\ell(\x) := \sum_{j = 0}^\ell \sum_{\substack{I \subseteq [n] \\ |I| = j}} x_I,
\end{equation}
where we have adopted the common notation $x_I := \prod_{i \in I} x_i$, along with the convention $x_\emptyset = 1$.  Note that $\eta_\ell$ is an orthant function if and only if $\ell \geq 1$.  We denote the diagonal restriction of $\eta_\ell$ by
\begin{equation}
\label{E:mu}
\mu_\ell(y) := \eta_\ell(y, \dots, y) = \sum_{j=0}^\ell \binom{n}{j} y^j.
\end{equation}

In Section 3 we will prove the following result, which states that $\eta_\ell \in \calS$ for $1 \leq \ell \leq n.$
\begin{theorem}
\label{T:main}
If $\ell$ and $n$ are integers with $0 \leq \ell \leq n$ and $n \geq 1$, then
\begin{equation*}
\left(\prod_{i = 1}^n \mu_\ell(x_i)\right)^{1/n} \leq \eta_\ell(\x)
\leq \frac{1}{n} \sum_{i=1}^n \mu_\ell(x_i), \text{ for all $\x \in \R_{\geq 0}^n$}.
\end{equation*}

Equality holds throughout if and only if $\ell = 0$, $\ell=n$, or $x_1 = \cdots = x_n$. \end{theorem}

These quasi-mean inequalities have an appealing application to combinatorial probability.  Let $\{X_{ij}, 1 \leq i,j \leq n\}$ be a collection of independent Bernoulli random variables with probability $p_j$; in other words, $\Prob(X_{ij} = 1) = p_j$ and $\Prob(X_{ij} = 0) = 1 - p_j$.  Using these, we further define the random variables 
\begin{align*}
%\label{E:CRdef}
C_j &:= \sum_{i=1}^n X_{ij} \quad \text{ for } 1 \leq j \leq n, \\
R_i &:= \sum_{j=1}^n X_{ij} \quad \text{ for } 1 \leq i \leq n. \notag
\end{align*}
Using Theorem \ref{T:main}, we prove bounds relating the distributions of the $C_j$s and $R_i$s.
\begin{theorem}
\label{T:CR}
Suppose that $p_1, \ldots, p_n \in [0,1].$
If $\ell$ is an integer with $0 \leq \ell \leq n$, then
\begin{equation*}
\Prob\left(\max_{1 \leq j \leq n}\{C_j\} \leq \ell\right) \leq \Prob\left(\max_{1 \leq i \leq n}\{R_i\} \leq \ell\right)
\end{equation*}
\end{theorem}
Theorem \ref{T:CR} has two immediate combinatorial reformulations: one to marked square grids and another to random bipartite graphs. First, suppose that markers are independently placed in the squares of an $n$ by $n$ grid such that the probability that a marker is placed in a square depends only on that square's column.  Then for all integers $\ell$ with $0 \leq \ell \leq n$, the probability that every column has at most $\ell$ markers is less than or equal to the probability that each row has at most $\ell$ markers.

Alternatively, suppose that $G$ is a finite complete bipartite graph with bipartition $(A,B)$, where $|A| = |B| = n$.  Let $H$ be a random subgraph of $G$ where each edge $e$ of $G$ is independently selected to belong to $H$ with a probability that depends only on the left vertex $e \cap A$.  If $\ell \geq 0$, then
\begin{equation*}
\Prob\left(\max_{a \in A} \left\{ d_H(a) \right\} \leq \ell\right) \leq \Prob\left(\max_{b\in B} \left\{d_H(b)\right\} \leq \ell\right).
\end{equation*}

\begin{remark}
In the grid formulation, both events in the inequality require that at most $n \ell$ squares be occupied.  Similarly, both events in the bipartite graph formulation require that there be at most $n \ell$ edges.
\end{remark}

The remainder of the paper is as follows.  In Section \ref{S:symm} we study the basic properties of homogeneous symmetric polynomials and the functions in $\calS$, and also prove Proposition \ref{P:S}.  In Section \ref{S:Proof} we use Lagrange multipliers and polynomial inequalities to prove Theorem \ref{T:main}.   We conclude in Section \ref{S:Colrow}, where we describe the relationship between the quasi-mean inequalities and combinatorial probability, and prove Theorem \ref{T:CR}.


\section{Properties of symmetric polynomials and $\calS$}
\label{S:symm}

As found in Chapter 7 of \cite{Sta99}, one can define various homogeneous (graded) bases for the ring of symmetric polynomials on $n$ variables; we will make explicit use of the {\it elementary symmetric polynomials} $\{e_j(\x) \; \mid \; 0 \leq j \leq n\}$, where the degree $j$ polynomial is defined as $e_j(\x) := \sum \{x_I : I \subseteq [n], |I| = j\}$.  We will also use the {\it monomial symmetric polynomials}, which are defined as follows.

For a positive integer $n$, let $\Delta(n) := \{\blam \in \R_{\geq 0}^n: \lambda_1 \geq \cdots  \geq \lambda_n\}$, and define the {\it weight} of such a vector $\blam$ as $\left| \blam \right| := \lambda(1) + \dots + \lambda(n).$  If $\blam \in \Delta(n)$, the monomial symmetric polynomial associated to $\blam$ is defined as
\begin{equation}
\label{E:M}
M_{\blam}(\x) := \frac{1}{n!} \sum_{\sigma \in S_n} x_{\sigma(1)}^{\lambda(1)} \cdots x_{\sigma(n)}^{\lambda(n)}.
\end{equation}
Note that this is homogeneous of degree $\left| \blam \right|.$

We now recall various inequalities between symmetric polynomials.  Suppose that $\blam[i] = (\lambda_i(1), \dots, \lambda_i(n)) \in \Delta(n)$ for $i \in \{1, 2\}$.  We say that $\blam[1]$ {\it majorizes} $\blam[2]$ if and only if
$\left| \blam[1] \right| = \left| \blam[2] \right|$, and
\begin{equation*}
\lambda_1(1) + \dots + \lambda_1(j) \geq \lambda_2(1) + \dots + \lambda_2(j)
\end{equation*}
for all $1 \leq j < n$.  In this case, we write $\blam[1] \succeq \blam[2]$.  Muirhead's inequalities can be concisely stated as follows.
\begin{theorem*}[Muirhead \cite{Muir03}]
Suppose that $\blam[1], \blam[2] \in \Delta(n)$.  The inequality
\begin{equation}
\label{E:Muirhead}
M_{\blam[1]}(\x) \geq M_{\blam[2]}(\x)
\end{equation}
is satisfied for all $\x \in \R_{\geq 0}^n$ if and only if $\blam[1] \succeq \blam[2]$.
\end{theorem*}
Note that \cite{Muir03} only contains the case where both $\blam[i]$ have integral parts, while \cite{HLP52} (Theorem 45, p. 45) contains the general result above.
We also recall the following elementary result from the general theory of series inequalities; see \cite{HLP52} (Theorem 368, p. 261).
\begin{theorem*}[Rearrangement Inequality]
Suppose that $a_1 \geq \dots \geq a_n \geq 0$ and $b_1 \geq \dots \geq b_n \geq 0$.  If $\sigma \in S_n$ is a permutation, then
\begin{equation}
\label{E:Rearrange}
\sum_{i = 1}^n a_i b_i \geq \sum_{i=1}^n a_i b_{\sigma(i)}.
\end{equation}
\end{theorem*}

Our final preliminary observations address the inequalities in \eqref{E:G<M<A} individually.  Let $\calL$ denote the set of orthant functions $F$ that satisfy the left inequality:
\begin{equation*}
\calG_F(\x) \leq \calM_F(\x), \text{ for all $\x \in \R_{\geq0}^n$,}
\end{equation*}
and let $\calR$ denote the set of orthant functions that satisfy the right inequality:
\begin{equation*}
\calM_F(\x) \leq \calA_F(\x),  \text{ for all $\x \in \R_{\geq0}^n$.}
\end{equation*}
Clearly we have $\calS = \calL \cap \calR$.  The following properties follow immediately from the definitions of the quasi-means.
\begin{proposition}
\label{P:LR} The classes $\calL$ and $\calR$ have the following closure properties:
\begin{enumerate}
\item If $F_i \in \calL$ for $i = 1,2$, then $F_1^a \cdot F_2^b \in \calL$ for all $a,b \geq 0$.
\item
\label{P:LR:R}
If $F_i \in \calR$ for $i = 1,2$, then $a F_1 + b F_2 \in \calR$ for all $a,b \geq 0$.
\end{enumerate}
\end{proposition}

The preceding facts now allow us to prove our first result about $\calS$.
\begin{proof}[Proof of Proposition \ref{P:S}]
We first prove statement \ref{P:S:symm}.
Suppose $F$ is a homogeneous symmetric polynomial with positive coefficients and total degree $w$.  It can be written as
\begin{equation}
\label{E:Fdef}
F(\x) = \sum_{i = 1}^k a_i M_{\blam[i]}(\x),
\end{equation}
where $a_i > 0$, $\blam[i] \in \Delta(n)$ and $\left| \blam[i]\right| = w$ for all $i$.  Writing $A := \sum_{i = 1}^k a_i > 0$, Muirhead's theorem \eqref{E:Muirhead} then implies that
\begin{equation}
\label{E:Fineq}
A \cdot M_{(w/n, \dots, w/n)}(\x) \leq F(\x) \leq A \cdot M_{(w, 0, \dots, 0)} (\x), \mbox{ for all $\x\in \R_{\geq 0 }^n$}.
\end{equation}
We finish the proof by showing that this is equivalent to the statement $F \in \calS$.  Since $f_F(y) = F(y, \dots, y) = A y^w$,
we find that the leftmost expression in \eqref{E:Fineq} is the same as
\begin{equation*}
A \cdot \frac{1}{n!} \cdot \left(x_1 \cdots x_n\right)^{w/n} \cdot n! = \left(\prod_{i=1}^n f_F(x_i)\right)^{1/n}.
\end{equation*}
Similarly, the rightmost expression in \eqref{E:Fineq} equals
\begin{equation*}
A \cdot \frac{1}{n!} \left(x_1^w + \dots + x_n^w\right) \cdot (n-1)! = \frac{1}{n} \sum_{i=1}^n f_F(x_i).
\end{equation*}
This completes the first part of the proof.


We now turn to statement \ref{P:S:add}. Throughout this part of the proof we write $f_i$ as shorthand for $f_{F_i}$.  By part 1 of Proposition \ref{P:LR} we need only show that if $F_i \in \calS$ for $i = 1,2$, then $F_1 \cdot F_2 \in \calR.$  This is equivalent to showing that
\begin{equation}
\label{E:F1F2}
(F_1 F_2)(\x) \leq \frac{1}{n} \sum_{i=1}^n f_{F_1 F_2}(\x),
\end{equation}
and we can immediately rewrite $f_{F_1 F_2} = f_1 \cdot f_2$.  Using the assumption that $F_i \in \calR$, we find that the left side of \eqref{E:F1F2} satisfies
\begin{equation}
\label{E:F1F2sum}
(F_1 F_2)(\x) \leq \left( \frac{1}{n} \sum_{i = 1}^n f_1(x_i)\right) \left( \frac{1}{n} \sum_{i = 1}^n f_2(x_i)\right)
= \frac{1}{n^2} \sum_{i_1, i_2 = 1}^n f_1(x_{i_1}) f_2(x_{i_2}).
\end{equation}
Define the one-step shift cyclical permutation by $\sigma(i) := i+1$ for $1 \leq i \leq n-1,$ and $\sigma(n) := 1$.  Reordering the $x_i$ if necessary so that $x_1 \geq \dots \geq x_n \geq 0$, we then further rewrite the sum from \eqref{E:F1F2sum} as
\begin{equation*}
%\label{E:F1F2sum}
\frac{1}{n^2} \sum_{i_1, i_2 = 1}^n f_1(x_{i_1}) f_2(x_{i_2})
= \frac{1}{n^2} \sum_{j = 0}^{n-1} \sum_{i = 1}^n f_1(x_i) f_2\left(x_{\sigma^j(i)}\right).
\end{equation*}
The Rearrangement Inequality, \eqref{E:Rearrange}, now implies that the largest term in the outer summation occurs when $j=0$, so
\begin{equation}
(F_1 F_2)(\x) \leq \frac{1}{n} \sum_{i=1}^n (f_1 f_2)(x_i),
\end{equation}
which verifies \eqref{E:F1F2}.
\end{proof}




\section{Proof of Theorem \ref{T:main}}
\label{S:Proof}

\subsection{Overview}

In this section we prove Theorem \ref{T:main}, devoting most of our effort to the left inequality.  In particular, we consider the level sets of $\eta_{\ell}(\x)$ and then apply the technique of Lagrange multipliers in order to determine the extremal behavior of
\begin{equation*}
U(\x) := \prod_{j = 1}^n \mu_{\ell}(x_j)^{\frac{1}{n}}.
\end{equation*}

For each $R$ in the range of $\eta_\ell$ on $\R^n_{\geq 0}$, define the surface $\Omega(R) = \{ \x \in\R^n_{\geq 0} : \eta_\ell(\x) = R\}$.   Given $d>0$ and an integer $k$ with $1 \leq k \leq n$, we define $\cbold_k(d) = d(\e[1] +\cdots + \e[k]) \in \R^n$, where $\e[i]$ is the $i$-th standard basis vector.  We refer to a point in $\R_{\geq 0}^n$ as a {\it $k$-diagonal} point if it is any coordinate permutation of a point of the form $\cbold_k(d)$ for some $d >0$.

\begin{lemma} \label{L:Lagrange}
If  $1 \leq \ell \leq n-1$, $1< R < \infty$, and $\z$ is a maxima of $U(\x)$ on $\Omega(R)$ then $\z$ is a $k$-diagonal point for some $k$ with $1 \leq k \leq n$.
\end{lemma}
\noindent
We will prove Lemma \ref{L:Lagrange} in Section \ref{S:Proof:Lag} using the method of Lagrange multipliers (see Theorem \ref{T:Lagrange}).

By the symmetry of $f$ and $\eta_\ell$, if we restrict our attention to a single point $\x \in \R_{\geq 0}^n$, we may assume that there is some $0 \leq k \leq n$ such that $x_1, \ldots, x_k >0$ and $x_{k+1} = \cdots = x_n = 0$.  With this in mind,
we generalize the functions defined in \eqref{E:eta} and \eqref{E:mu} by setting
\begin{align}
\label{E:ell,k}
\eta_{\ell, k}\left(\x\right) & :=  \eta_\ell\left(x_1, \dots, x_k, 0, \dots, 0\right) , \\
\mu_{\ell, k}(y) & := \eta_\ell(\underbrace{y, \ldots,y}_\text{$k$ times}, 0, \ldots, 0). \notag
 \end{align}
These are related to our earlier definitions by $\eta_\ell = \eta_{\ell, n}$ and $\mu_\ell = \mu_{\ell, n},$ and we also have the further relations
\begin{align}
\eta_{\ell, k}(\x) = \sum_{\substack{I \subseteq [k] \\ |I| \leq \ell}} x_I, \qquad
\mu_{\ell, k}(y) = \eta_{\ell,k}(y,\ldots,y) & = \sum_{j = 0}^\ell \binom{k}{j} x^j,
\end{align}
and finally, $\eta_{\ell, k}(\x) = \eta_{k, k}(\x) = \prod_{i=1}^k (1 + x_i)$ if $\ell \geq k$.
\begin{lemma} \label{L:maj}
If $0 \leq \ell \leq n$, $1 \leq k \leq n$, and $y \geq 0$, then
\begin{equation*}
\mu_{\ell,n}^k(y) \leq \mu_{\ell,k}^n(y).
\end{equation*}
The inequality is tight if and only if $\ell = 0$, $\ell = n$, $y=0$ or $k=n$.
\end{lemma}

We will prove Lemmas \ref{L:Lagrange} and \ref{L:maj} in Sections \ref{S:Proof:Lag} and \ref{S:Proof:Maj}, respectively.  We now show how they imply Theorem \ref{T:main}.
\begin{proof}[Proof of Theorem \ref{T:main}]
If $\ell = 0$ or $\x =0$, then all terms in the two inequalities are equal to $1$.  If $x_1 = \cdots = x_n = y$ then all terms are identically equal to $\mu_\ell(y)$.   If $\ell = n$, the left inequality is an identity and the right inequality is an application of the arithmetic-geometric mean inequality.  In general, the right inequality follows from Proposition \ref{P:S} part \ref{P:S:symm} and Proposition \ref{P:LR} part \ref{P:LR:R}.  So it suffices to prove the left inequality in the case where $\x \in \R^n_{\geq 0}$, $\x \neq 0$ and $1 \leq \ell \leq n-1$.

Since $\eta_\ell$ is strictly increasing in each variable, a non-zero $\x$ is contained in the surface $\Omega(R)$ with $R = R(\x) = \eta_\ell(\x) > \eta_\ell(0) = 1$.  Since $\eta_\ell(\x) \geq 1+ x_i$ for all $1 \leq i \leq n$, $\Omega(R)$ is bounded.  Since $\eta_\ell(\x)$ is continuous, $\Omega(R)$ is also closed, and hence compact.

This means that there exists at least one point $\z \in \Omega(R)$ at which $f(\x)$ takes its maximum value on $\Omega(R)$. Since $R >1$, $\z \neq 0$ and, by Lemma \ref{L:Lagrange}, $\z=\cbold_k(d)$, for some $1 \leq k \leq n$ and $d >0$.  By Lemma \ref{L:maj}, if $k < n$, then
\begin{equation*}
f(\z) = (\mu_{\ell,n}(d))^\frac{k}{n} < \mu_{\ell,k}(d) = \eta_\ell(\z) = R.
\end{equation*}
However, if $k=n$, we have $f(\z) = \mu_\ell(d)= \eta_\ell(\z) = R$.

\end{proof}

\subsection{Lagrange multipliers and maxima}
\label{S:Proof:Lag}

In this section we prove Lemma \ref{L:Lagrange} using Proposition 3.3.1 of \cite{B95}, p.284.  We restate this result as Theorem \ref{T:Lagrange}, a form more suitable to our purposes.

\begin{theorem}[The method of Lagrange multipliers with inequality constraints.]
\label{T:Lagrange}
Let $f,h_1,\ldots,h_m,g_1,\ldots,g_r: \R^n \to \R$ be continuously differentiable functions.  Suppose $\z$ is a point at which $f(\x)$ has a local maximum over $\Omega = \{\x : h_1(\x)=\cdots=h_m(\x) = 0, g_1(\x), \ldots, g_r(\x) \geq 0\}$.  Suppose also that $\z$ is regular, i.e. $\{\nabla h_1(\z), \ldots, \nabla h_m(\z)\} \cup \{\nabla g_i(\z) :  i\in A(\z)\}$ is a linearly independent set where $A(\x) := \{1 \leq j \leq r : g_j(\x) = 0\}$. Then there exist unique Lagrange multiplier vectors $\blamprime \in \R^m$ and $\brhoprime \in \R_{\geq0}^r$, such that
\[\begin{array}{rl}
\frac{\partial L}{\partial x_i}(\z,\blamprime,\brhoprime) = 0,& 1 \leq i \leq n,\\
\rho'_j =  0,&  j \not \in A(z)
\end{array}\]
where $L(\x,\blam,\brho):= f(\x) + \sum_{i=1}^m \lambda_i h_i(\x) + \sum_{j=1}^r \rho_j g_j(\x)$.
\end{theorem}

\begin{proof}[Proof of Lemma \ref{L:Lagrange}]
Theorem \ref{T:Lagrange} applies to the present setting with $\Omega(R)$ as the set $\Omega$, constraint function $h(\x) := \eta_\ell(\x) - R$, and inequality constraints $g_i(\x) := x_i$ for $1 \leq i \leq n$.   The Lagrangian function is then
\begin{equation*}
L(\x,\lambda,\brho) := U(\x) + \lambda (\eta_l(\x) - R) + \sum_{i=1}^n \rho_i x_i.
\end{equation*}

Let $\z \in \Omega(R)$ be a point at which $U(\x)$ attains its maximum value over $\Omega(R)$.  Since $R > 1$, $\z$ has at least one non-zero coordinate.  By symmetry we may assume $z_1, z_2, \ldots, z_k >0$ and $z_{k+1} = \ldots = z_n = 0$ for some $k \geq 1$. Since $\nabla h(\z)$ trivially has positive coordinates, $\nabla h(\z)$ together with $\nabla g_i(\z) = \e[i]$, for $k+1 \leq i \leq n$, form a linearly independent set.  Thus $\z$ is regular, and the conditions of Theorem \ref{T:Lagrange} are met.

The theorem statement now implies that there is a constant $\lambda'$ such that
\begin{equation*}
\frac{1}{n} \frac{\mu_{\ell,n}'(z_i)}{\mu_{\ell,n}(z_i)} U(\z) + \lambda' \frac{\partial \eta_\ell}{\partial x_i} (\z)= 0, \qquad 1 \leq i \leq k.
\end{equation*}
It is trivial to check that $U(\z) \geq 1$ and $\frac{\partial \eta_\ell}{\partial x_i} (\z) \geq 1$ for all $i$ with $1 \leq i \leq n$. Thus, if we define
\begin{equation*}
\gamma_i := \frac{1}{n} \frac{\mu_{\ell,n}'(z_i)}{\mu_{\ell,n}(z_i) \frac{\partial \eta_\ell}{\partial x_i}(\z) },
\qquad  1 \leq i \leq k,
\end{equation*}
then $\gamma_1 = \cdots  = \gamma_k = -\lambda'/f(z)$.
Note that
\[\gamma_i = \frac{\sum\limits_{j=0}^{\ell - 1} \binom{n-1}{j}z_i^j}
{\mu_{\ell,n}(z_i) \sum\limits_{j=0}^{\ell - 1}
\sum\limits_{\substack{I\subseteq [k]-i \\ |I| = j}} z_I},
\qquad  1 \leq i \leq k.\]

If $j,k$ are non-negative integers, define
$$
Z_{j,k} := \sum_{\substack{I \subseteq [k] \setminus \{1,2\} \\ |I| = j}} z_I.
$$
Suppose that $z_3, \dots, z_k$ are fixed.  We will show that the equality $\gamma_1 = \gamma_2$ holds if and only if $z_1 = z_2$. By symmetry, this will then prove that $z_1 = \cdots = z_k$, completing the proof that $\z$ is a $k$-diagonal point.

Observe that we can write
\begin{equation}
\label{E:gamma1}
\gamma_1 = \frac{\sum\limits_{j=0}^{\ell - 1} \binom{n-1}{j}z_1^j}
{\mu_{\ell,n}(z_1) \left((1 + z_2) \sum_{j=0}^{\ell - 2} Z_{j,k}
+ Z_{\ell - 1,k} \right)},
\end{equation}
and
\begin{equation}
\label{E:gamma2}
\gamma_2 = \frac{\sum\limits_{j=0}^{\ell - 1} \binom{n-1}{j}z_2^j}
{\mu_{\ell,n}(z_2) \left((1 + z_1) \sum_{j=0}^{\ell - 2} Z_{j,k}
+ Z_{\ell - 1,k}\right)}.
\end{equation}
Comparing \eqref{E:gamma1} and \eqref{E:gamma2}, it is now clear that
$\gamma_1 = \gamma_2$ if and only if $\Gamma_{\ell,k}(z_1) = \Gamma_{\ell,k}(z_2)$, where
\begin{equation}
\label{E:Gamma}
\Gamma_{\ell,k}(y) := \frac{\sum\limits_{j=0}^{\ell - 1} \binom{n-1}{j}y^j \cdot
\left((1 + y) \sum_{j=0}^{\ell - 2} Z_{j,k}
+ Z_{\ell - 1,k}\right)}
{\mu_{\ell,n}(y)}.
\end{equation}

To conclude, we show that $\Gamma_{\ell,k}(y)$ is strictly decreasing on $[0,\infty)$ and, hence, one-to-one.  Note that
$$\Gamma_{\ell,k}(y) = \tilG(y) \cdot \left(A + \frac{B}{1+y}\right),$$
where
$$
\tilG(y) := \frac{\sum\limits_{j=0}^{\ell - 1} \binom{n-1}{j}y^j \cdot
(1 + y)}{\mu_{\ell,n}(y)}.
$$
and where $A, B > 0$ are constants.  We show that $\tilG'(y) < 0$.  This implies $\tilG(y)$ is strictly decreasing and hence $\Gamma_{\ell,k}(y)$ is strictly decreasing as well.
Simple algebra shows that
$$
\tilG(y) = 1 - \frac{\binom{n-1}{\ell} y^\ell}{\sum_{j = 0}^\ell \binom{n}{j}y^j},
$$
and thus
$$
\tilG'(y) = \binom{n-1}{\ell} \cdot \frac{-\ell y^{\ell-1} \sum_{j = 0}^\ell \binom{n}{j}y^j
+ y^\ell \sum_{j = 0}^\ell j \binom{n}{j} y^{j-1}}
{\mu_{\ell,n}(y)^2}.
$$
The numerator simplifies to
$$
-z^{\ell}\sum_{j=0}^\ell (\ell - j) \binom{n}{j} y^j < 0,
$$
and the proof is complete.
\end{proof}



\subsection{Majorization and polynomial inequalities}
\label{S:Proof:Maj}

In this section we use a partial order on polynomials in order to prove Lemma \ref{L:maj}.
Let $f(y) = \sum_{n \geq 0}  c(n) y^n$ and $g(y) = \sum_{n \geq 0} d(n) y^n$ be polynomials in $y$ with real coefficients. We say that $f$ is dominated by $g$ in the {\it coefficient partial order}, denoted $f \sqsubseteq g$, if and only if $c(n) \leq d(n)$ for all $n \geq 0$.  If $f \sqsubseteq g$, and $c(n) < d(n)$ for some $n \geq 0$, then we denote this by $f \sqsubset g$.  We write $0 \sqsubseteq f$ if and only if $f$ has all coefficients non-negative and $0 \sqsubset f$ if and only $f$ has all coefficients non-negative and at least one coefficient positive.

\begin{proposition}
\label{P:ab}
If $a > b \geq 0$ are integers, then
\begin{equation*}
\mu_{\ell,a}(y)\mu_{\ell,b}(x) \sqsubseteq \mu_{\ell,a-1}(x)\mu_{\ell,b+1}(x).
\end{equation*}  We have $\mu_{\ell,a}(x)\mu_{\ell,b}(x) \sqsubset \mu_{\ell,a-1}(x)\mu_{\ell,b+1}(x)$ if and only if, additionally, $a \geq b+2$, $a-1 \geq \ell$, and $\ell \geq 1$.

\end{proposition}

The proof of Proposition \ref{P:ab} requires the two following lemmas.
\begin{lemma}
\label{binomial}
If $A,B,M,N$ are integers with $A \geq B \geq 0$ and $M \geq N \geq 0$ , then
\begin{equation*}
\binom{A}{M}\binom{B}{N} \geq \binom{A}{N}\binom{B}{M}.
\end{equation*}
For these same ranges of parameters, the inequality is strict if and only if $A > B$, $M > N$, $A \geq M$, and $B \geq N$.
\end{lemma}
\begin{proof}
If $A=B$ or $M=N$ then both sides of the inequality are identically equal.  If $M > A$, then $M > B$ and both sides are $0$.  If $N > B$, then $M>B$ and, again, both sides are $0$.  We may now assume $A > B, M >N, A \geq M,$ and $B \geq N$.  Canceling factorials, the desired inequality becomes
\begin{equation*}
(A-N)_{M-N} > (B-N)_{M-N},
\end{equation*}
where, for non-negative integers $n$ and real numbers $\alpha$, $(\alpha)_n := \prod_{i=0}^{n-1} (x-i)$ is the falling factorial.  Since $(\alpha)_n > (\beta)_n$ if $\alpha > \beta \geq n-1\geq 0$, we are done.
\end{proof}
\begin{lemma}
\label{product}
Suppose that $f_1,f_2,g_1,g_2$ are polynomials.  If $0 \sqsubseteq f_1 \sqsubseteq f_2$ and $0 \sqsubseteq g_1 \sqsubseteq g_2$, then $f_1 g_1 \sqsubseteq f_2 g_2$.  If, additionally, $f_1 \sqsubset f_2$ and $0 \sqsubset g_2$, then $f_1 g_1 \sqsubset f_2 g_2$.
\end{lemma}
\begin{proof}
Denoting the coefficients by $f_i = \sum_{j\geq 0} f_{i,j}y^j$ and $g_i = \sum_{j \geq0} g_{i,j} y^j$ for $i = 1,2$, the conditions of the lemma state that $0 \leq f_{1,j} \leq f_{2,j}$ and $0 \leq g_{1,j} \leq g_{2,j}$ for all $j \geq 0$.  Writing their products as $f_1g_1 = \sum_{l \geq 0} a_l y^l$ and $f_2g_2 = \sum_{l \geq 0} b_l y^l$, the coefficients then satisfy
\begin{equation*}
a_l = \sum_{j,k \geq 0, j+k = l} f_{1,j}g_{1,k} \leq \sum_{j,k \geq 0, j+k = l} f_{2,j}g_{2,k} = b_l,
\end{equation*}
since  $f_{1,j}g_{1,k} \leq f_{2,j}g_{2,k}$ for all $j,k \geq 0$.

If there is additionally some pair $j,k$ such that $0 \leq f_{1,j} < f_{2,j}$ and $0 < g_{2,k}$, then $f_{1,j}g_{1,k} < f_{2,j}g_{2,k}$, and therefore the stronger conclusion $a_{j+k} < b_{j+k}$ holds.
\end{proof}


\begin{proof}[Proof of Proposition \ref{P:ab}] By definition, proving that $\mu_{\ell,a}(y)\mu_{\ell,b}(y) \sqsubseteq \mu_{\ell,a-1}(y)\mu_{\ell,b+1}(y)$ is the same as proving that for each $0 \leq m \leq 2\ell$ we have
\begin{equation}
\label{E:ab1}
\sum_{d = M'}^M \binom{a}{d} \binom{b}{m-d}
\leq
\sum_{d = M'}^M \binom{a-1}{d} \binom{b+1}{m-d},
\end{equation}
where $M' := \max\{0, m-\ell\}$ and $M := \min\{\ell, m\}$. Likewise, the stronger condition that $\mu_{\ell,a}(y)\mu_{\ell,b}(y) \sqsubset \mu_{\ell,a-1}(y)\mu_{\ell,b+1}(y)$ is equivalent to additionally proving that there is an $m$ with $0 \leq m \leq 2 \ell$ for which \eqref{E:ab1} is strict.  Applying Pascal's identity $\binom{a}{d} = \binom{a-1}{d} + \binom{a-1}{d-1}$ to the left-side and $\binom{b+1}{m-d} = \binom{b}{m-d} + \binom{b}{m-d-1}$ to the right, and then cancelling like terms, \eqref{E:ab1} becomes
\begin{equation}
\label{E:ab2}
\sum_{d = M'}^M \binom{a-1}{d-1} \binom{b}{m-d}
\leq
\sum_{d = M'}^M \binom{a-1}{d} \binom{b}{m-d-1}.
\end{equation}
Furthermore, after a summation index shift all of the terms but one in \eqref{E:ab2} cancel, leaving only $d = M'$ on the left-side and $d = M$ on the right:
\begin{equation*}
\binom{a-1}{M'-1} \binom{b}{m-M'} {\leq} \binom{a-1}{M} \binom{b}{m-M-1}.
\end{equation*}

If $M' = 0$, then this inequality is trivially satisfied, and thus so is \eqref{E:ab1}.  We therefore need only consider the case that $M' = m-\ell$.  This means that $m \geq \ell$, so in this case $M = \ell$, and \eqref{E:ab1} is finally equivalent to the inequality
\begin{equation*}
\binom{a-1}{m-\ell -1} \binom{b}{\ell}
\leq
\binom{a-1}{\ell} \binom{b}{m - \ell - 1}.
\end{equation*}
We now apply Lemma \ref{binomial} with $A = a-1$, $B= b$, $M = \ell$, $N = m - \ell - 1$ to complete the proof.  The inequality easily follows.  It is also easy to see that \eqref{E:ab1} is strict in the cases where $a \geq b+2$, $a-1 \geq \ell$, and $2 \ell \geq m \geq \ell+1$ (and hence $\ell \geq 1$).

\end{proof}
\begin{remark}
Proposition \ref{P:ab} (and its proof) can also be interpreted combinatorially.  In particular, consider two rows consisting of $a$ and $b$ square cells, respectively.  The $y^m$ coefficient in
\begin{equation*}
\sum_{i = 0}^\ell \binom{a}{i} y^i \cdot \sum_{j = 0}^\ell \binom{b}{j} y^j
\end{equation*}
is the number of ways of marking exactly $m$ of the cells subject to the restriction that there are at most $\ell$ marked cells in each row, and the result then states that if $a > b$, then there are at least as many ways to mark two rows of length $a-1$ and $b+1$ subject to the same restriction.
\end{remark}

\begin{corollary}
\label{C:truncate}
If $y \geq 0$, $\blam[1], \blam[2] \in \Delta(m)$ each have integer coordinates, and $\blam[1] \succeq \blam[2]$ then
\begin{equation*}
\prod_{i = 1}^m \mu_{\ell, \lambda_1(i)}(y) \sqsubseteq \prod_{i = 1}^m \mu_{\ell, \lambda_2(i)}(y).
\end{equation*} .
\end{corollary}
\begin{proof}
Suppose $\blam[1] \neq \blam[2]$.  By definition, there must then be two indices $1 \leq \alpha < \beta \leq m$ such that $\lambda_1(\alpha) > \lambda_2(\alpha)$ and $\lambda_1(\beta) < \lambda_2(\beta).$
Define $\blamprime[1]$ by setting
\begin{equation*}
\lambda'_1(\alpha) := \lambda_1(\alpha) - 1, \qquad \lambda'_1(\beta) := \lambda_1(\beta) + 1,
\end{equation*}
and $\lambda'_1(i) := \lambda_1(i)$ for all $i \neq \alpha, \beta.$  Importantly, it is still true that $\blamprime[1]$ majorizes $\blam[2].$

Noting that $\lambda_1(\alpha) > \lambda_2(\alpha) \geq \lambda_2(\beta) > \lambda_1(\beta)$, Proposition \ref{P:ab} now states that
\begin{equation*}
\mu_{\ell, \lambda_1(\alpha)}(y) \mu_{\ell, \lambda_1(\beta)}(y)
\sqsubseteq \mu_{\ell, \lambda'_1(\alpha)}(y) \mu_{\ell, \lambda'_1(\beta)}(y)
\end{equation*}
which, combined with Lemma \ref{product}, implies that
\begin{equation}
\label{E:Lam1Lam'1}
\prod_{i = 1}^m \mu_{\ell, \lambda_1(i)}(x) \sqsubseteq
\prod_{i = 1}^m \mu_{\ell, \lambda'_1(i)}(x).
\end{equation}
If $\blamprime[1] = \blam[2],$ then \eqref{E:Lam1Lam'1} gives the statement of the corollary.  Otherwise, the above procedure is repeated (a finite number of steps) until this is the case.
\end{proof}

Applying this result with the partitions $\blam[1] = n^k$ and $\blam[2] = k^n$ will finally complete the proof of Lemma \ref{L:maj}.
\begin{proof}[Proof of Lemma \ref{L:maj}]
\label{C:mu}
Corollary \ref{C:truncate} implies $\mu_{\ell, n}(y)^k \sqsubseteq \mu_{\ell, k}(y)^n$.  Since this partial order requires that all coefficients be dominated, this immediately implies that $\mu_{\ell, n}(y)^k \leq \mu_{\ell, k}(y)^n$ for all $y \geq 0$. Clearly, if $k =n$, $\ell=0$, $\ell = n$, or $x = 0$, then $\mu_{\ell, n}(x)^k = \mu_{\ell, k}(x)^n$.  It therefore remains to be shown that the inequality is strict if $1 \leq \ell \leq n-1$, $k \leq n-1$ and $x >0$.

Proposition \ref{P:ab} implies that $\mu_{\ell,n} \mu_{\ell,0} \sqsubset \mu_{\ell,n-1} \mu_{\ell,1}$.  Following the proof method of Proposition \ref{P:ab}, we introduce the dummy term $\mu_{\ell, 0} = 1$ and find
\begin{equation*}
\mu_{\ell,n}^k = \mu_{\ell,n}^{k-1}(\mu_{\ell,n} \mu_{\ell,0}) \sqsubset \mu_{\ell,n}^{k-1} (\mu_{\ell,n-1} \mu_{\ell,1}) \sqsubseteq \mu_{\ell,k}^n.
\end{equation*}
The second relation follows from  Lemma \ref{product}, and the third follows from Corollary \ref{C:truncate}.  Since $\mu_{\ell,n}^k \sqsubset \mu_{\ell,k}^n$ and $x >0$, we conclude that $\mu_{\ell, n}(x)^k < \mu_{\ell, k}(x)^n$
\end{proof}



\section{Inequalities for sums of Bernoulli random variables}
\label{S:Colrow}

In this brief section we describe the relationship between our quasi-mean inequalities in Theorem \ref{T:main} and the distributions of sums of Bernoulli random variables.

\begin{proof}[Proof of Theorem \ref{T:CR}]  The inequality is trivial if $\ell = n$, so we henceforth assume that $\ell < n$.  Furthermore, if $p_i = 1$ for some $i$ with $1 \leq i \leq n$, then $\Prob(C_i \leq \ell)=0$ and the inequality is again trivially true.  We therefore also assume that $p_i \in [0,1)$ for each $i$.

All of the events $\{C_j \leq \ell\}$ are independent, and their individual probabilities are given by
\begin{equation*}
\Prob(C_j \leq \ell) = \sum_{0 \leq m \leq \ell} \binom{n}{m} p_j^m (1-p_j)^{n-m}.
\end{equation*}
Thus
\begin{equation}
\label{E:ProbC}
\Prob\Big(\max_{1 \leq j \leq n}\{C_j\} \leq \ell\Big)
= \prod_{j=1}^n \sum_{0 \leq m \leq \ell} \binom{n}{m} p_j^m (1- p_j)^{n-m}.
\end{equation}
Similarly, the events $\{R_i \leq \ell\}$ are also independent, and their probabilities are given by
\begin{equation*}
\Prob(R_i \leq \ell) = \sum_{0 \leq m \leq \ell}
\sum_{\substack{I \subseteq [n] \\ |I| = m}} \prod_{j \in I} p_j
\prod_{j \not \in I} (1-p_j),
\end{equation*}
so
\begin{equation}
\label{E:ProbR}
\Prob\Big(\max_{1 \leq i \leq n}\{R_i\} \leq \ell \Big)
= \left(\sum_{0 \leq m \leq \ell}
\sum_{\substack{I \subseteq [n] \\ |I| = m}} \prod_{j \in I} p_j
\prod_{j \not \in I} (1-p_j)\right)^n.
\end{equation}
Dividing \eqref{E:ProbC} and \eqref{E:ProbR} by $\prod_{j=1}^n (1-p_j)$, we see that the desired inequality is equivalent to the left inequality from
Theorem \ref{T:main} with $x_i = p_i/(1-p_i)$ for $1 \leq i \leq n$.
\end{proof}


\begin{thebibliography}{88}

\bibitem{B95} D. Bertsekas, {\it Nonlinear Programming}, Athena Scientific, Belmont, MA, 1995.

\bibitem{HLP52} G. Hardy, J.  Littlewood, and G. P\'olya, {\it Inequalities, 2nd. ed.}, Cambridge University Press, Cambridge,
1952.

\bibitem{Muir03}  R. Muirhead, {\it Some methods applicable to identities of symmetric algebraic functions of $n$
letters}, Proc. Edinburgh Math. Soc. \textbf{21} (1902/03), 144--157.

\bibitem{Sta99} R. Stanley, {\it Enumerative Combinatorics, vol. 2}, Cambridge University Press, Cambridge,
1999.

\end{thebibliography}




\end{document}