∎

11institutetext: E. Burman 22institutetext: University College London,
Department of Mathematics, 807b Gower Street, London, WC1E 6BT, United Kingdom
22email<EMAIL_ADDRESS>33institutetext: M. Nechita 44institutetext:
Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy &
Department of Mathematics, Babeș-Bolyai University, Cluj-Napoca, Romania.
44email<EMAIL_ADDRESS>55institutetext: L. Oksanen
66institutetext: Department of Mathematics and Statistics, University of
Helsinki, Finland.
66email<EMAIL_ADDRESS>
# Optimal finite element approximation of unique continuation ††thanks: EB was
supported by the EPSRC grants EP/T033126/1 and EP/V050400/1. LO was supported
in part by the EPSRC grant EP/P01593X/1

Erik Burman  Mihai Nechita  Lauri Oksanen

(Received: date / Accepted: date)

###### Abstract

We consider finite element approximations of ill-posed elliptic problems with
conditional stability. The notion of _optimal error estimates_ is defined
including both convergence with respect to mesh parameter and perturbations in
data. The rate of convergence is determined by the conditional stability of
the underlying continuous problem and the polynomial order of the finite
element approximation space. A proof is given that no finite element
approximation can converge at a better rate than that given by the definition,
justifying the concept. A recently introduced class of finite element methods
with weakly consistent regularisation is recalled and the associated error
estimates are shown to be quasi optimal in the sense of our definition.

###### Keywords:

unique continuation conditional stability finite element methods stabilised
methods error estimates optimality

###### MSC:

65N20

##  1 Introduction

Arguably one of the most fundamental results in finite element analysis is the
best approximation result for the Galerkin method, known as Cea’s Lemma Cea64
, which together with approximation error estimates for finite element
functions results in quasi optimal error estimates for finite element methods
Zlamal68 , Nit70 , Bab70 , Hel71 . This result, that we will review below,
essentially says that if a $(2m)$-order elliptic problem, $m\geq 1$, is
approximated with $H^{m}$-conforming finite elements of local polynomial order
$p$ the error in $H^{m}$-norm is of the order $h^{p+1-m}$ for a sufficiently
smooth solution and that this rate is optimal compared to approximation: the
best interpolant of the exact solution has similar accuracy.

For ill-posed elliptic problems the situation is different. On the continuous
level existence can only be guaranteed after regularisation of the problem.
The two main approaches are Tikhonov regularisation TA77  and quasi
reversibility LL69 . These two approaches are strongly related (see for
instance BR18 ). The main effort in the error analysis has been to estimate
the perturbation induced by the addition of regularisation, and how to choose
the associated regularisation operator or parameter Miller73 , Nat84 , Lu88 ,
Bour05 , IJ15 . The error due to approximation in finite dimensional spaces of
such regularised problems has also been analysed Nat77 , EHN88 , MP01 .

In spite of these developments there seems to be a clear divide between the
approaches for approximating well-posed problems and ill-posed problems. In
particular, the use of regularisation introduces a perturbation on the
continuous level, and the discretisation must then be made fine compared to
this perturbation to ensure numerical stability and accuracy. The perturbation
caused by the regularisation is, however, typically of first order. So error
estimates in terms of the discretisation parameter and perturbations can never
be optimal in the way estimates for well-posed problems are.

There is also a rich literature on projection methods for ill-posed problems
where the discretisation serves as regularisation and refinement has to stop
as soon as the effect of perturbations in data becomes dominant Natt77 ,
Engl83 , EN87 , HAG02 , Kalt00 . These methods are often based on least
squares methods and the convergence of the approximate solution to the exact
solution for unperturbed data has been proven in several works as well as
different stopping criteria for the discretisation process, to avoid
degeneration due to pollution from perturbations. However no results on rates
of convergence where the discretisation errors and the perturbation errors are
both included appear to exist in the literature. Some such methods are
included in the framework for methods with optimal convergence that will be
considered herein (see for instance BLO18 ).

Recently a class of methods based on consistent stabilised finite element
methods applied in a primal-dual framework Bu13 , Bu14b , Bu16 , BO18  was
proposed. Here stability is obtained through a combination of consistent
stabilisation and Tikhonov regularisation, scaled with the mesh parameter to
obtain weak consistency. The upshot is that for this class of methods an error
analysis exists, where the computational error is bounded in terms of the mesh
parameter and perturbations of data, with constants depending on Sobolev norms
of the exact solution. Similarly to the well-posed case, the error estimates
for this approach combine the stability of the physical problem with the
approximability of the finite element space. Contrary to the well-posed case,
numerical stability can not be deduced from the physical stability, but has to
be a consequence of the design of the stabilisation terms. This means that the
stabilisation in this framework is bespoke, and must be designed to combine
optimal (weak) consistency and sufficient numerical stability. There is often
a tension between these two design criteria. As noted above, sometimes
Tikhonov regularisation, scaled with the mesh parameter, may be used in the
framework. An interesting feature is that the bespoke character also allows
for the integration of the dependence of the estimates on physical parameters
and different problems regimes BNO19 , BNO20a . Other physical models that
have been considered in this framework include data assimilation for fluids
BO18 ,BH18 ,BBFV20 , or wave equations BFO20a .

Common for all these references is the fact that the error estimates reflect
the stability of the continuous problem and the approximation order of the
finite element space, which seems to be an optimality property of the methods.
No rigorous proof, however, has been given for this optimality. The objective
of the present work is to show, in the model case of unique continuation for
Laplace equation, that the proposed error estimates are indeed optimal.

###  1.1 Unique continuation problem

Let $0<r_{1}<r_{2}<R$ and write $\omega=B(r_{1})$ and $B=B(r_{2})$ where
$B(r)$ is the open ball of radius $r>0$, with the centre at the origin in
$\mathbb{R}^{n}$. The objective is to solve the continuation problem: given
the restriction $u|_{\omega}$ to the subset $\omega$, find the restriction
$u|_{B}$ when $u$ satisfies $\Delta u=0$ in $B(R)$.

Further, letting $r_{2}<r_{3}<R$ and writing $\Omega=B(r_{3})$, it is
classical that the following conditional stability estimate holds Fritz60 :

$\|u\|_{L^{2}(B)}\lesssim\|u\|_{L^{2}(\omega)}^{\alpha}\|u\|_{L^{2}(\Omega)}^{(1-\alpha)},$
(1)

where $\alpha\in(0,1)$ and the implicit constant do not depend on the harmonic
function $u$. Estimate (1) is often called a three-ball estimate. We may view
the unique continuation problem as finding $u\in H^{1}(\Omega)$ such that

