%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{59}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}


\usepackage{subcaption}
\usepackage{tikz}
%\usepackage{euler}
\usepackage{url}
\usepackage{colonequals}
\usepackage{mathrsfs}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{lemma}[theorem]{Lemma}

\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{slogan}[theorem]{Slogan}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{setup}[theorem]{Setup}
\newtheorem{question}[theorem]{Question}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{situation}[theorem]{Situation}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{warning}[theorem]{Warning}
\numberwithin{equation}{section}

\def\Q{{\mathbb Q}}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\R{{\mathbb R}}
\def\fS{{\mathfrak S}}
\def\S{{\mathbb S}}
\def\A{{\mathcal A}}
\def\D{{\mathcal D}}
\def\V{{\mathcal V}}
\def\nN{{\mathcal N}}
\def\hA{\overline{\mathcal A}}
\def\ha{\overline{a}}
\def\hU{\overline{U}}
\def\hu{\overline{\textbf{u}}}
\def\B{{\mathcal B}}
\def\F{{\mathcal F}}
\def\rR{{\mathcal R}}
\def\G{{\mathcal G}}
\def\O{{\mathbf 0}}
\def\bb{\textbf{b}}
\def\bd{\textbf{d}}
\def\bv{\textbf{v}}
\def\bn{\textbf{n}}
\def\bu{\textbf{u}}


\def\conv{\operatorname{Conv}}
\def\gale{\operatorname{Gale}}
\def\cone{\operatorname{Cone}}
\def\aff{\operatorname{aff}}
\def\lin{\operatorname{lin}}

\newcommand{\Mink}{\mathtt{Mink}}
\newcommand{\TMink}{\mathtt{TMink}}
\newcommand{\DMink}{\mathtt{DMink}}

