text:
\begin{document}
\title{Strong Pseudo Transitivity and Intersection Graphs
}
\author{Farhad Shahrokhi\\
Department of Computer Science and Engineering,  UNT\\
farhad@cs.unt.edu
}

\date{}
\maketitle
\thispagestyle{empty}
\date{} \maketitle

\begin{abstract}
A directed graph $G=(V,E)$ is {\it strongly pseudo transitive}  if there is a partition $\{A,E-A\}$ of $E$  so that graphs $G_1=(V,A)$ and
$G_2=(V,E-A)$ are transitive,  and additionally, if  $ab\in A$ and $bc\in E $ implies that  $ac\in E$.  A strongly pseudo  transitive graph $G=(V,E)$ is strongly pseudo transitive of the first type, if $ab\in A$ and $bc\in E$ implies $ac\in A$.
An undirected graph is co-strongly pseudo transitive (co-strongly pseudo transitive of the first type)  if its  complement has an orientation which is  strongly pseudo transitive (co-strongly pseudo transitive of the first type). Our purpose is  show that  the  results  in  computational geometry \cite{CFP, Lu} and intersection graph theory  \cite{Ga2, ES}  can be unified and extended,  using  the  notion of strong pseudo transitivity.  As a  consequence  the   general algorithmic  framework in  \cite{Sh} is applicable to solve the maximum independent set in $O(n^3)$ time in a variety of problems, thereby, avoiding case by case lengthily arguments for  each problem.

We show that  the  intersection graphs of axis parallel rectangles intersecting a diagonal line from bottom, and half segments  are co-strongly pseudo transitive.
In addition,  we show that  the class of the interval filament graphs is co-strongly transitive  of the  first type, and hence  the class of  polygon circle  graphs which is contained in the class of interval filament graphs (but contains the   classes of chordal graphs, circular arc, circle, and outer planar graphs), and the class of incomparability graphs are strongly transitive of the first type.  For class of chordal graphs we give two different proofs, using two different characterizations, verifying that they are  co-strongly transitive  of the  first type. Furthermore, we note that the class of co-strongly pseudo transitive  graphs of the first type  is properly contained in the class co-pseudo  transitive graphs, unless $P=NP$, and the class of tree filament graphs is  properly contained in the class co-pseudo  transitive graphs, unless $P=NP$.
Computational consequences are presented.
 \end{abstract}

