\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Which Young Tableaux Can Represent an \\
\vskip .1in
Outer Sum?
}
\vskip 1cm
\large
Colin Mallows \\
Flemington, NJ \\
USA \\
\href{mailto:colinm16@comcast.net}{colinm16@comcast.net}\\
\ \\
Robert J. Vanderbei\footnote{
Research supported by ONR Grant N0014-13-1-0093.}\\
Department of Operations Research and Financial Engineering \\
Princeton University \\
Princeton, NJ 08544 \\
USA \\
\href{mailto:rvdb@princeton.edu}{\tt rvdb@princeton.edu}
\end{center}
\vskip .2 in
\begin{abstract}
Given two vectors, not necessarily of the same length, each having increasing
elements, we form the matrix whose $(i,j)$-th element is the sum of the $i$-th
element from the first vector and the $j$-th element from the second vector.
Such a matrix is called an outer sum of the two vectors (a concept that is analogous to
outer products).
If we assume that all the entries of this matrix are distinct, then we can form another matrix
of the same size but for which the $(i,j)$-th element is not the matrix element
itself but rather
the rank of this element in a sorted list of all the numbers in the first matrix.
Such a matrix is called a Young tableau. We say that it ``represents'' the
outer sum. In this paper, we address the question as to whether all Young
tableaux can be generated this way. When one of the two dimensions is two, then
the answer is yes. In all higher dimensional cases, the answer is no. We
prove the positive result and give examples illustrating the negative result.
\end{abstract}
\section{Introduction}
Let $x$ and $y$ be real vectors of lengths $m$ and $n$, respectively, each with
increasing elements.
Define $s = \{s_{ij} \}$ where $s_{ij} = x_i + y_j$
($s$ is the ``outer sum'' of $x$ and $y$; we write $s = x \circ y$).
Suppose $x$ and $y$ are in general position, so that the $m \times n$ numbers
$\{s_{ij}\}$ are all different.
Let $t_{ij}$ be the rank of $s_{ij}$ in this set of numbers.
Then the array $t = \{ t_{ij} \}$ is an $m \times n$ {\em Young tableau},
with entries $(1,2,\ldots,mn)$,
satisfying $t_{ij} < t_{ik}$ whenever $j < k$ and $t_{ij} < t_{kj}$ whenever
$i < k$.
We say that this tableau {\em represents} the outer sum.
This raises an interesting question:
Can all Young tableaux be generated in this way?
In this paper, we prove that all $2 \times n$ tableaux can represent an outer sum,
and show that some larger tableaux cannot.
We will describe our efforts to characterize these tableaux.
We begin with some brief motivation for our interest in this problem.
During consideration of a new deconvolution algorithm for estimating the distribution of a
random variable $Y$ based on $m$ observations of a random variable $X$ and $n$
observations of the independent sum $X+Y$ (see \cite{mallows15} for details), one of us
encountered the question posed in the title. He did some hand
calculations (many of which were later found to be in error), and submitted the
results to the OEIS (\cite{oeis}, sequence \seqnum{A211400}). The second author saw that
linear programming (LP) could provide definitive answers in many small cases of
the problem, and obtained results for the cases
\[
(m,n) = (2,3), (2,4), \ldots (2,9), (3,3),\ldots, (3,7), (4,4).
\]
In this paper, we prove that for all $n \ge 1$,
every $2 \times n$ Young tableau can represent an outer sum, and show that for
$m ,n \ge 3$, this is not the case.
\begin{remark}
This problem is exactly equivalent to one expressed in terms of
the outer product of two positive ordered vectors, using products instead of
sums, simply by taking logs. We could also think in terms of ``outer
difference'' and ``outer division''; these are all equivalent problems.
\end{remark}
\begin{remark}
It is completely trivial that the (unique) $1 \times n$ tableau does represent
(and in fact equals) the outer sum $x \circ y$ where $x = (0)$ and $y =
(1,2,\ldots,n)$.
\end{remark}
\begin{remark}
For any vector $x = (x_1, \ldots , x_m)$ and real $k$
we define $x+k$ to be the vector $(x_1 + k, \ldots , x_m +k)$. Then for any
$k$ and $l$, $x \circ y$ and $(x+k) \circ (y+l)$ have the same tableau representation.
\end{remark}
\begin{example}
The $3 \times 3$ tableau
\[
\left[
\begin{array}{ccc}
1 & 2 & 6 \\ 3 & 5 & 7 \\ 4 & 8 & 9
\end{array}
\right]
\]
cannot represent an outer sum. Let $x$ be $(a,b,c)$, and, ignoring the obvious
vector/scalar notational conflict, let $y$ be $(x,y,z)$.
Then from $2<3$ we have
\[
a + y < b + x,
\]
and from $7 < 8$ we have
\[
b + z < c + y.
\]
Adding these inequalities gives
\[
a+y+b+z < b+x+c+y;
\]
i.e., $a + z < c + x$, which contradicts the entries $6, 4$ in the tableau.
This gives us our first taboo configuration:
\begin{center}
\vspace*{0.2in}
$T_3$: \quad $t_{12} < t_{21} \; $ and $\; t_{23} < t_{32} \;$ and $\; t_{31} < t_{13}.$
\vspace*{0.2in}
\end{center}
\end{example}
There are $42$ Young tableaux of size $3 \times 3$; just $3$ of these satisfy this taboo
condition, and another $3$ the same with all inequalities reversed, leaving
$36$ that can represent an outer sum. This result and several higher-order cases
are presented in OEIS \cite{oeis}, sequence \seqnum{A211400}.
\begin{remark}
Among the $m \times n$ tableaux with $m,n \ge 3$ are some whose
leading $3 \times 3$ sub-tableaux are copies of the $3 \times 3$ tableau above. These cannot
represent an outer sum.
\end{remark}
\begin{remark}
Suppose $A$ is an $m \times n$ tableau.
In the following, we will consider
various sub-tableaux of $A$. For most purposes, we need not distinguish between
an $a \times b$ sub-matrix $B$ of $A$, which is the usual concept,
simply dropping $m-a$ rows
and $n-b$ columns of $A$, and the corresponding sub-tableau $C$, which is
obtained from $B$ by replacing its elements by their ranks (within the set of elements of
$B$). Thus $C$ will be a proper $a \times b$ Young tableau. For example,
the $(2,3) \times (1,3)$ sub-matrix of the $3 \times 3$ tableau above is the $2
\times 2$ matrix
with rows $(3,7)$ and $(4,9)$, while the corresponding $2 \times 2$ sub-tableau has
rows $(1,3)$ and $(2,4)$. We need not distinguish between these, because all
relevant information is carried by the ordering of their elements,
without regard to their numerical values. We will never need to perform
any arithmetic operations on these elements, apart from considering their
ordering.
\end{remark}
\section{The $2 \times n$ case}
\begin{theorem} For all $n \ge 1$, each of the $2 \times n$ Young tableaux can represent an outer sum.
\end{theorem}
\begin{proof} The number of distinct $2 \times n$ Young tableaux is the Catalan number
\[
C_n = \frac{1}{n+1} \left( \begin{array}{c} 2n \\ n \end{array} \right).
\]
Very many enumerative problems have these numbers as
their solution (see \seqnum{A000108} in the OEIS) and we discuss just one of these,
namely the number of paths of $2n$ steps in the positive quadrant,
starting from the origin $(0,0)$ and ending at $(n,n)$, where each step is either
eastwards one unit, or northwards one unit, and where the whole path
stays below (or on) the line $y=x$. We call these ``lower paths''
(usually referred to as ``Dyck paths'' in the literature).
The top row of the Young tableau tells when the eastwards steps occur, and the
bottom row tells when the northwards steps occur. We will show that
each such path corresponds to an outer sum. The generating function of
the Catalan sequence is $C(x) = (1-\sqrt{1-4x})/2x = 1 + x + 2x^2 + 5x^3 +
14x^4 + 42x^5 + \cdots$.
For $n = 1$, the tableau represents $(0,1) \circ (0)$. For $n \ge 2$
we can describe a general lower path $p$ (of length $2n$) as the concatenation
$(p_1, p_2)$ of two
lower paths, of lengths $2a$ and $2b$, respectively, where $a \ge 1$ and $b
\ge 0$,
and where the path $p_1$ stays strictly below the line $y=x$ except at its
endpoints. We call $p_1$ a {\em sub-lower} path. The number of such
paths of length $2a$ is the coefficient of $x^a$ in $xC(x)$, since except for
the first and last steps, the path stays below or on the line $y=x-1$. The
total number of lower paths of length $2n$ is thus the coefficient of $x^n$ in
$1 + xC(x) \cdot C(x)$ which is just $C(x)$. (This argument is one way of deriving
$C(x)$.) The corresponding tableaux have the property
that the first time both partial rows have equal length (apart from the
initial state, where both have length zero) is when both
rows have length $a$. This can occur with $a=1$, in which case the first
column of the tableau is $(1,2)$. If $a \ge 2$ the top row of the tableau
starts $(1,2,\ldots)$, the bottom row has $(2a-1,2a)$ in the $(a-1)$-th and $a$-th
positions, and the first $a$ columns of $T$ contain a permutation of the
integers $(1,2,\ldots, 2a)$.
We proceed by induction. Suppose we have shown that for $n \le n_0$,
all $2 \times n$
Young tableaux, or the associated lower paths, can represent an outer sum. We
take $x = (0,1)$.
Consider a $2 \times n$ tableau $T$ with $n = n_0 + 1$, and its component
paths $p_1$ and $p_2$ as above.
Except when $b=0$, each of $a$ and $b$ is positive and
less than or equal to $n_0$, so by the inductive hypothesis each
component path can represent an outer sum,
$x \circ y$ with $y = (y_1,\ldots,y_a)$
and
$x \circ z$ with $z = (z_1, \ldots, z_b)$ say.
If $a < n$, we have
$t_{1,(a+1)} = 2a+1$, so we may take $k = 2+y_a$, and $T$ represents the outer sum
$x \circ (y,z+k)$.
The only case needing proof is when $a = n,
b=0$. In this case the tableau $T$ must be of the form
\[
\left[
\begin{array}{ccccc}
1 & 2 & \cdots & \cdots & f \\ g & \cdots & \cdots & 2n-1 & 2n
\end{array}
\right]
\]
with $n \le f \le 2n-2$ and $3 \le g \le n+1$. Consider the $2 \times
(n-1)$ matrix
\[
M =
\left[
\begin{array}{ccc}
2 & \cdots & f \\ g & \cdots & 2n-1
\end{array}
\right] .
\]
Since $T$ corresponds to a sub-lower path, the elements of this matrix have
the same order relations as a Young tableau $T^*$ of dimension $2 \times (n-1)$.
The $(i,j)$ entry $t^*_{ij}$ of $T^*$ is
just $M_{ij} - 1$.
$T^*$ corresponds to a
lower path of length $2(n-1)$ and so to an outer sum $x \circ y^*$ with
$y^* = (y_2, y_3,\ldots y_n)$ say.
We have only to show that we can choose
$y_1$ to make the tableau $T$ represent the outer sum $x \circ (y_1, y^*)$.
For this, we need $y_1 < y_2$, $\mbox{rank}(1+y_1) = g$. Since in
the outer sum $x \circ y^*$, $\mbox{rank}(1+y_2) = g-1$,
we must have that $y_{g-2} < 1+y_2$. So we can fit $1+y_1$ between $y_{g-2}$
and $1+y_2$, so that $y_1 < y_2$, and we are done.
\end{proof}
\section{Linear programming}
To use linear programming (LP) to study the $m \times n$ tableaux, we solve the
following problem:
\[
\begin{array}{lrcll}
\mbox{maximize } & \varepsilon \qquad \qquad \qquad \\[0.1in]
\mbox{subject to } & y_{i(k)} + x_{j(k)} + \varepsilon
& \le & y_{i(k+1)} + x_{j(k+1)},
& \qquad k = 1,\ldots,mn-1, \\[0.05in]
& y_k + \varepsilon & \le & y_{k+1} ,
& \qquad k = 1,\ldots,m-1, \\[0.05in]
& x_k + \varepsilon & \le & x_{k+1} ,
& \qquad k = 1,\ldots,n-1, \\[0.05in]
& 0 \;\; \le \;\; y_k & \le & 1, & \qquad k = 1,\ldots,m, \\[0.05in]
& 0 \;\; \le \;\; x_k & \le & 1, & \qquad k = 1,\ldots,n. \\[0.05in]
\end{array}
\]
Here, $i(k)$ and $j(k)$ denote the row and column of the $k$-th ranking entry in
the tableau.
If the optimal value of $\varepsilon$ is positive, then an outer sum
representation exists for that tableau. Otherwise not.
\subsection{The $3 \times 4$ case} One of us has used LP to study the $462$
Young tableaux of size $3 \times 4$,
finding $295$ that can represent an outer sum, leaving $167$ that
cannot. Study of these $167$ showed that $159$ of them satisfied the above
$3 \times 3$
taboo condition (or its reverse, reversing all inequalities), applied to each
of four sub-matrices, each omitting one column of the $3 \times 4$ tableau,
leaving $8$ tableaux that do not. Examination of these suggested four new taboo
configurations, namely
\begin{center}
\vspace*{0.2in}
$T_{41}$: \quad
$t_{12} < t_{21} \;$ and $\; t_{24} < t_{33} \;$ and $\; t_{23} < t_{14}
\;$ and $\; t_{31} < t_{22}$ \\
\vspace*{0.2in}
$T_{42}$: \quad
$t_{13} < t_{21} \;$ and $\; t_{24} < t_{32} \;$ and $\; t_{22} < t_{14}
\;$ and $\; t_{31} < t_{23}$ \\
\vspace*{0.2in}
and the same with all inequalities reversed.
\vspace*{0.2in}
\end{center}
For a $4 \times 3$ tableau there are
similar transposed taboo conditions. See Figure \ref{fig1} for pictures of these
taboo configurations. The values of $n$ in the figure give the number of $3
\times 4$
tableaux that satisfy each taboo configuration, or its reversal.
\subsection{The $4 \times 4$ case}
Examination of the $4 \times 4$ tableaux gave the following results.
\begin{center}
\begin{tabular}{llr}
& Total number of tableaux & 24024 \\
& Representing outer sums & 6660 \\
& Not representing & 17364 \\
& Taboo $T_{3}$ & 16432 \\
& Taboo $T_{41}$ or $T_{42}$, but not $T_3$ & 932 \\
\qquad
\end{tabular}
\end{center}
We do not need any new taboo configurations.
\subsection{The $3 \times 5$ case}
Examination of the $3 \times 5$ tableaux gave the following results.
\begin{center}
\begin{tabular}{llr}
& Total number of tableaux & 6006 \\
& Representing outer sums & 2583 \\
& Not representing & 3423 \\
& Taboo $T_3$ & 3233 \\
& Not representing, but not $T_3$ & 190 \\
& $T_{41}$, not $T_3$ or $T_{42}$ & 93 \\
& $T_{42}$, not $T_3$ or $T_{41}$ & 93 \\
& Both $T_{41}$ and $T_{42}$, not $T_3$ & 4 \\
\qquad
\end{tabular}
\end{center}
Again, no new taboo configurations are needed for this $3 \times 5$ case. At this
point we hoped that we had found a complete set of taboo configurations. But
when we studied the $3 \times 6$ cases, we found new taboos.
\subsection{The $3 \times 6$ case}
Examination of the $3 \times 6$ tableaux gave the following results.
\begin{center}
\begin{tabular}{llr}
& Total number of tableaux & 87516 \\
& Representing an outer sum & 23580 \\
& Not representing & 63936 \\
& Taboo $T_3$ & 60784 \\
& Not Taboo $T_3$ & 3152 \\
& Taboo $T_{41}$ and/or $T_{42}$, not $T_3$ & 3112 \\
& Not $T_3$ or $T_{41}$ or $T_{42}$ & 40 \\
\qquad
\end{tabular}
\end{center}
These last $40$ tableaux were found to require $8$ new taboo configurations, with their
reversals, as shown in Figure \ref{fig1}. The frequencies add to $48$, not $40$, since
four tableaux satisfy both $T_{61}$ and $T_{63}$ (or their reversals), while four more
satisfy both $T_{62}$ and $T_{64}$.
This result dashed our hopes. It seems clear that more taboo configurations
will be needed for the $3 \times 8$ case (perhaps not for the $3 \times 7$ case), and we can
guess at some of these, by analogy with $T_{61}$ and $T_{67}$. But even if we could
identify a complete description of all the taboo conditions, we would still have
a difficult enumerative problem: to count the Young tableaux that avoid all of
these.
\section{Final comment}
The problem remains ``hard'', as the entry \seqnum{A211400} in the
OEIS says. We hope that someone with more insight than us will make further
progress on this problem. Complete lists of the ``solved'' configurations in
the $3 \times 5$ and $3 \times 6$ cases are available online
\cite{van_tableaux35,van_tableaux36}.
\begin{figure}
\begin{center}
\includegraphics[width=3.25in]{Taboos.eps}
\end{center}
\caption{Eleven taboo configurations. In each panel of the Figure,
an arrow from node $a$ to node $b$ denotes the inequality $t_a < t_b$.
Any tableau with a sub-tableau satisfying all such inequalities cannot
represent an outer sum. In each panel, $n$ is the number of
tableaux (of minimal size) that satisfy the inequalities shown
(or the same with all inequalities reversed).}
\label{fig1}
\end{figure}
\begin{thebibliography}{1}
\bibitem{mallows15}
C.~L. Mallows, Decomposition by simulation.
\newblock In {\em Complex Datasets and Inverse Problems: Tomography, Networks
and Beyond}, Vol.~54,
IMS Lecture Notes -- Monograph Series,
2007, pp.~1--11.
\bibitem{oeis}
The {O}n-{L}ine {E}ncyclopedia of {I}nteger {S}equences, 2015.
\newblock Published electronically at \\ \url{http://oeis.org}.
\bibitem{van_tableaux35}
R.~J. Vanderbei, Young tableaux, 2015. Available at \\
\newblock \url{http://www.princeton.edu/~rvdb/YoungTableaux/solved\_3x5.txt}.
\bibitem{van_tableaux36}
R.~J. Vanderbei, Young tableaux, 2015. Available at \\
\newblock \url{http://www.princeton.edu/~rvdb/YoungTableaux/solved\_3x6.txt}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05E05; Secondary 05E10, 20C30, 17B10.
\noindent \emph{Keywords: }
outer sum, Young tableau, Dyck path, Catalan number, linear programming.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000108} and
\seqnum{A211400}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received April 1 2015;
revised versions received July 23 2015; July 30 2015.
Published in {\it Journal of Integer Sequences}, July 30 2015.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}