\newcommand{\defterm}[1]{\textbf{#1}}
\newcommand{\1}{\mathbf{1}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\KK}{\mathrm{K}}
\newcommand{\pol}{\mathrm{Pol}}
\newcommand{\flag}{\textcolor{red}{FLAG}}
\newcommand{\relint}{\mathrm{relint}}
\newcommand{\PP}{{\mathcal P}}
\newcommand{\codim}{\mathrm{codim}}
\newcommand{\type}{\mathbb{TP}}

\newcommand{\typecone}{\mathbb{TC}}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\White}[1]{\textcolor{white}{#1}}
\newcommand{\Red}[1]{\textcolor{red}{#1}}
\newcommand{\Blue}[1]{\textcolor{blue}{#1}}
\newcommand{\Green}[1]{\textcolor{ForestGreen}{#1}}
\newcommand{\Yellow}[1]{\textcolor{Yellow}{#1}}


%Colors for colorblind equity
\definecolor{orange}{rgb}{0.898, 0.621, 0.0}
\definecolor{skyblue}{rgb}{0.336, 0.703, 0.910}
\definecolor{bluishgreen}{rgb}{0, 0.617, 0.449}
\definecolor{yellow}{rgb}{0.937, 0.890, 0.258}
\definecolor{blue}{rgb}{0, 0.445, 0.695}
\definecolor{red}{rgb}{0.832, 0.367, 0}
\definecolor{purple}{rgb}{0.797, 0.473, 0.652}

\definecolor{bennetpurple}{rgb}{.5, 0, .635} %% A more perfect purple
\newcommand{\BBG}[1]{{\color{bennetpurple}\sf [#1]}} %% Bennet's comments
\newcommand{\JSD}[1]{{\color{orange}\sf [#1]}} %% Joseph's comments
\newcommand{\fcc}[1]{{\color{bluishgreen}\sf [#1]}} %% Federico's comments
\newcommand{\ly}[1]{{\color{blue}\sf [#1]}} %% Li's comments

%% For footnotes
\makeatletter
\newcommand{\barefootnote}[1]{{%
  \let\@makefnmark\relax \let\@thefnmark\relax
  \makeatletter
  \@footnotetext{#1}}}
\makeatother 



%% define your title in the usual way
\title{Minkowski summands of Cubes}


	
%%	{\sc Federico Castillo}, Max-Planck-Institut f\"{u}r Mathematik in den Naturwissenschaften, castillo@mis.mpg.de
	
%%	{\sc Joseph Doolittle}, Freie Universit\"{a}t Berlin, jdoolitt@zedat.fu-berlin.de
	
%%	{\sc Bennet Goeckner}, University of Washington, goeckner@uw.edu
	
%%	{\sc Michael S. Ross}, Iowa State University, msross@iastate.edu
	
%%	{\sc Li Ying}, University of Notre Dame, lying@nd.edu

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%\author[Optional shorter names]{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}
\author{Federico Castillo\thanks{\href{mailto:castillo@mis.mpg.de}{castillo@mis.mpg.de}}\addressmark{1}, Joseph Doolittle\thanks{\href{mailto:jdoolittle@tugraz.at}{jdoolittle@tugraz.at}}\addressmark{2}, Bennet Goeckner\thanks{\href{mailto:goeckner@uw.edu}{goeckner@uw.edu}}\addressmark{3}, Michael S. Ross\thanks{\href{mailto:msross@iastate.edu}{msross@iastate.edu}}\addressmark{4}, \and Li Ying\thanks{\href{mailto:lying@nd.edu}{lying@nd.edu}}\addressmark{5}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Max-Planck-Institut f\"{u}r Mathematik in den Naturwissenschaften \\ \addressmark{2}Technische Universit\"{a}t Graz\\ \addressmark{3}University of Washington\\ \addressmark{4}Iowa State University\\ \addressmark{5}University of Notre Dame}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{59Castillo.bib}


%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{In pioneering works of Meyer and of McMullen in the early 1970s, the set of Minkowski summands of a polytope was shown to be a polyhedral cone called the type cone. Explicit computations of type cones are in general intractable. Nevertheless, we show that the type cone of the product of simplices is simplicial. This remarkably simple result derives from insights about rainbow point configurations and the work of McMullen.}

%% put your French abstract here, or comment this out if you don't have one


%% put your keywords here, or comment this out if you don't have them yet
\keywords{Cubes, Gale Dual, Type Cone}


\hyphenation{mar-gin-al-ia}


\begin{document}

\maketitle

	
	\section{Introduction}
	
	\barefootnote{2010 Mathematics Subject Classification: 52B05, 52B35} 
	
	A fundamental operation on polytopes is Minkowski addition. In this paper, we consider the reverse of this operation. Our motivating question is ``Given a polytope $P$, what can we say about the set of its Minkowski summands?''
	
\begin{sloppypar}	It is convenient to modify this question and consider the set $\TMink(P)$ of weak Minkowski summands, polytopes that are summands of some positive dilate of $P$, up to translation equivalence. With this perspective, there are multiple equivalent definitions that provide tools to answer the motivating question.
	We briefly describe three existing techniques to parametrize the set $\TMink(P)$ as pointed polyhedral cone, which we refer to as the type cone of $P$.
\end{sloppypar}
	
	The starting point is a theorem of Shephard \cite[Section 15]{grunb} characterizing the weak Minkowski summands in terms of their support functions. In \cite{meyer}, Meyer used this connection to give a parametrization of $\TMink(P)$ using one parameter for each facet, so we refer to this construction as the facet parametrization. In the context of algebraic geometry, the type cone is the nef cone of the toric variety associated to $P$, when $P$ is a rational polytope. For instance, the definition of the nef cone in \cite[Chapter~6]{toric} implicitly uses the facet parametrization. This technique has been used recently to compute type cones; see, e.g., \cite{coxeter,  nested, chapoton, pilaud_arnau}. Notably, the type cone of the regular permutohedron is the cone of submodular functions \cite{edmonds}.
	
	
	Shephard's aforementioned theorem provides another characterization: $Q$ is a weak Minkowski summand of \(P\) if and only if we can obtain $Q$ by moving the vertices of $P$ while preserving edge directions, also allowing contraction of edges to points. It follows that we can parametrize weak Minkowski summands by the edge lengths. This parametrization is called the \emph{edge deformation space} in \cite{faces} and is equal to the set of nonnegative 1-Minkowski weights. The set of $r$-Minkowski weights, as defined in \cite[Section 5]{simple} and further explored on \cite{weights}, is crucial for the understanding of McMullen's polytope algebra.
	
	Finally, in \cite{mcmullen} McMullen used a different description, using the support function as in \cite{meyer}, but expressing the whole set as an intersection of cones, one for each cofacet. McMullen calls these sets type cones, since the interior of such a cone parametrizes polytopes of a strong combinatorial type\footnote{McMullen \cite[Section 2]{weights} uses ``strongly isomorphic'' to refer to polytopes with the same normal fan.}. Abusing notation, in this paper we use the term type cone to refer to the \emph{closure} of what \cite{mcmullen} calls type cone.
	
	We prove two main results, the first about polygons and the second about cubes. The former is proved using the edge parametrization and the latter using McMullen's methods. 
	
	Polygons are perhaps the easiest nontrivial polytopes to understand. However, their type cones are as general as possible within the dimension and facet count constraints.
	
	\begin{theorem}\label{thm:market2}
		Any $d$-cone with $d+2$ facets is the type cone of a polygon with $d+2$ vertices.
	\end{theorem}
	
	The second result is a description of type cones for cubes\footnote{By cubes, we mean any polytope combinatorially isomorphic to $[0,1]^d$.}. Cubes can have quite nontrivial geometry. For instance, Klee and Minty in \cite{klee-minty} famously constructed cubes for which Dantzing's simplex method takes exponentially many steps. Surprisingly, cubes have elementary type cones. 
	
	\begin{theorem}\label{thm:market}
		The type cone of any combinatorial $d$-cube is a $d$-simplicial cone.
	\end{theorem}
	
	
	 Combined, our two central results give an indication that the complexity of computing the type cone of a polytope cannot be easily determined from the complexity of the polytope itself.
	
	Recently Adiprasito, Kalmanovich, and Nevo proved that the realization space of the cube is contractible in \cite{karim}. Realization spaces parametrize the set of combinatorially isomorphic polytopes, whereas the interiors of type cones parametrize the set of polytopes with identical normal fans.
	
	
	
	When $P$ has a simplicial type cone, \cite[Corollary 1.11]{pilaud_arnau}	shows an explicit isomorphism between the type cone of \(P\) and the positive orthant. This isomorphism appears in the construction of Arkani-Hamed, Bai, He, and Yan \cite[Section 3.2]{scattering} of the \emph{kinematic} associahedron in the context of scattering amplitudes. Motivated by this connection with theoretical physics, Padrol, Palu, Pilaud, and Plamondon \cite{pilaud_arnau} analyzed the type cones of several families of polytopes to determine when they are simplicial. Also, Albertin, Pilaud, and Ritter in \cite{apr} classified which permutrees have simplicial type cones.
	
	
	From the results in \cite{apr} and \cite{pilaud_arnau}, it seems that having a simplicial type cone is a rare property. Moreover, these results depend on particular realizations, whereas our Theorem~\ref{thm:main} shows that \emph{all} realizations of products of simplices have simplicial type cones. Are these the only polytopes with this property?
	
	
    \acknowledgements{
	This work was completed in part at the 2019 Graduate Research Workshop in Combinatorics, which was supported in part by NSF grant \#1923238, NSA grant \#H98230-18-1-0017,  a generous award from the Combinatorics Foundation, and Simons Foundation Collaboration Grants \#426971 (to M. Ferrara) and \#315347 (to J. Martin). We thank Margaret Bayer and Tyrrell McAllister for discussions and encouragements in the early stages of the project.
	
We are particularly grateful to Jeremy Martin, Isabella Novik, Arnau Padrol, Vincent Pilaud, and Raman Sanyal for many insightful discussions and comments on earlier drafts. We thank Jean-Philippe Labb\'e for computational help and Jes\'us De Loera for discussions about oriented matroids.}
	
	\section{Background}\label{sec:background}
	
	Let $\R^d$ be the $d$-dimensional Euclidean space with the usual inner product $\langle \cdot,\cdot \rangle:\R^d\times \R^d\to\R$. An \textbf{$n$-point configuration} is a $d\times n$ matrix $M_\A$. We think of it via its multiset of columns $\A=\{a_1,\dots, a_n\}\subset \R^d$. Abusing notation, we identify a point $a_i$ with its label $i$.
	A \textbf{face} of a point configuration \(\A\) is a subset \(S \subset \A\) such that for some \(c\in \mathbb{R}^d\), we have \(\langle c,x \rangle \leq \langle c, y\rangle\) for every \(x \in \A\) and every \(y \in S\) and \(\langle c,x \rangle = \langle c, y\rangle\) if and only if $x\in S$. 
	We further include the empty set as a face of \(\A\), and note that the empty set and \(\A\) itself are called improper faces.
	The \textbf{dimension} of a face is the dimension of its affine hull.
	The set of all $k$-dimensional faces of $\A$ is denoted $\F_k(\A)$.  A \textbf{vertex} is a face of dimension \(0\), an \textbf{edge} is a face of dimension \(1\), and a \textbf{facet} is a face of codimension \(1\). A \textbf{coface} is a set of points \(S\subset\A\) such that \(\A \setminus S\) is a face, and a \textbf{cofacet} is the coface of a facet. If $\dim(\A)=d$, the vector $f(\A) \colonequals (f_0(\A),\dots,f_d(\A))$, where $f_k(\A) \colonequals |\F_k(\A)|$, is called the \textbf{f-vector} of \(\A\). The set of faces of \(\A\) forms a partially ordered set under inclusion called the \textbf{face lattice} $\F(\A)$.  Two point configurations $\A_1$ and $\A_2$ are said to be \textbf{combinatorially isomorphic} if their face lattices are isomorphic. 
	
	The \textbf{polytope} $P=P_\A$ obtained from a point configuration \(\A\)  is the convex hull $P_\A \colonequals \conv(\A)$.  Given a polytope $P$, we may treat it as a point configuration $\V(P)$ whose points are the vertices of \(P\) in some order. A cone is  \textbf{simplicial} if it has a linearly independent system of generators. Equivalently, a simplicial cone is the cone over a simplex.
	
	The polytope $\Delta_d:=\conv\{e_0,\dots,e_{d}\}\subset \R^{d+1}$, where the $e_i$ are the standard basis vectors, is called the \textbf{standard simplex} of dimension $d$. Its face lattice is the boolean lattice $B_{d+1}$ since every subset of the vertices forms a face. Any polytope combinatorially isomorphic to $\Delta_d$ is called a $d$-simplex, or simply a simplex if we do not specify dimension.
	
	Given a polytope $P\subset\R^d$ with $\dim P< d$, we can restrict to its affine hull, where it is full dimensional. Also, after some translation, any $d$-dimensional polytope $P$ in $\R^d$ contains the origin in the interior. In the present paper there is no harm in assuming that $P$ is full dimensional and contains the origin in the interior, in which case we define the \textbf{polar} polytope $P^\circ:=\{c \in \R^d : \langle c, x \rangle \leq 1 \text{ for all }x \in P\}$. On the level of face lattices, the face lattice of \(P^\circ\) is isomorphic to the face lattice of \(P\) with the order reversed. 
	
	By the Weyl--Minkowski Theorem \cite[Theorem 1.1]{ziegler}, a polytope $P$ can be alternatively described as the solution set to a finite system of linear inequalities, i.e., a \(d\)-dimensional polytope $P=\{x\in \R^d: Ux\leq z\}$ where $U$ is a $m\times d$ matrix and $z\in \R^m$. 
	If deleting any row of $U$ changes $P$, we call the system \textbf{irredundant} or \textbf{facet-defining}, since in this case each set $\{x\in P: \langle u_i,x\rangle = z_i\}$ defines a facet of $P$.
	
	\begin{remark}
		Any $d$-polytope $P$ with the origin in the interior can be presented as \begin{equation}\label{eq:system}
		P=\{x\in\R^d: Ux\leq 1\}
		\end{equation}
		for some matrix $U$ with $d$ columns and we allow the system to be redundant.  From the system we can read the polar polytope as \(P^{\circ}=
		\conv\{u: u\in \text{Rows}(U)\}\).
		
	\end{remark}
	\begin{definition}\label{def:polar}
		
		For our purposes we need a slightly more general notion of polarity.
		Given a system of inequalities of the form given in Equation \eqref{eq:system}, we define the $\D(P)$ as the point configuration of the row vectors of the system. The convex hull of $\D(P)$ is $P^\circ$. A point $u_i$ is a vertex if and only if $\langle u_i,x\rangle =1$ defines a facet of $P$.\end{definition}
	
	Let $Q\subset \R^c, R \subset \R^d$ be two polytopes. Their \textbf{(Cartesian) product} is
	\[
	Q\times R \colonequals  \{(q,r)\in \R^{c+d}: q\in Q, r\in R\}.
	\]
	The Cartesian product of two polytopes is a polytope and $\dim(Q\times R)=\dim(Q)+\dim(R)$. Furthermore every pair of nonempty faces $F_1\subset Q,F_2\subset R$ induces a nonempty face $F \colonequals F_1\times F_2$ of $Q\times R$ of dimension $\dim(F_1)+\dim(F_2)$. All nonempty faces of $Q\times R$ arise in this way. A \textbf{$d$-cube} is a polytope combinatorially isomorphic to the product of $d$ segments $\Delta_1$. 
	
	
	\subsection{Gale diagrams}
	We now come to a central tool for our results.
	
	\begin{definition}
		Let $\A=\{a_1,\dots, a_n\}\subset \R^d$ be a point configuration affinely spanning $\R^d$, and let $M_{\textbf{1},\A}$ be the matrix where the $i$-th column is $(1,a_i)\in \R^{d+1}$. A \textbf{Gale transform} of $\A$ is an $n$-point configuration $\gale(\A)= \{b_1,\dots, b_n\}\subset \R^{n-d-1}$ such that the row span of $M_{\textbf{1},\A}$ is orthogonal to the row span of $M_{\gale(\A)}$.
	\end{definition}
	
	The importance of Gale transforms stems from the fact that $\F(\A)$ can be read directly from $\gale(\A)$. More precisely \cite[Chapter 3, Theorem 1]{bible} states that
	\begin{equation}\label{eq:gale}
	\{a_{i_!},\dots,a_{i_k}\}\subset \A\text{ is a coface } \Longleftrightarrow \O\in\relint\left(\conv\left(\{b_{i_!},\dots,b_{i_k}\}\right)\right).
	\end{equation} 
	
	\begin{definition}
        We call two point configurations $\A_1$ and $\A_2$ \textbf{Gale equivalent} if there exists a bijection $\psi$ between them such that \[\O\in\relint(\conv\left(Z\right))\Longleftrightarrow \O\in\relint(\conv\left(\psi(Z)\right))\] for any subset $Z\subset\A_1$. Any point configuration that is Gale equivalent to a Gale transform of $\A$ is called a \textbf{Gale diagram} of $\A$.
	\end{definition}
	
	If $\A$ is an $n$-point configuration in $\R^d$, then a Gale diagram of $\A$ is an $n$-point configuration in $\R^{n-d-1}$. Thus Gale diagrams are particularly helpful when the number of vertices is small. Gale diagrams have also found uses in algebraic geometry; see, e.g., \cite{eisenbud}.
	\begin{example}\label{ex:gale}
		Let $\A=\{(0,0,0),(2,0,0),(0,2,0),(2,2,0),(1,1,1),(1,1,-1)\}$ be a point configuration in $\R^3$. The convex hull of $\A$ is an octahedron. Since the matrices $M_\A$ and $M_{\gale(\A)}$ below have orthogonal row spaces, the point configuration \\ $\gale(\A)=\{(1,0),(-1,-1),(-1,-1),(1,0),(0,1),(0,1)\}$ is a Gale transform of $\A$.
		\[
		M_\A=\begin{bmatrix}1&1&1&1&1&1\\ 0&2&0&2&1&1 \\ 0&0&2&2&1&1 \\ 0&0&0&0&1&-1 \end{bmatrix}, \qquad
		M_{\gale(\A)}=\begin{bmatrix}1&-1&-1&1&0&0\\ 0&-1&-1&0&1&1 \end{bmatrix}
		\]
		 The set $\{a_1,a_2,a_5\}$ is a coface of \(\A\), and $\conv(b_1,b_2,b_5)$ is a triangle that contains the origin in the interior, illustrating Equation \eqref{eq:gale}.
		
		\begin{figure}[ht]
            \centering
			
			\begin{tikzpicture}
			\node at (-5,2.8) {Point configuration $\A$};
			\node at (0.2,2.8) {A Gale transform $\A$};
			\node at (5.3,2.8) {A Gale diagram of $\A$};
			\begin{scope}[xshift=-7cm, yshift=-0.4cm,scale=1.5,
			x = {(1cm,0cm)}, y = {(.5cm,.3cm)}, z  = {(0cm,1.2cm)}]
			\coordinate (1) at (0,0,0);
			\coordinate (2) at (2,0,0);
			\coordinate (3) at (0,2,0);
			\coordinate (4) at (2,2,0);
			\coordinate (5) at (1,1,1);
			\coordinate (6) at (1,1,-1);
			
			\draw[thick] (1)--(2)--(5)--(1)--(6)--(2)--(4)--(5) (4)--(6);
			\draw[dashed] (5)--(3) (4)--(3) (3)--(1) (3)--(6);
			
			\foreach \p in {1,...,6}
			\node[shape=circle,draw,thick,fill=white] at (\p) {\p};
			
			\end{scope}
			
			\begin{scope}[xshift=0cm,scale=1.5]
			\coordinate (1) at (1,0);
			\coordinate (2) at (-1,-1);
			\coordinate (3) at (-1,-1);
			\coordinate (4) at (1,0);
			\coordinate (5) at (0,1);
			\coordinate (6) at (0,1);
			
			\draw[dotted] (1)--(2)--(5)--(1)--(6)--(2)--(4)--(5) (4)--(6);
			
			\node[shape=circle,draw,thick,fill=white] at (1) {1,4};
			\node[shape=circle,draw,thick,fill=white] at (2) {2,3};
			\node[shape=circle,draw,thick,fill=white] at (5) {5,6};
			
			\draw[fill=black] (0,0) circle [radius=.03];
			\node[above right] at (0,0) {$O$};
			
			
			\end{scope}
			
			\begin{scope}[xshift=4.6cm,scale=1.5]
			\coordinate (1) at (1,0);
			\coordinate (2) at (-0.9,-1.2);
			\coordinate (3) at (-1.2,-0.9);
			\coordinate (4) at (1.2,0.4);
			\coordinate (5) at (0,1.3);
			\coordinate (6) at (-.4,1);
			
			\draw[dotted] (1)--(2)--(5)--(1);
			\draw[dotted] (1)--(3)--(6)--(1);
			\draw[dotted] (4)--(2)--(6)--(4);
			\draw[dotted] (4)--(3)--(5)--(4);
			
			\foreach \p in {1,...,6}
			\node[shape=circle,draw,thick,fill=white] at (\p) {\p};
			
			
			\draw[fill=black] (0,0) circle [radius=.03];
			\node[above right] at (0,0) {$O$};
			
			
			\end{scope}
			
			\end{tikzpicture}
			\caption{The main objects of interest in Example \ref{ex:gale}.}
			\label{fig:basic_example}
		\end{figure}
		
	\end{example}
	
	
	\section{Minkowski Summands}\label{sec:type}
	
	Let $Q,R \subset \R^n$ be two polytopes. We define their \textbf{Minkowski sum} to be
	\[
	Q+R \colonequals  \{q+r: q\in Q, r\in R\}.
	\]
	The Minkoswki sum of two polytopes is a polytope. We call $Q$ a weak Minkowski summand of $P$, denoted $Q\preceq P$, if there exist a polytope $R$ and a positive scalar $\lambda$ so that $Q+R=\lambda P$. 
	Given a polytope $P$, we are interested in the set of all its Minkowski summands. 
	
	\begin{definition} Let $P$ be a polytope. Let $\sim_T$ be the equivalence relation \(P_1 \sim_T P_2 \iff P_1 = P_2 + \vec{v}\) for some vector \(\vec{v}\). Let \(\sim_{D+T}\) be the equivalence relation \(P_1 \sim_{D+T} P_2 \iff P_1 = \lambda P_2 + \vec{v} \) for some scalar \(\lambda\) and some vector \(\vec{v}\). We define
		
		
		\begin{align}
		\Mink(P) &\colonequals \{Q\text{ a polytope}: Q\preceq P \},\\
		\TMink(P)&\colonequals \Mink(P)/\sim_T,\\
		\DMink(P)&\colonequals \Mink(P)/\sim_{D+T}.
		\end{align}
		
	\end{definition}
	
	In the following sections we will study two different ways to parameterize these sets as  polyhedral sets. For this we need some classical results characterizing (weak) Minkowski summands. We use the characterization given in \cite[Chapter 15]{grunb}, written by G. Shephard, which we restate in the form we need for the present paper.
	
	\begin{theorem}[Shephard \cite{grunb}]
		Let $P=\{x\in\R^d: Ux\leq z\}$ be an irredundant inequality description for a polytope with $m$ facets. For any polytope $Q\subset \R^d$ the following are equivalent.
		\begin{enumerate}\label{thm:wms}
			\item[(i)] $Q$ is a weak Minkoswki summand of $P$.
			\item[(ii)] There exists a map $\phi:\F_0(P)\to \F_0(Q)$ such that for $v_i,v_j\in \F_0(P)$ with $\{v_i,v_j\}\in \F_1(P)$ we have $\phi(v_i)-\phi(v_j) = \lambda_{i,j} (v_i-v_j)$, for some $\lambda_{i,j}\in\R_{\geq 0}$.
			\item[(iii)] There exists $\eta\in\R^m$ such that $Q=\{x\in\R^d: Ux\leq \eta\}$ and for any subset of rows \(S\) such that the linear system $\{\langle u_i,x\rangle=z_i, \forall i\in S\}$ defines a vertex of $P$, the linear system $\{\langle u_i,x\rangle=\eta_i, \forall i\in S\}$ defines a vertex in $Q$.
		\end{enumerate}
	\end{theorem}
	
	
	\begin{remark}\label{rem:unique}
		In the description given in Theorem \ref{thm:wms}(iii) the vector $\eta$ is unique. In fact we have $\eta_i=\max_{x\in Q}\langle u_i,x\rangle$.
	\end{remark}
	
	\section{Parametrizing \(\Mink(P)\): Minkowski weights}\label{sec:polygons}
	
	We split this section into two parts. In the first, we describe some of the theory of Minkowski weights. In the second part, we use this theory to study the case of polygons. 
	
	\subsection{Minkowski weights}\label{sec:mink}
	\begin{definition}
		A \textbf{1-Minkowski weight} on $P$ is a function $\omega: \F_1(P)\to\R$ such that for each \(F \in \F_2(P)\) choosing a cyclic orientation \(v_E\)  of its edge vectors gives
		\begin{equation}\label{eq:balanced}
		\sum_{E\in F} v_E \cdot\omega(E) = \O.
		\end{equation}
		Equation \eqref{eq:balanced} is called the \textbf{balancing condition}.
		The set of all 1-Minkowski weights on $P$ is denoted $\Omega_1(P)$. See \cite{weights} for general information about Minkowski weights.
	\end{definition}
	
	\begin{definition}\label{def:type}
		Let $P$ be a polytope. We define
		\begin{align}
		\typecone(P) &\colonequals \left\{\omega\in\Omega_1(P): \omega(E)\geq 0, \forall E\in\F_1(P)\right\}, \label{eq:typecone}\\
		\type(P) &\colonequals \bigg\{\omega\in\typecone(P): \sum_{E\in\F_1(P)}\omega(E)=f_1(P)\bigg\}. \label{eq:type}
		\end{align}
		
		The \textbf{type cone} is the pointed polyhedral cone $\typecone(P)$.  We note that $\typecone(P)$ is a cone over the \textbf{type polytope} $\type(P)$, so they easily determine one another.
	\end{definition}
	
	The polyhedron $\typecone(P)$ parametrizes $\TMink(P)$.
	Indeed, Theorem \ref{thm:wms}(ii) guarantees the existence of a $1$-Minkowski weight for \(Q\) and conversely, \cite[Theorem 15.5]{faces} describes how to reconstruct $Q$ from a \(1\)-Minkowski weight, up to translation.
	The polytope $\type(P)$ parametrizes the set $\DMink(P)$.
	
	
	\begin{definition}
		Let $P$ be a polytope and $S\subset\F_1(P)$ a subset of its edges. If there exists $\omega\in\typecone(P)$ such that $\omega(E)=0$ if and only if $E\in S$, then $S$ is a \textbf{vanishing} set. The faces of the type cone are in bijection with vanishing sets of edges.
	\end{definition}
	
	When $P$ is a simple $d$-dimensional polytope we have 
	\begin{equation}\label{eq:dim}
	dim \left(\typecone(P)\right) = f_{d-1}(P)-d,
	\end{equation}by \cite[Theorem 11]{mcmullen}. Hence $\dim \left(\type(P)\right) = f_{d-1}(P)-d-1.$ The dimension of $\typecone(P)$ is hard to compute in general. When $\dim(\typecone(P))=1$ we say that $P$ is an indecomposable polytope, since its only weak Minkowski summands are, up to translation, dilations of $P$. 
	
	
	
	\subsection{Application: Polygons}
	
	We now focus on two-dimensional polytopes, better known as polygons. Let $P$ be a polygon. Each edge \(E_i\) of \(P\) gives an inequality \(\omega(E_i) \geq 0\) which could be a facet of \(\type(P)\). 
	For each edge $E_i$ of \(P\), let $\bn_i$ be the \emph{unit} outer-pointing normal.
	We use the notation $\nN(P)\subset \S^1$ to indicate the point configuration consisting of all these outer normals. 
	
	\begin{example}
		In Figure \ref{fig:normal} we depict a polygon \(P\) together with its associated point configuration \(\nN(P)\).
		\begin{figure}[ht]
            \centering
			\begin{tikzpicture}
			\begin{scope}[xshift=-3cm]
			\node at (0.5,-1) {$P$};
			\draw[fill=black] (0,0) circle (.05);
			\draw[fill=black] (2,0) circle (.05);
			\draw[fill=black] (2,1) circle (.05);
			\draw[fill=black] (1,2) circle (.05);
			\draw[fill=black] (0,2) circle (.05);
			\draw[fill=black] (-1,1) circle (.05);
			\draw (0,0)--(2,0)--(2,1)--(1,2)--(0,2)--(-1,1)--cycle;
			
			\node[below] at (1,0) {$E_1$};
			\node[right] at (2,.5) {$E_2$};
			\node[above right] at (1.5,1.5) {$E_3$};
			\node[above] at (.5,2) {$E_4$};
			\node[above left] at (-.5,1.5) {$E_5$};
			\node[below left] at (-.5,.5) {$E_6$};
			
			\end{scope}
			
			\begin{scope}[xshift=3cm, yshift=1cm]
			\node at (0,-2) {$\nN(P)$};
			\draw[dashed] (0,0) circle (1);
			\draw[fill=black] (0:1) circle (.05);  \draw[<-] (0:1.4) -- (0:0);
			\node at (10:1.3) {$\bn_2$};
			\draw[fill=black] (45:1) circle (.05); \draw[<-] (45:1.4) -- (0:0);
			\node at (57:1.3) {$\bn_3$};
			\draw[fill=black] (90:1) circle (.05); \draw[<-] (90:1.4) -- (0:0);
			\node at (103:1.3) {$\bn_4$};
			\draw[fill=black] (135:1) circle (.05); \draw[<-] (135:1.4) -- (0:0); 
			\node at (148:1.3) {$\bn_5$};
			\draw[fill=black] (225:1) circle (.05); \draw[<-] (225:1.4) -- (0:0);
			\node at (212:1.3) {$\bn_6$};
			\draw[fill=black] (270:1) circle (.05); \draw[<-] (270:1.4) -- (0:0);
			\node at (283:1.3) {$\bn_1$};
			\end{scope}
			
			\end{tikzpicture}
			
			\caption{A polygon $P$ and its associated $\nN(P)$.}\label{fig:normal}
			
		\end{figure}
		
	\end{example}
	
	
	\begin{proposition}\label{prop:polygon_normal}
		Let $P$ be a polygon with edges $\F_1(P)=\{E_1,\dots,E_n\}$. A subset $S\subset\F_1(P)$ is a vanishing set if and only if $\O\in\relint\left(\conv\{n_i:E_i\notin S\}\right).$
	\end{proposition}
	
	\begin{proof} 
		Denote the vertices of \(P\) by \(v_i\) so that the indices increase counterclockwise. To the edge \(E_i  \colonequals  conv(v_i,v_{i+1})\), we associate the vector \(v_{E_i} = v_{i+1}-v_i\). Let \(\{\lambda_j\}\) be a set of non-negative Minkowski weights for \(P\), that is, \(\sum \lambda_i v_{E_i} =\O \). Let $T$ be the linear transformation defined by $90$-degree clockwise rotation, so \(T(v_{E_i}) = \left|v_{E_i}\right| \bn_i\) and thus \(\sum \lambda_i \left|v_{E_i}\right| \bn_i = \O\). This is simply a non-negative linear combination of the \(\bn_i\).
		Therefore, 
		any choice of $1$-Minkowski weights with vanishing set \(S\) 
		corresponds exactly with 
		a strictly positive combination of \(\{\bn_i\}_{i \notin S}\) that sums to \(\O \).
	\end{proof}
	
	With some more work, this proposition can be modified to the following corollary.
	
	\begin{corollary}\label{cor:type_polygon}
		Let $P$ be a polygon. Then $\nN(P)$ is a Gale diagram for the configuration \(\A(P)\). 
	\end{corollary}
	
	This corollary allows us to read off the face lattice of $\A(P)$ (and hence $\type(P)$) from $\nN(P)$.
	
	\begin{proposition}[Theorem \ref{thm:market2}]\label{prop:all_types}
		Let $Q$ be a $d$-dimensional polytope with $d+3$ facets. Then for some \((d+3)\)-gon \(P\), \(Q\) is combinatorially equivalent to \(\type(P)\).
	\end{proposition}
	
	\begin{proof}
		Simple inspection shows that the assumptions imply that \(d\geq 2\), and \(Q\) has at least 5 facets.
		Since \(Q^\circ\) is \(d\)-dimensional and has $d+3$ vertices, \(\gale(Q^\circ)\) is in \(\R^2\). Scaling each point to be distance \(1\) from the origin, we get a Gale diagram for \(Q\) in $\S^1$. Any point configuration with at least 5 points on $\S^1$ with the origin in its relative interior is equal to $\nN(P)$ for some polygon $P$. One such polygon for \(\gale(Q^\circ)\) is obtained by drawing the tangents to \(\S^1\) at each of the \((d+3)\) points.
	\end{proof}
	
	From Proposition~\ref{prop:all_types} we see that there are many combinatorially different type polytopes of combinatorially equivalent polygons. This phenomenon is illustrated in Example \ref{ex:hexagons}. 
	
	
	We now compute the type cone for the particular case of regular $2n$-gons, since they are the Coxeter submodular cones of type $I_n$ defined in \cite{coxeter}.
	
	\begin{proposition}\label{prop:2dim} 
		The $f$-vector of $T_{2m} \colonequals \typecone(P)$ where $P$ is a regular $2m$-gon is
		\begin{align}
		f_0&=1,\\
		f_1(T_{2m})&=\binom{2m}{3}-2m\binom{m}{2}+m,\\
		f_k(T_{2m})&=\binom{2m}{k+3}-2m\binom{m}{k+2},\quad 2\leq k\leq 2m-2.
		\end{align}
	\end{proposition}
	
	
	
	Since different $m$-gons can have different type cones, it is natural to ask which polygon maximizes the $f$-vector of its type cone.
	Comparing Proposition~\ref{prop:2dim} with the Upper Bound Theorem  \cite[Chapter 4.2]{bible}, we see that for even \(m\) at least 4, the regular $m$-gons do not maximize the $f$-vector over all type polytopes of $m$-gons. Polygons that do maximize the $f$-vector are instead slight perturbations of regular $m$-gons as shown in (i) in Figure~\ref{fig:hexagons}. For $m$ odd, the regular realizations do maximize the $f$-vector.  
	
	If we wish to minimize the \(f\)-vector instead, there is no \(f\)-vector smaller than that of a simplex. For all \(m\), there is an \(m\)-gon whose type cone is a simplex.
	
	
	\begin{example}\label{ex:hexagons}
		Figure~\ref{fig:hexagons} shows the point configuration $\nN(P)$ for three hexagons with three different type polytopes.
		
		\begin{figure}[ht]
            \centering
			
			\begin{tikzpicture}
			
			\begin{scope}[xshift=4cm]
			
			\draw[dashed] (0,0) circle (1); 
			
			\foreach \r in {1,2,3}
			\draw[fill=black] (-120*\r+120:1) circle (.05);
			
			\foreach \a in {1,2,3}
			\draw (-120*\a+120:1.3) node {$\a$};
			
			\foreach \r in {4,5,6}
			\draw[fill=black] (90+\r*10:1) circle (.05);
			
			\foreach \a in {4,5,6}
			\draw (90+\a*10:1.3) node {$\a$};
			
			
			\node[above] at (0,0) {$O$};
			\draw[fill=black] (0,0) circle (0.05);
			
			\node at (0,-1.5) {$(iii)$};
			\node at (0,-2) {$f$-vector $=(1,4,6,4)$};
			\end{scope}
			
			\begin{scope}[xshift=0cm]
			\draw[dashed] (0,0) circle (1); 
			
			\foreach \r in {1,2,...,6}
			\draw[fill=black] (-60*\r+60:1) circle (.05);
			
			\foreach \a in {1,2,...,6}
			\draw (-60*\a+60: 1.3) node {$\a$};
			
			\foreach \a in {1,2,3}
			\draw[dotted] (-60*\a+60:1)--(-60*\a+60+180:1);
			
			\node[above] at (0,0) {$O$};
			\draw[fill=black] (0,0) circle (0.05);
			
			\node at (0,-1.5) {$(ii)$};
			\node at (0,-2) {$f$-vector $=(1,5,9,6)$};
			\end{scope}
			
			\begin{scope}[xshift=-4cm]
			
			
			\draw[dashed] (0,0) circle (1); 
			
			\foreach \r in {1,3,5}
			\draw[fill=black] (-60*\r+60:1) circle (.05);
			
			\foreach \a in {1,3,5}
			\draw (-60*\a+60: 1.3) node {$\a$};
			
			\foreach \r in {2,4,6}
			\draw[fill=white] (-60*\r+60:1) circle (.05);
			
			\foreach \r in {2,4,6}
			\draw[fill=black] (-60*\r+70:1) circle (.05);
			
			\foreach \a in {2,4,6}
			\draw (-60*\a+70: 1.3) node {$\a$};
			
			\foreach \a in {1,2,3}
			\draw[dotted] (-60*\a+60:1)--(-60*\a+60+180:1);
			
			\node[above] at (0,0) {$O$};
			\draw[fill=black] (0,0) circle (0.05);
			
			\node at (0,-1.5) {$(i)$};
			\node at (0,-2) {$f$-vector $=(1,8,12,6)$};
			\end{scope}
			
			\end{tikzpicture}
			\caption{Three hexagons with combinatorially different type polytopes with their $f$-vectors.}
			\label{fig:hexagons}
		\end{figure}
		
	\end{example}
	
	\section{Parametrizing $\Mink(P)$: Intersections in the Gale diagram}\label{sec:cubes}
	
	In \cite{mcmullen} McMullen gave a different technique to analyze type polytopes. In this section, we first discuss this technique and then apply it to compute the type polytope of the product of simplices.
	
	\begin{theorem}[McMullen \cite{mcmullen}]\label{thm:mcmullen}
		Let $P$ be a polytope, $\A=\{a_1,\dots,a_m\}$ be the vertex set of its polar $P^\circ$, and $\gale(A)=\{b_1,\dots,b_m\}$ be a Gale transform for $\A$. Then \[\type(P)\cong \bigcap_S \conv\{b_i: b_i\in S\},\] where the intersection is over all cofacets $S$ of $\A$.
	\end{theorem}
	
	Theorem~\ref{thm:mcmullen} follows from the results of \cite{mcmullen}, see in particular his comments on Page 88 at the end of Section 2. 
	
	

	
	\subsection{Application: products of simplices}
	
	Using this theorem of McMullen, we are able to compute the type cone of the product of arbitrary simplices. We start with a lemma describing the cofacets.
	
	
	\begin{lemma}\label{lem:product}
		Let $P$ a product of $k+1$ simplices, then the cofacets of \(P^\circ\) are of size \(k+1\), and the vertices of $P^\circ$ can be colored with $k+1$ colors such that every cofacet contains a vertex of each color.
	\end{lemma}
	
	Taking the Gale dual of this motivates the definition of a rainbow configuration, defined by example in the following illustration. 
	
	
	\begin{example}
		Figure~\ref{fig:rain_config} shows an example of a rainbow configuration in $\R^2$. 
		\begin{figure}[ht]
            \centering
			\begin{tikzpicture}[scale=0.6]
			\usetikzlibrary{intersections}
			\node[coordinate] at (-3,1) (x1){};
			\node[coordinate] at (-2,-1.5) (x2){};
			\node[coordinate] at (3,-.5) (y1){};
			\node[coordinate] at (1.75,-2) (y2){};
			\node[coordinate] at (2.25,2.75) (z1){};
			\node[coordinate] at (-1,3.5) (z2){};
			\node[coordinate] at (0.5,3.5) (z3){};%easy to go back, remove all the % lines
			\draw[fill=black,opacity=0.1] (x1) -- (y1) -- (z1) -- cycle;
			\draw[fill=black,opacity=0.1] (x1) -- (y1) -- (z2) -- cycle;
			\draw[fill=black,opacity=0.1] (x1) -- (y1) -- (z3) -- cycle;
			\draw[fill=black,opacity=0.1] (x1) -- (y2) -- (z1) -- cycle;
			\draw[fill=black,opacity=0.1] (x1) -- (y2) -- (z2) -- cycle;
			\draw[fill=black,opacity=0.1] (x1) -- (y2) -- (z3) -- cycle;
			\draw[fill=black,opacity=0.1] (x2) -- (y1) -- (z1) -- cycle;
			\draw[fill=black,opacity=0.1] (x2) -- (y1) -- (z2) -- cycle;
			\draw[fill=black,opacity=0.1] (x2) -- (y1) -- (z3) -- cycle;
			\draw[fill=black,opacity=0.1] (x2) -- (y2) -- (z1) -- cycle;
			\draw[fill=black,opacity=0.1] (x2) -- (y2) -- (z2) -- cycle;
			\draw[fill=black,opacity=0.1] (x2) -- (y2) -- (z3) -- cycle;
			\node[circle,inner sep=2pt,fill=blue] at (x1){$x_1$};
			\node[circle,inner sep=2pt,fill=blue] at (x2){$x_2$};
			\node[circle,inner sep=2pt,fill=red] at (y1){$y_1$};
			\node[circle,inner sep=2pt,fill=red] at (y2){$y_2$};
			\node[circle,inner sep=2pt,fill=orange] at (z1){$z_1$};
			\node[circle,inner sep=2pt,fill=orange] at (z2){$z_2$};
			\node[circle,inner sep=2pt,fill=orange] at (z3){$z_3$};
			
			%stuff to make the full intersection black.
			\path[name path=line 1] (z1) -- (x2);
			\path[name path=line 2] (z2) -- (y2);
			\path[name path=line 3] (y1) -- (x1);	
			\path [name intersections={of = line 1 and line 2}];
			\coordinate (c1)  at (intersection-1);
			\path [name intersections={of = line 1 and line 3}];
			\coordinate (c2)  at (intersection-1);
			\path [name intersections={of = line 2 and line 3}];
			\coordinate (c3)  at (intersection-1);
			\draw[fill=black,opacity=1] (c1) -- (c2) -- (c3) -- cycle;
			\end{tikzpicture}
			\caption{A rainbow configuration in the plane with three colors.}
			\label{fig:rain_config}
		\end{figure}
	\end{example}
	
	\begin{proposition}\label{prop:rainbow}
		Let $P\subset \R^d$ be combinatorially isomorphic to a product of $k+1$ simplices. Then every Gale transform $\G$ of $P^\circ$  is a rainbow configuration in $\R^{k}$.
	\end{proposition}	
	
	In Figure~\ref{fig:rain_config}, the intersection of all the rainbow triangles is again a triangle. We make this explicit in general.
	
	\begin{theorem}\label{thm:intersection}
		Let $T$ be the intersection of all rainbow simplices of some rainbow configuration \(\rR(\bd)\) in \(\mathbb{R}^k\). Then $T$ is a simplex.
	\end{theorem}
	
	
	
	We preface our final theorem with a comment on \(\type(P)\) for \(P\) a \(d\)-cube. In the parameterization of \(\type(P)\) by \(1\)-Minkowski weights using Equation \eqref{eq:typecone}, \(\type(P)\) is embedded in \(\mathbb{R}^{d2^{d-1}}\) given by exponentially many inequalities. It turns out that it has only $d+1$ facets.
	
	\begin{theorem}\label{thm:main}
		For any $P$ combinatorially isomorphic to a product of $k+1$ simplices, $\type(P)$ is a simplex of dimension $k$. In particular, the type cone of any combinatorial cube is simplicial of the same dimension.
	\end{theorem}
	
	\begin{proof}
		
		Theorem~\ref{thm:mcmullen} and Proposition~\ref{prop:rainbow} together show that \(\type(P)\) is the intersection of all rainbow simplices in a rainbow configuration, and Theorem~\ref{thm:intersection} shows this intersection is a simplex.
	\end{proof}
	
	
 \printbibliography
	
	%\bibliography{biblio}
	%\bibliographystyle{amsplain}
	
	
\end{document}\grid
