# Learned Indexes for a Google-scale Disk-based Database

Hussam Abu-Libdeh
Google &Deniz Altınbüken
Google &Alex Beutel
Google &Ed H. Chi
Google &Lyric Doshi
Google &Tim Kraska
MIT, Google &Xiaozhou (Steve) Li
Google &Andy Ly
Google &Christopher Olston
Google111Work done while at Google, although the author currently does not
work at Google.

###### Abstract

There is great excitement about learned index structures, but understandable
skepticism about the practicality of a new method uprooting decades of
research on B-Trees. In this paper, we work to remove some of that uncertainty
by demonstrating how a learned index can be integrated in a distributed, disk-
based database system: Google’s Bigtable. We detail several design decisions
we made to integrate learned indexes in Bigtable. Our results show that
integrating learned index significantly improves the end-to-end read latency
and throughput for Bigtable.

##  1 Introduction

There has been a lot of excitement about the potential benefits of using
machine learning methods in databases, but understandable skepticism about the
practicality of these new methods for real applications. Two years ago learned
index structures [10] were proposed as a novel technique to replace B-Trees
and similar range index structures. Learned index structures use a learned
CDF-model instead of the traditional tree-structures to achieve significantly
faster lookup times and index space savings. While there has since been a
flurry of follow up research, the impact of the work on real-world systems has
been under question. The most common points of criticism include, that (1) the
original learned index didn’t support inserts, (2) wasn’t designed for disk-
based systems, where indexes matter the most, and, more generally, (3) the
index size or speed improvement do not really matter in practice as it only
makes up a small fraction of the entire query execution time. While support
for inserts has already been addressed by follow-up work [4, 6, 9], the
question of whether learned indexes can have an impact on real, disk-based
systems remained unaddressed.

In this paper, we present initial results on integrating learned index
structures into Google’s Bigtable [1, 2] and show that they can significantly
improve the read latency and throughput, especially at the tail. This is a
surprising result as Bigtable is a distributed and disk-based system that has
been optimized for high-throughput and low-latency reads and writes. Requests
usually take tens to hundreds of milliseconds rather than nanoseconds. How can
a learned index structure, which improves request times by nanoseconds in
[10], have a positive impact on the overall latency of such a system? While
the faster lookup time has little impact, we see big performance gains from
the second-order effects of using a learned index, such as reducing the index
size, requiring fewer index seeks, reading fewer index blocks, and simplifying
data block prefetching.

Bigtable uses a traditional B-Tree to determine which key is stored in which
block. Hash maps are not an option in Bigtable as the system has to support
range scans. Like many database systems, the B-Tree itself is also stored in
the same block structure and can consist of several blocks. As a result, a
request for a key might involve several block reads; usually 1-2 to read the
index blocks and then 1 more to read the block with the data. Caching can
significantly reduce the number of blocks to fetch from the distributed file
system, especially the index blocks. However, in practice (1) Bigtable
instances can become really big, so big that the index might not fit into main
memory, (2) machines might host several Bigtable instances, reducing the
amount of available memory, (3) failures and load-balancing might clear the
cache, and (4) some Bigtable instances are both large and rarely used. All
these factors create pressure on the cache and can cause index blocks to be
fetched again. Reducing the index size by orders of magnitude can have an
overall positive impact, especially on the tail latency. With a smaller index,
fewer blocks have to be fetched even with a cold cache. The smaller index size
also reduces the overall resource consumption and improves throughput.

This paper explores the opportunity of learned indexes to reduce the index
size for distributed database systems in general, and Bigtable in particular.
In order to integrate learned index structures into Bigtable, we had to
significantly extend the original learned index design [10] for disk-based
systems with block identifiers. The original learned index assumed that all
data is stored in a large, continuous array in memory, thus avoiding the non-
trivial space cost of storing any pointers and allowing for cheap local
searches following mispredictions of data locations. Unfortunately, this is
not possible in Bigtable, which uses block-based files to store data and does
not allow laying out data in one continuous array. We overcome this issue by
using the model to _define_ which records are stored in which block, as
opposed to learning which records are in which block. Therefore, model
predictions are always correct. We also create a novel compressible mapping
table for the block pointers.

In summary, we make the following contributions:

  1. 1.

We present the first design of learned indexes for a distributed, disk-based
database.

  2. 2.

We offer a new learned index model design for string keys with monotonicity
guarantees.

  3. 3.

We present the evaluation of our method with uniform value sizes to understand
the trade-offs in read performance. We demonstrate using learned indexes
improves latency $36\%$ for point lookups and $22\%$ for scans on average.
Similarly, using learned indexes increases throughput by $55\%$ for point
lookups and $28\%$ for scans on average.

##  2 Related Work

Learned index structures were first introduced in [10]. Several works on
learned index structures followed [6, 7, 4, 9, 14, 13, 15, 12, 5, 11]. For
example, PGM index [6], FITing tree [7], RadixSpline [9] and ALEX [4] all
investigate how to efficiently support inserts, provide better worst-case
guarantees, and/or faster index construction. Lisa [8] extends the idea of
learned index structures for DNA Sequence search, [13, 15] for spatial
applications, and Flood [12] and Tsunami [5] for multi-dimensional data. More
recently, the SOSD benchmark [11] demonstrated that learned index structures
outperform their traditional counterparts on a wide range of datasets in size
and lookup latency. However, none of these algorithms are designed for disk-
based or distributed systems.

Most closely related to this work is BOURBON [3], which shows how to integrate
learned index structure for an LSM-based Key-Value Store. A log-structure
merge (LSM)-tree is a highly write optimized data structure for disk. However,
their system is a research prototype - so it is still not answering the
question if learned indexes would impact a real production system, nor are
their techniques targeted toward distributed systems and read-heavy workloads.

##  3 Background System Design

Bigtable [2] is a distributed structured storage system that serves petabytes
of data. Bigtable can support jobs that need to meet high throughput
requirements as well as jobs that require low latency, using a server that
manages the Bigtable cell, and many tablet servers that serve data.

Writes in Bigtable are handled directly by the tablet servers, where they are
first committed to a log on disk, then written to the memtable. When the
memtable size reaches a threshold, it is _compacted_ to disk as a read-only
SSTable. Reads are also handled directly by the tablet servers either from the
memtable or SSTables. During reads, SSTables are loaded into memory from a
distributed file system and scanned to find the correct value.

SSTables are structured as a map of key-value pairs, sorted by keys of the
form (row, column, timestamp). To support efficient operations on very large
data sets, SSTable implementation partitions data into data blocks and keeps
an index of which keys reside in which data blocks. Reads can then use the
SSTable index to find the correct data blocks for a given key.

The SSTable index is stored in index blocks as an ordered mapping from the
last key in a data block to the associated index entry for that data block.
The index entry contains information about the location and size of the block.
Using these, the data block can be efficiently loaded into memory. The index
block is intended to stay in memory, meaning reads, especially continuous
reads, can be fulfilled by querying the index block and only making directed
disk reads for the requested data.