$\left\\{\begin{array}[]{rcl}-\Delta u&=&0\mbox{ in }\Omega\\\
u|_{\omega}&=&q\mbox{ in }\omega,\end{array}\right.$ (2)

with a priori knowledge on the size of the solution in $\Omega$ as prescribed
by the $L^{2}(\Omega)$-norm in (1).

For primal-dual finite element methods applied to this problem, with perturbed
data $u|_{\omega}=q+\delta q$, error estimates of the form

$\|u-u_{h}\|_{L^{2}(B)}\lesssim
h^{\alpha}\|u\|_{H^{2}(\Omega)}+h^{\alpha-1}\|\delta q\|_{L^{2}(\omega)}$ (3)

have been shown, see BHL18 , BNO19 , BNO20a  for different variations. Here
$\alpha\in(0,1)$ and $h$ denotes the mesh parameter defining the
characteristic length scale of the finite dimensional space. This is in the
case of piecewise affine approximation, however the estimate generalises in a
natural way to higher order approximation, as we shall see below. One can
obtain a similar bound in the $H^{1}$-norm over $B$. In the counterfactual
case that $\alpha=1$ we would then recover an estimate that is optimal
compared to interpolation. Hence a natural question is if the bound (3) in the
$L^{2}$-norm can be improved upon, since it is suboptimal with one order in
$h$ when compared to interpolation in the case $\alpha=1$.

We show in this paper that assuming that the coefficient $\alpha$ in (1) is
optimal and depends continuously on $r_{3}$, then regardless of the underlying
method, no sequence of finite element approximations to (2) can converge with
a rate better than that given by (3). We also point out that although the
discussion focuses on the finite element method, the definition of optimal
convergence given and the proof of optimality hold for any method producing an
approximating sequence in $H^{1}$ (or relying on such a sequence for the
analysis).

The paper is organized as follows. In Section 2 we will discuss the notion of
optimality of finite element approximations. First we revisit the classical
finite element analysis for well-posed problems. In Section 2.2 we then
discuss how the ideas of the well-posed case translate to the ill-posed case.
This leads us to a definition of optimal approximation for the problem (2) and
we prove in Section 2.3 that no finite element method can converge at a better
rate. Finally in Section 3 we design a finite element method that produces
approximations that satisfy the bound (3), showing that the optimal rate can
indeed be attained.

##  2 Optimal error estimates for elliptic problems

In this section we will first briefly recall the theory of optimal error
estimates for Galerkin approximations of well-posed second order elliptic
problems. We then consider the ill-posed model problem (2) and discuss how the
construction that led to optimal approximation in the well-posed case can be
adapted to this situation. This leads us to a definition of optimality of
approximate solutions in the ill-posed case. We let $V:=H^{1}(\Omega)$ and
$V_{0}:=H^{1}_{0}(\Omega)$.

For simplicity we consider the Poisson problem for $f\in V_{0}^{\prime}$:

$\left\\{\begin{array}[]{rcl}-\Delta u&=&f\mbox{ in }\Omega\\\ u&=&0\mbox{ on
}\partial\Omega.\end{array}\right.$ (4)

We define the associated weak formulation by: find $u\in V_{0}$ such that

$a(u,v)=\ell(v)\quad\forall v\in V_{0},$ (5)

where $a(\cdot,\cdot):=\int_{\Omega}\nabla u\cdot\nabla v~{}\mbox{d}x$ and
$\ell(v):=\int_{\Omega}fv~{}\mbox{d}x$. It is well known that $a$ is a
$V$-elliptic, continuous bilinear form on $V_{0}\times V_{0}$, and $\ell$ is
bounded and continuous on $V$.

It then follows from Lax-Milgram’s lemma LM54  that the weak formulation
admits a unique solution satisfying the stability estimate

$\|u\|_{V}\leq\|\ell\|_{{V_{0}^{\prime}}}$ (6)

where $\|\cdot\|_{V}:=a(\cdot,\cdot)$ and the dual norm is defined by

$\|\ell\|_{{V_{0}^{\prime}}}:=\sup_{v\in
V_{0}\setminus\\{0\\}}\frac{|\ell(v)|}{\|v\|_{V}}.$

Introducing a finite dimensional subspace $V_{0h}\subset V_{0}$ we define the
Galerkin method, find $u_{h}\in V_{0h}$ such that

$a(u_{h},v_{h})=\ell_{\delta}(v_{h})\quad\forall v_{h}\in V_{0h},$ (7)

where $\ell_{\delta}$ denotes a perturbed right hand side
$\ell_{\delta}(v)=\int_{\Omega}(f+\delta f)v~{}\mbox{d}x$ with $\delta
f\in{V_{0}^{\prime}}$ and we assume $\|\delta f\|_{{V_{0}^{\prime}}}$ known.
The associated linear system is invertible since $a$ is $V$-elliptic. We can
also define the so-called Ritz projection in the same fashion, for all $w\in
V_{0}$ there exists $r_{w}\in V_{0h}$ such that

$a(r_{w},v_{h})=a(w,v_{h})\quad\forall v_{h}\in V_{0h}.$

It follows from (6) that $\|r_{w}\|_{V}\leq\|w\|_{V}$. Consider the
approximation error $e=u-u_{h}$. By definition this satisfies the equation (5)
with the following right hand side

$\ell(v)=a(u-w_{h},v-r_{v})+(\delta
f,r_{v})_{\langle{V_{0}^{\prime}},V_{0}\rangle}\quad\forall w_{h}\in V_{0h}.$

Since $\|v-r_{v}\|_{V}\leq 2\|v\|_{V}$ we immediately have the bound

$\|\ell\|_{{V_{0}^{\prime}}}\leq 2\inf_{w_{h}\in
V_{0h}}\|\Delta(u-w_{h})\|_{{V_{0}^{\prime}}}+\|\delta
f\|_{{V_{0}^{\prime}}}.$

Applying this bound in (6) we get the error bound

$\|e\|_{V}\lesssim\inf_{w_{h}\in
V_{0h}}\|\Delta(u-w_{h})\|_{{V_{0}^{\prime}}}+\|\delta
f\|_{{V_{0}^{\prime}}},$ (8)

which is equivalent to the classical result of Cea’s lemma, but written in a
form suitable for our purposes. If $V_{0h}$ is the space of $H^{1}$-conforming
piecewise polynomial finite elements of order $k$ we immediately have by
approximation that

$\|e\|_{V}\lesssim h^{k}|u|_{H^{k+1}(\Omega)}+\|\delta
f\|_{{V_{0}^{\prime}}}.$

Observe how the Lipschitz stability of (6) combines with the approximation
properties of the finite element space to yield an optimal error estimate.
Perturbations in data lead to stagnation of the error at the level of the
perturbation.

###  2.1 Optimal three-ball estimate

We will consider only the two and three dimensional cases. We have the three-
ball estimate with explicit constants.

###### Theorem 2.1

Let $0<r_{1}<r_{2}<r_{3}$. Then for all harmonic functions $u$ there holds

$\|u\|_{L^{2}(B(r_{2}))}\leq\|u\|_{L^{2}(B(r_{1}))}^{\alpha}\|u\|_{L^{2}(B(r_{3}))}^{(1-\alpha)},$
(9)

where

$\displaystyle\alpha=\frac{\beta}{1+\beta},\quad\beta=\frac{\log(r_{3})-\log(r_{2})}{\log(r_{2})-\log(r_{1})}.$
(10)

Moreover, there does not exist $\tilde{\alpha}>\alpha$ such that

$\|u\|_{L^{2}(B(r_{2}))}\lesssim\|u\|_{L^{2}(B(r_{1}))}^{\tilde{\alpha}}\|u\|_{L^{2}(B(r_{3}))}^{(1-\tilde{\alpha})}.$
(11)

###### Proof

For any $r>0$ and $\theta\in(0,1)$ there holds

$\displaystyle\left\|u\right\|_{L^{2}(B_{r})}\leq\left\|u\right\|_{L^{2}(B_{\theta
r})}^{1/2}\left\|u\right\|_{L^{2}(B_{\theta^{-1}r})}^{1/2},$ (12)

see e.g. (kuusi2021, , Eq. (1.2)). We aim to transform this estimate into (9).
We take the logarithm of (12) and write
$f(t)=\log\left\|u\right\|_{L^{2}(B(\exp(t)))}$ to obtain

$\displaystyle f(\log(r))\leq\frac{1}{2}f(\log(\theta
r))+\frac{1}{2}f(\log(\theta^{-1}r)).$

Notice that $\log(\theta r)+\log(\theta^{-1}r)=2\log(r)$, so that writing
$t=\log(\theta r)$ and $s=\log(\theta^{-1}r)$, we obtain that

$\displaystyle f(\tfrac{1}{2}(s+t))\leq\tfrac{1}{2}(f(s)+f(t)),$ (13)

yielding convexity of $f$. Hence, for every $\alpha\in(0,1)$ and
$s,t\in\mathbb{R}$

$\displaystyle f(\alpha s+(1-\alpha)t)\leq\alpha f(s)+(1-\alpha)f(t).$ (14)

We now set $r=r_{2}$ and $\theta=r_{1}/r_{2}$. Then $r_{1}=\theta r$ and
$r_{3}=\theta^{-\beta}r$, with $\beta$ given by (10). Taking $s=\log(\theta
r)$ and $t=\log(\theta^{-\beta}r)$ there holds

$\displaystyle\alpha s+(1-\alpha)t$ $\displaystyle=\alpha\log\theta+\alpha\log
r-(1-\alpha)\beta\log\theta+(1-\alpha)\log r$
$\displaystyle=(\alpha-(1-\alpha)\beta)\log\theta+\log r=\log r,$

since $(1-\alpha)\beta=\alpha$. With this choice, taking the exponential of
(14) gives (9).

Suppose now that (11) holds for some $\tilde{\alpha}>0$. We will show that
$\tilde{\alpha}\leq\alpha$. Let us consider first the two dimensional case.
Identifying $\mathbb{R}^{2}$ with $\mathbb{C}$, the function $u(z)=z^{n-1}$ is
harmonic for $n\in\mathbb{N}$. Using polar coordinates we have that

$\displaystyle\lVert
u\rVert_{L^{2}(B(\rho))}^{2}=2\pi\int_{0}^{\rho}r^{2(n-1)+1}dr=c_{n}\rho^{2n},\quad
c_{n}=\frac{\pi}{n},$ (15)

and (11) gives

$\displaystyle 1\lesssim\theta^{n(\tilde{\alpha}-\beta(1-\tilde{\alpha}))}.$
(16)

As $n\in\mathbb{N}$ is arbitrary and $\theta\in(0,1)$ we must have
$\tilde{\alpha}-\beta(1-\tilde{\alpha})\leq 0$. In other words,

$\displaystyle\tilde{\alpha}\leq\frac{\beta}{1+\beta}=\alpha.$

We turn to the three dimensional case, and consider the function

$\displaystyle u(x^{1},x^{2},x^{3})=z^{n-1},\quad z=x^{1}+ix^{2}.$ (17)

As above, this is harmonic for $n\in\mathbb{N}$. Passing to spherical
coordinates there holds

$\displaystyle\lVert
u\rVert_{L^{2}(B(\rho))}^{2}=2\pi\int_{0}^{\pi}\int_{0}^{\rho}(r\sin\theta)^{2(n-1)+1}rdrd\theta=c_{n}\rho^{2n+1},$
(18)

where the constant $c_{n}$ can be written using the Gamma function

$\displaystyle c_{n}=\frac{2\pi^{3/2}\Gamma(n)}{(2n+1)\Gamma(n+1/2)}.$

The conclusion follows as in the two dimensional case.

###### Remark 1

In Theorem 2.1 we proved the optimality and continuous dependence of $\alpha$
for unique continuation of Laplace equation. A discussion of optimality of
three balls inequalities can be found in EFV06  for elliptic and parabolic
problems. In LNW10 ; LUW10  some cases in fluid mechanics and elasticity are
considered for which optimality is claimed.

###  2.2 Definition of optimal convergence for ill-posed problems with
conditional stability

In this section we will try to mimic the development in the well-posed case
for the problem (2) and point out where things go wrong. We will do this with
minimal reference to a particular approximation method to keep the discussion
general. However in Section 3 we introduce a method for which the programme
can be carried out. First we will derive a weak formulation. This time, since
no boundary conditions are set on $u$, we must consider the space $V$.

However to make form $a$ consistent with the problem the test space must be
chosen to be $V_{0}$, as keeping $V$ would imply a homogeneous Neumann
condition on the boundary. We may then write a weak formulation of the problem
(2), find $u\in V$ such that $u|_{\omega}=q$ and

$a(u,v)=0\quad\forall v\in V_{0}.$

We know that the exact solution satisfies this formulation and that (1) holds.
Assume now that we have an approximation $u_{h}\in V_{h}$ obtained using the
perturbed data $\tilde{q}=q+\delta q$, where $\delta q\in L^{2}(\omega)$.
Observe that although for this data, most likely, no exact solution will
exist, a discrete approximation of the unperturbed exact solution $u$ may
still be constructed. Similarly as before the error $e:=u-u_{h}$ satisfies

$a(e,v)=\ell_{h}(v)\quad\forall v\in V_{0}$

where

$\ell_{h}(v)=a(u_{h},v),\,\mbox{ with
}\|\ell_{h}(v)\|_{{V_{0}^{\prime}}}=\|\Delta u_{h}\|_{{V_{0}^{\prime}}}.$

Observe that even if $u_{h}$ is produced using a Galerkin procedure we can not
use here the Ritz projection trick as above to replace $u_{h}$ by an arbitrary
function in $V_{h}$, since the trial space in this case is bigger than the
test space.

As before we would now like to apply a stability estimate, this time (1),
using the right hand side on the perturbation. However this is not possible,
since there is no right hand side in (2) and (1). Instead we first decompose
$e=e_{0}+\tilde{e}$, where $e_{0}\in V_{0}$ solves the well-posed problem

$a(e_{0},v)=\ell_{h}(v)\quad\forall v\in V_{0}$

and $\tilde{e}$ solves (2) with $\tilde{e}|_{\omega}=e-e_{0}$. Using the
triangle inequality and then applying (6) to $e_{0}$ and (1) to $\tilde{e}$ we
arrive at

$\|e\|_{L^{2}(B)}\leq\|e_{0}\|_{V}+\|\tilde{e}\|_{L^{2}(B)}\lesssim\|\Delta
u_{h}\|_{{V_{0}^{\prime}}}+\|\tilde{e}\|^{\alpha}_{L^{2}(\omega)}\|\tilde{e}\|^{1-\alpha}_{L^{2}(\Omega)}.$

Using once again the triangle inequality this leads to

$\|\tilde{e}\|^{\alpha}_{L^{2}(\omega)}\|\tilde{e}\|^{1-\alpha}_{L^{2}(\Omega)}\lesssim(\|e\|_{L^{2}(\omega)}+\|\Delta
u_{h}\|_{{V_{0}^{\prime}}})^{\alpha}(\|e\|_{L^{2}(\Omega)}+\|\Delta
u_{h}\|_{{V_{0}^{\prime}}})^{1-\alpha}.$

We conclude that any approximation $u_{h}$ must satisfy the bound

$\|e\|_{L^{2}(B)}\lesssim\|\Delta
u_{h}\|_{{V_{0}^{\prime}}}+(\|e\|_{L^{2}(\omega)}+\|\Delta
u_{h}\|_{{V_{0}^{\prime}}})^{\alpha}(\|e\|_{L^{2}(\Omega)}+\|\Delta
u_{h}\|_{{V_{0}^{\prime}}})^{1-\alpha}\\\
\lesssim(\|q-u_{h}\|_{L^{2}(\omega)}+\|\Delta
u_{h}\|_{{V_{0}^{\prime}}})^{\alpha}(\|e\|_{L^{2}(\Omega)}+\|\Delta
u_{h}\|_{{V_{0}^{\prime}}})^{1-\alpha}.$ (19)

If we assume that the term $\|e\|_{L^{2}(\Omega)}$ is bounded, the inequality
(19) gives an a posteriori bound for the error in $L^{2}$. Observe that since
the data $q$ is associated to a solution $u\in H^{2}(\Omega)$, we only need a
bound on $\|u_{h}\|_{L^{2}(\Omega)}$.

For the sake of discussion we will, for a moment, consider an approximation
$u_{h}$ satisfying certain properties. These properties can be thought of as
design criteria for the numerical method, since as it turns out they lead to
optimal convergence. In Section 3 we construct a finite element method with
these properties.

  1. 1.

Bound on the equation residual:

$\|\Delta u_{h}\|_{{V_{0}^{\prime}}}\lesssim
Ch^{k}|u|_{H^{k+1}(\Omega)}+\|\delta q\|_{L^{2}(\omega)}.$ (20)

Observe that this means that the residual convergence is as good as the best
approximation of the residual.

  2. 2.

Bound on the data fitting term:

$\|q-u_{h}\|_{L^{2}(\omega)}\lesssim Ch^{k}|u|_{H^{k+1}(\Omega)}+\|\delta
q\|_{L^{2}(\omega)}/$ (21)

This term is suboptimal by one order in $h$ compared to interpolation, but
nothing can be gained by assuming better convergence since the term always is
dominated by the contribution from $\|\Delta u_{h}\|_{{V_{0}^{\prime}}}$ in
the bound (19). Strengthening the norm on $\omega$ on the other hand is
possible provided the perturbation $\delta q$ also has additional smoothness.

  3. 3.

Finally we need to assume an a priori bound on $u_{h}$:

$\|u_{h}\|_{L^{2}(\Omega)}\lesssim|u|_{H^{k+1}(\Omega))}+h^{-k}\|\delta
q\|_{L^{2}(\omega)}.$ (22)

The rationale for this choice is that it is the strongest control that can be
achieved through Tikhonov regularisation without affecting the convergence
order when the data is unperturbed, assuming that the previous two assumptions
hold.

Injecting these bounds in (19) we get the error estimate

$\|u-u_{h}\|_{L^{2}(B)}\lesssim h^{\alpha
k}\|u\|_{H^{k+1}(\Omega)}+h^{-(1-\alpha)k}\|\delta q\|_{L^{2}(\omega)}.$ (23)

Based on the discussion above we here propose a definition of what it means
that a sequence of approximations $\\{u_{h}\\}$ to an ill-posed problem of the
form (2) is optimally convergent.

###### Definition 1

(Optimality of approximation of ill-posed problems) Let $\\{u_{h}\\}$ be a
family of functions in $H^{1}(\Omega)$ parametrized by $h>0$. If the family
$\\{u_{h}\\}$ satisfies the inequality (23), with $\alpha$ the largest value
for which (1) holds, then we say that its convergence is optimal and that the
bound (23) is quasi-optimal.

###  2.3 Proof of optimality

In this section we will prove that, independently of the method used, for the
optimal $\alpha$ in the stability estimate (1), no sequence $u_{h}\in
H^{1}(\Omega)$ of approximations to the solution of the problem (2) can exceed
the convergence rate in (23), nor can it have a more favorable sensitivity to
data perturbations.

We start by proving a technical lemma.

###### Lemma 1

Let $r_{3}<r_{4}<R$ and $k\geq 0$. Then for all $w\in H^{k+1}(B(R))$
satisfying $\Delta w=0$ in $B(R)$ there holds

$\|w\|_{H^{k+1}(B(r_{3}))}\lesssim\|w\|_{L^{2}(B(r_{4}))}.$

###### Proof

Divide the interval $(r_{3},r_{4})$ in $k+1$ subintervals of equal length
$(R_{j},R_{j+1})$ with $R_{j}=r_{3}+j\delta R$, $R_{0}=r_{3}$,
$R_{k+1}=r_{4},\delta R=R_{j+1}-R_{j}=(r_{4}-r_{3})/(k+1)$. For an interval
$j\in[0,k]$ choose a $\chi\in C_{0}^{\infty}(B(R_{j+1}))$ such that $\chi=1$
in $B(R_{j})$ and write $v=\chi y$, where $y\in H^{1}(B(R_{j+1}))$ and $\Delta
y=0$. Then, if $[\Delta,\chi]$ denotes the commutator $\Delta\chi-\chi\Delta$
,

$\displaystyle\begin{cases}\Delta v=[\Delta,\chi]y&\text{in $B(R_{j+1})$},\\\
v|_{\partial B(R_{j+1})}=0,\end{cases}$

and therefore by (6) we have that

$\displaystyle\lVert y\rVert_{H^{1}(B(R_{j}))}$ $\displaystyle\leq\lVert
v\rVert_{H^{1}(B(R_{j+1}))}\leq\lVert\Delta v\rVert_{H^{-1}(B(R_{j+1}))}$ (24)
$\displaystyle\lesssim\lVert[\Delta,\chi]y\rVert_{H^{-1}(B(R_{j+1})}\lesssim\lVert
y\rVert_{L^{2}(B(R_{j+1}))}.$

Here in the last step we used that

$\displaystyle([\Delta,\chi]y,w)_{B(R_{j+1})}$
$\displaystyle=((\Delta\chi)y+2\nabla\chi\cdot\nabla y,w)_{B(R_{j+1})}$
$\displaystyle=-((\Delta\chi)y,w)_{B(R_{j+1})}-2(y,\nabla\chi\cdot\nabla
w)_{B(R_{j+1})}$ $\displaystyle\lesssim\lVert
y\rVert_{L^{2}(B(R_{j+1}))}\|w\|_{H^{1}(B(R_{j+1}))}.$

Let $y=D^{k-j}w$ where $D^{k-j}$ denotes an arbitrary partial derivative of
order $k-j$, $j=0,\ldots,k$. Then $\Delta y=0$. It follows from equation (24)
that

$\lVert y\rVert_{H^{1}(B(R_{j}))}\lesssim\lVert y\rVert_{L^{2}(B(R_{j+1}))}.$

By applying this to all partial derivatives of order $k-j$, we see that

$\lVert w\rVert_{H^{k+1-j}(B(R_{j}))}\lesssim\lVert
w\rVert_{H^{k-j}(B(R_{j+1}))}.$

Hence by applying this inequality sequentially for $j=0,\ldots,k$ we see that

$\lVert w\rVert_{H^{k+1}(B(r_{3}))}=\lVert
w\rVert_{H^{k+1}(B(R_{0}))}\lesssim\ldots\lesssim\lVert
w\rVert_{H^{1}(B(R_{k}))}\lesssim\lVert w\rVert_{L^{2}(B(r_{4}))}.$

This concludes the proof.

###### Theorem 2.2

Consider a family of mappings $F_{h}:L^{2}(\omega)\to H^{1}(\Omega)$
parametrized by $h>0$. Let $\alpha\in(0,1)$ be the optimal exponent in Theorem
2.1. Then there are no $\alpha_{1},\alpha_{2}\geq\alpha$ with
$\alpha_{j}>\alpha$ for $j=1$ or $j=2$, such that

$\displaystyle\lVert u-u_{h}\rVert_{L^{2}(B)}\lesssim h^{\alpha_{1}k}\lVert
u\rVert_{H^{k+1}(B(r_{3}))}+h^{(\alpha_{2}-1)k}\lVert\delta
q\rVert_{L^{2}(\omega)}$ (25)

for all harmonic functions $u$ and all $\delta q\in L^{2}(\omega)$. Here
$u_{h}=F_{h}(q+\delta q)$ and $q=u|_{\omega}$.

###### Proof

We give a proof by contradiction. Assume that there are
$\alpha_{1},\alpha_{2}\geq\alpha$, with $\alpha_{j}>\alpha$ for $j=1$ or
$j=2$, such that (25) holds. Taking $u=0$ and $\delta q=\tilde{u}|_{\omega}$
for $\tilde{u}$ satisfying $\Delta\tilde{u}=0$ in $B(R)$, the estimate (25)
reduces to

$\displaystyle\lVert F_{h}(\tilde{u}|_{\omega})\rVert_{L^{2}(B)}\lesssim
h^{(\alpha_{2}-1)k}\lVert\tilde{u}\rVert_{L^{2}(\omega)}.$

Using (25) again with $u=\tilde{u}$ and $\delta q=0$, we get

$\displaystyle\lVert\tilde{u}-F_{h}(\tilde{u}|_{\omega})\rVert_{L^{2}(B)}\lesssim
h^{\alpha_{1}k}\lVert\tilde{u}\rVert_{H^{k+1}(B(r_{3}))}.$

Hence

$\displaystyle\lVert\tilde{u}\rVert_{L^{2}(B)}$
$\displaystyle\leq\lVert\tilde{u}-F_{h}(\tilde{u}|_{\omega})\rVert_{L^{2}(B)}+\lVert
F_{h}(\tilde{u}|_{\omega})\rVert_{L^{2}(B)}$ (26) $\displaystyle\lesssim
h^{\alpha_{1}k}\lVert\tilde{u}\rVert_{H^{k+1}(B(r_{3}))}+h^{(\alpha_{2}-1)k}\lVert\tilde{u}\rVert_{L^{2}(\omega)}.$

We will write $u=\tilde{u}$ from now on, and recall that $u$ is an arbitrary
solution to $\Delta u=0$ in $B(R)$. In what follows, we will take
$\tilde{u}(z)=z^{n}$ for large integer $n$. The three dimensional case
understood as in (17). Then the ratio

$\displaystyle r=\frac{\lVert u\rVert_{L^{2}(\omega)}}{\lVert
u\rVert_{H^{k+1}(B(r_{3}))}}$

is small in view of (15) and (18). Then we choose $h>0$ so that

$\displaystyle h^{\alpha_{1}k}\lVert
u\rVert_{H^{k+1}(B(r_{3}))}=h^{(\alpha_{2}-1)k}\lVert
u\rVert_{L^{2}(\omega)},$

that is,

$\displaystyle h=r^{1/((\alpha_{1}+1-\alpha_{2})k)}.$

With this choice, (26) reduces to

$\displaystyle\lVert u\rVert_{L^{2}(B)}\lesssim\lVert
u\rVert_{L^{2}(\omega)}^{\tilde{\alpha}}\lVert
u\rVert_{H^{k+1}(B(r_{3}))}^{1-\tilde{\alpha}},\quad\text{where}\quad\tilde{\alpha}=\frac{\alpha_{1}}{1+\alpha_{1}-\alpha_{2}}.$
(27)

Let us show that $\tilde{\alpha}>\alpha$. Consider first the case
$\alpha_{1}<\alpha_{2}$. As $\alpha_{j}\in[\alpha,1)$, $j=1,2$, there holds
$\alpha_{2}-\alpha_{1}\in(0,1)$ and

$\displaystyle\tilde{\alpha}\geq\frac{\alpha}{1-(\alpha_{2}-\alpha_{1})}>\alpha.$

Let us now turn to the case $\alpha_{1}\geq\alpha_{2}$. Then
$\alpha_{1}=\alpha+\epsilon$ for some $\epsilon>0$, and

$\displaystyle\tilde{\alpha}-\alpha\geq\frac{\alpha+\epsilon}{1+\epsilon}-\alpha=\frac{(1-\alpha)\epsilon}{1+\epsilon}>0.$

We have shown that $\tilde{\alpha}>\alpha$.

Observe that (27) would right away contradict the optimality of (1) if the
$H^{k+1}$-norm on its right-hand side was an $L^{2}$-norm. Let
$r_{3}<r_{4}<R$. Applying Lemma 1 we see that $\|u\|_{H^{k+1}(B(r_{3}))}\leq
C\|u\|_{L^{2}(B(r_{4}))}$ and hence, using this bound in (27) leads to

$\displaystyle\lVert u\rVert_{L^{2}(B)}\lesssim\lVert
u\rVert_{L^{2}(\omega)}^{\tilde{\alpha}}\lVert
u\rVert_{L^{2}(B(r_{4}))}^{1-\tilde{\alpha}}.$ (28)

In view of (10), the optimal exponent in (9) depends continuously on $r_{3}$.
Hence (28) is in contradiction with (9) when $r_{4}>r_{3}$ is sufficiently
close to $r_{3}$.

##  3 Primal-dual finite element methods with weakly consistent regularisation

In this section we will use a finite element method with weakly consistent
stabilisation to construct a sequence of approximate solutions that satisfy
(23), showing that the optimal convergence can be attained by a discrete
approximation method. This discussion is based on ideas from Bu16 ; BHL18 ,
modified to match the assumptions of the theoretical developments above. Let
$\\{\mathcal{T}\\}$ be a quasi-uniform family of triangulations of $\Omega$,
where triangles with curved boundaries are allowed so that the the covering of
$\Omega$ is exact Zlamal70 ; Bern89 .

On these meshes we define a $C^{0}$ finite element space $V_{h}\in
H^{1}(\Omega)$, consisting of piecewise polynomials of order $k$ (after
mapping of the triangles to a reference element). We also let
$V_{0h}=V_{h}\cap H^{1}_{0}(\Omega)$. It then follows that there exist
interpolants $\Pi_{h}:H^{1}(\Omega)\mapsto V_{h}$ (Bern89, , Corollary 4.1)
and $\Pi_{h}^{0}:H^{1}_{0}(\Omega)\mapsto V_{0h}$ (Bern89, , Corollary 5.2)
for which the following interpolation estimates hold

$\|u-\Pi_{h}u\|_{T}+h\|\nabla(u-\Pi_{h}u)\|_{T}+h^{2}\|D^{2}(u-\Pi_{h}u)\|_{T}\lesssim
h^{k+1}|u|_{H^{k+1}(\Delta_{T})},$ (29)

where $\Delta_{T}:=\\{T^{\prime}\in\mathcal{T}:T^{\prime}\cap
T\neq\emptyset\\}$ and $D^{2}$ is the standard multi index notation for the
partial derivatives of second order, and

$\|w-\Pi^{0}_{h}w\|_{L^{2}(\Omega)}+h\|\Pi_{h}^{0}w\|_{V}\lesssim h\|w\|_{V}.$
(30)

We will also use the broken norm defined by

$\|v\|_{\mathcal{T}}:=\left(\sum_{T\in\mathcal{T}}\|v\|_{T}^{2}\right)^{\frac{1}{2}}.$

We define the finite element method: find $(u_{h},z_{h})\in V_{h}\times
V_{0h}$ such that

$\displaystyle a(u_{h},w_{h})-a(z_{h},w_{h})$ $\displaystyle=0$ (31)
$\displaystyle a(v_{h},z_{h})+s(u_{h},v_{h})+(u_{h},v_{h})_{L^{2}(\omega)}$
$\displaystyle=(\tilde{q},v_{h})_{L^{2}(\omega)}$

for all $(v_{h},w_{h})\in V_{h}\times V_{0h}$, with

$s(u_{h},v_{h}):=\sum_{T\in\mathcal{T}}\left((h_{T}^{2}\Delta u_{h},\Delta
v_{h})_{T}+\sum_{F\in\partial T}(h_{T}\llbracket\nabla
u_{h}\rrbracket_{F},\llbracket\nabla
v_{h}\rrbracket_{F})_{F\setminus\partial\Omega}\right)\\\
+h^{2k}(u_{h},v_{h})_{L^{2}(\Omega)}$ (32)

where $F$ denotes a face of a triangle $T$ and the jump of the gradient over a
face $F$ is defined by $\llbracket\nabla u_{h}\rrbracket_{F}:=\nabla
u_{h}|_{T_{1}}n_{T_{1}}+\nabla u_{h}|_{T_{2}}n_{T_{2}}$ for
$F=\bar{T}_{1}\cap\bar{T}_{2}$, with $n_{T_{m}}$ the outward pointing unit
normal of the triangle $T_{m}$. For a more compact formulation we introduce
the global form $A_{h}$,

$A_{h}[(x_{h},y_{h}),(v_{h},w_{h})]:=a(x_{h},w_{h})-a(y_{h},w_{h})+a(v_{h},y_{h})+s(x_{h},v_{h})+(x_{h},v_{h})_{L^{2}(\omega)}$

to write: find $(u_{h},z_{h})\in V_{h}\times V_{0h}$ such that

$A_{h}[(u_{h},z_{h}),(v_{h},w_{h})]=(\tilde{q},v_{h})_{L^{2}(\omega)}$ (33)

for all $(v_{h},w_{h})\in V_{h}\times V_{0h}$. Observe that this form
satisfies the consistency property

$A_{h}[(u-u_{h},-z_{h}),(v_{h},w_{h})]=h^{2k}(u,v_{h})-(\delta
q,v_{h})_{L^{2}(\omega)}.$ (34)

To show that this method satisfies the error bound (23), we only need to
verify that it satisfies (20), (21) and (22). To this end we introduce the
norm

$|\\!|\\!|(v_{h},w_{h})|\\!|\\!|_{S}^{2}:=s(v_{h},v_{h})+\|w_{h}\|^{2}_{V}+\|v_{h}\|^{2}_{L^{2}(\omega)}$

and we observe that the formulation satisfies the positivity property

$|\\!|\\!|(u_{h},z_{h})|\\!|\\!|_{S}^{2}=A_{h}[(u_{h},z_{h}),(u_{h},-z_{h})]$
(35)

which ensures the existence of a discrete solution $(u_{h},z_{h})\in
V_{h}\times V_{0h}$ for all $h>0$.

We proceed by first proving convergence in the $S$-norm, which immediately
gives (21). The proof of the other two bounds and satisfaction of (23) then
follow as a corollary. First we establish an approximation result for the $S$
norm.

###### Lemma 2

Let $v\in H^{k+1}(\Omega)$ then there holds

$|\\!|\\!|(v-\Pi_{h}v,0)|\\!|\\!|_{S}\lesssim h^{k}\|v\|_{H^{k+1}(\Omega)}.$

###### Proof

By the definition of the $S$-norm we see that

$|\\!|\\!|(v-\Pi_{h}v,0)|\\!|\\!|_{S}^{2}=\|h\Delta(v-\Pi_{h}v)\|^{2}_{\mathcal{T}}+\sum_{T\in\mathcal{T}}\sum_{F\in\partial
T\setminus\partial\Omega}h_{T}\|\llbracket\nabla\Pi_{h}v\rrbracket_{F}\|^{2}_{F}\\\
+h^{2k}\|v-\Pi_{h}v\|_{L^{2}(\Omega)}^{2}+\|v-\Pi_{h}v\|^{2}_{L^{2}(\omega)}.$

By the approximation property (29) we see that

$\|h\Delta(v-\Pi_{h}v)\|^{2}_{\mathcal{T}}+h^{2k}\|v-\Pi_{h}v\|_{L^{2}(\Omega)}^{2}+\|v-\Pi_{h}v\|^{2}_{L^{2}(\omega)}\lesssim
h^{2k}|v|_{H^{k+1}(\Omega)}.$

For the term measuring the jump of $\Pi_{h}v$ over element faces we note that

$\|\llbracket\nabla\Pi_{h}v\rrbracket_{F}\|^{2}_{F}\leq\|\llbracket\nabla(v-\Pi_{h}v)\rrbracket_{F}\|^{2}_{F}\\\
\leq h^{-1}\|\nabla(v-\Pi_{h}v)\|^{2}_{T_{1}\cup
T_{2}}+h\|D^{2}(v-\Pi_{h}v)\|^{2}_{T_{1}\cup T_{2}}$

where we used the regularity of $v$ and the trace inequality MS99

$\|v\|_{\partial T}\lesssim h^{-\frac{1}{2}}\|v\|_{T}+h^{\frac{1}{2}}\|\nabla
v\|_{T},\quad\forall v\in H^{1}(T).$

We conclude by applying (29) once again and summing over all the faces.

###### Proposition 1

Let $(u_{h},z_{h})$ denote the solution to (33) and let $u\in H^{k+1}(\Omega)$
be the solution to (2) then there holds

$|\\!|\\!|(u-u_{h},z_{h})|\\!|\\!|_{S}\lesssim
h^{k}\|u\|_{H^{k+1}(\Omega)}+\|\delta q\|_{L^{2}(\omega)}.$

###### Proof

First we decompose the error in the continuous and discrete part
$u-u_{h}=u-\Pi_{h}u+\underbrace{\Pi_{h}u-u_{h}}_{e_{h}}$. By the triangle
inequality and Lemma 2 it is enough to bound
$|\\!|\\!|(e_{h},z_{h})|\\!|\\!|_{S}$. Using (35) and (34) we have

$|\\!|\\!|(e_{h},z_{h})|\\!|\\!|_{S}^{2}=A_{h}[(e_{h},-z_{h}),(e_{h},z_{h})]=A_{h}[(\Pi_{h}u-u,0),(e_{h},z_{h})]\\\
-(\delta q,e_{h})_{L^{2}(\omega)}+h^{2k}(u,e_{h})_{L^{2}(\Omega)}.$

For the last two terms on the right hand side we have

$-(\delta
q,e_{h})_{L^{2}(\omega)}+h^{2k}(u,e_{h})_{L^{2}(\Omega)}\leq(\|\delta
q\|_{L^{2}(\omega)}+h^{k}\|u\|_{L^{2}(\Omega)})|\\!|\\!|(e_{h},0)|\\!|\\!|_{S}.$

Finally, the following continuity holds

$A_{h}[(\Pi_{h}u-u,0),(e_{h},z_{h})]\lesssim\|\Pi_{h}u-u\|_{*}|\\!|\\!|(e_{h},z_{h})|\\!|\\!|_{S}$
(36)

where

$\|v\|_{*}:=\|v\|_{V}+|\\!|\\!|v|\\!|\\!|_{S}.$

To prove the continuity (36) recall that by definition

$A_{h}[(\Pi_{h}u-u,0),(e_{h},z_{h})]=a(\Pi_{h}u-u,z_{h})+s(\Pi_{h}u-u,e_{h})+(\Pi_{h}u-u,e_{h})_{L^{2}(\omega)}.$

Using the Cauchy-Schwarz inequality we have

$a(\Pi_{h}u-u,z_{h})\leq\|\Pi_{h}u-u\|_{V}|\\!|\\!|(0,z_{h})|\\!|\\!|_{S}$

and

$s(\Pi_{h}u-u,e_{h})+(\Pi_{h}u-u,e_{h})_{L^{2}(\omega)}\leq|\\!|\\!|(\Pi_{h}u-u,0)|\\!|\\!|_{S}|\\!|\\!|(e_{h},0)|\\!|\\!|_{S}.$

We end the proof by observing that by equation (29) and Lemma 2 there holds

$\|\Pi_{h}u-u\|_{*}\lesssim h^{k}|u|_{H^{k+1}(\Omega)}.$

###### Corollary 1

Under the same hypothesis as for Proposition 1 there holds

$\|u_{h}\|_{L^{2}(\Omega)}\lesssim\|u\|_{H^{k+1}(\Omega)}+h^{-k}\|\delta
q\|_{L^{2}(\omega)}$

and

$\|\Delta u_{h}\|_{H^{-1}(\Omega)}\lesssim
h^{k}\|u\|_{H^{k+1}(\Omega)}+\|\delta q\|_{L^{2}(\omega)}.$

Finally $u_{h}$ satisfies the bound (23).

###### Proof

First we observe that the third claim is an immediate consequence of the two
first and Proposition 1. This follows from the discussion of Section 2.2 and
equations (19) - (22).

The first inequality is immediate by Proposition 1 observing that

$\|u_{h}\|_{L^{2}(\Omega)}\leq\|u-u_{h}\|_{L^{2}(\Omega)}+\|u\|_{L^{2}(\Omega)}$

and for the first term in the right hand side,

$\|u-u_{h}\|_{L^{2}(\Omega)}\leq
h^{-k}|\\!|\\!|u-u_{h},0)|\\!|\\!|_{S}\lesssim\|u\|_{H^{k+1}(\Omega)}+h^{-k}\|\delta
q\|_{L^{2}(\omega)}.$

For the second inequality by definition

$\|\Delta u_{h}\|_{H^{-1}(\Omega)}=\sup_{w\in
V_{0}\setminus\\{0\\}}\frac{a(u_{h},w)}{\|w\|_{V}}.$

Using (34), followed by integration by parts, we see that for all $w_{h}\in
V_{0h}$

$a(u_{h},w)=a(u_{h}-u,w)=a(u_{h}-u,w-w_{h})+a(z_{h},w_{h})\\\
=\sum_{T\in\mathcal{T}}\left(-(\Delta(u_{h}-u),w-w_{h})_{L^{2}(T)}+(\llbracket\nabla
u_{h}\rrbracket_{F},w-w_{h})_{L^{2}(\partial
T\setminus\partial\Omega)}\right)+a(z_{h},w_{h}).$

Choosing $w_{h}=\Pi^{0}_{h}w$ and using the Cauchy-Schwarz inequality in the
first term of the right hand side and the continuity of $a$ in the second,
followed by (30), we see that

$\sum_{T\in\mathcal{T}}\left(-(\Delta(u_{h}-u),w-w_{h})_{L^{2}(T)}+(\llbracket\nabla
u_{h}\rrbracket_{F},w-w_{h})_{L^{2}(\partial
T\setminus\partial\Omega)}\right)+a(z_{h},w_{h})\\\
\lesssim|\\!|\\!|(u_{h}-u,z_{h})|\\!|\\!|_{S}\|w\|_{V}.$

The conclusion now follows using Proposition 1 to obtain the desired bound

$\|\Delta u_{h}\|_{H^{-1}(\Omega)}=\sup_{w\in
V_{0}\setminus\\{0\\}}\frac{a(u_{h},w)}{\|w\|_{V}}\lesssim
h^{k}\|u\|_{H^{k+1}(\Omega)}+\|\delta q\|_{L^{2}(\omega)}.$

###### Remark 2

Both for the well-posed problem and the ill-posed problem there is a lower
bound for how well the exact solution can be approximated if the data are
perturbed. In the well-posed case the limit is trivially given by $\|\delta
q\|_{L^{2}(\omega)}$, whereas in the ill-posed case the lower bound occurs
when the approximation error term and the perturbation term are equal, that
is,

$h^{\alpha k}\|u\|_{H^{k+1}(\Omega)}=h^{(\alpha-1)k}\|\delta
q\|_{L^{2}(\omega)}.$

This gives a theoretical lower bound on $h$,

$h_{min}=(\|\delta q\|_{L^{2}(\omega)}/\|u\|_{H^{k+1}(\Omega)})^{1/k}.$

If $h_{min}$ is known the numerical scheme can be designed to stagnate at the
level of the best approximation, by modifying the last term in the definition
of the stabilisation (32) to read
$\max(h,h_{min})^{2k}(u_{h},v_{h})_{L^{2}(\Omega)}$. It is straighforward to
show that this leads to stagnation at

$\|u-u_{h}\|_{L^{2}(B)}\lesssim h_{min}^{\alpha
k}\|u\|_{H^{k+1}(\Omega)}=\|\delta
q\|_{L^{2}(\omega)}^{\alpha}\|u\|_{H^{k+1}(\Omega)}^{1-\alpha}.$

Here the implicit constant may depend on $k$.

##  4 Conclusion

In this paper we have shown that the convergence order of the approximation
error for unique continuation problems, obtained by combining the
approximation orders of the data fitting and the pde-residual with the
conditional stability, can not be improved. This shows that the asymptotic
accuracy of the methods for unique continuation discussed in Bu14b ; Bu16 ;
BHL18 ; BLO18 ; BNO19 ; BNO20a ; DMS23  is optimal, in the sense that it is
impossible to design a method with better convergence properties. Indeed no
$H^{1}$-conforming sequence based on an approximation space with similar
properties can converge faster. The only remaining possibilities to enhance
the accuracy of approximation methods is either to resort to adaptivity, or to
introduce some additional a priori assumption, such as finite dimensionality
of target quantities (see burman2023finite ).

## References

  * (1) Armstrong, S., Kuusi, T., Smart, C.: Optimal unique continuation for periodic elliptic equations on large scales (2021).  Preprint arXiv 2107.14248
  * (2) Babuška, I.: Error-bounds for finite element method.  Numer. Math. 16, 322–333 (1970/71).  DOI 10.1007/BF02165003.  URL https://doi.org/10.1007/BF02165003
  * (3) Bernardi, C.: Optimal finite-element interpolation on curved domains.  SIAM J. Numer. Anal. 26(5), 1212–1240 (1989).  DOI 10.1137/0726068.  URL https://doi.org/10.1137/0726068
  * (4) Boulakia, M., Burman, E., Fernández, M.A., Voisembert, C.: Data assimilation finite element method for the linearized Navie-Stokes equations in the low Reynolds regime.  Inverse Problems 36(8), 085003–85024 (2020).  DOI 10.1088/1361-6420/ab9161.  URL https://doi.org/10.1088/1361-6420/ab9161
  * (5) Bourgeois, L.: A mixed formulation of quasi-reversibility to solve the Cauchy problem for Laplace’s equation.  Inverse Problems 21(3), 1087–1104 (2005).  DOI 10.1088/0266-5611/21/3/018.  URL https://doi.org/10.1088/0266-5611/21/3/018
  * (6) Bourgeois, L., Recoquillay, A.: A mixed formulation of the Tikhonov regularization and its application to inverse PDE problems.  ESAIM Math. Model. Numer. Anal. 52(1), 123–145 (2018).  DOI 10.1051/m2an/2018008.  URL https://doi.org/10.1051/m2an/2018008
  * (7) Burman, E.: Stabilized finite element methods for nonsymmetric, noncoercive, and ill-posed problems. Part I: Elliptic equations.  SIAM J. Sci. Comput. 35(6), A2752–A2780 (2013).  DOI 10.1137/130916862.  URL http://dx.doi.org/10.1137/130916862
  * (8) Burman, E.: Error estimates for stabilized finite element methods applied to ill-posed problems.  C. R. Math. Acad. Sci. Paris 352(7-8), 655–659 (2014).  DOI 10.1016/j.crma.2014.06.008.  URL http://dx.doi.org/10.1016/j.crma.2014.06.008
  * (9) Burman, E.: Stabilised finite element methods for ill-posed problems with conditional stability.  In: Building bridges: connections and challenges in modern approaches to numerical partial differential equations, _Lect. Notes Comput. Sci. Eng._ , vol. 114, pp. 93–127. Springer, [Cham] (2016)
  * (10) Burman, E., Feizmohammadi, A., Oksanen, L.: A finite element data assimilation method for the wave equation.  Math. Comp. 89(324), 1681–1709 (2020).  DOI 10.1090/mcom/3508.  URL https://doi.org/10.1090/mcom/3508
  * (11) Burman, E., Hansbo, P.: Stabilized nonconforming finite element methods for data assimilation in incompressible flows.  Math. Comp. 87(311), 1029–1050 (2018).  DOI 10.1090/mcom/3255.  URL https://doi.org/10.1090/mcom/3255
  * (12) Burman, E., Hansbo, P., Larson, M.G.: Solving ill-posed control problems by stabilized finite element methods: an alternative to Tikhonov regularization.  Inverse Problems 34(3), 035004, 36 (2018).  DOI 10.1088/1361-6420/aaa32b.  URL https://doi.org/10.1088/1361-6420/aaa32b
  * (13) Burman, E., Larson, M.G., Oksanen, L.: Primal-dual mixed finite element methods for the elliptic Cauchy problem.  SIAM J. Numer. Anal. 56(6), 3480–3509 (2018).  DOI 10.1137/17M1163335.  URL https://doi.org/10.1137/17M1163335
  * (14) Burman, E., Nechita, M., Oksanen, L.: Unique continuation for the Helmholtz equation using stabilized finite element methods.  J. Math. Pures Appl. (9) 129, 1–22 (2019).  DOI 10.1016/j.matpur.2018.10.003.  URL https://doi.org/10.1016/j.matpur.2018.10.003
  * (15) Burman, E., Nechita, M., Oksanen, L.: A stabilized finite element method for inverse problems subject to the convection-diffusion equation. I: diffusion-dominated regime.  Numer. Math. 144(3), 451–477 (2020).  DOI 10.1007/s00211-019-01087-x.  URL https://doi.org/10.1007/s00211-019-01087-x
  * (16) Burman, E., Oksanen, L.: Data assimilation for the heat equation using stabilized finite element methods.  Numer. Math. 139(3), 505–528 (2018).  DOI 10.1007/s00211-018-0949-3.  URL https://doi.org/10.1007/s00211-018-0949-3
  * (17) Burman, E., Oksanen, L.: Finite element approximation of unique continuation of functions with finite dimensional trace (2023).  Preprint arXiv 2305.06800
  * (18) Céa, J.: Approximation variationnelle des problèmes aux limites.  Ann. Inst. Fourier (Grenoble) 14(fasc. 2), 345–444 (1964)
  * (19) Dahmen, W., Monsuur, H., Stevenson, R.: Least squares solvers for ill-posed PDEs that are conditionally stable.  ESAIM Math. Model. Numer. Anal. 57(4), 2227–2255 (2023).  DOI 10.1051/m2an/2023050.  URL https://doi.org/10.1051/m2an/2023050
  * (20) Engl, H.W.: Regularization by least-squares collocation.  In: Numerical treatment of inverse problems in differential and integral equations (Heidelberg, 1982), _Progr. Sci. Comput._ , vol. 2, pp. 345–354. Birkhäuser Boston, Boston, MA (1983)
  * (21) Engl, H.W., Neubauer, A.: On projection methods for solving linear ill-posed problems.  In: Model optimization in exploration geophysics (Berlin, 1986), _Theory Practice Appl. Geophys._ , vol. 1, pp. 73–92. Friedr. Vieweg, Braunschweig (1987)
  * (22) Engl, H.W., Neubauer, A.: Convergence rates for Tikhonov regularization in finite-dimensional subspaces of Hilbert scales.  Proc. Amer. Math. Soc. 102(3), 587–592 (1988).  DOI 10.2307/2047228.  URL https://doi.org/10.2307/2047228
  * (23) Escauriaza, L., Fernández, F.J., Vessella, S.: Doubling properties of caloric functions.  Appl. Anal. 85(1-3), 205–223 (2006).  DOI 10.1080/00036810500277082.  URL https://doi.org/10.1080/00036810500277082
  * (24) Hämarik, U., Avi, E., Ganina, A.: On the solution of ill-posed problems by projection methods with a posteriori choice of the discretization level.  Math. Model. Anal. 7(2), 241–252 (2002)
  * (25) Helfrich, H.P.: Optimale lineare Approximation beschränkter Mengen in normierten Räumen.  J. Approximation Theory 4, 165–182 (1971).  DOI 10.1016/0021-9045(71)90027-x.  URL https://doi.org/10.1016/0021-9045(71)90027-x
  * (26) Ito, K., Jin, B.: Inverse problems, _Series on Applied Mathematics_ , vol. 22.  World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ (2015).  Tikhonov theory and algorithms
  * (27) John, F.: Continuous dependence on data for solutions of partial differential equations with a prescribed bound.  Comm. Pure Appl. Math. 13, 551–585 (1960)
  * (28) Kaltenbacher, B.: Regularization by projection with a posteriori discretization level choice for linear and nonlinear ill-posed problems.  Inverse Problems 16(5), 1523–1539 (2000).  DOI 10.1088/0266-5611/16/5/322.  URL https://doi.org/10.1088/0266-5611/16/5/322
  * (29) Lattès, R., Lions, J.L.: The method of quasi-reversibility. Applications to partial differential equations.  Translated from the French edition and edited by Richard Bellman. Modern Analytic and Computational Methods in Science and Mathematics, No. 18. American Elsevier Publishing Co., Inc., New York (1969)
  * (30) Lax, P.D., Milgram, A.N.: Parabolic equations.  In: Contributions to the theory of partial differential equations, Annals of Mathematics Studies, no. 33, pp. 167–190. Princeton University Press, Princeton, N. J. (1954)
  * (31) Lin, C.L., Nakamura, G., Wang, J.N.: Optimal three-ball inequalities and quantitative uniqueness for the Lamé system with Lipschitz coefficients.  Duke Math. J. 155(1), 189–204 (2010).  DOI 10.1215/00127094-2010-054.  URL https://doi.org/10.1215/00127094-2010-054
  * (32) Lin, C.L., Uhlmann, G., Wang, J.N.: Optimal three-ball inequalities and quantitative uniqueness for the Stokes system.  Discrete Contin. Dyn. Syst. 28(3), 1273–1290 (2010).  DOI 10.3934/dcds.2010.28.1273.  URL https://doi.org/10.3934/dcds.2010.28.1273
  * (33) Lukas, M.A.: Convergence rates for regularized solutions.  Math. Comp. 51(183), 107–131 (1988).  DOI 10.2307/2008582.  URL https://doi.org/10.2307/2008582
  * (34) Mathé, P., Pereverzev, S.V.: Optimal discretization of inverse problems in Hilbert scales. Regularization and self-regularization of projection methods.  SIAM J. Numer. Anal. 38(6), 1999–2021 (2001).  DOI 10.1137/S003614299936175X.  URL https://doi.org/10.1137/S003614299936175X
  * (35) Miller, K.: Stabilized quasi-reversibility and other nearly-best-possible methods for non-well-posed problems.  In: Symposium on Non-Well-Posed Problems and Logarithmic Convexity (Heriot-Watt Univ., Edinburgh, 1972), pp. 161–176. Lecture Notes in Math., Vol. 316 (1973)
  * (36) Monk, P., Süli, E.: The adaptive computation of far-field patterns by a posteriori error estimation of linear functionals.  SIAM J. Numer. Anal. 36(1), 251–274 (1999).  DOI 10.1137/S0036142997315172.  URL http://dx.doi.org/10.1137/S0036142997315172
  * (37) Natterer, F.: The finite element method for ill-posed problems.  RAIRO Anal. Numér. 11(3), 271–278 (1977).  DOI 10.1051/m2an/1977110302711.  URL https://doi.org/10.1051/m2an/1977110302711
  * (38) Natterer, F.: Regularisierung schlecht gestellter Probleme durch Projektionsverfahren.  Numer. Math. 28(3), 329–341 (1977).  DOI 10.1007/BF01389972.  URL https://doi.org/10.1007/BF01389972
  * (39) Natterer, F.: Error bounds for Tikhonov regularization in Hilbert scales.  Applicable Anal. 18(1-2), 29–37 (1984).  DOI 10.1080/00036818408839508.  URL https://doi.org/10.1080/00036818408839508
  * (40) Nitsche, J.: Lineare Spline-Funktionen und die Methoden von Ritz für elliptische Randwertprobleme.  Arch. Rational Mech. Anal. 36, 348–355 (1970).  DOI 10.1007/BF00282271.  URL https://doi.org/10.1007/BF00282271
  * (41) Tikhonov, A.N., Arsenin, V.Y.: Solutions of ill-posed problems.  V. H. Winston & Sons, Washington, D.C.: John Wiley & Sons, New York-Toronto, Ont.-London (1977).  Translated from the Russian, Preface by translation editor Fritz John, Scripta Series in Mathematics
  * (42) Zlámal, M.: On the finite element method.  Numer. Math. 12, 394–409 (1968).  DOI 10.1007/BF02161362.  URL https://doi.org/10.1007/BF02161362
  * (43) Zlámal, M.: Curved elements in the finite element method. I.  SIAM J. Numer. Anal. 10, 229–240 (1973).  DOI 10.1137/0710022.  URL https://doi.org/10.1137/0710022


# Degenerate Turán densities of sparse hypergraphs II:
a solution to the Brown-Erdős-Sós problem for every uniformity

Chong Shangguan111Research Center for Mathematics and Interdisciplinary
Sciences, Shandong University, Qingdao 266237, China. Email:
<EMAIL_ADDRESS>
###### Abstract

For fixed integers $r\geq 3,e\geq 3$, and $v\geq r+1$, let $f_{r}(n,v,e)$
denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in
which the union of arbitrary $e$ distinct edges contains at least $v+1$
vertices. In 1973, Brown, Erdős and Sós proved that
$f_{r}(n,er-(e-1)k,e)=\Theta(n^{k})$ and conjectured that the limit
$\lim_{n\rightarrow\infty}\frac{f_{3}(n,e+2,e)}{n^{2}}$ always exists for all
fixed integers $e\geq 3$. In 2020 Shangguan and Tamo conjectured that the
limit $\lim_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}$ always
exists for all fixed integers $r>k\geq 2$ and $e\geq 3$, which contains the
BES conjecture as a special case for $r=3,k=2$. Recently, based on a result of
Glock, Joos, Kim, Kühn, Lichev, and Pikhurko, Delcourt and Postle proved the
BES conjecture. Extending their result, we show that the limit
$\lim_{n\rightarrow\infty}\frac{f_{r}(n,er-2(e-1),e)}{n^{2}}$ always exists,
thereby proving the BES conjecture for every uniformity.

