# Singular solutions of the Yamabe problem in the Heisenberg group and their
bifurcation

Claudio Afeltra111Scuola Normale Superiore, Piazza dei Cavalieri 7, 56126 Pisa
(Italy) -<EMAIL_ADDRESS>
###### Abstract

We prove the existence of a homogeneous singular solution of the critical
equation

$-\Delta u=u^{\frac{Q+2}{Q-2}}$

on the Heisenberg group $H^{n}$, where $Q$ is the homogeneous dimension. In
order to do this, we introduce a suitable concept of normal curvature for
hypersurfaces. Furthermore we study the bifurcation of non-homogeneous
solutions from the homogeneous one.

##  1 Introduction

The Yamabe problem has drawn a large interest in Riemannian geometry. Its
solution in the compact case (due to the works of Yamabe, Trudinger, Aubin and
Schoen) has constituted a major advance in the fields of geometric analysis
and partial differential equations, and it has been drawing attention until
today (on this topic see, for example, [A] for a general treatment).

In the field of CR geometry, the analogous problem of finding a conformal
metric with constant Webster curvature (the analogous of scalar curvature).

On the Heisenberg group, which is the “model” CR manifold, the Yamabe problem
is equivalent to finding the positive solutions of the equation

$-\Delta u=u^{\frac{Q+2}{Q-2}},$ (1)

where $\Delta$ is the sublaplacian and $Q$ is the homogeneous dimension
(precise definitions are given later).

The positive solutions of this equation satisfying some integrability
hypotheses were classified by Jerison and Lee [JL]; geometrically they
correspond to conformal factors that trasform the standard pseudohermitian
structure of $\mathbf{H}^{n}$ into the push-forward of the pseudohermitian
structure of the sphere ${\bf S}^{2n+1}\subset\mathbf{C}^{n+1}$ with respect
to the Cayley transform, up to translations and dilations. This classification
plays an important role in the solution of the CR Yamabe problem, see [JL2],
[GY], [Gam] and [CMY].

Additionally to this, it is interesting to study the problem on
$\mathbf{H}^{n}\setminus\\{0\\}$. In the Riemannian case all the solutions
singular at a point were classified by Caffarelli, Gidas and Spruck (see
[CGS]). These form a continuous one-parameter family of radially periodic
metrics depending on a parameter $\tau\in(0,1]$, called Delaunay metrics: for
$\tau=1$ the metric is homogeneous and corresponds to the cylindrical metric,
and for $\tau\to 0$ tends to a superposition of regular solutions. This
classification has been useful in the study of the profiles of general
singular solutions (see [KMPS]), as well as in the study of blow-ups in the
problem of prescribed curvature (see [Li1], [Li2], [CL]).

The author of this article proved (see [Af]) the existence of analogues of the
Delaunay metrics for small values of $\tau$, constructed by perturbing an
approximated solution consisting of a series of regular solutions suitable
dilated. In this article, it is proved the existence of a homogeneous solution
analogous to the Euclidean one:

######  Theorem 1.1.

There exists a solution $\Psi$ of the equation

$-\Delta\Psi=\Psi^{\frac{Q+2}{Q-2}},$

defined on $\mathbf{H}^{n}\setminus\\{0\\}$, such that
$\Psi\circ\delta_{\lambda}=\lambda^{\frac{Q-2}{2}}\Psi$ and
$\Psi(z,t)=\Psi(|z|,t)$.

The above result is proved by posing the problem in a variational form, and
then performing a conformal change that trasforms
$\mathbf{H}^{n}\setminus\\{0\\}$ in a pseudohermitian cylinder, and imposing
symmetries in order to reduce the problem to an ODE with variational
structure.

The main difficulty is that, because of the non compactness of
$\mathbf{H}^{n}\setminus\\{0\\}$, the problem has to be formulated on a closed
annulus $\\{1\leq|x|\leq r\\}$ (where $|\cdot|$ is the homogeneous norm), and
so one has to put boundary conditions that, under a conformal change, behave
in a treatable way. It is known that the mean curvature behaves in such a way,
indeed the prescription of the mean curvature of the boundary is considered
the most natural boundary condition in the prescribed curvature problem for
manifolds with boundary (see, for example, [E]). In our case there is not such
a concept, except in dimension three (see [CHMY]). So we introduce, in
arbitrary dimension, the notion of canonical pseudohermitian normal curvature.
In such a way we can formulate variationally the problem of the prescription
of the Webster curvature with boundary conditions, with a functional that is
conformally invariant.

In the second part of the article, we study the problem of the bifurcation of
radially periodic solutions from the homogeneous one we found. That is,
considering a parameter $T$, we want to prove that solutions to equation (1)
such that $u\circ\delta_{T}=T^{-\frac{Q-2}{2}}$ bifurcate from the homogeneous
solution for infinitely many values of $T$. This problem has a variational
structure: the radially periodic solutions are critical points of a certain
functional $\mathscr{J}_{T}:X_{T}\to\mathbf{R}$ whose Morse index tends to
infinity for $T\to\infty$, and so, such that its second differential is
singular for infinitely many values of $T$. We prove the following result.

######  Theorem 1.2.

There exists arbitrarily large values of $T$ for which $d^{2}\mathscr{J}_{T}$
is singular, and every such value is a bifurcation value.

The article is structured as follows. After the preliminaries of Section 2, in
Section 3 we introduce a notion of curvature of a hypersurface in a
pseudohermitian manifold that serves our purposes. In Section 4 we prove
Theorem (1.1) solve the problem by a conformal change of pseudohermitian
metric, and through the imposition of natural simmetries. In Section 5 we
study the problem of bifurcation.

##  2 Preliminaries and notation

For a general introduction to CR manifolds we refer to [DT], but we recall
here some basic concepts.

A CR manifold is a real smooth manifold $M$ endowed with a subbundle
$\mathscr{H}$ of the complexified tangent bundle of $M$, $T^{\mathbf{C}}M$,
such that $\mathscr{H}\cap\overline{\mathscr{H}}=\\{0\\}$ and
$[\mathscr{H},\mathscr{H}]\subseteq\mathscr{H}$. We will assume $M$ to be of
hypersurface type, that is that $\dim M=2n+1$ and that $\dim\mathscr{H}=n$.
There exists a non-zero real differential form $\theta$ that is zero on
$\mathfrak{Re}(\mathscr{H}\oplus\overline{\mathscr{H}})$; it is unique up to
scalar multiple by a function. Such a form is called pseudohermitian or
contact form. On a pseudohermitian manifold, the Levi form on $\mathscr{H}$ is
defined as the 2-form
$L_{\theta}(V,W)=-id\theta(V,\overline{W})=id\theta([V,\overline{W}])$. A CR
manifold is said to be pseudoconvex if it admits a positive definite Levi form
(this implies every Levi form to be definite), it is said nondegenerate if it
admits a nondegenerate Levi form. An almost complex structure $J$ can be
defined on $H(M)=\mathfrak{Re}(\mathscr{H}+\overline{\mathscr{H}})$ in a
natural way, by $J(V+\overline{V})=i(V-\overline{V})$. There exists a unique
vector field $T$ such that $\theta(T)=1$ and $i_{T}d\theta=0$. This permits to
define a natural Riemannian metric $g_{\theta}$, which coincides with the
metric $G_{\theta}$ associated to $L_{\theta}$ on $H(M)$, and such that
$g_{\theta}(T,T)=1$ and $T$ is orthogonal to $H(M)$.

On a nondegenerate pseudohermitian manifold one can define a connection, the
Tanaka-Webster connection. This allows to define curvature operators in an
analogous manner as in Riemannian geometry: the pseudohermitian curvature
tensor is the curvature of the Tanaka-Webster connection, the Ricci tensor is

$\operatorname{Ric}(X,Y)=\operatorname{trace}(Z\mapsto R(Z,X)Y),$

and the Webster scalar curvature is the trace of the Ricci tensor with respect
to the Levi form.

If $\widetilde{\theta}=u^{2/n}\theta$, the transformation law of the Webster
curvature is

$\widetilde{W}=u^{-1-2/n}\left(-\frac{2n+2}{n}\Delta_{b}u+Wu\right),$ (2)

(see [DT]), where $\Delta_{b}$ is the sublaplacian, which can be defined as
the divergence of the subgradient with respect to the natural volume form in
such context, $\theta\wedge(d\theta)^{n}$. So the Yamabe problem leads to the
equation

$-\frac{2n+2}{n}\Delta_{b}u+Wu=\lambda u^{1+2/n}.$

The model pseudohermitian manifold, and the one we will study, is the
Heisenberg group $\mathbf{H}^{n}$, that is the Lie group
$\mathbf{C}^{n}\times\mathbf{R}$ with the product

$(z_{1},t_{1})\cdot(z_{2},t_{2})=(z_{1}+z_{2},t_{1}+t_{2}+2\,\mathfrak{Im}(z_{1}\cdot\overline{z_{2}})),$

endowed with the subbundle spanned by the standard left invariant vector
fields

$Z_{\alpha}=\frac{\partial}{\partial
z_{\alpha}}+i\overline{z_{\alpha}}\frac{\partial}{\partial t},$

and with the unique left invariant pseudohermitian with respect to this CR
structure. In this case the sublaplacian coincides with the group sublaplacian
given by

$\Delta=2\sum_{\alpha=1}^{n}(Z_{\alpha}\overline{Z_{\alpha}}+\overline{Z_{\alpha}}Z_{\alpha}).$

We will use also the Koranyi norm, given by

$|(z,t)|=\left(|z|^{4}+t^{2}\right)^{1/4},$

and the dilations given by

$\delta_{\lambda}(z,t)=(\lambda z,\lambda^{2}t)$

for $\lambda>0$. Notice that, in the above notation,
$|\delta_{\lambda}x|=\lambda|x|$.

It turns out that $\mathbf{H}^{n}$ has zero Webster curvature, and so, up to
an inessential constant, the Yamabe problem is equivalent to find positive
solution to equation

$-\Delta u=u^{\frac{Q+2}{Q-2}},$

(where $Q=2n+2$ is the homogeneous dimension).

An important transformation in the Heisenberg group is the Kelvin inversion

$\mathscr{K}:\mathbf{H}\setminus\\{0\\}\to\mathbf{H}\setminus\\{0\\}$

given by

$\mathscr{K}(z,t)=\left(\frac{-iz}{t+i|z|^{2}},-\frac{t}{\rho^{4}}\right).$

$\mathscr{K}$ leaves the unit sphere invariant, but, unlike its analogous on
the Euclidean space, it does not fix the unit sphere pointwise.

We recall the following formulas from [L] for conformal changes of
pseudohermitian metric, to which we refer also for the notation.

######  Proposition 2.1.

If $Z_{1},\ldots,Z_{n}$ are …and $\nabla
Z_{\alpha}=\omega_{\alpha}^{\beta}\otimes Z_{\beta}$ and $\theta^{\alpha}...$,
then, under the conformal change
$\theta\mapsto\widetilde{\theta}=e^{2f}\theta$, the Tanaka-Webster connection
trasforms as