The SSTable index is created while SSTables are constructed. During
construction, once a data block has been filled up, an appropriate entry is
added to the index. The data block is then written out and evicted from
memory. To finalize the SSTable, the index is written out as well.

With growing SSTable sizes, the size of the index block can also grow. To
improve index efficiency, SSTables use two-level indexes, comprising a level-0
index and a level-1 index. The level-0 index spans a single index block and
always resides in memory, pointing to level-1 index blocks. The level-1 index
is a sequence of level-1 index blocks, which point to data blocks. The level-1
index blocks are loaded into memory when a data block that they point to is
accessed.

##  4 Learned Indexes for Disk-based Databases

### Design

As described above, an SSTable $\mathcal{D}$ consists of key, value pairs
$r=\langle k,v\rangle$. These records are sorted by the key $k$ and stored
into blocks. A traditional look-up index searches through the index data
structure to identify which block contains the record for a given key. The
learned index design in [10] proposed the index tries to predict the record’s
location directly by a given key $k$. If the predicted location was incorrect,
the system needed to search nearby (e.g. with exponential search) to find the
requested record. Unfortunately, this doesn’t work well for Bigtable.
Predicting the exact location of a record is not useful since the system needs
to read the entire block. As a result, we instead focus on the learned index
predicting blocks not records. Even then, if the predicted block is incorrect,
searching nearby would require reading whole new blocks, which is much more
costly.

Therefore, we take a new approach. Let’s assume we are training a learned
index $f(\cdot)$ to take a key $k$ and predict a block number. Given a learned
index $f$, we designate block boundaries during SSTable creation such that
each record $\langle k,v\rangle$ is placed in predicted block $f(k)$. By
writing the data to match the index, we guarantee that the learned index
always predicts the correct block for a given key. Further, by using a
monotonic $f$, we ensure that records are still sorted by key and we can still
perform range scans.

### Learned Index Training

How should we train the learned index to predict the block number before the
block number is set? Rather than train the learned index to predict the block
number, we train it to predict how many bytes into the data the record falls.
We can use this estimation of number of bytes to build approximately equal-
sized blocks.

To make this precise, assume that $s(\langle k,v\rangle)$ is the number of
bytes in record $\langle k,v\rangle$ and let $S(\langle k,v\rangle)$ denote
the number of bytes preceding $k$ in the SSTable $\mathcal{D}$:

$\displaystyle S(\langle k,v\rangle)=\sum_{\langle
k^{\prime},v^{\prime}\rangle\in\mathcal{D}|k^{\prime}<k}s(\langle
k^{\prime},v^{\prime}\rangle)$ (1)

We use $S(\langle k,v\rangle)$ as the supervision for training $f$, i.e.
$\min_{f}\sum_{\langle k,v\rangle}(f(k)-S(\langle k,v\rangle))^{2}$. Given a
prediction of the number of bytes into the data a record lies, we can recover
the predicted block number by $\lfloor f(k)/\tau\rfloor$ where $\tau$ is the
desired average block size. While model inaccuracy may result in a less
uniform distribution of block sizes, the model will never predict the wrong
block.

### Model Structure

The results presented in this paper are based on a linear regression model,
but any model can be used (e.g., RMIs [10]). The simplicity of the model
reduces both storage and inference costs while providing the necessary
monotonicity guarantees over string keys.

Since the keys are strings of varying lengths, we convert them into an integer
for input to the linear regression. In this conversion, we treat the leading
characters of the string as the leading bits of the integer. Doing this
naively would mean we could only take into account the first few characters in
the key. Instead, we shift and re-base on a character by character basis,
based on the range of characters observed at each character position. During
training, we determine the minimum and maximum ASCII value of each character
position over all keys. We then convert the keys into integers by choosing a
different numerical base for each character position according to the range of
values that position can take. To give an example, consider first how we
encode numbers in base 10: $132=1*100+3*10+2$. Now, consider that the only
keys are "aab", "bdd", and "bcb". We need 2 values to encode the range of the
$0^{th}$ position, 4 values to encode the range of the $1^{st}$, and 3 values
to encode the range of the $2^{nd}$. Therefore, "bcb" becomes
$1*(4*3)+2*(3)+0$. These converted keys become the input $x$ for an Ordinary
Least Squares (OLS) model matching those $x$ to $S(\langle k,v\rangle)$. We
can compute the parameters in closed form after a single pass over the data.

### Block Locations

As the learned index predicts block numbers instead of disk locations, we need
a way to map a predicted block number to a disk location. For this, we store
the location of each block location in an array $B$ such that $B[\lfloor
f(k)/\tau\rfloor]$ outputs the location of the block on disk. Because the
blocks are stored contiguously, $B[\lfloor f(k)/\tau\rfloor+1]-B[\lfloor
f(k)/\tau\rfloor]$ makes the block size available. For backwards compatibility
with traditional indexes in Bigtable, we also store additional metadata (e.g.
checksums) for each block. While this design may not seem more efficient than
the last layer of a traditional index, it saves significant space in two
regards: (1) none of the keys need to be stored (2) the disk locations can be
compressed as they are approximately uniformly spaced222In the experiments
below we don’t use a compressed form of this map..

##  5 Evaluation and Conclusion

We evaluate how using a learned index affects Bigtable read performance in
comparison to using a two-level index (Bigtable’s default). In our preliminary
results, we measure point lookups and scans from 5 tablet servers, each with
4G RAM. For point lookups, 15 clients maintain a buffer of 100 asynchronous
single row read requests each, sending new requests as they receive replies.
For scans, every operation scans 100 consecutive rows of size 1KB. During
reads, tablet servers prefetch index and data blocks as needed. The SSTables
are constructed with random integer keys (encoded as strings). Each row key is
associated with data of size 1KB, and a data block size of 32KB.

We ran experiments with tables of different sizes (16 to 512 million rows) and
the size of the table did not impact the read performance. The results we are
presenting are for a table size of 256 million rows.

Figure 1(a) shows that the learned index reduces the read latency by $38\%$
for point lookups while maintaining it for scans in the 99th percentile. The
mean latency was also reduced $36\%$ for point lookups and $22\%$ for scans as
shown in Figure 1(b). Learned index eliminates the need for disk accesses for
fetching index blocks, which improves the read latency for databases with
larger indexes.

The learned index also significantly increases the throughput and indirectly,
reduces CPU resource usage. Throughput increased $54\%$ for point lookups and
$56\%$ for scans (see Figure 1(c)) in the 99th percentile. Comparably, the
mean throughput increased by $55\%$ for point lookups and by $28\%$ for scans
(see Figure 1(d)). The reason for this is more subtle: Like many disk-based
systems, Bigtable heavily compresses the data. Reducing the number of blocks
accessed reduces the amount of work needed to decompress the data in addition
to other secondary effects.

(a) p99 Latency

(b) Mean Latency

(c) p99 Throughput

(d) Mean Throughput

Figure 1: Learned index demonstrates performance improvements over the two-
level index for lookups and scans. (a), (b): Latency reduced. (c), (d)
Throughput improved. Scan numbers are normalized as per 1KB row.