##  1 Introduction

We will focus on the sparse hypergraph problem introduced by Brown, Erdős and
Sós [2] in 1973. To move forward, we will begin with some notations.

For an integer $r\geq 2$, an $r$-uniform hypergraph $\mathcal{H}$ (or
$r$-graph, for short) on the vertex set $V(\mathcal{H})$, is a family of
$r$-element subsets of $V(\mathcal{H})$, called the edges of $\mathcal{H}$.
For fixed integers $r\geq 3,e\geq 3$, and $v\geq r+1$, an $r$-graph
$\mathcal{H}$ is called $\mathscr{G}_{r}(v,e)$-free if the union of arbitrary
$e$ distinct edges of it contains at least $v+1$ vertices, namely, for
arbitrary distinct $A_{1},\ldots,A_{e}\in\mathcal{H}$ one has
$|\cup_{i=1}^{e}A_{i}|\geq v+1$. Due to the sparsity of its edges, such
$r$-graphs are also termed sparse hypergraphs [8]. Let $f_{r}(n,v,e)$ denote
the maximum number of edges in an $n$-vertex $\mathscr{G}_{r}(v,e)$-free
$r$-graph.

In 1973, Brown, Erdős and Sós [2] initiated the study of the function
$f_{r}(n,v,e)$, which has attracted considerable attention throughout the
years. More concretely, they showed that

