\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}