\documentclass[]{amsart}
%\input{quasi-preamble.tex}

\usepackage{verbatim}    % verbatim classes
\usepackage{url} % appropriately display url's
\usepackage{hyperref} \hypersetup{breaklinks=true,
  colorlinks= true, linkcolor=black, hyperfootnotes= false, urlcolor=blue }
\urlstyle{same}

\usepackage{longtable}
\usepackage{graphicx}
\usepackage{amssymb}% extra common ams symbols
\usepackage{mathrsfs} % Adds Script Fonts for Curly
\usepackage{ifsym}  % lots of symbols, weather, clocks,
\usepackage{enumerate}   % improved enumeration
\usepackage{fancyhdr}    % super headers --recommended


\newtheorem{theorem}{Theorem} %[section]
\renewcommand{\thetheorem}{\arabic{theorem}}
\newtheorem*{theorem*}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}

%\newtheorem{question}{Question}
%\newtheorem*{question*}{Question}
%\newtheorem{conjecture}{Conjecture}
%\newtheorem*{conjecture*}{Conjecture}

\theoremstyle{definition}
\newtheorem{problem}{Problem}
 \newtheorem{definition}{Definition}%[section]
%\newtheorem{definition}[theorem]{Definition}
\newtheorem*{definition*}{Definition}
\newtheorem{example}{Example}
%\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}

\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{remarks}{Remarks}
\newtheorem{note}[theorem]{Note}
\newtheorem{case}[theorem]{Case}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
% \newtheorem{remark}{Remark}[section]


\numberwithin{equation}{section}

% Here are the Blackboard letters for rings and spaceforms
\newcommand{\T}{\mathbb{T}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}


% Font Types
\newcommand{\mc}{\mathcal}
\newcommand{\mbf}{\mathbf}
\newcommand{\mb}{\mathbb}
\newcommand{\bb}{\mathbb}
\newcommand{\mf}{\mathfrak}
\newcommand{\msf}{\mathsf}
\newcommand{\scr}{\mathscr}

%Greek
\newcommand{\Ga}{\Gamma}
\newcommand{\ga}{\gamma}
\newcommand{\eps}{\epsilon }
\newcommand{\La}{\Lambda}
\newcommand{\la}{\lambda}
\newcommand{\al}{\alpha}
\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\up}{\upsilon}
\newcommand{\om}{\omicron}