$\displaystyle\Omega(n^{\frac{er-v}{e-1}})=f_{r}(n,v,e)=O(n^{\lceil\frac{er-v}{e-1}\rceil}).$
(1)

Improvements on lower or upper bounds of (1) for less general parameters were
obtained in a series of works, see, e.g. [1, 2, 3, 7, 9, 10, 13, 15, 17, 16,
18, 19, 20, 21].

In this paper we are interested in the special case where
$k=\frac{er-v}{e-1}\in\\{1,\ldots,r-1\\}$ is an integer. For $k=1$ the authors
of [11] (see also [6] (4) for the case $r=2$) noted that

$\displaystyle\lim_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1),e)}{n}=\frac{(e-1)n}{(e-1)(r-1)+1}.$
(2)

According to (1) it is easy to see that

$\displaystyle f_{r}(n,er-(e-1)k,e)=\Theta(n^{k}),$ (3)

and it is natural to ask whether the limit

$\lim_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}$

exists. For $e=2$ the above question is completely resolved by a classical
result of Rödl [14]. So we will focus on the case $e\geq 3$. For $e\geq
3,r=3,k=2$, Brown, Erdős and Sós [2] posed the following conjecture:

######  Conjecture 1 (see Section 5 in [2]).

The limit $\lim_{n\rightarrow\infty}\frac{f_{3}(n,e+2,e)}{n^{2}}$ exists for
every fixed $e\geq 3$.