Early results from our ongoing experiments with different key distributions,
workloads, and value sizes show similar performance improvements from using a
learned index (see also [11]). Furthermore, using the learned index does not
affect the write performance because the model training is decoupled from the
write path in Bigtable. The learned index model is trained in the background
during SSTable creation after memtables fill up.

In summary, our evaluation shows that learned indexes can improve real-world
systems because of the cascading benefits of their significantly smaller size
and simple usage.

## References

  * [1] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber.  Bigtable: A distributed storage system for structured data.  In 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 205–218, 2006.
  * [2] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber.  Bigtable: A distributed storage system for structured data.  ACM Transactions on Computer Systems (TOCS), 26(2):4, 2008.
  * [3] Y. Dai, Y. Xu, A. Ganesan, R. Alagappan, B. Kroth, A. Arpaci-Dusseau, and R. Arpaci-Dusseau.  From wisckey to bourbon: A learned index for log-structured merge trees.  In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 155–171. USENIX Association, Nov. 2020.
  * [4] J. Ding, U. F. Minhas, H. Zhang, Y. Li, C. Wang, B. Chandramouli, J. Gehrke, D. Kossmann, and D. Lomet.  ALEX: An Updatable Adaptive Learned Index.  arXiv:1905.08898 [cs], May 2019.
  * [5] J. Ding, V. Nathan, M. Alizadeh, and T. Kraska.  Tsunami: A learned multi-dimensional index for correlated data and skewed workloads.  CoRR, abs/2006.13282, 2020.
  * [6] P. Ferragina and G. Vinciguerra.  The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds.  Proceedings of the VLDB Endowment, 13(8):1162–1175, Apr. 2020.
  * [7] A. Galakatos, M. Markovitch, C. Binnig, R. Fonseca, and T. Kraska.  FITing-Tree: A Data-aware Index Structure.  In Proceedings of the 2019 International Conference on Management of Data, SIGMOD ’19, pages 1189–1206, New York, NY, USA, 2019. ACM.
  * [8] D. Ho, J. Ding, S. Misra, N. Tatbul, V. Nathan, V. Md, and T. Kraska.  LISA: towards learned DNA sequence search.  CoRR, abs/1910.04728, 2019.
  * [9] A. Kipf, R. Marcus, A. van Renen, M. Stoian, A. Kemper, T. Kraska, and T. Neumann.  RadixSpline: A single-pass learned index.  In Proceedings of the Third International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, pages 1–5. Association for Computing Machinery, June 2020.
  * [10] T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis.  The case for learned index structures.  In Proceedings of the 2018 International Conference on Management of Data, pages 489–504. ACM, 2018.
  * [11] R. Marcus, A. Kipf, A. van Renen, M. Stoian, S. Misra, A. Kemper, T. Neumann, and T. Kraska.  Benchmarking learned indexes.  CoRR, abs/2006.12804, 2020.
  * [12] V. Nathan, J. Ding, M. Alizadeh, and T. Kraska.  Learning multi-dimensional indexes.  In D. Maier, R. Pottinger, A. Doan, W. Tan, A. Alawini, and H. Q. Ngo, editors, Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, pages 985–1000. ACM, 2020.
  * [13] V. Pandey, A. van Renen, A. Kipf, I. Sabek, J. Ding, and A. Kemper.  The case for learned spatial indexes.  CoRR, abs/2008.10349, 2020.
  * [14] N. Setiawan, B. Rubinstein, and R. Borovica-Gajic.  Function Interpolation for Learned Index Structures.  In Database Theory and Applications, DTA ’20, 2020.
  * [15] H. Wang, X. Fu, J. Xu, and H. Lu.  Learned index for spatial queries.  In 2019 20th IEEE International Conference on Mobile Data Management (MDM), pages 569–574, 2019.


defiteor defi lemmateorlemma propteorprop corteorcor exteorex ossteoross

# An isoperimetric result for an energy related to the $p$-capacity

P. Acampora, E. Cristoforoni

###### Abstract

In this paper, we generalize the notion of relative $p$-capacity of $K$ with
respect to $\Omega$, by replacing the Dirichlet boundary condition with a
Robin one. We show that, under volume constraints, our notion of $p$-capacity
is minimal when $K$ and $\Omega$ are concentric balls. We use the $H$-function
(see [4, 8]) and a derearrangement technique.

MSC 2020: 35J66, 35J92, 35R35.

Keywords: Robin, p-capacity, free boundary, isocapacitary inequality

##  1 Introduction

Let $p>1$, $\beta>0$ be real numbers. For every open bounded sets
$\Omega\subset\mathbb{R}^{n}$ with Lipschitz boundary, and every compact set
$K\subseteq\overline{\Omega}$ with Lipschitz boundary, we define

$E_{\beta,p}(K,\Omega)=\inf_{\begin{subarray}{c}v\in W^{1,p}(\Omega)\\\
v=1\text{ in }K\end{subarray}}\left(\int_{\Omega}\lvert\nabla
v\rvert^{p}\,dx+\beta\int_{\partial\Omega}\lvert
v\rvert^{p}\,d\mathcal{H}^{n-1}\right).$ (1.1)

We notice that it is sufficient to minimize among all functions $v\in
H^{1}(\Omega)$ with $v=1$ in $K$ and $0\leq v\leq 1$ a.e., moreover if
$K,\Omega$ are sufficiently smooth, a minimizer $u$ satisfies

$\begin{cases}u=1&\text{in }K,\\\\[5.0pt] \Delta_{p}u=0&\text{in
}\Omega\setminus K,\\\\[6.0pt] \lvert\nabla u\rvert^{p-2}\dfrac{\partial
u}{\partial\nu}+\beta\lvert u\rvert^{p-2}u=0&\text{on
}\partial\Omega\setminus\partial K,\end{cases}$ (1.2)

where $\Delta_{p}u=\operatorname{div}\left(\lvert\nabla u\rvert^{p-2}\nabla
u\right)$ is the $p$-Laplacian of $u$ and $\nu$ is the outer unit normal to
$\partial\Omega$. If $\mathring{K}=\Omega$, equation (1.2) has to be intended
as $u=1$ in $\Omega$, and the energy is

$E_{\beta,p}(\Omega,\Omega)=\beta\mathcal{H}^{n-1}(\partial\Omega).$

In general, equation (1.2) has to be intended in the weak sense, that is: for
every $\varphi\in W^{1,p}(\Omega)$ such that $\varphi\equiv 0$ in $K$,

$\int_{\Omega}\lvert\nabla u\rvert^{p-2}\nabla
u\nabla\varphi\,d\mathcal{L}^{n}+\beta\int_{\partial\Omega}u^{p-1}\varphi\,d\mathcal{H}^{n-1}=0.$
(1.3)

In particular if $u$ is a minimizer, letting $\varphi=u-1$, we have that

$E_{\beta,p}(K,\Omega)=\int_{\Omega}\lvert\nabla
u\rvert^{p}\,dx+\beta\int_{\partial\Omega}u^{p}\,d\mathcal{H}^{n-1}=\beta\int_{\partial\Omega}u^{p-1}\,d\mathcal{H}^{n-1}.$

