On the exact region determined by Kendall's tau and Spearman's rho
\fnms{Manuela
\fnms{Roland
\fnms{Roland
\fnms{Wolfgang
Using properties of shuffles of copulas and tools from combinatorics we solve the open question about the exact region $\Omega$ determined by all possible values of Kendall's $\tau$ and Spearman's $\rho$. In particular, we prove that the well-known inequality established by Durbin and Stuart in 1951 is only sharp on a countable set with sole accumulation point $(-1,-1)$, give a simple analytic characterization of $\Omega$ in terms of a continuous, strictly increasing piecewise concave function, and show that $\Omega$ is compact and simply connected but not convex. The results also show that for each $(x,y)\in \Omega$ there are mutually completely dependent random variables whose $\tau$ and $\rho$ values coincide with $x$ and $y$ respectively.
tau_versus_rho20150216.tex
% \documentclass[aos,preprint]{imsart}
\documentclass[preprint]{imsart}
\pdfoutput=1

\RequirePackage[OT1]{fontenc}
\RequirePackage{amsthm,amsmath}
\RequirePackage[numbers]{natbib}
%\usepackage{natbib}
\RequirePackage[colorlinks,citecolor=blue,urlcolor=blue]{hyperref}
\usepackage{latexsym}
%\usepackage{eufrak}
\usepackage{euscript}
\usepackage{exscale}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{mathrsfs}

\allowdisplaybreaks[2]

% settings
%\pubyear{2005}
%\volume{0}
%\issue{0}
%\firstpage{1}
%\lastpage{8}
\arxiv{arXiv:0000.0000}

\startlocaldefs
\numberwithin{equation}{section}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{defin}[thm]{Definition}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{cor}[thm]{Corollary}
%\newdefinition{rmk}{Remark}
%\newdefinition{ex}{Example}
%\newtheorem{thm}{Theorem}[section]
\endlocaldefs

\newcommand{\fc}{\mathfrak{C}}
\newcommand{\kc}{\mathcal{C}}
\newcommand{\kp}{\mathcal{P}}
\newcommand{\ka}{\mathcal{A}}
\newcommand{\km}{\mathcal{M}}
\newcommand{\qn}{\mathbb{Q}_{[0,1]}}
\newcommand{\bor}{\mathcal{B}([0,1])}
\newcommand{\pc}{\mathcal{P}_\mathcal{C}}
\newcommand{\mk}{\mathcal{K}}

\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\invs}{invsum}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\id}{id}

\begin{document}

\begin{frontmatter}
%\title{A Sample Document\thanksref{T1}}
\title{On the exact region determined by Kendall's tau and Spearman's rho}
\runtitle{On the exact $\tau$-$\rho$ region}
%\thankstext{T1}{Footnote to the title with the ``thankstext'' command.}

\begin{aug}
\author{\fnms{Manuela} \snm{Schreyer}\ead[label=e1]{manuelalarissa.schreyer@sbg.ac.at}},
\author{\fnms{Roland} \snm{Paulin}\thanksref{t1}\ead[label=e2]{roland.paulin@sbg.ac.at}}
%\author{\fnms{Roland} \snm{Paulin}\thanksref{t3,m1,m2}\ead[label=e2]{second@somewhere.com}}
\and
\author{\fnms{Wolfgang} \snm{Trutschnig}\thanksref{t2}\ead[label=e3]{wolfgang.trutschnig@sbg.ac.at}
%\ead[label=u1,url]{http://www.foo.com}}
}
\thankstext{t1}{Supported by the Austrian Science Fund (FWF): P24574}
\thankstext{t2}{corresponding author}
%\thankstext{t3}{Second supporter of the project}
\runauthor{Schreyer, Paulin, Trutschnig}

\affiliation{University of Salzburg}

\address{Department for Mathematics\\
University of Salzburg \\
Hellbrunnerstrasse 34 \\
A-5020 Salzburg\\
\printead{e1}\\
\phantom{E-mail:\ }\printead*{e2} \\
\phantom{E-mail:\ }\printead*{e3}}

\address{}
\end{aug}

\begin{abstract}
Using properties of shuffles of copulas and tools from combinatorics we solve the open question about the exact region 
$\Omega$ determined by all possible values of Kendall's $\tau$ and Spearman's $\rho$. 
In particular, we prove that the well-known inequality established by Durbin and Stuart in 1951 is only sharp on 
a countable set with sole accumulation point $(-1,-1)$, give a simple analytic characterization of $\Omega$ in terms of 
a continuous, strictly increasing piecewise concave function, and show that 
$\Omega$ is compact and simply connected but not convex. 
The results also show that for each $(x,y)\in \Omega$ there are mutually completely dependent random variables 
whose $\tau$ and $\rho$ values coincide with $x$ and $y$ respectively. 
\end{abstract}

\begin{keyword}[class=MSC]
\kwd[Primary ]{62H20}
\kwd{60E15}
\kwd[; secondary ]{28D05} 
\kwd{05A05}
\end{keyword}

\begin{keyword}
\kwd{Measures of association}
\kwd{Kendall $\tau$}
\kwd{Spearman $\rho$}
\kwd{Copula}
\kwd{complete dependence}
\end{keyword}

\end{frontmatter}

\section{Introduction}
Kendall's $\tau$ and Spearman's $\rho$ are, without doubt, the two most famous nonparametric measures of association/concordance.
Given random variables $X,Y$ with continuous distribution functions $F$ and $G$ respectively, Spearman's $\rho$
is defined as the Pearson correlation coefficient of the $\mathcal{U}(0,1)$-distributed random 
variables $U:=F \circ X$ and $V:=G \circ Y$ whereas Kendall's $\tau$ is given by the probability of concordance minus the 
probability of discordance, i.e. 
\begin{align*}
\rho(X,Y)&= 12\big(\mathbb{E}(UV)-\tfrac{1}{4}\big) \\
\tau(X,Y)&= \mathbb{P}\big((X_1-X_2)(Y_1 -Y_2)>0) - \mathbb{P}\big((X_1-X_2)(Y_1 -Y_2)<0\big),
\end{align*}
whereby $(X_1,Y_1)$ and $(X_2,Y_2)$ are independent and have the same distribution as $(X,Y)$. 
Since both measures are scale invariant they only depend on the underlying (uniquely determined) copula $A$ of $(X,Y)$.
It is well known and straightforward to verify (see \cite{Ne}) that, given the copula $A$ of $(X,Y)$, 
Kendall's $\tau$ and Spearman's $\rho$ can be expressed as
\begin{align}
\tau(X,Y)&= 4 \int_{[0,1]^2} A(x,y)\, d\mu_A(x,y) - 1=:\tau(A)  \label{deftau} \\
\rho(X,Y)&= 12 \int_{[0,1]^2} xy \,d\mu_A(x,y) - 3=:\rho(A) \label{defrho}, 
\end{align}
whereby $\mu_A$ denotes the doubly stochastic measure corresponding to $A$. Considering that 
$\tau$ and $\rho$ quantify different aspects of the underlying dependence structure 
(see \cite{FreNe} and the references therein) a very natural question is how much they can 
differ, i.e. if $\tau(X,Y)$ is known which values may $\rho(X,Y)$ assume and vice versa. 
The following well-known universal inequalities
between $\tau$ and $\rho$ go back to Daniels \cite{Dan} and Durbin and Stuart \cite{D+S} respectively 
(for alternative proofs see \cite{Kr,Ge,Ne}):  
\begin{equation}\label{ineqdaniels}
\vert 3 \tau-2 \rho \vert \leq 1
\end{equation}
\begin{equation}\label{ineqdurbinstuart}
\frac{(1+\tau)^2}{2} -1 \leq \rho \leq 1- \frac{(1-\tau)^2}{2}
\end{equation}
The inequalities together yield the set $\Omega_0$ (see Figure \ref{regionintro}) 
to which we will refer to as \emph{classical $\tau$-$\rho$ region} in the sequel.
Daniels' inequality is known to be sharp (see \cite{Ne}) whereas the first part of the inequality by Durbin and Stuart
is only known to be sharp at the points $p_n=(-1+\frac{2}{n},-1+\frac{2}{n^2})$ with $n \geq 2$ (which, using symmetry, is
to say that the second part is sharp at the points $-p_n$). 
Although both inequalities are known since the 1950s and the interrelation between $\tau$ and $\rho$ has 
received much attention also in recent years (see \cite{FreNe} and the references therein), 
to the best of the authors' knowledge the \emph{exact $\tau$-$\rho$ region $\Omega$}, defined
by ($\kc$ denoting the family of all two-dimensional copulas)
\begin{align}\label{defregionall}
\Omega&=\big\{(\tau(X,Y),\rho(X,Y)):\,\, X,Y \textrm{ continuous random variables}\big\} \\
 &= \big\{(\tau(A),\rho(A)):\,\, A \in \kc\big\} \nonumber,
\end{align} 
is still unknown.

In this paper we give a full characterization of $\Omega$. We derive a piecewise concave, strictly increasing, continuous 
function $\Phi:[-1,1]\rightarrow [-1,1]$ and (see Theorem \ref{mainres} and Theorem \ref{identical}) prove that 
\begin{align}\label{finalobj}
\Omega=\big\{(x,y)\in [-1,1]^2: \Phi(x)\leq y \leq -\Phi(-x) \big\}.
\end{align} 
Figure \ref{regionintro} depicts $\Omega_0$ and the function $\Phi$ (lower red line), the explicit form of 
$\Phi$ is given in eq. (\ref{Phi}) and eq. (\ref{Phim}).   
As byproduct we get that the inequality by Durbin and Stuart is not sharp outside the aforementioned points $p_n$ and $-pn$, 
that $\Omega$ is compact and simply connected, but not convex. Moreover, we prove the surprising fact that
for each point $(x,y) \in \Omega$ there exist mutually completely dependent random variables $X,Y$ for which
$(\tau(X,Y),\rho(X,Y))=(x,y)$ holds.  
%---------------------------------fig
\begin{figure}[!h]
\centering
\includegraphics[width=12.5cm]{region_old.pdf}
\caption{The classical $\tau$-$\rho$-region $\Omega_0$ and some copulas (distributing mass uniformly on the blue segments)
for which the inequality by Durbin and Stuart is sharp. The red line depicts the true boundary of $\Omega$.}
\label{regionintro}
\end{figure} 

The rest of the paper is organized as follows: Section 2 gathers some notations and preliminaries. In Section 
3 we reduce the problem of determining $\Omega$ to a problem about so-called shuffles of copulas, prove
some properties of shuffles and derive the function $\Phi$. The main result saying that 
$\Omega$ is contained in the right-hand-side of eq. (\ref{finalobj}) is given in Section 4, tedious 
calculations needed for the proofs are collected to the Appendix. Finally, Section 5 serves to 
prove equality in eq. (\ref{finalobj}), and to collect some interesting consequences of this result.  
  

%---------------------------------------------------------------------------
\section{Notation and Preliminaries}
As already mentioned before, $\kc$ will denote the family of all two-dimen\-sional \emph{copulas},
see \cite{DuS,Em,Ne,Sem2}.
$M$ and $W$ will denote the minimum copula and the lower Fr\'echet-Hoeffding bound respectively.  
Given $A\in \kc$ the \emph{transpose} $A^t \in \kc$ of $A$ is defined by $A^t(x,y):=A(y,x)$ for all $x,y \in [0,1]$.
$d_\infty$ will denote the uniform distance on $\kc$; it is well known that $(\kc,d_\infty)$ is a compact metric space and
that $d_\infty$ is a metrization of weak convergence in $\kc$. 
For every $A \in \kc$ the corresponding \emph{doubly stochastic measure} will be denoted by $\mu_A$, i.e. we have
$\mu_A([0,x]\times [0,y]):=A(x,y)$ for all $x,y\in [0,1]$. $\mathcal{P}_\mathcal{C}$ denotes the class
of all these doubly stochastic measures.
$\mathcal{B}([0,1])$ and $\mathcal{B}([0,1]^2)$ will denote the Borel $\sigma$-fields in $[0,1]$ and $[0,1]^2$, 
$\lambda$ and $\lambda_2$ the Lebesgue measure on $[0,1]$ and $[0,1]^2$ respectively. 
Instead of $\lambda$-a.e. we will simply write a.e. since no confusion will arise. 
$\mathcal{T}$ will denote the class of all $\lambda$-preserving transformations $h:[0,1] \rightarrow [0,1]$, i.e.
transformations for which the push-forward $\lambda^h$ of $\lambda$ via $h$ coincides with $\lambda$,  
$\mathcal{T}_b$ the subclass of all bijective $h \in \mathcal{T}$. 

For every copula $A \in \kc$ there exists a \emph{Markov kernel} (regular conditional distribution) 
$K_A:[0,1] \times \mathcal{B}([0,1]) \rightarrow [0,1]$ fulfilling 
($G_x:=\{y \in [0,1]:(x,y) \in G\}$ denoting the $x$-section of $G \in \mathcal{B}([0,1]^2)$ for 
every $x \in [0,1]$)
\begin{equation}\label{bound}
 \int_{[0,1]} K_A(x,G_x)\, d\lambda(x) = \mu_A(G),
\end{equation}
for every $G \in \mathcal{B}([0,1]^2)$, so, in particular
 \begin{equation}\label{bound2}
 \int_{[0,1]} K_A(x,F)\, d\lambda(x) = \lambda(F)
\end{equation}
for every $F \in \mathcal{B}([0,1])$. We will refer to $K_A$ simply as Markov kernel of $A$.
On the other hand, every Markov kernel $K:[0,1]\times \mathcal{B}([0,1]) \rightarrow [0,1]$ fulfilling (\ref{bound2}) 
induces a unique element $\mu \in \pc([0,1]^2)$ via (\ref{bound}). 
For more details and properties of regular conditional distributions and disintegration we refer to \cite{Ka,Kl}.\\
A copula $A\in \kc$ will be called \emph{completely dependent} if and only if there exists 
$h \in \mathcal{T}$ such that $K(x,E):=\mathbf{1}_E(h(x))$ is a Markov kernel of $A$ 
(see \cite{Lan,Tru} for equivalent definitions and main properties). 
For every $h \in \mathcal{T}$ the induced completely dependent copula will be denoted by $A_h$.
Note that $h_1=h_2$ a.e. implies $A_{h_1}=A_{h_2}$ and that eq. (\ref{bound}) implies 
$A_h(x,y)=\lambda([0,x] \cap h^{-1}([0,y]))$ for all $x,y \in [0,1]$. In the sequel $\kc_d$ will 
denote the family of all completely dependent copulas. 
$A_h \in \kc_d$ will be called \emph{mutually completely dependent} if we even have $h \in \mathcal{T}_b$. Note that
in case of $h \in \mathcal{T}_b$ we have $A_{h^{-1}}=(A_h)^t$.
Complete dependence is the exact opposite of independence since it describes the (not necessarily mutual) 
situation of full predictability/maximum dependence. 
Some notions quantifying dependence of two-dimensional random variables which, contrary to Schweizer and 
Wolff's $\sigma$ (see \cite{SchW}) are not based on $d_\infty$ have been studied in \cite{Sib,Tru}. 

Tackling the problem of determining the region $\Omega$, our main tool will be special  
members of the class $\kc_d$ usually
referred to as \emph{shuffles of} the minimum copula \emph{$M$}. 
Following \cite{Ne} we will call $h\in \mathcal{T}_b$ a
\emph{shuffle} (and $A_h \in \kc_d$ a shuffle of $M$) if there exist $0=s_0<s_1<\ldots < s_{n-1} < s_n=1$ and 
$\varepsilon=(\varepsilon_1,\ldots,\varepsilon_n) \in \{-1,1\}^n$ such that we have 
$h'(x)=\varepsilon_i$ for every $x \in (s_{i-1},s_i)$. In case of $\varepsilon_i=1$ for every $i \in \{1,\ldots,n\}$ we will
call $h$ \emph{straight shuffle}. $\mathcal{S}$ will denote the family of all shuffles, 
$\mathcal{S}^+$ the family of all straight shuffles. It is well known (see \cite{Mish,Ne}) that 
$\kc_{\mathcal{S}^+}$, defined by
\begin{equation}
\kc_{\mathcal{S}^+}=\big\{A_h: \,h\in \mathcal{S}^+\big\}
\end{equation}
is dense in $(\kc,d_\infty)$. For more general definitions of shuffles we refer 
to \cite{DuS}.  
Obviously every shuffle $h \in \mathcal{S}$ can be expressed in terms
of vectors $u \in \Delta_n, \varepsilon \in \{-1,1\}^n$ and a permutation $\pi \in \sigma_n$, whereby 
$\Delta_n$ denotes the unit simplex $\Delta_n=\{x \in [0,1]^n: \sum_{i=1}^n x_i=1\}$ and $\sigma_n$ denotes
all bijections on $\{1,\ldots,n\}$. In fact, choosing suitable
$u \in \Delta_n, \varepsilon \in \{-1,1\}^n, \pi \in \sigma_n$, setting (empty sums are zero by definition)
\begin{eqnarray}
s_k&:=&\sum_{i=1}^k u_i, \qquad t_k:=\sum_{i=1}^k u_{\pi^{-1}(i)}
\end{eqnarray}
for every $k \in \{0,\ldots,n\}$, we have $s_k-s_{k-1}=u_k=t_{\pi(k)}-t_{\pi(k)-1}$ 
and on $(s_{k-1},s_k)$ the shuffle $h$ is given by   
\begin{equation}\label{defshuffle}
h(x) = h_{\pi,u,\varepsilon}(x):= \left\{
\begin{array}{ll}
t_{\pi(k)-1} + x - s_{k-1} & \text{if } \varepsilon_k=1,\\
t_{\pi(k)} - (x-s_{k-1}) & \text{if } \varepsilon_k=-1.
\end{array} \right.
\end{equation}
\begin{figure}[!h]
\centering
\includegraphics[width=9cm]{shuffle.pdf}
\caption{Shuffle $h_{\pi,u,\varepsilon}$ with 
$\pi=(4,2,1,3), u=(\frac{1}{8},\frac{3}{8},\frac{1}{4},\frac{1}{4})$ and $\varepsilon=(1,-1,1,1)$}
\label{exshuffle}
\end{figure} 

In the sequel we will directly work with the function $h_{\pi,u,\varepsilon}$, implicitly defined in eq. (\ref{defshuffle})
%on all intervals $(s_{k-1},s_k)$ and, by definition, zero outside these intervals, 
since all possible extensions of $h_{\pi,u,\varepsilon}$ from $\bigcup_{i=1}^k(s_{k-1},s_k)$ to $[0,1]$ yield the same copula,
which we will denote by $A_{h_{\pi,u,\varepsilon}}$. In case of $\varepsilon_i=1$ for every $i \in \{1,\ldots,n\}$ 
we will simply write $h_{\pi,u}$ in the sequel. Note that the chosen representation is not unique, i.e. for given
$u \in \Delta_n, \varepsilon \in \{-1,1\}^n, \pi \in \sigma_n$ there always exist 
$u' \in \Delta_m, \varepsilon' \in \{-1,1\}^m, \pi' \in \sigma_m$ with $m \not = n$ such that 
$h_{\pi,u,\varepsilon}=h_{\pi',u',\varepsilon'}$ a.e., implying $A_{h_{\pi,u,\varepsilon}}=A_{h_{\pi',u',\varepsilon'}}$. 
So, for instance, the shuffle $h_{\pi,u,\varepsilon}$ with 
$\pi=(4,2,1,3), u=(\frac{1}{8},\frac{3}{8},\frac{1}{4},\frac{1}{4})$ and 
$\varepsilon=(1,-1,1,1)$ as depicted in Figure \ref{exshuffle}, and the shuffle
$h_{\pi',u',\varepsilon'}$ with $\pi'=(5,3,1,2,4), u'=(\frac{1}{8},\frac{3}{8},\frac{1}{8},\frac{1}{8},\frac{1}{4})$ 
and $\varepsilon=(1,-1,1,1,1)$ coincide a.e. and induce the same copula. 
\begin{rmk}   
\emph{It might seem more natural to directly work with minimal representations (minimal dimension $n$) and 
to exclude the case of $u_k=0$ for some $k$ (implying $(s_{k-1},s_k)=\emptyset$) in the first place -- since we 
will, however, use various compactness arguments in the sequel the chosen representation is more convenient.} 
\end{rmk}
%------------------------------------------------------------------------------------------
\section{Basic properties of $\Omega$ and some results on shuffles}
In this section we will first show that for determining $\Omega$ it is sufficient to consider straight shuffles,
give explicit formulas for $(\tau(A_h),\rho(A_h))$ for arbitrary $h \in \mathcal{S}^+$, and derive a strictly increasing  
function $\Phi:[-1,1] \rightarrow [-1,1]$ which, after some change of coordinates, will finally be shown to fully
determine $\Omega$ in the subsequent section. \\  
We start with some observations about $\Omega$. The mapping $f:\kc \rightarrow [-1,1]^2$, defined by
$f(A)=(\tau(A),\rho(A))$, is easily seen to be continuous w.r.t. $d_\infty$, so compactness 
of $(\kc,d_\infty)$ implies compactness of $\Omega$. As a consequence, using eq. (\ref{defregionall}) and the fact that 
$\kc_{\mathcal{S}^+}$ is dense we immediately get 
($\overline{U}$ denoting the closure of a set $U$) 
\begin{equation}\label{omegashuffle}
\Omega=\overline{\big\{(\tau(A_h),\rho(A_h)): \, h \in \mathcal{S}^+ \big\}}.
\end{equation}
Based on this, our method of proof will be to construct a compact set $\Omega_\Phi$ (fully determined by the function $\Phi$) 
fulfilling $(\tau(A_h),\rho(A_h)) \in \Omega_\Phi$ for every $h \in \mathcal{S}^+$ since then 
we automatically get $\Omega \subseteq \Omega_\Phi$.  

Apart from being compact, $\Omega$ is easily seen to be symmetric w.r.t. $(0,0)$. In fact, letting 
$\hat{A} \in \kc$ denote the copula defined by $\hat{A}(x,y)=x-A(x,1-y)$ for every $A \in \kc$, both 
$\tau(\hat{A})=-\tau(A)$ and $\rho(\hat{A})=-\rho(A)$ follow
immediately from eq. (\ref{deftau}) and eq. (\ref{defrho}). Having this, considering $\hat{\hat{A}}=A$, we obtain 
the stated symmetry w.r.t. $(0,0)$. Note that, setting $\hat{h}:=1-h$, we get 
$\hat{A_h}=A_{\hat{h}}$ for every $h \in \mathcal{T}_b$. 
Analogously, it is straightforward to verify that 
$\tau(A^t)=\tau(A)$ as well as $\rho(A^t)=\rho(A)$ holds for every $A \in \kc$, implying
\begin{equation}\label{transposeinvar}
\tau(A_{h^{-1}})=\tau(A_h), \quad \rho(A_{h^{-1}})=\rho(A_h)
\end{equation}  
for every $h \in \mathcal{T}_b$. 

For every $h \in \mathcal{T}$ define the quantities $\inv(h)$ and $\invs(h)$ (notation loosely based 
on \cite{SaUl}) by
\begin{eqnarray}
\inv(h) &=& \int_{[0,1]^2} \mathbf{1}_{[0,x)}(y) \mathbf{1}_{(h(x),1]}(h(y)) \,d\lambda_2(x,y) \label{definv} \\
\invs(h) &=& \int_{[0,1]^2} \mathbf{1}_{[0,x)}(y) \mathbf{1}_{(h(x),1]}(h(y))(x-y) \,d\lambda_2(x,y). \label{definvsum} 
\end{eqnarray}
Then the following result holds:
\begin{lem}\label{trafo1}
For every $h \in \mathcal{T}_b$ the following relations hold:
\begin{eqnarray*}
\tau(A_h)&=& 4 \int_{[0,1]} A_h(x,h(x)) \,d\lambda(x) -1 = 1 - 4 \inv(h) \label{invtau}\\
\rho(A_h)&=& 12 \int_{[0,1]} xh(x) \,d \lambda(x) -3  = 1 - 12 \invs(h) \label{invsumrho}
\end{eqnarray*}
Moreover, for every $h \in \mathcal{T}_b$ we have 
$(\inv(h),\invs(h)) \in \big[0,\frac{1}{2}\big]\times \big[0,\frac{1}{6}\big]$.
\end{lem}
\begin{proof}
Using disintegration we immediately get
\begin{eqnarray*}
\tau(A_h)&=&4\int_{[0,1]} \int_{[0,1]} A_h(x,y) K_{A_h}(x,dy)\,d \lambda(x)-1 \\
         &=& 4 \int_{[0,1]} A_h(x,h(x)) \,d\lambda(x) -1
\end{eqnarray*}
as well as 
\begin{eqnarray*}
\inv(h)&=& \int_{[0,1]} \int_{[0,x]} \Big( 1- \mathbf{1}_{[0,h(x)]}(h(y)) \Big) \,d\lambda(y) d\lambda(x)\\
         &=& \int_{[0,1]} \big(x - A_h(x,h(x)) \big) \,d\lambda(x) = \frac{1-\tau(A_h)}{4}
\end{eqnarray*}
which proves the first identity. The first part of the second one is an immediate consequence of disintegration. To prove
the remaining equality use $\int_{[0,x)} \mathbf{1}_{(h(x),1]} (h(y))\, d\lambda(y)= x-A_h(x,h(x))$ and
$\int_{(y,1]} \mathbf{1}_{[0,h(y))} (h(x))\, d\lambda(x)= h(y)-A_h(y,h(y))$ to finally get
\begin{eqnarray*}
\invs(A_h)&=& \int_{[0,1]} x \big(x- A_h(x,h(x)) -(h(x)-A_h(x,h(x))  \big)\,d\lambda(x) \\
          &=& \frac{1}{3} - \int_{[0,1]} xh(x)\,d\lambda(x).
\end{eqnarray*} 
The fact that $(\inv(A_h),\invs(A_h)) \in \big[0,\frac{1}{2}\big]\times \big[0,\frac{1}{6}\big]$ is a direct
consequence of $\Omega \subseteq [-1,1]^2$.
\end{proof}
As next step we derive explicit formulas for $\inv(h)$ and $\invs(h)$ for the case of $h$ being a straight shuffle 
based on which we will afterwards derive 
the afore-mentioned function $\Phi$ determining the region $\Omega$. To simplify notation define
\begin{eqnarray}\label{defIQ}
I_{\pi} &=& \big\{\{i,j\}: \, 1 \le i < j \le n, \, \pi(i) > \pi(j)\big\} \nonumber \\
Q_{\pi} &=& \big\{\{i,j,k\}: \, 1 \le i < j < k \le n, \, \pi(i) > \pi(j) > \pi(k) \textrm{ or } \\
  & & \qquad \pi(j) > \pi(k) > \pi(i)  \textrm{ or } \pi(k) > \pi(i) > \pi(j) \big\}, \nonumber 
\end{eqnarray}
as well as 
\begin{equation}\label{defab}
a_\pi(u)= \inv(h_{\pi,u}), \qquad b_\pi(u)= \inv(h_{\pi, u}) - 2\invs(h_{\pi, u})
\end{equation}
for every $\pi \in \sigma_n$ and $u \in \Delta_n$. The following lemma (the proof of which is given in the Appendix) holds.
%-----------------lemma
\begin{lem}\label{invexplicit}
For every $(\pi,u) \in \sigma_n\times\Delta_n$ the following identities hold: 
\begin{eqnarray*}
\inv(h_{\pi, u}) &=& a_\pi(u) = \sum_{i<j, \, \{i,j\} \in I_\pi} u_i u_j \\
\invs(h_{\pi, u}) &=& \sum_{i<j, \,\{i,j\} \in I_\pi} \left(\frac{1}{2} u_i^2 u_j + 
\frac{1}{2} u_i u_j^2 + \sum_{k: \, i<k<j} u_i u_j u_k \right) \\
b_\pi(u) &=& \sum_{i<j<k, \, \{i,j,k\} \in Q_{\pi}} u_i u_j u_k
\end{eqnarray*}
\end{lem}  
As pointed out in the Introduction, the first part of inequality (\ref{ineqdurbinstuart}) is known to be sharp only at the points
$p_n=(-1+\frac{2}{n},-1+\frac{2}{n^2})$ with $n \geq 2$. According to \cite{Ne} (or directly using 
Lemma \ref{invexplicit}), considering 
$\pi=(n,n-1,\ldots,2,1)$ and $u_1=u_2=\ldots=u_n=\frac{1}{n}$ we get $p_n=(\tau(A_{h_{\pi,u}}),\rho(A_{h_{\pi,u}}))$. 
Having this, it seems natural to conjecture that all shuffles of the form
$A_{h_{\pi,u}}$ with  
$$
\pi=(n,n-1,\ldots,2,1), \qquad  u_1=u_2=\ldots=u_{n-1}=r,\, u_n=1-(n-1)r
$$
for some $n \geq 2$ and 
$r \in (\frac{1}{n},\frac{1}{n-1})$ might also be extremal in the sense that $(\tau(A_{h_{\pi,u}}),\rho(A_{h_{\pi,u}}))$ 
is a boundary point of $\Omega$. Main content of the paper is the confirmation of this very conjecture.
We will assign all shuffles of the just mentioned form the name prototype, calculate $\tau$ and $\rho$ explicitly for all 
prototypes and then, based on these values, derive the function $\Phi$. 
\begin{defin}\label{proto}
$\pi \in \sigma_n$ will be called \emph{decreasing} if $\pi=(n,n-1,\ldots,2,1)$.
The pair $(\pi,u) \in \sigma_n \times \Delta_n$ will be called a \emph{prototype} if $\pi$ is decreasing and 
there exists some $r \in [\frac{1}{n},\frac{1}{n-1}]$ such that
$u_1=u_2=\ldots=u_{n-1}=r$ and $u_n=1-(n-1)r$.   
Analogously, $h \in \mathcal{S}^+$ (and $A_h \in \kc_d$) 
is called a \emph{prototype} if there exists a prototype $(\pi,u)$ such that $h=h_{\pi,u}$ a.e.
\end{defin} 
Using the identities from Lemma \ref{invexplicit} we get the following expressions for prototypes (the proof is
given in the Appendix):
\begin{lem}\label{formulaproto}
Suppose that $(\pi,u)\in \sigma_n \times \Delta_n$ is a prototype, then 
\begin{eqnarray*}
\tau(A_{h_{\pi, u}}) &=& 1 - 4(n-1)r + 2r^2n(n-1) \in \big[\tfrac{2-n}{n},\tfrac{2-(n-1)}{n-1}\big] \\
\rho(A_{h_{\pi, u}}) &=& 1 - 2r(n-1)\big(3 - 3r(n-1) + r^2(n-2)n\big) \in \big[\tfrac{2-n^2}{n^2},\tfrac{2-(n-1)^2}{(n-1)^2}\big].
\end{eqnarray*}
\end{lem}
Fix $n\geq 2$. Then both functions $r \mapsto 1 - 4(n-1)r + 2r^2n(n-1)$ and 
$r \mapsto 1 - 2r(n-1)\big(3 - 3r(n-1) + r^2(n-2)n\big)$ are strictly increasing on $[\frac{1}{n},\frac{1}{n-1}]$. 
Expressing $r$ as function of $\tau$ and substituting the result in the expression for $\rho$ directly yields 
\begin{equation*}\label{Phim}
\rho(A_{h_{\pi,u}}) = -1 - \frac{4}{n^2} + \frac{3}{n} + \frac{3\tau(A_{h_{\pi,u}})}{n} 
  - \frac{n-2}{\sqrt{2} n^2 \sqrt{n-1} }(n - 2 + n \tau(A_{h_{\pi,u}}))^{3/2}.\\
\end{equation*}
Based on this interrelation define $\Phi_n:[-1+\tfrac{2}{n},1] \rightarrow [-1,1]$ by
\begin{equation}\label{Phim}
\Phi_n(x)=-1 - \frac{4}{n^2} + \frac{3}{n} + \frac{3x}{n} 
  - \frac{n-2}{\sqrt{2} n^2 \sqrt{n-1} }(n - 2 + n x)^{3/2}
\end{equation}
and set 
\begin{equation}\label{Phi}
\Phi(x) = \left\{
\begin{array}{ll}
-1 & \text{if } x = -1,\\
\Phi_n(x) & \text{if } x \in  \Big[\tfrac{2-n}{n},\tfrac{2-(n-1)}{n-1}\Big] \text{ for some } n\geq 2.
\end{array} \right.
\end{equation}
Since we have $\Phi_n(\tfrac{2-n}{n})=\Phi_{n+1}(\tfrac{2-n}{n})=-1+\tfrac{2}{n^2}$ for every $n \geq 1$ this 
defines a function $\Phi:[-1,1] \rightarrow [-1,1]$. Notice that $\Phi_2(x)=-\tfrac{1}{2} + \tfrac{3x}{2}$, i.e.
on $[0,1]$ $\Phi$ coincides with Daniels' linear bound and for $x_n=\tfrac{2-n}{n}$ and $n \ge 2$ 
we have $(x_n,\Phi(x_n))=p_n$, i.e. $(x_n,\Phi(x_n))$ coincides with the points 
at which Durbin and Stuart's inequality is known to be sharp. 
Furthermore, it is straightforward to 
verify that $\Phi$ is a strictly increasing homemorphism on $[-1,1]$ which is concave on every interval 
$[\tfrac{2-n}{n},\tfrac{2-(n-1)}{n-1}]$ with $n \geq 2$. Figure \ref{region_locale} depicts the function $\Phi$ as
well as some prototypes and their corresponding Kendall's $\tau$ and Spearman's $\rho$.   
\begin{figure}[!h]
\centering
\includegraphics[width=10cm]{region_new_locale.pdf}
\caption{The function $\Phi$ (red) and some prototypes with their corresponding Kendall's $\tau$ and Spearman's $\rho$. 
The shaded region depicts the classical $\tau$-$\rho$-region $\Omega_0$, 
straight lines connecting the points $p_n$ are plotted in green.}
\label{region_locale}
\end{figure} 
Defining the compact set $\Omega_\Phi$ by 
\begin{equation}\label{omegaphi}
\Omega_\Phi=\big\{(x,y)\in [-1,1]^2: \Phi(x)\leq y \leq -\Phi(-x) \big\},
\end{equation}
we can now state the following main result the proof of which is given in the next section.
\begin{thm}\label{mainres}
The precise $\tau$-$\rho$ region $\Omega$ fulfills $\Omega \subseteq \Omega_\Phi$. 
\end{thm}
\begin{rmk}
\emph{
The fact that $\Omega \subseteq \Omega_\Phi$ holds is the principal result of this paper since it improves the
classical inequality by Durbin and Stuart mentioned in the Introduction and, more importantly, gives sharp bounds everywhere. 
In Section 5 we will, however, show that even $\Omega=\Omega_\Phi$ holds and that for every point 
$(x,y) \in \Omega$ there exists a shuffle $h \in \mathcal{S}$ such that
$(\tau(A_h),\rho(A_h))=(x,y)$.
}
\end{rmk}
\begin{rmk}
\emph{
A function similar (but not identical) to $\Phi$ has appeared in the literature in \cite{Shao}, where the authors
tried to deduce sharp bounds of $\Omega$ by running simulations (but did not provide any analytic proof). 
Additionally, it has been brought
to our attention during the preparation of this manuscript that Manuel \'Ubeda-Flores (University of Almer\'ia) already
conjectured Theorem \ref{mainres} (with the exact form of $\Phi$) in a working paper in 2009.   
}
\end{rmk}
 
%------------------------------------------------------------------------------------------
\section{Proof of the main theorem}
Using the properties of $\Omega$ mentioned at the beginning of Section 3, Theorem \ref{mainres} is proved
if we can show that for every $h \in \mathcal{S}^+$ we have $\rho(A_{h}) \geq \Phi(\tau(A_{h}))$. 
Given Lemma \ref{invexplicit} it is straightforward to verify that this is equivalent to showing 
$\invs(h) \leq \varphi(\inv(h))$ for every $h \in \mathcal{S}^+$ whereby $\varphi:[0,\tfrac{1}{2}] \rightarrow [0,\tfrac{1}{6}]$
is defined by
\begin{equation}\label{phi}
\varphi(x) = \left\{
\begin{array}{ll}
\tfrac{1}{6} & \text{if } x = \frac{1}{2},\\
\varphi_n(x) & \text{if } x \in  [\tfrac{1}{2}-\tfrac{1}{2(n-1)},\tfrac{1}{2}-\tfrac{1}{2n}] \text{ for some } n\geq 2
\end{array} \right.
\end{equation}   
and $\varphi_n: [\tfrac{1}{2}-\tfrac{1}{2(n-1)},\tfrac{1}{2}-\tfrac{1}{2n}] \rightarrow [0,\tfrac{1}{6}]$ is given by
\begin{equation}\label{varphin}
\varphi_n(x)=\frac{1}{6} + \frac{1}{3n^2} - \frac{1}{2n} +\frac{x}{n} + \frac{n-2}{6n^2 \sqrt{n-1}}(n-1-2nx)^{3/2}.
\end{equation}
Translating this to $a_\pi(u)$ and $b_\pi(u)$, using eq. (\ref{defab}) and defining 
$\vartheta:[0,\tfrac{1}{2}] \rightarrow [0,\tfrac{1}{6}]$ by $\vartheta(x)=x-2\varphi(x)$
we arrive at the following equivalent form of Theorem \ref{mainres}:
%--------------------thm
\begin{thm}\label{mainresalt}
For every $n \in \mathbb{N}$, $\pi\in \sigma_n$ and $u \in \Delta_n$ the following inequality holds:
\begin{equation}\label{finalineq}
b_\pi(u) \geq \vartheta(a_\pi(u))
\end{equation}
\end{thm} 
We are now going to prove this result and start with some first observations and an outline of the structure of 
the subsequent proof. (i) $\vartheta$ is continuous and, by
calculating the derivative, it is straightforward to see that $\vartheta$ is non-decreasing. 
(ii) $\vartheta(0)=\vartheta(\tfrac{1}{4})=0$ and $\vartheta(\tfrac{1}{2})=\tfrac{1}{6}$. (iii) For every 
prototype $(\pi,u)$ we have equality $b_\pi(u) = \vartheta(a_\pi(u))$. (iv) For given $n$ and fixed $\pi \in \sigma_n$
the functions $v \mapsto a_\pi(v)$ and $v \mapsto b_\pi(v)$ are continuous on $\Delta_n$, so there exists
some $u \in \Delta_n$ minimizing the function $v \mapsto b_\pi(v) - \vartheta(a_\pi(v))$.
(v) For $n\leq 2$ the inequality $b_\pi(u) \geq \vartheta(a_\pi(u))$ trivially holds for every 
$\pi \in \sigma_n$ and every $u \in \Delta_n$, so \textbf{from now on we will only consider the case $n\geq 3$}. \\

The structure of the proof of Theorem \ref{mainresalt} is as follows:
\begin{enumerate}
\item Preliminary Step 1: We prove inequality (\ref{finalineq}) for the case of decreasing $\pi \in \sigma_n$.
\item Preliminary Step 2: We analyze how, for fixed $\pi \in \sigma_n$, the quantities 
$a_\pi(u)$ and $b_\pi(u)$ change if $u \in  \Delta_n$ changes.
\item Induction Step 1: Assuming that the result is true for all 
      $(\pi,u) \in \sigma_m \times \Delta_m$ with $m<n$ we prove inequality (\ref{finalineq}) for 
     $(\pi,u) \in \sigma_n \times \Delta_n$ under the hypothesis that there either exist 
       (i) $p < q < r$ such that $\pi(r) > \pi(q) > \pi(p)$ or 
       (ii) $p<q<r<s$ such that $\pi(q) > \pi(p) > \pi(s) > \pi(r)$ holds.  
\item Induction Step 2: Assuming that the result is true for all 
      $(\pi,u) \in \sigma_m \times \Delta_m$ with $m<n$ we prove inequality (\ref{finalineq}) for 
     $(\pi,u) \in \sigma_n \times \Delta_n$ with $\pi$ not fulfilling the hypothesis in Induction Step I.
\end{enumerate}


\emph{Preliminary Step 1}: Consider $n\geq 3$ and $\pi=(n,n-1,\ldots,2,1)$. 
Note that in this situation we have $e_1(u)=1, e_2(u)=a_\pi(u), e_3(u)=b_\pi(u)$ for every
$u \in \Delta_n$, whereby $e_i$ denotes the $i$-th elementary symmetric polynomial for $i \in \{1,2,3\}$, i.e.
$e_1(v):=\sum_{i}v_i$, $e_2(v):=\sum_{i<j} v_iv_j$ and $e_3(v):=\sum_{i<j<k} v_i v_j v_k$ for every $v \in \mathbb{R}^n$.
Hence $a_\pi(u)$ and $b_\pi(u)$ do not change if we reorder the coordinates of $u$.
%------------------------------------
\begin{lem}\label{step1}
Suppose that $n \geq 3, \pi=(n,n-1,\ldots ,2,1), c_2 \in a_\pi(\Delta_n)$ and that
$u \in \Delta_n$ fulfills $b_\pi(u)=\min \{b_\pi(v): v \in \Delta_n \cap (a_\pi)^{-1}(\{c_2\}) \}$ as well as 
$u_1 \ge \dotsm \ge u_n \ge 0$. Then there exists $m \in \{1, \dotsc, n\}$ such that $u_i = 0$ for every 
$i >m$, and $u_1 = \dotsm = u_{m-1} \ge u_m$. 
\end{lem} 
\begin{proof} Note that continuity of $b_\pi$ and compactness of $\Delta_n \cap (a_\pi)^{-1}(\{c_2\})$ implies the
existence of the minimum.  
We first prove the statement for the case $n = 3$ and suppose that $u$ is a minimizer fulfilling $u_3 \geq u_2 \geq u_1 \geq 0$. 
Define a polynomial $f:\mathbb{R} \rightarrow \mathbb{R}$ by
\[
f(T) = (T-u_1)(T-u_2)(T-u_3) = T^3 -  T^2 + c_2 T - e_3(u),
\]
and let $D_f$ denote the discriminant of $f$.
It is well known that $D_f > 0$ if and only if $f$ has three distinct real zeros and that in case of
$D_f \neq 0$ locally the zeros of $f$ are smooth (so in particular continuous) functions of the coefficients of $f$.

Suppose that $u_1 > u_2 > u_3 > 0$. Then $D_f > 0$.
Let $f_{\varepsilon}(T) = T^3 -  T^2 + c_2 T - (e_3(u)-\epsilon)$, then for small enough values of 
$\epsilon > 0$, the polynomial $f_{\epsilon}$ has three distinct, positive real zeros: 
$u_{\epsilon,1}, u_{\epsilon,2}, u_{\epsilon,3}$.
Then $u_{\epsilon,1} + u_{\epsilon,2} + u_{\epsilon,3} = 1$ and 
$u_{\epsilon,1} u_{\epsilon,2} + u_{\epsilon,2} u_{\epsilon,3} + u_{\epsilon,3} u_{\epsilon,1} = c_2$, while 
$u_{\epsilon,1} u_{\epsilon,2} u_{\epsilon,3} = e_3(u) - \varepsilon < e_3(u)$, contradiction.
So either $u_3 = 0$ or $u_1 = u_2$ or $u_1 > u_2 = u_3 > 0$.
In the first two cases we are done, so suppose that $u_1 > u_2 = u_3 > 0$.
Then $1 = u_1 + 2u_2$ and $c_2 = 2u_1 u_2 + u_2^2$.
Suppose that $u_1 \ge 4 u_2$.
Then $1 \ge 4 c_2$, so there are unique $y_1 \ge y_2 \ge 0$ such that $y_1 + y_2 = 1$ and $y_1 y_2 = c_2$. 
Let $y_3 = 0$, then considering $y=(y_1,y_2,y_3)$ we get $e_1(y) = 1$, $e_2(y) = c_2$, and 
$e_3(y) = 0 < e_3(u)$, contradiction. So $4u_2 > u_1 > u_2$.
Let $y_1 = y_2 = \frac{2u_1+u_2}{3}$ and $y_3 = \frac{4u_2 - u_1}{3}$.
Then $y_1, y_2, y_3 \ge 0$, $e_1(y) = 1$, $e_2(y) = c_2$, and 
$e_3(y) = \frac{1}{27}(2u_1+u_2)^2 (4u_2-u_1) = e_3(u) - \frac{4}{27}(u_1-u_2)^3 < e_3(u)$, contradiction.
This proves the claim for $n = 3$.

Suppose indirectly that the statement is false for some $n >3$.
Then there are $i<j<k$ such that $u_i > u_j \ge u_k > 0$.
Setting $\bar u_l:=\frac{u_l}{u_i+u_j+u_k}$ for every $l \in \{i,j,k\}$ obviously $\bar u_i +\bar u_j +\bar u_k=1$.
Applying the case $n=3$ to $\bar u_i, \bar u_j, \bar u_k$ yields  
$\bar y_i, \bar y_j, \bar y_k \in [0,1]$ such that 
$\bar y_i + \bar y_j + \bar y_k = \bar u_i + \bar u_j + \bar u_k$, $\bar y_i \bar y_j + \bar y_j \bar y_k + 
\bar y_k \bar y_i = \bar u_i \bar u_j + \bar u_j \bar u_k + \bar u_k \bar u_i$ and 
$\bar y_i \bar y_j \bar y_k < \bar u_i \bar u_j \bar u_k$.
Setting $y_l = u_l$ for every $l \in \{1, \dotsc, n\} \setminus \{i,j,k\}$ and $y_l = \bar y_l (u_i+u_j+u_k)$ 
for every $l \in \{i,j,k\}$ finally yields  
$e_1(y) = e_1(u)$, $e_2(y) = e_2(u)$ and $e_3(y) < e_3(u)$, contradiction.
\end{proof}
\begin{cor}
Suppose that $n \geq 3$ and that $\pi=(n,n-1,\ldots,2,1)$. Then $b_\pi(u) \geq \vartheta(a_\pi(u))$ holds for
every $u \in \Delta_n$. 
\end{cor}
\emph{Preliminary Step 2}: We investigate how, for fixed $\pi \in \sigma_n$, the quantities 
$a_\pi(u)$ and $b_\pi(u)$ change if $u \in  \Delta_n$ changes. 
To do so, temporarily extend $a_\pi$ and $b_\pi$ to full $\mathbb{R}^n$ using the identities in 
Lemma \ref{invexplicit}. The following lemmata (whose proof is given in the Appendix) will be crucial in the sequel.
\begin{lem}\label{pertab}
Suppose that $n \geq 3$ and that $\delta=(\delta_1,\ldots,\delta_n) \in \mathbb{R}^n$ fulfills $\sum_{i} \delta_i=0$. Then
for every $t \in \mathbb{R}$ the following identities hold:
\begin{align}
a_{\pi}(u + t\delta) - a_{\pi}(u) &= \alpha_1 t + \alpha_2 t^2 \label{diffa}\\
b_{\pi}(u + t\delta) - b_{\pi}(u) &= \beta_1 t + \beta_2 t^2 + \beta_3 t^3 \label{diffb}
\end{align}
where
\[
\alpha_1 = \sum_i a_i \delta_i, \qquad
\alpha_2 = \sum_{i < j, \, \{i,j\} \in I_{\pi}} \delta_i \delta_j,
\]
\[
\beta_1 = \sum_i b_i \delta_i, \qquad
\beta_2 = \sum_{i<j} c_{i,j} \delta_i \delta_j, \qquad
\beta_3 = \sum_{i<j<k, \{i,j,k\} \in Q_{\pi}} \delta_i \delta_j \delta_k,
\]
and
\[
a_i = \sum_{j: \, \{i,j\} \in I_{\pi}} u_j, \qquad
b_i = \sum_{j<k, \, \{i,j,k\} \in Q_{\pi}} u_j u_k, \qquad
c_{i,j} = c_{j,i} = \sum_{k: \, \{i,j,k\} \in Q_{\pi}} u_k.
\]
 
\end{lem}    
\begin{lem} \label{lemma:triangle-ineq}
Suppose that $n\geq 3$ and that $\pi \in \sigma_n$.
If $p,q,r \in \{1, \dotsc, n\}$ are distinct elements such that $\{p,q,r\} \notin Q_{\pi}$, 
then $c_{p,r} + c_{q,r} \ge c_{p,q} \ge 0$.
\end{lem}
We now state two conditions for $\pi$ that imply the existence of a direction 
$\delta\in \mathbb{R}^n\setminus \{0\}$ with $\sum_{i} \delta_i=0$ 
such that $t \mapsto a_\pi(u+t\delta)-a_\pi(u)$ is identical to zero for every $t$ and 
$t \mapsto b_\pi(u+t\delta)-b_\pi(u)$ is of degree two and concave.  
\begin{lem}\label{sufficientprel}
Suppose that $n\geq 3$, that $\pi \in \sigma_n$, and that one of the following two conditions holds:
\begin{enumerate}
\item[(i)] There exist $p,q,r \in \{1,2,\ldots,n\}$ with $p < q < r$ and $\pi(r) > \pi(q) > \pi(p)$. 
\item[(ii)] There exist $p,q,r,s \in \{1,2,\ldots,n\}$ with $p<q<r<s$ and $\pi(q) > \pi(p) > \pi(s) > \pi(r)$.  
\end{enumerate}
Then there exists $\delta\in \mathbb{R}^n\setminus \{0\}$  
such that the coefficients in (\ref{diffa}) and (\ref{diffb}) fulfill 
$\alpha_1=\alpha_2=\beta_3=0$ and $\beta_2 \leq 0$.
\end{lem}

\emph{Induction Step 1}: We prove the induction step for all $\pi \in \sigma_n$ fulfilling one of the 
conditions in Lemma \ref{sufficientprel}. 
\begin{lem}
Suppose that $n \geq 3$ and that $b_\omega (v) \geq \vartheta(a_\omega(v))$ holds for all 
$(\omega,v) \in \sigma_m \times \Delta_m$ with $m<n$. If $\pi \in \sigma_n$ fulfills one of the 
conditions in Lemma \ref{sufficientprel} then $b_\pi(u) \geq \vartheta(a_\pi(u))$ for every $u \in \Delta_n$.
\end{lem}
\begin{proof}
Suppose that $\pi \in \sigma_n$ fulfills one of the conditions in Lemma \ref{sufficientprel} and consider 
$u \in \Delta_n$. If $u_k=0$ for some $k \in \{1,\ldots,n\}$ then, defining $(\pi',v) \in \sigma_{n-1} \times \Delta_{n-1}$
by $v_i=u_i$ for $i<k$ and $v_i=u_{i+1}$ for $i \geq k$ as well as
$$
\pi'(i) = \left\{
\begin{array}{ll}
\pi(i) & \text{if } i<k \text{ and } \pi(i)<\pi(k)\\
\pi(i)-1 & \text{if } i<k \text{ and } \pi(i)>\pi(k),\\
\pi(i+1) & \text{if } i\geq k \text{ and } \pi(i+1)<\pi(k)\\
\pi(i+1)-1 & \text{if } i \geq k\text{ and } \pi(i+1)>\pi(k),\\
\end{array} \right.
$$
we immediately get $b_\pi(u)=b_{\pi'}(v) \geq \vartheta(a_{\pi'}(v))=\vartheta(a_{\pi}(u))$. 

Suppose now that $u \in (0,1)^n$ and, using Lemma \ref{sufficientprel}, 
choose $\delta \in \mathbb{R}^n\setminus \{0\}$ such that $\beta_2\leq 0$ and $a_\pi(u+t \delta)=a_\pi(u)$ and
$b_\pi(u+t \delta)-b_\pi(u)=\beta_1t + \beta_2 t^2$ for all $t \in \mathbb{R}$.
Considering $u \in (0,1)^n$ there are $t_0 < 0 < t_1$ such that 
$u+t\delta \in [0,1]^n$ if and only if $t \in [t_0, t_1]$. Concavity of $t \mapsto b_{\pi}(u + t \delta)$ 
implies that $b_{\pi}(u + t_0 \delta) \le b_{\pi}(u)$ or $b_{\pi}(u + t_1 \delta) \le b_{\pi}(u)$.
Moreover there are $i,j$ such that $(u+t_0 \delta)_i = 0$ and $(u+t_1 \delta)_j = 0$ by construction, 
so we can proceed as in the first step of the proof and use induction to get $b_\pi(u) \geq \vartheta(a_\pi(u))$.
\end{proof}

\emph{Induction Step 2:} As final step we concentrate on permutations 
$\pi \in \sigma_n$ not fulfilling any of the two conditions in \ref{sufficientprel} and start with the following
definition and the subsequent lemma (whose proof can be found in the Appendix).
\begin{defin}
A permutation $\pi \in \sigma_l$ is called \emph{almost decreasing} if there is at most one 
$i \in \{1, \dotsc, l-1\}$ such that $\pi(i) < \pi(i+1)$.  
\end{defin}
\begin{lem}\label{adequ}
Let $l \geq 1 $ and $\pi \in \sigma_l$. Then the following two conditions are equivalent:
\begin{itemize}
\item
There are no $1 \le p < q < r \le l$ such that $\pi(p) < \pi(q) < \pi(r)$, and there are no $1 \le p < q < r < s \le l$ such that $\pi(r) < \pi(s) < \pi(p) < \pi(q)$.
\item
$\pi$ or $\pi^{-1}$ is almost decreasing.
\end{itemize}
\end{lem}
Having this characterization we can now prove the remaining induction step for those $\pi \in \sigma_n$ fulfilling that 
$\pi$ or $\pi^{-1}$ is almost decreasing. Notice that w.l.o.g. we may assume that $\pi \in \sigma_n$ 
is almost decreasing since defining $v \in \Delta_n$ by 
$v_i = u_{\pi^{-1}(i)}$ for every $i \in \{1, \dotsc, n\}$ yields $a_{\pi}(u) = a_{\pi^{-1}}(v)$ as well as
$b_{\pi}(u) = b_{\pi^{-1}}(v)$. Both subsequent lemmata are therefore only stated and proved for almost decreasing $\pi$.
\begin{lem}
Suppose that $n \geq 3$ and that $b_\omega (v) \geq \vartheta(a_\omega(v))$ holds for all 
$(\omega,v) \in \sigma_m \times \Delta_m$ with $m<n$. If $\pi \in \sigma_n$ is almost decreasing with $\pi(1)=n$ or
$\pi(n)=1$ then $b_\pi(u) \geq \vartheta(a_\pi(u))$ holds for every $u \in \Delta_n$.
\end{lem}
\begin{proof}
As before we may assume $u \in (0,1)^n$. 
Suppose that $\pi(1) = n$. Defining $(\pi',u') \in \sigma_{n-1} \times \Delta_{n-1}$ by
 $\pi'(i)=\pi(i+1)$ and $u'_{i}=\frac{u_{i+1}}{1-u_1}$ for every $i \in \{1,\ldots,n-1\}$ and considering 
\begin{align*}
a_{\pi'}(u') &= \frac{1}{(1-u_1)^2} \sum_{2 \le i<j\le n: \, \{i,j\}\in I_\pi} u_i u_j\\
\end{align*}
yields that $a_\pi(u)= (1-u_1)^2 a_{\pi'}(u') + u_1 (1-u_1)$. Analogously, using 
\begin{align*}
b_{\pi'}(u') = \frac{1}{(1-u_1)^3} \sum_{2 \le i<j<k\le n: \, \{i,j,k\}\in Q_\pi} u_i u_j u_k\
\end{align*}
we get $b_\pi(u) = (1-u_1)^3 b_{\pi'}(u') + u_1 (1-u_1)^2 a_{\pi'}(u')$. 
To simplify notation let $\tilde{\pi}_k$ denote the decreasing permuation in $\sigma_k$ for every $k \in \mathbb{N}$.
Choose $u''_1,...,u''_{n-1} \in \Delta_{n-1}$ such that $a_{\tilde{\pi}_{n-1}}(u'')=a_{\pi'}(u')$ and 
$b_{\tilde{\pi}_{n-1}}(u'')=\vartheta(a_{\pi'}(u'))$. Define $\tilde{u}=(\tilde{u}_1,...,\tilde{u}_n)$ 
by $\tilde{u}_1=u_1$ and $\tilde{u}_i=(1-u_1)u''_{i-1}$ for every $i\in \{2,\ldots,n\}$. Then
 $\sum_{i=1}^n \tilde{u}_i=u_1+(1-u_1)\sum_{i=1}^{n-1}u''_i =1$ and we get
\begin{align*}
a_{\tilde{\pi}_n}(\tilde{u}) &=(1-u_1)^2 a_{\tilde{\pi}_{n-1}}(u'') + u_1 (1-u_1) = a_\pi(u)
\end{align*}
as well as
\begin{align*}
b_{\tilde{\pi}_n}(\tilde{u}) &=  \sum_{1<i<j<k: \, \{i,j,k\}\in Q_{\tilde{\pi}_n}} \tilde{u}_i \tilde{u}_j 
\tilde{u}_k + \tilde{u}_1 \sum_{1<j<k: \, \{j,k\}\in I_{\tilde{\pi}_n}} \tilde{u}_i \tilde{u}_j\\
&= (1-u_1)^3 b_{\tilde{\pi}_{n-1}}(u'')+ u_1 (1-u_1)^2 a_{\tilde{\pi}_{n-1}}(u'').
\end{align*}
Altogether this yields
\begin{align*}
b_\pi(u) &= (1-u_1)^3 b_{\pi'}(u') + u_1 (1-u_1)^2 a_{\pi'}(u')\\
&\ge (1-u_1)^3 \vartheta( a_{\pi'}(u')) + u_1 (1-u_1)^2 a_{\pi'}(u')\\
&= (1-u_1)^3 b_{\tilde{\pi}_{n-1}}(u'') + u_1 (1-u_1)^2 a_{\tilde{\pi}_{n-1}}(u'')= b_{\tilde{\pi}_n}(\tilde{u}) \\
&\geq  \vartheta( a_{\tilde{\pi}_n}(\tilde{u}))= \vartheta(a_\pi(u)).
\end{align*}
The proof of the case $\pi(n)=1$ is completely analogous.
\end{proof}
The following final lemma assures that in case of almost decreasing $\pi \in \sigma_n$ with 
$\pi(1)\not=n$ and $\pi(n)\not=1$ we can not be on the boundary of $\Omega_\Phi$. Note that in the proof we do not make
use of the induction hypothesis.  
\begin{lem}\label{lastlem}
Suppose that $n \geq 3$ and that $\pi \in \sigma_n$ is almost decreasing with $\pi(1)\not=n$ and
$\pi(n)\not=1$. Then for every $u \in \Delta_n \cap (0,1)^n$ we have  
\begin{equation*}
b_\pi(u)-\vartheta(a_\pi(u)) > \min\Big\{b_\omega(v)-\vartheta(a_\omega(v)): \omega \in \sigma_n, \, v \in \Delta_n \Big\}
\end{equation*}
\end{lem}
\begin{proof}
First note that the existence of the minimum is assured by the fact that $\sigma_n$ is finite and $\Delta_n$ is compact. 
Set $k := \pi^{-1}(1)$. Then $1 = \pi(k) < \pi(k-1) < \dotsm < \pi(1) < n$ and $1 < \pi(n)< \dotsm < \pi(k+2) < \pi(k+1)$, 
so $\pi(k+1) = n$.
Define $(\pi',u') \in \sigma_n \times \Delta_n$ as follows: 
$\pi'(i) = \pi(i)$ for $i \notin \{k, k+1\}$, $\pi'(k) = \pi(k+1) = n$ and 
$\pi'(k+1) = \pi(k) = 1$; $u'_i = u_i$ for $i \notin \{k,k+1\}$, $u'_k = u_{k+1}$ and $u'_{k+1} = u_k$.
Then it is straightforward to verify that
\[
a_{\pi'}(u') - a_{\pi}(u) = u_k u_{k+1}
\]
and
\[
b_{\pi'}(u') - b_{\pi}(u) = - \sum_{i \neq k, k+1} u_k u_{k+1} u_i,
\]
holds, which, considering $n \ge 3$ implies $a_{\pi'}(u') > a_{\pi}(u)$ and $b_{\pi'}(u') < b_{\pi}(u)$.
Having this we get $b_{\pi}(u) - \vartheta(a_{\pi}(u)) > b_{\pi'}(u') - \vartheta(a_{\pi'}(u'))$ since 
$\vartheta$ is non-decreasing, which completes the proof.
\end{proof}
Since Lemma \ref{lastlem} implies that in order to prove inequality (\ref{finalineq}) for every $\pi \in \sigma_n$ 
and $u \in \Delta_n$ it is not necessary to consider almost decreasing permutations $\pi$ with $\pi(1)\not=n$ 
and $\pi(n)\not=1$
the proof of Theorem \ref{mainresalt} (hence the one of Theorem \ref{mainres}) is complete.  
%----------------------------------------------------------------------------------------------
\section{Additional related results}
So far we have shown that $\Omega \subseteq \Omega_\Phi$. We now prove that the two sets are in fact identical.
\begin{thm}\label{identical}
The precise $\tau$-$\rho$ region $\Omega$ coincides with $\Omega_\Phi$. In particular, $\Omega$ is not convex.
\end{thm} 
\begin{proof}
The construction of $\Phi$ implies the existence of a family $(A_t)_{t \in [0,1]}$ of shuffles of $M$ fulfilling that
the map $t\mapsto A_t$ is continuous on $[0,1]$ (w.r.t. $d_\infty$) and that
\begin{equation}\label{gamma}
\gamma(t):=(\tau(A_t),\rho(A_t)) = \left\{
\begin{array}{ll}
(4t-1,\Phi(4t-1)) & \text{if } t \in [0,\tfrac{1}{2}]\\
(3-4t,-\Phi(4t-3)) & \text{if } t \in [\tfrac{1}{2},1].
\end{array} \right.
\end{equation} 
Obviously the curve $\gamma:[0,1] \rightarrow [-1,1]^2$ is simply closed and rectifiable. For every $s \in [0,1]$ consider 
similarities $f_s,g_s:[0,1]^2 \rightarrow [0,1]^2$, given by $f_s(x,y)=s(x,y)$ and $g_s(x,y)=(1-s)(x,y)+(s,s)$ and 
define the (ordinal sum) operator $O_s: \kc \rightarrow \kc$ implicitly via 
\begin{align*}
\mu_{O_s(A)}= s \mu_M^{f_s} \,+\, (1-s) \mu_A^{g_s}. 
\end{align*}  
Then we have $d_\infty(O_s(A),O_s(B))\leq d_\infty(A,B)$ for all $A,B \in \kc$ and every $s \in [0,1]$, and the 
mapping $s \mapsto O_s(A)$ is continuous for every $A \in \kc$. 
Consequently, the function $H:[0,1]^2 \rightarrow [-1,1]^2$, given by
\begin{align*}
H(s,t)=\big(\tau(O_s(A_t)), \rho(O_s(A_t))\big)
\end{align*}  
is continuous and fulfills, firstly, that $H(0,t)=\gamma(t)$ and $H(1,t)=(1,1)$ for every $t \in [0,1]$ and, secondly, 
that $H(s,0)=H(s,1)$ for all $s \in [0,1]$. In other words, $H$ is a homotopy and $\gamma$ is homotopic to the
constant curve $(1,1)$, implying $\Omega=\Omega_\Phi$. Since $\Phi$ is strictly concave on each interval 
$[\tfrac{2-n}{n},\tfrac{2-(n-1)}{n-1}]$ with $n\geq 3$, $\Omega=\Omega_\Phi$ cannot be convex.  
\end{proof}
\begin{figure}[!h]
\centering
\includegraphics[width=10cm]{homotopy.pdf}
\caption{The curves $\gamma_s(t)=H(s,t)$ for $t \in [0,1]$ and $s \in \{\tfrac{1}{10},\ldots,\tfrac{9}{10}\}$ with 
$H$ being the homotopy used in the proof of Theorem \ref{identical}.}
\label{homotopy_plot}
\end{figure} 
Considering that the operator $O_s: \kc \rightarrow \kc$ maps the family of all shuffles of $M$ into itself for every
$s\in[0,1]$ the proof of Theorem \ref{identical} has the following surprising byproduct:
\begin{cor}
For every point $(x,y) \in \Omega$ there is a shuffle $h \in \mathcal{S}$ such that $(\tau(A_h),\rho(A_h))=(x,y)$.
\end{cor}
Additionally, Theorem \ref{identical} also implies the following result concerning the possible range of Spearman's $\rho$ 
if Kendall's $\tau$ is known (and vice versa):
\begin{cor}
Suppose that $X,Y$ are continuous random variables with $\tau(X,Y)=\tau_0$.
Then $\rho(X,Y) \in [\Phi(\tau_0),-\Phi(-\tau_0)]$. 
\end{cor}
\begin{rmk}
\emph{Due to the simple analytic form of $\Phi$ is straightforward to verify that
\begin{align*}
\lambda_2(\Omega)=\frac{4}{5}-\frac{4}{5}\, \zeta(3)+\frac{2}{15} \pi^2 \approx 1.1543,
\end{align*}
whereby $\zeta(3)=\sum_{i=1}^\infty \tfrac{1}{i^3}$. Considering that $\lambda_2(\Omega_0)=\tfrac{7}{6}\approx 1.1667$ this underlines the 
quality of the classical inequalities. 
}
\end{rmk} 
%----------------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------------
\section{Appendix}
\begin{proof}[Proof of Lemma \ref{invexplicit}] 
Since the first identity is straightforward to verify we start with the proof of the second one.
Using $s_j^2-s_{j-1}^2=(s_j-s_{j-1})(s_j+s_{j-1})=u_j(2\sum_{k<j}u_k + u_j)$ we get
\begin{align*}\allowdisplaybreaks[4]
 \invs(h_{\pi,u}) &= \sum_{j=1}^n \int_{s_{j-1}}^{s_j} \int_0^1 \mathbf{1}_{[0,y)}(x) 
 \mathbf{1}_{(h_{\pi,u}(y),1]} (h_{\pi,u}(x))(y-x)
     \, d\lambda(x) \, d\lambda(y) \\
 &= \sum_{j=1}^n \int_{s_{j-1}}^{s_j}  \sum_{i: \, i<j, \atop  \pi(i)>\pi(j)} \int_{s_{i-1}}^{s_{i}}  (y-x) \, d\lambda(x)
       \, d\lambda(y) \\
 %&=& \sum_{j=1}^n \int_{s_{j-1}}^{s_j}  \sum_{i: \, i<j, \atop  \pi(i)>\pi(j)} 
 %  \left(y \, u_i-\frac{1}{2}u_i^2 - u_i \sum_{k<i}u_k \right)  \, d\lambda(y) \\
 &= \sum_{j=1}^n \sum_{i: \, i<j, \atop  \pi(i)>\pi(j)} \int_{s_{j-1}}^{s_j}  
    \left(y \, u_i-\frac{1}{2}u_i^2 - u_i \sum_{k:\,k<i}u_k \right)  \, d\lambda(y) \\
 &= \sum_{j=1}^n \sum_{i: \, i<j, \atop  \pi(i)>\pi(j)} \left( \frac{1}{2} u_i u_j 
    \Big(2\sum_{l: \, l<j} u_l + u_j\Big) -\frac{1}{2} u_i^2 u_j - u_i u_j \sum_{k: \, k<i} u_k \right) \\
 &= \sum_{i<j: \atop \pi(i)>\pi(j)} \left( u_i u_j \sum_{l: \, l<j} u_l + 
     \frac{1}{2} u_i u_j^2 -\frac{1}{2} u_i^2 u_j - u_i u_j \sum_{k: \, k<i} u_k \right)\\
 &= \sum_{i<j: \atop \pi(i)>\pi(j)} \left( \frac{1}{2} u_i u_j^2  + \frac{1}{2}u_i^2 u_j + \sum_{k: \, i<k<j}u_i u_j u_k \right). 
\end{align*}
The third identity follows from
\begin{eqnarray*}
b_{\pi}(u) &=& \inv(h_{\pi, u}) - 2\invs(h_{\pi, u})\\
&=& \sum_{k < i < j, \, \pi(i) > \pi(j)} u_i u_j u_k + \sum_{i < k < j, \, \pi(i) > \pi(j)} u_i u_j u_k + 
   \sum_{i < j < k, \, \pi(i) > \pi(j)} u_i u_j u_k   \\
&\phantom{=}& + \sum_{i < j, \, \pi(i) > \pi(j)} u_i^2 u_j + \sum_{i < j, \, \pi(i) > \pi(j)} u_i u_j^2\\
&\phantom{=}& - \sum_{i < j, \, \pi(i) > \pi(j)} u_i^2 u_j - \sum_{i < j, \, \pi(i) > \pi(j)} u_i u_j^2 -  2 \sum_{i < k < j, \, \pi(i) > \pi(j)} u_i u_j u_k  \\
&=& \sum_{i<j<k, \, \pi(j)>\pi(k)} u_i u_j u_k + \sum_{i<j<k, \, \pi(i)>\pi(j)} u_i u_j u_k - \sum_{i<j<k, \, \pi(i) > \pi(k)} u_i u_j u_k \\
&=& \sum_{i<j<k, \atop  \pi(i)>\pi(j)>\pi(k)} u_i u_j u_k + \sum_{i<j<k, \atop  \pi(j)>\pi(i)>\pi(k)} u_i u_j u_k + \sum_{i<j<k, \atop  \pi(j)>\pi(k)>\pi(i)} u_i u_j u_k\\
&\phantom{=}& +  \sum_{i<j<k,\atop  \pi(k)>\pi(i)>\pi(j)} u_i u_j u_k + \sum_{i<j<k, \atop  \pi(i)>\pi(k)>\pi(j)} u_i u_j u_k + \sum_{i<j<k, \atop  \pi(i)>\pi(j)>\pi(k)} u_i u_j u_k\\
&\phantom{=}& - \sum_{i<j<k, \atop  \pi(j)>\pi(i) > \pi(k)} u_i u_j u_k - \sum_{i<j<k, \atop  \pi(i) > \pi(j)>\pi(k)} u_i u_j u_k - \sum_{i<j<k, \atop  \pi(i) > \pi(k)>\pi(j)} u_i u_j u_k\\
&=& \sum_{i<j<k, \atop  \pi(i)>\pi(j)>\pi(k)} u_i u_j u_k + \sum_{i<j<k, \atop  \pi(j)>\pi(k)>\pi(i)} u_i u_j u_k +  \sum_{i<j<k, \atop  \pi(k)>\pi(i)>\pi(j)} u_i u_j u_k. 
\end{eqnarray*}
\end{proof}

\begin{proof}[Proof of Lemma \ref{formulaproto}]
To simplify calculations let $e_i(v)$ denote the $i$-th elementary symmetric polynomial for $i \in \{1,2,3\}$ and
$v \in \mathbb{R}^n$, i.e.
$e_1(v)=\sum_{i}v_i$, $e_2(v)=\sum_{i<j} v_iv_j$ and $e_3(v)=\sum_{i<j<k} v_i v_j v_k$.
Using $\sum_{i} v_i^2 = e_1 (v)^2 - 2e_2 (v)$ it follows that
\begin{align*}
\inv(h_{\pi,u}) &= e_2 (u) = \frac{1}{2}\Big(e_1(u)^2 - \sum_{i} u_i^2 \Big) = \frac{1}{2}\Big(1 - \sum_{i} u_i^2\Big) \\
&= \frac{1}{2}\Big(1 - (n-1)r^2 - (1-(n-1)r)^2\Big)= r (n-1)-\frac{1}{2} r^2 n (n-1).
\end{align*}
Moreover, considering $r \in [\tfrac{1}{n},\tfrac{1}{n-1}]$ we get 
$\inv(h_{\pi,u}) \in [\tfrac{1}{2} - \tfrac{1}{2(n-1)},\tfrac{1}{2} - \tfrac{1}{2n}]$,
implying $\tau(A_{h_{\pi,u}}) \in [-1+\tfrac{2}{n},-1+ \tfrac{2}{n-1}]$, which completes the proof of the first assertion. 
Using $\sum_i v_i^3 = e_1(v)^3 - 3 e_1(v) e_2(v) + 3 e_3(v)$ and Lemma \ref{invexplicit} moreover it follows that
\begin{align*}
\invs(h_{\pi,u}) &= \frac{1}{2} \inv(h_{\pi,u}) -\frac{1}{2} \, b_\pi(h) = 
 \frac{1}{2} e_2(u) -\frac{1}{2} e_3(u) \\
 &= \frac{1}{2} e_2(u) -\frac{1}{2} \Big(\frac{1}{3}\sum_i u_i^3 - \frac{1}{3} e_1(u)^3 + e_1(u) e_2(u)\Big)  \\
&= \frac{1}{2} e_2(u) -  \frac{1}{6}\sum_i u_i^3 + \frac{1}{6}  - \frac{1}{2} e_2(u)  =
    \frac{1}{6}  -  \frac{1}{6}\sum_i u_i^3  \\
&=  \frac{1}{6}  -  \frac{1}{6} \big( (n-1)r^3 + (1-(n-1)r)^3 \big).
\end{align*}
Again considering $r \in [\tfrac{1}{n},\tfrac{1}{n-1}]$ we get 
$\invs(h_{\pi,u}) \in [\tfrac{1}{6}-\tfrac{1}{6(n-1)^2}, \tfrac{1}{6}-\tfrac{1}{6n^2}]$,
implying $\rho(A_{h_{\pi,u}}) \in [-1+\tfrac{2}{n^2},-1+ \tfrac{2}{(n-1)^2}]$, which completes the proof.
\end{proof} 
\begin{proof}[Proof of Lemma \ref{pertab}]
The expression for $a_{\pi}(u + t\delta) - a_{\pi}(u)$ is easily verified:
\begin{align*}
a_{\pi}(u + t\delta) - a_{\pi}(u) &= \sum_{i<j, \, \{i,j\} \in I_{\pi}} ((u_i + \delta_i t)(u_j + \delta_j t) - u_i u_j) \\
&= t \sum_{i<j, \, \{i,j\} \in I_{\pi}} \delta_j u_i +\delta_i u_j + t^2 \sum_{i<j, \, \{i,j\} \in I_{\pi}} \delta_i \delta_j\\
&= t \left( \sum_{j<i, \, \{i,j\} \in I_{\pi}} \delta_i u_j + \sum_{i<j, \, \{i,j\} 
\in I_{\pi}} \delta_i u_j \right)+ t^2 \alpha_2 \\ 
&= t \sum_{i=1}^n \delta_i \sum_{j: \, \{i,j\} \in I_{\pi}} u_j  + t^2 \alpha_2 \\ 
&= t \sum_{i=1}^n \delta_i a_i  + t^2 \alpha_2 =  \alpha_1 t + \alpha_2 t^2 
\end{align*}
To derive the expression for $b_{\pi}(u + t\delta) - b_{\pi}(u)$ notice that
\begin{align*}
b_{\pi}(u + t\delta) - b_{\pi}(u) &= \sum_{i<j<k, \, \{i,j,k\} \in Q_{\pi}} \left((u_i + \delta_i t) (u_j + \delta_j t) (u_k + \delta_k t) - u_i u_j u_k\right)\\
&= \sum_{i<j<k, \, \{i,j,k\} \in Q_{\pi}} \delta_i \delta_j \delta_k t^3+ \delta_i \delta_j u_k t^2 + 
\delta_i \delta_k u_j t^2  \\
&\phantom{=}+ \delta_j \delta_k u_i t^2 + \delta_k u_i u_j t + \delta_j u_i u_k t + \delta_i u_j u_k t \\
&= t^3 \sum_{i<j<k, \, \{i,j,k\} \in Q_{\pi}} \delta_i \delta_j \delta_k\\
&\phantom{=} + t^2 \sum_{i<j<k, \, \{i,j,k\} \in Q_{\pi}} \delta_i \delta_j u_k  + \delta_i \delta_k u_j + \delta_j \delta_k u_i\\
&\phantom{=} + t \sum_{i<j<k, \, \{i,j,k\} \in Q_{\pi}} \delta_k u_i u_j + \delta_j u_i u_k + \delta_i u_j u_k \\
&= \beta_1 t + \beta_2 t^2 + \beta_3 t^3
\end{align*}
since
\begin{align*}
\sum_{i<j<k:\atop \{i,j,k\} \in Q_{\pi}} & \delta_i \delta_j u_k  + \delta_i \delta_k u_j + \delta_j \delta_k u_i \\
&= \sum_{i<j<k:\atop \{i,k,j\} \in Q_{\pi}} \delta_i \delta_j u_k  +  \sum_{i<k<j:\atop \{i,k,j\} \in Q_{\pi}} \delta_i \delta_j u_k +  \sum_{k<i<j:\atop \{k,i,j\} \in Q_{\pi}} \delta_i \delta_j u_k \\
&= \sum_{i<j} \delta_i \delta_j \left( \sum_{i<j<k:\atop \{i,k,j\} \in Q_{\pi}}  u_k  +  \sum_{i<k<j:\atop \{i,k,j\} \in Q_{\pi}} u_k +  \sum_{k<i<j:\atop \{k,i,j\} \in Q_{\pi}} u_k \right)\\
&= \sum_{i<j} \delta_i \delta_j  \sum_{k: \, \{i,k,j\} \in Q_{\pi}}  u_k \\
&= \sum_{i<j} \delta_i \delta_j  c_{i,j} = \beta_2 
\end{align*}
and
\begin{align*}
\sum_{i<j<k:\atop \{i,j,k\} \in Q_{\pi}} & \delta_k u_i u_j + \delta_j u_i u_k + \delta_i u_j u_k\\
&= \sum_{i<j<k:\atop \{i,j,k\} \in Q_{\pi}}  \delta_k u_i u_j + \sum_{i<j<k:\atop \{i,j,k\} \in Q_{\pi}} \delta_j u_i u_k + \sum_{i<j<k:\atop \{i,j,k\} \in Q_{\pi}} \delta_i u_j u_k\\
&= \sum_{j<k<i:\atop \{i,j,k\} \in Q_{\pi}}  \delta_i u_j u_k + \sum_{j<i<k:\atop \{i,j,k\} \in Q_{\pi}} \delta_i u_j u_k + \sum_{i<j<k:\atop \{i,j,k\} \in Q_{\pi}} \delta_i u_j u_k\\
&=\sum_{i=1}^n  \delta_i \left(\sum_{j<k<i:\atop \{i,j,k\} \in Q_{\pi}}   u_j u_k + \sum_{j<i<k:\atop \{i,j,k\} \in Q_{\pi}} u_j u_k + \sum_{i<j<k:\atop \{i,j,k\} \in Q_{\pi}}  u_j u_k \right) \\
&=\sum_{i=1}^n  \delta_i \sum_{j<k}   u_j u_k  =\sum_{i=1}^n  \delta_i b_i =\beta_1.
\end{align*}
\end{proof}

\begin{proof}[Proof of Lemma \ref{lemma:triangle-ineq}]
The inequality $c_{p,q} \ge 0$ immediately follows from $u_1, \dotsc, u_n \ge 0$.
Let
\[
\iota(i,j) = \iota(j,i) = \begin{cases}
1 & \textrm{if } (i<j \textrm{ and } \pi(i) > \pi(j)) \textrm{ or } (j<i \textrm{ and } \pi(j) > \pi(i)), \\
-1 & \textrm{otherwise}
\end{cases}
\]
and
\[
\gamma_{i,j,k} = \frac{1}{2}(1+\iota(i,j)\iota(i,k)\iota(j,k)) \in \{0,1\}
\]
for every $i,j,k \in \{1, \dotsc, n\}$.
Then we have $\{i,j,k\} \in Q_{\pi}$ if and only if $\iota(i,j) \iota(j,k) \iota(i,k) = 1$ if and only if $\gamma_{i,j,k} = 1$.
Therefore $c_{i,j} = \sum_k \gamma_{i,j,k} u_k$ for every $i,j$.
So
\[
c_{p,r} + c_{q,r} - c_{p,q} = \sum_i (\gamma_{p,r,i} + \gamma_{q,r,i} - \gamma_{p,q,i}) u_i
\]
and it is enough to prove $\gamma_{p,r,i} + \gamma_{q,r,i} \ge \gamma_{p,q,i}$ for every $i$.
If $\gamma_{p,q,i} = 0$ or $\gamma_{p,r,i} = 1$ or $\gamma_{q,r,i} = 1$, then this is clear.
So suppose indirectly that $\gamma_{p,q,i} = 1$ and $\gamma_{p,r,i} = \gamma_{q,r,i} = 0$.
Then $\iota(p,q) \iota(p,i) \iota(q,i) = 1$, $\iota(p,r) \iota(p,i) \iota(r,i) = -1$ and $\iota(q,r) \iota(q,i) \iota(r,i) = -1$.
Multiplying these together, we get that $\iota(p,q) \iota(p,r) \iota(q,r) = 1$, so $\gamma_{p,q,r} = 1$.
However $\{p,q,r\} \notin Q_{\pi}$, so $\gamma_{p,q,r} = 0$, contradiction.
\end{proof}

\begin{proof}[Proof of Lemma \ref{sufficientprel}]
(i) Suppose that there are $p < q < r$ such that $\pi(r) > \pi(q) > \pi(p)$.
Let $\delta_i = 0$ for every $i \neq p,q,r$.
We can fix a nonzero solution $(\delta_p,\delta_q,\delta_r) \in \mathbb{R}^3 \setminus \{0\}$ to the 
following system of homogeneous linear equations:
\[
\delta_p +\delta_q +\delta_r = 0, \qquad a_p\delta_p + a_q\delta_q + a_r\delta_r = 0.
\]
Then $\sum_i\delta_i = 0$, $\alpha_1 = 0$, moreover $\{p,q\}, \{p,r\}, \{q,r\} \notin I_{\pi}$ and 
$\{p,q,r\} \notin Q_{\pi}$, so $\alpha_2 = \beta_3 = 0$.
The numbers $\delta_p\delta_q$, $\delta_p\delta_r$, $\delta_q\delta_r$ cannot be all negative, so e.g., 
$\delta_p\delta_q \ge 0$.
Then using Lemma \ref{lemma:triangle-ineq} we obtain
\begin{align*}
\beta_2 &= c_{p,q}\delta_p\delta_q + c_{p,r}\delta_p\delta_r + c_{q,r}\delta_q\delta_r \\
&\le (c_{p,r} + c_{q,r})\delta_p\delta_q + c_{p,r}\delta_p\delta_r + c_{q,r}\delta_q\delta_r \\
&= c_{p,r}\delta_p (\delta_q +\delta_r) + c_{q,r}\delta_q (\delta_p +\delta_r) = 
-c_{p,r}\delta_p^2 - c_{q,r}\delta_q^2 \le 0.
\end{align*}

Now suppose that there are $p<q<r<s$ such that $\pi(q) > \pi(p) > \pi(s) > \pi(r)$.
Let $\delta_i = 0$ for $i \neq p,q,r,s$.
We can fix a nonzero solution $(\delta_p,\delta_q,\delta_r,\delta_s) \in \mathbb{R}^4 \setminus \{0\}$ to 
the following system of homogeneous linear equations:
\[
\delta_p +\delta_q = 0, \qquad\delta_r +\delta_s = 0, \qquad a_p\delta_p + a_q\delta_q + a_r\delta_r + a_s\delta_s = 0.
\]
Then $\sum_i\delta_i = 0$, $\alpha_1 = 0$, and
\[
\alpha_2 =\delta_p\delta_r +\delta_p\delta_s +\delta_q\delta_r +\delta_q\delta_s = (\delta_p +\delta_q)(\delta_r +\delta_s) = 0.
\]
Moreover $\{p,q,r\}, \{p,q,s\}, \{p,r,s\}, \{q,r,s\} \notin Q_{\pi}$, so $\beta_3 = 0$.
We claim that
\[
\beta_2 = -c_{p,q}\delta_p^2 + (c_{p,r} + c_{q,s} - c_{p,s} - c_{q,r})\delta_p\delta_r - c_{r,s}\delta_r^2 \le 0.
\]
Let $d = c_{p,r} + c_{q,s} - c_{p,s} - c_{q,r}$.
Lemma \ref{lemma:triangle-ineq} implies that $c_{p,q} \ge |c_{q,r}-c_{p,r}|$ and $c_{p,q} \ge |c_{p,s}-c_{q,s}|$, so $2c_{p,q} \ge |c_{q,r}-c_{p,r}| + |c_{p,s}-c_{q,s}| \ge |d|$.
Similarly, $c_{r,s} \ge |c_{p,r} - c_{p,s}|$ and $c_{r,s} \ge |c_{q,s}-c_{q,r}|$, so $2c_{r,s} \ge |d|$ too.
Since either $-d \le 0$ or $d \le 0$, the equations
\begin{align*}
2 \beta_2 &= -2c_{p,q}\delta_p^2 + 2d\delta_p\delta_r - 2c_{r,s}\delta_r^2 \\
&= -d(\delta_p -\delta_r)^2 - (2c_{p,q}-d)\delta_p^2 - (2c_{r,s}-d)\delta_r^2 = \\
&= d(\delta_p +\delta_r)^2 - (2c_{p,q}+d)\delta_p^2 - (2c_{r,s}+d)\delta_r^2
\end{align*}
imply that $\beta_2 \le 0$.
\end{proof}

\begin{proof}[Proof of Lemma \ref{adequ}]
Each of the two conditions is true for $\pi$ if and only if it is true for $\pi^{-1}$.
It is easy to see that the second condition implies the first one.
Conversely, suppose that $\pi$ (and hence also $\pi^{-1}$) satisfies the first condition.
We prove by induction on $l$. The statement is trivial for $l = 1$, so let $l \ge 2$.
If $\pi(l) = 1$ then we can use the induction hypothesis for $\pi|_{\{1, \dotsc, l-1\}} \in \sigma_{l-1}$.
If $\pi(1) = l$ then we can use the induction hypothesis for $\pi' \in \sigma_{l-1}$, where $\pi'(i) = \pi(i+1)-1$ 
for every $i \in \{1, \dotsc, l-1\}$.
So we may assume $\pi(1) \neq l$ and $\pi(l) \neq 1$.

Suppose that $\pi^{-1}(l) > \pi^{-1}(1)$ and set $k = \pi^{-1}(l)$.
If $\pi^{-1}(1) < k-1 < k$, then $1 = \pi(\pi^{-1}(1)) < \pi(k-1) < \pi(k) = l$, which contradicts the condition on $\pi$.
Consider $\pi^{-1}(1) = k-1$. If $i < j < k$, then we cannot have $\pi(i) < \pi(j)$, because then we would have 
$\pi(i) < \pi(j) < \pi(k) = l$, contradicting the condition on $\pi$.
If $k-1 < i < j$ then we cannot have $\pi(i) < \pi(j)$, because then we would have 
$1 = \pi(\pi^{-1}(1))=\pi(k-1) < \pi(i) < \pi(j)$, contradicting the condition on $\pi$.
So $\pi(i) > \pi(i+1)$ for every $i \in \{1, \dotsc, l-1\} \setminus \{k\}$, hence $\pi$ is almost decreasing.

Now suppose that $\pi^{-1}(l) < \pi^{-1}(1)$.
If $\pi(l) < \pi(1)$, then the condition on $\pi$ is false for $p = 1$, $q= \pi^{-1}(l)$, $r = \pi^{-1}(1)$, $s = l$.
So $\pi(l) > \pi(1)$ and $(\pi^{-1})^{-1}(l) > (\pi^{-1})^{-1}(1)$. Applying the previous paragraph to 
$\pi^{-1}$ shows that $\pi^{-1}$ is almost decreasing.
\end{proof}




%\appendix



%\section*{Acknowledgements}
%And this is an acknowledgements section with a heading that was produced by the
%$\backslash$section* command. Thank you all for helping me writing this
%\LaTeX\ sample file. See \ref{suppA} for the supplementary material example.

%\begin{supplement}
%\sname{Supplement A}\label{suppA}
%\stitle{Title of the Supplement A}
%\slink[url]{http://www.e-publications.org/ims/support/dowload/imsart-ims.zip}
%\sdescription{Dum esset rex in
%accubitu suo, nardus mea dedit odorem suavitatis. Quoniam confortavit
%seras portarum tuarum, benedixit filiis tuis in te. Qui posuit fines tuos}
%\end{supplement}


\begin{thebibliography}{99}


\bibitem{Dan}
\textsc{Daniels, H. E.} (1950).
Rank correlation and population models. \textit{J. R. Stat. Soc. Ser. B Stat. Methodol.}
\textbf{12} 171--191. 
\MR{0040629}
     
 
\bibitem{Dur}
\textsc{Durante, F.} and \textsc{Sarkoci, P.} and \textsc{Sempi, C.} (2009).
Shuffles of copulas. \textit{J. Math. Anal. Appl.}
\textbf{352} 914--921. 
\MR{2501937} 
   
   
\bibitem{DuS}
\textsc{Durante, F.} and \textsc{Sempi, C.} (2010).
Copula theory: an introduction. In  \textit{Copula theory and its applications, Lecture Notes in Statistics--Proceedings} (P. Jaworski, F. Durante, W. H\"{a}rdle, T. Rychlik) 1--314. Springer, Berlin. 


\bibitem{D+S}
\textsc{Durbin, J.} and \textsc{Stuart, A.} (1951).
Inversions and Rank Correlation Coefficients \textit{J. R. Stat. Soc. Ser. B Stat. Methodol.}
\textbf{13} 303--309.
\MR{0047994}


\bibitem{Em}
\textsc{Embrechts, P.} and \textsc{Lindskog, F.} and \textsc{McNeil, A.} (2001).
Modelling Dependence with Copulas and Applications to Risk Management. In  \textit{Handbook of Heavy Tailed Distributions in Finance} (S. T. Rachev) 329--384. Elsevier, Amsterdam. 


\bibitem{FreNe}
\textsc{Fredricks, G. A.} and \textsc{Nelsen, R. B.} (2007). On the relationship between Spearman's rho and Kendall's tau for pairs of continuous random variables. \textit{J. Statist. Plann. Inference} \textbf{137} 2143--2150.
\MR{2325421}


\bibitem{Ge}
\textsc{Genest, C.} and \textsc{Ne\v{s}lehov\'a, J.} (2009).
Analytical proofs of classical inequalities between Spearman's $\rho$ and Kendall's $\tau$. \textit{J. Statist. Plann. Inference}
\textbf{139} 3795–-3798.
\MR{2553765}


\bibitem{Ka}
\textsc{Kallenberg, O.} (1997). \textit{Foundations of modern probability}. Springer, New York Berlin Heidelberg.
\MR{1464694}

\bibitem{Kl}
\textsc{Klenke, A.} (2008). \textit{Probability Theory - A Comprehensive Course}. Springer, Berlin Heidelberg.
\MR{2372119}



\bibitem{Kr}
\textsc{Kruskal, W. H.} (1958).
Ordinal measures of association. \textit{J. Amer. Statist. Assoc.}
\textbf{53} 814--861.
\MR{0100941}
 

%\bibitem{Ku}
%\textsc{Kunze, H.} and \textsc{La Torre, D.} and \textsc{Vrscay, E. R.} (2012). \textit{Fractal Based Methods in Analysis}. Springer, New York Dordrecht Heidelberg London.
%\MR{3014680}


\bibitem{Lan}
\textsc{Lancaster, H. O.} (1963).
Correlation and complete dependence of random variables. \textit{Ann. Statist.}
\textbf{34} 1315--1321.
\MR{0154376}

 
\bibitem{Mish}
\textsc{Mikus\'inski, P.} and \textsc{Sherwood, H.} and \textsc{Taylor, M. D.} (1992).
Shuffles of Min. \textit{Stochastica}
\textbf{13} 61--74.
\MR{1197328} 
  

\bibitem{Ne}
\textsc{Nelsen, R. B.} (2006). \textit{An Introduction to Copulas}.
Springer, New York.
\MR{2197664}  


\bibitem{SaUl}
\textsc{Sack, J.} and \textsc{\'Ulfarsson, H.} (2012).
Refined inversion statistics on permutations. \textit{Electron. J. Combin.}
\textbf{19} P29. 
\MR{2880660}

\bibitem{SchW}
 \textsc{Schweizer, E.} and \textsc{Wolff, E.F.} (1981). On nonparametric measures of 
  dependence for random variables. \textit{Ann. Stat.} \textbf{9} 879-885.
  \MR{0619291}

\bibitem{Sem2}
\textsc{Sempi, C.} (2011).
Copulae: Some mathematical aspects. \textit{Appl. Stoch. Models Bus. Ind.}
\textbf{27} 37--50.
\MR{2752452}


\bibitem{Shao}
\textsc{Shao, W.} and \textsc{Guo, G.} and \textsc{Zhao, G.} and \textsc{Meng, F.} (2014).
Simulated annealing for the bounds of Kendall's $\tau$ and Spearman's $\rho$. \textit{J. Stat. Comput. Simul.}
\textbf{84} 2688--2699.
\MR{3250967}


\bibitem{Sib}
\textsc{Siburg, K. F.} and \textsc{Stoimenov, P. A.} (2010).
A measure of mutual complete dependence. \textit{Metrika}
\textbf{71} 239--251.
\MR{2602190}



\bibitem{Tru}
\textsc{Trutschnig, W.} (2011).
On a strong metric on the space of copulas and its induced dependence measure. \textit{J. Math. Anal. Appl.}
\textbf{384} 690--705.
\MR{2825218}


\end{thebibliography}

\end{document}

1502.04620.extracted_bib
{Dan \textsc{Daniels, H. E. (1950). Rank correlation and population models. J. R. Stat. Soc. Ser. B Stat. Methodol. 12 171--191. \MR{0040629
1502.04620.extracted_bib
{Dur \textsc{Durante, F. and \textsc{Sarkoci, P. and \textsc{Sempi, C. (2009). Shuffles of copulas. J. Math. Anal. Appl. 352 914--921. \MR{2501937
1502.04620.extracted_bib
{DuS \textsc{Durante, F. and \textsc{Sempi, C. (2010). Copula theory: an introduction. In Copula theory and its applications, Lecture Notes in Statistics--Proceedings (P. Jaworski, F. Durante, W. H\"{ardle, T. Rychlik) 1--314. Springer, Berlin.
1502.04620.extracted_bib
{D+S \textsc{Durbin, J. and \textsc{Stuart, A. (1951). Inversions and Rank Correlation Coefficients J. R. Stat. Soc. Ser. B Stat. Methodol. 13 303--309. \MR{0047994
1502.04620.extracted_bib
{Em \textsc{Embrechts, P. and \textsc{Lindskog, F. and \textsc{McNeil, A. (2001). Modelling Dependence with Copulas and Applications to Risk Management. In Handbook of Heavy Tailed Distributions in Finance (S. T. Rachev) 329--384. Elsevier, Amsterdam.
1502.04620.extracted_bib
{FreNe \textsc{Fredricks, G. A. and \textsc{Nelsen, R. B. (2007). On the relationship between Spearman's rho and Kendall's tau for pairs of continuous random variables. J. Statist. Plann. Inference 137 2143--2150. \MR{2325421
1502.04620.extracted_bib
{Ge \textsc{Genest, C. and \textsc{Ne\v{slehov\'a, J. (2009). Analytical proofs of classical inequalities between Spearman's $\rho$ and Kendall's $\tau$. J. Statist. Plann. Inference 139 3795–-3798. \MR{2553765
1502.04620.extracted_bib
{Ka \textsc{Kallenberg, O. (1997). Foundations of modern probability. Springer, New York Berlin Heidelberg. \MR{1464694
1502.04620.extracted_bib
{Kl \textsc{Klenke, A. (2008). Probability Theory - A Comprehensive Course. Springer, Berlin Heidelberg. \MR{2372119
1502.04620.extracted_bib
{Kr \textsc{Kruskal, W. H. (1958). Ordinal measures of association. J. Amer. Statist. Assoc. 53 814--861. \MR{0100941 %
1502.04620.extracted_bib
{Ku %\textsc{Kunze, H. and \textsc{La Torre, D. and \textsc{Vrscay, E. R. (2012). Fractal Based Methods in Analysis. Springer, New York Dordrecht Heidelberg London. %\MR{3014680
1502.04620.extracted_bib
{Lan \textsc{Lancaster, H. O. (1963). Correlation and complete dependence of random variables. Ann. Statist. 34 1315--1321. \MR{0154376
1502.04620.extracted_bib
{Mish \textsc{Mikus\'inski, P. and \textsc{Sherwood, H. and \textsc{Taylor, M. D. (1992). Shuffles of Min. Stochastica 13 61--74. \MR{1197328
1502.04620.extracted_bib
{Ne \textsc{Nelsen, R. B. (2006). An Introduction to Copulas. Springer, New York. \MR{2197664
1502.04620.extracted_bib
{SaUl \textsc{Sack, J. and \textsc{\'Ulfarsson, H. (2012). Refined inversion statistics on permutations. Electron. J. Combin. 19 P29. \MR{2880660
1502.04620.extracted_bib
{SchW \textsc{Schweizer, E. and \textsc{Wolff, E.F. (1981). On nonparametric measures of dependence for random variables. Ann. Stat. 9 879-885. \MR{0619291
1502.04620.extracted_bib
{Sem2 \textsc{Sempi, C. (2011). Copulae: Some mathematical aspects. Appl. Stoch. Models Bus. Ind. 27 37--50. \MR{2752452
1502.04620.extracted_bib
{Shao \textsc{Shao, W. and \textsc{Guo, G. and \textsc{Zhao, G. and \textsc{Meng, F. (2014). Simulated annealing for the bounds of Kendall's $\tau$ and Spearman's $\rho$. J. Stat. Comput. Simul. 84 2688--2699. \MR{3250967
1502.04620.extracted_bib
{Sib \textsc{Siburg, K. F. and \textsc{Stoimenov, P. A. (2010). A measure of mutual complete dependence. Metrika 71 239--251. \MR{2602190
1502.04620.extracted_bib
{Tru \textsc{Trutschnig, W. (2011). On a strong metric on the space of copulas and its induced dependence measure. J. Math. Anal. Appl. 384 690--705. \MR{2825218