In 2019 Glock [10] solved the $e=3$ case of 1 by showing that
$\lim_{n\rightarrow\infty}\frac{f_{3}(n,5,3)}{n^{2}}=\frac{1}{5}$. In a recent
work, Glock, Joos, Kim, Kühn, Lichev, and Pikhurko [11] solved the $e=4$ case
of 1 by showing that
$\lim_{n\rightarrow\infty}\frac{f_{3}(n,6,4)}{n^{2}}=\frac{7}{36}$. Quite
recently, based on a result of [11] Delcourt and Postle [5] solved 1 in the
full generality, without determining the limit precisely.

In the spirit of (3) and Conjecture 1 Shangguan and Tamo [18] posed the
following conjecture, which largely generalizes 1:

######  Conjecture 2 (see Question 2 in [18]).

The limit $\lim_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}$ exists
for all fixed integers $r>k\geq 2,e\geq 3$.

In [18], such a limit, if it exists, is called the degenerate Turán density of
sparse hypergraphs. Extending Glock’s result from $r=3,k=2,e=3$ to arbitrary
fixed $r\geq 4$, Shangguan and Tamo [18] showed that

$\displaystyle\lim_{n\rightarrow\infty}\frac{f_{r}(n,3r-4,3)}{n^{2}}=\frac{1}{r^{2}-r-1}.$