Moreover from the strict convexity of the functional, the minimizer is the
unique solution to (1.3).

This problem is related to the so-called _relative $p$-capacity of $K$ with
respect to $\Omega$_, defined as

$\operatorname{Cap}_{p}(K,\Omega):=\inf_{\begin{subarray}{c}v\in
W^{1,p}_{0}(\Omega)\\\ v=1\text{ in
}K\end{subarray}}\left(\int_{\Omega}\lvert\nabla v\rvert^{p}\,dx\right).$

In the case $p=2$ it represents the electrostatic capacity of an annular
condenser consisting of a conducting surface $\partial\Omega$, and a conductor
$K$, where the electrostatic potential is prescribed to be 1 inside $K$ and 0
outside $\Omega$. Let $\omega_{n}$ be the measure of the unit sphere in
$\mathbb{R}^{n}$, and let $M>\omega_{n}$, then it is well known that there
exists some $r\geq 1$ such that

$\min_{\begin{subarray}{c}\lvert K\rvert=\omega_{n}\\\ \lvert\Omega\rvert\leq
M\end{subarray}}\operatorname{Cap}_{p}(K,\Omega)=\operatorname{Cap}_{p}(B_{1},B_{r}).$

This is an immediate consequence of the Pólya-Szegő inequality for the Schwarz
rearrangement (see for instance [11, 9]). We are interested in studying the
same problem for the energy defined in (1.1), which corresponds to changing
the Dirichlet boundary condition on $\partial\Omega$ into a Robin boundary
condition, namely, we consider the following problem

$\inf_{\begin{subarray}{c}\lvert K\rvert=\omega_{n}\\\ \lvert\Omega\rvert\leq
M\end{subarray}}E_{\beta,p}(K,\Omega).$ (1.4)

In this case, the previous symmetrization techniques cannot be employed
anymore.

Problem (1.4) has been studied in the linear case $p=2$ in [6], with more
general boundary conditions on $\partial\Omega$, namely

$\frac{\partial u}{\partial\nu}+\frac{1}{2}\Theta^{\prime}(u)=0,$

where $\Theta$ is a suitable increasing function vanishing at $0$. This
problem has been addressed to thermal insulation (see for instance [7, 1]).
Our main result reads as follows.

######  Theorem 1.1.

Let $\beta>0$ such that

$\beta^{\frac{1}{p-1}}>\frac{n-p}{p-1}.$

Then, for every $M>\omega_{n}$ the solution to problem (1.4) is given by two
concentric balls $(B_{1},B_{r})$, that is

$\min_{\begin{subarray}{c}\lvert K\rvert=\omega_{n}\\\ \lvert\Omega\rvert\leq
M\end{subarray}}E_{\beta,p}(K,\Omega)=E_{\beta,p}(B_{1},B_{r}),$

in particular we have that either $r=1$ or $M=\omega_{n}r^{n}$.

Moreover, if $K_{0}\subseteq\overline{\Omega_{0}}$ are such that

$E_{\beta,p}(K_{0},\Omega_{0})=\min_{\begin{subarray}{c}\lvert
K\rvert=\omega_{n}\\\ \lvert\Omega\rvert\leq
M\end{subarray}}E_{\beta,p}(K,\Omega),$

and $u$ is the minimizer of $E_{\beta,p}(K_{0},\Omega_{0})$, then the sets
$\Set{u=1}$ and $\Set{u>0}$ coincide with two concentric balls up to a
$\mathcal{H}^{n-1}$-negligible set.

######  Remark .

In the case

$\beta^{\frac{1}{p-1}}\leq\frac{n-p}{p-1},$

adapting the symmetrization techniques used in [6], it can be proved that a
solution to problem (1.4) is always given by the pair $(B_{1},B_{1})$.

We point out that the proof of the theorem relies on the techniques involving
the $H$-function introduced in [4, 8].

The case in which $\Omega$ is the Minkowski sum $\Omega=K+B_{r}(0)$, the
energy $E_{\beta,p}(K,\Omega)$, has been studied in [3] under suitable
geometrical constraints.

##  2 Proof of the theorem

In order to prove Theorem 1.1, we start by studying the function

$R\mapsto E_{\beta,p}(B_{1},B_{R}).$

A similar study of the previous function can also be found in [3]. Let

$\Phi_{p,n}(\rho)=\begin{cases}\log(\rho)&\text{if }p=n,\\\\[7.0pt]
-\dfrac{p-1}{n-p}\dfrac{1}{\rho^{\frac{n-p}{p-1}}}&\text{if }p\neq
n.\end{cases}$

For every $R>1$, consider

$u^{*}(x)=1-\dfrac{\beta^{\frac{1}{p-1}}\left(\Phi_{p,n}(\lvert
x\rvert)-\Phi_{p,n}(1)\right)_{+}}{\Phi^{\prime}_{p,n}(R)+\beta^{\frac{1}{p-1}}\left(\Phi_{p,n}(R)-\Phi_{p,n}(1)\right)},$
(2.1)

the solution to

$\begin{cases}u^{*}=1&\text{in }B_{1},\\\\[5.0pt] \Delta_{p}u^{*}=0&\text{in
}B_{R}\setminus B_{1},\\\\[6.0pt] \lvert\nabla
u^{*}\rvert^{p-2}\dfrac{\partial u^{*}}{\partial\nu}+\beta\lvert
u^{*}\rvert^{p-2}u^{*}=0&\text{on }\partial B_{R}.\end{cases}$

We have that

$\begin{split}E_{\beta,p}(B_{1},B_{R})&=\int_{B_{R}}\lvert\nabla
u^{*}\rvert^{p}\,dx+\beta\int_{\partial B_{R}}\lvert
u^{*}\rvert^{p}\,d\mathcal{H}^{n-1}\\\\[10.0pt]
&=\dfrac{n\omega_{n}\beta}{\left[\Phi^{\prime}_{p,n}(R)+\beta^{\frac{1}{p-1}}\left(\Phi_{p,n}(R)-\Phi_{p,n}(1)\right)\right]^{p-1}}.\end{split}$
(2.2)

Notice that $E_{\beta,p}(B_{1},B_{R})$ is decreasing in $R>0$ if and only if

$\dfrac{d}{dR}\left(\Phi^{\prime}_{p,n}(R)+\beta^{\frac{1}{p-1}}\Phi_{p,n}(R)\right)\geq
0$

that is, if and only if

$R\geq\dfrac{n-1}{p-1}\dfrac{1}{\beta^{\frac{1}{p-1}}}=:\alpha_{\beta,p}.$

Moreover

$\begin{split}&E_{\beta,p}(B_{1},B_{1})=n\omega_{n}\beta,\\\\[10.0pt]
\lim_{R\to\infty}&E_{\beta,p}(B_{1},B_{R})=\begin{cases}n\omega_{n}\left(\dfrac{n-p}{p-1}\right)^{p-1}&\text{if
}p<n,\\\\[10.0pt] 0&\text{if }p\geq n.\end{cases}\end{split}$