$\widetilde{\omega}_{\alpha}^{\beta}=\omega_{\alpha}^{\beta}+2(f_{\beta}\theta^{\alpha}-f_{\alpha}\theta^{\beta})+\delta_{\alpha}^{\beta}(f_{\gamma}\theta^{\gamma}-f^{\gamma}\theta_{\gamma})+F\cdot\theta$

(where $F$ is a function of $f$ explicitly known, but whose expression is
irrelevant for our purposes).

##  3 The canonical pseudohermitian normal curvature

Let $\Sigma$ be a two-sided hypersurface in $M$ such that $V=\dim(T\Sigma\cap
H(M))=2n-1$ at every point. If $N$ is a normal vector field to $\Sigma$ with
respect to $g_{\theta}$, the normalization of his orthogonal projection on
$H(M)$, $\nu$, is normal to $V$. Let $\xi=-J\nu$. This is a canonical
direction (given an orientation on $\Sigma$). So we define the canonical
pseudohermitian normal curvature of $\Sigma$ as

$\kappa=g_{\theta}(\nabla_{\xi}\xi,\nu).$

######  Proposition 3.1.

Under the conformal change $\theta\mapsto\widetilde{\theta}^{2/n}\theta$,
$\kappa$ the canonical pseudohermitian normal curvature of the new
pseudohermitian metric is given by the formula

$\kappa u-\frac{3}{n}\nu(u)=u^{1+\frac{1}{n}}\widetilde{\kappa}.$

###### Proof.

Let us choose a frame $Z_{1},\ldots,Z_{n}$ for $\mathscr{H}$ such that
$Z_{1}+\overline{Z}_{1}=\xi$ and $Z_{2},\ldots,Z_{n}$ form a frame for
$(T\Sigma\otimes\mathbf{C})\cap\mathscr{H}$. Because of formula (4.2) in [L],
$\omega_{\overline{1}}^{\overline{1}}=-\omega_{1}^{1}$. Then, since
$\nu=i(Z_{1}-\overline{Z}_{1})$,

$\kappa=g_{\theta}(\nabla_{\xi}\xi,\nu)=ig_{\theta}(\nabla_{\xi}Z_{1}+\nabla_{\xi}\overline{Z}_{1},Z_{1}-\overline{Z}_{1})=$
$=ig_{\theta}(\omega_{1}^{\alpha}(\xi)Z_{\alpha}+\omega_{\overline{1}}^{\overline{\alpha}}(\xi)Z_{\overline{\alpha}},Z_{1}-\overline{Z}_{1})=$
$=-i\omega_{1}^{1}(\xi)g_{\theta}(Z_{1},\overline{Z}_{1})-i\omega_{1}^{1}(\xi)g_{\theta}(Z_{1},\overline{Z}_{1})=-i\omega_{1}^{1}(\xi).$

Applying Lee’s formula, since $h_{1\overline{1}}=1$ we obtain that

$\widetilde{\omega}_{1}^{1}=\omega_{1}^{1}+2(f_{1}\theta^{1}-f_{1}\theta^{1})+\delta_{1}^{1}(f_{1}\theta^{1}-f^{1}\theta_{1})+F\cdot\theta=$
$=\omega_{1}^{1}+3(Z_{1}f\theta^{1}+\overline{Z}_{1}f\overline{\theta}^{1})\;\;\;\;\;\;\operatorname{mod}\theta.$

Considering that after the conformal change the Levi form is multiplied by
$e^{2f}$, and so the canonical tangent vector becomes
$\widetilde{\xi}=e^{-f}\xi$, we obtain that

$\widetilde{\kappa}=-i\widetilde{\omega}_{1}^{1}(\widetilde{\xi})=-ie^{-f}(\omega_{1}^{1}+3(Z_{1}f\theta^{1}-\overline{Z}_{1}f\overline{\theta}^{1}))(\xi)=$
$=e^{-f}\kappa-3i(Z_{1}f\theta^{1}-\overline{Z}_{1}f\overline{\theta}^{1}))(Z_{1}+\overline{Z}_{1})=e^{-f}\kappa-3i(Z_{1}-\overline{Z}_{1})f=$
$=e^{-f}\kappa-3\nu(f).$

This concludes the proof. ∎

Recall that the Webster curvature transforms by the formula

$-b_{n}\Delta_{b}u+Wu=\widetilde{W}u^{1+\frac{2}{n}},$

where $b_{n}=2+\frac{2}{n}$. Now let us pick a frame of $H(M)$,
$e_{1},\ldots,e_{2n}$ such that $e_{2n-1}=\xi$, $e_{2n}=\nu$, and such that it
is orthonormal with respect to the Levi form. Let $e^{1},\ldots,e^{2n}$ be the
dual basis thereof. Then, if
$Z_{\alpha}=\frac{1}{2}(e_{2\alpha-1}-ie_{2\alpha})$ and
$\overline{Z}_{\alpha}=\frac{1}{2}(e_{2\alpha-1}+ie_{2\alpha})$, the dual
basis thereof, $\theta^{1},\ldots,\theta^{n}$ is given by the formula
$\theta^{\alpha}=e^{2\alpha-1}+ie^{2\alpha}$. It holds that

$\theta^{\alpha}\wedge\overline{\theta^{\alpha}}=(e^{2\alpha-1}+ie^{2\alpha})\wedge(e^{2\alpha-1}-ie^{2\alpha})=-2ie^{2\alpha-1}\wedge
e^{2\alpha}.$

By the definition of the Levi form we have

$d\theta=i\sum_{\alpha=1}^{n}\theta^{2\alpha-1}\wedge\overline{\theta^{2\alpha}}=i\sum_{\alpha=1}^{n}(e^{2\alpha-1}+ie^{2\alpha})\wedge(e^{2\alpha-1}-ie^{2\alpha})=2\sum_{\alpha=1}^{n}e^{2\alpha-1}\wedge
e^{2\alpha},$

so

$\theta\wedge(d\theta)^{n}=2^{n}\theta\wedge\left(\sum_{\alpha=1}^{n}e^{2\alpha-1}\wedge
e^{2\alpha}\right)^{n}=2^{n}n!\theta\wedge e^{1}\wedge\ldots\wedge
e^{n}=2^{n}n!\operatorname{vol}_{g_{\theta}}.$

We want to give a variational formulation to the problem of the prescription
of the Webster curvature and the prescription of the canonical pseudohermitian
normal curvature on the boundary.

######  Proposition 3.2.

The functional

$Q(v)=\int_{M}(b_{n}|\nabla
v|^{2}+Wv^{2})\theta\wedge(d\theta)^{n}-c_{n}\int_{\partial M}\kappa
v^{2}\sigma\wedge\theta,$

where $c_{n}=\frac{b_{n}}{3}n2^{n}n!$ and $\sigma=e^{1}\wedge
e^{2}\wedge\ldots\wedge e^{2n-1}$, is invariant by the transformation

$\theta\mapsto\widetilde{\theta}=u^{2/n}\theta,\;\;\;v\mapsto\widetilde{v}=vu^{-1}.$

###### Proof.

Under this conformal change $G_{\theta}\mapsto u^{2/n}G_{\theta}$, and so
$\widetilde{\nabla}=u^{-2/n}\nabla$. Therefore

$\int_{M}|\widetilde{\nabla}\widetilde{v}|^{2}\widetilde{\theta}\wedge(d\widetilde{\theta})^{n}=\int_{M}u^{-2/n}|\nabla(u^{-1}v)|^{2}u^{2(n+1)/n}\theta\wedge(d\theta)^{n}=$
$=u^{2}\int_{M}|u^{-1}\nabla v-u^{-2}v\nabla u|^{2}\theta\wedge(d\theta)^{n}=$
$=\int_{M}\left(|\nabla v|^{2}+u^{-2}v^{2}|\nabla u|^{2}-2u^{-1}v\nabla
u\cdot\nabla v\right)\theta\wedge(d\theta)^{n}=$ $=\int_{M}|\nabla
v|^{2}+\int_{M}\left(v^{2}|\nabla\log u|^{2}-\nabla\log
u\cdot\nabla(v^{2})\right)\theta\wedge(d\theta)^{n}=$ $=\int_{M}|\nabla
v|^{2}+\int_{M}v^{2}\left(|\nabla\log u|^{2}+\Delta_{b}\log
u\right)\theta\wedge(d\theta)^{n}-2^{n}n!\int_{\partial
M}v^{2}g_{\theta}(\nabla\log u,\xi)\mathscr{V},$

where $\mathscr{V}$ is the volume form associated to the restiction of
$g_{\theta}$. It is easy to verify that for every $X$ in $H(M)$, the
restriction of $g_{\theta}(\xi,X)\mathscr{V}$ is equal to the restriction of
$e^{2n}(X)\sigma\wedge\theta$. So

$\int_{M}|\widetilde{\nabla}\widetilde{v}|^{2}\widetilde{\theta}\wedge(d\widetilde{\theta})^{n}=$
$=\int_{M}|\nabla v|^{2}+\int_{M}v^{2}\left(|\nabla\log u|^{2}+\Delta_{b}\log
u\right)\theta\wedge(d\theta)^{n}-2^{n}n!\int_{\partial M}v^{2}\nu(\log
u)\sigma\wedge\theta.$

Thanks to the conformal change formula,

$\int_{M}\widetilde{W}\widetilde{v}^{2}\widetilde{\theta}\wedge(d\widetilde{\theta})^{n}=\int_{M}(-b_{n}u^{-1-2/n}\Delta_{b}u+Wu^{-2/n})v^{2}u^{-2}u^{2+2/n}\theta\wedge(d\theta)^{n}=$
$=\int_{M}(-b_{n}u^{-1}\Delta_{b}u+W)v^{2}\theta\wedge(d\theta)^{n}.$

It holds that

$\Delta_{b}\log u=\operatorname{div}(\nabla\log
u)=\operatorname{div}\left(\frac{\nabla
u}{u}\right)=\frac{\Delta_{b}u}{u}-\frac{|\nabla
u|^{2}}{u^{2}}=\frac{\Delta_{b}u}{u}-|\nabla\log u|^{2},$

and so

$\int_{M}\widetilde{W}\widetilde{v}^{2}\widetilde{\theta}\wedge(d\widetilde{\theta})^{n}=\int_{M}Wv^{2}\theta\wedge(d\theta)^{n}-b_{n}\int_{M}(\Delta_{b}\log
u+|\nabla\log u|^{2})v^{2}\theta\wedge(d\theta)^{n}.$

Finally

$\int_{\partial
M}\widetilde{\kappa}\widetilde{v}^{2}\widetilde{\sigma}\wedge\widetilde{\theta}=\int_{\partial
M}\left(u^{-1/n}\kappa-\frac{3}{n}u^{-1-1/n}\nu(u)\right)v^{2}u^{-2}u^{2+1/n}\sigma\wedge\theta=$
$=\int_{\partial M}\kappa v^{2}\sigma\wedge\theta-\frac{3}{n}\int_{\partial
M}\nu(\log u)v^{2}\sigma\wedge\theta.$