Following this line of work, Glock, Joos, Kim, Kühn, Lichev, and Pikhurko [11]
proved that

$\displaystyle\lim_{n\rightarrow\infty}\frac{f_{r}(n,3r-2k,3)}{n^{k}}=\frac{2}{k!(2\binom{r}{k}-1)}\quad\text{and}\quad\lim_{n\rightarrow\infty}\frac{f_{r}(n,4r-3k,4)}{n^{k}}=\frac{1}{k!}\binom{r}{k}^{-1},$
(4)

thereby settling 2 completely for $e\in\\{3,4\\}$.

The main result of this paper is the following theorem, which settles 2 for
$k=2$ and proves 1 for every uniformity.

######  Theorem 3.

The limit $\lim_{n\rightarrow\infty}\frac{f_{r}(n,er-2(e-1),e)}{n^{2}}$ exists
for all fixed integers $r\geq 3$ and $e\geq 3$.

The idea of our proof is sketched as follows. Let us begin with an attempt
that aims to prove the general case of 2. We will make use of the following
result proved in [11].

######  Lemma 4 (see Corollary 3.2 in [11]).

Let $\mathcal{F}$ be an $m$-vertex $r$-graph which simultaneously
$\mathscr{G}_{r}(er-(e-1)k,e)$-free and $\mathscr{G}_{r}(ir-(i-1)k-1,i)$-free
for all $2\leq i\leq e-1$. Then

$\liminf_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}\geq\frac{|\mathcal{F}|}{m^{k}}.$

For $t\in\\{2,\ldots,e-1\\}$, let $f_{r}^{(t)}(n,er-(e-1)k,e)$ denote the
maximum number of edges in an $n$-vertex $r$-graph which simultaneously
satisfy all of the following properties:

$\displaystyle\begin{split}\left\\{\begin{array}[]{cc}\text{it is
$\mathscr{G}_{r}(er-(e-1)k,e)$-free, and is
$\mathscr{G}_{r}(ir-(i-1)k-1,i)$-free for all $t\leq i\leq e-1$;}&\\\
\text{for every $(k-1)$-subset $T$, the number of edges containing $T$ is
either $0$ or at least $e$.}&\end{array}\right.\end{split}$ (5)

Then it is clear that

$\displaystyle f_{r}(n,er-(e-1)k,e)\geq
f_{r}^{(e-1)}(n,er-(e-1)k,e)\geq\cdots\geq f_{r}^{(2)}(n,er-(e-1)k,e)$

and hence

$\displaystyle\limsup_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}$
$\displaystyle\geq\limsup_{n\rightarrow\infty}\frac{f_{r}^{(e-1)}(n,er-(e-1)k,e)}{n^{k}}$
(6)
$\displaystyle\geq\cdots\geq\limsup_{n\rightarrow\infty}\frac{f_{r}^{(2)}(n,er-(e-1)k,e)}{n^{k}}.$

Moreover, as an easy consequence of Lemma 4 we have the following inequality:

$\displaystyle\liminf_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}\geq\limsup_{n\rightarrow\infty}\frac{f_{r}^{(2)}(n,er-(e-1)k,e)}{n^{k}}.$
(7)

Therefore, to prove the existence of
$\lim_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}$, it suffices to
show

$\displaystyle\limsup_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}$
$\displaystyle\leq\limsup_{n\rightarrow\infty}\frac{f_{r}^{(e-1)}(n,er-(e-1)k,e)}{n^{k}}$
(8)
$\displaystyle\leq\cdots\leq\limsup_{n\rightarrow\infty}\frac{f_{r}^{(2)}(n,er-(e-1)k,e)}{n^{k}}.$

Indeed, it follows by (6) and (8) that
$\limsup_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}=\limsup_{n\rightarrow\infty}\frac{f_{r}^{(2)}(n,er-(e-1)k,e)}{n^{k}}$,
which together with (7) would imply that
$\limsup_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}=\liminf_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}$,
and hence the existence of the corresponding limit. However, we are only able
to prove (8) for $k=2$, stated as below.

######  Lemma 5.

For all fixed $r\geq 3$ and $e\geq 3$,

$\displaystyle\limsup_{n\rightarrow\infty}\frac{f_{r}(n,er-2(e-1),e)}{n^{2}}$
$\displaystyle\leq\limsup_{n\rightarrow\infty}\frac{f_{r}^{(e-1)}(n,er-2(e-1),e)}{n^{2}}$
$\displaystyle\leq\cdots\leq\limsup_{n\rightarrow\infty}\frac{f_{r}^{(2)}(n,er-2(e-1),e)}{n^{2}}.$

In Delcourt and Postle’s solution to 1, their proof was based on a result
which is similar to Lemma 5 for the special case $r=3$. Using our notation,
they essentially proved that
$\limsup_{n\rightarrow\infty}\frac{f_{3}(n,e+2,e)}{n^{2}}\leq\limsup_{n\rightarrow\infty}\frac{f^{(2)}_{3}(n,e+2,e)}{n^{2}}$
(see Theorem 1.7 in [5]). To prove that result, they first proved a structural
lemma for $\mathcal{G}_{3}(e+2,e)$-free 3-graphs which are not
$\mathcal{G}_{3}(i+1,i)$-free for some $2\leq i\leq e+1$ (see Lemma 2.1 in
[5]). Our proof of Lemma 5 is inspired by their approach. At the core of our
proof is a more powerful structural lemma (see Lemma 9 below) for $r$-graphs
that satisfy the assumptions of (5) but are not
$\mathscr{G}_{r}((t-1)r-(t-2)k-1,t-1)$-free. Based on this new structural
lemma and a density increment argument, we are able to show that for $k=2$,
all such $r$-graphs must contain a sufficiently large
$\mathscr{G}_{r}((t-1)r-(t-2)k-1,t-1)$-free subhypergraph with non-decreasing
edge density (see Lemma 10 below). This enables us to prove the inequality
$\limsup_{n\rightarrow\infty}\frac{f_{r}^{(t)}(n,er-2(e-1),e)}{n^{2}}\leq\limsup_{n\rightarrow\infty}\frac{f_{r}^{(t-1)}(n,er-2(e-1),e)}{n^{2}}$
for every fixed $3\leq t\leq e-1$. We suspect that the above assertion holds
for all $k\geq 3$. If so, it would settle 2 in the full generality.

The rest of this paper is organized as follows. The proof of Lemma 5 is
presented in Section 2. In Section 2.1 we will prove the first inequality of
Lemma 5. In Section 2.2 we will state and prove our structural and density
lemmas (see Lemma 9 and Lemma 10 below). In Section 2.3 we will prove the
remaining inequalities of Lemma 5.

##  2 Proof of Lemma 5

###  2.1 The first inequality

In this subsection, we will prove the first inequality of Lemma 5, and in fact
we can prove it for every $k\geq 2$. Let us begin with some notations. For a
positive integer $n$, let $[n]=\\{1,\ldots,n\\}$. For a finite set $X$ and a
positive integer $r$, let $\binom{X}{r}$ denote the collection of all distinct
$r$-element subsets of $X$. Therefore,
$\binom{[n]}{r}=\\{A\subseteq[n]:|A|=r\\}$. For an $r$-graph
$\mathcal{F}\subseteq\binom{[n]}{r}$ and a subset $T\subseteq[n]$, the
codegree of $T$ in $\mathcal{F}$, denoted by $\deg_{\mathcal{F}}(T)$, is the
number of edges in $\mathcal{H}$ which contain $T$ as a subset, i.e.,
$\deg_{\mathcal{F}}(T)=|\\{A\in\mathcal{F}:T\subseteq A\\}|.$

The following lemma shows that any $r$-graph can be made to have no
$(k-1)$-subset of codegree belonging to $\\{1,\ldots,e-1\\}$ by deleting at
most $(e-1)\binom{n}{k-1}$ of its edges.

######  Lemma 6.

For every $r$-graph $\mathcal{F}\subseteq\binom{[n]}{r}$ there exists a
subhypergraph $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ such that
$|\mathcal{F}^{\prime}|\geq\max\\{0,|\mathcal{F}|-(e-1)\binom{n}{k-1}\\}$ and
for every $T\in\binom{[n]}{k-1}$, we have either
$\deg_{\mathcal{F}^{\prime}}(T)=0$ or $\deg_{\mathcal{F}^{\prime}}(T)\geq e$.

###### Proof.

Successively remove the edges of $\mathcal{F}$ which contain at least one
$(k-1)$-subset of codegree at least one and at most $e-1$, where the codegree
is counted with respect to the yet unmoved edges of $\mathcal{F}$. Let $A_{i}$
be the $i$-th removed edge, and $T_{i}$ be some $(k-1)$-subset of codegree at
least one and at most $e-1$ contained in $A_{i}$. In such a case we say that
$A_{i}$ is removed due to $T_{i}$ and $T_{i}$ is responsible for $A_{i}$. On
one hand, every $(k-1)$-subset of $[n]$ can be responsible for at most $e-1$
edges, since otherwise it would have codegree at least $e$ and could not be
responsible for any removed edge in the beginning. On the other hand, every
removed edge is removed due to some edge. Therefore we conclude that the
removal process must terminate after at most $(e-1)\binom{n}{k-1}$ edge
removals. Note that the resulting $r$-graph is possibly empty. ∎

The next lemma proves a lower bound of $f_{r}^{(e-1)}(n,er-(e-1)k,e)$ in terms
of $f_{r}(n,er-(e-1)k,e)$.

######  Lemma 7.

$f_{r}(n,er-(e-1)k,e)-(e-1)\binom{n}{k-1}\leq f_{r}^{(e-1)}(n,er-(e-1)k,e)).$

###### Proof.

Let $\mathcal{F}$ be an arbitrary $n$-vertex
$\mathscr{G}_{r}(er-(e-1)k,e)$-free $r$-graph. Let $\mathcal{F}^{\prime}$ be
the subhypergraph of $\mathcal{F}$ given by Lemma 6. To prove the lemma, it
suffices to show that $\mathcal{F}^{\prime}$ satisfies the condition of (5)
for $t=e-1$. Therefore, it is enough to show that $\mathcal{F}^{\prime}$ is
$\mathscr{G}_{r}((e-1)r-(e-2)k-1,e-1)$-free.

