\section{Introduction}

In this paper we investigate stationary viscous Mean Field Games (MFG) systems of the form
\begin{equation}\label{MFG}
\begin{cases}
- \Delta u(x) + H(\nabla u(x)) + \lambda = V(x) - f(m(x))  \\
- \Delta m(x) -{\rm div}(\nabla H(\nabla u(x)) \, m(x)) = 0  & \text{in $\Omega$}  \\
\int_\Omega m \, dx = 1, \, m > 0,
\end{cases}
\end{equation}
where the function $f$ is non-negative, and $\Omega \subseteq  {\mathbb{R}^N} $. In particular, we have in mind nonlinearities of the form
\begin{equation}\label{Hf_partic}
H(p) = \frac{1}{\gamma} |p|^{\gamma}, \quad \gamma > 1, \qquad \text{and} \qquad f(m) = C_f m^{\alpha}, \quad C_f, \alpha > 0.
\end{equation}

The MFG system \eqref{MFG} captures Nash equilibria of infinite-horizon games with a large number of indistinguishable rational agents, who seek to optimize an individual utility. In particular, a typical agent of the game, distributed in the long-time regime with invariant density $m$, pays a cost which depends on his velocity and $V(x) - f(m(x))$, where $x \in \Omega$ is his own state. While $V$ can be considered as a fixed potential, $-f(m(x))$ depends on the distribution $m$ itself: this term realizes the coupling between the individual and the overall population, and the coupling between the Hamilton-Jacobi-Bellman and the Kolmogorov equations in \eqref{MFG} at the PDE level. In this model, every agent is also subject to a Brownian noise.

From the game point of view, if $-f(\cdot)$ is an increasing function every individual aims at avoiding regions where the population is highly distributed. This class of MFG systems has received a considerable attention in the last years, starting from the seminal works \cite{HCM1, HCM2, jeux1, jeux2, LasryLions}. It has been shown that \eqref{MFG} corresponds to the long-time limit of non-stationary MFG (see \cite{Cardalialong, Cardalialong2}). For a description and up-to-date developments on MFG we refer the reader to \cite{MR3134900, MR3195844, Cardalianotes, LionsVideo}.

Here, we address the problem of existence of solutions to \emph{focusing} MFG systems, namely when the coupling $-f(\cdot)$ in \eqref{MFG} is a \emph{decreasing} function; that is, we assume that every player of the game is attracted by regions where the population is highly distributed. As far as we know, this setting has not yet been expolored systematically; a study in the quadratic and linear-quadratic case has been carried out in \cite{BardiPriuli, gueant09, gueant12}. A serious technical difficulty here comes from the fact that the couplings $-f$ we consider are not bounded from below. The particular coupling $-f(m) = \log m$, having the opposite monotonicity but lacking of boundedness from below, has been treated for example in \cite{PV, GomesPimentel} (see also references therein). Still, we consider this framework \emph{defocusing}, as $ \log(\cdot)$ is increasing. We stress that in our case the lack of increasing monotonicity of $-f$ cuts off from a large class of general approaches that have been developed in the MFG literature, for example in \cite{CardaliaguetGraber, PorrettaWeak, GomesFerreira}.

As for the existence of solutions, we set our problem on the flat torus, i.e. $\Omega =  {\mathbb{T}^N} $; in this setting we avoid boundary issues, and exploit compactness of the state space. Our focus is to obtain solutions $(u, \lambda, m)$ of \eqref{MFG} such that $\nabla u$ and $m$ are (at least) \emph{bounded}. We believe that this requirement is meaningful from the point of view of the game: $-\nabla H(\nabla u)$ provides (formally) the optimal strategy of an average player in feedback form, and bounded $\nabla u$ guarantees boundedness of the optimal velocity (and therefore an agent does not have to move with infinite velocity). Moreover, boundedness of $m$ is a crucial point in our analysis: here, $m$ has an intrinsic tendency to concentrate and hence to develop singularities. We have to carefully examine the delicate interplay between the Brownian motion, that has a smoothing effect on the distribution, and the focusing behavior of the distribution itself, which is not an issue in the defocusing case.

At the PDE level, even a-priori bounds on the ergodic constant $\lambda$ are not obvious, as well as $L^1$ bounds on $m^{\alpha+1}$ and $|\nabla u|^\gamma m$, which are related to the ``energy'' of the system \eqref{MFG} (see Remark \ref{rem:var}); those bounds are somehow ``for free'' in the defocusing case. We clarify this aspect of the problem through Proposition \ref{prop_energy} and Corollary \ref{cor_energy}, which establish a regularity result for Kolmogorov equations (of independent interest), providing estimates on $m^{\alpha+1}$ with respect to $|\nabla u|^\gamma m$. In particular, we observe that there are two ``critical'' exponents
\[
\alpha_1 = \frac{\gamma'}{N} \quad < \quad \alpha_2 = \frac{\gamma'}{N-\gamma'},
\]
(where $\gamma' = \gamma/(\gamma-1)$ is the usual conjugate exponent) that give rise to three different qualitative behaviors for \eqref{MFG}:  if $\alpha \in (0, \alpha_1)$, then $\lambda$ and the ``energy'' are bounded a-priori (and hence a solution exists), while if $\alpha \in [\alpha_1, \alpha_2)$ estimates can be obtained only under additional conditions on the coupling. If $\alpha \in (\alpha_2, \infty)$ we will see that the problem may not possess bounded solutions. Such critical exponents can be better understood by having a look at the variational formulation of \eqref{MFG}, that is discussed in Remark \ref{rem:var}; basically, $\alpha_2$ is related to the Sobolev critical exponent, while $\alpha_1$ comes from the Gagliardo-Nirenberg inequality and the $L^1$ constraint on $m$.

\smallskip

We suppose that $H \in C^2( {\mathbb{R}^N}  \setminus \{0\})$ and that there exist $C_H > 0$, $\gamma > 1$ such that
\begin{equation}\label{Hass}
\begin{split}
\bullet \quad & C_H^{-1}|p|^\gamma-C_H \le H(p) \le C_H(|p|^{\gamma} + 1), \\
\bullet \quad & |\nabla H(p)| \le  C_H(|p|^{\gamma-1} + 1),\\
\bullet \quad & \nabla H(p) \cdot p - H(p) \ge C_H^{-1} |p|^\gamma - C_H,
\end{split}
\end{equation}
for all $p \in  {\mathbb{R}^N} $. Moreover, $f \in C^1((0, \infty))$, $V \in C^1(\Omega)$ and there exist $\alpha, C_f, C_V > 0$ such that
\begin{align}
& 0 \le f(m) \le C_f(m^\alpha + 1) \quad \text{for all $m \ge 0$}, \label{fass} \\
& 0 \le V(x) \le C_V \quad \text{for all $x \in  {\mathbb{R}^N} $}. \label{Vass1}
\end{align}
Of course, the model nonlinearities \eqref{Hf_partic} satisfy \eqref{Hass}, \eqref{fass}. Note that we are not requiring monotonicity of $f$ in general; our methods really rely on the behavior of $f$ at infinity.

The first main result of this paper, regarding existence of solutions in the ``subcritical'' case $\alpha < {\gamma'}/({N-\gamma'})$, is stated in the following

\begin{thm}\label{thm_existence}
Let $\Omega =  {\mathbb{T}^N} $, $H, f, V$ be such that \eqref{Hass}, \eqref{fass}, \eqref{Vass1} hold. If
\[
\alpha < \gamma'/N,
\]
then there exists a solution $(u, \lambda, m) \in C^2( {\mathbb{T}^N} ) \times \mathbb{R} \times W^{1,p}( {\mathbb{T}^N} )$, for all $p > 1$, of \eqref{MFG}. Else, if
\begin{equation}
\gamma'/N \le \alpha < \begin{cases}
\gamma'/(N-\gamma') & \text{if $\gamma' < N$} \\
\infty & \text{if $\gamma' \ge N$,}
\end{cases}
\end{equation}
a solution $(u, \lambda, m)$ of \eqref{MFG} exists under the additional condition that $C_f$ (in \eqref{fass}) is small enough.
\end{thm}

The proof of Theorem \ref{thm_existence} relies on an approximating procedure. Proposition \ref{prop_energy} provides the main estimates for $\lambda$ and the $L^1$ norm of $m^{\alpha +1}$ and $|\nabla u|^\gamma m$ (see \eqref{EI1}-\eqref{EI2}). The standard tool of Schauder's fixed point theorem implies the existence of a solution $(u_k, \lambda_k, m_k)$ of a suitable ``regularized'' version of \eqref{MFG}. It is crucial to produce  approximate solutions whose energy is uniformly bounded with respect to $k$. Still, such estimates are not powerful enough to pass to the limit $k \to \infty$ in the approximating problem \eqref{mkdef}. The new idea presented here, which is used to obtain uniform $L^\infty$ bounds for $m_k$, leans on a blow-up method and exploits the scaling properties of \eqref{MFG}. We observe that our blow-up procedure works if $\alpha$ is below the critical exponent $\alpha_2$, which is the same exponent that appears in Proposition \ref{prop_energy}. This key bound enables us to use the machinery of Schauder and classical elliptic estimates, and to prove the existence of a regular solution of \eqref{MFG}.

\begin{rem} We want Hamiltonians of the form \eqref{Hf_partic} to fit into our theory, and therefore we cannot expect to obtain \emph{classical} solutions in general: even if $u$ is $C^\infty$, $\nabla H(\nabla u)$ is just an Holder function if $\gamma < 2$, so $m$ may not be a solution in the classical sense of the Kolmogorov equation in \eqref{MFG}. We will look for solutions $(u,m) \in C^2 \times W^{1,p}$, and consider them ``regular'', at least if compared with \emph{weak} solutions that are obtained by other methods in the defocusing case (see \cite{PorrettaWeak} and \cite{GomesFerreira}). Still, if $\gamma \ge 2$, or if $\nabla H$ is suitably regular, solutions will be a-posteriori smooth in view of $L^\infty$-boundedness of $m$, $\nabla u$.
\end{rem}

The second part of this work focuses on the ``supercritical'' case $\alpha \ge \gamma'/(N-\gamma')$. In this regime, the fast decay of the coupling $-m^\alpha$ might not be compensated by viscosity, leading to spike formation in the distribution $m$. This point can be made more clear by considering the variational formulation of \eqref{MFG} (see again Remark \ref{rem:var}), where ``compactness'' of the problem is somehow lost.

We shift our attention to the whole space, that is $\Omega =  {\mathbb{R}^N} $. The flat torus is indeed not suitable anymore for studying non-existence and concentration phenomena, as $(u, m) \equiv (0, 1)$ is always a solution of \eqref{MFG} if $\Omega =  {\mathbb{T}^N} $, for all $\alpha > 1$. An unbounded state space boils down the possibility of having the constant solution. We will also set $V \equiv 0$, for simplicity, and $H$ will be of the form \eqref{Hf_partic}. Moreover, we will consider classical solutions $u$ satisfying the following condition at infinity (see the discussion in Remark \ref{rem:infinity}).
\begin{equation}\label{uinfty}
\text{$u \to +\infty$ as $|x| \to \infty$}, \quad \text{and} \quad \text{$\exists c, \eta > 0$ s.t. $|\nabla u(x)| \le c(|x|^\eta + 1), \forall x \in  {\mathbb{R}^N} $.}
\end{equation}

In order to understand \eqref{MFG} in the case $\alpha \ge \gamma'/(N-\gamma')$ we multiply the equations in \eqref{MFG} by $x \cdot \nabla m$ and $x \cdot \nabla u$, and obtain new integral identities (see Proposition \ref{pohozaev}). Let us set \[F(m) := \int_0^m f(s) \, ds,\]
and suppose that the following condition holds true:
\begin{equation}\label{fass2}
(N-\gamma') f(m) m - N F(m) > 0 \quad \text{for all $m > 0$.}
\end{equation}
Note that if $f$ is of the form \eqref{Hf_partic} and $\alpha > \gamma'/(N-\gamma')$, then \eqref{fass2} holds.

The second main result of this paper, regarding non-existence of ``regular'' solutions, is stated as follows.

\begin{thm}\label{thm_nonex} Let $\Omega =  {\mathbb{R}^N} $, suppose that $H$ is of the form \[ H(p) = \frac{1}{\gamma} |p|^\gamma, \quad \gamma > 1, \] that \eqref{fass2} holds, and $V \equiv 0$. Then, \eqref{MFG} has no solutions $(u, \lambda, m) \in C^2( {\mathbb{R}^N} ) \times \mathbb{R} \times W^{1,1}( {\mathbb{R}^N} )$ satisfying
\begin{equation}\label{finiteness}
\int_{\Rset^N} |\nabla u|^\gamma m \, dx < \infty, \quad \int_{\Rset^N} m^{\alpha+1} \, dx < \infty, \quad \int_{\Rset^N} |\nabla u |\, |\nabla m| \, dx < \infty
\end{equation}
and \eqref{uinfty}.
\end{thm}

Theorems \ref{thm_existence} and \ref{thm_nonex} give a rather precise picture of the problem of existence of regular solution for \eqref{MFG}, showing that criticality phenomena arise. We have chosen the state space $ {\mathbb{R}^N} $ in the non-existence part of the work in order to avoid some technical difficulties, but we believe that existence of solutions can be obtained under the same assumptions on the growth of $f$ of Theorem \ref{thm_existence}. This and other aspects of MFG systems on the whole space will be matter of future work. The critical case $\alpha = \gamma'/(N-\gamma')$ is also not covered by our theorems.

We conclude our study of focusing MFG by considering uniqueness of solutions. Even though the standard uniqueness condition by Lasry-Lions (see, for example, \cite{LasryLions}) is violated, we can lean on some results on uniqueness of ground states of nonlinear Schr\"odinger equations and show that solutions of a particular class of quadratic MFG systems are unique. The main difficulty here is that $u,m$ might not be unique even if the ergodic constant $\lambda$ is fixed, and $\lambda$ is itself an unknown of the problem; this issue is circumvented by exploiting invariances of the system. Our considerations on this aspect of the problem are collected in Section \ref{s:unique}.

\medskip

We mention that the methods developed here for focusing MFG can be implemented also to study defocusing MFG systems, that is
\begin{equation}\label{MFGde}
\begin{cases}
- \Delta u(x) + H(\nabla u(x)) + \lambda = V(x) + f(m(x))  \\
- \Delta m(x) -{\rm div}(\nabla H(\nabla u(x)) \, m(x)) = 0  & \text{in $\Omega$}  \\
\int_\Omega m \, dx = 1, \, m > 0,
\end{cases}
\end{equation}