By summing the above identities we get the desired result. ∎

One can easily check the following Proposition

######  Proposition 3.3.

A conformal change has Webster curvature $W_{1}$ and canonical pseudohermitian
normal curvature $\kappa_{1}$ if and only if it is a stationary point of the
functional

$I_{W_{1},\kappa_{1}}(v)=Q(v)-\frac{n}{n+1}\int_{M}W_{1}v^{2+2/n}\theta\wedge(d\theta)^{n}+\frac{nc_{n}}{2n+1}\int_{\partial
M}\kappa_{1}v^{2+1/n}\sigma\wedge\theta,$

that is invariant for the same transformation of $Q$.

##  4 Proof of Theorem 1.1

Now that we have a variational and conformally covariant formulation of the
problem of prescribed curvature with boundary conditions, thanks to
Proposition 3.3, we study this problem on suitable annuli, imposing that the
boundary has zero curvature, a natural condition because of the simmetry given
by the Cayley transform. So let us study the problem

$\begin{cases}-b_{n}\Delta_{b}u=u^{1+2/n}\;\;\;\;\text{on}\;\;\;\;A_{r}\\\
-\frac{3}{n}\nu(u)+\kappa_{A_{r}}u=0\;\;\;\;\text{on}\;\;\;\;\partial
A_{r}\end{cases}$

where $A_{r}=B_{r}\setminus\overline{B}_{1}$, and $B_{r}=B_{r}(0)$ with
respect to the Koranyi norm. The latter problem is equivalent to find the
critical points of

$I(v)=b_{n}\int_{M}|\nabla v|^{2}\theta\wedge(d\theta)^{n}-c_{n}\int_{\partial
M}\kappa
v^{2}\sigma\wedge\theta-\frac{n}{n+1}\int_{M}v^{2+2/n}\theta\wedge(d\theta)^{n}.$

We restrict the functional to functions such that $u(x,t)=u(|x|,t)$.

Let us consider the conformal change

$\theta\mapsto\widetilde{\theta}=\rho^{-2}\theta,$

where $\rho=|x|$.

######  Lemma 4.1.

The Webster curvature of $\widetilde{\theta}$ is

$\widetilde{W}=-b_{n}u^{-1-\frac{2}{n}}\Delta_{b}u=-b_{n}\rho^{n+2}\Delta_{b}(\rho^{-n})=b_{n}n^{2}\frac{|x|^{2}}{\rho^{2}},$

and the mean curvature of the boundary of $A_{r}$ is zero.

###### Proof.

We have

$X_{\alpha}(\rho^{4})=\left(\frac{\partial}{\partial
x^{\alpha}}+2y^{\alpha}\frac{\partial}{\partial t}\right)(|x|^{4}+t^{2})=$
$=4(x_{\alpha}^{3}+(|x|^{2}-x_{\alpha}^{2})x_{\alpha}+y_{\alpha}t)=4(|x|^{2}x_{\alpha}+y_{\alpha}t);$

$Y_{\alpha}(\rho^{4})=\left(\frac{\partial}{\partial
y^{\alpha}}-2x^{\alpha}\frac{\partial}{\partial
t}\right)(|x|^{4}+t^{2})=4(|x|^{2}y_{\alpha}-x_{\alpha}t);$

$X_{\alpha}^{2}(\rho^{4})=4\left(\frac{\partial}{\partial
x^{\alpha}}+2y^{\alpha}\frac{\partial}{\partial
t}\right)(x_{\alpha}^{3}+|y_{\alpha}|^{2}x_{\alpha}+y_{\alpha}t)=4(|x|^{2}+2|x_{\alpha}|^{2}+2|y_{\alpha}|^{2});$

$Y_{\alpha}^{2}(\rho^{4})=4\left(\frac{\partial}{\partial
y^{\alpha}}-2x^{\alpha}\frac{\partial}{\partial
t}\right)(y_{\alpha}^{3}+|x_{\alpha}|^{2}y_{\alpha}-x_{\alpha}t)=4(|x|^{2}+2|x_{\alpha}|^{2}+2|y_{\alpha}|^{2}).$

$X_{\alpha}^{2}(\rho^{-n})=X_{\alpha}(X_{\alpha}((\rho^{4})^{-n/4}))=-\frac{n}{4}X_{\alpha}(\rho^{-n-4}X_{\alpha}(\rho^{4}))=$
$=\frac{n(n+4)}{16}\rho^{-n-8}|X_{\alpha}(\rho^{4})|^{2}-\frac{n}{4}\rho^{-n-4}X^{2}_{\alpha}(\rho^{4})=$
$=\frac{n(n+4)}{16}\rho^{-n-8}16(|x|^{2}x_{\alpha}+y_{\alpha}t)^{2}-\frac{n}{4}\rho^{-n-4}4(|x|^{2}+2|x_{\alpha}|^{2}+2|y_{\alpha}|^{2})=$
$=n(n+4)\rho^{-n-8}(|x|^{2}x_{\alpha}+y_{\alpha}t)^{2}-n\rho^{-n-4}(|x|^{2}+2|x_{\alpha}|^{2}+2|y_{\alpha}|^{2}),$

and analogously

$Y_{\alpha}^{2}(\rho^{-n})=n(n+4)\rho^{-n-8}(|x|^{2}y_{\alpha}-x_{\alpha}t)^{2}-n\rho^{-n-4}(|x|^{2}+2|x_{\alpha}|^{2}+2|y_{\alpha}|^{2}),$

so

$\Delta_{b}(\rho^{-n})=\sum_{\alpha=1}^{n}(X_{\alpha}^{2}+Y_{\alpha}^{2})(\rho^{-n})=$
$=n(n+4)\rho^{-n-8}(|x|^{6}+|x|^{2}t^{2})-2n(n+2)\rho^{-n-4}|x|^{2}=-n^{2}\rho^{-n-4}|x|^{2}.$

Since $u=\rho^{-n}$, by formula (2) we get the desired result.

It can be readily verified that the Kelvin transform is isopseudohermitian
with respect to $\widetilde{\theta}$ (that is, it preserves the
pseudohermitian structure). Also the transformations of $\mathbf{H}^{n}$ of
the form $(z,t)\mapsto(Az,t)$ with $A$ unitary, and the dilations, are
isopseudohermitian. So, for every point $x$ of $\partial A_{r}$, there is a
isopseudohermitian transformation that fixes $x$, leaves its component of
$\partial A_{r}$ invariant, but reverses the orientation. Since reversing the
orientation changes sign to $\widetilde{\kappa}$, it follows that
$\widetilde{\kappa}=0$.

Since the Cayley transform is isopseudohermitian with respect to
$\widetilde{\theta}$ (that is, it preserves the pseudohermitian structure),
and that the transformations of $\mathbf{H}^{n}$ of the form
$(z,t)\mapsto(Az,t)$ with $A$ unitary also are, it can be proved by simmetry
that $\widetilde{\kappa}=0$. ∎

Therefore, thanks to Proposition 3.3,

$\widetilde{I}(v)=b_{n}\int_{A_{r}}\left(|\widetilde{\nabla}v|_{\widetilde{\theta}}^{2}+n^{2}\frac{|x|^{2}}{\rho^{2}}v^{2}\right)\widetilde{\theta}\wedge(d\widetilde{\theta})^{n}-\frac{n}{n+1}\int_{A_{r}}v^{2+2/n}\widetilde{\theta}\wedge(d\widetilde{\theta})^{n}.$

We want to impose that the solution is homogeneous and symmetric, in the sense
that $u\circ\delta_{\lambda}=\lambda^{\frac{Q-2}{2}}u$ and $u(x,t)=u(|x|,t)$.

We want to express this functional in suitable coordinates.

######  Lemma 4.2.

If $v=v(|x|,t)$, in the coordinates $l=\frac{1}{n}\log\rho\in\mathbf{R}$,
$\uptau=t/\rho^{2}\in[-1,1]$ and $\gamma=x/|x|\in{\bf S}^{2n-1}$, it holds
that

$|\widetilde{\nabla}v|_{\widetilde{\theta}}^{2}=(1-\uptau^{2})^{3/2}\left|\frac{\partial
v}{\partial\uptau}\right|^{2}+\frac{1}{4n^{2}}(1-\uptau^{2})^{1/2}\left|\frac{\partial
v}{\partial l}\right|^{2}.$

###### Proof.

A transformation of $\mathbf{H}^{n}$ of the form $(x,t)\mapsto(Ax,t)$ with $A$
linear is an isomorphism of the pseudohermitian structure if and only if $A$
is unitary. Since this kind of transformations preserves the sphere of unit
radius, and since the action of the unitary group is transitive between
vectors of the same length, we can calculate
$|\widetilde{\nabla}v|_{\widetilde{\theta}}^{2}$ in the points of the curve

$(\sqrt[4]{1-t^{2}},0,\ldots,0,t).$

At such points

$X_{\alpha}=\frac{\partial}{\partial x_{\alpha}}$

for every $\alpha=1,\ldots,n$,

$Y_{\alpha}=\frac{\partial}{\partial y_{\alpha}}$

for every $\alpha\neq 1$, and

$Y_{1}=\frac{\partial}{\partial
y_{1}}-2\sqrt[4]{1-t^{2}}\frac{\partial}{\partial t}.$

Using the symmetry of $v$ in $x$, we get

$|\widetilde{\nabla}v|_{\widetilde{\theta}}^{2}=v^{-2/n}|\nabla
v|_{\theta}^{2}=\frac{1}{4}|X_{1}u|^{2}+\frac{1}{4}|Y_{1}u|^{2}=$
$=\frac{1}{4}\left|\frac{\partial v}{\partial
x_{1}}\right|^{2}+(1-t)^{1/2}\left|\frac{\partial v}{\partial t}\right|^{2}.$

Since

$\frac{\partial\uptau}{\partial
x_{1}}=-\frac{1}{2}\uptau^{3}\frac{\partial(\uptau^{-2})}{\partial
x_{1}}=-\frac{1}{2}\frac{\uptau^{3}}{t^{2}}\frac{\partial}{\partial
x_{1}}(x_{1}^{4}+t^{2})=-2tx_{1}^{3};$ $\frac{\partial l}{\partial
x_{1}}=\frac{1}{n}\frac{\partial\log\rho}{\partial
x_{1}}=\frac{1}{4n}\frac{\partial\rho^{4}}{\partial
x_{1}}=\frac{1}{n}x_{1}^{3};$ $\frac{\partial\uptau}{\partial
t}=\frac{1}{2}\uptau^{-1}\frac{\partial(\uptau^{2})}{\partial
t}=\frac{1}{2}t^{-1}(2t-2t^{3})=(1-t^{2});$ $\frac{\partial l}{\partial
t}=\frac{1}{4n}\frac{\partial\rho^{4}}{\partial t}=\frac{1}{2n}t,$

we obtain