Assume otherwise, then there exist distinct edges
$A_{1},\ldots,A_{e-1}\in\mathcal{F}^{\prime}$ such that
$|\cup_{i=1}^{e-1}A_{i}|\leq(e-1)r-(e-2)k-1$. Let $T$ be an $(k-1)$-subset of
$A_{1}$. According to Lemma 6, there exists
$A_{e}\in\mathcal{F}^{\prime}\setminus\\{A_{1},\ldots,A_{e-1}\\}$ such that
$T\subseteq A_{e}$. It follows that

$\displaystyle|\cup_{i=1}^{e}A_{i}|\leq|\cup_{i=1}^{e-1}A_{i}|+|A_{e}\setminus
A_{1}|\leq\big{(}(e-1)r-(e-2)k-1\big{)}+\big{(}r-k+1\big{)}=er-(e-1)k,$

contradicting the fact that $\mathcal{F}^{\prime}$ is
$\mathscr{G}_{r}(er-(e-1)k,e)$-free. ∎

###### Proof of the first inequality of Lemma 5.

According to the lemma above, it is easy to see that

$\displaystyle\limsup_{n\rightarrow\infty}\frac{f_{r}(n,er-(e-1)k,e)}{n^{k}}\leq\limsup_{n\rightarrow\infty}\frac{f_{r}^{(e-1)}(n,er-(e-1)k,e)}{n^{k}}.$
(9)

Setting $k=2$ in (9) proves the first inequality of Lemma 5. ∎

###  2.2 The structural and density lemmas

First of all let us mention the following easy lemma.

######  Lemma 8.

Let $n$ be sufficiently large enough as a function of $e$ and $r$. Then

  * (i)

$f_{r}(n,er-(e-1),e)<\frac{n}{r-1}$;

  * (ii)

if $\mathcal{F}\subseteq\binom{[n]}{r}$ is
$\mathscr{G}_{r}(er-(e-1)k,e)$-free, then for every $T\in\binom{[n]}{k-1}$,
$\deg_{\mathcal{F}}(T)<\frac{n}{r-k}$.

###### Proof.

The first inequality is an easy consequence of (2). To prove the second
inequality, it is straightforward to verify by definition that for every
$T\in\binom{n}{k-1}$, the $(r-k+1)$-graph $\\{A\setminus T:A\in\mathcal{F}\\}$
defined on the vertex set $[n]\setminus T$ is
$\mathscr{G}_{r-k+1}(e(r-k+1)-(e-1),e)$-free, and therefore the result follows
by (i). ∎

Next we present a structural lemma for $\mathscr{G}_{r}(er-(e-1)k,e)$-free
$r$-graphs which are not $\mathscr{G}_{r}(ir-(i-1)k-1,i)$-free for some $2\leq
i\leq e-1$.

######  Lemma 9.

Let $t\geq 3$ and $\mathcal{F}\subseteq\binom{[n]}{r}$ be an $r$-graph
satisfying the assumptions of (5). If it is not
$\mathscr{G}_{r}((t-1)r-(t-2)k-1,t-1)$-free, i.e., there are $t-1$ distinct
edges $A_{1},\ldots,A_{t-1}\in\mathcal{F}$ such that
$|\cup_{i=1}^{t-1}A_{i}|\leq(t-1)r-(t-2)k-1$, then the following hold:

  * (i)

let $X=\cup_{i=1}^{t-1}A_{i}$, then $|X|=(t-1)r-(t-2)k-1$;

  * (ii)

for every $A\in\mathcal{F}\setminus\\{A_{1},\ldots,A_{t-1}\\}$, $|A\cap X|\leq
k-1$;

  * (iii)

let
$\mathcal{I}(X)=\big{\\{}A\in\mathcal{F}\setminus\\{A_{1},\ldots,A_{t-1}\\}:|A\cap
X|=k-1\big{\\}}$, then

$|\mathcal{I}(X)|\leq\max\big{\\{}e-t+1,f_{r-k+1}(n-|X|,(e-t+1)(r-k+1)-(e-t),e-t+1)\big{\\}}.$

In particular, if $n$ is large enough as a function of $r$ and $e$, then
$|\mathcal{I}(X)|<\frac{n-|X|}{r-k}$.

###### Proof.

(i) For the ease of notation let $x=(t-1)r-(t-2)k-1$. Assume for contradiction
that $|X|\leq x-1$. Let $T$ be an $(k-1)$-subset of $A_{1}$. As
$\deg_{\mathcal{F}}(T)\geq e$ there exists
$A_{t}\in\mathcal{F}\setminus\\{A_{1},\ldots,A_{t-1}\\}$ such that $T\subseteq
A_{t}$. It follows that

$\displaystyle|\cup_{i=1}^{t}A_{i}|\leq|X|+|A_{t}\setminus
A_{1}|\leq(x-1)+(r-k+1)=tr-(t-1)k-1,$

violating the assumption that $\mathcal{F}$ is
$\mathscr{G}_{r}(tr-(t-1)k-1,t)$-free.

(ii) If there exists $A_{t}\in\mathcal{F}\setminus\\{A_{1},\ldots,A_{t-1}\\}$
such that $|A_{t}\cap X|\geq k$, then similar to the proof of (i), it is clear
that

$|\cup_{i=1}^{t}A_{i}|\leq|X|+|A_{t}\setminus X|\leq x+(r-k)=tr-(t-1)k-1,$

a contradiction.

(iii) Assume that $|\mathcal{I}(X)|\geq e-t+1$, otherwise there is nothing to
prove. As $\mathcal{F}$ is $\mathscr{G}_{r}(er-(e-1)k,e)$-free, for arbitrary
$e-t+1$ distinct edges $A_{t},\ldots,A_{e}\in\mathcal{I}(X)$ we have

$\displaystyle|\cup_{i=1}^{e}A_{i}|=|X|+|\cup_{i=t}^{e}(A_{i}\setminus X)|\geq
er-(e-1)k+1,$

which implies that

$\displaystyle|\cup_{i=t}^{e}(A_{i}\setminus X)|\geq
er-(e-1)k+1-|X|=(e-t+1)(r-k+1)-(e-t)+1.$

It follows that the $(r-k+1)$-graph $\mathcal{J}(X):=\\{A\setminus
X:A\in\mathcal{I}(X)\\}$ defined on the vertex set $V(\mathcal{F})\setminus X$
is $\mathscr{G}_{r-k+1}((e-t+1)(r-k+1)-(e-t),e-t+1)$-free. Moreover, it is
clear that for all distinct $A,B\in\mathcal{I}(X)$, we have $A\setminus X\neq
B\setminus X$, since otherwise

$|\cup_{i=1}^{t-1}A_{i}\cup A\cup B|\leq x+r-k+1=tr-(t-1)k,$

contradicting the fact that $\mathcal{F}$ is
$\mathscr{G}_{r}((t+1)r-tk-1,t+1)$-free. We conclude that

$\displaystyle|\mathcal{I}(X)|=|\mathcal{J}(X)|\leq
f_{r-k+1}(n-|X|,(e-t+1)(r-k+1)-(e-t),e-t+1),$

as needed. Finally, the last sentence of (iii) follows by Lemma 8 (i). ∎

Applying Lemma 9 with $k=2$ yields the following result, which shows that any
$r$-graph that satisfy the assumptions of (5) but are not
$\mathscr{G}_{r}((t-1)r-2(t-2)-1,t-1)$-free must contain a sufficiently large
$\mathscr{G}_{r}((t-1)r-2(t-2)-1,t-1)$-free subhypergraph with non-decreasing
edge density. Note that we did not try to optimize the constants written in
Lemma 10.

######  Lemma 10.

Let $t\geq 3$ and $r\geq 3$. Let $n$ be sufficiently large as a function of
$e$ and $r$. Let $\mathcal{F}\subseteq\binom{[n]}{r}$ be an $r$-graph
satisfying the assumptions of (5). Moreover, assume that
$\frac{|\mathcal{F}|}{n^{2}}\geq\max\\{\frac{1}{r(r-1)}-\frac{\delta}{r(r-2)},\frac{1}{2r^{2}-2r-5}\\}$,
where $\delta=\frac{1}{(3r-4)(r-1)+1}$. Then there exists a subhypergraph
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ with the following properties:

  * (i)

$\mathcal{F}^{\prime}$ is $\mathscr{G}_{r}((t-1)r-2(t-2)-1,t-1)$-free;

  * (ii)

$|V(\mathcal{F}^{\prime})|\geq\alpha n$, where
$\alpha=\sqrt{\frac{3r^{2}-4r-14}{3r^{2}+2r-8}}$;

  * (iii)

$\frac{|\mathcal{F}^{\prime}|}{|V(\mathcal{F}^{\prime})|^{2}}\geq\frac{|\mathcal{F}|}{n^{2}}$.

###### Proof.

Let $x=(t-1)r-2(t-2)-1$. Assume that $\mathcal{F}$ is not
$\mathscr{G}_{r}(x,t-1)$-free, otherwise there is nothing to prove. Call a
family of $t-1$ distinct edges
$\\{A_{1},\ldots,A_{t-1}\\}\subseteq\mathcal{F}$ a bad configuration if
$|\cup_{i=1}^{t-1}A_{i}|\leq x$. By Lemma 9 (i), the union of every bad
configuration has size exactly $x$.

Let $\mathcal{F}_{0}=\mathcal{F}$. We will successfully construct hypergraphs
$\mathcal{F}_{1},\mathcal{F}_{2},\ldots$ as follows. We aim to show that such
a process will terminate and produce a hypergraph as needed. For $j\geq 0$, if
$\mathcal{F}_{j}$ is not $\mathscr{G}_{r}(x,t-1)$-free, say, it contains a bad
configuration $\\{A_{1,j},\ldots,A_{t-1,j}\\}$ with
$X_{j}:=\cup_{i=1}^{t-1}A_{i,j}$. Then we set $\mathcal{F}_{j+1}$ to be the
subhypergraph of $\mathcal{F}_{j}$ formed by

$\displaystyle\mathcal{F}_{j+1}:=\mathcal{F}_{j}\setminus(\mathcal{I}(X_{j})\cup\\{A_{1,j},\ldots,A_{t-1,j}\\})\quad\text{and}\quad
V(\mathcal{F}_{j+1}):=V(\mathcal{F}_{j})\setminus X_{j}$

where $\mathcal{I}(X_{j})$ is the $r$-graph defined in Lemma 9 with $k=2$ and
$A_{1,j},\ldots,A_{t-1,j},X_{j}$ playing the roles of
$A_{1},\ldots,A_{t-1},X$, respectively.

Before going any further, we need to show that $V(\mathcal{F}_{j+1})$ is well-
defined, namely, for every $A\in\mathcal{F}_{j+1}$, we have $A\cap
X_{j}=\emptyset$. Indeed, by applying Lemma 9 (ii) with $k=2$ and the
definition of $\mathcal{I}(X_{j})$, it is not hard to see that

$\displaystyle\\{A\in\mathcal{F}_{j}:A\cap
X_{j}\neq\emptyset\\}=\\{A\in\mathcal{F}_{j}:|A\cap X_{j}|\geq
1\\}=\mathcal{I}(X_{j})\cup\\{A_{1,j},\ldots,A_{t-1,j}\\},$

which proves that $V(\mathcal{F}_{j+1})$ is well-defined.

For each $j\geq 0$, denote $e_{j}=|\mathcal{F}_{j}|$ and
$v_{j}=|V(\mathcal{F}_{j})|$. We claim that for $0\leq
j\leq\frac{(1-\alpha)n}{x}$, the following hold:

$\displaystyle e_{j+1}>e_{j}-\frac{v_{j}}{r-2}\quad\text{and}\quad
v_{j+1}=v_{j}-x.$ (10)

Indeed, by definition we have $e_{j+1}=e_{j}-|\mathcal{I}(X_{j})|-(t-1)$;
moreover, by applying Lemma 9 (iii) with $k=2$ we have for large enough $n$
(thus $v_{j}$ is also large enough for $0\leq j\leq\frac{(1-\alpha)n}{x}$),

$\displaystyle|\mathcal{I}(X_{j})|+(t-1)<\frac{v_{j}-x}{r-2}+(t-1)<\frac{v_{j}}{r-2},$

which proves the inequality. The equality follows from the definition of
$V(\mathcal{F}_{j+1})$ and the fact that $X_{j}\subseteq V(\mathcal{F}_{j})$.

Applying (10) repeatedly yields that for every $0\leq
j\leq\frac{(1-\alpha)n}{x}$,

$\displaystyle
e_{j}>e_{0}-\frac{1}{r-2}\sum_{i=0}^{j-1}v_{i}\quad\text{and}\quad
v_{j}=v_{0}-xj.$ (11)