Therefore, there are three cases:

  * •

if

$\beta^{\frac{1}{p-1}}\geq\dfrac{n-1}{p-1},$

$R\in[1,+\infty)\mapsto E_{\beta,p}(B_{1},B_{R})$ is decreasing;

  * •

if

$\dfrac{n-p}{p-1}<\beta^{\frac{1}{p-1}}<\dfrac{n-1}{p-1},$

$R\in[1,+\infty)\mapsto E_{\beta,p}(B_{1},B_{R})$ increases on
$[1,\alpha_{\beta,p}]$ and decreases on $[\alpha_{\beta,p},+\infty)$, with the
existence of a unique $R_{\beta,p}>\alpha_{\beta,p}$ such that
$E_{\beta,p}(B_{1},B_{R_{\beta,p}})=E_{\beta,p}(B_{1},B_{1})$;

  * •

if

$\beta^{\frac{1}{p-1}}\leq\dfrac{n-p}{p-1},$

$R\in[1,+\infty)\mapsto E_{\beta,p}(B_{1},B_{R})$ reaches its minimum at
$R=1$.

See for instance Figure 1, where

$\beta_{1}=\left(\frac{n-p}{p-1}\right)^{p-1},\qquad\beta_{2}=\left(\frac{n-1}{p-1}\right)^{p-1},\qquad
p=2.5,\qquad n=3.$

$E_{\beta,p}(B_{1},B_{r})$$r$$\beta\geq\beta_{2}$$\beta_{1}<\beta<\beta_{2}$$\beta\leq\beta_{1}$
Figure 1: $E_{\beta,p}(B_{1},B_{r})$ depending on the value of $\beta$

In the following, we will need

######  Lemma .

Let $R>1$,$\beta>0$ and let $u^{*}$ be the solution of the problem on
$(B_{1},B_{R})$. Then

$\dfrac{\lvert\nabla u^{*}\rvert}{u^{*}}\leq\beta^{\frac{1}{p-1}}$

in $B_{R}\setminus B_{1}$, if and only if

$E_{\beta,p}(B_{1},B_{\rho})\geq E_{\beta,p}(B_{1},B_{R})$

for every $\rho\in[1,R]$.

###### Proof.

Recalling the expressions of $u^{*}$ in (2.1), by straightforward computations
we have that

$\dfrac{\lvert\nabla u^{*}\rvert}{u^{*}}\leq\beta^{\frac{1}{p-1}}$

in $B_{R}\setminus B_{1}$ if and only if

$\Phi^{\prime}_{p,n}(R)+\beta^{\frac{1}{p-1}}\left(\Phi_{p,n}(R)-\Phi_{p,n}(1)\right)\geq\Phi^{\prime}_{p,n}(\rho)+\beta^{\frac{1}{p-1}}\left(\Phi_{p,n}(\rho)-\Phi_{p,n}(1)\right)$
(2.3)

for every $\rho\in[1,R]$, using the expression of
$E_{\beta,p}(B_{1},B_{\rho})$ in (2.2), (2.3) is equivalent to

$E_{\beta,p}(B_{1},B_{\rho})\geq E_{\beta,p}(B_{1},B_{R})$

for every $\rho\in[1,R]$. ∎

######  Definition .

Let $\Omega\subseteq\mathbb{R}^{n}$ be an open set, and let $U\subseteq\Omega$
be another set. We define the _internal boundary_ of $U$ as

$\partial_{i}U=\partial U\cap\Omega,$

and the _external boundary_ of $U$ as

$\partial_{e}U=\partial U\cap\partial\Omega.$

Let $K\subseteq\overline{\Omega}\subseteq\mathbb{R}^{n}$ be open bounded sets,
and let $u$ be the minimizer of $E_{\beta.p}(K,\Omega)$. In the following, we
denote by

$U_{t}=\Set{x\in\Omega}{u(x)>t}.$

######  Definition  ($H$-function).

Let $\varphi\in W^{1,p}(\Omega)$. We define

$H(t,\varphi)=\int_{\partial_{i}U_{t}}\lvert\varphi\rvert^{p-1}\,d\mathcal{H}^{n-1}-(p-1)\int_{U_{t}}\lvert\varphi\rvert^{p}\,d\mathcal{L}^{n}+\beta\mathcal{H}^{n-1}(\partial_{e}U_{t}).$

Notice that this definition is slightly different from the one given in [5].

######  Lemma .

Let $K\subseteq\Omega\subseteq\mathbb{R}^{n}$ be an open, bounded sets, and
let $u$ be the minimizer of $E_{\beta,p}(K,\Omega)$. Then for a.e. $t\in(0,1)$
we have

$H\left(t,\frac{\lvert\nabla u\rvert}{u}\right)=E_{\beta,p}(K,\Omega).$

###### Proof.

Recall that

$E_{\beta,p}(K,\Omega)=\int_{\Omega}\lvert\nabla
u\rvert^{p}\,d\mathcal{L}^{n}+\beta\int_{\partial\Omega}u^{p}=\beta\int_{\partial\Omega}u^{p-1}\,d\mathcal{H}^{n-1}.$
(2.4)

Let $t\in(0,1)$, we construct the following test functions: let
$\varepsilon>0$, and let

$\varphi_{\varepsilon}(x)=\begin{dcases}-1&\text{if }u(x)\leq t,\\\
\frac{u(x)-t}{\varepsilon u(x)^{p-1}}-1&\text{if }t<u(x)\leq t+\varepsilon,\\\
\frac{1}{u(x)^{p-1}}-1&\text{if }u(x)>t+\varepsilon,\end{dcases}$

so that $\varphi_{\varepsilon}$ is an approximation the function
$(u^{1-p}\chi_{U_{t}}-1)$, and

$\nabla\varphi_{\varepsilon}(x)=\begin{dcases}0&\text{if }u(x)\leq t,\\\
\frac{1}{\varepsilon}\left(\frac{\nabla u(x)}{u(x)^{p-1}}-(p-1)\frac{\nabla
u(x)(u(x)-t)}{u(x)^{p}}\right)&\text{if }t<u(x)\leq t+\varepsilon,\\\
-(p-1)\frac{\nabla u(x)}{u(x)^{p}}&\text{if }u(x)>t+\varepsilon.\end{dcases}$

We have that $\varphi_{\varepsilon}$ is an admissible test function for the
Euler-Lagrange equation (1.3), which entails

$\begin{split}0=&\frac{1}{\varepsilon}\int_{\\{t<u\leq
t+\varepsilon\\}\cap\Omega}\\!\frac{\lvert\nabla
u\rvert^{p-1}}{u^{p-1}}\lvert\nabla
u\rvert\,d\mathcal{L}^{n}-(p-1)\int_{\\{t<u\leq
t+\varepsilon\\}\cap\Omega}\\!\frac{\lvert\nabla
u\rvert^{p}}{u^{p}}\frac{u-t}{\varepsilon}\,d\mathcal{L}^{n}\\\\[7.0pt]
&-(p-1)\int_{\\{u>t+\varepsilon\\}\cap\Omega}\frac{\lvert\nabla
u\rvert^{p}}{u^{p}}\,d\mathcal{L}^{n}+\beta\int_{\\{t<u\leq
t+\varepsilon\\}\cap\partial\Omega}\frac{u-t}{\varepsilon}\,d\mathcal{H}^{n-1}\\\\[7.0pt]
&+\beta\mathcal{H}^{n-1}\left(\partial\Omega\cap\\{u>t+\varepsilon\\}\right)-\beta\int_{\partial\Omega}u^{p-1}\,d\mathcal{H}^{n-1}.\end{split}$