$|\widetilde{\nabla}v|_{\widetilde{\theta}}^{2}=\frac{1}{4}\left|\frac{\partial
v}{\partial x_{1}}\right|^{2}+(1-t^{2})^{1/2}\left|\frac{\partial v}{\partial
t}\right|^{2}=$ $=\frac{1}{4}\left|-2tx_{1}^{3}\frac{\partial
v}{\partial\uptau}+\frac{x_{1}^{3}}{n}\frac{\partial v}{\partial
l}\right|^{2}+(1-t^{2})^{1/2}\left||x|^{4}\frac{\partial
v}{\partial\uptau}+\frac{t}{2n}\frac{\partial v}{\partial l}\right|^{2}=$
$=t^{2}(1-t^{2})^{3/2}\left|\frac{\partial
v}{\partial\uptau}\right|^{2}+\frac{1}{4n^{2}}(1-t^{2})^{3/2}\left|\frac{\partial
v}{\partial l}\right|^{2}-\frac{1}{n}t(1-t^{2})^{3/2}\frac{\partial
v}{\partial\uptau}\frac{\partial v}{\partial l}+$
$+(1-t^{2})^{5/2}\left|\frac{\partial
v}{\partial\uptau}\right|^{2}+\frac{1}{4n^{2}}t^{2}(1-t^{2})^{1/2}\left|\frac{\partial
v}{\partial l}\right|^{2}+\frac{1}{n}(1-t^{2})^{3/2}t\frac{\partial
v}{\partial\uptau}\frac{\partial v}{\partial l}=$
$=(1-t^{2})^{3/2}\left|\frac{\partial
v}{\partial\uptau}\right|^{2}+\frac{1}{4n^{2}}(1-t^{2})^{1/2}\left|\frac{\partial
v}{\partial l}\right|^{2}.$

By the dilation invariance of $\widetilde{\theta}$ we obtain the formula in
the general case ∎

Now we compute the volume form.

######  Lemma 4.3.

In the coordinates of Lemma 4.2

$\widetilde{\theta}\wedge(d\widetilde{\theta})^{n}=2^{n}n!(1-\uptau^{2})^{(n-2)/2}dl\wedge
d\gamma\wedge d\uptau.$

###### Proof.

The volume form becomes

$\widetilde{\theta}\wedge(d\widetilde{\theta})^{n}=\rho^{-2(n+1)}\theta\wedge(d\theta)^{n}=\frac{2^{n}n!}{\rho^{2(n+1)}}\operatorname{vol}_{g_{\theta}}=\frac{2^{n}n!}{\rho^{2(n+1)}}|x|^{2n-1}d|x|\wedge
d\gamma\wedge dt.$

By an easy computation

$d|x|=\frac{1}{4|x|^{3}}d(\rho^{4}-t^{2})=\frac{1}{4|x|^{3}}d(e^{4ln}(1-\uptau^{2}))=$
$=\frac{1}{4(1-\uptau^{2})^{3/4}e^{3nl}}e^{4ln}(4n(1-\uptau^{2})dl-2\uptau
d\uptau)=$
$=e^{ln}\left(n(1-\uptau^{2})^{1/4}dl-\frac{\uptau}{2(1-\uptau^{2})^{3/4}}d\uptau\right);$
$dt=d(e^{2nl}\uptau)=e^{2nl}(2n\uptau dl+d\uptau);$ $d|x|\wedge
dt=e^{3nl}\frac{1}{(1-\uptau^{2})^{3/4}}dl\wedge d\uptau,$

so

$\widetilde{\theta}\wedge(d\widetilde{\theta})^{n}=-\frac{2^{n}n!}{\rho^{2(n+1)}}(1-\uptau^{2})^{(2n-1)/4}\rho^{2n-1}d|x|\wedge
dt\wedge d\gamma=$
$=-\frac{2^{n}n!}{e^{3nl}}(1-\uptau^{2})^{(2n-1)/4}e^{3nl}\frac{1}{(1-\uptau^{2})^{3/4}}dl\wedge
d\uptau\wedge d\gamma=$ $=2^{n}n!(1-\uptau^{2})^{(n-2)/2}dl\wedge
d\gamma\wedge d\uptau,$

as desired. ∎

Using Lemmas 4.2 and 4.3 we have that

$\widetilde{I}(v)=b_{n}\int_{A_{r}}\left((1-\uptau^{2})^{3/2}\left|\frac{\partial
v}{\partial\uptau}\right|^{2}+\frac{1}{4n^{2}}(1-\uptau^{2})^{1/2}\left|\frac{\partial
v}{\partial l}\right|^{2}v^{2}+\right.$
$\left.+n^{2}(1-\uptau^{2})^{1/2}\right)2^{n}n!(1-\uptau^{2})^{(n-2)/2}dl\wedge
d\gamma\wedge d\uptau+$
$-\frac{n}{n+1}\int_{A_{r}}v^{2+2/n}2^{n}n!(1-\uptau^{2})^{(n-2)/2}dl\wedge
d\gamma\wedge d\uptau=$ $=b_{n}2^{n}n!\int_{0}^{\frac{\log
r}{n}}\int_{-1}^{1}\left((1-\uptau^{2})^{(n+1)/2}\left|\frac{\partial
v}{\partial\uptau}\right|^{2}+\frac{1}{4n^{2}}(1-\uptau^{2})^{(n-1)/2}\left|\frac{\partial
v}{\partial l}\right|^{2}v^{2}+\right.$
$\left.+n^{2}(1-\uptau^{2})^{(n-1)/2}\right)dl\wedge
d\uptau-\frac{n2^{n}n!}{n+1}\int_{0}^{\frac{\log
r}{n}}\int_{-1}^{1}v^{2+2/n}(1-\uptau^{2})^{(n-2)/2}dl\wedge d\uptau.$

If $\uptau=\sin s$, then

$\widetilde{I}(v)=b_{n}2^{n}n!\int_{0}^{\frac{\log
r}{n}}\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}\left(\frac{(\cos s)^{n+1}}{(\cos
s)^{2}}\left|\frac{\partial v}{\partial s}\right|^{2}+\frac{1}{4n^{2}}(\cos
s)^{n-1}\left|\frac{\partial v}{\partial l}\right|^{2}+\right.$
$\left.+n^{2}(\cos s)^{n-1}v^{2}\right)dl(\cos
s)ds-\frac{n2^{n}n!}{n+1}\int_{0}^{\frac{\log
r}{n}}\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}v^{2+2/n}(\cos s)^{n-2}dl(\cos
s)ds=$ $=b_{n}2^{n}n!\int_{0}^{\frac{\log
r}{n}}\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}(\cos
s)^{n}\left(\left|\frac{\partial v}{\partial
s}\right|^{2}+\frac{1}{4n^{2}}\left|\frac{\partial v}{\partial
l}\right|^{2}+n^{2}v^{2}\right)dlds+$
$-\frac{n2^{n}n!}{n+1}\int_{0}^{\frac{\log
r}{n}}\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}v^{2+2/n}(\cos s)^{n-1}dlds.$

Now let us look for homogeneous solutions. Homogeous solutions in the original
setting correspond to solutions invariant by translation (in the $l$
direction), and so let us set $\frac{\partial v}{\partial l}=0$, and $v=v(s)$.
In this special case we have

$\widetilde{I}(v)=b_{n}2^{n}n!\frac{\log
r}{n}\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}(\cos
s)^{n}\left((v^{\prime})^{2}+n^{2}v^{2}\right)ds+$
$-\frac{n2^{n}n!}{n+1}\frac{\log
r}{n}\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}v^{2+2/n}(\cos s)^{n-1}ds.$

The Euler-Lagrange equation for this functional is

$-\frac{d}{ds}((\cos s)^{n}v^{\prime}(s))+n^{2}(\cos
s)^{n}v(s)=\frac{n}{2(n+1)}(\cos s)^{n-1}v(s)^{1+2/n},$

or equivalently

$-\cos sv^{\prime\prime}(s)+n\sin sv^{\prime}(s)+n^{2}\cos
sv(s)=\frac{n}{2(n+1)}v(s)^{1+2/n},$

on the interval $\left(-\frac{\pi}{2},\frac{\pi}{2}\right)$, with Neumann
boundary conditions, that is also the Euler-Lagrange equation (up to
rescaling, thanks to homogeneity) of

$J(v)=\frac{\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}(\cos
s)^{n}\left((v^{\prime})^{2}+n^{2}v^{2}\right)ds}{\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}v^{2+2/n}(\cos
s)^{n-1}ds}.$

Let us define the weighted Sobolev and Lebesgue spaces

$X=\left\\{u\in
H^{1}_{\rm{loc}}\left(-\frac{\pi}{2},\frac{\pi}{2}\right)\;\;\middle|\;\;\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}(\cos
s)^{n}\left((v^{\prime})^{2}+v^{2}\right)ds<\infty\right\\},$ $Y=\left\\{u\in
L^{1}_{\rm{loc}}\left(-\frac{\pi}{2},\frac{\pi}{2}\right)\;\;\middle|\;\;\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}(\cos
s)^{n-1}v^{2+2/n}ds<\infty\right\\}.$

######  Proposition 4.4.

$X$ embeds compactly in $Y$.

###### Proof.

Let $Z$ be the subspace of $H^{1}(S^{n+1})$ formed by functions invariant by
rotation around the last coordinate axis. Every such function is of the form
$v(x)=u(\cos x^{n+2})$, and it is easy to verify thar under such an
identification

$\left\lVert v\right\rVert_{Z}=\left\lVert u\right\rVert_{X}.$