Since $\mathcal{F}_{j}\subseteq\mathcal{F}$, it has to be
$\mathscr{G}_{r}(er-2(e-1),e)$-free. Therefore, it follows by Lemma 8 (ii)
that the average degree of $V(\mathcal{F}_{j})$ must be less than
$\frac{v_{j}}{r-2}$, or equivalently,

$\displaystyle\frac{e_{j}r}{v_{j}}<\frac{v_{j}}{r-2}.$ (12)

According to (11) and (12), we have

$\displaystyle\frac{e_{0}-\frac{v_{0}j}{r-2}+\frac{j(j-1)x}{2(r-2)}}{(v_{0}-xj)^{2}}<\frac{e_{j}}{v_{j}^{2}}<\frac{1}{r(r-2)}.$
(13)

Substituting $v_{0}=n,e_{0}\geq(\frac{1}{r(r-1)}-\frac{\delta}{r(r-2)})n^{2}$,
setting $y=xj$, and rearranging yields that

$\displaystyle
y(2n-y)-\frac{ry}{2x}(2n-y)-\frac{ry}{2}<(\frac{1}{r-1}+\delta)n^{2}.$ (14)

Note that $\frac{ry}{2}\leq\frac{rn}{2}$. Observe that $x$ is at least the
size of the union of two distinct $r$-subsets, so $x\geq r+1$. Substituting
the above inequalities to (14) gives that

$\displaystyle\frac{r+2}{2r+2}n^{2}-\frac{r+2}{2r+2}(n-y)^{2}<(\frac{1}{r-1}+\delta)n^{2}+\frac{rn}{2}<\frac{3n^{2}}{3r-4},$

where the last inequality follows from the choice of $\delta$ and the
assumption that $n$ is sufficiently large as a function of $r$. Rearranging
gives that

$\displaystyle(n-y)^{2}>\alpha^{2}n^{2}.$

As $y\leq n$, it follows that $y<(1-\alpha)n$ and hence
$j<\frac{(1-\alpha)n}{x}$. We conclude that the above process must stop in at
most $\frac{(1-\alpha)n}{x}$ steps, and therefore at most $(1-\alpha)n$
vertices of $V(\mathcal{F})$ could be removed. By our construction, it is
clear that the resulting $r$-graph, denoted by $\mathcal{F}^{\prime}$,
satisfies conditions (i) and (ii) in the lemma.

In order to prove that $\mathcal{F}^{\prime}$ also satisfies (iii), it is
enough to show that for every $j\geq 1$,
$\frac{e_{j}}{v_{j}^{2}}>\frac{e_{0}}{v_{0}^{2}}$. Indeed, by (13) we have

$\displaystyle\frac{e_{j}}{v_{j}^{2}}-\frac{e_{0}}{v_{0}^{2}}>\frac{e_{0}-\frac{v_{0}j}{r-2}+\frac{j(j-1)x}{2(r-2)}}{(v_{0}-xj)^{2}}-\frac{e_{0}}{v_{0}^{2}}.$

Plugging $y=jx$ and rearranging, we have

$\displaystyle\frac{e_{j}}{v_{j}^{2}}-\frac{e_{0}}{v_{0}^{2}}>\frac{1}{(n-y)^{2}}\Big{(}\frac{e_{0}}{v_{0}^{2}}(2ny-y^{2})-\frac{ny}{(r-2)x}+\frac{y^{2}}{2(r-2)x}-\frac{y}{2(r-2)}\Big{)}$

Observe that $-\frac{ny}{(r-2)x}+\frac{y^{2}}{2(r-2)x}$ is negative. Then as
$x\geq r+1$ and $\frac{e_{0}}{v_{0}^{2}}\geq\frac{1}{2r^{2}-2r-5}$, we have

$\displaystyle\frac{e_{j}}{v_{j}^{2}}-\frac{e_{0}}{v_{0}^{2}}>\frac{y}{(n-y)^{2}}\Big{(}\frac{n}{(2r^{2}-2r-5)(r^{2}-r-2)}-\frac{y/2}{(2r^{2}-2r-5)(r^{2}-r-2)}-\frac{1}{2(r-2)}\Big{)}>0,$

completing the proof of (iii), where the last inequality follows from the fact
that $y/2<n/2$ and the assumption that $n$ is sufficiently large. ∎

###  2.3 The remaining inequalities

In this subsection we will prove the remaining inequalities of Lemma 5. We
will make use of the following result, proved independently in [4, 12].

######  Lemma 11 (see Theorem 1.3 in [4] and Theorem 1.1 in [12]).

Let $r\geq 3$ and $e\geq 3$ be fixed integers. Then there exists $n_{0}$ and
$\epsilon>0$ such that for all $n\geq n_{0}$ there exists an $n$-vertex
$r$-graph which has at least $(1-n^{-\epsilon})\frac{n^{2}}{r^{2}-r}$ edges
and is $\mathscr{G}_{r}(tr-2(t-1),t)$-free for every $2\leq t\leq e$.

We will use the following easy consequence of Lemma 11.

######  Lemma 12.

Let $r\geq 3$ and $e\geq 3$ be fixed integers. Then there exists $n_{0}$ such
that for all $n\geq n_{0}$ there exists an $n$-vertex $r$-graph $\mathcal{F}$
which satisfies
$\frac{|\mathcal{F}|}{n^{2}}>\max\\{\frac{1}{r(r-1)}-\frac{\delta}{r(r-2)},\frac{1}{2r^{2}-2r-5}\\}$,
where $\delta=\frac{1}{(3r-4)(r-1)+1}$, and the assumptions of (5) for $k=2$.

###### Proof.

It is clear that the $r$-graph given by Lemma 11 satisfies the first line of
(5). It is also clear by Lemma 6 that the $r$-graph given by Lemma 11 can be
made to satisfy the second line of (5) by removing at most $(e-1)n$ of its
edges. Lastly, the required lower bound on $\frac{|\mathcal{F}|}{n^{2}}$ holds
for sufficiently large $n$ since for every $r\geq 3$, $\frac{1}{r^{2}-r}$ is
strictly larger than both $\frac{1}{r(r-1)}-\frac{\delta}{r(r-2)}$ and
$\frac{1}{2r^{2}-2r-5}$. ∎

Given Lemmas 10 and 12, the remaining inequalities of Lemma 5 can be proved by
standard analysis. We will follow the proof of Theorem 1.7 in [5].

###### Proof of the remaining inequalities of Lemma 5.

For every $3\leq t\leq e-1$, let

$a_{t}=\limsup_{n\rightarrow\infty}\frac{f_{r}^{(t)}(n,er-2(e-1),e)}{n^{2}}.$

It suffices to show that for every $t$, $a_{t}\leq a_{t-1}$.

Assume for the sake of contradiction that there exists some $3\leq t\leq e-1$
such that $a_{t}>a_{t-1}$. Let $\epsilon=a_{t}-a_{t-1}$,
$b=\max\\{\frac{1}{r(r-1)}-\frac{\delta}{r(r-2)},\frac{1}{2r^{2}-2r-5}\\}$
with $\delta=\frac{1}{(3r-4)(r-1)+1}$, and $c=\max\\{a_{t}-\epsilon/2,b\\}$.
Since $a_{t}>b$ by Lemma 12, it follows that

$\displaystyle a_{t}>c\geq a_{t}-\epsilon/2>a_{t-1}.$

Let

$\displaystyle\mathcal{I}_{t}=\\{n\in\mathbb{N}:\frac{f_{r}^{(t)}(n,er-2(e-1),e)}{n^{2}}\geq
c\\}$

and

$\displaystyle\mathcal{I}_{t-1}=\\{n\in\mathbb{N}:\frac{f_{r}^{(t-1)}(n,er-2(e-1),e)}{n^{2}}\geq
c\\}.$

Then, as $a_{t}>c$, $\mathcal{I}_{t}$ is infinite. As $a_{t-1}<c$,
$\mathcal{I}_{t-1}$ is finite. Let
$n_{t-1}=\max\\{n:n\in\mathcal{I}_{t-1}\\}$. Since $\mathcal{I}_{t}$ is
infinite, there exists $n_{t}\in\mathcal{I}_{t}$ such that
$n_{t}>n_{t-1}/\alpha$, where $\alpha$ is defined in Lemma 10 (ii). According
to the definition of $\mathcal{I}_{t}$, there exists an $n_{t}$-vertex
$r$-graph $\mathcal{F}$ which satisfies the conditions of (5) with $k=2$, and
$\frac{|\mathcal{F}|}{|V(\mathcal{F})|^{2}}\geq c$. As $\mathcal{F}$ also
satisfies the assumptions of Lemma 10, it follows that there exists a
subhypergraph $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ that satisfies all of
the three properties listed in Lemma 10. In particular, we have
$\frac{|\mathcal{F}^{\prime}|}{|V(\mathcal{F}^{\prime})|^{2}}\geq\frac{|\mathcal{F}|}{n^{2}}\geq
c$, which implies that $|V(\mathcal{F}^{\prime})|\in\mathcal{I}_{t-1}$.
However, we also have
$|V(\mathcal{F}^{\prime})|\geq\alpha|V(\mathcal{F})|>n_{t-1}$, which
contradicts the maximality of $n_{t-1}$. ∎

## Acknowledgements

The research of Chong Shangguan is supported by the National Key Research and
Development Program of China under Grant No. 2021YFA1001000, the National
Natural Science Foundation of China under Grant No. 12101364, and the Natural
Science Foundation of Shandong Province under Grant No. ZR2021QA005.

## References

  * [1] Noga Alon and Asaf Shapira.  On an extremal hypergraph problem of Brown, Erdos and Sós.  Combinatorica, 26(6):627–645, 2006.
  * [2] W. G. Brown, P. Erdős, and V. T. Sós.  Some extremal problems on $r$-graphs.  In New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971), pages 53–63, 1973.
  * [3] David Conlon, Lior Gishboliner, Yevgeny Levanzov, and Asaf Shapira.  A new bound for the brown–erdos–sos problem.  arXiv eprint 1912.08834, 2019.
  * [4] Michelle Delcourt and Luke Postle.  Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings.  arXiv:2204.08981, 2022.
  * [5] Michelle Delcourt and Luke Postle.  The limit in the $(k+2,k)$-problem of Brown, Erdős and Sós exists for all $k\geq 2$.  arXiv:2210.01105, 2022.
  * [6] P. Erdős.  Extremal problems in graph theory.  In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29–36. Publ. House Czech. Acad. Sci., Prague, 1964\.
  * [7] P. Erdős, P. Frankl, and V. Rődl.  The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent.  Graphs Combin., 2(2):113–121, 1986.
  * [8] Zoltán Füredi and Miklós Ruszinkó.  Uniform hypergraphs containing no grids.  Adv. Math., 240:302–324, 2013.
  * [9] Gennian Ge and Chong Shangguan.  Sparse hypergraphs: new bounds and constructions.  J. Combin. Theory Ser. B, 147:96–132, 2021.
  * [10] Stefan Glock.  Triple systems with no three triples spanning at most five points.  Bull. Lond. Math. Soc., 51(2):230–236, 2019.
  * [11] Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, Lyuben Lichev, and Oleg Pikhurko.  On the (6,4)-problem of Brown, Erdős and Sós.  arXiv:2209.14177, 2022.
  * [12] Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, and Lyuben Lichev.  Conflict-free hypergraph matchings.  arXiv:2205.05564, 2022.
  * [13] B. Nagle, V. Rödl, and M. Schacht.  Extremal hypergraph problems and the regularity method.  In Topics in discrete mathematics, volume 26 of Algorithms Combin., pages 247–278. Springer, Berlin, 2006.
  * [14] Vojtěch Rödl.  On a packing and covering problem.  European J. Combin., 6(1):69–78, 1985.
  * [15] I. Z. Ruzsa and E. Szemerédi.  Triple systems with no six points carrying three triangles.  In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, volume 18 of Colloq. Math. Soc. János Bolyai, pages 939–945. North-Holland, Amsterdam-New York, 1978.
  * [16] Gábor N. Sárközy and Stanley Selkow.  An extension of the Ruzsa-Szemerédi theorem.  Combinatorica, 25(1):77–84, 2005.
  * [17] Gábor N. Sárközy and Stanley Selkow.  On a Turan-type hypergraph problem of Brown, Erdos and Sós.  Discrete Math., 297(1-3):190–195, 2005.
  * [18] Chong Shangguan and Itzhak Tamo.  Degenerate Turán densities of sparse hypergraphs.  J. Combin. Theory Ser. A, 173:105228, 25, 2020.
  * [19] Chong Shangguan and Itzhak Tamo.  Sparse hypergraphs with applications to coding theory.  SIAM J. Discrete Math., 34(3):1493–1504, 2020.
  * [20] Alexander Sidorenko.  Approximate Steiner $(r-1,r,n)$-systems without three blocks on $r+2$ points.  J. Combin. Des., 28(2):144–148, 2020.
  * [21] V. T. Sós, P. Erdős, and W. G. Brown.  On the existence of triangulated spheres in $3$-graphs, and related problems.  Period. Math. Hungar., 3(3-4):221–228, 1973.