\section{Introduction}
``The first genuine monograph on graph theory (K\"onig, 1936)
had the following subtitle: {\it Combinatorial Topology of
Systems of Segments} \cite{K}. Although graph theory and topology
stem from the same root, the connection between them has
somewhat faded away in the past few decades. In the most
prolific new areas of graph theory including Ramsey theory, extremal
graph theory and  random graphs, graphs are regarded as
abstract binary relations rather than systems of segments.
It is quite remarkable that {\em traditional} graph theory is
often incapable of providing satisfactory answers for the
most natural questions   concerning the  drawings of graphs'' \cite{Pa}.

Recall that a directed graph $G=(V,E)$ is {\it transitive} if $ab\in E$ and $bc\in E$ implies $ac\in E$. One can view a transitive graph as an alternate way of defining a partial order
\cite{Tr2}. By dropping the orientation on the edges of a transitive  graph we obtain a comparability graph. The complement of a comparability graph is an incomparability
graph. In \cite{Sh} we  introduced the  concepts of {\it pseudo  transitivity} and {\it strong pseudo  transitivity}  which are  ways of generalizing the concept of transitivity in graphs. The motivation behind writing this  paper arose from recent results in computational geometry \cite{CFP, Lu} and  intersection graphs theory \cite{ES}, \cite{Ga2}  that can be unified  and generalized  using the  concept of strong pseudo  transitivity.

Let $S$ be a finite set and $\{S_1,S_2,...,S_k\}$ be a collection of subsets of $S$.
The intersection (overlap) graph of $S$ is a graph with  the vertex set $S$, where $S_iS_j$ is an edge if $S_i\cap S_j\ne \emptyset$
($S_i\cap S_j\ne \emptyset$, and $S_i\not\subseteq S_j$,  $S_j\not\subseteq S_i$).

Many intersecting graphs are the intersection or the overlap graphs of combinatorial or geometric structures. For instance  incomparability graphs are intersection graphs of $x-$monotone curves intersecting two lines parallel  to the  $y$ axis \cite{GR},  overlap graphs are  overlap graphs of intervals on a line, chordal graphs are the intersection graph of subtrees of a tree \cite{Ga1},  polygon-circle graphs are  the intersection graphs of  convex polygons in a circle, Interval  filament  graphs are the intersection graphs of filaments over intervals \cite{Ga2} and,
subtree filament are intersection graphs of filaments over trees \cite{Ga2}, or overlap graph of subtrees of a tree \cite{ES}.

 A directed graph $G=(V,E)$ is {\it  pseudo transitive} if there is a partition $\{A,E-A\}$ of $E$  so that graphs $G_1=(V,A)$  is transitive,  and additionally, if  $ab\in A$ and $bc\in E $ implies that  $ac\in E$.
 A directed graph $G=(V,E)$ is {\it strongly pseudo  transitive} if there is a partition $\{A,E-A\}$ of $E$  so that graphs $G_1=(V,A)$ and
$G_2=(V,E-A)$ are transitive,  and additionally, if  $ab\in A$ and $bc\in E $ implies that  $ac\in E$.
Let   $G=(V,E)$  be pseudo  transitive (pseudo transitive) with the underlying partition $\{A, E-A\}$, then $G$ is  {\it  pseudo transitive  of the first type} (pseudo transitive of the first type)  if  $ab\in A$ and $bc\in E$ implies that  $ac\in A$.

An undirected graph $G$ is co-pseudo transitive (co-pseudo transitive of the first type)  if the complement of $G$  has an orientation that is pseudo transitive (pseudo transitive of the first type one. $G$ is  co-strongly pseudo transitive (co-strongly transitive  of the first type), if  the complement of $G$    has an  orientation which  is strongly pseudo transitive (co-strongly transitive of the first type). Co-pseudo transitive graphs contain the intersection graph of many geometric structures.
For instance,  the following result was shown  in \cite {Sh}, with  a slightly altered  language.
\begin {th}\label{t0}
{\sl
Let $P$ be a finite collection of bounded closed subsets of $R^k$, then
the intersection graph of $P$ is co-pseudo transitive of the first type.
}

\end{th}

A half segment is a straight  line segment that has  one end point on the $x$-axis,  another end point in the upper half plane, and makes  an  acute angel with $x-$axis.
Motivation behind introducing these segments  arose from the work of Pach and Torocsik \cite{PT}  on  geometric  graphs. Biro and Trotter \cite{BT} studied  properties  of partial orders arising from half segments. Computing the maximum independent set in the intersection graph of a set of rectangles is a fundamental problem arising  in map labeling \cite{TDE}.
 Since the general  version of this problem is known to be NP-hard, some researchers have  focused to solve the special version of the problem, including the instances where all rectangles are intersected by a diagonal line from below.
See the work of Lubiw \cite{Lu}, and  Correa, Feuilloley,Perez-Lantero , and  Soto \cite{CFP}, which provide an $O(n^3)$ and $O(n^2)$  time algorithm, respectively.

In this paper we explore the connections between the  graph  classes mentioned above  and  the class of  co-strongly pseudo transitive graphs.  Specifically we show  that  the  intersection graphs of  half line segments and  axis parallel rectangles intersecting a diagonal line from bottom are co-strongly pseudo transitive. Moreover,  we show that  the class of the interval filament graphs is co-strongly transitive of the first type, and hence  the class of  polygon circle  graphs which is contained in the class of interval filament graphs (but contains the   classes of chordal, circular arc, circle, and outer planar graphs), and the class of incomparability graphs are strongly transitive of the first type.  For the  class of chordal graphs which is  contained in the class of polygon circle graphs, we provide two  direct direct proofs,  showing  that they are co-strongly transitive of the first type. Additionally, we present some results concerning the
Containment of different classes.  A contribution of our work is  to connect and unify the problems  in  computational geometry \cite{CFP, Lu},  intersection graph theory  \cite{Ga2, ES} and combinatorics
 \cite{BT}  using  the  notion of strong pseudo transitivity, thereby, showing they are all   amenable to the  algorithmic  framework in  \cite{Sh}  for  solving  the maximum independent set in $O(n^3)$ time, thereby, avoiding case by case or lengthy arguments for each scenario.

\section{Structural Results}
\begin{th}
{\sl Let $R$ be a set of axis parallel  rectangles in the plane all of them are intersected by a diagonal  line $l$ with the property that if two elements of $R$ intersect, then they also intersect below $l$.  Let  $G=(V,E)$ be the intersection graph of $S$,   then $G$ is co-strongly pseudo transitive.}
 \end{th}
 {\bf Proof.} For any $C\in R$, let $x_C$ and $y_C$ denote the smallest  $x$ coordinate, and smallest  $y$ coordinate of four corners of $C$, respectively. Now let $W, Z\in R$ with $WZ\notin E$,  so   that  $x_W\le x_Z$
 (the case $x_W>x_Z$ is symmetric). If $y_W\le y_Z$, then, orient $WZ$ from $W$ to $Z$, and place it in $A$. Otherwise if $y_W>y_Z$, then, still orient $WZ$ from $W$ to $Z$ but place it in $B$. It can be verified   that $A\cap B=\emptyset $, and that any non edge of $G$ has a orientation  in $\hat E=A\cup B$.
 Furthermore, it can be shown that  this case, the directed acyclic  graph   $H=(V,\hat E)$   is strongly pseudo-transitive, with the partition $\{A, \hat E-A\}$. $\Box$.

The following result was mentioned in \cite{Sh} without an explicit proof. Next,  we specifically state and prove it.

 \begin{th}
 {\sl Let $R$ be a set of half segments in the plane, and let  $G=(V,E), V=R$ be the intersection graph of $R$,   then $G$ is co-strongly pseudo transitive.}
 \end{th}
 {\bf Proof.} For any $r\in R$, let $x_1(r)$ and $x_2(r)$ denote the smallest $x$ coordinate, and the largest $x$ coordinate of any points in $r$.
 Now let $r,s\in R$ so that $rs\notin E$ so that $x_1(r) < x_1(s)$.  if
 $x_2(s)\ge x_2(r)$, then orient $rs$ from $r$ to $s$ and place $rs$ in $A$.
 Otherwise, if $x_2(s)<x_2(r)$ (note the assumption $rs\notin E$), then still  orient $rs$ from $r$ to $s$, but  place the directed  edge $rs$ in $B$. The remaining of the proof copies previous the theorem. $\Box$

 \begin{th}
{\sl Let $G=(V,E)$ be an interval filament graph, then $G$ is co-strongly pseudo transitive of the first type.}
 \end{th}

 {\bf Proof.} Consider a representation of $G$, where  $I$ is  a set of intervals on the real line, and for each $i\in I, C_i$ is a collection of curves on the half plane above $i$ that connects the end points of $i$. Then $V=\cup_{i\in I}C_i$ and furthermore $xy\in E$, if  $x,y\in C_i$ for some $i\in I$, and  $x$ and $y$  intersect.
 Now let  $x,y\in V, xy\not\in E$.  If $x\in C_i, y\in C_j, i<j$, then orient $xy$ from $x$ to $y$ and place $xy$ in $A$. Otherwise $x,y\in C_i$ for some $i\in I$. Since  $x$ and $y$ do not intersect and connect the endpoint for interval $i$, the area under one of them (say $x$) contains the area under the other (say $y$). In this case orient $xy$ from $x$ to $y$ and place it in $B$. Note that  $A\cap B=\emptyset$, every $xy\notin  E$ has an orientation in $\hat E=A\cap B$. Furthermore the  directed acyclic  graph   $H=(V,\hat E)$, is strongly pseudo transitive, and  for any  $xy\in A$ and $yz\in  \hat E$, we have  $xy\in A$. $\Box$.

\begin{con}\label{c1}
 {\sl The class of interval filament graphs is properly contained in the class co-strongly pseudo  transitive of the first type.}

  \end{con}

Since chordal graphs play an important role in graph theory,  we
give  two different direct proofs, based on  different representations,   showing that  they are co-strongly pseudo transitive. The first proof  uses the  characterization that every chordal graph is the intersection graph of subtrees of the a tree, where, the second assumes  a perfect elimination ordering is given.

 Let $L={v_1,v_2,...,v_n}$ be a perfect elimination ordering  (PEO) of a chordal graph $G=(V,E)$. A {\it canonical depth first search tree}  of $G$ (with respect to $L$) is  a depth first search  spanning tree rooted at $v_1$  constructed applying  the following simple rule for visiting vertices: Assume vertex  $v_i$ is  currently visited, then,  select   the next vertex to visit  to be the smallest indexed vertex $v_j, j>i$ among all unvisited vertices adjacent to $v_i$ in $G$.

   \begin{th}\label{t1}
{\sl Every choral graph $G=(V,E)$ is co-strongly pseudo transitive of the first type.}
 \end{th}
 {\bf First Proof.}
  Let $T$ be a tree,  let $V=\{T_1,T_2,...,T_k\}$ be a set of subtrees of $T$. Assign a root $r$ to $T$, embed $T$ in the  plane, and assign  root $r_i$ to each $T_i\in V$, which is the closest vertex of $T_i$ to $r$. Let  $ G=(V,E)$ be the intersection graph of these subtrees, let ${\bar G}=(V,{\bar E})$ be the complement of $G$.  To prove the claim we will show there is a suitable  orientation on  $\bar E$.
  For any  $e=T_iT_j\in\bar E$ so that $r_i$ is not an ancestor of $r_j$ in $T$, and $r_i$  to the left of $r_j$ in the planar  embedding of $T$, orient $e$ from $T_i$ to $T_j$ and place the resulting oriented  edge in $A$.  For any $e=T_iT_j\in {\bar E}$ so that  $r_i$ is an ancestor  of $r_j$ in $T$
 orient  $e$ from $T_i$ to $T_j$ and place the resulting  oriented  edge in $B$.

 It can be verified that  $A\cap B=\emptyset$, every $e\in {\bar E}$ has an orientation in $\hat E=A\cap B$, and  that directed acyclic  graph   $H=(V,\hat E)$,   is strongly pseudo  transitive, thus verifying the claim.  Moreover, in this case $xy\in A$ and $yz\in  \hat E$ implies $xy\in A$.

{\bf Second Proof.}
Let $L=\{v_1,v_2,....,v_n\}$ be a PEO  of $G$. Let $T$ be a canonical depth first search spanning tree of $G$ rooted at $v_1$. Let ${\bar e}=xy\not\in E$ with $dfs(x)<dfs(y)$. If $x$ and $y$ are on two different branches of $T$ then orient ${\bar e}$ from $x$ to $y$ and place $xy$ in $A$. Otherwise,  $x=v_i$ and $y=v_j$ are on the same  branches of $T$. Observe  in this case that  we must have $i<j$.   Since $T$ is a canonical depth first tree, and, orient ${\bar e}$ from $x$ to $y$ and place $xy$ in $B$.

{\bf  Claim.} Let $v_i,v_j, v_k, i<j<k$ be three  vertices on the same branch of $T$. If $v_iv_j\notin E$, and $v_jv_k\notin E$, then $v_iv_k\notin E$.

It can verified (using the claim and properties of $T$) that $A\cap B=\emptyset$, every $e\in {\bar E}$ has an orientation in $\hat E=A\cap B$,  and that  directed acyclic  graph   $H=(V,\hat E)$   is strongly pseudo  transitive. Additionally,  for any  $xy\in A$ and $yz\in  \hat E$, we have  $xy\in A$.
$\Box$

We finish this section by the  establishing  some containment properties.

\begin{th}\label{t10}
{\sl

$(i)~$The class of co-pseudo  (co-strongly pseudo) transitive graphs of the first type is contained in the class of co-pseudo  (co-strongly pseudo) transitive graphs.

$(ii)~$The class of co-strongly pseudo transitive  graphs of the first type  is properly contained in the class co-pseudo  transitive graphs of the first type, unless $P=NP$.

$(iii)~$The class of tree filament graphs is  contained in the class
co-pseudo  transitive graphs.

$(iv)~$The class of tree filament graphs is  properly contained in the class
co-pseudo  transitive graphs, unless $P=NP$.
}
\end{th}

{\bf Proof.} Clearly $(i)$ holds. For $(ii)$, first note that by Theorem \ref{t0}
the intersection graph  $G$ of a set of rectangles is co-pseudo transitive of the first time. Next note that  computing the maximum independent set of $G$ is NP-hard, but can be done in $O(n^3)$ time for any co-strongly pseudo transitive graph. We omit proof of $(iii)$. $(iv)$ follows that graphs of boxicity two are co-pseudo transitive and  computing their maximum independent set is known to be NP-hard, but  computing
maximum independent set in tree filament graphs can be done in polynomial time.
$\Box$.

\section{Algorithmic Consequences}
The following result was shown in \cite{Sh}

\begin{th}
{\sl
Let $H=(V,F)$ be strongly pseudo-transitive. The maximum weighted chain  can be computed in $O(\sum_{x\in V}deg^2(x)+n^2)$.
}
 \end{th}
 Using our notations the above theorem implies.
 \begin{th}
{\sl
Let $G=(V,E)$ be co-strongly pseudo-transitive. The maximum weighted independent set  can be computed in $O(n^3)$.
}
 \end{th}

The above theorem  implies the following general result.
\begin{th}
{\sl
Let $G=(V,E)$ be one of the following graphs $(i)$ incomparability  $(ii)$ overlap , $(iii)$ chordal, $(iii)$ polygon circle $(iv)$ interval filament $(v)$, or,
$(vi)$ intersection graph half segments,  $(vii)$ intersection  graph axis parallel rectangles intersected by a diagonal line. Then,   the maximum weighted independent set  can be computed in $O(n^3)$.
}
 \end{th}

Note that  our  general frame work  extends the work of  Lubiw
 \cite{Lu} who showed the weighted maximum independent set of rectangles all which  have their right most corner on a line  can be computed in  $O(n^3)$ time, but gives  weaker result than a  more recent work of  Correa, Feuilloley,Perez-Lantero ,  Soto
 \cite{CFP} that had  $O(n^2)$  time complexity.

config: arxiv


text:
\begin{document}

\title{Majorization and Spherical Functions}

\author{Colin McSwiggen and Jonathan Novak}

\begin{abstract}
In this paper, we generalize a result of Cuttler, Greene, Skandera, and Sra that characterizes the majorization order
on Young diagrams in terms of nonnegative specializations of Schur polynomials. More precisely,
we introduce a generalized notion of majorization associated to an arbitrary crystallographic root system $\Phi,$ and show that it admits a natural characterization in terms of the values of spherical functions on any Riemannian symmetric space with restricted root system $\Phi.$  We also conjecture a further generalization of this theorem in terms of Heckman--Opdam hypergeometric functions.
\end{abstract}

\maketitle

\section{Introduction}
Given a positive integer $d$ and a pair of Young diagrams $\lambda,\mu \vdash d,$ we write $\lambda \succeq \mu$ if,
for any $r \geq 1,$ the number of cells in the first $r$ rows of $\lambda$ is at least as large as the number of cells in the
first $r$ rows of $\mu.$ This relation --- which is known as \emph{majorization} --- defines a partial order on the set of Young diagrams with
$d$ cells. Given a Young diagram $\lambda$ and a positive integer $N,$
a Young tableau of shape $\lambda$ and rank $N$ is a function $T$ on the cells of $\lambda$ which takes values in
$\{1,\dots,N\}.$ We say that $T$ is \emph{semistandard} if it is weakly increasing along rows and strictly increasing along
columns. If $\lambda \vdash d \leq N,$ then the set $\mathrm{SSYT}(\lambda,N)$ of semistandard Young tableaux of shape $\lambda$
and rank $N$ is nonempty, and the \emph{normalized} Schur polynomials

	\begin{equation*}
		S_\lambda(x_1,\dots,x_N) = \frac{1}{|\mathrm{SSYT}(\lambda,N)|} \sum_{T \in \mathrm{SSYT}(\lambda,N)}
		\prod_{j=1}^N x_j^{|T^{-1}(j)|}, \qquad \lambda \vdash d,
	\end{equation*}

\noindent
form a basis of the space of homogeneous symmetric polynomials of degree $d$ in $N$ variables.
The starting point of this paper is
a result of Cuttler--Greene--Skandera \cite{CGS} and Sra \cite{Sra},\footnote{Ait-Haddou and Mazure have also given a different proof of this theorem via the theory of blossoms \cite{AH-M}.} which states that the polynomials $S_\lambda$ characterize the majorization order in the following sense.

	\begin{theorem}
	\label{thm:CGSS}
	For any $\lambda,\mu \vdash d \leq N,$ we have $\lambda \succeq \mu$ if and only if

		\begin{equation*}
			S_\lambda(x_1,\dots,x_N) \geq S_\mu(x_1,\dots,x_N) \quad \textrm{for all } \, x_1,\dots,x_N \in \mathbb{R}_{\geq 0}.
		\end{equation*}
	\end{theorem}

Quite recently, Khare and Tao \cite{KhTao, KhTao2} have provided an analytic
extension of Theorem \ref{thm:CGSS} by showing that the functions $S_\lambda$ can also be used to
characterize \emph{weak} majorization, i.e.~the preorder obtained by dropping the condition $|\lambda|=|\mu|$ in
the definition of majorization. The present paper provides a geometric generalization of Theorem \ref{thm:CGSS}:
we consider a new notion of majorization associated to the Weyl group of a given root system\footnote{In this paper all root systems are assumed to be crystallographic, but not necessarily reduced.} $\Phi$, and show that it is characterized by a pointwise inequality
for spherical functions on any Riemannian symmetric space with restricted root system $\Phi$.

The paper is organized as follows.

In Section \ref{sec:majorization}, we introduce the notion of Weyl group majorization and prove our main result in the special
case of spherical functions on the Lie algebra $\gog$ of a compact group $G$ (Theorem \ref{thm:H-W-convexity}).  We treat this case separately
because spherical functions reduce to Harish-Chandra orbital integrals in this setting, leading to a very natural and direct
generalization of Theorem \ref{thm:CGSS}. Moreover, the proofs in the Lie algebra case do not require a discussion of symmetric spaces,
and are thus somewhat more elementary.

In Section \ref{sec:symspaces}, we treat the general case of spherical functions on a Riemannian symmetric space of
non-compact type, and prove our main result (Theorem \ref{thm:spherical-majorization}).
We then use this theorem to deduce majorization-characterizing inequalities for spherical functions on symmetric spaces of
Euclidean type (Proposition \ref{prop:euclidean-majorization}) and compact type (Proposition \ref{prop:compact-majorization}).
Furthermore, we discuss how the result for the compact case implies inequalities
for various families of orthogonal polynomials, such as Schur polynomials.

In Section \ref{sec:conjecture}, we develop an even more general framework based on
Heckman--Opdam hypergeometric functions \cite{RSHF1}.  We state a conjectural characterization of majorization in this context,
and prove one direction of this conjecture. Moreover, we show that the full conjecture holds in rank one, where it reduces to an
inequality for the classical Gauss hypergeometric function.

\section{Lie Algebras}
\label{sec:majorization}

Let $G$ be a connected, compact Lie group with Lie algebra $\gog$.  Let $T \subset G$ be a maximal torus, $\tot = \mathrm{Lie}(T) \subset \gog$ the corresponding Cartan subalgebra, and $\Phi$ the root system of $\gog$ with respect to $\tot$.  Fix a choice of positive roots $\Phi^+$, and let $W$ be the Weyl group generated by reflections in the root hyperplanes in $\tot$.

\begin{definition} \label{def:W-majorization} \normalfont
Let $V$ be any vector space on which $W$ acts by reflections, and let $\lambda, \mu \in V$.  We say that $\lambda$ $W$-{\it majorizes} $\mu$, written $\lambda \succeq \mu$, if $\mu$ lies in the convex hull of the Weyl orbit of $\lambda$.
A function $F: V \to \R$ is said to be $W$-{\it convex} if $F(\lambda) \ge F(\mu)$ whenever $\lambda \succeq \mu$.
\end{definition}

The relation $\succeq$ defines a preorder on $\tot$ and a partial order on each
Weyl chamber.\footnote{The $W$-majorization preorder is not the same as the height partial order on $\tot$.  If $\lambda, \mu \in \tot$, we say that $\lambda$ is {\it higher} than $\mu$ if $\lambda - \mu$ can be written
as a linear combination of positive roots with nonnegative coefficients. The resulting order coincides with $W$-majorization when $\lambda$ and $\mu$ are both dominant, but the height partial order is not $W$-invariant.}
When $G = \mathrm{U}(N),$ so that $W \cong S_N$ and $\tot \cong \R^N$, $W$-majorization coincides with the usual majorization order on vectors, and $W$-convexity coincides with the widely studied notion of Schur-convexity.  In particular, we recover the ordering on Young diagrams by regarding them as vectors with weakly decreasing integer coordinates.
Generalized majorization orders associated to group actions have been studied since the 1960's; see \cite{AOA,EP, GW, Mudh1}.

In this section, we prove that $W$-majorization may be characterized by comparing the pointwise behavior of Laplace transforms of invariant probability measures on coadjoint orbits of $G$.
Concretely, choose an invariant inner product $\langle \cdot,\cdot \rangle$ identifying $\gog \cong \gog^*$, and for $\lambda \in \gog$ let $\mathcal{O}_\lambda = \{ \mathrm{Ad}_g \lambda \ | \ g \in G \}$ denote its (co)adjoint orbit.
Define
\begin{equation} \label{eqn:L-def}
L_{\lambda}(x) = \int_{\mathcal{O}_\lambda} e^{\langle y,x \rangle} dy = \int_G e^{\langle \mathrm{Ad}_g \lambda, x \rangle} \, dg, \qquad \lambda, x \in \tot_\C,
\end{equation}
where $dy$ is the unique invariant probability measure on $\mathcal{O}_\lambda$, $dg$ is the Haar probability measure on $G$, and $\tot_\C \cong \tot \oplus i \tot$ is a
Cartan subalgebra of the complexified Lie algebra $\gog_\C$.

The functions $L_{\lambda}(x)$ are ubiquitous objects that arise in many different areas of mathematics and physics.  They were originally studied by Harish-Chandra in the context of harmonic analysis on Lie algebras \cite{HC},
and they play an important role in the orbit method in representation theory \cite{AK}.  When $G = \U(N)$, the transform $L_\lambda(x)$ is known
as the Harish-Chandra--Itzykson--Zuber (HCIZ) integral; it has been widely studied in theoretical physics and random matrix theory since the 1980's \cite{IZ}.  More recently, the HCIZ integral
has become an important object in combinatorics \cite{GGN,Novak:New} and probability \cite{BGH,Novak:JSP}.
For further background on these functions and their diverse applications, we refer the reader to \cite{McS1, McS2}.

The main result of this section is the following characterization theorem.

\begin{theorem} \label{thm:H-W-convexity}
For any $\lambda, \mu \in \tot$, the following are equivalent:
\begin{enumerate}
\item $\lambda \succeq \mu$,
\item $L_\lambda(x) \ge L_\mu(x)$ for all $x \in \tot$.
\end{enumerate}
\end{theorem}

\begin{proof}
We first show (ii) implies (i), by proving the contrapositive.  The {\it discriminant} of $\gog$ is the polynomial $\Delta_\gog(x) = \prod_{\alpha \in \Phi^+} \langle \alpha, x \rangle$, i.e.~the product of the positive roots.\footnote{Here we take the roots to be real-valued linear functionals in $\tot^*$, which we identify with $\tot$ via the inner product.  As a result, our roots differ by a factor of $i$ from those typically used in the setting of complex semisimple Lie algebras.}  Let $x \in \tot$ with $\Delta_\gog(x) \not = 0$.  We assume for now that $\Delta_\gog(\lambda), \Delta_\gog(\mu) \not = 0$ as well; later we will remove this assumption.  The Laplace transform (\ref{eqn:L-def}) admits an exact expression, due to Harish-Chandra \cite{HC}:
\begin{equation} \label{eqn:hc}
L_\lambda(x) = \frac{\Delta_\gog(\rho)}{\Delta_\gog(\lambda) \Delta_\gog(x)} \sum_{w \in W} \epsilon(w) e^{\langle w(\lambda), x \rangle},
\end{equation}
where $\rho = \frac{1}{2} \sum_{\alpha \in \Phi^+} \alpha$ and $\epsilon(w)$ is the sign of $w \in W$.  Taking $t > 0$ and using (\ref{eqn:hc}), we can write
\begin{equation} \label{eqn:first-H-diff}
L_\mu(tx) - L_\lambda(tx) = \frac{\Delta_\gog(\rho)}{\Delta_\gog(tx)} \sum_{w \in W} \epsilon(w) \left( \frac{e^{t \langle w(\mu), x \rangle}}{\Delta_\gog(\mu)} - \frac{e^{t \langle w(\lambda), x \rangle}}{\Delta_\gog(\lambda)} \right).
\end{equation}
This expression is manifestly $W$-invariant in $\lambda$, $\mu$ and $x$, so we may assume without loss of generality that all three are dominant.  Then as $t \to +\infty$ we have:
\begin{equation} \label{eqn:H-asymp}
L_\mu(tx) - L_\lambda(tx) = \frac{\Delta_\gog(\rho)}{\Delta_\gog(tx)} \left( \frac{e^{t \langle \mu, x \rangle}}{\Delta_\gog(\mu)} - \frac{e^{t \langle \lambda, x \rangle}}{\Delta_\gog(\lambda)} \right) + (\textrm{lower-order terms}).
\end{equation}
Now suppose $\lambda \not \succeq \mu$.  Then $\mu$ lies outside the convex hull of the $W$-orbit of $\lambda$, so by the hyperplane separation theorem there is some $x_0 \in \tot$ and $C > 0$ such that $\langle \mu, x_0 \rangle > C$ while $\langle w(\lambda), x_0 \rangle < C$ for all $w \in W$.  By making a small perturbation to $x_0$ if necessary, we can ensure that $\Delta_\gog(x_0) \not = 0$.  Take $x$ in (\ref{eqn:H-asymp}) to be the dominant representative of the Weyl orbit of $x_0$.  Then we still have $\langle \mu, x \rangle > C$, $\langle \lambda, x \rangle < C$, and from (\ref{eqn:H-asymp}) we find:
$$ \lim_{t \to \infty} \Big[ L_\mu(tx) - L_\lambda(tx)  \Big] \ge \lim_{t \to \infty} \frac{\Delta_\gog(\rho)}{\Delta_\gog(tx)} \left( \frac{e^{t \langle \mu, x \rangle}}{\Delta_\gog(\mu)} - \frac{e^{t C}}{\Delta_\gog(\lambda)} \right) = \infty, $$
which implies $L_\mu(tx) > L_\lambda(tx)$ for some $t > 0$, so that (ii) cannot hold.

Now we remove the assumption that $\Delta_\gog(\lambda), \Delta_\gog(\mu) \not = 0$.  In this case the expression (\ref{eqn:first-H-diff}) may be singular, so we instead take a limit:
\begin{equation} \label{eqn:singular-H-diff}
L_\mu(tx) - L_\lambda(tx) = \lim_{\eta \to 0} \frac{\Delta_\gog(\rho)}{\Delta_\gog(tx)} \sum_{w \in W} \epsilon(w) \left( \frac{e^{t \langle w(\mu + \eta \rho), x \rangle}}{\Delta_\gog(\mu + \eta \rho)} - \frac{e^{t \langle w(\lambda + \eta \rho), x \rangle}}{\Delta_\gog(\lambda + \eta \rho)} \right).
\end{equation}
To evaluate this limit, we apply l'H\^opital's rule as many times as needed, treating the $\lambda$ and $\mu$ terms separately.  After $j$ applications to the $\lambda$ terms and $k$ applications to the $\mu$ terms for some $j, k \ge 0$, in place of (\ref{eqn:H-asymp}) we find:
\begin{equation} \label{eqn:singular-H-asymp}
L_\mu(tx) - L_\lambda(tx) = \frac{\Delta_\gog(\rho)}{\Delta_\gog(tx)} \left( \frac{t^k \langle \rho, x \rangle^k e^{t \langle \mu, x \rangle}}{\partial_\rho^k \Delta_\gog(\mu)} - \frac{t^j \langle \rho, x \rangle^j e^{t \langle \lambda, x \rangle}}{\partial_\rho^j \Delta_\gog(\lambda)} \right) +\ (\textrm{lower-order terms}),
\end{equation}
where $\partial_\rho^k \Delta_\gog(\mu) = \frac{d^k}{d \eta^k} \Delta_\gog(\mu + \eta \rho) \big |_{\eta = 0}$. The remainder of the argument then goes through as before, and we conclude that (ii) implies (i).

The other direction of the proof, (i) implies (ii), amounts to showing that for all $x \in \tot$, the function \mbox{$\lambda \mapsto L_\lambda(x)$}
is $W$-convex.  This function is clearly $W$-invariant, and by \mbox{\cite[Theorem 1]{GW},} a $W$-invariant, convex function is $W$-convex.
It therefore remains only to show that $L_\lambda(x)$ is convex in $\lambda$, and for this it is sufficient to show midpoint convexity.  For $u, v \in \tot$ we have
\begin{multline*}
L_{\frac{1}{2}(u+v)}(x) = \int_{G} e^{ \langle \mathrm{Ad}_g (u + v)/2, x \rangle} dg =  \int_{G} \sqrt{e^{\langle \mathrm{Ad}_g u, x \rangle} e^{\langle \mathrm{Ad}_g v, x \rangle} } \,dg \\
\le \int_{G} \frac{1}{2}\big( e^{\langle \mathrm{Ad}_g u, x \rangle} + e^{\langle \mathrm{Ad}_g v, x \rangle} \big) \, dg = \frac{1}{2}L_u(x) + \frac{1}{2}L_v(x),
\end{multline*}
where in the final line we have applied the inequality of arithmetic and geometric means. This proves the theorem.
\end{proof}

\begin{remark} \normalfont
It is easily verified from the definition (\ref{eqn:L-def}) that $L_\lambda(x) = L_x(\lambda)$, so condition (ii) in Theorem \ref{thm:H-W-convexity} could equivalently be written: $$L_x(\lambda) \ge L_x(\mu) \textrm{ for all } x \in \tot.$$
\end{remark}

\section{Symmetric spaces}
\label{sec:symspaces}

This section contains our main results, which are majorization inequalities for spherical functions on Riemannian symmetric spaces.  After introducing some background on symmetric spaces and spherical functions, we state and prove separate inequalities for each of the three types of irreducible symmetric space.  In each case the theorem takes the form of an inequality between the pointwise values of any two spherical functions, which reflects the $W$-majorization order on the space of vectors that index the spherical functions.  As we explain below, these results imply Theorem \ref{thm:H-W-convexity} and discretizations
thereof, such as the Schur function inequality studied in \cite{CGS,Sra}.

\subsection{Background on symmetric spaces and spherical functions}
\label{sec:symspace-background}

Here we introduce only the minimum background required to state and prove the theorems.  We refer the reader to \cite[Appendices B and C]{OlPe} for a concise introduction to these topics, and to \cite{DS, GGA} for detailed references.  The definitions below mostly follow \cite[ch.~4]{GGA}

\begin{definition} \label{def:symspace} \normalfont
Let $G$ be a connected Lie group, and $K \subset G$ a compact subgroup.  We say that $(G, K)$ is a {\it symmetric pair} if $K$ is the fixed-point set of an involutive automorphism $\sigma: G \to G$.  For our purposes, a {\it Riemannian symmetric space} is a quotient $X = G/K$, where $(G, K)$ is a symmetric pair.  When $G$ is non-compact and semisimple with finite center, and $K$ is a maximal compact subgroup, we say that $X$ is of {\it non-compact type}.
\end{definition}

Below, the term ``symmetric space'' always means a Riemannian symmetric space as defined above.

\begin{definition} \label{def:spherical-funcs} \normalfont
Let $X = G/K$ be a Riemannian symmetric space, and write $[g] \in X$ for the image of $g \in G$ under the quotient map $G \to G/K$.  Let $\mathcal{D}(X)$ be the algebra of differential operators on $X$ that are invariant under all translations $[x] \mapsto [gx]$, $g \in G$.  A complex-valued function $\phi \in C^\infty(X)$ is called a {\it spherical function} if all of the following hold:
\begin{enumerate}
\item $\phi([\mathrm{id}]) = 1$,
\item $\phi([kx]) = \phi([x])$ for all $k \in K$,
\item $D \phi = \gamma_D \phi$ for each $D \in \mathcal{D}(X)$, where $\gamma_D$ is some complex eigenvalue.
\end{enumerate}
\end{definition}

Spherical functions play a central role in the theory of harmonic analysis on symmetric spaces, and many important families of special functions can be realized as spherical functions on some symmetric space.

\begin{example} \label{ex:cpt-gp-symspace} \normalfont
Let $G$ be a compact connected Lie group, and $K \subset G \times G$ the diagonal subgroup.  Then $(G \times G, K)$ is a symmetric pair, and we can identify $(G \times G)/K \cong G$ via $(g_1, g_2) K \mapsto g_1 g_2^{-1}$.  The spherical functions on $G$ are precisely the functions of the form $$\phi_\lambda(g) = \frac{\chi_\lambda(g)}{\dim V_\lambda},$$ where $V_\lambda$ is the irreducible representation of $G$ with highest weight $\lambda$, and $\chi_\lambda$ is its character.
\end{example}

\begin{example} \label{ex:alg-spherical-funcs} \normalfont
Let $G$ again be a compact connected Lie group.  If we regard its Lie algebra $\gog$ as an abelian Lie group, we can form the semidirect product $G \ltimes \gog$ with multiplication $(g_1, x_1) \cdot (g_2, x_2) = (g_1 g_2, \, \mathrm{Ad}_{g_1} x_2 + x_1)$.  Then $(G \ltimes \gog, G)$ is a symmetric pair, and we can identify $(G \ltimes \gog)/G \cong \gog$ via $(g, x) \mapsto \mathrm{Ad}_g x$.  Thus $\gog$ is a symmetric space, and the spherical functions on $\gog$ reduce to the Laplace transforms studied in Section \ref{sec:majorization},
$$L_{\lambda}(x) = \int_G e^{\langle \mathrm{Ad}_g \lambda, x \rangle} \, dg, \qquad x \in \gog, \quad \lambda \in \tot_\C,$$
where $\tot_\C$ is the complexification of a Cartan subalgebra $\tot \subset \gog$.
\end{example}

If $X$ is a symmetric space then its universal cover $\tilde X$ is also symmetric, and the spherical functions on $X$ may be identified with spherical functions on $\tilde X$ that are constant on the fibers of the covering map.  In this sense the spherical functions on $\tilde X$ subsume those on $X$, so that in what follows we may assume without loss of generality that $X$ is simply connected.  We say that $X$ is {\it irreducible} if it cannot be written as a nontrivial product of symmetric spaces.  A simply connected, irreducible symmetric space is always:
\renewcommand{\labelenumi}{(\arabic{enumi})}
\begin{enumerate}
\item of non-compact type; or,
\item a Euclidean space; or,
\item compact.
\end{enumerate}
\renewcommand{\labelenumi}{(\roman{enumi})}
These three types correspond respectively to the cases in which $X$ is negatively curved, flat, or positively curved.  There is a a well-known correspondence between the three types, which we now describe.  If $X^- = G/K$ is a symmetric space of non-compact type, $\sigma : G \to G$ is the associated involution fixing $K$, and $\gog = \mathrm{Lie}(G)$, then we have the Cartan decomposition $\gog = \mathfrak{k} + \mathfrak{p}$, where $\mathfrak{k} = \mathrm{Lie}(K)$ is the fixed-point set of $d \sigma$.  From these data we can construct both a Euclidean symmetric space and a compact symmetric space.  First define $\gog^+ = \mathfrak{k} + i \mathfrak{p} \subset \gog_\C$, which is the Lie algebra of the compact real form $G^+$ of $G$.  The symmetric space $X^+ = G^+/K$ is obviously compact.  Next define the algebra $\gog^0$, which is equal to $\gog$ as a vector space but is endowed with a different Lie bracket $[ \cdot, \cdot ]_0$ defined by
$$[x, y]_0 = \begin{cases}0, & x, y \in \mathfrak{p}, \\ [x,y], & \textrm{otherwise.} \end{cases}$$
Then the group $G^0 = \exp(\gog^0) \cong K \ltimes \mathfrak{p}$ acts on $\mathfrak{p}$ by affine transformations, $(k, p) \cdot x = \mathrm{Ad}_k x + p$, and $X^0 = G^0 / K \cong \mathfrak{p}$ is a Euclidean symmetric space.

Thus we have constructed a triple of symmetric spaces $(X^-, X^0, X^+)$ that belong respectively to the three types listed above.  Moreover, every simply connected, irreducible symmetric space occurs in such a triple.  In the following subsections, we study spherical functions on the spaces $X^-$, $X^0$, and $X^+$.

\subsection{Symmetric spaces of non-compact type}

When $X^- = G/K$ is a symmetric space of non-compact type, the spherical functions admit a convenient integral representation, due to Harish-Chandra \cite{HC2, HC3}.  The version that we use here is proved in \cite[ch.~4, Theorem 4.3]{GGA}.  Let $G = NAK$, $\gog = \mathfrak{n} + \mathfrak{a} + \mathfrak{k}$ be the Iwasawa decompositions of $G$ and $\gog$.  For $g \in G$, let $a(g)$ be the unique element of $\mathfrak{a}$ such that $g \in N e^{a(g)} K$. The Killing form $\langle \cdot, \cdot \rangle$ on $\gog$ restricts to an inner product on $\mathfrak{a}$.  For $\alpha \in \mathfrak{a}$, define $$\gog_\alpha = \{ \ x \in \gog \ | \ [h, x] = \langle \alpha, h \rangle x \ \textrm{for all} \ h \in \mathfrak{a} \ \}.$$
The {\it restricted root system} $\Phi$ of $X^-$ consists of all nonzero $\alpha \in \mathfrak{a}$ for which $\gog_\alpha$ is nontrivial.  Fix a choice $\Phi^+$ of positive roots, and let $W$ be the Weyl group generated by reflections in the root hyperplanes.  For $\lambda, \mu \in \mathfrak{a}$, we again write $\lambda \succeq \mu$ to indicate that $\lambda$ $W$-majorizes $\mu$.  For $\alpha \in \Phi$, define $m_\alpha = \dim \gog_\alpha$, and set $\rho = \frac{1}{2} \sum_{\alpha \in \Phi^+} m_\alpha \alpha$.  Write $dk$ for the normalized Haar measure on $K$.

\begin{theorem}[Harish-Chandra] \label{thm:hc-integral-spherical}
The spherical functions on $X^-$ are exactly the functions of the form
\begin{equation} \label{eqn:hc-integral-spherical}
\phi^-_\lambda([g]) = \int_K e^{\langle i \lambda + \rho, a(kg) \rangle} dk, \qquad g \in G,
\end{equation}
as $\lambda$ ranges over $\mathfrak{a}_\C$. Moreover, two such functions $\phi^-_\lambda$ and $\phi^-_\mu$ are identical if and only if $\mu = w(\lambda)$ for some $w \in W$.
\end{theorem}

The following theorem is the main result of this paper.

\begin{theorem} \label{thm:spherical-majorization}
Let $X^- = G/K$ be a Riemannian symmetric space of non-compact type. For any $\lambda, \mu \in \mathfrak{a}$, the following are equivalent:
\begin{enumerate}
\item $\lambda \succeq \mu$,
\item $\phi^-_{i \lambda}(x) \ge \phi^-_{i \mu}(x)$ for all $x \in X$.
\end{enumerate}
\end{theorem}

\begin{proof}
The argument generalizes the proof of Theorem \ref{thm:H-W-convexity}.  We first show that (ii) implies (i) by proving the contrapositive, and then that (i) implies (ii) using the integral representation (\ref{eqn:hc-integral-spherical}) for the spherical functions.

Suppose $\lambda \not \succeq \mu$.  Since the map $\lambda \mapsto -\lambda$ is an isometry of $\mathfrak{a}$, we have $\lambda \succeq \mu$ if and only if $- \lambda \succeq - \mu$.  Accordingly, to prove that (ii) implies (i), it suffices to show that $\phi^-_{- i \mu}(x) > \phi^-_{- i \lambda}(x)$ for some $x \in X$.  By hyperplane separation, we can obtain $y \in \mathfrak{a}$ and $C_1 > 0$ such that $\langle \mu, y \rangle > C_1$ and $\langle w(\lambda), y \rangle < C_1$ for all $w \in W$.  Clearly both of these inequalities still hold if we replace $y$ with the dominant representative of its Weyl orbit, and by Theorem \ref{thm:hc-integral-spherical} we have $\phi^-_{i \lambda} = \phi^-_{i w(\lambda)}$ for $w \in W$.  Therefore without loss of generality we may take all three of $\lambda$, $\mu$ and $y$ to be dominant.

With these assumptions, we will study the asymptotic behavior of the spherical functions $\phi^-_{- i \lambda}$ and $\phi^-_{- i \mu}$ at infinity.  This topic is well understood; see e.g.~\cite{Duis-asymp}.  In particular we have the following sharp estimate as $t \to +\infty$, which also follows directly from (\ref{eqn:symspace-HGF}) and (\ref{eqn:HGF-asymp}) below:
\begin{equation} \label{eqn:spherical-asymp}
\phi^-_{- i \lambda}([e^{ty}]) \ \asymp \ e^{t \langle \lambda - \rho, \, y \rangle} \prod_{\alpha \in \Phi^+_\lambda} (1 + 2 t \langle \alpha, y \rangle ),
\end{equation}
where
\begin{equation} \label{eqn:phi-plus-lambda}
\Phi^+_\lambda = \Big \{ \ \alpha \in \Phi^+ \ \Big | \ \frac{1}{2} \alpha \not \in \Phi^+, \ \langle \alpha, \lambda \rangle = 0  \ \Big \}.
\end{equation}
Here the notation $f(t) \asymp g(t)$ means that there exist constants $c, C, T > 0$ such that $c g(t) < f(t) < Cg(t)$ for all $t > T$.  Thus the estimate (\ref{eqn:spherical-asymp}) implies that
$$\phi^-_{- i \mu}([e^{ty}]) - \phi^-_{- i \lambda}([e^{ty}]) \ > \ e^{-t \langle \rho, y \rangle} \bigg(C_2 \, e^{t \langle \mu, y \rangle} - C_3 \, e^{tC_1} \prod_{\alpha \in \Phi^+_\lambda} (1 + 2 t \langle \alpha, y \rangle ) \bigg)$$
for large $t$ and some constants $C_2, C_3 > 0$.  For $t$ sufficiently large, the quantity on the right-hand side above is positive, proving that $\phi^-_{- i \mu}(x) > \phi^-_{- i \lambda}(x)$ for some $x \in X$, as desired.

We next prove that (i) implies (ii). It suffices to show that the function $f_x(\lambda) = \phi^-_{i \lambda}(x)$ is $W$-convex.  As in the proof of Theorem \ref{thm:H-W-convexity}, we use the result of \cite[Theorem 1]{GW}, which states that a $W$-invariant, convex function is $W$-convex.  By Theorem \ref{thm:hc-integral-spherical}, $f_x$ is $W$-invariant, so we need only prove that $f_x$ is convex, for which it suffices to check midpoint convexity.  Write $x = [g]$ for some $g \in G$.  Using the integral representation (\ref{eqn:hc-integral-spherical}) and the inequality of arithmetic and geometric means, we find:
\begin{align*}
f_{x} \bigg(\frac{1}{2}(\lambda + \mu) \bigg) &= \int_K e^{\langle \rho - (\lambda + \mu)/2, \, a(kg) \rangle} dk \\
&=  \int_K e^{\langle \rho, a(kg) \rangle} \sqrt{ e^{- \langle \lambda, a(kg) \rangle} e^{- \langle \mu, a(kg) \rangle} } \, dk \\
& \ge \frac{1}{2} \int_K e^{\langle \rho, a(kg) \rangle} ( e^{- \langle \lambda, a(kg) \rangle} + e^{- \langle \mu, a(kg) \rangle} ) \, dk \\
&= \frac{1}{2} \big( f_x(\lambda) + f_x(\mu) \big),
\end{align*}
which shows that $f_x$ is convex, completing the proof.
\end{proof}

\begin{remark} \label{rem:bounded-phi} \normalfont
There are parallels between Theorem \ref{thm:spherical-majorization} and a celebrated result of Helgason and Johnson \cite{HJ}, which classifies the bounded spherical functions on $X^-$.  Write $\mathrm{Re} \lambda,\, \mathrm{Im} \lambda \in \mathfrak{a}$ for the real and imaginary parts of $\lambda \in \mathfrak{a}_\C$.  Although Helgason and Johnson do not use the terminology of $W$-majorization, their theorem states that $\phi^-_\lambda$ is bounded if and only if $\rho \succeq \mathrm{Im} \lambda.$  More recently, this result has been generalized to a classification of bounded Heckman--Opdam hypergeometric functions \cite{NPP}.

Theorem \ref{thm:spherical-majorization} and the Helgason--Johnson theorem are independent but related.  The boundedness of $\phi^-_\lambda$ when $\rho \succeq \mathrm{Im} \lambda$ follows from Theorem \ref{thm:spherical-majorization} once one observes from the integral formula (\ref{eqn:hc-integral-spherical}) that $|\phi^-_\lambda| \le \phi^-_{i \, \mathrm{Im} \lambda}$ and that $\phi^-_{i \rho} \equiv 1.$  On the other hand, Theorem \ref{thm:spherical-majorization} by itself does not imply that all other $\phi^-_\lambda$ are unbounded (though this can be deduced from the estimate (\ref{eqn:spherical-asymp})), while the Helgason--Johnson theorem does not tell us that $W$-majorization actually induces a partial order on {\it all} $\phi^-_\lambda$ with $\lambda \in i \mathfrak{a}$.
\end{remark}

\subsection{Euclidean symmetric spaces}

The spherical functions on the Euclidean symmetric space $X^0 \cong \mathfrak{p}$ are precisely the functions
\begin{equation} \label{eqn:spherical-typeI}
\phi^0_\lambda(x) = \lim_{\varepsilon \to 0} \phi^-_{\lambda / \varepsilon}([e^{\varepsilon x}]) = \int_K e^{i \langle \lambda, \mathrm{Ad}_k x \rangle} dk, \qquad x \in \mathfrak{p},
\end{equation}
as $\lambda$ ranges over $\mathfrak{a}_\C$; see \cite[ch.~4, Proposition 4.8]{GGA}.  Taking the limit (\ref{eqn:spherical-typeI}) in the proof of Theorem \ref{thm:spherical-majorization}, we obtain the following.

\begin{proposition} \label{prop:euclidean-majorization}
Let $X^0$ be a Euclidean symmetric space.  For any $\lambda, \mu \in \mathfrak{a}$, the following are equivalent:
\begin{enumerate}
\item $\lambda \succeq \mu$,
\item $\phi^0_{i \lambda}(x) \ge \phi^0_{i \mu}(x)$ for all $x \in X$.
\end{enumerate}
\end{proposition}

In particular, Theorem \ref{thm:H-W-convexity} is a special case of Proposition \ref{prop:euclidean-majorization}, corresponding to the Euclidean symmetric space described in Example \ref{ex:alg-spherical-funcs}.

\subsection{Compact symmetric spaces} \label{sec:cpt-sym}

We now consider the compact symmetric space $X^+ = G^+/K$.  Let $V_\lambda$ be the irreducible $G^+$-representation with highest weight $\lambda$, and $\chi_\lambda$ its character.  If $V_\lambda$ contains a nontrivial $K$-fixed vector, we say that $V_{\lambda}$ is a {\it spherical} representation and $\lambda$ is a spherical highest weight.  By \cite[ch.~4, Theorem 4.2]{GGA}, the spherical functions on $X^+$ are precisely the functions
\begin{equation} \label{eqn:cpt-spherical}
\phi^+_\lambda([g]) = \int_K \chi_\lambda(g^{-1}k) \, dk, \qquad g \in G^+,
\end{equation}
where $\chi_\lambda$ is the character of an irreducible spherical representation of $G^+$.

Here we depart in two ways from the conventions used above in Section \ref{sec:majorization}.  First, we now use the notation $\langle \cdot, \cdot \rangle$ to indicate the Killing form, which restricts to a {\it negative}-definite form on $\gog^+$ rather than an inner product.  Second, we now regard the roots and weights of $G^+$ as {\it imaginary}-valued linear functionals on a Cartan subalgebra $\tot \subset \gog^+$ with $i \mathfrak{a} \subset \tot$.  We then use the Killing form to identify the weights and roots with elements of $i \tot$.

With these conventions, the spherical highest weights of $G^+$ correspond to certain lattice points in $\mathfrak{a} \subset i \tot$; see \cite[ch.~5 \textsection 4]{GGA}.  By \cite[ch.~5, Theorem 4.1 and Corollary 4.2]{GGA}, if $G^+$ is simply connected and semisimple then the spherical highest weights are exactly those $\lambda \in \mathfrak{a}$ satisfying
\begin{equation} \label{eqn:lambda-reqs}
\frac{\langle \lambda, \alpha \rangle}{\langle \alpha, \alpha \rangle} \in \Z_{\ge 0} \quad \textrm{for all } \alpha \in \Phi^+,
\end{equation}
where $\Phi^+$ are the positive restricted roots of $X^-$.  Here as well, given $\lambda, \mu \in \mathfrak{a}$, we write $\lambda \succeq \mu$ to indicate that $\lambda$ $W$-majorizes $\mu$, where $W$ is the Weyl group of the {\it restricted} root system of $X^-$ (rather than the root system of $G^+$).

The function $\phi^+_\lambda$ can be analytically continued to the complexification $G_\C$, so that we may evaluate $\phi^+_\lambda([e^x])$ for any $x \in \tot_\C$.  We then have the following majorization inequality.

\begin{proposition} \label{prop:compact-majorization}  Let $\lambda, \mu \in \mathfrak{a}$ be two spherical highest weights of $G^+$. The following are equivalent:
\begin{enumerate}
\item $\lambda \succeq \mu$,
\item $\phi^+_\lambda([e^{ix}]) \ge \phi^+_\mu([e^{ix}])$ for all $x \in \tot$.
\end{enumerate}
\end{proposition}

\begin{proof}
Consider the spherical function $\phi^-_{-i(\lambda - \rho)}$ on $X^-$, regarded as a function on the non-compact group $G$.  When $\lambda$ is a spherical highest weight, this function also admits an analytic continuation to $G_\C$, which coincides with $\phi^+_\lambda$; see \cite[\textsection 4]{LV}.  Since $\tot = \tot \cap \mathfrak{k} + i \mathfrak{a}$ and $[e^{y + x}] = [e^x] \in X^+$ for $y \in \tot \cap \mathfrak{k}$, we can take $x \in i \mathfrak{a}$, so that $e^{ix} \in G$.  The desired result is then immediate from Theorem \ref{thm:spherical-majorization}.
\end{proof}

\subsection{Application to orthogonal polynomials}
Let us explain how Proposition \ref{prop:compact-majorization} implies the results of \cite{CGS,Sra} relating majorization and Schur polynomials, which we stated above in Theorem \ref{thm:CGSS}.  Young diagrams with $N$ rows index the irreducible polynomial representations of $\U(N)$.  If $\lambda$ is a Young diagram and $V_\lambda$ is the corresponding irreducible representation, we can identify $\R^N$ with a Cartan subalgebra in $\mathfrak{u}(N)$ such that
\begin{equation} \label{eqn:schur-char}
S_\lambda(e^{iy_1}, \hdots, e^{iy_N}) = \frac{\chi_\lambda(e^y)}{\dim V_\lambda}, \qquad y = (y_1, \hdots, y_N) \in \R^N.
\end{equation}
If we then regard the group $\U(N)$ as a compact symmetric space as in Example \ref{ex:cpt-gp-symspace}, we find
\begin{equation} \label{eqn:spherical-schur}
\phi^+_\lambda([e^{iy}]) = S_\lambda(e^{y_1}, \hdots, e^{y_N}),
\end{equation}
that is, in an appropriate choice of coordinates, the spherical functions are normalized Schur polynomials.  Writing $x_i = e^{y_i}$, Proposition \ref{prop:compact-majorization} then yields Theorem \ref{thm:CGSS} under the stricter assumption that all
$x_1, \hdots, x_N > 0$.  Since Schur polynomials are continuous, we can relax this to $x_1, \hdots, x_N \ge 0$, which proves Theorem \ref{thm:CGSS} in full.  A related characterization of \emph{weak majorization} in terms of Schur polynomials was recently obtained by Khare and Tao in \cite{KhTao}.

Schur polynomials are not unique in this regard.  Many families of orthogonal polynomials, such as the real and quaternionic zonal polynomials, can be realized as spherical functions on compact symmetric spaces.  In fact, Vretare \cite{LV} showed that {\it every} compact symmetric space gives rise to an associated family of orthogonal polynomials, which express the spherical functions via a relation similar to (\ref{eqn:spherical-schur}).  In all such cases, Proposition \ref{prop:compact-majorization} gives an inequality for the orthogonal polynomials that is analogous to Theorem \ref{thm:CGSS}.

\begin{remark} \normalfont
One can also deduce Theorem \ref{thm:CGSS} directly from Theorem \ref{thm:H-W-convexity} by using the Kirillov character formula for compact groups \cite[ch.~5]{AK} to write the Schur polynomials in terms of integrals of the form (\ref{eqn:L-def}). Since the arguments in (\ref{eqn:L-def}) are not constrained to lie in the weight lattice, in the case $G=\U(N)$ Theorem \ref{thm:H-W-convexity} in fact entails an extension of Theorem \ref{thm:CGSS} to generalized Schur polynomials with non-integer exponents, which was previously observed by Khare and Tao \cite{KhTao2}.  Corresponding statements for the characters of other compact groups are also immediate from Theorem \ref{thm:H-W-convexity}.
\end{remark}

\section{Hypergeometric functions}
\label{sec:conjecture}

The Heckman--Opdam hypergeometric functions are a family of special functions associated to root systems, which generalize the classical Gauss hypergeometric function to higher dimensions.  They are eigenfunctions of the hyperbolic quantum Calogero--Sutherland Hamiltonian and were introduced in the paper \cite{RSHF1} in order to prove the complete integrability of quantum Calogero--Sutherland models.  Many special functions of interest can be expressed via limits or specializations of Heckman--Opdam hypergeometric functions, including the spherical functions on all Riemannian symmetric spaces of non-compact type.  Also in \cite{RSHF1}, Heckman and Opdam defined the multivariable Jacobi polynomials, now known as Heckman--Opdam polynomials.  These are closely related to hypergeometric functions and generalize numerous widely studied families of orthogonal polynomials, such as Schur and Jack polynomials.

In this final section, we conjecture that Heckman--Opdam hypergeometric functions satisfy a fundamental monotonicity property with respect to $W$-majorization.  If true, this conjecture would unify and generalize all of the majorization results discussed in this paper.  We prove one of the two directions of implication that comprise the conjecture, and we show that the full conjecture holds in rank one.

Just as Heckman--Opdam hypergeometric functions generalize the spherical functions $\phi^-_{\lambda}$ on different symmetric spaces of non-compact type, the Heckman--Opdam polynomials generalize of the functions $\phi^+_\lambda$, up to some differences in normalization.  Similarly, another related class of functions, the generalized Bessel functions, interpolate between the functions $\phi^0_\lambda$ on different Euclidean symmetric spaces.  If the conjecture is true, then analogous results hold for both generalized Bessel functions and Heckman--Opdam polynomials.  In particular, we show below that the conjecture would immediately imply an analogue for Heckman--Opdam polynomials of the Schur polynomial inequality proved in \cite{CGS,Sra}.

To define the Heckman--Opdam hypergeometric functions, we first must fix some preliminary data.  Here we largely follow the conventions of Anker \cite{AnkerDunklNotes} and Heckman and Schlichtkrul \cite{HS}.  Let $V \cong \R^r$ be a Euclidean space with inner product $\langle \cdot, \cdot \rangle$, $\Phi \subset V$ a (crystallographic) root system spanning $V$, and $W$ the Weyl group acting on $V$ by reflections in the root hyperplanes.  The Heckman--Opdam hypergeometric function $F_{k,\lambda}$ depends on a point $\lambda$ in the complexification $V_\C$, as well as on a {\it multiplicity parameter}, which is a function $k: \Phi \to \C$ such that $k_{w \cdot \alpha} = k_\alpha$ for $w \in W$.  Unless stated otherwise, we assume in what follows that $\lambda \in V$ and that all $k_\alpha$ are nonnegative real numbers.

We now define $F_{k,\lambda}$ in terms of solutions to certain differential-difference equations.  Fix a choice of positive roots $\Phi^+$.  For $\alpha \in \Phi^+$ let $s_\alpha$ be the reflection through the hyperplane $\{x \in V \ | \ \langle \alpha, x \rangle = 0 \},$ and define $\rho^{(k)} = \frac{1}{2} \sum_{\alpha \in \Phi^+} k_\alpha \alpha.$

\begin{definition} \label{def:cherednik-op} \normalfont
For $y \in V$, the \emph{Cherednik operator} $D_{k,y}$ is the differential-difference operator
\begin{equation}
D_{k,y} = \partial_y + \sum_{\alpha \in \Phi^+} \langle y, \alpha \rangle k_\alpha \frac{1}{1 - e^{-\alpha}} (1 - s_\alpha) - \langle y, \rho^{(k)} \rangle.
\end{equation}
\end{definition}

The Cherednik operators were originally defined and studied in \cite{Ch1, Ch2}. For details of their properties, we refer the reader to these papers as well as to \cite[\textsection 4]{AnkerDunklNotes} and \cite[\textsection 2]{Op}.  Here we need only the following fact: when all $k_\alpha$ are nonnegative, for any $\lambda \in V_\C$ there is a unique smooth function $G_{k,\lambda}$ on $V$ satisfying the system of differential-difference equations
\begin{equation} \label{eqn:opdam-HG-eqn}
D_{k,y} G_{k,\lambda} = \langle y, \lambda \rangle G_{k,\lambda} \quad \textrm{for all } y \in V
\end{equation}
and normalized so that $G_{k,\lambda}(0) = 1$.

\begin{definition} \label{def:hgf} \normalfont
For any nonnegative real multiplicity parameter $k$ and any $\lambda \in V_\C$, the {\it Heckman--Opdam hypergeometric function} $F_{k, \lambda}$ is defined as
\begin{equation} \label{eqn:hgf-def}
F_{k, \lambda}(x) = \frac{1}{|W|} \sum_{w \in W} G_{k,\lambda}(w(x)).
\end{equation}
\end{definition}

The functions $F_{k, \lambda}$ unify and interpolate between many widely studied special functions, as illustrated in the following examples.

\begin{example} \label{ex:rank1} \normalfont
In the 1-dimensional case where $V \cong \R$, the root system $\Phi$ can be either $A_1$ or $BC_1$.  For $BC_1$ there are two Weyl orbits $\{ \pm 1 \}$, $\{ \pm 2 \} \subset \R$, and the Heckman--Opdam hypergeometric function reduces to the Gauss hypergeometric function:
\begin{equation} \label{eqn:HO-to-Gauss}
F_{k, \lambda}(x) = {}_{2}F_1 \Big( \frac{k_1}{2} + k_2 + \lambda, \, \frac{k_1}{2} + k_2 - \lambda ; \, k_1 + k_2 + \frac{1}{2} ; \, - \sinh^2 \frac{x}{2} \Big).
\end{equation}
The Heckman--Opdam hypergeometric function for $A_1$ corresponds to the special case \mbox{$k_2 = 0$}.
\end{example}

\begin{example} \label{ex:symspace-HGF} \normalfont
Suppose $\Psi$ is the restricted root system of a symmetric space $X = G/K$ of non-compact type, and $m_\alpha = \dim \mathfrak{g}_\alpha$ for each $\alpha \in \Psi$.  Take $V = \mathfrak{a}$, $\Phi = \{ 2 \alpha \ | \ \alpha \in \Psi \}$ and $k_{2\alpha} = \frac{1}{2} m_{\alpha}$.  Then
\begin{equation} \label{eqn:symspace-HGF}
\phi^-_{\lambda}([e^x]) = F_{k, i \lambda }(x), \qquad x \in \mathfrak{a}, \quad \lambda \in \mathfrak{a}_\C.
\end{equation}
See \cite[\textsection 4]{AnkerDunklNotes}.
\end{example}

\begin{example} \label{ex:gen-bessel} \normalfont
The generalized Bessel function $J_{k, \lambda}$ on $V$ can be obtained as the {\it rational limit} of $F_{k,\lambda}$:
\begin{equation}
J_{k, \lambda}(x) = \lim_{\varepsilon \to 0} F_{k, \lambda / \varepsilon}(\varepsilon x).
\end{equation}
From the previous example and the relation (\ref{eqn:spherical-typeI}), it is clear that $J_{k, \lambda}$ generalizes the spherical functions on Euclidean symmetric spaces in the same way that $F_{k, \lambda}$ generalizes the spherical functions on symmetric spaces of non-compact type.  See \cite[\textsection 3 and \textsection 4.4]{AnkerDunklNotes} for details on generalized Bessel functions and the rational limit.
\end{example}

For any multiplicity parameter $k$, we define the function
\begin{equation} \label{eqn:delta-k-def}
\delta_k(x) = \prod_{\alpha \in \Phi^+} (e^{\langle \alpha, x \rangle/2} - e^{- \langle \alpha,x \rangle/2})^{k_\alpha}.
\end{equation}

\begin{example} \label{ex:HGF-to-L} \normalfont
When $\Phi$ is reduced, we can identify $V$ with a Cartan subalgebra $\tot$ of a compact semisimple Lie algebra $\gog$ with root system $\Phi$. We write $k = \vec 1$ for the multiplicity parameter with $k_\alpha = 1$ for all $\alpha \in \Phi$. Then
\begin{equation} \label{eqn:HGF-to-L}
F_{\vec 1, \lambda}(x) = \frac{\Delta_\gog(x)}{\delta_{\vec 1}(x)} L_{\lambda}(x), \qquad x \in \tot.
\end{equation}
\end{example}

The notion of $W$-majorization is defined in this setting just as in Definition \ref{def:W-majorization}.  We conjecture the following monotonicity property for Heckman--Opdam hypergeometric functions with respect to $W$-majorization.

\begin{conjecture} \label{conj:HGF-majorization}
Let $\lambda, \mu \in V$ and let $k$ be a nonnegative real multiplicity parameter.  The following are equivalent:
\begin{enumerate}
\item $\lambda \succeq \mu$,
\item $F_{k,\lambda}(x) \ge F_{k,\mu}(x)$ for all $x \in V$.
\end{enumerate}
\end{conjecture}

Here we show one half of the conjecture, namely that (ii) implies (i), using known sharp asymptotics for $F_{k,\lambda}$.  We then give an elementary proof of the conjecture in rank one, where it amounts to an inequality for the Gauss hypergeometric function.

\begin{proposition} \label{prop:HGF-majorization-onlyif}
Take $\lambda, \mu$ and $k$ as in Conjecture \ref{conj:HGF-majorization}.  If $F_{k,\lambda}(x) \ge F_{k,\mu}(x)$ for all $x \in V$, then $\lambda \succeq \mu$.
\end{proposition}

\begin{proof}
Again we show the contrapositive.  Suppose $\lambda \not \succeq \mu$, and again use hyperplane separation to obtain a $y \in V$ and $C_1 > 0$ such that $\langle \mu, y \rangle > C_1$ and $\langle w(\lambda), y \rangle < C_1$ for all $w \in W$.  Without loss of generality, we take $\lambda$, $\mu$ and $y$ to be dominant.  We have the following sharp asymptotic estimate, due to Schapira \cite[Remark 3.1]{SchapiraHGF} and Narayanan--Pasquale--Pusti \cite[Theorem 3.4]{NPP}:
\begin{equation} \label{eqn:HGF-asymp}
F_{k,\lambda}(ty) \ \asymp \ e^{t \langle \lambda - \rho^{(k)}, \, y \rangle} \prod_{\alpha \in \Phi^+_\lambda} (1 + t \langle \alpha, y \rangle )
\end{equation}
as $t \to +\infty,$ with $\Phi^+_\lambda$ as defined above in (\ref{eqn:phi-plus-lambda}) and $\asymp$ as defined immediately after. We thus find that
$$F_{k, \mu}(ty) - F_{k, \lambda}(ty) \ > \ e^{-t \langle \rho^{(k)}, \, y \rangle} \bigg( C_2 \, e^{t \langle \mu, y \rangle} - C_3 \, e^{t C_1} \prod_{\alpha \in \Phi^+_\lambda} (1 + t \langle \alpha, y \rangle ) \bigg)$$
for large $t$ and some constants $C_2, C_3 > 0$.  For $t$ sufficiently large, the quantity on the right-hand side above is positive, which implies that $F_{k,\lambda}(x) < F_{k,\mu}(x)$ for some $x \in V$, completing the proof.
\end{proof}

\begin{remark} \label{rem:HO-integral-formulae} \normalfont
As in the proof of Theorem \ref{thm:spherical-majorization}, to complete the proof of Conjecture \ref{conj:HGF-majorization} it suffices to check that the function $\lambda \mapsto F_{k,\lambda}(x)$ is midpoint-convex.  However, integral representations analogous to (\ref{eqn:hc-integral-spherical}) for general Heckman--Opdam hypergeometric functions are not known, so we cannot directly apply the same technique.  Although there are known integral expressions in certain cases where the multiplicity parameter does not correspond to a symmetric space (see e.g.~\cite{RoslerVoit, Sun}), these are more complicated than (\ref{eqn:hc-integral-spherical}) and have so far resisted a similar analysis. A more promising approach to a general proof of Conjecture \ref{conj:HGF-majorization} might be to use hypergeometric differential equations, as illustrated in the following proposition.  Another approach could be to analyze a series expansion for the hypergeometric function as in \cite{NPP}.
\end{remark}

\begin{proposition} \label{prop:HGF-rank1}
When $\dim V = 1$, Conjecture \ref{conj:HGF-majorization} is true.
\end{proposition}

\begin{proof}
In light of Proposition \ref{prop:HGF-majorization-onlyif}, we need only show that (i) implies (ii) in Conjecture \ref{conj:HGF-majorization}.  Following the discussion in Example \ref{ex:rank1}, it is sufficient to consider the case $\Phi = BC_1$.  It is a classical result that the Gauss hypergeometric function $F(z) = {}_2 F_1(a, b; c; z)$ satisfies Euler's hypergeometric equation:
$$ z(1-z) \frac{d^2F}{dz^2} + [c - (a+b+1)z] \frac{dF}{dz} - ab \, F = 0.$$
Comparing to (\ref{eqn:HO-to-Gauss}), we find:
\begin{equation} \label{eqn:HGDE-rank1}
F''_{k,\lambda}(x) + \Big( k_1 \coth \frac{x}{2} + 2 k_2 \coth x \Big) F'_{k, \lambda}(x) + \Big[ \Big(\frac{k_1}{2} + k_2 \Big)^2 - \lambda^2 \Big] F_{k,\lambda}(x) = 0,
\end{equation}
for $\lambda, x \in \R$.  The function $F_{k,\lambda}$ is determined by (\ref{eqn:HGDE-rank1}) and by the initial conditions
\begin{equation} \label{eqn:rank1-ICs}
F'_{k,\lambda}(0) = 0, \qquad F_{k, \lambda}(0) = 1.
\end{equation}
The above initial conditions follow directly from the definition (\ref{eqn:hgf-def}) in rank one: we must have $F'_{k,\lambda}(0) = 0$ because $F_{k, \lambda}$ is $W$-invariant (i.e.~even), and we must have $F_{k, \lambda}(0) = 1$ due to the stipulation that $G_{k, \lambda}(0) = 1$.

Suppose $\lambda \succeq \mu$, which in dimension one just means that $|\lambda| \ge |\mu|$.  Since the equation (\ref{eqn:HGDE-rank1}) depends only on $\lambda^2$ and not on the sign of $\lambda$, we find $F_{k, -\lambda} = F_{k, \lambda}$, so we can in fact take $|\lambda| > |\mu|$.  We will show that $F_{k, \lambda}(x) \ge F_{k, \mu}(x)$ for all $x \in \R$, with equality only at $x = 0$.

Since $F_{k, \lambda}$ is even, it suffices to consider $x \ge 0$.  From (\ref{eqn:HGDE-rank1}) and the initial conditions (\ref{eqn:rank1-ICs}), we have:
$$F_{k, \lambda}(0) = F_{k, \mu}(0) = 1,$$
$$F'_{k,\lambda}(0) = F'_{k,\mu}(0) = 0,$$
$$F''_{k,\lambda}(0) = \lambda^2 - \Big(\frac{k_1}{2} + k_2 \Big)^2 > \mu^2 - \Big(\frac{k_1}{2} + k_2 \Big)^2 = F''_{k,\mu}(0).$$
Therefore there is some $\varepsilon > 0$ such that for all $x \in (0, \varepsilon)$,
$$F_{k, \lambda}(x) > F_{k, \mu}(x), \qquad F'_{k, \lambda}(x) > F'_{k, \mu}(x), \qquad F''_{k, \lambda}(x) > F''_{k, \mu}(x).$$
Consider the set $E = \{ x > 0 \ | \ F_{k, \lambda}(x) = F_{k, \mu}(x) \}.$  If $E$ is empty, then $F_{k, \lambda}(x) > F_{k, \mu}(x)$ for all $x > 0$, and there is nothing to prove.  Assume for the sake of contradiction that $E$ is not empty, and let $x_0 = \inf E.$  Clearly $x_0 > \varepsilon.$  Since $F_{k, \lambda}$ and $F_{k, \mu}$ are continuous, we have $F_{k, \lambda}(x_0) = F_{k, \mu}(x_0)$, and
\begin{equation} \label{eqn:F-x0}
F_{k, \lambda}(x) > F_{k, \mu}(x) \textrm{ for all } x \in (0, x_0).
\end{equation}
However, since $$F_{k, \lambda}(x_0) = 1 + \int_{0}^{x_0} F'_{k, \lambda}(\tau) \, d\tau, \qquad F_{k, \mu}(x_0) = 1 + \int_{0}^{x_0} F'_{k, \mu}(\tau) \, d\tau,$$ and $F'_{k, \lambda} > F'_{k, \mu}$ on $(0, \varepsilon)$, in order to have $F_{k, \lambda}(x_0) = F_{k, \mu}(x_0)$ there must be some $x_1 \in (\varepsilon, x_0)$ such that $F'_{k, \lambda}(x_1) < F'_{k, \mu}(x_1)$.  By the intermediate value theorem and by (\ref{eqn:F-x0}), there must then be some $x_2 \in (\varepsilon, x_1)$ such that all of the following hold:
\[
\textrm{(a) } F'_{k, \lambda}(x_2) = F'_{k, \mu}(x_2), \qquad
\textrm{(b) } F''_{k, \lambda}(x_2) < F''_{k, \mu}(x_2), \qquad
\textrm{(c) } F_{k, \lambda}(x_2) > F_{k, \mu}(x_2).
\]
Subtracting (\ref{eqn:HGDE-rank1}) from the corresponding equation for $F_{k, \mu}$ and using condition (a) above to cancel terms, we find
$$ F''_{k,\mu}(x_2) - F''_{k,\lambda}(x_2) + \Big[ \Big(\frac{k_1}{2} + k_2 \Big)^2 - \mu^2 \Big] F_{k,\mu}(x_2) - \Big[ \Big(\frac{k_1}{2} + k_2 \Big)^2 - \lambda^2 \Big] F_{k,\lambda}(x_2) = 0.$$
But by (b), (c), and the assumption that $|\lambda| > |\mu|$, the left-hand side above must be positive, yielding a contradiction and completing the proof.
\end{proof}

We next turn our attention from hypergeometric functions to the closely related family of Heckman--Opdam polynomials, which we now define.  For $\alpha \in \Phi$, write $$\alpha^\vee = \frac{2 \alpha}{\langle \alpha, \alpha \rangle}.$$  The fundamental weights $\omega_1, \hdots, \omega_r$ are defined by $\langle \omega_i, \alpha_j^\vee \rangle = \delta_{ij},$ where $\alpha_1, \hdots, \alpha_r$ are the simple roots.  They span the {\it weight lattice} $P \subset V$.  The {\it dominant integral weights} are the lattice points $P^+ \subset P$ that lie in the dominant Weyl chamber.

The Heckman--Opdam polynomials $P_{k,\lambda}$ depend on a nonnegative multiplicity parameter $k$ and a dominant integral weight $\lambda \in P^+$.  They are elements of $\R[P]$, the group algebra of the weight lattice, and are therefore polynomials in an abstract-algebraic sense.  However, it is typical to identify $\R[P]$ with the algebra spanned by the functions $e^{\langle \lambda, x \rangle}$, $\lambda \in P$, so that as functions on $V$ the Heckman--Opdam polynomials are actually {\it exponential} polynomials.

We write an element $f \in \R[P]$ as $f = \sum_{\lambda \in P} f_\lambda e^\lambda$, where only finitely many $f_\lambda$ are nonzero, and set $$\bar f = \sum_{\lambda \in P} f_{-\lambda} e^\lambda.$$ Define a bilinear form $(\cdot, \cdot)_k$ on $\R[P]$ by $$( f, g )_k = (f \bar g \delta_k \bar \delta_k)_0,$$ which extracts the constant term (i.e.~the coefficient of $e^0 = 1$) in $f \bar g \delta_k \bar \delta_k$, where $\delta_k$ is the function defined in (\ref{eqn:delta-k-def}).  This bilinear form is symmetric and positive definite, and therefore defines an inner product on $\R[P]$.

For $\lambda \in P^+$, let $$M_\lambda = \frac{|W \cdot \lambda|}{|W|} \sum_{w \in W} e^{w(\lambda)}$$ be the monomial $W$-invariant (exponential) polynomial, and define $\mathrm{low}(\lambda)$ as the set of $\mu \in P^+$ such that $\lambda - \mu$ can be written as a linear combination of simple roots with non-negative integer coefficients.

\begin{definition} \label{def:HO-polys} \normalfont
For $\lambda \in P^+$, the {\it Heckman--Opdam polynomial} $P_{k, \lambda}$ is defined by
\begin{equation} \label{eqn:HO-poly1}
P_{k, \lambda} = \sum_{\mu \in \mathrm{low}(\lambda)} c_{\lambda \mu} M_\mu, \qquad c_{\lambda \lambda} = 1,
\end{equation}
and by the orthogonality relations
\begin{equation} \label{eqn:HO-orth}
(P_{k, \lambda} , \, M_\mu)_k = 0, \qquad \mu \in \mathrm{low}(\lambda), \ \mu \not = \lambda.
\end{equation}
Note that (\ref{eqn:HO-poly1}) and (\ref{eqn:HO-orth}) together determine the coefficients $c_{\lambda \mu} \in \R$ for $\mu \not = \lambda.$
\end{definition}

As $\lambda$ ranges over $P^+$ with $k$ fixed, the $P_{k,\lambda}$ form an $\R$-basis of the algebra $\R[P]^W$ of $W$-invariant elements in $\R[P]$.  Moreover this basis is orthogonal with respect to the inner product $(\cdot, \cdot)_k$.

\begin{example} \label{ex:HO-poly-examples} \normalfont
When all $k_\alpha$ are 0, $P_{0,\lambda} = M_\lambda.$

Let $\gog$ be a compact semisimple Lie algebra with root system $\Phi$, and identify $V$ with a Cartan subalgebra $\tot \subset \gog$.  Let $G$ be the connected, simply connected Lie group with $\mathrm{Lie}(G) = \gog$.  When $k = \vec 1$, $P_{\vec 1, \lambda}(ix) = \chi_\lambda(e^x)$ is the character of the irreducible $G$-representation with highest weight $\lambda$.

When $\Phi = A_{N-1}$, there is a natural injective homomorphism from $\R[P]^W$ to the usual ring of symmetric polynomials in $N$ variables.  This homomorphism is obtained by identifying $M_\lambda$ with the monomial symmetric polynomial $$m_\lambda(x_1, \hdots, x_N) = \frac{|S_N \cdot \lambda |}{N!} \sum_{\sigma \in S_N} \prod_{i=1}^N x_i^{\lambda_{\sigma(i)}}.$$ Under this identification, the Heckman--Opdam polynomials are Jack polynomials.  In particular, for $k = \vec 1$, they are Schur polynomials.  In light of Proposition \ref{prop:HO-majorization} below, Conjecture \ref{conj:HGF-majorization} therefore subsumes both
the Schur polynomial inequality of \cite{CGS,Sra} and the classical Muirhead inequality for monomial symmetric polynomials \cite{Muirhead}.
\end{example}

Up to a normalizing factor, the Heckman--Opdam polynomials turn out to be specializations of the Heckman--Opdam hypergeometric function.  In particular, for $\lambda \in V$, define
\begin{equation} \label{eqn:tilde-c-def}
\tilde c(\lambda, k) = \prod_{\alpha \in \Phi^+} \frac{\Gamma(\langle \lambda, \alpha^\vee \rangle + \frac{1}{2} k_{\frac{1}{2} \alpha})}{\Gamma(\langle \lambda, \alpha^\vee \rangle + \frac{1}{2} k_{\frac{1}{2} \alpha} + k_\alpha)},
\end{equation}
where $k_{\frac{1}{2} \alpha} = 0$ if $\frac{1}{2} \alpha \not \in \Phi$.  Observe that if $\Phi$ is the root system of a compact Lie algebra $\gog$, we have $\tilde c(\lambda, \vec 1) = \Delta_\gog(\lambda)^{-1}.$  Set $$c(\lambda, k) = \frac{\tilde c(\lambda, k)}{\tilde c(\rho^{(k)}, k)}.$$
We then have the following relation between Heckman--Opdam polynomials and hypergeometric functions \cite[eq.~4.4.10]{HS}:
\begin{equation} \label{eqn:P-to-F}
F_{k,\lambda + \rho^{(k)}}(x) = c(\lambda + \rho^{(k)}, k) \, P_{k,\lambda}(x), \qquad x \in V, \ \lambda \in P^+.
\end{equation}
This relation generalizes the relation between the spherical functions $\phi^-_{-i(\lambda - \rho)}$ and $\phi^+_\lambda$ discussed in Section \ref{sec:cpt-sym}.  It immediately yields the following proposition.

\begin{proposition} \label{prop:HO-majorization}
Let $\lambda, \mu \in P^+$.  If Conjecture \ref{conj:HGF-majorization} holds, then the following are equivalent:
\begin{enumerate}
\item $\lambda \succeq \mu$,
\item $\tilde c(\lambda + \rho^{(k)}, k) P_{k,\lambda}(x) \ge \tilde c(\mu + \rho^{(k)}, k) P_{k,\mu}(x)$ for all $x \in V$.
\end{enumerate}
\end{proposition}

In other words, Conjecture \ref{conj:HGF-majorization} would imply a generalization of Proposition \ref{prop:compact-majorization} to the case of Heckman--Opdam polynomials.  A similar generalization of Proposition \ref{prop:euclidean-majorization} to generalized Bessel functions would also follow immediately via the rational limit in Example \ref{ex:gen-bessel}.

It is well known that Heckman--Opdam polynomials can be realized as a limit of Macdonald polynomials \cite{Mac}.  It is interesting to speculate about whether Conjecture \ref{conj:HGF-majorization}, if it holds, is itself a manifestation of an even more general monotonicity property of Macdonald polynomials with respect to $W$-majorization.

\section*{Acknowledgements}
Colin McSwiggen would like to thank Patrick McSwiggen for helpful discussions during the preparation of this manuscript.  The work of Colin McSwiggen is partially supported by the National Science Foundation under Grant No.~DMS 1714187.

The work of Jonathan Novak is partially supported by a Lattimer Fellowship, as well as by the Natural Science Foundation under Grant No.~DMS 1812288.

Both authors would like to thank the anonymous referee for helpful comments.

\bibliographystyle{alpha}


TITLE: Surface area with cavalier's principle
QUESTION [2 upvotes]: The formula for the lateral surface area of an oblique cylinder as shown in the picture (linked because I can't post images) is
$$A=2\pi ra$$
or
$$A =\frac{2\pi rh}{\sin(v)}$$
oblique cylinder
This makes intuitive sense by Cavalieri's principle, but how would one prove it explicitly by integration? Is there a parametrisation for the cylinder which we could integrate to get the surface area?

REPLY [2 votes]: Update
Set up a parametrical representation in the form
$$(\phi,s)\mapsto {\bf r}(\phi,s):=(r\cos\phi+ s\cos v,r\sin\phi, s\sin v)\qquad(0\leq\phi\leq2\pi, \ 0\leq s\leq a)\ ,$$
and compute the area according to the standard formula. You will obtain
$${\rm area}(S)=ar\int_0^{2\pi}\sqrt{1-\cos^2\theta\sin^2\phi}\>d\phi\ .$$
From this we can draw two conclusions, namely (i) that the area cannot be expressed in terms of elementary functions, and (ii) that the intuitive approach using Cavalieri's principle does not lead to the correct result. (I was surprised, too.)
The formula ${\rm area}(S)=2\pi ar$ is only correct, if $\theta={\pi\over2}$. In fact one easily verifies "geometrically" that in the case $\theta=0$ one has ${\rm area}(S)=4 ar$, which is also the value produced by the above formula.


TITLE: Show that there are $\binom{n-1}{k-1}$ ways to describe $n$ as a sum with $k$ positive, ordered parts
QUESTION [1 upvotes]: Show that there are $\binom{n-1}{k-1}$ ways to describe $n$ as a sum of $k$ positive, ordered parts.

I know that there are $n-k+1$ options for the first part of the sum. And the first choice affects the choice for the snd part and so on. I have also tried a proof by induction, assuming that there are $\binom{n-1}{k-1}$ ways to describe $n$ as a $k$-part sum, we pick one possibility and add 1 to one of the parts and we get $n+1$  That means there would be $k\binom{n-1}{k-1}$ ways to describe $n+1$ but there are doubles such that $(m_1,\dots,m_k)\ne(m'_1,\dots,m'_k)$ but $(m_1,\dots,m_i+1,\dots,m_k) = (m'_1,\dots,m'_j + 1,\dots,m'_k)$ with $i\ne j$ and $m_1 + \dots+ m_k = n = m'_1 +\dots+ m'_k$ and $m'_1 +\dots+ m'_j + 1 +\dots+ m'_k  = m_1 +\dots + m_i + 1 +\dots+ m_k = n + 1$.
It would be good if we could show somehow that there are $\binom nk$ ways to describe $n+1$.
These are my ideas maybe I am completely wrong with my approaches if so please tell me, any hint would be appreciated.

REPLY [1 votes]: You are, indeed, completely missing a direct solution. Picture $n$ stars and $k-1$ bars which go into the $n-1$ gaps between the stars, at most one bar per gap. Then the $\binom{n-1}{k-1}$ ways to put the bars in the gaps are in bijection with the number of ways to describe $n$ as a sum in $k$ (ordered, positive) parts; I leave it to you to show this bijection.


TITLE: Prove that each connected component is closed
QUESTION [2 upvotes]: Good evening, I'm doing exercise II.4.6 in textbook Analysis I by Amann.

Here $X$ is a metric space.

Could you please verify if my attempt contains logical mistakes/gaps! Thank you so much!

My attempt:
(a)
For $x \in X$. Let $M_x = \{Y \in \mathcal P(X) \mid Y \, \text{is connected} \wedge x \in Y \}$. Then $\{x\} \in M_x$. We have $X =\bigcup_{x \in X} \{x\} \subseteq \bigcup_{x \in X} K(x) \subseteq X$, so $X = \bigcup_{x \in X} K(x)$.
Assume that $K(x) \cap K(y)$ is nonempty. Then $K(x) \cup K(y)$ is connected. So $M_y \ni (K(x) \cup K(y)) \in M_x$ and hence $(K(x) \cup K(y)) \subseteq K(x)$ and $(K(x) \cup K(y)) \subseteq K(y)$. Then $K(x) = K(y)$.
As such, $\{K(x) \mid x \in X\}$ is a partition of $X$.
(b)
Let $(x_n)$ be a sequence in $K(a)$ such that $x_n \to b \in X$. Then $K(x_n) =K(a)$ for all $n$. There exists $x_N \in \mathbb B(b,1)$. On the other hand, $\mathbb B(b,1)$ is connected. So $\mathbb B(b,1) \in M_{x_N}$ and hence $\mathbb B(b,1) \subseteq K(x_N) = K(a)$. As such, $b \in K(a)$. Hence $K(a)$ is closed.
Update: Here is my fixed proof of (b):
For $x \in K(a)$, $x \in \overline{K(a)}$. Because $K(a)$ is connected, $\overline{K(a)}$ is connected. So $\overline{K(a)} \in M_a$ and hence $\overline{K(a)} \subseteq K(a) \subseteq \overline{K(a)}$. As such, $K(a) = \overline{K(a)}$ is closed in $X$.

REPLY [1 votes]: Use this fact: the closure of a connected set is connected. Here is the proof:  if $\overline A=C\cup D$ for some non-empty sets $C,D$ open in $\overline A$.  Since $A$ is connected, we may assume without loss of generality, that $A\subseteq C$. Then, $\overline A\subseteq \overline C.$ But $\overline C\cap D=\emptyset$ (why?) and so $\overline A\cap D=\emptyset$. Thus, we have shown that $D$ is empty, which is a contradiction.
Now, let $C$ be a component of $x$. Then, $x\in \overline C$, which is connected, so by definition of component, $\overline C\subseteq C$. That is, $\overline C=C$, so $C$ is closed.


TITLE: What is the formula to predict a high probability of range 0~9, given by past results?
QUESTION [0 upvotes]: I'm very new and i'm below average for my math.
But there's this thing about a lucky draw game that bugs me to think of a probability.
Say the host of a party has already drawn several luck draw numbers for each 2 hours, such as below:
$$\begin{array}{c|c|c}
\text{Time} & \text{1st Draw} & \text{2nd Draw} & \text{3rd Draw}\\
\hline
\\08 AM & 1516 & 4865 & 9876
\\10 AM & 0513 & 7805 & 9843
\\12 PM & 1124 & 0350 & 8790
\\02 PM & 9802 & 7967 & 3210
\\04 PM & 8794 & 6350 & 7842
\\06 PM & ???? & ???? & ????
\end{array}$$
Now, at $06:00 PM$ I would like to find out the [????].
I wish to know from the range of [0~9], what will be the 4 digits highly probable number to appear.
It does not need to be sorted in any order.
e.g, if you think the result is $0531$, then it doesn't matter if its $0351$ or $5130$ or $3150$ or etc...
It does not need to be in any specific draws, meaning dont care if its [1st draw] or [3rd draw]...
All I need to know is the 4 high probability digits.

Any ideas? Thank in advance.

REPLY [1 votes]: Are those draws some of 10000 cards that are drawn and will never be drawn again?
If not and they are just drawn sets of digits that are allowed to repeat and are not dependent on each other then it's impossible to get the answer that you want. In this case the previous numbers give no information about the following numbers and this is how such lotteries work in real life.