So this is an isometric isomorphism between X and Z. By Rellich-Kondrachov’s
theorem, Z embeds compactly into $L^{p}(S^{n})$ for every
$p\in[1,2\frac{n+1}{n−1})$, which by similar arguments is isometrically
isomorphic to $L^{p}\left((\left(-\frac{\pi}{2},\frac{\pi}{2}\right),(\cos
s)^{n}ds\right)$. Given $\alpha>0$, $q>1$,

$\int_{-\frac{\pi}{2}}^{-\frac{\pi}{2}}(\cos
s)^{n−1}v^{2+2/n}ds=\int_{-\frac{\pi}{2}}^{-\frac{\pi}{2}}\frac{(\cos
s)^{n−1+\alpha}}{(\cos s)^{\alpha}}ds\leq$
$\leq\left(\int_{-\frac{\pi}{2}}^{-\frac{\pi}{2}}v^{(2+2/n)q}(\cos
s)(n−1+\alpha)qds\right)^{1/q}\left(\int_{-\frac{\pi}{2}}^{-\frac{\pi}{2}}(\cos
s)^{−\alpha q^{\prime}}ds\right)^{1/q^{\prime}}.$

If we impose that $(n−1+\alpha)q=n$, then taking $\alpha$ small enough, we can
find that $p=\left(2+\frac{2}{n}q\right)<2\frac{n+1}{n−1}$ and $\alpha
q^{\prime}<n$, getting that

$\int_{-\frac{\pi}{2}}^{-\frac{\pi}{2}}(\cos s)^{n−1}v^{2+2/n}ds\leq
C\int_{-\frac{\pi}{2}}^{-\frac{\pi}{2}}\left(v^{p}(\cos
s)^{n}ds\right)^{1/q},$

that is

$\left\lVert v\right\rVert_{Y}\leq C\left\lVert v\right\rVert_{L^{p}((\cos
s)^{n}ds)},$

and so $L^{p}\left(\left(\frac{\pi}{2},\frac{\pi}{2}\right)(\cos
s)^{n}ds\right)$ embeds into $Y$. So we get the thesis. ∎

Now Theorem 1.1 can be proved, in a standard way, by the direct methods of the
calculus of variation. Since the solution does not depend on $r$, by
homogeneity this defines a solution on the whole
$\mathbf{H}^{n}\setminus\\{0\\}$.

##  5 Proof of Theorem 1.2

Let $\Omega_{t}=\\{1\leq|x|\leq T\\}$ be a cylinder in the Heisenberg group.
In the following, all integrals are meant with respect to the Haar measure and
volume elements will be omitted.

Let

$\mathscr{J}_{T}(u)=\int_{\Omega_{T}}\left(|\nabla_{\mathbf{H}^{n}}u|^{2}-\frac{1}{2^{*}}|u|^{2^{*}}\right)$

be defined on the space

$X_{T}=\left\\{u\in
S^{1}_{\rm{loc}}(\mathbf{H}^{n})\;|\;u\circ\delta_{T}=T^{-\frac{Q-2}{2}}u\right\\},$

where $S^{1}_{\rm{loc}}(\mathbf{H}^{n})$ is the Stein-Folland space (see [F]).
Let $\Psi$ be the homogeneous solution of the PDE

$-\Delta u=u^{2^{*}-1}$

found in the previous section, that is, a stationary point of
$\mathscr{J}_{T}$.

######  Proposition 5.1.

The Morse index of $\mathscr{J}_{T}$ at $\Psi$ is finite and tends to infinity
as $T\to\infty$.

###### Proof.

The Morse index is finite because the operator on $X_{T}$ associated to the
bilinear form

$d^{2}\mathscr{J}_{T}(\Psi)[u,v]=\int_{\Omega_{T}}\left(\nabla u\nabla
v-(2^{*}-1)\Psi^{2^{*}-2}uv\right)$

is of the sum of the identity and a compact operator (thanks to the Rellich-
Kondrachov theorem for the Stein-Folland space).

The signature of a simmetric bilinear form remains invariant passing to the
complexification and extending it to a hermitian form. So let us take

$u(x)=\exp\left(i\frac{1}{M}\log|x|\right)\Psi(x),$

where

$\frac{\log T}{2\pi M}\in\mathbf{Z}.$

Then

$d^{2}\mathscr{J}_{T}(\Psi)[u,u]=\int_{\Omega_{T}}\left(\left|\nabla\left(\exp\left(i\frac{1}{M}\log|x|\right)\Psi\right)\right|^{2}-(2^{*}-1)\Psi^{2^{*}-2}\Psi^{2}\right)=$
$=\int_{\Omega_{T}}\left(\frac{1}{M^{2}|x|^{2}}\Psi^{2}+|\nabla\Psi|^{2}+2\frac{1}{M|x|}\Psi\nabla\Psi\cdot\nabla|x|-(2^{*}-1)\Psi^{2^{*}}\right)=$
$=\int_{\Omega_{T}}\left(\frac{1}{M^{2}|x|^{2}}\Psi^{2}+2\frac{1}{M|x|}\Psi\nabla\Psi\cdot\nabla|x|-(2^{*}-2)\Psi^{2^{*}}\right)=$
$=-(2^{*}-2)\int_{\Omega_{T}}\Psi^{2^{*}}+\int_{\Omega_{T}}\left(\frac{1}{M^{2}|x|^{2}}\Psi^{2}+2\frac{1}{M|x|}\Psi\nabla\Psi\cdot\nabla|x|\right).$

By homogeneity the three integrals

$\int_{\Omega_{T}}\Psi^{2^{*}},\;\;\int_{\Omega_{T}}\frac{1}{|x|^{2}}\Psi^{2},\;\;\int_{\Omega_{T}}\frac{1}{|x|}\Psi\nabla\Psi\cdot\nabla|x|$

are constant multiples of $\log T$, so there exists a constant $C$ such that
if $M\geq C$ then $d^{2}\mathscr{J}_{T}(\Psi)[u,u]$ is negative. Given
$k\in\mathbf{N}$, let $T$ be big enough so that

$\frac{2\pi k}{\log T}\leq\frac{1}{C}.$

Then the functions

$u_{m}(x)=\exp\left(i\frac{2\pi m}{\log T}\log|x|\right)\Psi(x)$

with $m=1,\ldots,k$, are such that
$d^{2}\mathscr{J}_{T}(\Psi)[u_{m},u_{m}]\leq-\varepsilon\log T$ is negative.
If $f$ is a homogeneous function of degree zero and $m\neq 0$ then

$\int_{\Omega_{T}}\exp\left(i\frac{2\pi m}{\log
T}\log|x|\right)\frac{f(x)}{|x|^{Q}}=\int_{S_{1}}d\sigma
f\int_{1}^{T}dr\frac{\exp\left(i\frac{2\pi m}{\log T}\log r\right)}{r}=0.$

When calculating

$d^{2}\mathscr{J}_{T}(\Psi)[u_{m},u_{j}]$

with $m\neq j$, the result is a sum of terms of this kind, so it is zero. So
the functions $u_{m}$ span a vector space of dimension $k$ on which
$d^{2}\mathscr{J}_{T}(\Psi)$ is negative definite. ∎

In order to apply bifurcation theory, let us rewrite the functional with
respect to the pseudohermitian form given by the conformal change
corresponding to $\Psi$. So we get the functional

$\widetilde{\mathscr{J}}_{T}(u)=\int_{\Omega_{T}}\left(|\widetilde{\nabla}_{\mathbf{H}^{n}}u|^{2}+\frac{1}{2}u^{2}-\frac{1}{2^{*}}|u|^{2^{*}}\right),$

defined on the space

$Y_{T}=\left\\{u\in
S^{1}_{\rm{loc}}(\mathbf{H}^{n})\;|\;u\circ\delta_{T}=u,\;\;\int_{\Omega_{T}}u=0\right\\}.$

Let $\Sigma$ be the sphere with respect to the Euclidean metric 222this is
necessary to perform the next steps of the proofs because the sphere with
respect to the Heisenberg metric is not smooth. Let $\phi_{k}$ be a complete
set in $L^{2}(\Sigma)$ consisting of analytic functions. So

$\gamma_{k,m,T}(x)=\phi_{k}\left(\frac{x}{|x|_{\rm{eucl}}}\right)\sin\left(i\frac{2\pi
m}{\log T}\log|x|_{\rm{eucl}}\right)$

is a complete set of functions in $H^{1}(\Omega_{T})$, analytic with respect
to the couple $(x,T)$. SO it is complete also in $S^{1}(\Omega_{T})$. With the
Gram-Schmidt algorithm, we can obtain a family of Hilbert bases $\psi_{k,T}$
of $S^{1}(\Omega_{T})$, and preserve the analyticity property. Let us define
the isometry $\Psi_{T}$ between $Y_{T}$ and $Y_{2}$ obtained sending
$\psi_{k,T}$ into $\psi_{k,2}$. Let us call

$L_{T}=\Psi_{T}\circ\widetilde{\mathscr{J}}^{\prime\prime}_{T}(1)\circ\Psi_{T}^{-1}.$

Then, for every $l,k$,

$\left\langle
L_{T}u_{2,k},u_{2,k}\right\rangle_{Y_{2}}=\left\langle\widetilde{\mathscr{J}}^{\prime\prime}_{T}(1)u_{k,T},u_{l,T}\right\rangle_{Y_{T}}=$
$=\int_{\Omega_{T}}\widetilde{\nabla}u_{k,T}\widetilde{\nabla}u_{l,T}+u_{k,T}u_{l,T}-(2^{*}-1)u_{k,T}u_{l,T}.$

It is an analytic function by the following lemma of immediate proof.

######  Lemma 5.2.

If $S:I\to X$, $T:I\to Y$ are two analytic vector valued functions and
$L:X\times Y\to Z$ is a bilinear continuous form, then $t\mapsto B(S(t),T(t))$
is analytic.

So $L_{T}$ is an analytic operator-valued function.

It holds that

$\left\langle\widetilde{\mathscr{J}}^{\prime\prime}_{T}(1)u,v\right\rangle=\int_{\Omega_{T}}\widetilde{\nabla}u\widetilde{\nabla}v+uv-(2^{*}-1)uv=\int_{\Omega_{T}}\widetilde{\nabla}u\widetilde{\nabla}v-(2^{*}-2)\Delta(G_{T}u)v=$
$=\int_{\Omega_{T}}\widetilde{\nabla}u\widetilde{\nabla}v+(2^{*}-2)\widetilde{\nabla}(G_{T}u)\widetilde{\nabla}v,$

where $G_{T}:Y_{T}\to Y_{T}$ is the Green’s operator, so

$\widetilde{\mathscr{J}}^{\prime\prime}_{T}(1)=I+(2^{*}-2)G_{T}.$

Since $L_{T}$ is, by definition, conjugated to
$\widetilde{\mathscr{J}}^{\prime\prime}_{T}(1)$, it is of the form $I-K(T)$,
where $K(T)$ is an analytic operator-valued function of compact operators.

Now, by means of known results in bifurcation theory, we can prove Theorem
1.2.

###### Proof of Theorem 1.2.

It suffices to apply Theorem 8.9 in [MW]. In our case the hypotheses of that
Theorem are all either trivial or standardly verifiable, with exception of
hypothesis $\gamma$, that is consequence of Corollary 8.3 in the same book. ∎

## References

  * [Af] Afeltra, Claudio, Singular periodic solutions to a critical equation in the Heisenberg group, Pacific J. Math. 305 (2020), no. 2, 385–406.
  * [A] Aubin, Thierry, Some nonlinear problems in Riemannian geometry Springer Monographs in Mathematics. Springer-Verlag, Berlin, 1998. xviii+395 pp.
  * [CGS] Caffarelli, Luis A.; Gidas, Basilis; Spruck, Joel, Asymptotic symmetry and local behavior of semilinear elliptic equations with critical Sobolev growth. Comm. Pure Appl. Math. 42 (1989), no. 3, 271–297.
  * [CL] Chen, Chiun-Chuan; Lin, Chang-Shou, Estimate of the conformal scalar curvature equation via the method of moving planes. II. J. Differential Geom. 49 (1998), no. 1, 115–178.
  * [CHMY] Cheng, Jih-Hsin, Hwang, Jenn-Fang, Malchiodi, Andrea, Yang, Paul, Minimal surfaces in pseudohermitian geometry, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 4 (2005), no. 1, 129–177.
  * [CMY] Cheng, Jih-Hsin; Malchiodi, Andrea; Yang, Paul, A positive mass theorem in three dimensional Cauchy-Riemann geometry. Adv. Math. 308 (2017), 276–347.
  * [DT] Dragomir, Sorin; Tomassini, Giuseppe Differential geometry and analysis on CR manifolds, Progress in Mathematics, 246. Birkhäuser Boston, Inc., Boston, MA, 2006. xvi+487 pp.
  * [E] Escobar, José F., The Yamabe problem on manifolds with boundary, J. Differential Geom. 35 (1992), no. 1, 21–84.
  * [F] Folland, G. B., Subelliptic estimates and function spaces on nilpotent Lie groups, Ark. Mat. 13 (1975), no. 2, 161–207.
  * [Gam] Gamara, Najoua, The CR Yamabe conjecture—the case n=1. J. Eur. Math. Soc. (JEMS) 3 (2001), no. 2, 105–137.
  * [GY] Gamara, Najoua; Yacoub, Ridha; CR Yamabe conjecture—the conformally flat case. Pacific J. Math. 201 (2001), no. 1, 121–175.
  * [JL] Jerison, David; Lee, John M., Extremals for the Sobolev inequality on the Heisenberg group and the CR Yamabe problem. J. Amer. Math. Soc. 1 (1988), no. 1, 1–13.
  * [JL2] Jerison, David; Lee, John M.; The Yamabe problem on CR manifolds., J. Differential Geom. 25 (1987), no. 2, 167–197.
  * [KMPS] Korevaar, Nick; Mazzeo, Rafe; Pacard, Frank; Schoen, Richard, Refined asymptotics for constant scalar curvature metrics with isolated singularities. Invent. Math. 135 (1999), no. 2, 233–272.
  * [L] Lee, John M.; The Fefferman metric and pseudo-Hermitian invariants, Trans. Amer. Math. Soc. 296 (1986), no. 1, 411–429.
  * [Li1] Li, Yan Yan Prescribing scalar curvature on Sn and related problems. I. J. Differential Equations 120 (1995), no. 2, 319–410.
  * [Li2] Li, Yanyan Prescribing scalar curvature on Sn and related problems. II. Existence and compactness. Comm. Pure Appl. Math. 49 (1996), no. 6, 541–597.
  * [MW] Mawhin, Jean, Willem, Michel, Critical point theory and Hamiltonian systems, Applied Mathematical Sciences, 74. Springer-Verlag, New York, 1989. xiv+277 pp.


# Complexity of Simon’s problem in classical sense

Hans Zantema
Eindhoven University of Technology, The Netherlands
email<EMAIL_ADDRESS>
Radboud University Nijmegen, The Netherlands

###### Abstract

Simon’s problem is a standard example of a problem that is exponential in
classical sense, while it admits a polynomial solution in quantum computing.
It is about a function $f$ for which it is given that a unique non-zero vector
$s$ exists for which $f(x)=f(x\oplus s)$ for all $x$, where $\oplus$ is the
exclusive or operator. The goal is to find $s$. The exponential lower bound
for the classical sense assumes that $f$ only admits black box access. In this
paper we investigate classical complexity when $f$ is given by a standard
representation like a circuit. We focus on finding the vector space of all
vectors $s$ for which $f(x)=f(x\oplus s)$ for all $x$, for any given $f$. Two
main results are: (1) if $f$ is given by any circuit, then checking whether
this vector space contains a non-zero element is NP-hard, and (2) if $f$ is
given by any ordered BDD, then a basis of this vector space can be computed in
polynomial time.

##  1 Introduction

Simon’s problem [7] is the following. A function
$f:\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ is given with the particular property that
exactly one non-zero $s\in\\{0,1\\}^{n}$ exists such that $f(x\oplus s)=f(x)$
for all $x\in\\{0,1\\}^{n}$, where $\oplus$ stands for the exclusive or
operation on each of the $n$ coordinates. The goal is to find $s$. Although
the problem itself is purely artificial, it is of interest for the following
reason. When $f$ is a black box function, that is, the only access to $f$ is
by doing queries: apply $f$ on a given input and observe the output, the worst
case complexity to find $s$ in the classical sense is exponential in $n$. A
basic observation is that as soon as two distinct values $x,y$ are found with
$f(x)=f(y)$ then $s=x\oplus y$, but finding such $x,y$ may take exponential
time. On the other hand, a quantum circuit can be designed that solves the
problem in linear time [7]. In this way Simon’s problem has become a standard
example showing that quantum computing may be exponentially faster than
classical computing.

For this exponential gap it is crucial that $f$ is purely black box: nothing
is known about how $f$ is computed. In contrast, in this paper we assume that
$f$ is given by some standard representation, and we investigate the
corresponding classical complexity of Simon’s problem. Before discussing the
particular representations we give a general observation on information
content. For any non-zero $s\in\\{0,1\\}^{n}$ we can construct $2^{2^{n-1}}$
distinct functions $f$ having the required property as follows. Let
$i\in\\{1,\ldots,n\\}$ such that $s_{i}=1$. Let
$f_{1}:\\{x\in\\{0,1\\}^{n}\mid x_{i}=0\\}\to\\{0,1\\}^{n}$ be arbitrary, and
define $f(x)=f_{1}(x)$ if $x_{i}=0$ and $f(x)=f_{1}(x\oplus s)$ if $x_{i}=1$,
note that $(x\oplus s)_{i}=0$ if both $s_{i}=1$ and $x_{i}=1$. Now $f$
satisfies the required property. For every $s$ there are $2^{2^{n-1}}$
distinct functions $f_{i}$ all yielding distinct functions $f$ with the
required property. Hence in any representation an arbitrary instance of such
$f$ will require at least $\log(2^{2^{n-1}})$ bits on average, being of
exponential size. It makes sense to consider cases for which an algorithm to
compute $f$ is given, and is of less than exponential size.

A standard way to implement any function $f:\\{0,1\\}^{n}\to\\{0,1\\}^{m}$ is
by a circuit: an acyclic network starting by $n$ input nodes, and in which
values of internal nodes are computed by the standard boolean operators
$\neg$, $\vee$, $\wedge$. Eventually, $m$ resulting nodes serve as the output
nodes, where $m=n$ in case of Simon’s problem. A natural question now is: when
$f$ is given by such a circuit, how hard is it to solve Simon’s problem? A
standard measure for hardness is being NP-hard. However, that is about
decision problems, that is, problems with a binary answer as output, and here
the question is to find a vector $s$. A natural way to construct $s$ by a
series of decision queries is by first putting $s_{1}$ to 0, and then ask
whether in the remaining problem on $s_{2},\ldots,s_{n}$ admits an answer on
Simon’s problem. If it does, then $s_{1}$ is defined to be 0, otherwise
$s_{1}$ is defined to be 1: from the fact that $s$ exists and no $s$ satisfies
$s_{1}=0$ indeed $s_{1}=1$ may be concluded. This is repeated for
$s_{2},s_{3},\ldots$ until the full vector $s$ has been determined. So the key
decision problem in this approach is: given any boolean function $f$, does
there exist $s$ such that $f(x\oplus s)=f(x)$ for all $x$? One main result of
this paper is that this decision problem is NP-hard. Note that NP-hardness of
this natural building block does not prove NP-hardness of Simon’s problem
itself, since this approach does not exploit the given property that a
corresponding non-zero $s$ uniquely exists.

A special kind of circuit is a reduced ordered binary decision diagram
(ROBDD). A key property is that every boolean function has a unique
representation as an ROBDD, and that’s one of the reasons that ROBDDs provide
a standard data structure in symbolic model checking, VLSI design, and many
other applications. A second main result of this paper is that if $f$ is given
by an ROBDD, then Simon’s problem can be solved in polynomial time. In fact
reducedness is not used here, so the results holds for any ordered BDD.

The paper is organized as follows. First in Section 2 we give some
preliminaries: we formulate Simon’s problem in terms of vector spaces over the
Boolean domain. Next in Section 3 we present our NP-hardness result for $f$
being presented by a circuit. Finally, in Section 4 we present our polynomial
algorithm for $f$ being presented as an ordered BDD.

##  2 Preliminaries

We write ${\bf B}=\\{0,1\\}$ for the Booleans, where $0,1$ are identified with
false, true. The exclusive or operation (usually denoted by $\oplus$) we
denote by $+$, as it coincides with additional modulo 2. So $0+0=1+1=0$,
$0+1=1+0=1$. For any $x,y\in{\bf B}^{n}$ we write
$x+y=(x_{1}+y_{1},x_{2}+y_{2},\ldots,x_{n}+y_{n})$ for
$x=(x_{1},\ldots,x_{n})$ and $y=(y_{1},\ldots,y_{n})$.

For any function $f:{\bf B}^{n}\to{\bf B}^{m}$ we define

$V(f)=\\{s\in{\bf B}^{n}\mid\forall x\in{\bf B}^{n}:f(x+s)=f(x)\\}.$

With $+$ as addition and $\wedge$ as multiplication, ${\bf B}$ is a field. It
is straightforward to check that for any function $f:{\bf B}^{n}\to{\bf
B}^{m}$ the set $V(f)$ is a vector space over ${\bf B}$, that is,
$\overline{0}=(0,0,\ldots,0)\in V(f)$, and $a+b\in V(f)$ for all $a,b\in
V(f)$. We recall some basic notions and properties of such a vector space [4]:

  * •

The size of any vector space $V\subseteq{\bf B}^{n}$ is $2^{k}$ for some $k$
satisfying $0\leq k\leq n$; this number $k$ is called the dimension of $V$.

  * •

A set $A\subseteq{\bf B}^{n}$ is called linearly independent if no non-empty
subset of $A$ has sum $\overline{0}$.

  * •

A set $A\subseteq V$ is called a basis of the vector space $V$ if it is
linearly independent and every element of $V$ can be written as a sum of
elements of $A$. Due to linear independence this representation is unique, in
particular $\overline{0}$ is uniquely written as the empty sum.

  * •

For a vector space of dimension $k$ every basis has exactly $k$ elements.

  * •

A vector space $V$ is of dimension 0 if and only if $V=\\{\overline{0}\\}$. A
vector space $V$ is of dimension 1 if and only if $V=\\{\overline{0},s\\}$ for
some $s\in{\bf B}^{n}\setminus\\{\overline{0}\\}$.

So Simon’s problem can be formulated as follows: given $f:{\bf B}^{n}\to{\bf
B}^{n}$ for which $V(f)$ has dimension 1, find $s\neq\overline{0}$ such that
$V(f)=\\{\overline{0},s\\}$.

Such a function $f:{\bf B}^{n}\to{\bf B}^{m}$ can be seen as an $m$-tuple
Boolean functions $f_{1},\ldots,f_{m}:{\bf B}^{n}\to{\bf B}$, where
$f(x)=(f_{1},\ldots,f_{m})$ for every $x\in{\bf B}^{n}$. From the definition
of $V(f)$ it is clear that $V(f)=\bigcap_{i=1}^{m}V(f_{i})$. So Simon’s
problem can be reformulated as follows: given $f:{\bf B}^{n}\to{\bf B}^{n}$
for which $V(f)$ has dimension 1, find $s\neq\overline{0}$ such that
$s\in\bigcap_{i=1}^{m}V(f_{i})$.

##  3 Representing functions by circuits

A natural way to represent a function $f:{\bf B}^{n}\to{\bf B}^{m}$ is by a
circuit with $n$ input nodes and $m$ output nodes, and several internal nodes
of which the (boolean) values are computed by logical gates in an acyclic way.
Conceptually this is the same as stating that every output is a logical
formula composed from the operators $\neg$, $\vee$ and $\wedge$ and $n$
variables representing the input nodes, while in computing the size of such a
logical formula we allow equal subformulas to be shared. So we represent
circuits as being formulas, one formula for every output node. For instance,
the following circuit with three input nodes $x_{1},x_{2},x_{3}$ and two
output nodes $f_{1},f_{2}$ represents the function $f:{\bf B}^{3}\to{\bf
B}^{2}$ defined by

$f(x_{1},x_{2},x_{3})=((x_{1}\wedge x_{2})\vee\neg((x_{1}\wedge x_{2})\wedge
x_{3}),\neg((x_{1}\wedge x_{2})\wedge x_{3})\wedge\neg(x_{2}\vee x_{3})).$

$\wedge$$\vee$$\wedge$$\neg$$\neg$$f_{1}$$f_{2}$$\vee$$\wedge$$x_{1}$$x_{2}$$x_{3}$

The exclusive or operator $+$ may also be used in formulas, where $p+q$ may be
seen as an abbreviation of $(p\wedge\neg q)\vee(\neg p\wedge q)$, in which in
the circuit the instances of $p$ are shared, and similarly for $q$.

A circuit with $n$ input nodes and one output node is called satisfiable if it
is possible to give Boolean values to the input nodes such that the output
node yields true. It is well-known [3] that checking satisfiability of such a
circuit is NP-complete, that is, the problem is in NP and it is NP-hard.

The goal of this section is to investigate the hardness of Simon’s problem in
case the function $f:{\bf B}^{n}\to{\bf B}^{n}$ is given by a circuit with $n$
input nodes and $n$ output nodes. Taking each of the $n$ output nodes
separately, this can be seen as $n$ circuits for the functions
$f_{1},\ldots,f_{n}$, each having one output node, and the goal is to find
$s\in\bigcap_{i=1}^{m}V(f_{i})$. One problem about stating NP-hardness is that
Simon’s problem is about finding this Boolean vector $s$, while the notion of
NP-hardness is about decision problems: problems with only a yes/no answer. A
natural approach to find the vector $s=(s_{1},\ldots,s_{n})$ by a series of
calls to a decision problem is as follows. First replace $s_{1}$ by 0, and
then check whether $s=(0,s_{2},\ldots,s_{n})\neq\overline{0}$ exists in
$V(f)$. If so, we fix $s_{1}$ to 0, otherwise we know that by the assumption
that $s\neq\overline{0}$ exists such that $s\in V(f)$ we may fix $s_{1}$ to 1.
Next we do the same for $s_{2}$, and continue until $s=(s_{1},\ldots,s_{n})$
has been determined completely. In this approach we apply SIMCIRC
consecutively for values $n-1,n-2,\ldots$, for SIMCIRC defined as follows:

> (SIMCIRC ) Given a circuit with $n$ input nodes and one output node, does
> there exist $s\neq\overline{0}$ such that $s\in V(f)$, for $f$ being the
> function $f:{\bf B}^{n}\to{\bf B}$ defined by the circuit?

We will prove that SIMCIRC is NP-hard. The key idea is to define a circuit
$F(C)$ for any arbitrary single output circuit $C$ such that $C$ is
unsatisfiable if and only if this SIMCIRC question yields true for the circuit
$F(C)$. Let $n$ be the number of inputs of $C$, let $p_{1},\ldots,p_{n}$ be
the $n$ variables corresponding to the $n$ input nodes of $C$. In order to
define the transformation $F$ we introduce $n+1$ fresh variables
$p,q_{1},\ldots,q_{n}$. We define $h(C)$ to be a copy of $C$ in which every
variable $p_{i}$ has been replaced by $p_{i}\wedge q_{i}$, and we define
$D=(\bigwedge_{i=1}^{n}p_{i})\wedge(\bigwedge_{i=1}^{n}\neg q_{i})$. Now
$F(C)$ is defined by

$F(C)\;=\;(p\vee(h(C)+D))\wedge(\neg p\vee D).$

A main observation is that if $C$ is unsatisfiable, then $F(C)$ does not
depend on $p$, yielding some $s\neq\overline{0}$ such that $s\in V(f)$, being
one direction of the desired key property of $F(C)$. The ingredients $h(C)$
and $D$ of the definition of $F$ are chosen in order to be able to prove the
reverse direction.

Now NP-hardness of SIMCIRC is an immediate consequence of the following
theorem, combined with the observation that $F$ is polynomial.

###### Theorem 1

Let $C$ be an arbitrary circuit with $n$ inputs and one output. Then $C$ is
unsatisfiable if and only if there exists $s\neq\overline{0}$ such that $s\in
V(f)$, for $f$ being the function $f:{\bf B}^{2n+1}\to{\bf B}$ defined by the
circuit $F(C)$.

Proof: First assume that $C$ is unsatisfiable. Then both $C$ and $h(C)$ are
equivalent to false, and $h(C)+D$ is equivalent to $D$, and also $F(C)$ is
equivalent to $D$. Let $s\neq\overline{0}$ be the input vector in which $p$ is
true and all other variables $p_{i},q_{i}$ are false. Then $x+s$ is a copy of
$x$ in which the value of $p$ is swapped, while the values of all other
variables are kept. As $F(C)\equiv D$ and $p$ does not occur in $D$, we obtain
$s\in V(f)$, proving the ’only if’ part of the theorem.

Conversely, assume that $s\in V(f)$ for some $s\neq\overline{0}$, that is,
$s\in{\bf B}^{2n+1}$ and $F(C)(x)=F(C)(x+s)$ for all $x\in{\bf B}^{2n+1}$. We
have to prove that $C$ is unsatisfiable, that is, equivalent to false. We
consider two cases depending on the value of $s_{p}$, where $s_{p}$ is the
coordinate of $s\in{\bf B}^{2n+1}$ corresponding to the variable $p$.

(1) First assume that $s_{p}$ is false. Choose an arbitrary $x\in{\bf
B}^{2n+1}$ such that $x_{p}=1$, hence also $x_{p}+s_{p}=1$. Then
$D(x)=F(C)(x)=F(C)(x+s)=D(x+s)$. Note that
$D=(\bigwedge_{i+1}^{n}p_{i})\wedge(\bigwedge_{i+1}^{n}\neg q_{i})$, and
$D(x+s)=D^{\prime}(x)$ for $D^{\prime}$ obtained from $D$ by replacing at
least one of the variables $p_{i},q_{i}$ by its negation. As this holds for
every $x\in{\bf B}^{2n+1}$ for which $x_{p}$ is true, we obtain that $D$ and
$D^{\prime}$ are equivalent, contradiction.

(2) Next assume the remaining case in which $s_{p}$ is true. Choose an
arbitrary $x\in{\bf B}^{2n+1}$ with $x_{p}$ is false. Then
$h(C)(x)+D(x)=F(C)(x)=F(C)(x+s)=D(x+s)$. So $h(C)(x)=D(x)+D(x+s)$. We consider
$h(C)$ and $D$ as circuits over $p_{1},\ldots,p_{n},q_{1},\ldots,q_{n}$, and
have to prove that $h(C)$ is unsatisfiable. If it is not, then we can choose
$x$ such that $h(C)(x)=D(x)+D(x+s)=1$. That is, $D(x)=1$ and $D(x+s)=0$, or
conversely. In the latter case we replace $x$ by $x+s$. So without loss of
generality we may assume that $D(x)=1$ and $D(x+s)=0$. From $D(x)=1$ and the
definition of $D$ we conclude $x_{p_{i}}=1$ and $x_{q_{i}}=0$ , for all
$i=1,\ldots,n$. Now we modify $x$ to $x^{\prime}$ and $x^{\prime\prime}$ as
follows.

$x^{\prime}_{p_{1}}=0,\;x^{\prime}_{q_{1}}=0,\;x^{\prime\prime}_{p_{1}}=0,\;x^{\prime\prime}_{q_{1}}=1,\;x^{\prime}_{p_{i}}=x^{\prime\prime}_{p_{i}}=1,x^{\prime}_{q_{i}}=x^{\prime\prime}_{q_{i}}=0\mbox{
for $i>1$}.$

Since $h(C)$ only depends on $p_{i}\wedge q_{i}$, and the value of
$p_{i}\wedge q_{i}$ does not change by replacing $x$ by
$x^{\prime},x^{\prime\prime}$, both $h(C)(x^{\prime})$ and
$h(C)(x^{\prime\prime})$ yield true just like $h(C)(x)$. Since
$h(C)(x^{\prime})=D(x^{\prime})+D(x^{\prime}+s)=1$ and $D(x^{\prime})=0$, we
obtain $D(x^{\prime}+s)=1$. Similarly we obtain $D(x^{\prime\prime}+s)=1$. But
now we have two distinct boolean vectors $x^{\prime}+s$ and
$x^{\prime\prime}+s$ for which $D$ both yield true, contradicting the
definition of $D$.

$\Box$

In our version of SIMCIRC we considered functions of which the output is a
single boolean. But this generalizes easily: the same result is obtained for
functions $f:{\bf B}^{n}\to{\bf B}^{m}$ for a fixed $m$, or functions $f:{\bf
B}^{n}\to{\bf B}^{n}$ as they occur in Simon’s problem, simply by taking
multiple output circuits in which all outputs are equal.

Although SIMCIRC seems to be a natural building block for solving Simon’
problem, Theorem 1 does not prove that Simon’s problem itself is NP-hard. A
main observation is that in using SIMCIRC to solve Simon’s problem, the given
fact that $V(f)$ contains a unique $s\neq\overline{0}$ is not exploited.
However, by using this unicity, the problem is in the class UP [8]
(unambiguous polynomial) rather than in NP, and UP-complete problems are not
known.

##  4 BDDs

A standard data structure for representing boolean functions is given by BDDs:
boolean decision diagrams. Introduced in [1], they have several applications
in, e.g., symbolic model checking and VLSI design ([6, 2]). Surprisingly, they
can be presented as a special instance of circuits by adding additional
operators. For every variable $p$ we introduce an additional binary operator,
also denoted by $p$ in a prefix notation to be used in circuits / formulas, in
which the meaning of $p(A,B)$ is defined to be $(\neg p\vee A)\wedge(p\vee
B)$. Intuitively, the meaning of $p(A,B)$ is: if $p$ then $A$ else $B$. It is
straightforward to see that the notion of BDD as introduced in [1, 6, 2]
coincides with a circuit only composed from false, true, and the operators $p$
for $p$ running over all variables. Hence here we identify BDDs with such
circuits. A BDD is called reduced if it is optimally shared, that is, no two
distinct nodes represent the same boolean function. A BDD is called ordered
with respect to a total order $<$ on the variables if for every node of the
form $p(A,B)$, the nodes $A,B$ are false, true, or of the form $q(-,-)$ with
$p<q$. So for every node in an ordered BDD all nodes below are larger. The
notion of reduced ordered BDD is abbreviated to ROBDD. A key property of
ROBDDs is unicity, see e..g, [6], Cor 6.12:

> For a fixed order $<$ on variables, every boolean function on these
> variables has a unique representation as ROBDD with respect to $<$.

For our result this uniqueness and being reduced does not play a role, but
being ordered does. So we will focus on ordered BDDs.

An example of an ROBDD on the variables $p,q,r$ with respect to the order
$p<q<r$ is given on the right; later on we will use it to illustrate our main
algorithm. The top node is the output. To compute the value of the
corresponding boolean function we start at this top node. For every node we go
to the left if the value of the corresponding variable is true, and to the
right if this value is false, following the if-then-else meaning of the nodes.
This is continued until one of the leaves 0 or 1 is reached. If it is 0, then
the function result is false, if it is 1 then the function result is true.

$p$$q$$q$$r$$r$$0$$1$

We may also consider BDDs with multiple output nodes, representing functions
${\bf B}^{n}\to{\bf B}^{m}$, where $n$ is the number of variables and $m$ is
the number of output nodes. Just like in any circuit, every node represents a
function ${\bf B}^{n}\to{\bf B}$.

Any BDD corresponds to a classical circuit representing the same function,
obtained by expanding every occurrence of $p(A,B)$ by $(\neg p\vee
A)\wedge(p\vee B)$. In contrast to arbitrary circuits for which we showed that
even the basic question whether $V(f)$ contains a non-zero vector is already
NP-hard, for ordered BDDs this turns out to be feasible in polynomial time.
Not only this decision question is feasible, even computing a full basis, not
only for ordered BDDs with a single output node, but also for any number of
output nodes. For doing so, we need some standard algorithms from linear
algebra:

  * •

When two vector spaces are given by a basis of each of them, a basis of the
intersection of the vector spaces can be computed by the standard Zassenhaus
algorithm in polynomial time, see [5].

  * •

Exploiting this algorithm, if $V,W$ are vector spaces and $v,w$ are vectors,
then it can be checked whether $v+V\cap w+W$ is empty, and if not, an element
in $v+V\cup w+W$ can be determined. All of this in polynomial time.

For presenting the algorithm we need the notion $V(T,U)$ for $T,U$ being nodes
in an ordered BDD, defined as follows:

$V(T,U)=\\{s\mid T(x)=U(x+s)\mbox{ for all $x$}\\}.$

It satisfies the following properties.

###### Lemma 2

For every two nodes $T,U$ in an ordered BDD we have

  1. 1.

$V(T,U)=V(U,T)$.

  2. 2.

If $T,U$ are labeled by distinct variables, then $V(T,U)=\emptyset$.

  3. 3.

If $s\in V(T,U)$ then $V(T)=V(U)$ and $V(T,U)=s+V(T)$.

Proof: 1 and 3 directly follow from the definitions. For 2 let $T$ and $U$ be
labeled by distinct variables, and assume $s\in V(T,U)$. Then one among $T,U$
depends on the smaller of these two variables while the other does not,
contradicting $T(x)=U(x+s)$ for all $x$. $\Box$

###### Theorem 3

For an ordered BDD with respect to any order $<$, representing a boolean
function $f:{\bf B}^{n}\to{\bf B}^{m}$, there is an algorithm that computes a
basis for the vector space $V(f)$ in time polynomial in the size of the BDD.

Proof: Let $p_{1}<p_{2}<\cdots<p_{n}$ be the $n$ variables. We identify each
node $T$ of the BDD by the boolean function it represents. The algorithm runs
over all nodes labeled by $p_{i}$, for $i$ running down from $n$ to 1, and
controlled by Lemma 2 it computes

  1. 1.

whether $V(T,U)$ is empty for every two nodes $T,U$ labeled by $p_{i}$, and if
not then it computes an element $s_{TU}\in V(T,U)$;

  2. 2.

a basis of $V(T)$ for every node $T$ labeled by $p_{i}$.

As $T$ labeled by $p_{i}$ only depends on $p_{i},p_{i+1},\ldots,p_{n}$, $V(T)$
is considered as a subspace of the corresponding $n-i+1$-dimensional vector
space.

As the computation is done for $i$ running down from $n$ to 1, during the
process a node labeled by $p_{i}$ is considered when a basis of $V(T)$ has
been computed already for all nodes $T$ with label $p_{j}$, $j>i$, and for all
nodes with label $>p_{i}$ the corresponding vectors $s_{TU}$ are known.

First for any two distinct nodes $T,U$ labeled by $p_{i}$ a vector $s_{TU}\in
V(T,U)$ is computed if it exists. Let $T=p_{i}(T_{1},T_{2})$ and
$U=p_{i}(U_{1},U_{2})$. For the new coordinate of $s_{TU}$ corresponding to
the variable $p_{i}$ there are two options: either 0 or 1. First consider
adding 0. Then both $V(T_{1},U_{1})$ and $V(T_{2},U_{2})$ should be non-empty,
and $s_{T_{1}U_{1}}\in V(T_{1},U_{1})$ and $s_{T_{2}U_{2}}\in V(T_{2},U_{2})$
have been computed already. In case the root of $T_{1}$ is $p_{i+1}$ then
$s_{T_{1}U_{1}}$ has the right dimension, if it is $p_{j}$ for $j>i+1$ then
$j-i-1$ zeros are added to the vector $s_{T_{1}U_{1}}$ before the new 0 for
$p_{i}$ is added, and similarly for $T_{2}$.

Now the algorithm checks whether $s_{T_{1}U_{1}}+V(T_{1})\cap
s_{T_{2}U_{2}}+V(T_{2})$ is empty. If it is not, then $s_{TU}$ is defined to
be an element of this intersection, extended by a 0 for the new position
$p_{i}$. One checks that indeed $s_{TU}\in V(T,U)$. If this fails, then the
other option is that the value for $p_{i}$ is 1. Then both $s_{T_{1}U_{2}}$
and $s_{T_{2}U_{1}}$ should exist, and extended by zeros if necessary. In that
case it is checked whether $s_{T_{1}U_{2}}+V(T_{1})\cap
s_{T_{2}U_{1}}+V(T_{2})$ is empty. If it is not, then $s_{TU}$ is defined to
be an element of this intersection, extended by a 1 for the new position
$p_{i}$. One checks that indeed $s_{TU}\in V(T,U)$. In all other cases
$V(T,U)$ is empty.

Next a basis for $V(T)$ is computed for every $T$ labeled by $p_{i}$, that is,
$T=p_{i}(T_{1},T_{2})$. In case the root of $T_{1}$ is $p_{j}$ with $j>i+1$
then $j-i-1$ zeros are added to all vectors in the basis of $V(T_{1})$, and
similarly for $T_{2}$. Now a basis for $V(T_{1})\cap V(T_{2})$ is computed,
and every vector in the basis is extended by an extra 0 for the new position
$p_{i}$. In case $s_{T_{1}T_{2}}$ does not exist then this is a basis for
$V(T)$. In case $s_{T_{1}T_{2}}$ exists then one more vector is added to the
basis, namely $s_{T_{1}T_{2}}$ extended by an extra 1 for the new position
$p_{i}$. In both cases a basis for $V(T)$ has been computed.

This is done for all $i$, running down from $n$ to 1. Then finally a basis of
$T(f)$ is obtained as a basis of the intersection of all $V(T)$, for $T$
running over the $m$ output nodes of the BDD. $\Box$

To sketch what is going on in the algorithm we consider the same ROBDD with
respect to $p<q<r$ that we saw before. First for the two nodes $T_{r},U_{r}$
labeled by $r$ the one-dimensional vector $s_{T_{r}U_{r}}$ is computed, being
equal to $s_{U_{r}T_{r}}$. The value 0 for the position $r$ fails since
$s_{01}$ does not exist, but the value 1 for the position $r$ succeeds since
$s_{00}=s_{11}=\epsilon$. So $s_{T_{r}U_{r}}=(1)$: a vector of length 1
corresponding to the variable $r$, expressing that by swapping $r$, the two
$r$-nodes transform to each other. Next bases of $V(T_{r})$ and $V(U_{r})$ are
computed, both being empty. Let $T_{q},U_{q}$ be the two nodes labeled by $q$,
the next step is to compute $s_{T_{q}U_{q}}=s_{U_{q}T_{q}}$.

$p$$q$$q$$r$$r$$0$$1$

The algorithm computes the intersection of $(1)+V(T_{q1})$ consisting of the
single vector $(1)$ and $s_{00}+V(T_{q2})$, which is the full one-dimensional
space, so the intersection consists of $(1)$. Extended by a 0 in front for the
new position for variable $q$ this yields
$s_{T_{q}U_{q}}=s_{U_{q}T_{q}}=(0,1)$. Both $V(T_{q})$ and $V(U_{q})$ only
consist of the zero vector $(0,0)$, and have an empty basis.

Finally, a basis for $V(T_{p})$ is computed, for $T_{p}$ being the root node
labeled by $p$. It starts by taking a basis for $V(T_{q}\cap V(U_{q})$, and
then it is checked whether $s_{T_{q}U_{q}}$ exists. Indeed it exists and
equals $(0,1)$, to be extended by 1 in front. So the empty basis is extended
by the vector $(1,0,1)$. So the resulting basis of $V(T_{p})$ is $(1,0,1)$.
Indeed, the effect of addition of $(1,0,1)$ is that both $p$ and $r$ are
swapped, by which the BDD is transformed to itself, and according to the
theorem apart from the identity this is the only operation doing so.

## References

  * [1] R.E. Bryant.  Graph-based algorithms for boolean function manipulation.  IEEE Trans. Comput., 35(8):677––691, 1986.
  * [2] E.M. Clarke, T.A. Henzinger, H. Veith, and R. Bloem.  Handbook of Model Checking.  Springer International Publishing, 2018.
  * [3] J.E. Hopcroft, R. Motwani, and J.D. Ullman.  Introduction to Automata Theory, Languages and Computation.  Addison Wesley, 2007.
  * [4] S. Lang.  Introduction to linear algebra.  Springer, 1997.
  * [5] E. M. Luks, F. Rákóczi, and C. R. B. Wright.  Some algorithms for nilpotent permutation groups.  Journal of Symbolic Computation, 23(4):335––354, 1997.
  * [6] C. Meinel and T. Theobold.  Algorithms and data structures in VLSI design.  Springer, 1998.
  * [7] D.R. Simon.  On the power of quantum computation.  SIAM Journal on Computing, 26(5):1474––1483, 1997.
  * [8] L. Valiant.  The relative complexity of checking and evaluating.  Information Processing Letters, 5(1):20–23, 1976.