%Miscellaneous symbols
\newcommand{\op}[1]{\operatorname{#1}}
\newcommand{\set}[1]{\left\{#1 \right\}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\union}{\cup}
\newcommand{\intersect}{\cap}
\newcommand{\semidirect}{\ltimes}
\newcommand{\directsum}{\oplus}
\newcommand{\grad}{\nabla}
\newcommand{\rest}[2]{ #1_{\downharpoonleft_{#2}} }
\newcommand{\dvol}{dg}
\newcommand{\del}{\partial }
\newcommand{\pa}{\partial }
\newcommand{\degree}{^\circ}
\newcommand{\degrees}{^\circ}
\newcommand{\goto}[1]{\stackrel{#1}{\longrightarrow}}
\newcommand{\ident}{\equiv }
\newcommand{\comp}{\circ }
\newcommand{\argmax}{\mathop{\rm argmax}}
\newcommand{\smallcircle}{ {\scriptstyle \; \circ \; }   }
\newcommand{\s}{\scriptscriptstyle}
\newcommand{\toarrow }{\!   \to   }
\newcommand{\suchthat }{     \! \!  :  }
\newcommand{\of}{  \hspace{-1pt}  \smallcircle    \hspace{-1pt} }
\newcommand{\tensor}{\otimes }
\newcommand{\minus}{\tiny{-}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert }
\newcommand{\norm}[1]{\left\| #1 \right\| }
\newcommand{\inner}[1]{\left\langle #1 \right\rangle }
\newcommand{\dd}[1][t]{\frac{d}{d #1} }
\newcommand{\dds}[1][t]{\frac{d^2}{d #1}^2 }
\newcommand{\omicron}{\circ}
\newcommand{\conv}{\circledast}
\newcommand{\til}{\widetilde}
\newcommand{\ds}{\displaystyle}

\renewcommand{\hat}{\widehat}

\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}

\author{Chris Connell$^\dagger$}
\thanks{$^\dagger$Supported in part by Simons Foundation Grant \#210442}
\address{Department of Mathematics, Indiana University}
\email{connell@indiana.edu}
\author{Eric B. Rasmusen$^\ddagger$}
\thanks{$^\ddagger$Supported in part by Olin Center, Harvard Law School}
\address{Department of Business Economics and Public Policy, Kelley
School of Business, Indiana University}
\email{erasmuse@indiana.edu}


\title{Concavifying the quasiconcave}


%----------------------------------------------------------

%:   Indiana University,  Department of
%Mathematics, Rawles Hall,
%RH 351,   Bloomington,
%Indiana, 47405.     (812) 855-1883. Fax:(812) 855-0046.
%\href{mailto:connell@indiana.edu}{connell@indiana.edu}.
%
%\noindent
%Eric Rasmusen, Department of Business Economics and Public Policy, Kelley
%School of Business, Indiana University. BU 438, 1309 E. 10th Street,
%Bloomington, Indiana,
%47405-1701. (812) 855-9219. Fax: 812-855-3354.
%\href{mailto:erasmuse@indiana.edu}{erasmuse@indiana.edu},
%\url{http://rasmusen.org}.

% \noindent
%   This paper:
%\url{http://rasmusen.org/papers/connell-rasmusen.quasiconcavity.pdf}.\\
% Mathematica and diagram files: \url{http://rasmusen.org/papers/quasi}.
%
% \noindent
%  Keywords: quasiconcavity, quasiconvexity, concavity,
%convexity, unique maximum, maximization. JEL Code: C61. 
%
%  We would like to thank  Per Hjertstrand and  participants in the BEPP Brown Bag Lunch
%for
%comments, and Dan Zhao for research assistance.
\begin{document}
\begin{abstract}
We revisit a classic question of Fenchel from 1953: Which quasiconcave functions can be concavified by post-composition with a monotonic transformation? This question has a long history in economics utility theory. While many authors have given partial answers  under various assumptions, we offer a complete characterization for quasiconcave functions without a priori assumptions on regularity. The answer hinges on the local regularity class of the function.

We establish this characterization of concavifiability for continuous functions whose domain is any arbitrary geodesic metric space. Under the additional assumption of twice differentiability, we also provide simpler necessary and sufficient conditions for concavifiability on Riemannian manifolds which essentially generalize those given by Kannai for the Euclidean case.
%Lastly we present the approximation result that if a function $f$ is either weakly or strongly quasiconcave then there exists an arbitrarily close strictly concavifiable approximation $h$ to $f$.

\end{abstract}

\maketitle


\section{Introduction}

Quasiconcavity is a property of a function which, if strict, guarantees a unique global
maximum on any compact convex domain. As the name suggests, it weakens the
property of concavity, and has found wide application in economics and other fields. The
purpose of this paper is to further analyze a natural way to link quasiconcavity to
concavity: by means of a monotonically increasing transformation. We will show that to say
a continuous function is strictly quasiconcave is close, in a specific sense, to saying it
can be made concave by a post-composing with a strictly increasing function.  Almost any
sufficiently regular quasiconcave function can  be concavified this way. Any function that
is not quasiconcave cannot be concavified by post-composition.

The ``almost'' above refers to the two additional qualifications  beyond quasiconcavity  that must be required of the function after concavifying one monotonic slice--- which can always be done even if the function is not continuous. (It turns out to be easy to reduce the question of concavifiability of a monotonic discontinuous function $f$ to that of an associated function which must be continuous to be concavifiable.) These qualifications, which appear as regularity assumptions involving upper derivatives (see Section \ref{sec:nonmonotonic}), are most easily stated for the case when the domain of the objective function $f$ is an interval $(a,b)\subset\R$. This leads to our first main result.

{
%\renewcommand{\thetheorem}{\ref{thm:1-d}}
\begin{theorem}
For any continuous nonmonotonic function $f\suchthat  (a,b) \toarrow \R$, there is a function $g
\suchthat   \op{Range(f)} \toarrow   \R$ such that $g \of f$ is strictly concave if and
only if
\begin{enumerate}[(i)]
\item
 $f$ or $-f$ is strictly  quasiconcave achieving it's maximum at $m\in (a,b)$. 
\item
 for $h  =  \rest{f} {(a,m]}^{\scriptscriptstyle -1}$,  the function $h
\of  \rest{f} {(m,b)}$  and its inverse are locally Lipschitz.
\item 
$\log \abs{\overline{D}(h \of f)}\in\op{BV}_{loc}((m,b))$.
\end{enumerate}
Moreover, when $g$ exists it is strictly monotone.
\end{theorem}
}

The general case for  arbitrary (complete) geodesic metric space domains is similar:
{
%\renewcommand{\thetheorem}{\ref{thm:metric}}
\begin{theorem}
Let $X$ be any geodesic metric space.
For any continuous function $f\suchthat   X\toarrow  \R$
there is a function $g  \suchthat  \op{Range(f)}\toarrow  \R$  such that $g
\of  f$ is strictly concave if and only if:

\begin{enumerate}
\item[(i)]
 Either $f$ or $-f$ is strictly quasiconcave with maximum

\item[(ii)] $h\of f$ is locally Lipschitz on $X-\set{m}$ where $h=(f\of\ga_o)^{-1}$
for some geodesic $\ga_o$ in
$X$ ending at $m$ such that $\op{Range}(f\of \ga_o)=\op{Range}(f)$. Moreover
$\overline{D}(h\of f \of \ga)$ does not vanish on any geodesic segment $\ga\suchthat
(0,1)\to X$ for which $h\of f\of \ga$ is strictly increasing.

\item[(iii)] The total variation of $\log \overline{D} (h\of f)$ along all geodesics
$\ga\suchthat [0,1]\to X$
for
which $h\of f\of \ga$ is strictly increasing is uniformly bounded away from the
extrema of $h\of f$,  or in
other words,
\begin{equation*} %\label{e17}
\inf_{\ga}\set{[\overline{D}(\log \overline{D}(h\of f\of \ga)^{-1})]^- }\in
L^1_{loc}(R).
\end{equation*}
(Here $R$ is the interior of the range of $f$ and the infimum is taken over all
geodesic segments $\ga\suchthat [0,1]\to X$ for which $h\of f\of \ga$ is strictly
increasing.)
\end{enumerate}
\end{theorem}
}
%
%We refer the reader to Theorems \ref{thm:1-d} and \ref{thm:metric} for the precise statements. 
%An extension is that certain  quasiconcave functions that are not only nondifferentiable but discontinuous   can also be characterized this way, including all monotonic discontinuous functions.

Our topic goes back to the origins of the study of quasiconcavity starting in the 1940's found in papers by DeFinetti \cite{DeFinetti}  and  Fenchel \cite{Fenchel} (who invented the name, as Guerraggio \&  Molho explain in their history \cite{Guerragio}). Both DeFinetti (in
his ``second problem") and Fenchel investigated whether any quasiconcave function could
be transformed into a concave function, which with related problems is surveyed in
\cite{Rapsak} (see also Section 9 of \cite{Aumann}).  Kannai \cite{Kannai:77} (and more elaborately in \cite{Kannai:81}) treats the question in depth in the context of utility
functions, giving  conditions under which, in the language of economics, continuous convex preference orderings can be represented by concave utility functions.  Richter \& Wong \cite{Richter} and Kannai \cite{Kannai:05} similarly address  preferences over discrete sets. We will discuss some of Kannai's conditions in greater detail in Section \ref{sec:Riemannian} below where we prove the following generalization for Riemannian manifolds. (See that section for definitions of $f_{ij}$ and $\la_i$.)
{
%\renewcommand{\thetheorem}{\ref{thm:manifold}}
\begin{theorem} %\label{thm:manifold}
%\refstepcounter{theoremcounter} \label{thm:c2}
Let $M^n$ be a $C^2$ Riemannian manifold, possibly with boundary.  For
any twice-differentiable function $f\suchthat M\toarrow
\R$ there is a strictly increasing twice-differentiable $g
\suchthat  \R \toarrow  \R$  such that $g \of  f$ is strictly concave if and only if:
\begin{enumerate}
\item[(i)]
 $f$ is strictly quasiconcave;
\item[(ii)]
$\grad f$ does not vanish on the interior of $M$ except possibly at the maximum point of
$f$,
\item[(iii)] The function 
\begin{equation*} %\label{e20}
q(t)=\inf_{x\in f^{-1}(t)}
\frac{1}{\norm{\nabla f(x)}^2} \left(-f_{11}(x)-\sum_{j=2}^n
\frac{f_{1j}^2(x)}{\lambda_j(x)\norm{\nabla f(x)}}\right)
\end{equation*}
has negative part $q^{-}$ belonging to $L^1_{loc}(R)$, where $R$ is the interior of the range of $f$.
\end{enumerate}

 A suitable $g$ is 
\begin{equation*} %\label{g-function}
 g(z)=\int_{f(m)}^z e^{\int_{f(m)}^s (-1+q^{-}(t))\,dt}\,ds. 
\end{equation*}  
\end{theorem}
\addtocounter{theorem}{-3}
}
%-------------------------------------------------
\bigskip
\paragraph{\bf Acknowledgements.} 
We would like to thank  Per Hjertstrand and Dan Zhao for helpful comments. 

\section{Preliminaries}


 
\begin{definition}\label{def:qc}
(quasiconcavity)   A  function $f$ defined on a subset $D\subset\R^n$ is {\em weakly
quasiconcave} if for any two distinct points
 $ x',x''\in D$ and any number $t \in (0,1)$ with $t x'+ (1-t)x''\in D$, we have
 \begin{equation}  \label{e3}
 f(t x'+ (1-t)x'')  \geq  \min\set{f(x'), f(x'')}.
\end{equation}
We say that $f$ is {\em strictly quasiconcave} if the inequality is strict whenever $x'\neq x''$, .
\end{definition}

If $-f$ is strictly  quasiconcave  then $f$ is    {\em strictly  quasiconvex}. If $-f$ is
weakly quasiconcave  then $f$ is    {\em weakly  quasiconvex}.

Compare the right-hand side of \eqref{e3} to the condition for concavity,
\begin{equation} \label{eq:quasi2}
f(tx'+ (1-t)x'')  \geq  t f(x') + (1-t) f(x'') .
\end{equation}
 
%\begin{definition}\label{def:con}
% (CONCAVITY)  A  function $f$ defined on a subset $D\subset \R^n$ is {\em concave} iff
%for any two points $ x',x''\in
%D$ and any number $t \in (0,1)$ with $t x'+ (1-t)x''\in D$, we have
% \begin{equation} \label{eq:quasi2}
% f(tx'+ (1-t)x'')  \geq  t f(x') + (1-t) f(x'') .
%\end{equation}
% Iff  inequality  \eqref{eq:quasi2} is strict, we say that $f$ is strictly
%concave; otherwise it is weakly concave or simply ``concave''.
%\end{definition}
 

% \begin{figure}[ !ht]
%  \centering
% \includegraphics[width=3in]{quasifig02-concavifying}
%\caption{\sc   A Non-Concave Strictly  Quasiconcave Function $f(x)$ that
%  Can Be Concavified by a Monotonic  $g(f)$ }
% \label{quasi3}
% \vspace*{24pt}
% \end{figure}
We will be looking at whether  given a quasiconcave $f$ we can always find a strictly
monotonic function $g$ that will transform  $f$ to a strictly concave $g\of f$. 
%Figure \ref{quasi3} shows an example of a  strictly quasiconcave function $f(x)$ that is not
%concave, and a compound function $g(f(x))$ that is strictly concave. 

Many of the difficulties in concavifying quasiconcave functions already arise when the
function's domain is just $\R$, so this will be the focus of the rest of the current section. 
As the complexity of the domain increases, these issues become harder to detect,
even in the case of $\R^2$, as may be seen from Figure \ref{quasifig-aumann.jpg}'s
example:

\begin{example}\label{ex:Aumann}
{\bf Fenchel's example.}  The function $f(x, y)   = y +\sqrt{x + y^2}$, graphed in Figure
\ref{quasifig-aumann.jpg}, cannot be concavified. This was first proposed by
\cite{Fenchel} and features in \cite{Aumann}. The function is strictly increasing in both
$x$ and $y$,  and  strictly concave in each variable separately. It is only weakly
quasiconcave, however, because its level sets are straight lines, as shown in the
right-hand side of Figure \ref{quasifig-aumann.jpg}. %As a result,
% $f$ is not
%concavifiable, and, more surprisingly, is not even weakly concavifiable.
\begin{figure}[ht]
 \centering
 \includegraphics[width=4in]{quasifig04-aumann}
\caption{\sc   Fenchel's Example:  Nonconcavifiable with Linear Level Sets. }
 \label{quasifig-aumann.jpg}
 \end{figure}
To see that it cannot be weakly concavified, we note that for any postcomposition by
a strictly increasing function $g$, the rate of increase of the function $g\of f$ from
point $a$ to point $b$ is greater than that of the same length segment from $d$ to $e$. More
precisely, the gradient at $a$ is larger than the gradient at $c$. Hence, if we choose the
point $b$ sufficiently close to $a$, the level sets with values slightly larger than
$g(f(a))$, but less than $g(f(b))$, must lie under the segment connecting $(c,g(f(c)))$ to
$(b,g(f(b))$ near the point $(c,g(f(c))$. Hence part of the graph of $g\of f$ lies over
the line segment from $(c,g(f(c)))$ to $(b,g(f(b))$. Consequently, $g\of f$ could not have
been weakly concave. %\\ \hspace*{18pt}A word of
%caution regarding this intuitive proof: it depends crucially on the fact that the level
%sets are only weakly convex.  If they were strictly convex, even ever so slightly, then
%the function $f$ would be concavifiable (see Theorem \ref{thm:manifold}).  In that case,
%$g$ could be chosen in such a way that the gradient would change rapidly so that that the
%point $b$ must be chosen very close to $a$ in order for the linear gradient approximation
%to remain valid. However, then the line segment from $c$ to $b$ would lie mostly to the
%left of the bent level set on which $a$ and $c$ lie, and thus it would not cross, near
%$c$, the other level sets in the domain with values greater than $g(f(c))$.
\end{example}

Consider a function $f  \suchthat
I\toarrow    \R$  defined on an interval $I\subset \R$ which is either  open (in
which case it might be unbounded), half open, or closed. For the rest of the paper we
will define  $a =  \inf(I)$ and   $b  =  \sup(I)$.
% and $f^*  =   \sup(f)$. % % Not used.

The following lemma explains why we may restrict our attention to the case when the postcomposing function $g$ is strictly increasing.

\bigskip
\bigskip %was newpage
\begin{lemma}\label{lem:g}
  Given continuous functions $f\suchthat D\to \R$ with $D\subset \R$ connected and $g
\suchthat\op{Range(f)}\to \R$,
for $g\of f$ to be strictly
quasiconcave it is necessary that $f$ and $g$ fall into precisely one of these four
cases:
 % \vspace{-16pt}
\begin{enumerate}[(i)]
  \item $f$ is strictly increasing and $g$ is strictly quasiconcave,
  \item $-f$ is strictly increasing and $-g$ is strictly quasiconcave,
  \item $f$ is strictly quasiconcave but not monotone and $g$ is strictly increasing,
or
  \item $-f$ is strictly quasiconcave but not monotone and $-g$ is strictly
increasing.
\end{enumerate}

\end{lemma}


\begin{proof}
The cardinality $\op{card}( (g\of f)^{-1}(t))$ of the level set of  value $t$ for $g\of
f$ is \\
 $\sum_{s\in g^{-1}(t)}
\op{card}(f^{-1}(s))$. In particular, postcomposition
by a function never  reduces a level set's  cardinality. The maximum cardinality of a
level set of the strictly quasiconcave
function $g\of f$ is two. Hence on values where
the level sets of $f$ have cardinality two, $g$ must be one-to-one, and $g$ can only be
two-to-one on values where $f$
has cardinality one. Such continuous functions
are fairly simple to analyze.

If all the level sets of $f$ have cardinality one everywhere then $f$ is monotone by
continuity and we are in  case (i) or (ii). Then $g$ or $-g$ must be quasiconcave since
the
composition of the strictly increasing function $f^{-1}$ (or $(-f)^{-1}$) with the
quasiconcave function $g\of f$ is again quasiconcave.

If the cardinality of the level sets of $f$ is two on a subset $L\subset \op{Range}(f)$, then
consider any $p\in L$. Let $\set{x,y}=f^{-1}(p)$, with $x<y$, and let $\set{U_i}$ be any
sequence of connected open intervals centered at $p$ and strictly decreasing to $p$. By
continuity of $f$, the preimages of each $U_i$ under $f$  are open and contain  both
$x$ and $y$. Since each point has at most two preimages, for some sufficiently large $i$,
the open subintervals $A$ containing $x$ and $B$ containing $y$ in $f^{-1}(U_i)$
must be distinct, and hence disjoint. If $C=f(A)\cap f(B)$, then $f$ must be monotone on
$f^{-1}(C)\cap A$ and $f^{-1}(C)\cap B$. Now $C$, being connected, either has
interior, or else is just $p$. If it is just $p$, some points are  to the right of $x$
and have values less than $p$ and some points are to the left of $y$  and  have values
greater
than $p$. Hence, the intermediate value theorem guarantees, since $D$ is connected,
another point $z\in (x,y)\subset D$ for which $f(z)=f(x)=f(y)=p$, which violates the
cardinality restriction on the level sets. Therefore, we conclude that each point $p\in
L$ contains an interval about it, a priori not necessarily in $L$, on which $f$ is
monotone. Since $f$ is one-to-one off of $L$, $f$ is locally monotone everywhere except
for local extrema. The cardinality rule then implies that $f$ has at most two extrema
and is monotone on each connected segment after removing these points.

Now $g$ preserves the local extreme points of $f$. So if $f$ has more than one local
extreme point, then the values must coincide under $g$, but then there are at least four
preimages of some value near this extreme value for $g\of f$, violating strict
quasiconvexity. So $f$ can have at most one local extremum. It has exactly one because
$f$ is not
monotone and $D$ is connected. In particular, $L$ is connected.

\begin{comment}
%each subinterval. then note that $L$ necessarily excludes any local extrema of $f$, but contains
all of them in its closure. If $L$ is not closed in $\op{Range}(f)$ then
%take a point $p\in
%\overline{L}\backslash L \cap
%\op{Range}(f)$. The unique preimage point $x=f^{-1}(p)$ is a
%we will show that $L$ must be an interval. Note that $L$ necessarily excludes the local extrema of
$f$, but contains all of them in its closure. Since $g$ is necessarily
%one-to-one on $L$, $L$ is connected if and only if $g(L)$ is. However, if $g(L)$ is not connected
then the graph of $g\of f$ must have changed directions at a minimum
%of two points, since $f$ already has one local extrema and hence has more than one local extrema,
violating quasiconvexity. (To see this connect one point close before
%the first extremum to a point close after the second.)
%one of which is the unique point $m$ where the maximum of $g\of f$ occurs, and the other point we
will call $x$. A superlevel set of $g\of f$ at a slightly higher value than
%$g\of f(x)$ must then be disconnected, and hence not convex, violating quasiconcavity.
\end{comment}

Since $L$ is connected,  $g$ is one-to-one on the closure of  $L$, not just on $L$. This
contains all of the local extrema of $f$. Now assume $g$ is strictly increasing on this
closure. If the graph of $g$ changes direction elsewhere, then $g\of f$ has at least two
local extrema, violating quasiconcavity. Hence, $g$ is strictly increasing everywhere.
This then implies that $f$ was strictly quasiconcave since postcomposition by a strictly
increasing function $g^{-1}$ preserves quasiconcavity.

If $g$ was strictly decreasing on the closure of $L$ then similarly it is strictly
decreasing everywhere and $-f$ is strictly quasiconcave.
\end{proof}
 

Observe that if $f:(a,b)\to\R$ is not continuous, but quasiconcave with maximum at $m\in(a,b)$, then any concavifier $g$ must be constant on any intervals that correspond to the (at most countable) jump discontinuities in the range of $f$ on $(a,m]$. Let $g_1: \R\to\R$ be the continuous function that is constant on these segments and is linear with slope $1$ on all other intervals. Note that $g_1\of f$ must be continuous for $f$ to be strictly concavifiable, since collapsing any further interval would yield a constant segment in $g\of f$. (To achieve weak concavifiability $g$ must be constant on $[f(y),f(m)]$ for any discontinuity $y$ of $g_1\of f$.)  Hence, it is no loss of generality to consider only continuous $f$.

%----------------------------------------------------------
\section{Functions on $\R$}

In this section we prove the classification theorem for the case of real valued functions, which will be generalized later. We treat this case by progessively removing regularity conditions. The reason for this being that the general case and final conditions will make sense from the constructions we develop en-route. 

\subsection{The Case Where the Objective Function Is Twice-Differentiable and
Strictly Monotone}

\bigskip
If the continuous function $f$ is strictly increasing or decreasing, then  $f  \suchthat I\to \R$
is invertible. Hence,  we can easily solve the problem of concavifying $f$ by
choosing $g=h\of f^{-1}$ where $h$ is a concave function  and hence $g(f(x))=h(x)$ is
concave.
%\footnote{This can even be done in the case that $f$ is discontinuous and
%strictly increasing or decreasing,  by first repairing the range (see Section \ref{subsec:discont}).
%However, note that basic obstructions like those in Example \ref{ex:Aumann}
%arise in two or more dimensions regardless of continuity.}
Here, however, we will treat the twice-differentiable case more intrinsically and connect the
definition of concavity more viscerally with the properties of $f$. This will  build a
foundation for the next section, where we treat the noninvertible case.

Thus, let us move to  the special case where  $f$ is twice differentiable and strictly
increasing. We will also for now assume $g$ is twice differentiable and strictly
increasing.
Recall that we are searching for a strictly concave function $g\of f$. The twice
differentiable function $g\of f$ is strictly concave if   the expression
\begin{equation} \label{e100}
 (g \of  f)''(x)=g''(f(x)) \cdot f'(x)^2+g'(f(x))\cdot f''(x),
\end{equation}
  is nonpositive and never vanishes on an interval.
Equivalently, this occurs if
\begin{equation} \label{e01}
  \frac{g''(f(x))}{g'(f(x))}\leq -\frac{f''(x)}{ f'(x)^2},
\end{equation}
with equality never holding on any interval. (There are examples of strictly convex functions where
equality holds on a full measure set, however.)

Since we assume that $f$ is strictly increasing, it is invertible. Define  $z = f(x)$,
so $x=f^{\scriptscriptstyle -1}(z)$. Note that  $ \frac{1}{f'(x)} = \frac{1}
{f'(f^{\scriptscriptstyle -1}(z))} =\frac{\del}{\del  z} f^{\scriptscriptstyle -1}(z),$ so  the
right-hand side of inequality \eqref{e01}  is
\begin{equation} \label{e02}
 -\frac{f''(x)}{f'(x)^2}=\frac{\del}{\del  x}  \left( \frac{1}{f'(x)}
\right)  =  \frac{\del}{\del  x} \left( \frac{\del}{\del  (z=f(x))}
f^{\scriptscriptstyle -1}(f(x)) \right) =    f^{{\scriptscriptstyle -1}
\prime \prime }  (f(x)) \cdot  f'(x)   .
\end{equation}



Taking another step:
\begin{equation} \label{e03}
 -\frac{f''(x)}{f'(x)^2}=    f^{{\scriptscriptstyle -1} \prime \prime }
(f(x)) \cdot  f'(x)  =  \frac{\del}{\del  x}    \log
f^{{\scriptscriptstyle -1}  \prime }    (f(x))   .
\end{equation}

Similarly (though since we are constructing $g$ we need not invert), the
left hand side of  inequality  \eqref{e01}  is $\frac{\del}{\del   f(x)}
\log g^{   \prime }    (f(x) )   .$
Hence a sufficient criterion    for inequality  \eqref{e100}   to be true is that
\begin{equation} \label{e04}
\frac{\del}{\del   z}    \log g^{   \prime }    (z )  < \frac{\del}{\del z}
\log  f^{{\scriptscriptstyle -1}  \prime }    (z)
\end{equation}
  for all $z$ in the range of $f$, provided both sides are well
defined.

 If we choose a number $c>0$ and a function $g$ so that
\begin{equation} \label{e05}
g'(z)=e^{-c z} \cdot  f^{{\scriptscriptstyle -1}\prime}  ( z )
\end{equation}
then
\begin{equation} \label{e05a}
\log g'(z)=  -c z + \log f^{{\scriptscriptstyle -1}\prime}   (z)
\end{equation}
 and
\begin{equation} \label{e05b}
\frac{\del}{\del   z}   \log g'(z)=  -c+  \frac{\del}{\del   z}    \log
f^{{\scriptscriptstyle -1}\prime}(z)   < \frac{\del}{\del   z}    \log
f^{{\scriptscriptstyle -1}\prime}(z)
\end{equation}

Integrating $g'$ from equation \eqref{e05} will produce the desired
function.

This approach, using Equation \eqref{e05},    has the advantage of relying
only on first derivative data of $f$ in its construction  (although the
properties requisite for its application do rely on the second derivatives
of $f$.) Later we will make use of a second approach.
To construct $g$,  choose any function $u(z)<f'(f^{\scriptscriptstyle -1}(
z) )
\cdot f^{\scriptscriptstyle -1 \prime \prime}(z) $.   Then set
\begin{equation} \label{e06}
g(z)= \int_0^z  \left( e^{\int_{a}^s u(t)dt} \right) ds
\end{equation}
 for any $a\in\R$ chosen at the top of the domain of  $u(z)$. This yields
a function with $g \of  f$ concave on $(a,d]$. (Note that shifting the function $g$ by adding a constant is immaterial to its effectiveness.)
 

\bigskip


%---------------------------------------------------------
 
\subsection{The  Case When the  Objective Function Is Nonmonotonic but Twice
Differentiable}\label{sec:nonmonotonic}
\bigskip

Now suppose the function  $f$ is twice differentiable and strictly quasiconcave but not
monotone. In that case it achieves its maximum at a unique internal point $m\in (a,b)$,
so that $f$ is rising on $(a,m]$ and  falling  on $[m,b)$  as in Figure
\ref{quasi-f1f2.jpg}.

  \begin{figure}[ht!]
   \centering
 \includegraphics[width=5in]{fig-f1f2}
\caption{\sc   The Construction of   $f_1$ and $f_2$   }
 \label{quasi-f1f2.jpg}
 \end{figure}

For now, we will also require that $f$ have a non-vanishing derivative except at an
internal maximum or
endpoints.



Denote by $f_1\suchthat [0,1) \toarrow\R$ the strictly increasing function
$$
f_1(x)= f(a(1-x)+x m)
$$
   and by $f_2 \suchthat  [0,1) \toarrow \R$ the strictly increasing function
$$
f_2(x)=f(b (1-x)+x m).
$$



Figure \ref{quasi-f1f2.jpg} illustrates this construction, which splits $f(x)$ into two
strictly increasing functions on $[0,1]$ to save the bother of using negative  signs and
absolute values of slopes in our analysis. (In Figure \ref{quasi-f1f2.jpg} the $f(x)$ is
not twice differentiable; it is drawn with a kink to illustrate the $f_1$, $f_2$
construction  clearly.)

The new functions $f_1$ and $f_2$ are homeomorphisms onto their images, so
they have inverses $f_1^{\scriptscriptstyle -1}$ and
$f_2^{\scriptscriptstyle -1}$. Hence, by
post-composition we can easily  choose a $g$  such that  either $g \of  f_1$
or $g \of  f_2$ is strictly concave and smooth.  The difficulty is  in
making   $g \of  f$   concave on
its entire domain--- that is, to  use the same function to concavify  both
$f_1$ and $f_2$---  especially when $f$ is nondifferentiable or not defined
over a compact set. We will
treat this general problem in the next section.
 
 
 


Since $f$ is twice differentiable with first derivative bounded away from $0$, and  $I$
is compact, the problem becomes easy in light of what we discovered in the previous
section. Simply set
\begin{equation} \label{e06c}
\text{(Concavifying function)}\quad g'(z)=e^{\int_0^z u(t)dt}
\cdot  f_1^{{\scriptscriptstyle -1}  \prime } (z) \cdot
f_2^{{\scriptscriptstyle -1}  \prime }(z)
\end{equation}
  for any continuous function $u  \suchthat   \R \toarrow    \R$ satisfying
\begin{equation} \label{e07}
 u(z)< \min\set{0,-    \frac{\del}{\del   z}  \log
 f_1^{{\scriptscriptstyle -1}  \prime } (z) ,-  \frac{\del}{\del   z}  \log
f_2^{{\scriptscriptstyle -1}  \prime } (z) }.
\end{equation}
so that
\begin{equation} \label{e08}
\frac{\del}{\del   z}  \log g' (z) =  \frac{\del}{\del   z}   \log
f_1^{{\scriptscriptstyle -1}  \prime } (z)  + \frac{\del}{\del   z}  \log
f_2^{{\scriptscriptstyle -1}  \prime } (z) +u(z)< \min\set{ \frac{\del}{\del
z}
\log  {f_1^{\scriptscriptstyle -1}}'(z) , \frac{\del}{\del   z}  \log
{f_2^{\scriptscriptstyle -1}}'(z) }.
\end{equation}

Note that we used the   nonvanishing derivative condition  on $f$ simply to
guarantee the existence of $u$ in that the right-hand side of \eqref{e07} is
bounded from below.  Thus we can solve for
$g$, yielding $g\of f$ concave.
 



%--------------------------------------------------------------------

\subsection{The  Case When the Function Is Nondifferentiable and Nonmonotonic but
Continuous}
\bigskip

In the case of a nondifferentiable $f$,  we would like, following equation
\eqref{e06c},  to form
\begin{equation}\label{e08a}
 g'(z)=e^{\int_0^z u(t)dt} {f_1^{\scriptscriptstyle -1}}'(z) \cdot
{f_2^{\scriptscriptstyle -1}}'  (z),
\end{equation}
but in a distributional sense, since we can only rely on weak derivatives. For this we consider the Sobolev space $W^{k,p}$, the space of functions whose weak $k$-th derivatives
belong to $L^p$. Since $f_1^{\scriptscriptstyle -1}$ and $f_2^{\scriptscriptstyle -1}$
are strictly increasing, they are absolutely continuous and live in $W^{1,1}$. However,
$W^{1,1}$ does not form an algebra, since it is not closed under multiplication of
functions. This creates a problem as demonstrated in the following example. 

\begin{example}\label{bi-cubic}
Suppose our quasiconcave function $f(x)$ was  such that $f_1(x)=f_2(x)=x^3$.
The strictly increasing function $f_1^{-1}(x)=f_2^{-1}(x)=x^{\frac13}$ belong to $W^{1,1} $ on
$[-1,1]$.  This has derivative ${f_1^{-1}}'(x)=\frac13 x^{-\frac23}\in L^1$,  but the product we would have for our construction in equation \eqref{e08a} is ${f_1^{\scriptscriptstyle -1}}'(z) \cdot
{f_2^{\scriptscriptstyle -1}}'  (z)=\frac19 x^{-\frac43}$, which is not in $ L^1$, and integrating
it to get $g$ yields   $-\frac13 x^{-\frac13}$,  which is not even increasing on $[-1,1]$. On
the other hand, this $f$ is easily concavified by $g(y)=-y^{2/3}.$
\end{example}

Hence, simply taking the product
$f_1^{{\scriptscriptstyle -1} \prime} (z) \cdot f_2^{{\scriptscriptstyle -1}
\prime} (z)$ for
$g'(z)$ will not always work. If we assumed that each $f_i^{-1}$  was in
$W^{1,p}$ for $p\geq 2$, then the product would be in $W^{1,1}$. Though, if we allow one to be in $W^{1,1}$, then the other would necessarily have to be in $W^{1,\infty}$,
and this is a stronger assumption than we need, since $W^{1,\infty}$
coincides with the space of Lipschitz functions  and we know that there are non-Lipschitz
quasiconcave functions that can be concavified (e.g. $f(x) =
x^\frac13$ on $[-1,1]$).

Conversely, if we wanted to work directly on weak second derivatives to guarantee that $
\frac{\del}{\del   z}
\log
g' (z)<\min\set{\frac{\del}{\del z} \log
f_1^{{\scriptscriptstyle -1} \prime} (z), \frac{\del}{\del   z}  \log
f_2^{{\scriptscriptstyle -1} \prime} (z)} $ for
equation \eqref{e08},  we would need to work with $f_i^{-1}$ in
$W^{2,1}$. By the Sobolev embedding theorem,
however, $W^{2,1}\subset W^{1,\infty}$ for one-dimensional functions.\footnote{For the
general Sobolev Embedding Theorem, see Chapter 2 of \cite{Aubin}. For $W^{2,1}
(\R)\subset W^{1,\infty}(\R)$, see Exercise 2.18 in \cite{Ziemer}.} Thus we gain nothing over working with Lipschitz functions.

\bigskip

In view of these problems, instead of weak derivatives, we will work with the following upper and lower derivatives
$\overline{D}f,\underline{D}f\suchthat    \R  \toarrow
[-\infty,\infty]$ defined for a function $f$ by,
\begin{equation} \label{e09}
 \overline{D}f(x)=\limsup_{h \toarrow     0}
\frac{f(x+h)-f(x)}{h}\quad\text{and}\quad  \underline{D}
f(x)=\liminf_{h \toarrow    0}
\frac{f(x+h)-f(x)}{h}.
\end{equation}

These quantities always exist, if we allow for values of $-\infty$ and $\infty$, and $ \overline{D}
f(x)\geq
\underline{D} f(x)$ with equality occurring if and only if the derivative of
$f$ exists at $x$, in
which case both quantities coincide with $f'(x)$.

Note that if $w<x<y$ then the slope of the secant line between $(w,f(w))$ and $(y,f(y))$
lies between the values of the slopes of the secant lines from $(w,f(w)))$ to $(x,f(x))$
and $(x,f(x))$ to $(y,f(y)))$. Hence we have,
\begin{equation} \label{e10}
 \overline{D}f(x)=\limsup_{\substack{\abs{y-w}\to 0 \\ w\leq x <
y}}\frac{f(y)-f(w)}{y-w}\quad\text{and}\quad
\underline{D}f(x)=\liminf_{\substack{\abs{y-w}\to 0 \\ w\leq x <
y}}\frac{f(y)-f(w)}{y-w}.
\end{equation}

In other words, these quantities reflect the lower and upper limit of the slopes of all secant lines
between points before and after $x$, not just those with an endpoint
at $x$. Also, we cannot dispense with the ordering $w\leq x <y$ in the above limits; for example, the
continuous extension of the function $x^2 \sin(\frac1{x^2})$ has
derivative $0$ at $0$ and yet admits secant lines of unboundedly positive and negative slope whose
endpoints are arbitrarily close to $0$.

We now begin to explore analogues of conditions for concavity of $C^2$ functions using the above
objects that are available to us for arbitrary continuous functions.
For what follows let $\ell(x,y)$ represent the secant line between $(x,f(x))$ and $(y,f(y))$, and
let $s(x,y)$ represent the slope of $\ell(x,y)$. In the next three lemmas,
we will explore the relationship between concavity and conditions on $\overline{D}f$. (Analogous
statements invoking $\underline{D}(f)$ could also naturally be
formulated.)

\begin{lemma}\label{lemma1}
A continuous function $f:I\to \R$ is strictly concave
 if and only if for all $x\in  I$, and all
$w<x$, $\overline{D}f(x) < s(w,x)$.
\end{lemma}

\begin{proof}
If $f$ is concave, then for any $y>w$ in $I$ we have $s(x,y)<s(x,w)$ and hence taking the $\limsup$
as ${y\to x}$ we obtain the forward implication. Conversely,  if
$f$ is not convex then   there exist points $r<s<t$ in $I$ such that $f(s)$ lies below the secant
line $\ell(r,t)$. By continuity, one may trace the graph in both
directions from $(s,f(s))$ until it runs into the segment $\ell(r,t)$ showing that there is some
open interval $(w,x)\subset (s,t)$ such that the entire graph of $f$ over
 $(w,x)$ lies strictly below the secant line $\ell(w,x)$. For all $z\in(w,x)$, we then have $s(z,x)>
s(w,x)$ and therefore $\overline{D}f(x)\geq s(w,x)$ contradicting our hypothesis.
\end{proof}

\bigskip

\begin{lemma}\label{lem:2}
A continuous function $f:I\to \R$ is strictly concave if and only if $\overline{D}f$ is a strictly
decreasing function.
\end{lemma}

\begin{proof}
If $f$ is concave, then for any three points $w<x<y$ in $I$ we have $s(w,x)>s(w,y)$ and $s(w,y)>
\overline{D}f(y)$ by  Lemma \ref{lemma1}. Taking the $\limsup$ as
$w$ approaches $x$ from below we see that $\overline{D}f(x)\geq s(w,y)> \overline{D}f(y)$, as
desired.

Conversely, if $f$ is not concave we can find, as in the proof of Lemma \ref{lemma1}, points $w<x$ for which the entire graph of $f$ over $(w,x)$ lies strictly below the
secant line $\ell(w,x)$. After possibly shrinking this neighborhood we may assume the graph of $f$
changes sides of the secant line $\ell(x,w)$ at both $w$ and $x$.
Then for any point $z$ sufficiently near $w$, and any point $y$ sufficiently near $x$, we have
$s(z,w)<s(w,x)<s(x,y)$. Taking limsup's as $z$ approaches $w$ and $y$
approaches $x$, we obtain $\overline{D}f(w)\leq \overline{D}f(x)$, contradicting our hypothesis.
\end{proof}

We now combine Lemma \ref{lem:2} with  the fact that one can always control, after
post-composition, the Lipschitz constant of $f$ over any interval where $f$ is monotone.
This yields the following necessary criterion for strict quasiconcavity  of $f$. First
recall that  $a$ was defined as the lower bound of the support of $f$ and $m$ as its
argmax in Section \ref{sec:nonmonotonic}. Also, for the remainder of the
paper, let $\rest{f} {(a,m]}$ denote the restriction of the function $f$ to the interval
$(a,m]$.

\begin{lemma}\label{lem:concavif-noncont}
Given a strictly quasiconcave function $f\suchthat    (a,b)
\toarrow \R$, there is a $g  \suchthat   \R \toarrow   \R$ such that $g \of
f$  is strictly concave
only if there is a function $h\suchthat  \R \toarrow   \R$ such that $h \of
f$ satisfies,
\begin{equation} \label{e11}
\begin{cases}
\phantom{\infty}0<\underline{D}(h \of  f)(x)\leq\overline{D}(h \of
f)(x)<\infty & {\rm for }\; x\in(a,m)\\
\\
-\infty<\underline{D}(h \of  f)(x)\leq\overline{D}(h \of  f)(x)<0 & {\rm for
}\; x\in(m,b).
\end{cases}
\end{equation}
 In particular, $h \of  f$ must be (locally) Lipschitz except at $m$.
 \end{lemma}


\begin{proof}
Suppose there is no such $h$.      We can compose $f$ by the function $h=\rest{f}
{(a,m]}^{\scriptscriptstyle
-1}$ so that $h \of  f$ is still strictly quasiconcave, but $(h \of  f)_1$ is linear. By
hypothesis, $(h
\of f)_2$ either admits a vertical tangency on the pre-image of the range of $(h \of f)_1$,
or else $\underline{D} (h
\of  f)_2(x)=0$ for some $x\in (0,1)$. In the latter case, if we had instead chosen $h=
-\rest{f} {[m,b)}^{\scriptscriptstyle -1}$ then $(h \of f)_2$ would be linear and $(h \of  f)_1$
would admit a vertical tangency, and so we are back in the first case after
switching ``1''and ``2''. Hence, without loss of generality we may assume that there is a point
$x\in (0,1)$ with $\overline{D}(h \of f)_2(x)=\infty.$ (Recall here that $(h \of
f)_2$ is increasing, see Figure \ref{quasi-f1f2.jpg}.)

Since $(h \of  f)_1$ is the identity, any  strictly  concavifying $g$ for $h
\of  f$ must be concave and strictly increasing, and hence with
$\underline{D}(g)(z)>0$ for any $z$ in the
interior of the range of $(h \of  f)_1$. Then, however,  it could not have
concavified $(h \of f)_2$.
\end{proof}


The function $h$ in Lemma \ref{lem:concavif-noncont} can also be taken to be the inverse of the
restriction to the strictly increasing side, so $h=
 \rest{f} {[m,b)}^{\scriptscriptstyle -1}$.

 
We shall see that the necessary conditions in Lemma \ref{lem:concavif-noncont} turn out to
not be sufficient for concavifiability. A significantly more subtle
problem arises. Consider the following example. 
 
 
\begin{example}\label{ex:quasi3b}
{\bf A positive log-derivative with unbounded variation.} Consider the strictly
quasiconcave function $f(x)$ on $[-1,4]$ shown in Figure \ref{quasi3b}, which is defined
as follows.
\begin{equation*} \label{e09b}
f(x)=\begin{cases}
  q(x) & -1\leq   x<1 \\
  q(1)-\frac{1}{2} (x-3) (x-1) q'(1) & \phantom{-}1\leq x\leq 4
\end{cases}
\end{equation*}
where
$$
 q(x)=\int_{-1}^x e^{t \sin \left(\frac{1}{t}\right)+1}\, dt
  $$

From the formula we can readily verify that the first derivative,
$$
f'(x)=
 \begin{cases}
  e^{x\sin(1/x)+1} & -1\leq x<1 \text{ and } x\neq0\\ e & x=0 \\
e^{1+\sin(1)}(2-x) & \phantom{-}1\leq x \leq4
  \end{cases},
$$
is a $C^1$ function with derivative bounded away from $0$, except at the peak of
$f$ at $x=2$, and is strictly concave on $[1,4]$.   Nevertheless, on
the interval $(-1,1)$, we have $\log f'(x)=x\sin(\frac1x)+1$ which is a classic example
of a function with unbounded variation. While not obvious,
Theorem \ref{thm:1-d}  will show that such an $f$ cannot be concavified by any
postcomposition.
\end{example}

\begin{figure}[ht]
  \centering
 \includegraphics[width=4in]{quasifig08-sinewave}
\caption{A Nonconcavifiable Strictly Quasiconcave Function with Strictly Positive Derivatives but  Unbounded Variation  }
 \label{quasi3b}
 \end{figure}
%was pagebreak

Recall that the variation of a function  $f\suchthat    [a,b] \toarrow    \R$ is defined
as
\begin{equation} \label{e12}
  { \op{Var}(f)}  =  \sup\set{\sum_{i=1}^{n} \abs{f(x_{i})-
f(x_{i-1})}\,  \suchthat\,  n\in \N
 \;\; {\rm and} \;\; a\leq x_0<x_1<\cdots<x_n\leq b }.
\end{equation}

Denote the  functions of bounded variation on the closed interval $[a,b]$  by
\begin{equation} \label{e13}
  { \op{BV}([a,b]) }     =  \set{f  \suchthat [a,b] \toarrow   \R
\suchthat \op{Var}(f)<\infty}.
\end{equation}




For a general interval $I\subset \R$,   denote by  $\op{BV}_{loc}(I)$ 
the set of {\em locally} bounded variation functions, i.e. those which
belong to $\op{BV}([a,b])$ for
every compact interval $[a,b]\subset I$.

In Theorem \ref{thm:1-d} below, without loss of generality, we will assume that our function  $f
\suchthat (a,b)\to \R$ has the property that if either $f$ or $-f$ is
quasiconcave, then $\op{Range}(\rest{f}{(a,m]})=\op{Range}(f)$ where $m$
represents the unique extremal point (the $\argmax$ or $\op{argmin}$). (Otherwise, just replace $f(x)$ by its reflection about $\frac{b+a}{2}$, namely $f(b+a-x)$. The resulting $g$ will concavify the original $f$.)

 
\begin{theorem}\label{thm:1-d}
For any continuous nonmonotonic function $f\suchthat  (a,b) \toarrow \R$, there is a function $g
\suchthat   \op{Range(f)} \toarrow   \R$ such that $g \of f$ is strictly concave if and
only if
\begin{enumerate}[(i)]
\item
 $f$ or $-f$ is strictly  quasiconcave. 
\item
 for $h  =  \rest{f} {(a,m]}^{\scriptscriptstyle -1}$,  the function $h
\of  \rest{f} {(m,b)}$  and its inverse are locally Lipschitz.
\item 
$\log \abs{\overline{D}(h \of f)}\in\op{BV}_{loc}((m,b))$.
\end{enumerate}
Moreover, when $g$ exists it is strictly monotone.
\end{theorem}

\begin{proof}
We will first explain the necessity of (i). If $f(x)$ is not strictly quasiconcave, then  there exist points $w,y,z$ such that
  $w<y<z$ and one  of the following three conditions holds:

\begin{enumerate}[(a)]
\item $f(y)  < \min (f(w), f(z))$ (if $f(x) $ is not even weakly quasiconcave)

\item $f(y)  = \min (f(w), f(z))$  and $f(w) \neq f(z)$

\item $f(y)  =  f(w)=f(z)$.
\end{enumerate}

In any of these cases,  for any strictly monotonic function $g$,  $ g(f(y))$
will be below a straight line connecting $g(w)$ and $g(z)$ and hence by
definition is not concave,  because:
\begin{equation} \label{e444b}
g(f(y))  \leq  \left| \frac{w-y}{w-z} \right| g(f(w)) + \left| \frac{
y-z}{w-z} \right| g(f(z))
\end{equation}

In case (a), this is because $g(f(y))$ is less than either  $ g(f(w)) $   or
$ g(f(z)) $, so the inequality in \eqref{e444b} is strict.  In
case  (b), $g(f(y))$ is equal to one
of the other two $g$'s and less than the other, so inequality \eqref{e444b} is again strict. In case (c), $g(f(y))$ is equal to both the other two $g$'s, so
the inequality becomes an equality. 

Lemma  \ref{lem:concavif-noncont} demonstrates
the necessity of condition (ii) on the upper derivatives.  
Necessity of condition (iii) will be deferred until the end of the proof.

To prove sufficiency without loss of generality we may assume $f$, as opposed to $-f$, is
strictly quasiconcave. The existence of $g$ implies that it is continuous,  since $f$ and
$g\of f$ are. Moreover, $\overline{D}(h \of  f)$ is nonpositive on $(m,b)$ since $f$ is
strictly decreasing there and $h$ is strictly increasing on its domain. (This accounts for
taking the absolute value in condition (iii),  which is unnecessary in the case when $-f$
is quasiconcave.) Since $\log \abs{\overline{D}(h \of f)}\in\op{BV}_{loc}((m,b))$,  it is
a standard fact, e.g. see \cite{Folland}, that $\log \abs{\overline{D}(h \of  f)}$ is
the difference of two strictly increasing functions. Also,  $\log \abs{\overline{D}(h \of 
f)}$  is continuous except at a countable set of points such that the sizes of the jumps
at the discontinuities on any compact interval are summable. Now $\log \abs{(h \of  f)'}$
agrees with this function wherever it is defined, which is almost everywhere since $h\of
f$ is monotone. 

By Darboux's Theorem, and since a full measure set is dense, $\log \abs{(h
\of f)'}$ then agrees with $\log \abs{\overline{D}(h \of  f)}$ at each point where $\log
\abs{\overline{D}(h \of  f)}$ is continuous. Since $-\log \abs{(h \of f)'(x)}=\log
\abs{((h \of f)^{\scriptscriptstyle -1})'(h \of f(x))}$, it also agrees with $\log
\abs{\overline{D}(h \of f)^{\scriptscriptstyle -1} \of h \of  f}$ except at a countable
number of points where  $\log \abs{\overline{D}(h \of f)^{\scriptscriptstyle -1} \of h \of
f}$ has discontinuities with summable gaps. Thus, since precomposition does not affect the
$\op{BV}$ property, except for the domain over which it applies, $\log \abs{\overline{D}(h
\of  f) ^{\scriptscriptstyle -1}}\in \op{BV}_{loc}\(\(h(f(m)), h(f(b))\)\).$

Let $h_1  =  h_0 \of  h$,  where $h_0$ is a smooth strictly increasing concave
function on $(-\infty,f(m)]$ with $\lim_{x \toarrow    m} \overline{D}(h_0 \of f)(x)=0$.
This
can always be done by using an $h_0$ that increases sufficiently slowly near $f(m)$.

From now on in the proof,  we will  write $f$ for $\rest{f} {[m,b)}$ to avoid distraction
from the subscript. Since the derivative of $h_0$ is bounded away from $0$ and
$\infty$ and is strictly decreasing on any compact subinterval of $\(f(b),f(m)\)$, the
function  $\log \abs{\overline{D}((h_1 \of f)^{\scriptscriptstyle -1})}$ still lies in
$\op{BV}_{loc}((h_1(f(b)),h_1(f(m))))$ and $h_1 \of  f$ is concave on $(a,m]$.

Now choose $z_0\in \(h_1(f(b)),h_1(f(m))\)$. Since 
\[
\log \abs{\overline{D}((h_1
\of f)^{\scriptscriptstyle -1})}\in\op{BV}_{loc}\(\(h_1(f(b)),h_1(f(m))\)\),
\]
there is a representative
\begin{align}\label{eq:q}
q\in L^1_{loc}\(\(h_1(f(b)),h_1(f(m))\)\)
\end{align}
 of the almost everywhere defined function $\left(\log \abs{\overline{D}((h_1 \of
f) ^{\scriptscriptstyle -1})}\right)'$ such that 

\[
\log\abs{\overline{D}((h_1 \of f)
^{\scriptscriptstyle -1}) (z)}=\log\abs{\overline{D}((h_1 \of f)^{\scriptscriptstyle
-1})(z_0)}+\int_{z_0}^z q(t) \,dt.
\]
Since $\lim_{z
\toarrow m}\overline{D}(h_0 \of f)(z)=0$, the negative part of $q$, namely
\begin{align}\label{eq:q-}
q^-(x) =  \begin{cases} q(x) & q(x)<0 \\ 0 & q(x)\geq 0\end{cases},
\end{align}
belongs to $L^1([h_1(f(c)),h_1(f(m))])$ for any $c<b$. By integrating, we can find a twice-differentiable (though not necessarily in $C^2$) function 
$g_0 \suchthat \(h_1(f(b)),h_1(f(m))\)\to \R$ such that
\begin{equation} \label{e14}
 g_0'(z)=e^{\int_{h_1(f(m))}^z (-1+q^-(t))\,dt}.
\end{equation}

Consequently,  $g_0'(z)> 0$, $g_0''(z)<0$ and $(\log g_0')'<q^-(z)$ for each
$z\in\(h_1(f(b)),h_1(f(m))\).$ Since by construction $(\log g_0')'(z) < (\log
\abs{((h_1\of  f)^{\scriptscriptstyle -1})'})'(z)$ for almost every
$z\in\(h_1(f(b)),h_1(f(m))\)$, it follows that $\overline{D}(g_0 \of h_1 \of f)$ is
strictly decreasing on $(a,b)$ and so $g_0 \of  h_1 \of  f$ is concave, which is what we
needed to prove. Lastly note that $g=g_0\of h_1$ is strictly monotone since $h_1$ is and $g_0'>0$. 

All that remains to be proved is the necessity of condition (iii). If 
$\log \overline{D} (h \of f)\not\in\op{BV}_{loc}((m,b))$,  then no such function
$q\in L^1$ can be
found: there exists no $g_0$ for which $\log g_0'$ grows slower than $\log (h_1
\of  f)'$  since   $\log g_0'(z)$ would necessarily become unbounded before
$z$ reached $h_1(f(b))$.
\end{proof}

\begin{remark}
Theorem \ref{thm:1-d} shows that quasiconcavity is not quite equivalent to concavifiability.
In addition, we require condition (ii), which roughly says that after straightening
out one side, the other side has no horizontal or vertical tangencies. And beyond that, one
still needs the yet more subtle condition (iii) governing the oscillation of the
derivative on the unstraightened side. 

Strictly speaking, condition (ii) is superfluous  in that it only serves to establish the
existence of the function in   condition (iii), where its existence is   implicit. In
particular, we need $\log \abs{\overline{D}(h\of f)}$ to exist  almost everywhere  in
order to make sense of it being in $\op{BV}_{loc}$. Once it belongs to $\op{BV}_{loc}$ we
can conclude that $h\of f$ on $(m,b)$, and its inverse, are locally Lipschitz.
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Functions on an Arbitrary Geodesic Metric Space}
\label{sec:metric} 
 We now extend our results to $\R^n$ and more general geodesic metric spaces. 

\begin{definition}\label{def:qc_metric}
%(QUASICONCAVITY AND CONCAVITY ON A GEODESIC METRIC SPACE)
A function $f  \suchthat X\toarrow \R$ on a geodesic metric space is  {\em
(strictly/weakly) quasiconcave} if and only if $f \of \gamma \suchthat  [0,1] \toarrow 
\R$ is (strictly/weakly) quasiconcave for every geodesic $\gamma \suchthat [0,1]\toarrow 
\R$, where we assume that $\ga$ is parameterized so that
$d(\ga(s),\ga(t))=\abs{t-s}d(\gamma(0),\gamma(1))$ for all $s,t\in [0,1]$.
%\addtocounter{footnote}{1}\footnotemark[\value{footnote}]


\hspace{18pt}Similarly, $f$ is {\em (strictly/weakly) concave} if and only if  for each
geodesic $\ga \suchthat[0,1]\to X$, $f\of \ga$ is (strictly/weakly) concave as a function
on $[0,1]$. (Note that this definition generalizes standard concavity for $X=\R^n$ with
the Euclidean metric.)
\end{definition}

%\footnotetext[\value{footnote}]{ That is, we
% assume that our geodesics are parameterized so that if $\ga(0)=x$ and $\ga(1)=y$ then
%$d(\ga(s),\ga(t))=\abs{t-s}d(x,y)$ for all $s,t\in [0,1]$.}



In what follows, we let $m\in X$ be the unique point maximizing $f$ if $f$ is quasiconcave or
minimizing $f$  if $-f$ is quasiconcave. We will denote the negative part of $F$ by $F^{-}$ as in \eqref{eq:q-}.
%Also recall that for a function
%$F:X\to \R$, the negative part of $F$, $F^{-}$, is defined by
%\[
%F^-(x) = \begin{cases} F(x) & F(x)<0\\ 0 & F(x)\geq 0\end{cases}.
%\]

We now state the complete criterion for  concavification of quasiconcave functions,
generalizing Theorem \ref{thm:1-d}. 

\begin{comment}
%In what follows,  let $\op{BV}_C$ denote the subset of $f\in\op{BV}([0,1])$ such
%that $\op{Var}(f)\leq C$.

%Following Remark \ref{rem:1-d} after Theorem \ref{thm:1-d}, for any constant $C>0$, we denote by
$\Omega$ the family of strictly increasing functions $f  \suchthat [0,1]\toarrow \R$ with
\comment{Does $\overline{\abs{D}}(f)$ exist for arbitrary metric spaces, with  no norm?}
%\begin{enumerate}
%\item[(i)]
%  $\log \overline{D}(f)$ bounded above on $[0,t]$ for any $t<1$  and bounded   below on $[s,t]$ for
any $0<s<t<1$,  and
%\item[(ii)]
%  $[\overline{D}(\log
%\overline{D}(f))]^-\in L^1_{loc} ([0,1))$.
%\end{enumerate}
\end{comment}

 \begin{comment}
%
%   bounded above away from $0,1$, and bounded away from
%$-\infty$ away from the minimum point $m\in[0,1]$ with the
%negative part of the derivative of this function satisfying
%$\op{Var}(q^-)<C$ where $q=\overline{D}
%(\log\overline{\abs{D}}(f))$. (Note that $q^-$ this is an
%explicitly defined $L^1$ representative of $(\log \abs{f'})'$.)
%
 \end{comment}


\bigskip


\begin{theorem}\label{thm:metric}
Let $X$ be any geodesic metric space.
For any continuous function $f\suchthat   X\toarrow  \R$
there is a function $g  \suchthat  \op{Range(f)}\toarrow  \R$  such that $g
\of  f$ is strictly concave if and only if:

\begin{enumerate}
\item[(i)]
 Either $f$ or $-f$ is strictly quasiconcave;

\item[(ii)] $h\of f$ is locally Lipschitz on $X-\set{m}$ where $h=(f\of\ga_o)^{-1}$
for some geodesic $\ga_o$ in
$X$ ending at $m$ such that $\op{Range}(f\of \ga_o)=\op{Range}(f)$. Moreover
$\overline{D}(h\of f \of \ga)$ does not vanish on any geodesic segment $\ga\suchthat
(0,1)\to X$ for which $h\of f\of \ga$ is strictly increasing.

\item[(iii)] The total variation of $\log \overline{D} (h\of f)$ along all geodesics
$\ga\suchthat [0,1]\to X$
for
which $h\of f\of \ga$ is strictly increasing is uniformly bounded away from the
extrema of $h\of f$,  or in
other words,
\begin{equation} \label{e17}
\inf_{\ga}\set{[\overline{D}(\log \overline{D}(h\of f\of \ga)^{-1})]^- }\in
L^1_{loc}(R).
\end{equation}
(Here $R$ is the interior of the range of $f$ and the infimum is taken over all
geodesic segments $\ga\suchthat [0,1]\to X$ for which $h\of f\of \ga$ is strictly
increasing.)
\end{enumerate}
\end{theorem}


\begin{proof}
Suppose first that the conditions are met. Let $q$ be the infimal function
\[
q=\inf_{\ga}\set{[\overline{D}(\log \overline{D}(h\of f\of \ga)^{-1})]^- }.
\] 
From the proof of  Theorem \ref{thm:1-d}, any function $g_0$ such that $(\log g_0')'<q$
(pointwise) will concavify $h \of  f  \of  \gamma$ for each such $\gamma$. Choose $g_0$ such
that $(\log g_0')'= -1+q$. (Note that we can extend $g_o$ to a function at the endpoints
of $R$ as well.)

Observe that every segment $\gamma \suchthat [0,1]\toarrow  X$ contains a subsegment
$[s,1]$ where $h \of  f \of
\gamma$ is strictly increasing on $[s,1]$. Moreover, $h \of  f \of  \gamma(1-t)$ is also
strictly increasing for $t\in [1-s,1]$. We now
note that a strictly quasiconcave function that is concave on both its strictly increasing and
strictly decreasing part separately  is concave. Hence, the function $g_0$ concavifies
$h
\of f \of
\gamma$ for every geodesic $\gamma$, and so $g_0 \of  h \of  f$ is concave. (This applies
even to geodesics through $m$ since $g_0\of h\of f$ is concave on every
subinterval on either side of $m$.) Taking $g=g_0 \of h$ finishes this direction of the
proof.

Conversely, suppose that there is a function $g$ such that $g\of f$ is concave. Since $h$
is invertible, we may write $g\of f=g\of h^{-1}\of h\of f$, and set $g_o=g\of h^{-1}$.
By concavity of $g\of f$ along $\ga_o$, we have that $g_o=g\of f\of \ga_o$ is convex. In
particular it $C^1$ with $\log (g_o)'$ Lipschitz with derivative belonging to
$L^1_{loc}(R)$.    Moreover, for any geodesic $\ga\suchthat [0,1]\to X$, with $f\of \ga$
strictly increasing, we have $(\log (g_o)')'\leq q_\ga$ where
$q_\ga=[\overline{D}(\log
\overline{D}(h\of f\of \ga)^{-1})]^-$,  the comparison holding almost everywhere. Taking
infima over all such $\ga$ implies $(\log (g_o)')'\leq q$ as desired.
\begin{comment}
%
%By the final hypothesis of Theorem \ref{thm:1-d}, we have $\log g_o'$ If the conditions of the
theorem are not satisfied, then for any
%$h  \suchthat \R\toarrow  \R$ as in the statement, there is a geodesic $\ga:[0,1]\to X$ for which
$h\of f\of \ga$ is increasing, but
%either $\log\abs{\overline{D}(h \of  f \of  \gamma)}$ is unbounded at an interior point of
$\gamma$, or there is   a geodesic along which the restriction
%of $h \of  f$
%cannot be concavified by Theorem \ref{thm:metric} . In the second case we
%are done, and in the first case we may assume that the geodesic does not
%pass through the
%global maximum of $f$ since we can always choose an $h$ which increases so
%slowly at $f(m)$ that after possibly postcomposing $h$ with another $h_1$,
%we may
%assume that the entire differential of $h \of  f$ vanishes at $m$, i.e.
%$d_m(h \of  f)=0$. If the function $h \of  f \of \gamma$ does not have
%bounded upper derivative at
%its maximum point, however,  then it is not concave. Thus, if this property
%does not apply to    all $\gamma$ simultaneously,   $f$ is not
%concavifiable.
\end{comment}
\end{proof}

Put crudely, Theorem \ref{thm:metric} says that in any geodesic metric space, even nonseparable ones, the function $f$ being strictly concavifiable by a strictly increasing
$g$ is equivalent to three conditions on $f$. First, $f$ must be strictly quasiconcave.
Second, after being straightened to linear along one geodesic spanning the whole range,
the resulting function must not be too flat or too steep in any direction. Lastly,
the total variation of the log of the derivative along all
geodesic segments must be bounded uniformly, away from the endpoints. Note that since there are typically an infinite number of geodesics in $X$, these criteria become much more restrictive than in the setting of Theorem \ref{thm:1-d}. Fortunately, for the special case of smooth functions on manifolds, these conditions are both more easily satisfied and more easily verified.
  

%---------------------------------------------------
 
%---------------------------------------------------

\section{Twice Differentiable Functions on a Riemannian Manifold $M$}\label{sec:Riemannian}

Here  we consider a $C^2$  $n$-dimensional Riemannian manifold $M$ with its Riemannian
connection $\nabla$.  We will make the assumption that the strictly quasiconcave function
$f\suchthat M\to \R$ is  twice differentiable. Later, for our last theorem, we will weaken
this to functions belonging only to the Sobolev space $W^{2,1}$ (i.e. possessing weak
second derivatives).

Let $f  \suchthat   M\toarrow  \R$ be strictly  quasiconcave. Suppose $\grad f$ does not
vanish at a point $x$. Then some contractible open neighborhood $U$ of $x$ within the
level set $f^{-1}(f(x))$ is a hypersurface of $M$. On $U$, choose an orthonormal framing
$\set{e_i(x)}$ of the tangent bundle $TM$ of $M$ restricted to $U$ such that (i) $e_1=
\frac{\grad f}{\norm{\grad f}} $, the unit normal to $U$, and (ii)  $e_2,\dots,e_n$ forms
a diagonal basis for the second fundamental form (i.e. the shape operator) of the
hypersurface $U\subset M$.

The Hessian  of a function $f$ on an arbitrary Riemannian manifold is the $(0,2)$
tensor
$\op{Hess} (f)=\nabla df$.
Given any basis, $v_1,\dots,v_n$ of the tangent space $T_pM$ at the point $p$,  the
corresponding matrix of the Hessian at $p$ has entries
\begin{equation} \label{e18}
 f_{ij}=\inner{\nabla_{v_i}(\nabla
f),v_j}=\nabla_{v_i}\inner{\grad f,v_j}-\inner{\grad
f,\nabla_{v_i}v_j},
\end{equation}
where on the right hand side we have extended the basis of vectors to local vector fields, though it is independent of the extension.

This  matrix depends on the metric, and not just on the smooth structure
(except at critical points of the function $f$, where $\nabla df=d^2f$).
Note, too, that $\op{Hess}(f)$ is symmetric, which can be seen easily by
extending the basis $\set{v_i}$ to a coordinate basis so that
\begin{equation} \label{e19}
f_{ij}-f_{ji}=v_i(df(v_j))-v_j(df(v_i))-df(\nabla_{v_i}
v_j-\nabla_{v_j}v_i)=[v_i,v_j](f)-df([v_i,v_j])=0.
\end{equation}

Thus equipped,  we  can present a necessary and sufficient condition for concavifiability
of a twice-differentiable quasiconcave function $f$ by postcomposing with a
twice-differentiable function $g$. Our theorem will apply to $C^2$ Riemannian manifolds;
that is,   manifolds admitting $C^2$ charts for which the metric tensor coefficients are
also $C^2$ functions. It will depend on the principal curvatures
$\lambda_2(x),\dots,\lambda_n(x)$ of the level sets of $f$, which are the eigenvalues of
the second fundamental form at the point $x\in M$. These values (which  are always
positive for a strictly quasi-concave function) indicate the bending of the submanifold
relative to the ambient manifold's curvature.  For an  $\R^2$ example to illustrate the
theorem, look ahead to the example in Figure \ref{fig:condition3} after the proof.
 

\begin{theorem}\label{thm:manifold}
%\refstepcounter{theoremcounter} \label{thm:c2}
Let $M^n$ be a $C^2$ Riemannian manifold, possibly with boundary.  For
any twice-differentiable function $f\suchthat M\toarrow
\R$ there is a strictly increasing twice-differentiable $g
\suchthat  \R \toarrow  \R$  such that $g \of  f$ is strictly concave if and only if:
\begin{enumerate}
\item[(i)]
 $f$ is strictly quasiconcave;

\item[(ii)]
$\grad f$ does not vanish on the interior of $M$ except possibly at the maximum point of
$f$,

\item[(iii)] The function 
\begin{equation} \label{e20}
q(t)=\inf_{x\in f^{-1}(t)}
\frac{1}{\norm{\nabla f(x)}^2} \left(-f_{11}(x)-\sum_{j=2}^n
\frac{f_{1j}^2(x)}{\lambda_j(x)\norm{\nabla f(x)}}\right)
\end{equation}
has negative part $q^{-}$ belonging to $L^1_{loc}(R)$, where $R$ is the interior of the range of $f$.
\end{enumerate}

 A suitable $g$ is 
\begin{equation} \label{g-function}
 g(z)=\int_{f(m)}^z e^{\int_{f(m)}^s (-1+q^{-}(t))\,dt}\,ds. 
\end{equation}  
\end{theorem}

\begin{proof}
Consider $f$ in a neighborhood of  a point $p\in M$. We assumed $\grad_p f\neq 0$ which
allows us to choose an orthonormal basis of $T_xM$ for $x$ in a neighborhood $U$ of $p$ as
before,  so that $e_1(x)=\frac{\grad_x f}{\norm{\grad_x f}} $ and $e_2(x),\dots,e_n(x)$ is
a basis of $\operatorname{span}\{e_1(x)\}^\perp$ which diagonalizes the second fundamental
form of the level set $f^{\scriptscriptstyle -1}(f(x))$ at the point $x\in U$. By
quasiconcavity of $f$ (condition (i)), these are all strictly positive. In terms of our
basis we have $\lambda_j=-\inner{\nabla_{e_j}e_1,e_j}$ (see e.g. \cite{Chavel}).

For any twice-differentiable function $g  \suchthat  \R\toarrow  \R$, the Hessian of $g
\of  f$ is given by $\grad^2 (g \of  f)=(g'' \of  f)df \tensor df + g' \of  f
\op{Hess}(f)$. We need to show that this is negative definite under the hypotheses.

Recall that in the above frame we computed the $(i,j)$-entry of the Hessian to be
$f_{ij}=\inner{\nabla_{e_i}(\nabla f),e_j}= \nabla_{e_i}\inner{\grad f,e_j}-\inner{\grad
f,\nabla_{e_i} e_j}$. By our choice of frame,  for $j>1$ the term $\inner{\grad f,e_j}$
identically vanishes, and so
\[
f_{ij}=-\inner{\grad
f,\nabla_{e_i}e_j}=-\norm{\grad f}\inner{e_1,\nabla_{e_i}e_j}=-\norm{\grad
f}(\nabla_{e_i}\inner{e_1,e_j}-\inner{\nabla_{e_i}e_1,e_j})=\norm{\grad
f}(\inner{\nabla_{e_i}e_1,e_j}).
\]

In particular $f_{ii}=-\norm{\grad f}\la_i$ when $i>1$.
Putting this together we compute the Hessian of $g\of f$ to be,
\begin{equation} \label{e21}
 \grad^2 (g \of  f)=(g'' \of  f)\begin{pmatrix}
\norm{\grad f}^2& 0 & 0 & \cdots &0\\
0& 0 & 0 & \cdots &0\\
0& 0 & 0 & \cdots &0\\
\vdots & \vdots & \ddots & \vdots &\vdots\\
0& 0 & 0 & \cdots &0
\end{pmatrix}+
(g' \of  f)\begin{pmatrix}
f_{11}&  f_{12}             &  f_{13}  &\cdots & f_{1n} \\
f_{21} & -\lambda_2 \norm{\grad f}     & 0         & \cdots & 0 \\
f_{31} & 0                      & -\lambda_3 \norm{\grad f}&  \cdots &0 \\
\vdots & \vdots                     & \ddots & \vdots & \vdots \\
f_{n1} &0                       &\cdots & 0 &-\lambda_{n}\norm{\grad f}
\end{pmatrix},
\end{equation}
Note we have $f_{1j}=-\inner{\grad f,\nabla_{e_1}e_j}$ for $j>1$, and moreover,
$$
 f_{11}=\frac{1}{\norm{\nabla f}^2}
\inner{\nabla_{\nabla f}\nabla f,\nabla f}=
\frac{\nabla_{\nabla f}\norm{\nabla f}^2}{2\norm{\nabla f}
^2}=\frac{\nabla_{\nabla f}\norm{\nabla f}}
{\norm{\nabla f}}=\nabla_{e_1}\norm{\nabla f},
$$
 or, in other words,
$f_{11}$ is the growth rate of $\norm{\nabla f}$ in the
$\nabla f$ direction.



Similarly, since $\inner{e_1,e_1}=1$ identically,
$\inner{e_1,\nabla_{e_j}e_1}=\frac12 e_j(\inner{e_1,e_1})=
0$. Therefore,
\begin{equation} \label{e22}
f_{1,j}=f_{j,1}=\nabla_{e_j}\inner{\grad
f,e_1}-\inner{\grad f,\nabla_{e_j}e_1}=\nabla_{e_j}
\norm{\nabla f}.
\end{equation}

Since the values $\la_i$ are all positive, we see that the principal minors, starting
from the lower right, alternate
sign. Hence in order to show that the eigenvalues of $\op{Hess}(g\of f)$ are all negative
it remains to show that the
sign of the entire determinant is $(-1)^n$.

Observe that for $j>1$, the $(1,j)$-minor matrix of the combined matrix, formed by
removing the first row and $j$-th column, can be made lower triangular by the following
operations. We move the $j-1$-th row of the minor matrix, whose entry begins with $f_{j1}$, to
the first row and shift all of the $j-2$ rows above the $j-1$-th row down by one. These
operations introduce a $(-1)^{j-2}$ factor to the value of the minor, the determinant of the minor matrix, which is then
$(-1)^{j-2}(g' \of  f) ^{n-1} f_{j1}\lambda_2\dots\lambda_{j-1}
\lambda_{j+1}\dots\lambda_n (-\norm{\grad f})^{n-2}$. In particular the $(1,j)$-
entry times the $(1,j)$-cofactor
for $j>1$, namely $(-1)^{j-1}f_{1j}(g'\of f)$ times the $(1,j)$-minor, is simply
$$(-1)^{n-1}(g' \of  f)^{n} \norm{\grad f}^{n-2}
\frac{f_{1j}^2}{\lambda_j}\prod_{i=2}^n\lambda_i.$$

Hence the sum of these expressions from $j=1$ to $n$, corresponding to the determinant expansion across the first row, yields the entire determinant of $\op{Hess}(g \of  f) $, namely
\begin{equation} \label{e23}
 \det \op{Hess}(g \of  f)=(-1)^{n-1}\left( \frac{g'' \of  f}{g' \of  f}
\norm{\grad f}^2+f_{11}+\sum_{j=2}^n
\frac{f_{1j}^2}{\lambda_j\norm{\grad f}}\right)(\norm{\grad f})^{n-1}(g' \of
f)^{n}\prod_{i=2}^n
\lambda_i.
\end{equation}

For $j<n$ the $j$-th (lower corner) principal minor, namely the determinant of the last
$j$ rows and columns, is $(-1)^j (g'\of f)^j \norm{\grad f}^{j}\prod_{i=n-j+1}^n
\lambda_i$. This sequence in $j$ has alternating sign since $\norm{\grad f}$, $g'$ and the
$\la_i$ are all positive. In order for $\op{Hess}(g \of  f)$ to be negative definite, it
remains to show that expression \eqref{e23} has sign $(-1)^n$. Since $f_{1j}^2$ is also
positive, this happens if and only if
\begin{equation} \label{e24}
 \frac{(g'' \of  f)}{(g' \of  f)} < \frac{1}{\norm{\grad f}^2}\left(-f_{\s 11}-\sum_{j=2}^n
\frac{f_{{\s 1}j}^2}{\lambda_j \norm{\grad f}}\right),
\end{equation}
which can   be satisfied for a given $f$ by a properly chosen $g$ with $g'> 0$ and $g''<0$,
provided that for almost every value $t$ in the range of $f$, the quantity
$$
\frac{1}{\norm{\nabla f}^2} \left(-f_{\s 11}-\sum_{j=2}^n
\frac{f_{{\s 1}j}^2}{\lambda_j \norm{\grad f}}\right)
$$
is bounded below by a value $q(t)>-\infty$ on the level set $f^{\scriptscriptstyle -1}(t)
$, and where $q^{-}\in L^1_{loc}$. By the theorem's assumption we have such a bound. The
$g$ function in the statement of the theorem then satisfies condition \eqref{e24}.

Conversely, $\grad f$ must be bounded, away from the maximum point $m$, by the condition in Theorem \ref{thm:metric}. If we cannot find such a function $q$ then we cannot
obtain a $g$ which everywhere satisfies the needed inequality, for the same reason as for
the analogous result in the proof of Theorem \ref{thm:1-d}.

\begin{comment}
   Since we assumed that the $C^1$ norm of $\nabla f$ is
bounded, and the    eigenvalues of the second fundamental form are uniformly
bounded away    from 0 (uniform quasiconcavity), it follows that each term
$\frac{f_{1j}^2}{\lambda_j}$ is uniformly bounded. Hence if the gradient is
uniformly positive on each level set, then we can solve for a smooth $g$.
\end{comment}

\end{proof}

Theorem \ref{thm:manifold} generalizes the ``one-point'' conditions of Fenchel
\cite{Fenchel} for $\R^n$ (as reformulated in Section 4 of \cite{Kannai:77})  to the
Riemannian setting. Kannai's condition (I) on  utility $v$ corresponds to our condition
(ii) on $f$. However he is allowing for weak concavifiability, which accounts for his
necessary conditions (II) and (III) differing from our condition (i) when the sublevel
sets of $v$ are not strictly convex. Otherwise,  these conditions are equivalent to our
condition (i)   and his conditions (IV) and (V) are folded into our condition (iii). This
is best seen through the rephrasing of Kannai's condition (IV) as (IV$'$) and noting that
his quantity ``$k$'' equals our $\norm{\grad f}$ and that under our assumptions in his
setting when $M=\R^n$, we have $-\la_j \norm{\grad f}=f_{jj}$. Note also that Kannai's
perspective is that of constructing a concave utility function based on  weakly convex
preference relations, whereas we start with an arbitrary function and see if it can be
concavified.

\begin{example}\label{ex:condition3}
{\bf  What condition (iii) excludes. } Condition (iii) can be easily violated by a $C^2$
function $f$ satisfying conditions (i) and (ii) by allowing for noncompact level sets
which become asymptotically flat sufficiently quickly as points tend to infinity. A simple
example is the quasiconcave function $f(x,y)=e^{e^x} y$  defined in the open positive
quadrant of $\R^2$, shown in Figure \ref{fig:condition3}. (While this is not a $C^2$
manifold with boundary, we could smooth the corner to make it so.)  Its gradient, $\grad
f=\left(e^{x+e^x} y,e^{e^x}\right)$, is nonvanishing and its Hessian restricted to the
level set of value $t$ as a function of the $x$ coordinate is $f_{22}=-\la_2 \norm{\grad
f}=-\frac{t e^x \left(e^x-1\right)}{t^2 e^{2 x-2 e^x}+1}$. Similarly, $f_{11}=\frac{t e^{2
x} \left(t^2 e^{x-2 e^x} \left(e^x+1\right)+2\right)}{t^2 e^{2 x-2 e^x}+1}$ and
$f_{12}=-\frac{e^{x+e^x} \left(t^2 e^x+e^{2 e^x}\right)}{t^2 e^{2 x}+e^{2 e^x}}$. The
negative definiteness shows that $f$ is strictly quasiconcave. The quantity in condition
(iii) on the level set of $t$ works out to be $\frac{1}{t(e^{-x}-1)}$, whose infimum over
$x>0$ is always $-\infty$ for each $t$, and thus $f$ is not concavifiable. Intuitively, a concavifying $g$ must raise the values of the level sets along the $y$-axis, whereas much further along the $x$-axis on the same level sets $g$ must squash the function $f$. 
\end{example}

 \begin{figure}[h!]
  \centering
 \includegraphics[width=1.5in]{condition3}
\caption{\sc A function violating condition (iii) of Theorem \ref{thm:manifold} and some level sets}
\label{fig:condition3}
 \end{figure}

\bigskip

\begin{remark}
Since $f_{1j}=-\inner{\grad f,\nabla_{e_1}e_j}$, in the special case that the integral
curves of the
vector field $\grad f$ lie along geodesics of $M$, then $f_{1j}=0$ for
all $j>1$. This occurs, for instance, when $f$ is constant on distance spheres about a
fixed point. In this case condition (iii) in Theorem \ref{thm:manifold} becomes vacuous.
\end{remark}

\bigskip

\begin{remark}
Some twice-differentiable functions $f$ with $\grad f$ vanishing at points other than the
maximum  can also be concavified, provided  we are willing to concavify using a   $g$
which is not twice differentiable. The more general condition is that after an initial
postcomposition by a non-twice differentiable function $g_o$ the resulting $g_o\of f$
must
satisfy conditions (ii) and (iii). In particular, when $\grad f$ vanishes at a point, it
must do so on the entire level set, though this alone is not sufficient.
\end{remark}

\bigskip

\begin{remark} % Remark 14
In contrast to Theorems \ref{thm:1-d} and \ref{thm:metric},  here $f$ is Lipschitz from
the beginning, by virtue of being twice differentiable, and moreover $\log (h\of f\of
\ga)'$ automatically belongs to $\op{BV}_{loc}$ for any twice differentiable increasing
function $h$ and geodesic $\ga$ under the assumption of condition (ii). Also, condition
(iii) of Theorem \ref{thm:manifold} is vacuous  for one-dimensional $M$ and $C^2$ function
$f$  when condition (ii) holds. So applying the theorem to one-dimensional examples is
pointless.
\end{remark}

If  $f$ is $C^2$ with nonvanishing gradient, then the quantity \eqref{e20} in the  infimum
of the definition of $q(t)$ in condition (iii) of Theorem \ref{thm:manifold} is uniformly
bounded and continuous on compact sets. (Recall that the $\la_j$ are uniformly positive on the convex compact level sets.) Moreover, the infimum of any compact family of
continuous functions is always continuous. Hence, we immediately obtain that the variation
function $q$ from \eqref{e20} is continuous if $f$ is $C^2$ with compact level sets.  We
express this as the following especially simple corollary. \bigskip


\begin{corollary}\label{cor:1}
If $f  \suchthat  M\toarrow  \R$ is strictly quasiconcave and $C^2,$ with compact level
sets, then there is a $C^2$ strictly concavifying $g$ if and only if $\grad f$ does not
vanish except possibly at $f$'s global maximum and minimum points, if any.
\end{corollary}

\begin{remark}
Fenchel's Example from Figure \ref{quasifig-aumann.jpg} does not
satisfy the conditions of Corollary \ref{cor:1}, because it is not strictly
quasiconcave. In fact, for any function  not strictly quasiconcave, at least
one of the principal curvatures $\la_i$ vanishes somewhere and thus quantity \eqref{e20}
becomes unbounded.
\end{remark}

%We can also work with the weak Hessian of $f$ for functions $f\in W^{2,1}$. Recall that a
%weak gradient for $f  \suchthat \Omega\subset\R^n\toarrow  \R$ is any function $\phi
%\suchthat \Omega\toarrow  \R^n$ such that for every smooth compactly supported function
%$\rho \suchthat  \Omega\toarrow  \R$,
%\begin{equation}\label{e26}
%\int_{\Omega}\phi(x) \rho(x)dx=-\int_\Omega f(x) (\grad
%\rho)(x) dx.
%\end{equation}
%
%We will denote any such weak gradient by $\nabla f$. This is justified, since from the
%definition any two weak gradients agree almost everywhere. By taking charts and using the
%volume forms one can see that this definition extends to arbitrary tensors on arbitrary
%smooth manifolds. Define $W^{0,p}(M)$ to be $L^p(M)$, which we extend to denote the space
%of $L^p$ tensors of any type on $M$. We then extend inductively by defining $f\in W^{k,p}(M)$
%if $\nabla f\in W^{k-1,p}(M)$. We only used $L^1$ existence of second derivatives in Theorem
%\ref{thm:manifold}'s proof,  though all inequalities must be understood in the weak sense of holding only after integrating against positive test functions. Thus, we obtain another corollary. 
%%Nah q(t) doesn't necessarily exist anywhere!
%
%\begin{corollary}\label{cor:2}
%The result of Theorem \ref{thm:manifold} holds for $f\in W^{2,1}(M)$, provided we interpret condition (ii) and the conclusion in the weak sense. 
%\end{corollary}
%
%For $f\in W^{2,1}(M)$, taking small local convolutions yields smooth functions $f_\eps
%\suchthat M\toarrow \R$ whose Hessians converge in $L^1$ to the weak Hessian of $f$.
%Hence, the $W^{2,1}(M)$ Sobolev space provides a large and flexible class of functions
%with good closure and embedding properties for which the ``differential'' conditions in
%Theorem~\ref{thm:manifold} are still easy to check.
%
%%The space  $W^{2,1}$ is a fairly large, and flexible, class frequently used in
%%the theory of partial differential equations because of its closure properties and
%%techniques for embedding it in other  function spaces.

%---------------------------------------------------------

%
%\section{Concluding Remarks}
%
%  We have tried in this article to clarify the relationship between
%concavity and quasiconcavity at two levels. The first level is the
%intuitive one, where we have explored when continuous  strictly
%quasiconcave functions, whether  differentiable or not, are functions
%that can be monotonically blown up into strictly concave functions.  The
%second level is the rigorous one, where we have shown that the intuition
%holds true for arbitrary geodesic metric spaces of any dimension, but
%subject to caveats that apply even in $\R$, caveats involving the
%Lipschitz continuity of the function and the amount of variation in its
%derivatives.  


%---------------------------------------------------------------
\bigskip

%\section*{References}


\begin{thebibliography}{AAA}
\bibliographystyle{myalpha}
%\bibliography{allbib}

\bibitem{Aubin}
Aubin, Thierry, {\it Nonlinear Analysis on Manifolds. Monge-Ampre equations}.
Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical
Sciences], vol. 252, Berlin, New York: Springer-Verlag (1982).

\bibitem{Aumann}
Aumann,  Robert, ``Values  of Markets  with  a Continuum  of
Traders,''  {\it  Econometrica},  43:(1975) 611--646.
 
\bibitem{Chavel}
Chavel, Isaac (1993) {\it Riemannian Geometry--- A  Modern  Introduction},  Cambridge Tracts
  in Mathematics, vol. 108, Cambridge University Press, Cambridge (1993).


\bibitem{DeFinetti}
DeFinetti, B.,  ``Sulle Stratificazioni Convesse,"  {\it Annali di
Matematica}, 30:(1949) 173--183.

\bibitem{Fenchel}
Fenchel,  W., ``Convex  Cones,  Sets,  and  Functions,'' unpublished notes, Princeton
Mathematics Department,  Princeton, New Jersey.  (1953) \url{http://rasmusen.org/x/abros/fenchel.pdf}.

\bibitem{Folland}
Folland, G. B., {\it Real Analysis. Modern Techniques and Their
Applications}, Pure and Applied Mathematics Series, New York: John Wiley \&
Sons Inc.  (1984).

\bibitem{Ginsberg}
Ginsberg, W., ``Concavity and Quasiconcavity in Economics,'' {\it Journal of
Economic Theory},  6:(1973) 596--605.
 
\bibitem{Guerragio}
Guerraggio, Angelo  \&  Elena Molho, ``The Origins of Quasiconcavity:
A Development between Mathematics and Economics,'' {\it Historia
Mathematica},  31:(2004) 62--75.

%\bibitem{Hjerstrand}
%Hjertstrand, Per, ``A Generalized Afriat's Theorem,''
%working paper,   Department of Economics, Lund University, (2011).

\bibitem{Kannai:77}
Kannai, Yakar,    ``Concavifiability and   Constructions of  Concave
Utility Functions,''   {\it Journal  of Mathematical  Economics},   4:(1977)
l--56.

\bibitem{Kannai:81}
Kannai, Yakar,  ``Concave Utility Functions--- Existence, Construction, and
Cardinality,''  pp. 543-612 of     {\it  Generalized Concavity in Optimization and
Economics,} ed. by Siegried Schaible and William T. Ziemba, New York: Academic Press,
(1981).

\bibitem{Kannai:05}
Kannai, Yakar, ``Remarks Concerning Concave Utility Functions on Finite Sets,''
{\it Journal of Economic Theory} 26:(2005) 333--344.

%\bibitem{Matzkin}
%Matzkin, Rosa L. \& Marcel K. Richter, ``Testing Strictly Concave
%Rationality,'' {\it Journal of Economic Theory},
% 53:(1991) 287--303.

\bibitem{Papadopoulos}
Papadopoulos, Athanase, {\it Metric Spaces, Convexity and Nonpositive Curvature},
  IRMA Lectures in Mathematics and Theoretical Physics, vol.~6, European
  Mathematical Society (EMS), Z\"urich (2005).

 
\bibitem{Rapsak}
Rapcsak, T., ``Survey of the Fenchel Problem of Level Sets,'' in {\it Variational
Analysis and Applications,}
F. Giannessi and A. Maugeri (eds), pp. 935--956,
Dordrecht, Holland: Kluwer Academic Publishers  (2005).

%
%Reny, Philip J. (2010) ``A Simple Proof of the Nonconcavifiability of
%Functions
%with Linear Not-All-Parallel Contour Sets,'' working paper,
%Department of Economics,
%University of Chicago
%(October 2010).

\bibitem{Richter}
Richter, Marcel K. \& K.-C. Kam-Chau Wong, ``Concave Utility on Finite
Sets,'' {\it
Journal of Economic Theory,}
 115:(2004) 341--357.

\bibitem{Ziemer}
Ziemer, William, {\it Weakly Differentiable Functions}. Graduate Texts in
Mathematics, New York: Springer-Verlag
(1989).
\end{thebibliography}
\end{document}