Following the same lines of the proof of Theorem \ref{thm_existence}, we are able to prove the following
\begin{thm}\label{thm_existence_def}
Let $\Omega =  {\mathbb{T}^N} $, $H, f, V$ be such that \eqref{Hass}, \eqref{fass}, \eqref{Vass1} hold. If
\begin{equation*}
\alpha < \begin{cases}
\gamma'/(N-\gamma') & \text{if $\gamma' < N$} \\
\infty & \text{if $\gamma' \ge N$,}
\end{cases}
\end{equation*}
then there exists a solution $(u, \lambda, m) \in C^2( {\mathbb{T}^N} ) \times \mathbb{R} \times W^{1,p}( {\mathbb{T}^N} )$, for all $p > 1$, of \eqref{MFGde}.
\end{thm}

Existence of smooth solutions for \eqref{MFGde} is still an open problem for general power-like nonlinearities, and known results require conditions on the exponents $\alpha, \gamma$; see \cite{MR3333058, GomesPatrizi, GomesMorgado, PV}. As far as we know, the best available results are contained in \cite{PV}, and require $\alpha \le \gamma'/N$. We are able to improve this condition in Theorem \ref{thm_existence_def}. We stress that the critical exponent $\gamma'/(N-\gamma')$ does not seem to be optimal in the defocusing case (if $\gamma =2$, smooth solutions exist for all $\alpha \ge 0$ and for all $N$), but is fundamental in the focusing case, where concentration of solutions is intrinsically likely to arise.

This paper is structured as follows. In Section \ref{s:ex} we will discuss the existence of solutions for \eqref{MFG} in the flat torus. Section \ref{s:nonex} will be devoted to the non-existence proof in the whole space, by means of Pohozaev identities. In Section \ref{s:unique} we will collect some observations on uniqueness of solutions in some special cases, while in Appendix \ref{a:defoc} we will prove the existence of regular solutions in the defocusing and ``subcritical'' case.

{\bf Notation.} Throughout the paper, we will refer to the HJB equation and to the Kolmogorov equation in \eqref{MFG} as the first and second equation of the system, respectively. For all $R > 0$, $x \in  {\mathbb{R}^N} $, $B_R(x) := \{y \in  {\mathbb{R}^N} : |y-x| < R\}$, $B_R := B_R(0)$. If $\Omega$ is a smooth domain of $ {\mathbb{R}^N} $, $\nu$ will denote the outward normal vector field at $\partial \Omega$.  Finally, $C, C_1, C_2,\ldots$ will be (positive) constants we need not to specify.

\section{Existence of solutions}\label{s:ex}

This section is devoted to the proof of existence of solutions to \eqref{MFG}, where the state space $\Omega$ is the flat torus $ {\mathbb{T}^N} $. Unless otherwise specified, $L^p$ and $W^{1,p}$ norms will be intended on $ {\mathbb{T}^N} $, that is $\| \cdot \|_{L^p} = \| \cdot \|_{L^p( {\mathbb{T}^N} )}$. We will always assume that $H$ satisfies \eqref{Hass} and $\alpha$ of assumption \eqref{fass} will be such that
\begin{equation}\label{critical_alpha}
\alpha < \begin{cases}
\gamma'/(N-\gamma') & \text{if $\gamma' < N$} \\
\infty & \text{if $\gamma' \ge N$.}
\end{cases}
\end{equation}

We start by recalling some classical results on regularity of solutions of uniformly elliptic and HJB equations, that will be used in the sequel.

\begin{prop}\label{ell_regularity} Let $\Omega \subseteq  {\mathbb{R}^N} $, $p > 1$ and $u \in L^p(\Omega)$ be such that
\[
\left| \int_\Omega u \, \Delta \varphi \, dx \right| \le K\|\varphi\|_{W^{1,p'}(\Omega)} \quad \text{for all $\varphi \in C^\infty_c(\Omega)$}
\]
for some $K > 0$. Then, for all $\Omega' \subset \subset \Omega$, $u \in W^{1,p} (\Omega')$ and there exists $C > 0$, depending on $\Omega$, $\Omega'$ and $p$ such that
\[
\|u\|_{W^{1,p}(\Omega')} \le C(K + \|u \|_{L^p(\Omega)}).
\]
\end{prop}

\begin{proof} See, for example, \cite[Theorem 6.1]{agmon}. \end{proof}

\begin{prop}\label{hjb_regularity} Suppose that $\Omega \subseteq  {\mathbb{R}^N} $, $H$ satisfies \eqref{Hass} and $u \in C^2( {\mathbb{R}^N} )$ is such that
\[
\left| -\Delta u + H(\nabla u) \right| \le K \quad \text{in $\Omega$}.
\]
Then, for all $\Omega' \subset \subset \Omega$, $q > 1$,
\[
\|\nabla u\|_{L^q(\Omega')} \le C,
\]
where $C > 0$ depends on $\Omega'$, $\Omega$, $K$, $q$ and $C_H, \gamma$ in \eqref{Hass}.
\end{prop}

\begin{proof} This estimate, which relies on the Bernstein method, has been proved in \cite[Theorem A.1]{lasry1989nonlinear} when $H$ is of the form \eqref{Hf_partic}. If one looks carefully at the proof, it is possible to carry out the same procedure also for perturbations of that Hamiltonians, namely when $H$ satisfies \eqref{Hass}. A detailed proof in this case can be found in \cite{PV}, where the HJB equation is set on the flat torus $ {\mathbb{T}^N} $. \end{proof}

In the following proposition we prove the inequalities \eqref{EI1A}-\eqref{EI2A}, by a delicate combination of Sobolev embeddings and elliptic regularity. The idea of the first part of the proof comes from \cite{Metafune}; here we compute explicitly some key exponents. As for \eqref{EI2A}, it follows by an appropriate use of the Gagliardo-Nirenberg inequality.

\begin{prop}\label{prop_energy} Suppose that $m \in W^{1,2}( {\mathbb{T}^N} )$, $A \in L^{\infty}( {\mathbb{T}^N} )$ solve (weakly\footnote{that is: $\int_\Tn \nabla m \cdot \nabla \varphi - m A \cdot \nabla \varphi = 0$ for all $\varphi \in C^{\infty}( {\mathbb{T}^N} )$.})
\begin{equation}\label{kolmo}
- \Delta m(x) + {\rm div}(A(x) \, m(x)) = 0 \quad \text{in $ {\mathbb{T}^N} $}, \qquad \int_ {\mathbb{T}^N}  m \, dx = 1.
\end{equation}

Then, for all $\beta > 1$ such that
\begin{equation}\label{beta}
\beta < \begin{cases}
1 + \gamma'/(N-\gamma') & \text{if $\gamma' < N$} \\
\infty & \text{if $\gamma' \ge N$,}
\end{cases}
\end{equation}
there exists $C > 0$ and $\delta > 1$, depending on $\beta$, $N$ and $\gamma'$ such that
\begin{equation}\label{EI1A}
\|m\|^\delta_{L^\beta} \le C\left(\int_\Tn |A|^{\gamma'} m  \, dx  + 1\right).
\end{equation}

Moreover, for all $1 < \beta < 1 + \gamma'/N$ it holds true that
\begin{equation}\label{EI2A}
\|m\|^{\delta \beta}_{L^\beta} \le C\left(\int_\Tn |A|^{\gamma'} m \, dx  + 1\right).
\end{equation}

\end{prop}

\begin{proof} Set
\begin{equation}\label{Edef}
E := \int_{\Rset^N} |A|^{\gamma'} m \, dx.
\end{equation}
The inequality \eqref{EI1A} will be proved firstly. One observes that $m$ solves \eqref{kolmo}, so
\[
\left| \int_\Tn m \, \Delta \varphi \, dx \right| \le \int_\Tn |A| m^{1/\gamma'} \, m^{1- 1/\gamma'} \, |\nabla \varphi| \, dx,
\]
and an application of the Holder inequality provides
\[
\left| \int_\Tn m \, \Delta \varphi \, dx \right| \le E^{1/\gamma'}\|m\|^{1/\gamma}_{L^{\beta}} \|\nabla \varphi\|_{L^{r'}},
\]
where the following equality holds
\[
\qquad \frac{1}{r} = \frac{1}{\gamma'} + \left(1 - \frac{1}{\gamma'}\right)\frac{1}{\beta}.
\]
In view of Proposition \ref{ell_regularity} one argues that
\[
\|m\|_{W^{1,r}} \le C_r (E^{1/\gamma'}\|m\|^{1/\gamma}_{L^{\beta}} + \|m\|_{L^r}).
\]
By interpolation $\|m\|_{L^r} \le \|m\|^{1/\gamma'}_{L^1} \|m\|^{1/\gamma}_{L^{\beta}}$, so
\begin{equation}\label{eq11}
\|m\|_{W^{1,r}} \le C_1 \|m\|^{1/\gamma}_{L^{\beta}} (E^{1/\gamma'} + 1),
\end{equation}
and by standard Sobolev embedding one has
\begin{equation}\label{eq12}
\|m\|_{L^{\eta}}  \le C_2 \|m\|^{1/\gamma}_{L^{\beta}} (E^{1/\gamma'} + 1),
\end{equation}
where
\[
\frac{1}{\eta} = \frac{1}{r} - \frac{1}{N} = \frac{1}{\gamma'} - \frac{1}{N} + \left(1 - \frac{1}{\gamma'}\right)\frac{1}{\beta}.
\]
Note that $1 < r < N$, if $\gamma' < N$. One verifies also that $\eta > \beta$, because $\beta < N/(N-\gamma')$. Therefore, again by interpolating between $L^1$ and $L^{\eta}$ there exists $0 < \theta < 1$ such that
$\|m\|_{L^{\beta}} \le \|m\|_{L^{\eta}}^\theta$, and it follows that
\[
\|m\|^{1/\theta}_{L^{\beta}}  \le C_2 \|m\|^{1- 1/\gamma'}_{L^{\beta}} (E^{1/\gamma'} + 1).
\]
Hence one has \eqref{EI1A} by setting $\delta = 1 + (1/\theta-1) \gamma'$.

If $\gamma' \ge N$, then \eqref{eq12} is satisfied for all $\eta \ge 1$, so the claimed inequality \eqref{EI1} again follows by interpolation between $L^1$ and $L^{\eta}$, with $\eta$ large enough.

In order to prove \eqref{EI2A}, the Gagliardo-Nirenberg inequality will be used instead of the Sobolev inequality. In particular, one has
\[
\|m\|_{L^{\eta}}  \le C_3 ( \| \nabla m \|_{L^r}^{N/(N+1)} \| m \|_{L^1}^{1/(N+1)} + \| m \|_{L^r}^{N/(N+1)}),
\]
where
\[
\frac{1}{\eta} = \left(\frac{1}{r} - \frac{1}{N}\right) \frac{N}{N+1} + 1 -  \frac{N}{N+1} = \frac{N}{N+1}\left[\frac{1}{\gamma'} + \left(1 - \frac{1}{\gamma'}\right)\frac{1}{\beta}\right],
\]
so, by plugging \eqref{eq11} into the last inequality,
\[
\|m\|^{(N+1)/N}_{L^{\eta}}  \le C_4 \|m\|^{1/\gamma}_{L^{\beta}} (E^{1/\gamma'} + 1).
\]
It is now crucial to observe that $\eta > \beta$ because $\beta < 1 + \gamma'/N$. Arguing by interpolation as before one has
\[
\|m\|^{(N+1)/(\theta N)}_{L^{\beta}}  \le C_5 \|m\|^{1- 1/\gamma'}_{L^{\beta}} (E^{1/\gamma'} + 1),
\]
which implies
\[
\|m\|^{1 + \gamma' (N+1)/(\theta N) - \gamma'}_{L^{\beta}}  \le C_6(E + 1).
\]
The inequality \eqref{EI2} then follows because $1 + \gamma' (N+1)/(\theta N) - \gamma' \ge \gamma'/N + 1 > \beta$.

\end{proof}

\begin{cor}\label{cor_energy} Suppose that $(u, m) \in C^2( {\mathbb{T}^N} ) \times W^{1,2}( {\mathbb{T}^N} )$ solves the Kolmogorov equation in \eqref{MFG}. Then, for all $\beta$ satisfying \eqref{beta},
\begin{equation}\label{EI1}
\|m\|^\delta_{L^\beta} \le C\left(\int_\Tn |\nabla u|^\gamma m \, dx  + 1\right),
\end{equation}
and for all $1 < \beta < 1 + \gamma'/N$ it also holds true that
\begin{equation}\label{EI2}
\|m\|^{\delta \beta}_{L^\beta} \le C\left(\int_\Tn |\nabla u|^\gamma m \, dx  + 1\right).
\end{equation}
\end{cor}

The corollary clearly follows from \eqref{EI1A}, \eqref{EI2A}, with $A = -\nabla H(\nabla u)$ and the assumptions on the Hamiltonian \eqref{Hass} ($C$ will also depend on $C_H$).

\begin{rem}\label{rem_energy} If one goes back to the proof of Proposition \ref{prop_energy}, boundedness of $\int |A|^{\gamma'} m$ implies uniform boundedness of $\|m\|_{L^\beta}$ for all $\beta$ satisfying \eqref{beta}, but also that any solution of the Kolmogorov equation $m_k$ such that $\int |A_k|^{\gamma'} m_k \le C$ converges (up to subsequences) in $L^\beta( {\mathbb{T}^N} )$. This is true because Sobolev embeddings are compact (see \eqref{eq11}-\eqref{eq12}).
\end{rem}

We are now ready to prove the main existence result, which will be obtained through a fixed point/approximation scheme. Several lemmas will provide the required regularity of the approximating problem, and will justify the limiting procedure.

\begin{proof}[Proof of Theorem \ref{thm_existence}]

Let $k$ be a positive integer, $\psi$ be a radial mollifier (i.e. $\psi \ge 0$ and $\int_{\Rset^N} \psi = 1$) and
\[
\psi_k := k^N \psi(kx), \quad \forall k \ge 1, x \in  {\mathbb{R}^N} .
\]
Of course $\int_{\Rset^N} \psi_k = 1$ for all $k$. Let $(u_k, \lambda_k, m_k) \in C^2( {\mathbb{T}^N} ) \times \mathbb{R} \times W^{1,p}( {\mathbb{T}^N} )$ be the defined by
\begin{equation}\label{mkdef}
\begin{cases}
- \Delta u_k + H(\nabla u_k) + \lambda_k = V(x) - f(m_{k} \star \psi_k(x))  \\
- \Delta m_k -{\rm div}(\nabla H(\nabla u_k) \, m_k) = 0  & \text{in $ {\mathbb{T}^N} $},  \\
\int_\Tn m \, dx = 1, \, m > 0,
\end{cases}
\end{equation}
where $\star$ is the standard convolution operator.

\begin{lem}\label{lemma_welldef} If $\alpha < \gamma'/N$,
\begin{align}
\bullet \quad &\text{the triple $(u_k, \lambda_k, m_k)$ is well-defined for all $k \in \mathbb{N}$,} \label{welldef} \\
\bullet \quad & \text{$\exists C > 0$ s.t. $\forall k \ge 1$,} \quad |\lambda_k| \le C, \quad \int_\Tn m_k^{\alpha+1} \, dx \le C, \quad \int_\Tn |\nabla u_k|^{\gamma} m_k \, dx \le C. \label{energybound}
\end{align}

Otherwise, if $\alpha \ge \gamma'/N$, then \eqref{welldef} and \eqref{energybound} hold under the additional condition that $C_f$ is small enough.
\end{lem}

\begin{proof} In order to prove that a solution $(u_k, \lambda_k, m_k)$ of \eqref{mkdef} exists, one looks for fixed points of the map $\mathscr{F} = \mathscr{F}_k : \mu \mapsto m$, defined by $\mu \mapsto (v, \lambda) \mapsto m$, where $(v, \lambda)$ is a solution of
\begin{equation}\label{FHJB}
- \Delta v + H(\nabla v) + \lambda = V(x) - f(\mu \star \psi_k), \quad \text{in $ {\mathbb{T}^N} $},
\end{equation}
and $m$ is the invariant distribution solving
\begin{equation}\label{FKolmo}
- \Delta m -{\rm div}(\nabla H(\nabla v) \, m) = 0 , \quad \text{in $ {\mathbb{T}^N} $}, \quad \int_\Tn m \, dx = 1, \, m > 0.
\end{equation}

Let
\[
\mathcal{K}_\xi := \left\{ m \in W^{1,p}( {\mathbb{T}^N} ) : \int_\Tn m \, dx = 1, \, \int_\Tn m^{\alpha + 1} \, dx \le \xi, \, m \ge 0 \right\},
\]
for $\xi > 0$ ($p > N$ is chosen). The fact that $\mathscr{F}$ is well-defined, continuous and compact on $C( {\mathbb{T}^N} ) \supset \mathcal{K}_\xi$ is standard (see, for example, \cite{MR3333058}). Moreover, one has the following

\begin{lem} If $\alpha < \gamma'/N$, then there exists $\xi > 0$ such that $\mathscr{F}$ maps $\mathcal{K}_\xi$ into itself. Otherwise, if $\alpha \ge \gamma'/N$, the existence of $\xi$ such that $\mathscr{F}$ maps $\mathcal{K}_\xi$ into itself holds under the additional condition that $C_f$ is small enough.
\end{lem}

\begin{proof} Let $\mu \in \mathcal{K}_\xi$, and $v, \lambda, m$ be defined above. Firstly, $\lambda$ is bounded from above, uniformly with respect to $\mu$ and $k$. Indeed, integrating the HJB equation \eqref{FHJB} on $ {\mathbb{T}^N} $,
\[
-C_H + \lambda \le \int_\Tn H(\nabla v) \, dx + \lambda = \int_\Tn V(x) \, dx - \int_\Tn f(\mu \star \psi_k(x)) \, dx \le C_V,
\]
by \eqref{Hass} and \eqref{Vass1}.

In order to prove that $\int m^{\alpha + 1} \, dx \le \xi$, one starts by multiplying \eqref{FHJB} by $m$, and \eqref{FKolmo} by $v$; integrating by parts leads to
\[
\int_\Tn (\nabla H(\nabla v) \cdot \nabla v -H(\nabla v) ) m \, dx + \int_\Tn V \, m \, dx = \lambda + \int_\Tn f(\mu \star \psi_k) m \, dx.
\]
In view of \eqref{Hass} and \eqref{fass}, it holds true that
\begin{multline}\label{eq20}
C_H^{-1} \int_\Tn |\nabla v|^\gamma m \, dx + \int_\Tn V \, m \, dx \le \\ \lambda +  C_H + \int_\Tn f(\mu \star \psi_k) m \, dx \le C_1 + C_f \|(\mu \star \psi_k)^\alpha m\|_{L^1},
\end{multline}
hence by Holder inequality and standard properties of the convolution
\begin{equation}\label{eq21}
 \int_\Tn |\nabla v|^\gamma m \, dx \le C_2 + C_H C_f \|\mu\|^\alpha_{L^{\alpha + 1}} \|m\|_{L^{\alpha+1}}.
\end{equation}

\underline{Case 1}: $\alpha < \gamma'/N$. The inequality \eqref{EI2} applies, and one has
\[
\|m\|^{\delta(\alpha + 1)}_{L^{\alpha +1}} \le C_3(\| \mu \|^\alpha_{L^{\alpha + 1}} \|m\|_{L^{\alpha+1}} + 1),
\]
that is
\begin{equation}\label{eq22}
\|m\|^{\delta'}_{L^{\alpha +1}} \le C_4(\|\mu\|_{L^{\alpha + 1}} + 1),
\end{equation}
where $\delta' = (\delta(\alpha + 1)-1)/\alpha > 1$. This readily implies
\[
\int_\Tn m^{\alpha + 1} \, dx\le C_5(\xi^{1/\delta'} + 1) \le \xi,
\]
provided that $\xi$ is large enough.

\underline{Case 2}: $\alpha\ge\gamma'/N $. Since \eqref{EI2} is not available anymore, one has to exploit \eqref{EI1}, that is
\begin{equation}\label{eq23}
\|m\|^{\delta}_{L^{\alpha +1}} \le C_6(C_f \|\mu\|^\alpha_{L^{\alpha + 1}} \|m\|_{L^{\alpha+1}} + 1),
\end{equation}
hence
\[
\left(\int_\Tn m^{\alpha + 1} \, dx\right)^\delta \, dx \le C_7\left(C_f \xi^\alpha \int_\Tn m^{\alpha + 1}  \, dx + 1\right).
\]
In this case, one may argue that there exists $\xi$ (large, and depending on $C_7, \alpha, \delta$) such that
\[
\int_\Tn m^{\alpha + 1} \, dx \le \xi,
\]
provided that $C_f$ is small enough. In particular, one  might choose $C_f, \xi$ such that $\xi$ is the smallest root of $\xi^\delta = C_7(C_f \xi^{\alpha+1} + 1)$.

Note that, in both cases, $\mathscr{F}(\mathcal{K}_\xi) \subseteq \mathcal{K}_\xi$ for all $k$, because $\xi$ does not depend on $k$.

\end{proof}

{\it End of the proof of Lemma \ref{lemma_welldef}}. Since $\mathscr{F}$ is well-defined, continuous, compact and maps $\mathcal{K}_\xi$ into itself, the existence of a fixed point of $\mathscr{F}$, and therefore a solution of \eqref{mkdef}, follows by Schauder theorem.

As for the bounds \eqref{energybound}, we have already obtained that $\lambda_k$ is uniformly bounded from above. Note also that $m_k \in \mathcal{K}_\xi$, that is $\int {m_k}^{\alpha + 1} \, dx \le \xi$, hence \eqref{eq21} implies that
\[
 \int_\Tn |\nabla u_k|^\gamma m_k \, dx \le C_2 + C_H C_f \|m_k\|^{\alpha+1}_{L^{\alpha + 1}} \le C_2 + C_H C_f \xi .
\]
It remains to bound from below $\lambda_k$; one may read \eqref{eq20} as
\[
- \lambda_k \le  C_H + C_f \|(m_{k} \star \psi_k)^\alpha m_k\|_{L^1} \le C_H + C_f \|m_{k}\|^\alpha_{L^{\alpha + 1}} \|m_k\|_{L^{\alpha+1}} \le C_H + C_f \xi,
\]
which proves the assertion.
\end{proof}

The aim is now to pass to the limit as $k \to \infty$, and prove that $(u_k, \lambda_k, m_k)$ converges to a solution of \eqref{MFG}.

\begin{lem}\label{lem_infty} If $\alpha < \gamma'/N$, there exists $C > 0$ such that
\begin{equation}\label{inftybound}
\|m_k\|_{L^\infty} \le C
\end{equation}
for all $k \ge 1$. Otherwise, if $\alpha \ge \gamma'/N$, then \eqref{inftybound} holds under the additional condition that $C_f$ is small enough.
\end{lem}

\begin{proof} By contradiction, let $M_k > 0, x_k \in  {\mathbb{T}^N} $ be such that
\[
0 < M_k := m_k(x_k) = \max_{ {\mathbb{T}^N} } m_k \to \infty, \quad \text{as $k \to \infty$}.
\]
Let us define the following blow-up sequences
\begin{equation}\label{blowupdef}
v_k(x) := a_k^{\gamma'-2} u(x_k + a_k x), \quad \mu_k(x) := \frac{1}{M_k} m_k(x_k + a_k x), \quad a_k = M_k^{-\alpha/\gamma'},
\end{equation}
for all $x \in  {\mathbb{R}^N} $. Then, $v_k, \Lambda_k, \mu_k$ solve
\begin{equation}\label{MFGn}
\begin{cases}
- \Delta v_k(x) + H_k(\nabla v_k(x)) +\Lambda_k = W_k(x) - F_k(\mu_{k} \star \hat{\psi}_k(x)))  \\
- \Delta \mu_k(x) -{\rm div}(\nabla H_k(\nabla v_k(x)) \, \mu_k(x)) = 0  & \text{in $\mathbb{T}_k^N$},
\end{cases}
\end{equation}
where $\mathbb{T}_k^N = \{x \in  {\mathbb{R}^N}  : x_k + a_k x \in  {\mathbb{T}^N}  \}$ and
\begin{equation}\label{blowup2}
\begin{split}
\bullet \quad & H_k(p) = a_k^{\gamma'}H(a_k^{1-\gamma'}p), \\
\bullet \quad & \Lambda_k = a_k^{\gamma'} \lambda_k, \\
\bullet \quad & W_k(x) = a_k^{\gamma'}V(x_k + a_k x), \\
\bullet \quad & F_k(\mu) = a_k^{\gamma'}f(M_k \mu),
\end{split}
\end{equation}
and $\hat{\psi}_k(x) = a^N_k \psi_k(a_k x)$, and hence it is a radial mollifier. Note that \[a_k \to 0,\] so $H_k$ satisfies \eqref{Hass}, where $C_H$, $\gamma$ are the same as for $H$, and $\Lambda_k \to 0$ by \eqref{energybound}. As for $W_k$, one has that $W_k \to 0$ uniformly on $\mathbb{T}_k^N$, in view of \eqref{Vass1}. Moreover $\mu_{k} \le 1$ on $\mathbb{T}_k^N$, so $\mu_{k} \star \hat{\psi}_k(x) \le 1$, and
\[
0 \le F_k(\mu_{k} \star \hat{\psi}_k(x))) \le C_f a_k^{\gamma'} (M_k^\alpha + 1) \le 2 C_f
\]
for all $k$, by \eqref{fass}. The couple $(v_k, \Lambda_k)$ solves the HJB equation in \eqref{MFGn}, hence the a-priori estimates of Proposition \ref{hjb_regularity} apply, namely $\|\nabla u_k\|_{L^q(B_2)} \le C_q$, for all $q > 1$. On the other hand, $\mu_k$ is a solution of the Kolmogorov equation in \eqref{MFGn}, and it is uniformly bounded with respect to $k$, so Proposition \ref{ell_regularity} guarantees that $\|\mu_k\|_{W^{1,p}(B_1)} \le C_1$, for some $p > N$ (by choosing $q$ large enough). By standard Sobolev embeddings one may conclude that $\|\mu_k\|_{C^{0,\theta}(B_1)} \le C_2$ for some $\theta > 0$, and finally that
\[
\mu_k(x) \ge C_3 > 0 \quad \text{on $B_r$}
\]
for some positive $r, C_3$ not depending on $k$, as $\mu_k(0) = 1$. Therefore,
\begin{equation}\label{belowLalpha}
\int_{B_r} \mu^{\alpha + 1}_k \, dx \ge C_4 > 0.
\end{equation}

On the other hand, recalling \eqref{energybound} (the assumptions of Lemma \ref{lemma_welldef} are satisfied),
\begin{multline*}
\int_{\mathbb{T}_k^N} \mu_k^{\alpha +1}(x) \, dx = \frac{1}{M_k^{\alpha+1}} \int_{\mathbb{T}_k^N} m_k^{\alpha +1}(x_k + a_k x) \, dx = \frac{1}{a_k^N M_k^{\alpha+1}} \int_\Tn m_k^{\alpha +1}(x) \, dx\\ \le \frac{C_5}{M_k^{\alpha+1 - \alpha N/\gamma'}} \rightarrow 0 \quad \text{as $k \rightarrow \infty$},
\end{multline*}
because $M_k \rightarrow \infty$, and $\alpha+1 - \alpha N/\gamma' > 0$ if and only if \eqref{critical_alpha} holds, but this contradicts \eqref{belowLalpha}.

\end{proof}

{\it End of the proof of Theorem \ref{thm_existence}.} Once the crucial estimates \eqref{energybound} and \eqref{inftybound} are established, it is sufficient to pass to the limit as $k \to \infty$. Note that uniform $L^\infty$ bounds on $m_k$ imply uniform $W^{1, p}$ bounds on $u_k$ (by Proposition \ref{hjb_regularity}), that in turn provide $W^{1, p}$ and $C^{0, \alpha}$ bounds for $m_k$ (apply Proposition \ref{ell_regularity} and Sobolev embeddings). By Schauder regularity, $u_k$ is bounded in $C^{2,\alpha}( {\mathbb{T}^N} )$, so, up to subsequences,
\[
u_k \to u \quad \text{in $C^2( {\mathbb{T}^N} )$}, \quad m_k \rightharpoonup m \quad \text{in $W^{1,p}( {\mathbb{T}^N} )$}, \quad \lambda_k \to \lambda,
\]
and by passing to the limit in \eqref{mkdef}, one has that $(u, \lambda, m)$ solves \eqref{MFG}.

\end{proof}

\begin{rem}\label{rem:var} In order to better understand the features of system \eqref{MFG}, it can be useful to consider its \emph{variational} formulation (see \cite{LasryLions}), in the particular case of $H,f$ satisfying \eqref{Hf_partic} (we also choose $V \equiv 0$ for simplicity): solutions of \eqref{MFG} are associated, at least formally, to critical points of the functional
\[
\mathcal{E}(A, m) = \frac{1}{\gamma'} \int_\Tn |A|^{\gamma'} m - \frac{C_f}{\beta}\int_\Tn m^{\beta},
\]
where $\beta = \alpha + 1$, subject to the constraint that the vector field $A :  {\mathbb{T}^N}  \to  {\mathbb{R}^N} $ and the distribution $m$ are coupled via the Kolmogorov equation
\begin{equation}
- \Delta m + {\rm div}(A \, m) = 0, \quad \int_\Tn m \, dx = 1, \, \quad m > 0.
\end{equation}
The functional $\mathcal{E}$ can be regarded as the \emph{energy} of the system; it is convex in the defocusing case (where $-m^\beta$ is replaced by $m^\beta$), but it is not convex when the coupling is focusing. One may ask whether or not $\mathcal{E}$ is at least bounded from below (or above), if $A,m$ are suitably chosen. At this level, the key insight comes from Proposition \ref{prop_energy}, which states that
\begin{equation}\label{SI_vs_KIN}
\left(\int_\Tn m^\beta  \, dx\right)^\delta \le C\left(\int_\Tn |A|^{\gamma'} m  \, dx  + 1\right)
\end{equation}
for some $C > 0$, $\delta > 1$, at least if $\beta < 1 + \gamma'/N$, that is $\alpha < \gamma'/N$. With this inequality in mind, that deeply relies on the Gagliardo-Nirenberg inequality and $L^1$-constraint of $m$, one may argue that $\mathcal{E}$ is bounded from below among $A,m$ satisfying $\int |A|^{\gamma'} m < \infty$, and direct minimization of $\mathcal{E}$ makes sense. In other words, if the growth of $f$ at infinity is sufficiently mild, the ``kinetic'' part of $\mathcal{E}$, represented by $\int_\Tn |A|^{\gamma'} m$, is stronger than the ``self-interaction'' term $\int m^\beta$.

Proposition \ref{prop_energy} states that while \eqref{SI_vs_KIN} is not available anymore if $\beta \ge 1 + \gamma'/N$, boundedness of $\int |A|^{\gamma'} m$ still guarantees compactness of $m$ in $L^\beta( {\mathbb{T}^N} )$ if $\beta < 1 + \gamma'/(N-\gamma')$, that is when $\alpha < {\gamma'}/({N-\gamma'})$ (see Remark \ref{rem_energy}). Hence, even if direct minimization of $\mathcal{E}$ might not be possible, the problem should posses enough compactness, and a critical point of $\mathcal{E}$ might exist.

All these considerations are inspired by some classical results within the theory of \emph{focusing} nonlinear Schr\"odinger equations (NLS). The link between the MFG system \eqref{MFG} and NLS equations can be made precise in the quadratic case $\gamma = \gamma' = 2$, by the observation that if $H$ satisfies \eqref{Hf_partic}, then $\varphi^2 := m = e^{-u} / \int e^{-u}$ trivializes the Kolmogorov equation in \eqref{MFG}, and \eqref{MFG} reduces to the following Hartree equation
\[
-2 \Delta \varphi = \lambda \varphi + C_f \varphi^{2\alpha + 1}, \quad \int_\Tn \varphi^2\, dx = 1, \, \quad \varphi > 0,
\]
which is associated to the functional
\[
\widetilde{\mathcal{E}}(\varphi) = \int_\Tn |\nabla \varphi|^2 \, dx - \frac{C_f}{2\beta} \int_\Tn \varphi^{2 \beta} \, dx, \quad \text{subject to $\int_\Tn \varphi^2 = 1$}.
\]
This minimization problem is well-understood in the so-called $L^2$-subcritical regime, namely when $2 \beta < 2 + 4/N$: in this case, $\widetilde{\mathcal{E}}(\varphi)$ is bounded from below in view of the Gagliardo-Nirenberg inequality and the $L^2$ constraint, and a minimizer can be found via the direct method of calculus of variations (see, for example, \cite{CazLions, Caz} for a description in $ {\mathbb{R}^N} $). Note that $2 \beta < 2 + 4/N$ is equivalent to $\alpha < 2/N$, and $2/N$ is precisely the first exponent $\alpha_1 = \gamma'/N$ that appears in our analysis: we may regard $\alpha_1$ as the \emph{mass-critical} exponent.

In the $L^2$-supercritical regime, $\widetilde{\mathcal{E}}(\varphi)$ is not bounded from below; if $2 \beta < 2N/(N-2)$, one expects the existence of a critical point under the additional condition that the $L^2$ constraint is small, or equivalently that $C_f$ is small (see \cite{NTV}, where the setting of a bounded domain $\Omega$ and homogeneous Dirichlet boundary data is considered). The condition $2 \beta < 2N/(N-2)$ can be read as $\alpha < 2/(N-2)$, and $2/(N-2)$ is $\alpha_2 = \gamma'/(N-\gamma')$ in the quadratic case $\gamma' = 2$; in the NLS jargon, $\alpha_2$ is the \emph{energy-critical} exponent.

If $2\beta \ge 2N/(N-2)$, the lack of Sobolev embeddings and compactness is a serious issue in variational methods and the classical Pohozaev identity implies non-existence of solutions in many situations.

Back to the general MFG system \eqref{MFG}, we prove that it exhibits the same behaviour as NLS: the two critical values $\alpha_1$ and $\alpha_2$ are such that if $\alpha \in (0, \alpha_1)$, then \eqref{MFG} has a solution, if $\alpha \in [\alpha_1, \alpha_2)$ a solution exists if the additional condition that $C_f$ be small is imposed, and if $\alpha \in [\alpha_2, \infty)$ solutions may not exist. In view of this analogy with focusing NLS, we have decided to call focusing the MFG systems with decreasing (and unbounded) coupling.
\end{rem}

\section{A Pohozaev identity and non-existence of solutions}\label{s:nonex}

This section in devoted to the proof of non-existence of solutions in the ``supercritical'' regime $\alpha \ge \gamma'/(N-\gamma')$. We start with an integral identity, which is produced by implementing in the MFG setting a celebrated idea of Pohozaev (see \cite{Pohoz}).

\begin{prop}\label{pohozaev} Let $\Omega \subset \mathbb{R}^N$ be a bounded and smooth domain, and $g, G \in C^1(\overline{\Omega} \times \mathbb{R})$ be such that
\[
\partial_m G(x,m) = g(x,m) \quad \forall x,m.
\]
Suppose that $(u, \lambda, m) \in C^2(\overline{\Omega})\times \mathbb{R} \times W^{1,1}(\Omega)$ is a solution of
\begin{equation}\label{MFGg}
\begin{cases}
- \Delta u(x) + \frac{1}{\gamma} {|\nabla u(x)|^\gamma} = g(x,m(x))  \\
- \Delta m(x) -{\rm div}(|\nabla u(x)|^{\gamma-2}\nabla u(x) \, m(x)) = 0  & \text{in $\Omega$}.  \\
\end{cases}
\end{equation}
Then, the following equality holds
\begin{equation}
N \int_\Omega G(x,m) \, dx+ \int_\Omega \nabla_x G \cdot x \, dx + \left(1- \frac{N}{\gamma}\right) \int_\Omega |\nabla u|^\gamma m + (2-N) \int_\Omega \nabla u \cdot \nabla m \, dx = I_{\partial \Omega},
\end{equation}
where
\begin{multline*}
I_{\partial \Omega} = \int_{\partial \Omega} \left( G - \nabla u \cdot \nabla m - \frac{1}{\gamma}|\nabla u|^\gamma m \right) \,  x \cdot \nu \, d \sigma \\
+ \int_{\partial \Omega}  (\nabla u \cdot \nu)(\nabla m \cdot x) + (\nabla m \cdot \nu)(\nabla u \cdot x) + |\nabla u|^{\gamma-2}(\nabla u \cdot \nu)( \nabla u \cdot x) m \, d \sigma
\end{multline*}
\end{prop}

\begin{proof} As we already mentioned in the introduction, if $1 < \gamma < 2$ the Kolmogorov equation is solved in the weak sense (while $m$ is twice differentiable everywhere if $\gamma \ge 2$, and all the following computations are justified). In this case, it is sufficient to approximate the problem by replacing $H(p) = |p|^\gamma/\gamma$ by $H_\epsilon(p) = (\epsilon + |p|^2)^{\gamma/2}/\gamma$: in this way, $m = m_\epsilon$ is a-posteriori a classical solution of the Kolmogorov equation, and the statement of the theorem follows by letting $\epsilon \to 0$.

The following equality is obtained by integrating by parts and exchanging the order of derivation\footnote{For the sake of brevity, the Einstein summation convention on repeated indices is used here.}:
\begin{multline}\label{eq1}
\int_\Omega \nabla u \cdot \nabla (\nabla m \cdot x) \, dx = \int_\Omega u_{x_i} m_{x_i x_j} x_j \, dx +  \int_\Omega \nabla u \cdot \nabla m \, dx = \\
- \int_\Omega m_{x_i} u_{x_i x_j} x_j \, dx +  (1-N) \int_\Omega \nabla u \cdot \nabla m \, dx + \int_{\partial \Omega} \nabla u \cdot \nabla m \,  x \cdot \nu d \sigma = \\
- \int_\Omega \nabla m \cdot \nabla (\nabla u \cdot x) \, dx +  (2-N) \int_\Omega \nabla u \cdot \nabla m \, dx + \int_{\partial \Omega} \nabla u \cdot \nabla m \,  x \cdot \nu d \sigma.
\end{multline}
One sees that
\begin{equation}\label{eq2}
\frac{1}{\gamma}\nabla(|\nabla u|^\gamma)\cdot x = |\nabla u|^{\gamma-2} u_{x_i} u_{x_i x_j} x_j = |\nabla u|^{\gamma-2} \nabla u \cdot \nabla(\nabla u \cdot x) - |\nabla u|^\gamma,
\end{equation}
hence
\begin{multline}\label{eq3}
- \frac{1}{\gamma} \int_\Omega \nabla(|\nabla u|^\gamma) \cdot x \, m \, dx = \int_\Omega \nabla m \cdot \nabla (\nabla u \cdot x) \, dx + \int_\Omega |\nabla u|^\gamma m \, dx \\
-\int_{\partial \Omega} (\nabla m \cdot \nu)(\nabla u \cdot x) \, d \sigma - \int_{\partial \Omega} |\nabla u|^{\gamma-2}(\nabla u \cdot \nu)( \nabla u \cdot x) m \, d \sigma,
\end{multline}
by exploiting  the second equation of \eqref{MFGg} multiplied by $\nabla u \cdot x$. Therefore, by multiplying \eqref{MFGg} by $\nabla m \cdot x$ and integrating by parts we obtain
\begin{multline*}
\int_\Omega g \, \nabla m \cdot x \, dx = - \int_\Omega \Delta u (\nabla m \cdot x) \, dx +\frac{1}{\gamma} \int_\Omega  |\nabla u|^\gamma (\nabla m \cdot x) \, dx =  -\int_{\partial \Omega} (\nabla u \cdot \nu)(\nabla m \cdot x) \, d \sigma + \\
\int_\Omega \nabla u \cdot \nabla (\nabla m \cdot x) \, dx - \frac{1}{\gamma} \int_\Omega {\rm div}(|\nabla u|^\gamma x) m \, dx + \frac{1}{\gamma} \int_{\partial \Omega} |\nabla u|^\gamma m \,  x \cdot \nu \, d \sigma, \\
\end{multline*}
that is, plugging in \eqref{eq1} and \eqref{eq3},
\begin{multline}\label{eq4}
\int_\Omega g \, \nabla m \cdot x \, dx =
- \int_\Omega \nabla m \cdot \nabla (\nabla u \cdot x) \, dx - \frac{N}{\gamma} \int_\Omega |\nabla u|^\gamma m \, dx  - \frac{1}{\gamma} \int_\Omega \nabla(|\nabla u|^\gamma) \cdot x \, m \, dx  \\ + (2-N) \int_\Omega \nabla u \cdot \nabla m \, dx + \int_{\partial \Omega} \left( \nabla u \cdot \nabla m + \frac{1}{\gamma}|\nabla u|^\gamma m\right) \,  x \cdot \nu  - (\nabla u \cdot \nu)(\nabla m \cdot x) \, d \sigma, = \\
\left(1 - \frac{N}{\gamma}\right) \int_\Omega |\nabla u|^\gamma m \, dx  + (2-N) \int_\Omega \nabla u \cdot \nabla m \, dx +
\int_{\partial \Omega} \left( \nabla u \cdot \nabla m + \frac{1}{\gamma}|\nabla u|^\gamma m\right) \,  x \cdot \nu\, d \sigma \\ - \int_{\partial \Omega}  (\nabla u \cdot \nu)(\nabla m \cdot x) + (\nabla m \cdot \nu)(\nabla u \cdot x) + |\nabla u|^{\gamma-2}(\nabla u \cdot \nu)( \nabla u \cdot x) m \, d \sigma.
\end{multline}
Finally, integrating again by parts,
\begin{equation}
-N \int_\Omega G \, dx = - \int_\Omega G\,  {\rm div}(x) \, dx =  \int_\Omega \nabla_x G \cdot x \, dx +  \int_\Omega g \, \nabla m \cdot x \, dx - \int_{\partial \Omega} G \,  x \cdot \nu \, d \sigma
\end{equation}
which gives the stated equality in view of \eqref{eq4}.
\end{proof}

The following basic lemma will be useful to control the behavior of $u,m,\nabla u, \nabla m$ at infinity. We provide the proof for the convenience of the reader (following the lines of \cite{BerestyckiLions}, where the Pohozaev identity is used in $ {\mathbb{R}^N} $ in the setting of NLS equations).

\begin{lem}\label{decay} Let $h \in L^1( {\mathbb{R}^N} )$. Then, there exists a sequence $R_n \to \infty$ such that
\[
R_n \int_{\partial B_{R_n}} |h(x)| \, dx \rightarrow 0 \quad \text{as $n \to \infty$}.
\]
\end{lem}

\begin{proof} By the co-area formula, it holds true that
\begin{equation}\label{eq30}
\int_{\Rset^N} |h(x)|\,dx = \int_0^\infty \int_{\partial B_{R}} |h(x)| \, dx \, dR < \infty.
\end{equation}
If, by contradiction,
\[
\liminf_{R \rightarrow \infty} R \int_{\partial B_{R}} |h(x)| \, dx = \alpha > 0,
\]
then
\[
R \mapsto \int_{\partial B_{R}} |h(x)| \, dx
\]
would not be in $L^1(0, +\infty)$, that is not compatible with \eqref{eq30}.
\end{proof}

While the negativity of the ergodic constant $\lambda$ is a direct consequence of the comparison principle when the state space $\Omega$ is the flat torus, if the problem is set on $ {\mathbb{R}^N} $ the following lemma is required.

\begin{lem}\label{lambdanegative}
Suppose that $(u, \lambda) \in C^2( {\mathbb{R}^N} ) \times \mathbb{R}$ is a solution of the HJB equation in \eqref{MFG}, where $H$ is of the form \eqref{Hf_partic}, $V \equiv 0$, and $u$ satisfies \eqref{uinfty}. Then,
\[
\lambda \le 0.
\]
\end{lem}

\begin{proof} Let $\mu_\epsilon(x) := \epsilon^{N/2} (2 \pi)^{-N/2} e^{-\epsilon|x|^2/2}$ for all $x \in  {\mathbb{R}^N} $, $\epsilon > 0$. Note that $\int_{\Rset^N} \mu_\epsilon = 1$ for all $\epsilon$.

Since $|p|^\gamma/\gamma$ is the Legendre transform of $|p|^{\gamma'}/\gamma'$, one observes that
\[
- \Delta u(x) + \nabla u(x) \cdot (\epsilon x) - \frac{1}{\gamma'}|\epsilon x|^{\gamma'} + \lambda \le - \Delta u(x) + \sup_{\alpha \in  {\mathbb{R}^N} }\left\{\nabla u(x) \cdot \alpha - \frac{1}{\gamma'}|\alpha|^{\gamma'} \right\} + \lambda = -f(m(x)),
\]
by choosing $\alpha = \alpha(x) = \epsilon x$. Multiplying this equality by $\mu_\epsilon$ on $B_R$, $R > 0$ and integrating by parts gives
\begin{multline*}
\int_{B_R} \nabla u \cdot \nabla \mu_\epsilon \, dx - \int_{\partial B_R} \mu_\epsilon  \nabla u \cdot \nu \, dx + \int_{B_R} \nabla u \cdot (\epsilon x) \mu_\epsilon \, dx + \lambda \int_{B_R} \mu_\epsilon \, dx \le\\ \frac{1}{\gamma'} \int_{B_R} |\epsilon x|^{\gamma'} \mu_\epsilon \, dx - \int_{B_R} f(m(x)) \mu_\epsilon \, dx.
\end{multline*}
Recall that $f \ge 0$ and $\nabla \mu_\epsilon = -\epsilon x \mu_\epsilon$, so one obtains
\begin{equation}\label{eq31}
 \lambda \int_{B_R} \mu_\epsilon \, dx \le \frac{1}{\gamma'} \int_{B_R} |\epsilon x|^{\gamma'} \mu_\epsilon \, dx + \int_{\partial B_R} \mu_\epsilon  \nabla u \cdot \nu \, dx.
\end{equation}
The first integral of the right-hand side of \eqref{eq31} can be made arbitrarily small as $\epsilon \to 0$, that is $\int_{B_R} |\epsilon x|^{\gamma'} \mu_\epsilon  \le C \epsilon^{\gamma'/2}$, where $C > 0$ does not depend on $\epsilon$. Moreover, for any $\epsilon > 0$ fixed,
\[
\left| \int_{\partial B_R} \mu_\epsilon  \nabla u \cdot \nu \, dx \right| \le C \epsilon^{N/2} |\partial B_R| \| \nabla u \|_{L^\infty(\partial B_R)} e^{-\epsilon|R|^2/2} \to 0 \quad \text{as $R \to \infty$},
\]
because, $|\partial B_R|, \| \nabla u \|_{L^\infty(\partial B_R)} $ grow polynomially in $R$ as $R \to \infty$. Therefore, letting $R \to \infty$ in \eqref{eq31} provides
\[
\lambda \le C \epsilon^{\gamma'/2},
\]
and the stated assertion follows by letting $\epsilon \to 0$.
\end{proof}

We are now ready to prove the non-existence theorem.

\begin{proof}[Proof of Theorem \ref{thm_nonex}]
Suppose, by contradiction, that $(u, \lambda, m) \in C^2( {\mathbb{R}^N} ) \times \mathbb{R} \times W^{1,1}( {\mathbb{R}^N} )$ is a solution of \eqref{MFG} satisfying
\eqref{uinfty}-\eqref{finiteness}. Let us define $g(x,m) = - \lambda- f(m), G(x,m) = - \lambda m - F(m)$; of course, $\partial_m G(x,m) = g(x,m)$ for all $x,m$. We argue that, by Proposition \ref{pohozaev}, it holds true that
\begin{equation}\label{eq43}
N \int_{\Rset^N} G(x,m) \, dx + \left(1- \frac{N}{\gamma}\right) \int_{\Rset^N} |\nabla u|^\gamma m + (2-N) \int_{\Rset^N} \nabla u \cdot \nabla m \, dx = 0.
\end{equation}
In particular, the proposition applies if we choose $\Omega = B_R$, $R > 0$. In order to obtain \eqref{eq43}, it suffices to observe that
\[
|I_{\partial B_{R_n}}| \le R_n \int_{\partial {B_{R_n}}} ( |G| + 3 |\nabla u| | \nabla m| + 2|\nabla u|^\gamma m )  \, d \sigma \to 0,
\]
for some sequence $R_n \to \infty$, because $G, |\nabla u| | \nabla m|, |\nabla u|^\gamma m \in L^1( {\mathbb{R}^N} )$ (use Lemma \ref{decay}).

It also holds true that
\begin{align}
\int_{\Rset^N} \nabla u \cdot \nabla m \, dx & = - \int_{\Rset^N} |\nabla u|^{\gamma} m \, dx \label{eq41} \\
\int_{\Rset^N} \nabla u \cdot \nabla m \, dx & = \int_{\Rset^N} g(x,m(x))m(x) \, dx - \frac{1}{\gamma} \int_{\Rset^N} |\nabla u|^{\gamma} m \label{eq42} \, dx.
\end{align}
Indeed, set
\begin{equation}\label{omegas}
\text{$\Omega_s := \{x \in  {\mathbb{R}^N}  : u(x) \le s\}\quad$ and $\quad v_s(x) := u(x) - s$ for all $s > 0, x \in  {\mathbb{R}^N} $.}
\end{equation}
Without loss of generality, we may suppose that $u(0) = 0$. In this situation, every $\Omega_s$ is non-empty and bounded, and $\cup_s \Omega_s =  {\mathbb{R}^N} $, by the fact that $u \to \infty$ as $|x| \to \infty$. If one multiplies the Kolmogorov equation in \eqref{MFG} by $v_s$, an integration by parts yields
\[
\int_{\Omega_s} \nabla v_s \cdot \nabla m \, dx = - \int_{\Omega_s} |\nabla u|^{\gamma-2} \nabla u \cdot \nabla v_s m \, dx.
\]
Note that $\nabla u = \nabla v_s$ for all $s$, so \eqref{eq41} follows by letting $s \to \infty$. As for \eqref{eq42}, it suffices to multiply the HJB equation in \eqref{MFG} by $m$ and integrate by parts on a generic ball $B_R$, that is
\[
\int_{B_R} \nabla u \cdot \nabla m\, dx - \int_{\partial B_R} m \nabla u \cdot \nu \, dx + \frac{1}{\gamma}\int_{B_R} |\nabla u|^\gamma \, dx  = \int_{B_R} g(m) m \, dx.
\]
A straightforward application of the Holder inequality leads to
\begin{equation}\label{eq40}
\int_{\Rset^N} |\nabla u| m \, dx \le \left(\int_{\Rset^N} |\nabla u|^\gamma m \, dx \right)^{1/\gamma} \left(\int_{\Rset^N} m \, dx \right)^{1/\gamma'} < \infty,
\end{equation}
so
\[
\int_{\partial B_{R_n}} m \nabla u \cdot \nu \, dx \to 0 \quad \text{as $R_n \to \infty$},
\]
along an appropriate sequence $R_n \to \infty$, in view of \eqref{eq40} and Lemma \ref{decay}, and \eqref{eq42} follows.

Equations \eqref{eq41} and \eqref{eq42} are now plugged into \eqref{eq43} to get
\[
N \int_{\Rset^N} G(m) \, dx - (N- \gamma') \int_{\Rset^N} g(m)m \, dx = 0,
\]
that is
\[
\int_{\Rset^N} [ (N-\gamma') f(m) m - N F(m) ] \, dx = \lambda \gamma' \le 0
\]
by $\int_{\Rset^N} = 1$ and Lemma \ref{lambdanegative}. Therefore, recalling \eqref{fass2}, a contradiction is reached.
\end{proof}

\begin{rem}\label{rem:infinity} We end this section with some remarks about conditions \eqref{uinfty} and \eqref{finiteness}. As for $u \to \infty$ as $x \to \infty$, it is a quite natural ``boundary'' condition for ergodic HJB equations on the whole space. Observe that the optimal control $-\nabla H(\nabla u)$ should give rise to an ergodic process, and this happens heuristically if $-\nabla H(\nabla u) \cdot x < 0$ for $x$ large, that is $\nabla u \cdot x > 0$ when $H$ is the model Hamiltonian \eqref{Hf_partic}. We refer to \cite{CirantErgodic} (and references therein) for more information about ergodic problems on the whole space. The polynomial control at infinity of $\nabla u$ is more technical than substantial, and it is usually true under mild assumptions: for example, if $\|m\|_{W^{1,\infty}( {\mathbb{R}^N} )} < \infty$, one may invoke standard Bernstein estimates to obtain a uniform control of $\nabla u$ on the whole space (see, for example, \cite{lasry1989nonlinear}).

As we have seen in Remark \ref{rem:var}, boundedness of $|\nabla u|^\gamma m$, $m^{\alpha+1}$ in $L^1( {\mathbb{R}^N} )$ is a natural requirement for the well-posedness of \eqref{MFG}. If one just looks at the Kolmogorov equation, integrability of the vector field $-\nabla H(\nabla u)$ with respect to $m$ is recommended to ensure some minimal regularity of $m$ and  uniqueness of the invariant distribution itself (see \cite{Metafune}).

Integrability of $|\nabla u| |\nabla m|$ is another technical requirement; it is a consequence of the other conditions in the quadratic case, and we expect the same also in more general situations: the decay at infinity of $m$ is usually exponential, while the growth of $|\nabla u|$ is polynomial (see \cite{CirantErgodic}).

To conclude, it is not the aim of this work to pursue non-existence results under minimal conditions on $u,m$ at infinity; our focus here is concentration of $m$ caused by criticality phenomena, rather than a careful analysis of the behavior of the problem at infinity.
\end{rem}

\section{Uniqueness in very special cases}\label{s:unique}

The aim of this section is to obtain uniqueness results for the system \eqref{MFG}, in the case
\begin{equation}\label{polyHf}
\Omega =  {\mathbb{R}^N} , \qquad V \equiv 0, \qquad H(p) = \frac{1}{2} |p|^2, \qquad f(m) = m^\alpha, \quad \alpha > 0.
\end{equation}
Even though in what follows we might multiply $H, f$ by some positive constants and obtain analogous results, we stress that the assumption \eqref{polyHf} is still quite rigid and selects a very special class of focusing MFG systems. The quadratic form of $H$ enables us to exploit the standard Hopf-Cole transformation (see \cite{LasryLions}), in the following way.

\begin{lem}\label{hopfcole} Let $(u, \lambda, m)$ be a classical solution of \eqref{MFG}-\eqref{uinfty}, such that
\begin{equation}\label{finite_energy}
\int_{\Rset^N} |\nabla u|^2 m < \infty.
\end{equation}
Then, $\varphi := e^{-u/2}$ satisfies
\begin{equation}\label{semilin}
\begin{cases}
2 \Delta \varphi + \lambda \varphi + \varphi^{2\alpha +1} = 0 & \text{in $ {\mathbb{R}^N} $} \\
\varphi(x) \rightarrow 0 \quad\text{as $x \rightarrow \infty$} \\
\int_ {\mathbb{R}^N}  \varphi^2 \, dx = 1, \, \varphi > 0,
\end{cases}
\end{equation}
and $m = \varphi^2$.
\end{lem}

\begin{proof} By exploiting the HJB equation in \eqref{MFG}, an easy computation shows that $\varphi = e^{-u/2}$ solves
\begin{equation}\label{eq51}
2 \Delta \varphi + \lambda \varphi + m^{\alpha}\varphi = 0 \quad \text{in $ {\mathbb{R}^N} $}.
\end{equation}
Since $u \to +\infty$ as $x \to \infty$, $\varphi$ vanishes at infinity. Note that $m$ and $\mu := e^{-u}$ are both solution of the Kolmogorov equation
\begin{equation}\label{kolmoB}
-\Delta m +{\rm div}(A \, m) = 0 \quad \text{on $ {\mathbb{R}^N} $,}
\end{equation} where $A = - \nabla u$. Applying uniqueness results of probability solutions for \eqref{kolmoB} (see for example \cite{BRS11} and references therein), since $\int_{\Rset^N} |A|^2 m < \infty$, one has $m \equiv \mu = \varphi^2$. Substituting the last equality into \eqref{eq51} concludes the proof.
\end{proof}

\begin{prop} Suppose that $0 < \alpha< 2/(N-2)$ and $\alpha \neq 2/N$. Then, there exists a unique classical solution $(u, \lambda, m)$ of \eqref{MFG} such that
\[
\int_{\Rset^N} |\nabla u|^2 m < \infty, \qquad \text{and} \quad \int_{\Rset^N} x \, m \, dx = 0.
\]
Moreover, $m$ and $u$ are radially symmetric around the origin.
\end{prop}

\begin{proof} Suppose that $(u_i, \lambda_i, m_i)$, $i = 1,2$ are classical solutions of \eqref{MFG}. By Lemma \ref{hopfcole}, $\lambda_i$ and $\varphi_i = e^{-u_i/2} = \sqrt{m_i}$ are classical solutions of the semilinear elliptic equation \eqref{semilin}. Firstly, $\int |\nabla u_i|^2 m_i < \infty$ reads
\[
\int_{\Rset^N} |\nabla \varphi_i|^2 < \infty.
\]
Moreover, $\lambda_i < 0$, because $2 \Delta \varphi + \lambda \varphi + \varphi^{2\alpha +1} = 0$ has no non-trivial solutions in $ {\mathbb{R}^N} $ if $\lambda \ge 0$.

Set $\psi_i(x) = |\lambda_i|^{-1/(2\alpha)} \varphi_i (x/|\lambda_i|^{1/2})$. Then, $\psi_1$ and $\psi_2$ are positive solutions of
\begin{equation}\label{normalized_semilin}
2 \Delta \psi - \psi + \psi^{2\alpha +1} = 0 \quad \text{in $ {\mathbb{R}^N} $},
\end{equation}
vanishing at infinity. Standard results on symmetry of solutions of semilinear equations imply that $\psi_i$ are radially symmetric, i.e. there exist $x_i \in  {\mathbb{R}^N} $, $i = 1,2$ such that $\psi_i(x-x_i)$ are radially symmetric around the origin (see, for example, \cite{LiNi}). Note that $\int x \, \varphi^2_i \, dx = 0$ is required, so $x_1 = x_2 = 0$.

As uniqueness holds for radial solutions of \eqref{normalized_semilin} (see \cite{Kwong}), one has
\[
\psi_1(x) = \psi_2(x) \quad \text{for all $x \in  {\mathbb{R}^N} $}.
\]
Since $\int \varphi_i^2 = 1$, one obtains
\[
|\lambda_1|^{\frac{N\alpha - 2}{2 \alpha}} = \int_{\Rset^N} \psi_1^2 \, dx = \int_{\Rset^N} \psi_2^2 \, dx = |\lambda_2|^{\frac{N\alpha - 2}{2 \alpha}},
\]
that implies $\lambda_1 = \lambda_2$ whenever $\alpha \neq 2/N$, and consequently $\varphi_1 \equiv \varphi_2$. By the equality $\varphi_i = e^{-u_i/2} = \sqrt{m_i}$ one obtains the assertion on uniqueness. As for existence, it follows by standard existence arguments for \eqref{normalized_semilin}.
\end{proof}

\begin{rem} The previous argument uses extensively the special form of $H, f$ and the scaling properties of \eqref{semilin} to reduce the problem of uniqueness of a solution $(\varphi, \lambda)$ to the uniqueness of $\psi$ solving \eqref{normalized_semilin}. Being the equation homogeneous in the $x$-variable, one expects uniqueness ``up-to-translations'', that is, agents have no preferences about the concentration point of $m$ in the state space.

The situation drastically changes if some potential function is added into the problem, namely
\[
V(x) \not\equiv 0.
\]
This case is much more delicate and tricky to treat from the point of view of uniqueness, as it is not possible anymore to remove the unknown $\lambda$ by rescaling. Heuristically, a radially increasing potential $V$ should localize the problem around the origin and boil down the possibility of having multiple ``concentration points''. It is still possible to transform \eqref{MFG} into a semilinear equation (with potential), but uniqueness of a solution $(\varphi, \lambda)$ with $L^2$-constraint is in general an open problem. As far as we know, a complete description of the ground states (positive solutions vanishing as $x \rightarrow \infty$) of
\begin{equation}\label{semilinV}
2 \Delta \varphi + \lambda \varphi - V(x) \varphi + \varphi^{2\alpha +1} = 0 \quad \text{in $ {\mathbb{R}^N} $},
\end{equation}
is available only in space dimension $N=1$, with bounded $V$ and in the $L^2$-subcritical case $\alpha < 2/N =1$ (see \cite{mcleod2003}).

We mention that the uniqueness of a couple $(\varphi, \lambda)$ solving \eqref{semilinV} such that $\int \varphi^2 = 1$ is strictly related to the problem of \emph{orbital stability} of ground states of \eqref{semilinV}, that is the long-time stability of standing waves of the associated nonlinear Schr\"odinger equation.

\end{rem}

\begin{rem} If $H$ is non-quadratic, but of the form $H(p) = |p|^\gamma$, $\gamma > 1$, it is possible to transform \emph{radial} solutions of \eqref{MFG} into solutions of a quasi-linear equation involving the $\Delta_{\gamma'}$ operator (see \cite{MR3377677}). A rescaling argument and uniqueness results for this kind of quasilinear equations (see, for example, \cite{pucci1998uniqueness}) then applies as in the quadratic case, leading to uniqueness of radial finite-energy solutions of the MFG system. However, it is not known in general if any $u,m$ solving \eqref{MFG} with non-quadratic Hamiltonian has radial symmetry.
\end{rem}

\begin{rem} We observe that if condition \eqref{finite_energy} does not hold, one may not expect in general uniqueness of solutions for the Kolmogorov equation on $ {\mathbb{R}^N} $ (see, for example, counterexamples in \cite{BRS11}).
\end{rem}


\section{Introduction}

A new bosonic state with a mass around $125\,\mbox{GeV}$,
which was discovered at the LHC a few years ago, can provide a window into
new physics beyond the Standard Model (SM). The
signal strengths associated with this particle are currently consistent with
the SM Higgs boson. However further exploration of this resonance
can lead to new exciting discoveries. Physics beyond the SM may change
the Higgs decay rates to SM particles and give rise to new decay modes.
Here we consider the decays of the SM-like Higgs boson into a pair of
pseudoscalar states within $U(1)$ extensions of the Minimal Supersymmetric
Standard Model (MSSM). In particular we focus on the $E_6$ inspired
SUSY models which are based on the low--energy SM gauge group together
with an extra $U(1)_{N}$ gauge symmetry defined by:
\begin{equation}
U(1)_N=\frac{1}{4} U(1)_{\chi}+\frac{\sqrt{15}}{4} U(1)_{\psi}\,.
\label{1}
\end{equation}
Gauge $U(1)_{\psi}$\quad and $U(1)_{\chi}$ symmetries can
originate from the breakings $E_6\to$ $SO(10)\times U(1)_{\psi}$,
$SO(10)\to SU(5)\times U(1)_{\chi}$. Different aspects of the phenomenology
of these $E_6$ inspired supersymmetric (SUSY) models have been extensively studied in
\cite{King:2005jy,King:2005my,King:2007uj,King:2008qb,Athron:2009ue,Athron:2009bs,Hall:2010ix,Athron:2011wu,Nevzorov:2012hs,Athron:2012sq,Nevzorov:2013tta,Nevzorov:2013ixa,Athron:2014pua}.

\section{The $U(1)_N$ extensions of the MSSM}

These SUSY models imply that just below the scale $M_X$ the gauge symmetry
in the $E_6$ Grand Unified Theory (GUT) is broken down to
$SU(3)_C\times SU(2)_W\times U(1)_Y\times U(1)_{N}\times Z_{2}^{M}$,
where $Z_{2}^{M}=(-1)^{3(B-L)}$ is a matter parity. To ensure anomaly
cancellation, gauge coupling unification and the appropriate breakdown of
the gauge symmetry at low energies the matter content of the SUSY models
under consideration involves three $27$ representations of the $E_6$,
two $SU(2)_W$ doublets $L_4$ and $\overline{L}_4$ from extra $27'_1$
and $\overline{27'}_1$, two SM singlets $S$ and $\overline{S}$ that carry
non--zero $U(1)_N$ charges and stem from another pair of $27'_2$
and $\overline{27'}_2$ as well as a SM singlet $\phi$ that does not participate
in gauge interactions. Thus these models involve extra matter beyond the
MSSM. In particular, they include three pairs of $SU(2)_W$--doublets
($H^d_{i}$ and $H^u_{i}$) that have the quantum numbers of Higgs doublets,
and three pairs of colour triplets of exotic quarks $\overline{D}_i$ and $D_i$ with
electric charges $+ 1/3$ and $-1/3$ respectively. To suppress flavour changing
neutral currents as well as the most dangerous baryon and lepton number violating
operators one can impose a discrete $\tilde{Z}^{H}_2$ symmetry, under which
all superfields except one pair of $H^{d}_{i}$ and $H^{u}_{i}$ (say
$H_d\equiv H^{d}_{3}$ and $H_u\equiv H^{u}_{3}$), $L_4$, $\overline{L}_4$,
$S$, $\overline{S}$ and $\phi$ are odd.

The conservation of $Z_{2}^{M}$ and
$\tilde{Z}^{H}_2$ symmetries implies that these models contain at least two
states which are absolutely stable and can contribute to the dark matter density.
One of these states is a lightest SUSY particle (LSP) whereas another one is
the lightest ordinary neutralino. Using the method proposed in \cite{Hesselbach:2007te}
it was argued that there is a theoretical upper bound on the mass of the LSP
\cite{Hall:2010ix}. In the simplest phenomenologically viable scenarios the LSP
has a mass around $1\,\mbox{eV}$ or even smaller forming hot dark matter
in the Universe. The presence of such very light neutral fermions in the particle spectrum
may have interesting implications for neutrino physics (see, for example \cite{Frere:1996gb}).
In these scenarios the lightest ordinary neutralino can account for all or some of the observed
dark matter density.

\section{Non-Standard Higgs Decays}

The Higgs sector of the SUSY models under consideration contains two Higgs
doublets $H_d$ and $H_u$ as well as $S$, $\overline{S}$ and $\phi$.
The scalar components of the superfields $S$ and $\overline{S}$ acquire
large vacuum expectation values (VEVs) that break the $U(1)_N$ gauge symmetry inducing
the masses of exotic particles and the $Z'$ boson. The interaction of $S$, $\overline{S}$
and $\phi$ is determined by the following terms in the superpotential that can be written as
\begin{equation}
W_{S}= \sigma \phi S \overline{S} + \frac{\kappa}{3}\phi^3+\frac{\mu}{2}\phi^2+\Lambda\phi\,.
\label{2}
\end{equation}
When~ the~ couplings~ $\kappa$,~ $\mu$ and $\Lambda$ are rather small these models possess~
an~ approximate global $U(1)$ symmetry. This symmetry is spontaneously broken by the
VEVs of $S$, $\overline{S}$ and $\phi$ leading to the presence of a light pseudoscalar
state in the particle spectrum. Our analysis indicates that the couplings of this state to the
SM particles are always small. Therefore even if this pseudoscalar is substantially lighter
than $100\,\mbox{GeV}$ it could escape detection at former and present collider experiments.
Moreover this state can be so light that it gives rise to the decays of the SM-like Higgs boson
into a pair of these pseudoscalar states. The branching ratio of such decays depends
rather strongly on the values of the couplings that explicitly violate the global $U(1)$ symmetry.

To simplify our analysis we set $\mu=0$ as well as $\Lambda=0$ and examine the dependence
of the branching ratio of the exotic Higgs decays on $\kappa$. For $\kappa\sim 0.001$ the pseudoscalar
Higgs boson with a mass of $40-60\,\mbox{GeV}$ can be obtained without fine-tuning but
the branching ratio of the SM-like Higgs decays into a pair of such particles is smaller
than $10^{-4}$ \cite{Athron:2014pua}. Thus it will be rather difficult to observe such decays at the LHC.
If $\kappa > 0.01$ a fine tuning of at least $1\%$ is required to get the lightest
CP-odd Higgs state with mass of $40-60\,\mbox{GeV}$. However the branching ratio of the
corresponding exotic Higgs decays can be larger than $1\%$ in this case \cite{Athron:2014pua}.
After being produced from such decays the lightest pseudoscalars decay into a pair of
$b$-quarks or $\tau$-leptons resulting in four fermion final states.

\section*{Acknowledgments}

This work was supported by the University of Adelaide and the
Australian Research Council through the ARC Center of Excellence in
Particle Physics at the Terascale.


\section{Introduction}

\IEEEPARstart{T}{he} problem of compressed sensing and sparse reconstruction \cite{candes2008introduction} \cite{donoho2006compressed} has drawn tremendous interest over the past decade due to its potential applications in sub-Nyquist sampling, imaging, biomedical signal processing, astronomy and geophysics. Consider the problem of reconstructing an $N$ dimensional sparse signal vector $\bm{x}$ from its noisy $M$ dimensional compressed measurement vector $\bm{y}$:
\begin{equation}\label{eq1}
\bm{y}=\bm{A}\bm{x} + \bm{z}
\end{equation}
Here $\bm{A}$ is the $M \times N$ dimensional sensing matrix with $ M \ll N$ and $\bm{z}$ is the noise vector. We assume $\bm{z} \sim \mathcal{N}(0,\bm{I}_{M \times M}) $. The signal $\bm{x}$ is said to be $K$--sparse (Usually $K \ll N$) if $ ||\bm{x}||_0 \leq K$. A detailed review of various sparse reconstruction algorithms proposed over the past decade can be found in \cite{tropp2010computational}.

It appears intuitive that during the acquisition of compressive measurements of an unknown signal $\bm{x}$, ``choosing an adaptive or sequential strategy that cleverly selects the next rows of sensing matrix based on what has been previously observed"\cite{arias2013fundamental} might help in easily reconstructing the unknown signal as compared to a non-adaptive strategy. In a non-adaptive strategy, the entire measurement vector $\bm{y}$ is acquired in one-shot and the rows of sensing matrix $\bm{A}$ are not chosen based on any prior or acquired information. In this paper, we choose the $l_0$ cost (similar to ``$l_0$ norm"), \textit{i.e.}, number of non-zero entries of the sensing matrix as our measure of sensing complexity for comparison between adaptive \cite{malloy2014near} \cite{davenport2012compressive} and non-adaptive strategies.

In this paper, we derive a general information-theoretic lower bound on the $l_0$ cost of reconstruction of a one--sparse signal that hold for any non-adaptive sensing matrix and demonstrate that adaptivity can achieve a lower $l_0$ cost as compared to any non-adaptive strategy, by a factor that diverges to infinity for large $N$. It is well established that both adaptive \cite{malloy2014near} and non-adaptive \cite{baraniuk2008simple} \cite{do2010lower} sensing strategies require at least $\Theta\left(\log_2(N)\right)$ measurements \cite{grover2012fundamental} \cite{aksoylar2014information}for the reconstruction of a one--sparse signal. We show that in the reconstruction of a one--sparse signal, any adaptive strategy would require an $l_0$ cost of $\Theta\left({N\log_2(N)}\right) $ as compared to bisection-type\cite{malloy2014near} adaptive strategies that require at most an $\mathcal{O}(N) $ $l_0$ cost when the number of measurements are limited to $\Theta({\log_2(N)})$. Our problem translates into a novel sphere packing problem within an $M$ dimensional sphere with an additional constraint of minimizing the $l_0$ cost of the sphere centres. We also discuss scenarios when the number of measurements varies from $\Theta(\log_2(N))$ to $\Theta(\log_2(N))$. Lastly, we provide outlines on extension of our results to $K$--sparse signals.

A sparser sensing matrix would offer significant advantages in terms of implementation, storage and reconstruction as discussed in \cite{gilbert2010sparse}. However, this line of work is mostly focused on the design of non-adaptive, sparse matrices and efficient reconstruction algorithms, rather than the derivation of fundamental limits. Adding on to the benefits of sparse matrices in \cite{gilbert2010sparse}, one can view the process of acquiring a measurement, \textit{i.e.}, computing the dot product of the signal with a row of the sensing matrix as a ``filtering-type" operation. The magnitude of the entries in the sensing matrix then corresponds to amplification/scaling during sample acquisition, while a zero value implies that no filter-tap (multiplier) is turned on. Then the $l_0$ cost would actually correspond to the number of multipliers required during compressive acquisition and thus have a direct implication on the sensing cost. A higher number of multipliers would also add more noise to the system and also increase the acquisition complexity. Similarly, in group testing/pooling type applications, the $l_0$ cost would correspond to the number of mixing operations required.

While not in the context of sparsity of sensing matrices, there is a body of literature that addresses the question of whether and when adaptivity is really helpful. Arias-Castro, Candes and Davenport \cite{arias2013fundamental} derive a minimax (worst case) lower bound on the mean square error for any sensing strategy (adaptive/non-adaptive). While they do not show any explicit advantage of adaptivity as in this paper, the authors argue that the potential benefits in Mean Square Error offered by adaptivity ``in the worst case" are within $\mathcal{O}(\log(N))$ over non-adaptive, random strategies. In this paper, we show an explicit advantage to adaptivity as compared to \textit{any} non-adaptive strategy and also highlight the costs of using random matrices in terms of $l_0$ cost. On the other hand, Malloy and Nowak\cite{malloy2014near} point out various advantages to adaptivity that include reducing reconstruction complexity (as does feedback in noisy channels) and also in providing gain in signal-to-noise ratio under limitations of sensing energy. They show that ``bisection-type" adaptive strategies can recover the support of the unknown $K$--sparse signal with minimum amplitude  $\Omega\left(\sqrt{\frac{N}{B}\log(K)}\right)$ as compared to traditional non-adaptive strategies that require an amplitude of $\Omega\left(\sqrt{\frac{N}{B}\log(N)}\right)$\cite{wang2010information} \cite{aeron2010information} for the same number of measurements, \textit{i.e.}, $\Theta(K\log_2(N))$. Here $\sqrt{B}$ is a constraint on the Frobenius norm of the sensing matrix. In a different scenario where $M>N$, Haupt, Castro and Nowak \cite{haupt2011distilled} establish that adaptivity in sensing can recover signals with "vanishingly small" amplitudes as compared to random non-adaptive strategies, under sensing energy constraints.
Some other related references that show advantages of adaptivity in specific scenarios can be found in \cite{malloy2011limits}, \cite{castro2008finding} and \cite{braun2014info}.

\textit{Why would one think adaptivity can make the sensing matrix sparser?} Fig.\ref{fig1} illustrates a scenario of ``bisection-type" adaptive sensing in comparison to non-adaptive sensing as the sensing matrices get sparser. It provides an intuition that while the number of measurements remain the same (at least in order sense), even with the sparsest non-adaptive sensing matrices, adaptivity always incurs a lower $l_0$ cost than non-adaptive sensing. References in favour of adaptivity \cite{malloy2014near} have cited existing information-theoretic bounds\cite{aeron2010information}\cite{wang2010information} on SNR and number of measurements for non-adaptive compressive sensing that are mostly based on certain deterministic matrices or random, Gaussian matrices. However, Gaussian matrices are dense with an $l_0$ cost of $N M$. Adaptivity can allocate non-zero entries in the sensing matrix selectively, like a binary search. The intuition is most clear for one--sparse signals, and hence those are discussed first.
\begin{figure}[!t]
\centering
\includegraphics[height=3 in]{Sensing_mat.png

\caption{The figure provides intuition on why adaptive sensing could have fundamentally sparser matrices than nonadaptive sensing. The matrices on the left use an adaptive bisection strategy to narrow down the search space in $\Theta (\log_2 N)$ steps, requiring $\Theta(\log_2 N)$ measurements. Interestingly, the construction on the right can simulate the bisection strategy nonadaptively. However, the cost is increased density of the matrices.}
\label{fig1}
\end{figure}

\section{Notation and Problem Formulation}

Let the $l_0$ cost of a sensing matrix $\bm{A}=[A_1 A_2 \ldots A_N]$ in problem (\ref{eq1}) be defined as:
\begin{equation}
||\bm{A}||_{0,0} = \sum_{i=1}^N ||A_i||_0 = \sum_{i=1}^N \sum_{j=1}^M \mathbb{I}(A(j,i) \neq 0)
\end{equation}
Here $A_i$ denotes the $i$-th column of $\bm{A}$ and $\mathbb{I}(.)$ denotes the indicator function.
We say a function $F(N)=\Omega(g(N))$ if there exist a positive constant $C_0$ such that, $F(N)\geq C_0 g(N)$ as $N \to \infty$. It implies that asymptotically, $g(N)$ is not dominated by $F(N)$. Similarly, $F(N)=\Theta(g(N))$ if there exist positive constants $C_1,C_2$ such that, $C_1 g(N) \leq F(N) \leq C_2 g(N)$. It implies that neither $F(N)$ nor $g(N)$ are asymptotically dominated by each other. Lastly, $F(N)=\mathcal{O}(g(N))$ if $F(N) \leq C_3 g(N)$ for some positive constant $C_3$.

We derive lower bounds on $||\bm{A}||_{0,0}$ for non-adaptive sensing that asymptotically dominate upper bounds for adaptive sensing. In Theorem 1 we consider the case of reconstruction of a one sparse signal $\bm{x}$ using a \textit{binary} sensing matrix $\bm{A}$ in the absence of noise. In Theorem 2, we extend our analysis to real-valued sensing matrices for reconstructing a  one sparse signal $\bm{x}$ with a target probability of error in the presence of additive  white Gaussian noise. Note that we have assumed $M$ to vary as a logarithmic function of $N$, when $N$ is large.

\section{Main Results}

Our first theorem establishes an information-theoretic lower bound on the $l_0$ cost of non-adaptive sensing for \textit{binary} sensing matrices in the absence of noise when the number of measurements are limited to $\Theta\left( \log_2 (N)\right)$.

\newtheorem{theorem}{Theorem}
\begin{theorem}
 For the reconstruction of an arbitrary one--sparse signal with amplitude $\mu$ using \textit{binary} sensing matrices with number of measurements $M =T \log_2 (N)$ where $T$ is a constant greater or equal to $1$, any non-adaptive sensing strategy incurs an $l_0$ cost of $ \Theta \left(N\log_2(N)\right) $.
\end{theorem}

\textit{Proof Sketch}:
Consider the recovery of the support of a one--sparse vector $\bm{x}$, from $\bm{y}$ and $\bm{A}$ when $ M=\Theta \left(\log_2(N)\right) $. Then, any non-adaptive strategy would at least require the columns $\{A_i\}$ of $\bm{A}$ to be distinct. Notice $$\bm{A x}=[A_1,\cdot \ \cdot, A_N]\begin{bmatrix}
x_1\\
\cdot\\
\cdot\\
x_N
\end{bmatrix}=\sum_{i=1}^N A_ix_i$$
If two columns (say $i_1$ and $i_2$) of $\bm{A}$ are equal, then two one--sparse $\bm{x}$ vectors with respective supports $\{i_1\}$ and $\{i_2\}$ become indistinguishable.
Among all \textit{binary} sensing matrices $\bm{A}$ with $N$ unique columns, we consider one with minimum $l_0$ cost and derive lower bounds on its $l_0$ cost. Such a \textit{binary} sensing matrix $\bm{A}$ with minimum $l_0$ cost can be easily designed by choosing the columns in ascending order of $l_0$ cost, \textit{i.e.}, first all possible columns with $l_0$ cost $1$, then all possible columns with $l_0$ cost $2$ and so on until we get $N$ unique columns. We show that $||\bm{A}||_{0,0}$ is always $\Theta(N\log_2(N))$.

\emph{Note that for $M < \log_2(N)$, it is not possible to construct binary sensing matrices with unique non-zero columns. So we assume $M =T \log_2 (N)$ where $T \geq 1$.}
Our next theorem establishes a lower bound on the $l_0$ cost of any non-adaptive sensing matrix in the presence of noise, when $||A_i||_2$ is bounded. For non-adaptive strategies, limitations of sensing energy \cite{malloy2014near} usually enforce upper bounds on $||A_i||_2$, thus justifying the assumptions of \textit{Theorem 2}.

\begin{theorem}
For the reconstruction of an arbitrary one--sparse signal with amplitude $\mu$ in the presence of Gaussian Noise of unit variance, using real-valued sensing matrices, under the constraints that $M =T \log_2 (N)$ where $T$ is a constant greater or equal to $1$ and $||A_i||_2$ is bounded by  $\tau$, any non-adaptive sensing strategy cannot achieve a target probability of error $\epsilon$  without incurring an $l_0$ cost of  $\Theta\left(N \log_2(N)\right)$, provided that the allowed bound on $||A_i||_2$ \textit{i.e.}, $\tau=\Theta(Q^{-1}(\epsilon)/\mu) $ .
\end{theorem}

\textit{Proof Sketch:}
First consider the case of one--sparse signal $\bm{x}$ with non-zero value equal to $\mu$. Think of each column of $\bm{A}$ as a point in the $M$ dimensional space $ \mathbb{R}^M$. The minimum probability of error in distinguishing two points in $\mathbb{R}^M$, say $A_i$ and $A_j$ (that correspond to two columns of $\bm{A}$) scaled by $\mu$ is always bounded by $P_e ^{ i,j} \geq Q\left(\frac{\mu ||A_i-A_j||_2}{2}\right)$ where $||\cdot||_2$ denotes the $l_2$ norm and $Q(\cdot)$ is the Gaussian tail function defined as $Q(a)=\frac{1}{\sqrt{2\pi}}\int_{a}^{\infty}e^{-b^2/2}db $. For any non-adaptive strategy to attain a target probability of error $\epsilon$, we must have
\begin{equation}
 ||A_i-A_j||_2 \geq \frac{2Q^{-1}(\epsilon)}{\mu }\ \forall\ i,j\in \{1,2,\ldots,N\},\ i \neq  j
\end{equation}
Let $d=\frac{2Q^{-1}(\epsilon)}{\mu }$.
Under $||A_i||_2 \leq \tau$ for some constant $\tau$, the problem translates to finding $N$ unique points in a sphere in $\mathbb{R}^M$ of radius $\tau$, that are each separated by at least $d$. As before, among all such matrices, (\textit{i.e.}, a collection of $N$ points in $\mathbb{R}^M$), we consider a matrix $\bm{A}$ with minimum $l_0$ cost and attempt to find a lower bound for it.

\newtheorem{corollary}{Corollary}
\begin{corollary}
Bisection-type adaptive strategies only require an $l_0$ cost of $\mathcal{O}(N)$ to reconstruct one--sparse signals when the number of measurements vary from $\Theta(\log_2(N))$ to $\Theta(N) $and are thus asymptotically dominated by non-adaptive strategies.
\end{corollary}

In the next Section, we provide some preliminary lemmas and then we use them prove our theorems.

\section{Proofs of Theorems 1 and 2}

\subsection{Preliminary Results}
\newtheorem{lemma}{Lemma}
\begin{lemma}
 Let $r$ be an integer such that $1\leq r < M/2$. Also, let $p=\frac{r}{M}< 1/2$.
\end{lemma}
\begin{equation}
\sum_{l=1}^r \binom{M}{l} \leq \frac{\binom{M}{r}}{1-2p}
\end{equation}
Moreover, if there exists a constant $\lambda$ such that $p\leq \lambda < 1/2$, then the partial summation is of the same order as the last term.
\begin{equation}\label{eq2}
\binom{M}{r} \leq \sum_{l=1}^r \binom{M}{l} \leq \frac{\binom{M}{r}}{1-2\lambda}
\end{equation}

\begin{IEEEproof}
First observe that
\begin{equation}
  \frac{\binom{M}{r-1}}{\binom{M}{r}} = \frac{r}{M-r+1} < \frac{2r}{M}= 2p < 1
\end{equation}

Similarly, for $t=1,2,\cdots,r-2$,
\begin{equation}
    \frac{\binom{M}{r-t-1}}{\binom{M}{r-t}} = \frac{r-t}{M-r+t+1} < \frac{2r}{M}= 2p < 1
\end{equation}

Thus,
\begin{align}
\MoveEqLeft  \sum_{l=1}^r \binom{M}{l} \leq \binom{M}{r}\left(1+(2p)+(2p)^2+ \cdots+ (2p)^{(r-1)}  \right)  \nonumber \\
& \leq \binom{M}{r}\left(1+(2p)+(2p)^2+ \cdots \right)
= \frac{\binom{M}{r}}{1-2p}
\end{align}

Note that, if $p\leq \lambda< 1/2$ ,(\ref{eq2}) follows.
\end{IEEEproof}

\begin{lemma}\cite[Lemma 4.7.1]{ash1990}
The binary entropy function is defined as $H(p)=-p\log_2(p)-(1-p)log_2(1-p)$  where $0 \leq p \leq 1$. Let $p=\frac{r}{M} \leq 1$.

\begin{equation}
\frac{2^{M H(p)}}{\sqrt{8Mp(1-p)}} \leq \binom{M}{r} \leq \frac{2^{M H(p)}}{\sqrt{2\pi Mp(1-p)}}
\end{equation}
\end{lemma}

\begin{lemma}\cite[Lemma 2]{sahai2008price}
For an integer $d >1$, and $p<1/2$
\begin{equation}
H(p) \leq \frac{2d}{ln(2)} (p)^{1-\frac{1}{d}}
\end{equation}
\end{lemma}

\subsection{Binary Sensing Matrices}

\textit{Proof of Theorem 1:} Recall that we are required to bound $||\bm{A}||_{0,0}$ where the columns of $\bm{A}$ are chosen in ascending order of $l_0$ cost. Let $r_0$ be the integer such that
\begin{equation}
\sum_{l=1}^{r_0} \binom{M}{l} < N \leq \sum_{l=1}^{r_0+1} \binom{M}{l}
\end{equation}
For $l=1,2,\cdots,r_0$, there can be at most $\binom{M}{l}$ columns with $l$ ones, (\textit{i.e.}, $l_0$ cost $l$) and the remaining $\left(N-\sum_{l=1}^{r_{0}} \binom{M}{l}\right)$ columns have $l_0$ cost $(r_0+1)$.

If $M \leq \lfloor \log_2(N) \rfloor$, it is not possible to construct \textit{binary} matrices with $N$ unique columns. If $M=\lfloor \log_2(N)\rfloor+1$, then $r_0 \leq M/2$ and $||\bm{A}||_{0,0} \approx 0.5 N\log_2(N)$. As $M$ increases beyond $\lfloor \log_2(N)\rfloor+1$ for fixed $N$, $r_0$ decreases, and \emph{so does $||\bm{A}||_{0,0}$}. Thus, it is sufficient to prove the lower bound on $||\bm{A}||_{0,0}$ for  $M=T\log_2(N)$ where $T$ is a constant strictly greater than 1, as $||\bm{A}||_{0,0}$ for $T=1$ will only be higher. For $T>1$, we always have $r_0<M/2$ (required for \textit{Lemma 1}).

Let $ N = c_M \sum_{l=1}^{r_0} \binom{M}{l}$ for some $c_M$. Let $p_0=\frac{r_0}{M}$. First, we show that if $M=T\log_2(N)$ ( $T>1$), then there exists a constant $\lambda$ such that $p_0\leq \lambda <1/2$. Note that,
\begin{equation}
 \frac{2^{M H(p_0)}}{\sqrt{8Mp_0(1-p_0)}} \overset{\textit{Lemma2}}{\leq}  \sum_{l=1}^{r_0} \binom{M}{l} < N
\end{equation}
Taking logarithm of both sides,
\begin{equation}\label{eq11}
H(p_0)\leq \frac{\log_2(N)}{M} +\frac{\log_2(\sqrt{8r_0})}{M} < \frac{1}{T} + \frac{\log_2(\sqrt{8M})}{M}
\end{equation}
Note that, $\frac{\log_2(\sqrt{8M})}{M}$ is decreasing and tends to $0$ for large $M$. For any constant $\lambda'$ such that $(1/T)<\lambda'<1$, there always exists an $M=M(\lambda')$, such that
$\frac{\log_2(\sqrt{8M})}{M}<\lambda'-(1/T) $ for all $M >M(\lambda')$. Or, there exists a constant $\lambda=H^{-1}(\lambda')$ such that, $p_0 \leq \lambda < H^{-1}(1)=1/2$. This is required to apply \textit{Lemma 1}.

We now provide a lower bound on the $l_0$ cost of $\bm{A}$.
\begin{align}\label{eq3}
\MoveEqLeft ||\bm{A}||_{0,0} =\sum_{l=1}^{r_0} \binom{M}{l} \ l + \left(N-\sum_{l=1}^{r_0} \binom{M}{l}\right) \ (r_0+1)\nonumber\\
&\geq  r_0 \binom{M}{r_0} + \sum_{l=1}^{r_0} \binom{M}{l}(c_M-1)  (r_0+1)\nonumber\\
&\geq r_0 \ c_M \binom{M}{r_0} \overset{\textit{Lemma1}}{\geq} r_0\ c_M \sum_{l=1}^{r_0} \binom{M}{l}(1-2\lambda) \nonumber\\
&= (1-2\lambda) \ r_0\ N
\end{align}
Now, note that $r_0 < M$. Therefor either $r_0=\Theta(M)$ or $r_0 =\bm{o}(M)$. We show here that $r_0=\Theta(M)$. Look into the range of $c_M$.
\begin{align}\label{eq4}
\MoveEqLeft 1 < c_M \leq \frac{\sum_{l=1}^{r_0+1} \binom{M}{l}}{\sum_{l=1}^{r_0} \binom{M}{l}} <\frac{M+1}{r_0+1}<\frac{M}{2}
\end{align}
Using \textit{Lemma 1} and \textit{2},
\begin{equation}
N=c_M \sum_{l=1}^{r_0} \binom{M}{l}\leq \frac{c_M 2^{M H(p_0)}}{(1-2\lambda)\sqrt{\pi r_0}}
\end{equation}
Taking logarithm of both sides,
\begin{align} \label{eq12}
 \MoveEqLeft \frac{\log_2(N)}{M} \leq \frac{\log_2(c_M/((1-2\lambda)\sqrt{\pi r_0})}{M}+ H(p_0) \nonumber\\
 &\overset{(\ref{eq4})}{\leq}\frac{\log_2(M/(1-2\lambda))}{M}+ H(p_0)
\end{align}
Recall that $M=T\log_2(N)$ for some constant $T>1$. For large $M$, $\frac{\log_2(M/(1-2\lambda))}{M} \to 0$. For any positive constant $\eta' < (1/T)$, there always exist an $M=M(\eta')$ such that $\frac{\log_2(M/(1-2\lambda))}{M} <\eta' $ for all $M>M(\eta')$. \\Or, $H(p_0)\geq (1/T)-\eta' >0 $ for large $M$, which implies that, $r_0 \geq H^{-1}((1/T)-\eta') M=\eta M$ for some constant $\eta$.
Using this result in (\ref{eq3}), we finally obtain the lower bound,
\begin{equation}
||\bm{A}||_{0,0} \geq(1-2\lambda)\eta NM = C N \log_2(N)
\end{equation}
Here $C= (1-2\lambda)\eta T$ is a constant. Needless to say, the $l_0$ cost $||\bm{A}||_{0,0} \leq NM = T N\log_2(N)$ which is the total number of elements in an $M \times N$ matrix. Thus the sensing matrix is always dense,\textit{i.e.}, the $l_0$ cost is of same order as the total number of elements. Thus $||\bm{A}||_{0,0}=\Theta(N\log_2(N) )$\hfill $\IEEEQED$

\subsection{Real Valued Sensing Matrix in Noise}
\begin{figure}[!t]
\centering
\includegraphics[height=4in]{Sphere_packing.png}

\caption{A New Sphere Packing Problem - The figure illustrates the problem of finding $N$ unique columns of the sensing matrix $\bm{A}$ with minimum $l_0$ cost. The problem has an interesting interpretation as a sphere packing problem. For simplicity, we choose $M=3$ in this figure and then show how we can keep placing spheres of radius $d/2$ such that the total $l_0$ cost of the centres of the spheres (columns of $\bm{A}$) is minimum.}
\label{fig2}
\end{figure}
\textit{Proof of Theorem 2:}
The performance of non-adaptive reconstruction strategies relies on how well one can distinguish any two columns of sensing matrix $\bm{A}$, in the presence of noise. As already mentioned, we first consider the one--sparse case. We need to find $N$ unique points in a sphere in $\mathbb{R}^M$ dimensional space of radius $\tau$ that are each separated by at least $d =\frac{2 Q^{-1}(\epsilon)}{\mu}$. Assume we have $u_1$ points of $l_0$ cost $1$, $u_2$ points of $l_0$ cost $2$ and so on. Thus, $N=u_1+ u_2 +\cdots+u_{r_0'}$ and $||\bm{A}||_{0,0}= \sum_{l=1}^{r'}u_l \ l$.

Now consider the maximum possible number of points with $l_0$ cost equal to 1, and separated by distance $d$ in an $M$ dimensional sphere. Clearly there are $\binom{M}{1}$ possible choices of the non-zero dimension, and at most $\frac{2\tau}{d}$ points can be placed along each dimension. Thus $ u_1 \leq \binom{M}{1}\frac{2\tau}{d}$.

Similarly, consider the maximum possible number of points with $l_0$ cost equal to $2$, and separated by distance $d$. There are $\binom{M}{2}$ possible choices of $2$ non-zero dimensions among $M$. For any such combination of $2$ dimensions, the problem is equivalent to fitting maximum number of $2D$ spheres of radius $d/2$ within a $2D$ sphere of radius  $\tau$. We would always have less than $\frac{\pi \tau^2}{\pi (d/2)^2}$ such points (or equivalently spheres) along any such combination of $2$ dimensions. Thus $ u_2 \leq \binom{M}{2}\left(\frac{2\tau}{d}\right)^2$.

For any $l \in \{1,2,\cdots,M\} $, the maximum number of points with $l_0$ cost equal to $l$ and separated by distance $d$ within the $M$ dimensional sphere of radius $\tau$ is always less than $\binom{M}{l}(\frac{2\tau}{d})^l $ as shown in Fig.\ref{fig2}. This follows since there are $\binom{M}{l}$ possible choices of the $l$ non-zero dimensions and for each such choice of $l$ non-zero dimensions, the number of $l$ dimensional spheres of radius $d/2$ that can be placed in a big $l$ dimensional sphere of radius $\tau$ is given by the ratio of the volumes of the two $l$ dimensional spheres. Thus $u_l \leq \binom{M}{l} (\frac{2\tau}{d})^l$.

Choose $v_l=\binom{M}{l} \left(\frac{2\tau}{d}\right)^l \ \forall \ l \in {1,2 .. M}$. Let $r_0$ be the integer such that $\sum_{l=1}^{r_0} v_l < N \leq \sum_{l=1}^{r_0+1} v_l$.  Thus, for $\kappa >0$,\\
$ v_1+v_2+..v_{r_0}+\kappa= N =u_1+u_2+\cdots+u_{r_0'} $

First we prove that $r_0 < r_0'$. Assume $r_0 \geq r_0'$. Then,
\begin{align}
 \MoveEqLeft N=u_1+u_2+..+u_{r_0'} \leq v_1+v_2+..+v_{r_0'} \nonumber\\
 & \leq v_1+v_2..+v_{r_0} < N
\end{align}
This is a contradiction. Thus, the $l_0$ cost can be lower bounded as shown below, using the fact that the summation puts more weights on the lower cost terms.
\begin{equation}
||\bm{A}||_{0,0}= \sum_{l=1}^{r_0'}u_l \ l \geq \sum_{l=1}^{r_0}v_l  l +\kappa (r_0+1)
\end{equation}
We follow a similar analysis to find a lower bound for $\sum_{l=1}^{r_0}v_l \ l +\kappa (r_0+1)$. Let $c_M\sum_{l=1}^{r_0} v_l = N$ and $p_0=r_0/M$.

\begin{equation}
    H(p_0)+p_0\log_2\left(\frac{2\tau}{d}\right)\leq \frac{\log_2(N)}{M}+\frac{\log_2(\sqrt{8r_0})}{M}\to \frac{1}{T}
\end{equation}
Recall that, $\left(\frac{2\tau}{d}\right)$ is $\Theta(1)$. Thus, for large $M$, there exists a constant $\lambda<1/2$ such that, $p_0\leq \lambda < H^{-1}(1)=1/2  $.  We now provide a lower bound on the $l_0$ cost of $\bm{A}$.
\begin{align}\label{eq5}
\MoveEqLeft ||\bm{A}||_{0,0} \geq \sum_{l=1}^{r_0} v_l l + \sum_{l=1}^{r_0} v_l(c_M-1) \ (r_0+1)\nonumber\\
&\geq  r_0 \ c_M\ v_{r_0}  \overset{\textit{Lemma 1}}{\geq} r_0 N (1-2\lambda)
\end{align}

Lastly, we show that $r_0=\Theta(M)$. As before, since it is already known that $r_0 <M$, either $r_0=\Theta(M)$ or $r_0=\bm{o}(M)$. Look into the range of $c_M$.

\begin{align}\label{eq6}
\MoveEqLeft 1 < c_M \leq \frac{\sum_{l=1}^{r_0+1} v_l}{\sum_{l=1}^{r_0} v_l}  <1+\frac{(M-r_0)(\frac{2\tau}{d})}{r_0+1}< M \frac{2\tau}{d}
\end{align}
Like the previous proof,
\begin{equation}
N =  c_M \sum_{l=1}^{r_0} \binom{M}{l}\left(\frac{2\tau}{d}\right)^l \leq \frac{c_M 2^{M H(p_0)}}{(1-2\lambda)\sqrt{\pi r_0}} \left(\frac{2\tau}{d}\right)^{r_0}
\end{equation}

Taking logarithm and using (\ref{eq6})
\begin{align}\label{eq7}
\MoveEqLeft \frac{\log_2(N)}{M}  \leq \frac{\log_2\left(\frac{2\tau M}{d(1-2\lambda)}\right)}{M} + H(p_0) + p_0\log_2\left(\frac{2\tau}{d}\right)
\end{align}
Now, if $p_0=r_0/M \to 0$ for large $M$, then all the terms in R.H.S. of (\ref{eq7}) would tend to $0$.  But since $M=T\log_2(N)$ for some constant $T \geq 1$, the L.H.S. is always a non-zero constant $1/T$. Thus we arrive at a contradiction. Thus, we have $r_0 \geq \eta M$ for some constant $\eta=\Theta(1)$.
Using  this result in (\ref{eq5}), we obtain,
\begin{equation}
    ||\bm{A}||_{0,0} \geq (1-2\lambda)\eta N M\geq C N \log_2(N)
\end{equation}
As $M=\Theta(\log_2(N))$, we have $||\bm{A}||_{0,0} =\Theta(N\log_2(N))$. \hfill $\IEEEQED$
\subsection{Comparison with Adaptive Sensing}
\textit{Proof of Corollary: }
Consider the $l_0$ cost of the bisection-type adaptive sensing strategies as described in \cite{davenport2012compressive}. As in Fig.\ref{fig1}, first the total length $\{1,2,\cdots,N\}$ is divided into two equal blocks, and any one measurement is acquired. Based on the received measurement value, the active block (set of possible non-zero locations) is narrowed down. That blocks is again divided into two parts and any one part is sensed. For such a sensing strategy,
\begin{equation}
||\bm{A}||_{0,0} \leq \left(\frac{N}{2} + \frac{N}{4} + \cdots \right) \leq N
\end{equation}
Thus, adaptive sensing matrices require an $l_0$ cost of at most $\mathcal{O}(N)$ for signal reconstruction and are thus sparse. Clearly, this upper bound is asymptotically dominated by $N\log_2(N)$.

Note that, since we have already allowed the values of the non-zero elements of $\bm{x}$ to be sufficiently high, it is guaranteed (from \cite{malloy2014near}) to succeed in the presence of noise.

\subsection{Discussion on higher orders of M}
We consider the case of reconstruction of one--sparse signals using \textit{binary} sensing matrices, when $M$ is between $\log_2(N)$ and $N$. From (\ref{eq11}), we note that $p_0 \to 0$ if $\log_2(N)/M \to 0$ for large $M$ and $N$. We can always find a constant $\lambda$ arbitrarily small, such that $p_0\leq \lambda <1/2$. The binomial summation in \textit{Lemma 1} is practically equal to the largest term. From (\ref{eq3})
\begin{equation}
  ||\bm{A}||_{0,0} \geq c_M r_0 \binom{M}{r_0} \geq r_0 N(1-2\lambda) \approx r_0 N
\end{equation}
In general, note that when $M=\Theta(\log_2(N))$, then $r_0=\Theta(M)$ and $||\bm{A}||_{0,0}=\Theta(N\log_2(N))$. As $M$ increases, the lower bound on $l_0$ cost decreases. When $M$ is of higher order, say $M=N$, then $r_0=1$ and we have a reduced $l_0$ cost $N$ using simply an identity sensing matrix. From (\ref{eq12}),
\begin{align}
 \frac{\log_2(N/c_M)}{M}\leq H(r_0/M)\overset{\textit{Lemma 3}}{\leq} \frac{2d}{ln(2)} \left(\frac{r_0}{M}\right)^{1-\frac{1}{d}}\\
 \left(\frac{ln2 \ \log_2(N/c_M)}{2d}\right)^{d/(d-1)} M^{-1/(d-1)}\leq r_0\ \ \ \ \ \
\end{align}
This leads to the following bound.
\begin{equation}
||\bm{A}||_{0,0}
\geq C \max_{d} \frac{N}{ M^{1/(d-1)}} \left(\frac{ln2 \log_2(N/c_M)}{2d}\right)^{d/d-1}
\end{equation}
Similar bounds may be derived for real-valued matrices.

\section{Conclusions}
This paper clearly shows an advantage of adaptivity in terms of $l_0$ cost of sensing. It establishes a lower bound on the $l_0$ cost that holds for any non-adaptive strategy, whether it is random or not.  $K$--sparse signals, we can argue that if a matrix does not have unique columns and fails to reconstruct one--sparse signals, it naturally fails to reconstruct a $K$--sparse signal. If a matrix has two similar columns say $\{i_1\}$ and $\{i_2\}$, then two exactly $K$ sized supports differing only at $\{i_1\}$ and $\{i_2\}$ become indistinguishable. Thus, the lower bound on the $l_0$ cost of $\bm{A}$  cannot be less than that in the case of one--sparse signals. Thus, $||\bm{A}||_{0,0}=\Theta\left(N K\log_2(N)\right)$ when $M=\Theta(K\log_2(N))$. For small values of $K$,  this still asymptotically dominates $ \mathcal{O}(KN)$ which is the $l_0$ cost for bisection-type adaptive strategies.
\section*{Acknowledgment}
This work was supported in part by Systems on Nanoscale Information fabriCs (SONIC), one of the six SRC STARnet Centers, sponsored by MARCO and DARPA. We also acknowledge the support of NSF-CCF-1350314 (NSF Career Award). S Dutta was also supported by a Dean's Fellowship from Carnegie Mellon University.

We also thank Praveen Venkatesh, Haewon Jeong, Yaoqing Yang and Aarti Singh for their suggestions on the paper.

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

\bibliographystyle{IEEEtran}