Letting now $\varepsilon$ go to 0, by coarea formula we get that for a.e.
$t\in(0,1)$

$\begin{split}\beta\int_{\partial\Omega}u^{p-1}\,d\mathcal{H}^{n-1}=&\int_{\partial_{i}U_{t}}\left(\frac{\lvert\nabla
u\rvert}{u}\right)^{p-1}\,d\mathcal{H}^{n-1}-(p-1)\int_{U_{t}}\left(\frac{\lvert\nabla
u\rvert}{u}\right)^{p}\,d\mathcal{L}^{n}\\\\[7.0pt]
&+\beta\mathcal{H}^{n-1}(\partial_{e}U_{t}).\end{split}$ (2.5)

Joining (2.4) and (2.5), the lemma is proven. ∎

######  Remark .

Notice that if $K,$ and $\Omega$ are two concentric balls, the minimizer $u$
is the one written in (2.1), for which the statement of the above Lemma holds
for every $t\in(0,1)$.

######  Lemma .

Let $\varphi\in L^{\infty}(\Omega)$. Then there exists $t\in(0,1)$ such that

$H(t,\varphi)\leq E_{\beta,p}(K,\Omega).$

###### Proof.

Let

$w=\lvert\varphi\rvert^{p-1}-\left(\frac{\lvert\nabla
u\rvert}{u}\right)^{p-1},$

then we evaluate

$\begin{split}H(t,\varphi)-H\left(t,\frac{\lvert\nabla
u\rvert}{u}\right)\\!&=\int_{\partial_{i}U_{t}}\\!\\!w\,d\mathcal{H}^{n-1}-(p-1)\\!\int_{U_{t}}\\!\left(\lvert\varphi\rvert^{p}-\left(\frac{\lvert\nabla
u\rvert}{u}\right)^{p}\right)\,d\mathcal{L}^{n}\\\\[7.0pt]
&\leq\int_{\partial_{i}U_{t}}w\,d\mathcal{H}^{n-1}-p\int_{U_{t}}\frac{\lvert\nabla
u\rvert}{u}w\,d\mathcal{L}^{n}\\\\[7.0pt]
&=-\frac{1}{t^{p-1}}\frac{d}{dt}\left(t^{p}\int_{U_{t}}\frac{\lvert\nabla
u\rvert}{u}w\,d\mathcal{L}^{n}\right),\end{split}$

where we used the inequality

$a^{p}-b^{p}\leq\frac{p}{p-1}a\,(a^{p-1}-b^{p-1})\qquad\forall a,b\geq 0.$
(2.6)

Multiplying by $t^{p-1}$ and integrating, we get

$\int_{0}^{1}t^{p-1}\left(H(t,\varphi)-H\left(t,\frac{\lvert\nabla
u\rvert}{u}\right)\right)\,dt\leq-\left[t^{p}\int_{U_{t}}\frac{\lvert\nabla
u\rvert}{u}w\,d\mathcal{L}^{n}\right]_{0}^{1}=0,$ (2.7)

from which we obtain the conclusion of the proof. ∎

######  Remark .

Notice that the inequality (2.6) holds as equality if and only if $a=b$.
Therefore, if $\varphi\neq\frac{\lvert\nabla u\rvert}{u}$ on a set of positive
measure, then the inequality in (2.7) is strict, since

$\left\lvert\Set{\varphi\neq\frac{\nabla u}{u}}\cap U_{t}\right\rvert>0$

for small enough $t$. Therefore, there exists $S\subset(0,1)$ such that
$\mathcal{L}^{1}(S)>0$ and for every $t\in S$

$H(t,\varphi)<E_{\beta,p}(K,\Omega).$

In the following, we fix a radius $R$ such that $\lvert
B_{R}\rvert\geq\lvert\Omega\rvert$, $u^{*}$ the minimizer of
$E_{\beta,p}(B_{1},B_{R})$, and

$\begin{split}H^{*}(t,\varphi)=&\int_{\partial\set{u^{*}>t}\cap
B_{R}}\lvert\varphi\rvert^{p-1}\,d\mathcal{H}^{n-1}-(p-1)\int_{\set{u^{*}>t}}\lvert\varphi\rvert^{p}\,d\mathcal{L}^{n}\\\\[7.0pt]
&+\beta\mathcal{H}^{n-1}(\partial\set{u^{*}<t}\cap\partial B_{R}).\end{split}$

######  Proposition .

Let $\beta>0$. Assume that

$\frac{\lvert\nabla u^{*}\rvert}{u^{*}}\leq\beta^{\frac{1}{p-1}}.$ (2.8)

Then we have that

$E_{\beta,p}(K,\Omega)\geq E_{\beta,p}(B_{1},B_{R}).$

###### Proof.

In the following, if $v$ is a radial function on $B_{R}$ and $r\in(0,R)$, we
denote with abuse of notation

$v(r)=v(x),$

where $x$ is any point on $\partial B_{r}$. By section 2 we know that for
every $t\in(0,1)$

$H^{*}\left(t,\frac{\lvert\nabla
u^{*}\rvert}{u^{*}}\right)=E_{\beta,p}(B_{1},B_{R}),$ (2.9)

while by section 2, for every $\varphi\in L^{\infty}(\Omega)$ there exists a
$t\in(0,1)$ such that

$E_{\beta,p}(K,\Omega)\geq H(t,\varphi).$ (2.10)

We aim to find a suitable $\varphi$ such that, for some $t$,

$H(t,\varphi)\geq H^{*}\left(t,\frac{\lvert\nabla u^{*}\rvert}{u^{*}}\right),$
(2.11)

so that combining (2.10), (2.11), and (2.9) we conclude the proof. In order to
construct $\varphi$, for every $t\in(0,1)$ we define

$r(t)=\left(\frac{\lvert U_{t}\rvert}{\omega_{n}}\right)^{\frac{1}{n}},$
(2.12)

then we set, for every $x\in\Omega$,

$\varphi(x)=\frac{\lvert\nabla u^{*}\rvert}{u^{*}}(r(u(x))).$ ††margin:  Claim

The functions $\varphi\chi_{U_{t}}$ and $\frac{\lvert\nabla
u^{*}\rvert}{u^{*}}\chi_{B_{r(t)}}$ are equi-measurable, in particular

$\int_{U_{t}}\varphi^{p}\,d\mathcal{L}^{n}=\int_{B_{r(t)}}\left(\frac{\lvert\nabla
u^{*}\rvert}{u^{*}}\right)^{p}\,d\mathcal{L}^{n}.$ (2.13)

Indeed, let $g(r)=\frac{\lvert\nabla u^{*}\rvert}{u^{*}}(r)$, and by coarea
formula,

$\begin{split}\lvert{U_{t}\cap\set{\varphi>s}}\rvert&=\\!\int_{U_{t}\cap\Set{g(r(u(x)))>s}}\,d\mathcal{L}^{n}\\\\[7.0pt]
&=\\!\int_{t}^{+\infty}\int_{\partial^{*}U_{\tau}\cap\set{g(r(\tau))>s}}\frac{1}{\lvert\nabla
u(x)\rvert}\,d\mathcal{H}^{n-1}(x)\,d\tau\\\\[7.0pt]
&=\\!\int_{0}^{r(t)}\\!\\!\int_{\partial^{*}U_{r^{-1}(\sigma)}}\frac{1}{\lvert\nabla
u(x)\rvert\lvert
r^{\prime}(r^{-1}(\sigma))\rvert}\chi_{\set{g(\sigma)>s}}\,d\mathcal{H}^{n-1}(x)\,d\sigma.\end{split}$
(2.14)

Notice now that, since

$\omega_{n}r(\tau)^{n}=\lvert U_{\tau}\rvert,$

then

$r^{\prime}(\tau)=-\frac{1}{n\omega_{n}r(\tau)^{n-1}}\int_{\partial^{*}U_{\tau}}\frac{1}{\lvert\nabla
u(x)\rvert}\,d\mathcal{H}^{n-1}(x).$ (2.15)

Therefore, substituting in (2.14), we get

$\lvert{U_{t}\cap\set{\varphi>s}}\rvert=\int_{0}^{r(t)}n\omega_{n}\sigma^{n-1}\chi_{\Set{g(\sigma)>s}}\,d\sigma=\left\lvert
B_{r(t)}\cap\Set{\frac{\lvert\nabla u^{*}\rvert}{u^{*}}>s}\right\rvert;$

where we have used polar coordinates to get the last equality. Thus, the claim
is proved.

Recalling the definition of $\varphi$, (2.8) reads

$\beta\geq\varphi^{p-1},$

then using (2.13) and the definition of $H$ (see section 2), we have

$\begin{split}H(t,\varphi)&=\beta\mathcal{H}^{n-1}(\partial_{e}U_{t})+\int_{\partial_{i}U_{t}}\varphi^{p-1}\,d\mathcal{H}^{n-1}-(p-1)\int_{U_{t}}\varphi^{p}\,d\mathcal{L}^{n}\\\\[7.0pt]
&\geq\int_{\partial
U_{t}}\varphi^{p-1}\,d\mathcal{H}^{n-1}-(p-1)\int_{B_{r(t)}}\left(\frac{\lvert\nabla
u^{*}\rvert}{u^{*}}\right)^{p}\,d\mathcal{L}^{n}\\\\[7.0pt]
&\geq\int_{\partial B_{r(t)}}\left(\frac{\lvert\nabla
u^{*}\rvert}{u^{*}}\right)^{p-1}\,d\mathcal{H}^{n-1}-(p-1)\int_{B_{r(t)}}\left(\frac{\lvert\nabla
u^{*}\rvert}{u^{*}}\right)^{p}\,d\mathcal{L}^{n}\\\\[7.0pt]
&=H^{*}\left(u^{*}(r(t)),\frac{\lvert\nabla
u^{*}\rvert}{u^{*}}\right)\\\\[7.0pt] &=E_{\beta,p}(B_{1},B_{R}),\end{split}$
(2.16)

where in the last inequality we have used the isoperimetric inequality and the
fact that $\varphi$ is constant on $\partial U_{t}$. ∎

######  Remark .

By section 2, we have that if $K$ and $\Omega$ are such that

$E_{\beta,p}(K,\Omega)=E_{\beta,p}(B_{1},B_{R}),$

then

$\varphi=\frac{\lvert\nabla u\rvert}{u}\qquad\text{for a. e. }x\in\Omega,$

so that, by section 2, we have equality in (2.16) for a.e. $t\in(0,1)$. Thus,
by the rigidity of the isoperimetric inequality, we get that $U_{t}$ coincides
with a ball up to a $\mathcal{H}^{n-1}$-negligible set for a.e. $t\in(0,1)$.
In particular, $\Set{u>0}=\bigcup_{t}U_{t}$ and $\set{u=1}=\bigcap_{t}U_{t}$
coincide with two balls up to a $\mathcal{H}^{n-1}$-negligible set.

###### Proof of Theorem 1.1.

Fix $M=\omega_{n}R^{n}$ with $R>1$. We divide the proof of the minimality of
balls into two cases, and subsequently, we study the equality case.

Let us assume that

$\beta^{\frac{1}{p-1}}\geq\dfrac{n-1}{p-1},$

and recall that in this case the function

$\rho\in[1,+\infty)\mapsto E_{\beta,p}(B_{1},B_{\rho})$

is decreasing. Let $u^{*}$ be the minimizer of $E_{\beta,p}(B_{1},B_{R})$, by
section 2 condition (2.8) holds and, by section 2, we have that a solution to
(1.4) is given by the concentric balls $(B_{1},B_{R})$.

Assume now that

$\dfrac{n-p}{p-1}<\beta^{\frac{1}{p-1}}<\dfrac{n-1}{p-1},$

then, in this case, letting

$\alpha_{\beta,p}=\dfrac{(n-1)}{(p-1)\beta^{\frac{1}{p-1}}},$

the function

$\rho\in[1,+\infty)\mapsto E_{\beta,p}(B_{1},B_{\rho})$

increases on $[1,\alpha_{\beta,p}]$ and decreases on
$[\alpha_{\beta,p},+\infty)$, and there exist a unique
$R_{\beta,p}>\alpha_{\beta,p}$ such that
$E_{\beta,p}(B_{1},B_{R_{\beta,p}})=E_{\beta,p}(B_{1},B_{1})$. If $R\geq
R_{\beta,p}$ the function $u^{*}$, minimizer of $E_{\beta,p}(B_{1},B_{R})$,
still satisfies condition (2.8) and, as in the previous case, a solution to
(1.4) is given by the concentric balls $(B_{1},B_{R})$. On the other hand, if
$R<R_{\beta,p}$, we can consider $u^{*}_{\beta,p}$ the minimizer of
$E_{\beta,p}(B_{1},B_{R_{\beta,p}})$. By section 2 we have that, for the
function $u^{*}_{\beta,p}$, condition (2.8) holds and, by section 2, we have
that if $K$ and $\Omega$ are open bounded Lipschitz sets with
$K\subseteq\Omega$, $\lvert K\rvert=\omega_{n}$, and $\lvert\Omega\rvert\leq
M$, then

$E_{\beta,p}(K,\Omega)\geq
E_{\beta,p}(B_{1},B_{R_{\beta,p}})=E_{\beta,p}(B_{1},B_{1})$

and a solution to (1.4) is given by the pair $(B_{1},B_{1})$.

For what concerns the equality case, we will follow the outline of the
rigidity problem given in [10, Section 3] (see also [2, Section 2]). Let
$K_{0}\subseteq\overline{\Omega_{0}}$ be such that

$E_{\beta,p}(K_{0},\Omega_{0})=\min_{\begin{subarray}{c}\lvert
K\rvert=\omega_{n}\\\ \lvert\Omega\rvert\leq
M\end{subarray}}E_{\beta,p}(K,\Omega),$

let $u$ be the minimizer of $E_{\beta,p}(K_{0},\Omega_{0})$. If
$\mathring{K_{0}}=\Omega_{0}$, then $\lvert\Omega_{0}\rvert=\lvert
B_{1}\rvert$ and isoperimetric inequality yields

$\mathcal{H}^{n-1}(\partial\Omega_{0})\geq\mathcal{H}^{n-1}(\partial B_{1}),$

while, from the minimality of $(K_{0},\Omega_{0})$ we have that

$E_{\beta,p}(K_{0},\Omega_{0})=\beta\mathcal{H}^{n-1}(\partial\Omega_{0})\leq
E_{\beta,p}(B_{1},B_{1})=\beta\mathcal{H}^{n-1}(\partial B_{1}),$

so that $\mathcal{H}^{n-1}(\Omega_{0})=\mathcal{H}^{n-1}(\partial B_{1})$.
Hence, by the rigidity of the isoperimetric inequality we have that
$\mathring{K_{0}}=\Omega_{0}$ are balls of radius $1$. On the other hand, if
$\mathring{K_{0}}\neq\Omega_{0}$, from the first part of the proof, there
exists $R_{0}>1$ such that $\lvert B_{R_{0}}\rvert\geq M$ and

$E_{\beta,p}(K_{0},\Omega_{0})=E_{\beta,p}(B_{1},B_{R_{0}}).$

Therefore, by section 2, we have that for a.e. $t\in(0,1)$, the superlevel
sets $U_{t}$ coincide with balls up to $\mathcal{H}^{n-1}$-negligible sets,
and $\Set{u=1}$ and $\Set{u>0}$ coincide with balls, up to
$\mathcal{H}^{n-1}$-negligible sets, as well. We only have to show that
$\Set{u=1}$ and $\Set{u>0}$ are concentric balls. To this aim, let us denote
by $x(t)$ the center of the ball $U_{t}$ and by $r(t)$ the radius of $U_{t}$,
as already done in (2.12). In addition, we also have that

$\frac{\lvert\nabla
u^{*}\rvert}{u^{*}}\Big{(}r\big{(}u(x)\big{)}\Big{)}=\varphi(x)=\frac{\lvert\nabla
u\rvert}{u}(x),$

so that, if $u(x)=t$, then $\lvert\nabla u(x)\rvert=C_{t}>0$. This ensures
that we can write

$\begin{split}x(t)&=\frac{1}{\lvert
U_{t}\rvert}\int_{U_{t}}x\,d\mathcal{L}^{n}(x)\\\\[7.0pt] &=\frac{1}{\lvert
U_{t}\rvert}\left(\int_{t}^{1}\int_{\partial U_{s}}\frac{x}{\lvert\nabla
u(x)\rvert}\,d\mathcal{H}^{n-1}(x)\,ds+\int_{K}x\,d\mathcal{L}^{n}(x)\right),\end{split}$

and we can infer that $x(t)$ is an absolutely continuous function, since
$\lvert\nabla u\rvert>0$ implies that $\lvert U_{t}\rvert$ is an absolutely
continuous function as well. Moreover, on $\partial U_{t}$ we have that for
every $\nu\in\mathbb{S}^{n-1}$,

$u(x(t)+r(t)\nu)=t,$ (2.17)

from which

$\nabla u(x(t)+r(t)\nu)=-C_{t}\nu.$ (2.18)

Differentiating (2.17), and using (2.18), we obtain

$-C_{t}\,x^{\prime}(t)\cdot\nu-C_{t}\,r^{\prime}(t)=1.$ (2.19)

Finally, joining (2.19) and (2.15), and the fact that $\lvert\nabla
u\rvert=C_{t}$ on $\partial U_{t}$, we get

$x^{\prime}(t)\cdot\nu=0$

for every $\nu\in\mathbb{S}^{n-1}$, so that $x(t)$ is constant and $U_{t}$ are
concentric balls for a.e. $t\in(0,1)$. In particular,
$\Set{u=1}=\bigcap_{t}U_{t}$ and $\Set{u>0}=\bigcup_{t}U_{t}$ share the same
center. ∎

## References

  * [1] P. Acampora and E. Cristoforoni  “A free boundary problem for the p-Laplacian with nonlinear boundary conditions”  In _preprint_ , 2022
  * [2] G. Aronsson and G. Talenti  “Estimating the integral of a function in terms of a distribution function of its gradient”  In _Boll. Un. Mat. Ital. B (5)_ 18.3, 1981, pp. 885–894
  * [3] R. Barbato  “Shape optimization for a nonlinear elliptic problem related to thermal insulation”  In _preprint_ arXiv, 2022
  * [4] M. Bossel  “Longueurs extrémales et fonctionnelles de domaine”  In _Complex Variables Theory Appl._ 6.2-4, 1986, pp. 203–234
  * [5] D. Bucur and D. Daners  “An alternative approach to the Faber-Krahn inequality for Robin problems”  In _Calc. Var. Partial Differential Equations_ 37.1-2, 2010, pp. 75–86
  * [6] D. Bucur, M. Nahon, C. Nitsch and C. Trombetti  “Shape optimization of a thermal insulation problem”  In _Calc. Var. Partial Differential Equations_ 61.5, 2022, pp. Paper No. 18629
  * [7] L.. Caffarelli and D. Kriventsov  “A free boundary problem related to thermal insulation”  In _Communications in Partial Differential Equations_ 41.7 Taylor & Francis, 2016, pp. 1149–1182
  * [8] D. Daners  “A Faber-Krahn inequality for Robin problems in any space dimension”  In _Math. Ann._ 335.4, 2006, pp. 767–785
  * [9] S. Kesavan  “Symmetrization & applications” 3, Series in Analysis  World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2006, pp. xii+148
  * [10] A.. Masiello and G. Paoli  “A rigidity result for the Robin Torsion problem”  arXiv, 2022
  * [11] G. Pólya and G. Szegö  “Isoperimetric Inequalities in Mathematical Physics”, Annals of Mathematics Studies, No. 27  Princeton University Press, Princeton, N. J., 1951, pp. xvi+279

Dipartimento di Matematica e Applicazioni “R. Caccioppoli”, Università degli
studi di Napoli Federico II, Via Cintia, Complesso Universitario Monte S.
Angelo, 80126 Napoli, Italy.

E-mail address, P. Acampora<EMAIL_ADDRESS>
Mathematical and Physical Sciences for Advanced Materials and Technologies,
Scuola Superiore Meridionale, Largo San Marcellino 10, 80126, Napoli, Italy.

E-mail address, E. Cristoforoni<EMAIL_ADDRESS>