and for each $B_{K^{2}}\in\mathcal{B}^{\prime}$ the following holds: there
exists some $b\in\mathcal{B}$ such that

(7.19) $B_{K^{2}}\subset N_{\rho^{1/2+\delta_{m}}/2}(Z+b),$

and there exist at most $O(1)$ vectors $b\in\mathcal{B}$ for which

(7.20) $B_{K^{2}}\cap N_{\rho^{1/2+\delta_{m}}}(Z+b)\neq\varnothing.$

For every $b\in\mathcal{B}$, we let $\mathcal{B}_{b}^{\prime}$ denote the
collection of all the balls $B_{K^{2}}$ satisfying (7.19). By (7.18) and
(7.19), we know that

(7.21) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B(\widetilde{{\bf
x}}_{0},\rho))}^{p}\lesssim(\log{r})^{2p}\sum_{b\in\mathcal{B}}\sum_{B_{K^{2}}\in\mathcal{B}_{b}^{\prime}}\mu_{H^{\lambda}g}(B_{K^{2}}).$

We define

(7.22) $\widetilde{\mathbb{T}}_{b}^{\prime}[B(\widetilde{{\bf
x}}_{0},\rho)]:=\\{\widetilde{T}\in\bigcup_{{T}_{\theta,v}\in\mathbb{T}_{Z}[B({\bf
x}_{0},r)]}\widetilde{\mathbb{T}}_{\theta,v}[B(\widetilde{{\bf
x}}_{0},\rho)]:\widetilde{T}\cap\bigcup_{B_{K^{2}}\in\mathcal{B}_{b}^{\prime}}B_{K^{2}}\neq\varnothing\\}.$

Since every element of $\widetilde{\mathbb{T}}_{b}^{\prime}[B(\widetilde{{\bf
x}}_{0},\rho)]$ intersects $N_{\rho^{1/2+\delta_{m}}/2}(Z+b)$, by Lemma 7.10,
we know that $\widetilde{\mathbb{T}}_{b}^{\prime}[B(\widetilde{{\bf
x}}_{0},\rho)]\subset\widetilde{\mathbb{T}}_{b}[B(\widetilde{{\bf
x}}_{0},\rho)]$. Let us define
$g_{b}:=g|_{\widetilde{\mathbb{T}}_{b}^{\prime}[B(\widetilde{{\bf
x}}_{0},\rho)]}$. By the proof of Lemma 5.4, the construction of the
collection $\widetilde{\mathbb{T}}_{b}^{\prime}[B(\widetilde{{\bf
x}}_{0},\rho)]$, and the triangle inequality of the broad norm (Lemma 6.2 of
[GHI19]), we also know that

(7.23)
$\begin{split}\mu_{H^{\lambda}g}(B_{K^{2}})\lesssim\mu_{H^{\lambda}g_{b}}(B_{K^{2}})+\mathrm{RapDec}(r)\|g\|_{2}^{p}\end{split}$

for every $B_{K^{2}}\in\mathcal{B}_{b}^{\prime}$. Therefore, by combining the
above inequality with (7.21) and the cardinality condition on $\mathcal{B}$,
we obtain the first inequality (7.13).

Let us now show the second inequality (7.14). By Lemma 4.2 and (7.20), we
obtain

(7.24)
$\begin{split}\sum_{b\in\mathcal{B}}\|g_{b}\|_{2}^{2}&=\sum_{b\in\mathcal{B}}\big{\|}\sum_{\widetilde{T}\in\widetilde{\mathbb{T}}_{b}^{\prime}[B(\widetilde{{\bf
x}}_{0},\rho)]}g_{\widetilde{T}}\big{\|}_{2}^{2}\\\
&\lesssim\sum_{b\in\mathcal{B}}\sum_{\widetilde{T}\in\widetilde{\mathbb{T}}_{b}^{\prime}[B(\widetilde{{\bf
x}}_{0},\rho)]}\|g_{\widetilde{T}}\|_{2}^{2}\lesssim\sum_{\widetilde{T}\in\widetilde{\mathbb{T}}[B(\widetilde{{\bf
x}}_{0},\rho)]}\|g_{\widetilde{T}}\|_{2}^{2}\lesssim\|g\|_{2}^{2}.\end{split}$

This completes the proof. ∎

##  8\. Finding polynomial structures

In this and the next section, we build a big algorithm to break down the
quantity $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{R})}$ in our main
estimate (3.20), and use it to prove our main result, Theorem 3.4. The whole
algorithm is involved, so we split it into two smaller ones. This section is
devoted for the first one, and we follow Section 6.1 in [HZ20]. See also
Section 9 in [HR19].

Recall the following admissible parameters introduced in (1.11)

(8.1)
$\epsilon^{C}\ll\delta\ll\delta_{n}\ll\delta_{n-1}\ll\cdots\ll\delta_{1}\ll\epsilon_{\circ}\ll\epsilon.$

We define $\tilde{\delta}_{m-1}$ to be

(8.2) $(1-\tilde{\delta}_{m-1})(1/2+\delta_{m-1})=1/2+\delta_{m}.$

Notice that $\delta_{m-1}/2\leq\tilde{\delta}_{m-1}\leq 2\delta_{m-1}$. This
constant $\tilde{\delta}_{m-1}$ is introduced for some technical reasons and
plays a minor role in the proof.

###  8.1. Polynomial partitioning lemma

For a polynomial $P$, we denote by $\mathrm{cell}(P)$ a collection of the
connected components of $\mathbb{R}^{n}\setminus Z(P)$. We state the polynoial
partitioning lemma used in [Gut18].

######  Lemma 8.1 ([Gut18]).

Let $r\gg 1$ and $d,m$ be positive integers. Let $0<\delta_{m}\ll 1$. Suppose
that $Z=Z(P_{1},\ldots,P_{n-m})$ is a $m$-dimensional transverse complete
intersection, with $\mathrm{deg}P_{j}\leq d$. Suppose that $F\in
L^{1}(\mathbb{R}^{n})$ is non-negative and supported on $B_{r}\cap
N_{r^{1/2+\delta_{m}}}Z$. Then at least one of the following cases hold true:

  1. (1)

(Cellular case) There exists a polynomial $P$ of degree at most $O(d)$ with
the following properties:

    1. (a)

$\\#\mathrm{cell}(P)\sim d^{m}$

    2. (b)

For each $O^{\prime}\in\mathrm{cell}(P)$, define the shrunken cells
$O:=O^{\prime}\setminus N_{R^{1/2+\delta_{m}}}(Z(P))$. Then for every $O$

$\int_{O}F\sim d^{-m}\int_{\mathbb{R}^{n}}F.$

Moreover, the number of the shrunken cells $O$ is comparable to $d^{m}$, and
the diameter of $O$ is smaller than $r/2$.

  2. (2)

(Algebraic case) There exists $(m-1)$-dimensional transverse complete
intersection $Y$, defined using polynomials of degree at most $O(d)$ such that

$\int_{B_{r}\cap N_{r^{1/2+\delta_{m}}}(Z)}F\lesssim\int_{B_{r}\cap
N_{r^{1/2+\delta_{m}}}(Y)}F.$

Suppose that a function $g$ and a grain $(Z,B_{r})$ of dimension $m$ are
given. We will apply the above lemma to the function

(8.3)
$F(x)=\sum_{B_{K^{2}}}\mu_{H^{\lambda}g}(B_{K^{2}})\frac{1}{|B_{K^{2}}|}1_{{B_{K^{2}}\cap
B_{r}\cap N_{r^{1/2+\delta_{m}}}(Z)}}(x)$

with a number $d$. This number $d$ will be much larger than the degrees of
polynomial defining $Z$. If the cellular case holds true, then

(8.4) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{r}\cap
N_{r^{1/2+\delta_{m}}}(Z))}^{p}\lesssim
d^{m}\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(O)}^{p}$

for all $O\in\mathcal{O}$. Here, every $O\in\mathcal{O}$ has a diameter at
most $r/2$ and $\\#\mathcal{O}\sim d^{m}$ for some sufficiently large number
$d$, which will be determined later. If the algebraic case holds true, then

(8.5) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{r}\cap
N_{r^{1/2+\delta_{m}}}(Z))}\lesssim\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{r}\cap
N_{r^{1/2+\delta_{m}}}(Y))}$

for some $(m-1)$-dimensional transverse complete intersection $Y$, defined
using polynomials of degree at most $d$.

###  8.2. The first algorithm

Let us illustrate the first algorithm. This algorithm is the counterpart of
the first algorithm in Section 6.1 of [HZ20]. Let $1\leq m\leq n$.

Input The algorithm [alg 1] takes as its input:

  * •

A grain $\big{(}Z,B({\bf x}_{0},r)\big{)}$ of dimension $m$ with $B({\bf
x}_{0},r)\subset[-3C_{n}\lambda,3C_{n}\lambda]^{n-1}\times[R/C_{n},C_{n}\lambda]$.

  * •

A function $g\in L^{1}$ which is tangent to the grain $\big{(}Z,B({\bf
x}_{0},r)\big{)}$.

  * •

An admissible large integer $A\in\mathbb{N}$.

Output The $j$th stage of [alg 1] outputs:

  * •

A choice of spatial scale $\rho_{j}\geq 1$

  * •

Certain integers
$\\#_{\mbox{\small$\texttt{a}$}}(j),\\#_{\mbox{\small$\texttt{c}$}}(j)\in\mathbb{N}_{0}$
satisfying
$\\#_{\mbox{\small$\texttt{a}$}}(j)+\\#_{\mbox{\small$\texttt{c}$}}(j)=j$.555The
integers $\\#_{\mbox{\small$\texttt{a}$}}(j)$ and
$\\#_{\mbox{\small$\texttt{c}$}}(j)$ indicate the number of occurrences of
algebraic cases and cellular cases, respectively.

  * •

A family of subsets $\mathcal{O}_{j}$ of $\mathbb{R}^{n}$ referred to as
_cells_. Each cell $O_{j}\in\mathcal{O}_{j}$ is contained in some
$\rho_{j}$-ball $B_{O_{j}}:=B({\bf x}_{O_{j}},\rho_{j})$.

  * •

A collection of functions $\\{g_{O_{j}}\\}_{O_{j}\in\mathcal{O}_{j}}$. For
each cell $O_{j}$ there is a translate $Z_{O_{j}}:=Z+{\bf y}_{O_{j}}$ such
that $g_{O_{j}}$ is tangent to the grain $(Z_{O_{j}},B_{O_{j}})$.

  * •

A large integer $d\in\mathbb{N}$ which depends only on the admissible
parameters and $\deg Z$.

All the outputs will be constructed so that for some constants

(8.6)
$C^{\mathrm{I}}_{j,\delta}(d,r),\;C^{\mathrm{II}}_{j,\delta}(d),\;C^{\mathrm{III}}_{j,\delta}(d,r),\;C^{\mathrm{IV}}_{j,\delta}(d,r)\lesssim_{d,\delta}r^{\epsilon_{\circ}}d^{\\#_{\mbox{\scriptsize$\texttt{c}$}}(j)\delta},$

which will be defined explicitly in (8.13), and
$A_{j}=2^{-\\#_{\mbox{\scriptsize$\texttt{a}$}}(j)}A$ the following properties
hold true:

##### Property I

For some fixed $N\in\mathbb{N}$

(8.7) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B({\bf x}_{0},r))}^{p}\leq
C^{\mathrm{I}}_{j,\delta}(d,r)\sum_{O_{j}\in\mathcal{O}_{j}}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}^{p}+jr^{-N}\|g\|_{L^{2}(B^{n-1})}^{p}$

##### Property II

(8.8) $\sum_{O_{j}\in\mathcal{O}_{j}}\|g_{O_{j}}\|_{2}^{2}\leq
C^{\mathrm{II}}_{j,\delta}(d)d^{\\#_{\mbox{\scriptsize$\texttt{c}$}}(j)}\|g\|_{2}^{2}.$

##### Property III

(8.9) $\|g_{O_{j}}\|_{L^{2}(B^{n-1})}^{2}\leq
C_{j,\delta}^{\mathrm{III}}(d,r)\Big{(}\frac{r}{\rho_{j}}\Big{)}^{-\frac{n-m}{2}}d^{-\\#_{\mbox{\scriptsize$\texttt{c}$}}(j)(m-1)}\|g\|_{L^{2}(B^{n-1})}^{2}.$

To state the last property, we need to introduce some notations. For
$\widetilde{\mathbb{W}}\subseteq\widetilde{\mathbb{T}}[B({{\bf
x}}_{O_{j}},\rho_{j})]$ let $\uparrow^{j}\\!\widetilde{\mathbb{W}}$ denote the
set of wave packets $T_{\theta,v}({\bf x}_{0})\in\mathbb{T}[B({\bf x}_{0},r)]$
satisfying

(8.10) $\text{dist}(\theta,\widetilde{\theta}_{j})\leq
c_{j}\rho_{j}^{-1/2}\quad\textrm{and}\quad\text{dist}\big{(}\widetilde{T}_{\tilde{\theta}_{j},\tilde{v}_{j}}({{\bf
x}}_{O_{j}}),\,T_{\theta,v}({\bf x}_{0})\cap B_{O_{j}}\big{)}\leq
c_{j}r^{1/2+\delta}$

for some $\widetilde{T}_{\tilde{\theta}_{j},\tilde{v}_{j}}({{\bf
x}}_{O_{j}})\in\widetilde{\mathbb{W}}$. Here $\\{c_{j}\\}_{j=0}^{\infty}$ is a
increasing positive sequence that each of which is bounded above by an
absolute constant $C_{\circ}$. In fact, one can take
$c_{j}=C_{\circ}(1-2^{-j/2})$ for some big constant $C_{\circ}$. We introduce
this sequence only for the sake of rigorousness. Heuristically, one can take
$c_{j}=1$.

##### Property IV

For any $\widetilde{\mathbb{W}}\subseteq\widetilde{\mathbb{T}}[B({\bf
x}_{O_{j}},\rho_{j})]$, each $g_{O_{j}}$ satisfies

(8.11) $\|{g}_{O_{j}}|_{\widetilde{\mathbb{W}}}\|_{2}^{2}\leq
C_{j,\delta}^{\mathrm{IV}}(d,r)\Big{(}\frac{r}{\rho_{j}}\Big{)}^{-\frac{n-m}{2}}\|g|_{\uparrow^{j}\widetilde{\mathbb{W}}}\|_{2}^{2}+\mathrm{RapDec}(r)\|g\|_{L^{2}}^{2}.$

##### Stopping conditions

Suppose that we have the $j$th stage of [alg 1] outputs. We stop our algorithm
if one of [tiny] and [tang] holds true.

  * Stop:[tiny]

The algorithm terminates if $\rho_{j}\leq r^{\tilde{\delta}_{m-1}}$.

  * Stop:[tang]

Let $C_{\textrm{{tang}}}$ and $C_{\mathrm{alg}}$ be large, fixed dimensional
constants and $\tilde{\rho}:=\rho_{j}^{1-\tilde{\delta}_{m-1}}$. The algorithm
terminates if there exist

  * •

$\mathcal{S}$ a collection of grains $(S,B_{\tilde{\rho}})$ of dimension
$m-1$, scale $\tilde{\rho}$ and degree at most $C_{\mathrm{alg}}d$;

  * •

An assignment of a function $g_{(S,B_{\tilde{\rho}})}$ to each
$(S,B_{\tilde{\rho}})\in\mathcal{S}$ which is tangent to
$(S,B_{\tilde{\rho}})$

such that the following four conditions hold:

##### Condition I

$\sum_{O_{j}\in\mathcal{O}_{j}}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}^{p}\leq
C_{\textrm{{tang}}}\sum_{(S,B_{\tilde{\rho}})\in\mathcal{S}}\|H^{\lambda}g_{(S,B_{\tilde{\rho}})}\|_{\mathrm{BL}_{k,A_{j}/2}^{p}(B_{\tilde{\rho}})}^{p}.$

##### Condition II

$\sum_{(S,B_{\tilde{\rho}})\in\mathcal{S}}\|g_{(S,B_{\tilde{\rho}})}\|_{L^{2}(B^{n-1})}^{2}\leq
C_{\textrm{{tang}}}r^{n\tilde{\delta}_{m}}\sum_{O_{j}\in\mathcal{O}_{j}}\|g_{O_{j}}\|_{L^{2}(B^{n-1})}^{2}.$

##### Condition III

$\max_{(S,B_{\tilde{\rho}})\in\mathcal{S}}\|g_{(S,B_{\tilde{\rho}})}\|_{2}^{2}\leq
C_{\textrm{{tang}}}\max_{O_{j}\in\mathcal{O}_{j}}\|g_{O_{j}}\|_{2}^{2}.$

To state the last condition, we need to introduce some notations. Let us
denote by $\tilde{{\bf x}}$ the center of $B_{\tilde{\rho}}$. Given
$\widetilde{\mathbb{W}}\subset\widetilde{\mathbb{T}}[B(\tilde{{\bf
x}},\tilde{\rho})]$, we denote by $\uparrow\\!\widetilde{\mathbb{W}}$ the set
of all $T_{\theta,v}({\bf x}_{O_{j}})\in\mathbb{T}[B({\bf
x}_{O_{j}},\rho_{j})]$ for which there exists some
$\widetilde{T}_{\tilde{\theta},\tilde{v}}(\tilde{{\bf
x}})\in\widetilde{\mathbb{W}}$ satisfying

(8.12)
$\text{dist}(\tilde{\theta},\theta)\lesssim\tilde{\rho}^{-1/2},\quad\text{dist}(\widetilde{T}_{\tilde{\theta},\tilde{v}}(\tilde{{\bf
x}}),\,T_{\theta,v}({\bf x}_{O_{j}})\cap B(\tilde{{\bf
x}},\tilde{\rho})\big{)}\lesssim\rho_{j}^{1/2+\delta}.$

##### Condition IV

Given $(S,B(\tilde{{\bf x}},\tilde{\rho}))\in\mathcal{S}$ there exists some
$O_{j}\in\mathcal{O}_{j}$ such that

$\|{g}_{(S,B_{\tilde{\rho}})}|_{\widetilde{\mathbb{W}}}\|_{2}^{2}\leq
C_{\textrm{{tang}}}\|g_{O_{j}}|_{\uparrow\widetilde{\mathbb{W}}}\|_{2}^{2}$

holds for all
$\widetilde{\mathbb{W}}\subseteq\widetilde{\mathbb{T}}[B(\tilde{{\bf
x}},\tilde{\rho})]$.

###  8.3. A construction of outputs in the first algorithm

In this subsection, we construct outputs and show that they satisfy the
desired properties. Let $d$ be a sufficiently large number, which will be
determined later. We first define the constants

(8.13)
$\begin{split}C_{j,\delta}^{\mathrm{I}}(d,r)&:=d^{\\#_{\mbox{\scriptsize$\texttt{c}$}}(j)\delta}(\log{r})^{2p\\#_{\mbox{\scriptsize$\texttt{a}$}}(j)(1+\delta)},\\\
C_{j,\delta}^{\mathrm{II}}(d)&:=d^{\\#_{\mbox{\scriptsize$\texttt{c}$}}(j)\delta+n\\#_{\mbox{\scriptsize$\texttt{a}$}}(j)(1+\delta)},\\\
C_{j,\delta}^{\mathrm{III}}(d,r)&:=d^{\\#_{\mbox{\scriptsize$\texttt{c}$}}(j)\delta+\\#_{\mbox{\scriptsize$\texttt{a}$}}(j)\delta}r^{C\\#_{\mbox{\scriptsize$\texttt{a}$}}(j)\delta_{m}},\\\
C_{j,\delta}^{\mathrm{IV}}(d,r)&:=d^{j\delta}r^{C\\#_{\mbox{\scriptsize$\texttt{a}$}}(j)\delta_{m}},\end{split}$

and define the initial outputs

  * •

$\rho_{0}:=r$,
$\\#_{\mbox{\small$\texttt{a}$}}(0)=\\#_{\mbox{\small$\texttt{c}$}}(0):=0$.

  * •

$\mathcal{O}_{0}:=\\{\mathbb{R}^{n}\\}$ and $Z_{O_{0}}=Z$.

  * •

$g_{\mathbb{R}^{n}}:=g$.

Note that (8.6) holds true. Properties I, II, III, and IV are also vacuously
true with the initial outputs.

Let us now assume that we have the outputs of $j$th stage and the stopping
conditions fail. We need to construct the outputs of $(j+1)$th stage
satisfying all the desired properties. For each function $g_{O_{j}}$, by the
tangency assumption and Property III of $g_{O_{j}}$, we obtain

(8.14)
$\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}=\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j}\cap
N_{\rho_{j}^{1/2+\delta_{m}}(Z+{\bf
y}_{O_{j}})})}+\mathrm{RapDec}(r)\|g\|_{2}^{p}.$

Hence, we can apply the polynomial partitioning lemma to the first term on the
right hand side as in the discussion of Section 8.1. Let us denote by
$\mathcal{O}_{j,\mathrm{cell}}$ the subcollection of $\mathcal{O}_{j}$
consisting of all the cells for which the cellular case holds. We define
$\mathcal{O}_{j,\mathrm{alg}}:=\mathcal{O}_{j}\setminus\mathcal{O}_{j,\mathrm{cell}}$.
By Property I of the $j$th outputs, we have

(8.15) $\begin{split}\|H^{\lambda}g\|_{\mathrm{BL}_{k,A_{j}}^{p}(B({\bf
x}_{0},r))}^{p}&\leq
C_{j,\delta}^{\mathrm{I}}(d,r)\Big{(}\sum_{O_{j}\in\mathcal{O}_{j,\mathrm{cell}}}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}^{p}+\sum_{O_{j}\in\mathcal{O}_{j,\mathrm{alg}}}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}^{p}\Big{)}\\\
&+\big{(}jr^{-N}+\mathrm{RapDec}(r)\big{)}\|g\|_{2}^{p}.\end{split}$

There are two cases depending on which term dominates.

#### Cellular-dominant case

Consider the case that the first term on the right hand side of (8.15)
dominates the second term. In this case, we have

(8.16) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A_{j}}^{p}(B({\bf x}_{0},r))}^{p}\leq
2C_{j,\delta}^{\mathrm{I}}(d,r)\sum_{O_{j}\in\mathcal{O}_{j,\mathrm{cell}}}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}^{p}+\big{(}jr^{-N}+\mathrm{RapDec}(r)\big{)}\|g\|_{2}^{p}.$

We take the outputs

(8.17)
$\rho_{j+1}:=\rho_{j}/2,\;\;\;\\#_{\mbox{\small$\texttt{c}$}}(j+1)=\\#_{\mbox{\small$\texttt{c}$}}(j)+1,\;\;\;\\#_{\mbox{\small$\texttt{a}$}}(j+1)=\\#_{\mbox{\small$\texttt{a}$}}(j).$

Let us now construct the collection of step $j+1$ cells $\mathcal{O}_{j+1}$
and $\\{g_{{O}_{j+1}}\\}_{O_{j+1}\in\mathcal{O}_{j+1}}$ so that they satisfy
the desired properties mentioned in the algorithm. Since we are in the
cellular case, for every $O_{j}\in\mathcal{O}_{j,\mathrm{cell}}$, we have a
polynomial $P$, depending on the choice of $O_{j}$, of degree at most $d$ and
we have the following properties:

  * •

The number of connected components of $\mathbb{R}^{n}\setminus Z(P)$ is
comparable to $d^{m}$.

  * •

For each connected component $O^{\prime}$ of $\mathbb{R}^{n}\setminus Z(P)$,
define the shrunken cell $O=O^{\prime}\setminus N_{R^{1/2+\delta_{m}}}(Z(P))$.
Then

(8.18)
$\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}^{p}\lesssim
d^{m}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O)}^{p}.$

  * •

The number of the shrunken cells $O$ is comparable to $d^{m}$.

  * •

The diameter of $O$ is at most $r/2$.

We denote by $\mathcal{O}(O_{j})$ the collection of the shrunken cells. As
mentioned above, we know that $\\#\mathcal{O}(O_{j})\sim d^{m}$ and each
$O\in\mathcal{O}(O_{j})$ has diameter at most $\rho_{j+1}$, and

(8.19)
$\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}^{p}\lesssim
d^{m}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O)}^{p},$

and thus,

(8.20)
$\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}^{p}\lesssim\sum_{O\in\mathcal{O}}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O)}^{p}.$

Let us denote by $B({\bf x}_{O},\rho_{j+1})$ the ball containing $O$. Define

(8.21) $\mathbb{T}_{O}:=\mathbb{T}_{O}[B({{\bf
x}_{O_{j}}},\rho_{j})]:=\\{T\in\mathbb{T}_{Z+{\bf y}_{O_{j}}}[B({\bf
x}_{O_{j}},\rho_{j})]:T\cap O\neq\varnothing\\},$ (8.22)
$\widetilde{\mathbb{T}}_{O}:=\widetilde{\mathbb{T}}_{O}[B({\bf
x}_{O},\rho_{j+1})]:=\bigcup_{T_{\theta,v}\in\mathbb{T}_{O}}\widetilde{\mathbb{T}}_{\theta,v}[B({\bf
x}_{O},\rho_{j+1})],$

where $\widetilde{\mathbb{T}}_{\theta,v}[B({\bf x}_{O},\rho_{j+1})]$ was
defined in (5.3). By Lemma 5.4, it holds that

(8.23)
$\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O)}\lesssim\|H^{\lambda}((g_{O_{j}}|_{\mathbb{T}_{O}})|_{\widetilde{\mathbb{T}}_{O}})\|_{\mathrm{BL}_{k,A_{j}}^{p}(O)}+\mathrm{RapDec}(r)\|g\|_{2}.$

By Lemma 5.5 and a simple calculation, we know that

(8.24)
$\begin{split}\bigcup_{\widetilde{T}\in\widetilde{\mathbb{T}}_{O}}\widetilde{T}&\subset
N_{2\rho_{j}^{1/2+\delta_{m}}}(Z+{\bf y}_{O_{j}})\\\
&\subset\bigcup_{b\in\mathbb{Z}^{n}:|b|\lesssim
1}N_{\rho_{j+1}^{1/2+\delta_{m}}/2}\big{(}Z+{\bf
y}_{O_{j}}+({\rho_{j+1}^{1/2+\delta_{m}}}/{2})b\big{)}.\end{split}$

Thus, every tube $\widetilde{T}\in\widetilde{\mathbb{T}}_{O}$ intersects
$N_{\rho_{j+1}^{1/2+\delta_{m}}/2}\big{(}Z+{\bf
y}_{O_{j}}+({\rho_{j+1}^{1/2+\delta_{m}}}/{2})b\big{)}$ for some $b$ depending
on the choice of $\widetilde{T}$. We now write

(8.25) $\widetilde{\mathbb{T}}_{O}=\bigsqcup_{b\in\mathbb{Z}^{n}:|b|\lesssim
1}\widetilde{\mathbb{T}}_{O,b}$

where $\widetilde{\mathbb{T}}_{O,b}$ is some sub-collection of
$\widetilde{\mathbb{T}}_{O}$ satisfying

(8.26)
$\widetilde{\mathbb{T}}_{O,b}\subset\\{\widetilde{T}\in\widetilde{\mathbb{T}}_{O}:\widetilde{T}\cap
N_{\rho_{j+1}^{1/2+\delta_{m}}/2}\big{(}Z+{\bf
y}_{O_{j}}+({\rho_{j+1}^{1/2+\delta_{m}}}/{2})b\big{)}\neq\varnothing\\}.$

Define

(8.27) $\mathcal{O}_{j+1}(O_{j}):=\Big{\\{}O\cap
N_{\rho_{j+1}^{1/2+\delta_{m}}/2}\big{(}Z+{\bf
y}_{O_{j}}+(\rho_{j+1}^{1/2+\delta_{m}}/2)b\big{)}:O\in\mathcal{O}(O_{j}),\;\;b\in\mathbb{Z}^{n}~{}\text{with}~{}|b|\lesssim
1\Big{\\}},$ (8.28)
$\mathcal{O}_{j+1}:=\bigcup_{O_{j}\in\mathcal{O}_{j,\mathrm{cell}}}\mathcal{O}_{j+1}(O_{j}).$

For every $O_{j+1}\in\mathcal{O}_{j+1}$, there exist corresponding $O_{j}$,
$b$, and $O$. Define a translate of the variety

(8.29) $Z_{O_{j+1}}:=Z+{\bf y}_{O_{j+1}}:=Z+{\bf
y}_{O_{j}}+(\rho_{j+1}^{1/2+\delta_{m}}/2)b$

and a function

(8.30)
$g_{O_{j+1}}:=\big{(}(g_{O_{j}})|_{\mathbb{T}_{O}}\big{)}\big{|}_{\widetilde{\mathbb{T}}_{O,b}}.$

Let us define ${\bf x}_{O_{j+1}}:={\bf x}_{O}$. By Lemma 7.10, we have
$\widetilde{\mathbb{T}}_{O,b}\subset\widetilde{\mathbb{T}}_{Z_{O_{j+1}}}[B({{\bf
x}}_{O_{j+1}},\rho_{j+1})]$.

Via Lemma 4.2 (the $L^{2}$ orthogonality), one has

(8.31)
$\begin{split}\sum_{O_{j+1}\in\mathcal{O}_{j+1}(O_{j})}\|g_{O_{j+1}}\|_{2}^{2}&\lesssim\sum_{O\in\mathcal{O}(O_{j})}\sum_{b:|b|\lesssim
1}\|(g_{O_{j}}|_{\mathbb{T}_{O}})|_{\widetilde{\mathbb{T}}_{O,b}}\|_{2}^{2}\\\
&\lesssim\sum_{O\in\mathcal{O}(O_{j})}\|g_{O_{j}}|_{\mathbb{T}_{O}}\|_{2}^{2}\\\
&\lesssim\sum_{O\in\mathcal{O}(O_{j})}\sum_{T\in\mathbb{T}_{O}}\|(g_{O_{j}})_{T}\|_{2}^{2}.\end{split}$

By the fundamental theorem of algebra, we know that each tube
$T_{\theta,v}\in\mathbb{T}[B({\bf x}_{O_{j}},\rho_{j})]$ can intersect at most
$O(d)$ cells $O_{j+1}\in\mathcal{O}_{j+1}(O_{j})$. Therefore, we further have

(8.32)
$\begin{split}\sum_{O\in\mathcal{O}(O_{j})}\sum_{T\in\mathbb{T}_{O}}\|(g_{O_{j}})_{T}\|_{2}^{2}&\lesssim\sum_{O\in\mathcal{O}(O_{j})}\sum_{T\in\mathbb{T}[B({\bf
x}_{O_{j}},\rho_{j})]:T\cap O\neq\varnothing}\|(g_{O_{j}})_{T}\|_{2}^{2}\\\
&\lesssim\sum_{T\in\mathbb{T}[B({\bf
x}_{O_{j}},\rho_{j})]}\sum_{O\in\mathcal{O}(O_{j}):T\cap
O\neq\varnothing}\|(g_{O_{j}})_{T}\|_{2}^{2}\lesssim
d\|g_{O_{j}}\|_{2}^{2}.\end{split}$

The above two estimates lead to

(8.33)
$\sum_{O_{j+1}\in\mathcal{O}_{j+1}(O_{j})}\|g_{O_{j+1}}\|_{2}^{2}\lesssim
d\|g_{O_{j}}\|_{2}^{2}.$

Since we know that $\\#\mathcal{O}_{j+1}(O_{j})\sim d^{m}$, by pigeonholing
argument, we can take a subcollection of $\mathcal{O}_{j+1}(O_{j})$ such that
the cardinality is similar to $\mathcal{O}_{j+1}(O_{j})$ and every element
$O_{j+1}$ of the subcollection satisfies

(8.34) $\|g_{O_{j+1}}\|_{2}^{2}\lesssim d^{-(m-1)}\|g_{O_{j}}\|_{2}^{2}.$

By abusing the notation, we still call such subcollection
$\mathcal{O}_{j+1}(O_{j})$ and their union $\mathcal{O}_{j+1}$. This completes
the construction of our outputs.

It remains to show that our outputs satisfy the desired properties. The
function $g_{O_{j+1}}$ is tangent to the grain $(Z_{O_{j+1}},B_{O_{j+1}})$
because of
$\widetilde{\mathbb{T}}_{O,b}\subset\widetilde{\mathbb{T}}_{Z_{O_{j+1}}}[B({{\bf
x}_{O_{j+1}}},\rho_{j+1})]$. Property I, II, and III follow from the arguments
in page 254–256 of [HR19]. We follow pages 19–20 of [HZ20] for Property IV.
Our proofs are very similar to theirs, so we only give a sketch of the proof.

Let us start with Property I. By (8.16), (8.20), (8.23), (8.25) and (8.30)
with the triangle and Hölder’s inequality, we obtain

(8.35) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A_{j}}^{p}(B({\bf x}_{0},r))}^{p}\leq
CC_{j,\delta}^{\mathrm{I}}(d,r)\sum_{O_{j+1}\in\mathcal{O}_{j+1}}\|H^{\lambda}g_{O_{j+1}}\|_{\mathrm{BL}_{k,A_{j+1}}^{p}(O_{j+1})}^{p}+(j+1)r^{-N}\|g\|_{2}^{p}.$

Property I follows by taking $d$ sufficiently large so that
$CC_{j,\delta}^{\mathrm{I}}(d,r)\leq C_{j+1,\delta}^{\mathrm{I}}(d,r)$. To
prove Property II, we take the sum over $O_{j}\in\mathcal{O}_{j}$ to the
inequality (8.33) and obtain

(8.36) $\sum_{O_{j+1}\in\mathcal{O}_{j+1}}\|g_{O_{j+1}}\|_{2}^{2}\lesssim
d\sum_{O_{j}\in\mathcal{O}_{j}}\|g_{O_{j}}\|_{2}^{2}\lesssim
C_{j,\delta}^{\mathrm{II}}(d)d^{1+\\#_{\mbox{\scriptsize$\texttt{c}$}}(j)}\|g\|_{2}^{2},$

where the second inequality follows from Property II of the $j$th outputs.
Property II follows by taking $d$ sufficiently large so that
$CC_{j,\delta}^{\mathrm{II}}(d)\leq C_{j+1,\delta}^{\mathrm{II}}(d)$.
Similarly, Property III follows from the inequality (8.34) and Property II of
the $j$th outputs. We leave out the details.

Finally, let us prove Property IV. Recall that the notations
$\uparrow^{j}\\!\\!\widetilde{\mathbb{W}}$ and
$\uparrow\\!\\!\widetilde{\mathbb{W}}$ were introduced in (8.10) and in
(8.12). By an application of Lemma 7.7, (7.7), and Property IV of the $j$th
outputs, we obtain

(8.37)
$\begin{split}\|g_{O_{j+1}}|_{\widetilde{\mathbb{W}}}\|_{2}^{2}&\lesssim\|g_{O_{j}}|_{\uparrow\widetilde{\mathbb{W}}}\|_{2}^{2}+\mathrm{RapDec}(r)\|g\|_{2}^{2}\\\
&\lesssim
C_{j,\delta}^{\mathrm{IV}}(d,r)\Big{(}\frac{r}{\rho_{j}}\Big{)}^{-\frac{n-m}{2}}\|g|_{\uparrow^{j}(\uparrow\widetilde{\mathbb{W}})}\|_{2}^{2}+\mathrm{RapDec}(r)\|g\|_{L^{2}}^{2}.\end{split}$

It is proved that
$\uparrow^{j}\\!\\!(\uparrow\\!\\!\widetilde{\mathbb{W}})\subset\uparrow^{j+1}\\!\\!\widetilde{\mathbb{W}}$
on page 20 of [HZ20]. Therefore, by arguing similarly as in the proof of Lemma
7.7, and by modifying the constant $c_{j+1}$ appropriately and taking $d$
sufficiently large, we obtain Property IV. This finishes the discussion on the
cellular-dominant case.

#### Algebraic-dominant case

Consider the case that the second term on the right hand side of (8.15)
dominates the first term. Recall (8.14):

(8.38)
$\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}=\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j}\cap
N_{\rho_{j}^{1/2+\delta_{m}}(Z+{\bf
y}_{O_{j}})})}+\mathrm{RapDec}(r)\|g\|_{2}^{p}.$

Since we are in the algebraic case, we have

(8.39)
$\begin{split}\|H^{\lambda}g\|_{\mathrm{BL}_{k,A_{j}}^{p}(B_{r})}^{p}\leq
2C_{j,\delta}^{\mathrm{I}}(d,r)\sum_{O_{j}\in\mathcal{O}_{j,\mathrm{alg}}}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j}\cap
N_{\rho^{1/2+\delta_{m}}}(Y(O_{j})))}^{p}+(jr^{-N}+\mathrm{RapDec}(r))\|g\|_{2}^{p}\end{split}$

for some $(m-1)$-dimensional transverse complete intersection $Y(O_{j})$ that
is defined using polynomials of degree at most $d$. Abbreviate $Y(O_{j})$ to
$Y$ for simplicity. We take the outputs

(8.40)
$\rho_{j+1}:=\rho_{j}^{1-\tilde{\delta}_{m-1}},\;\;\;\\#_{\mbox{\small$\texttt{c}$}}(j+1)=\\#_{\mbox{\small$\texttt{c}$}}(j),\;\;\;\\#_{\mbox{\small$\texttt{a}$}}(j+1)=\\#_{\mbox{\small$\texttt{a}$}}(j)+1.$

It remains to define $\mathcal{O}_{j+1}$ and
$\\{g_{{O}_{j+1}}\\}_{O_{j+1}\in\mathcal{O}_{j+1}}$, and prove the desired
properties. Given $O_{j}\in\mathcal{O}_{j,\mathrm{alg}}$, we take a collection
$\mathcal{B}(O_{j})$ of finitely overlapping balls of $\rho_{j+1}$ covering
$O_{j}\cap N_{\rho_{j}^{1/2+\delta_{m}}}Y$. For every
$B\in\mathcal{B}(O_{j})$, we record tubes intersecting $B$;

(8.41) $\mathbb{T}_{B}:=\\{T\in\mathbb{T}_{Z_{O_{j}}}[B({\bf
x}_{O_{j}},\rho_{j})]:T\cap B\neq\varnothing\\}.$

Let us define tangent and transverse tubes.

######  Definition 8.2.

We denote by $\mathbb{T}_{B,\mathrm{tang}}$ the collection of all the tubes
$T_{\theta,v}\in\mathbb{T}_{B}$ such that

  1. (1)

$T_{\theta,v}\cap 2B\subset N_{2\rho_{j+1}^{1/2+\delta_{m-1}}}(Y)$;

  2. (2)

For every $x\in T_{\theta,v}$ and $y\in Y\cap 2B$ satisfying
$|y-x|\lesssim\rho_{j+1}^{1/2+\delta_{m-1}}$, it holds that

(8.42)
$\measuredangle(G^{\lambda}(\omega_{\theta}),T_{y}Y)\lesssim\rho_{j+1}^{-1/2+\delta_{m-1}}.$

We define a collection of transverse tubes by
$\mathbb{T}_{B,\mathrm{trans}}:=\mathbb{T}_{B}\,\setminus\,\mathbb{T}_{B,\mathrm{tang}}$,
and define functions

(8.43)
$g_{B,\mathrm{tang}}:=(g_{O_{j}})|_{\mathbb{T}_{B,\mathrm{tang}}},\;\;\;\;g_{B,\mathrm{trans}}:=(g_{O_{j}})|_{\mathbb{T}_{B,\mathrm{trans}}}.$

Since for any ball $B\in\mathcal{B}(O_{j})$ the wave packets not intersecting
$B$ are negligible, we have

(8.44)
$H^{\lambda}g_{O_{j}}(x)=H^{\lambda}g_{B,\mathrm{tang}}(x)+H^{\lambda}g_{B,\mathrm{trans}}(x)+\mathrm{RapDec}(r)\|g\|_{2},\;\;\;\;x\in
B.$

By the finite sub-additivity of the broad norm (See Lemma 6.1 of [GHI19]), we
obtain

(8.45)
$\begin{split}&\sum_{O_{j}\in\mathcal{O}_{j,\mathrm{alg}}}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j}\cap
N_{\rho^{1/2+\delta_{m}}}(Y))}^{p}\\\
&\sim\sum_{O_{j}\in\mathcal{O}_{j,\mathrm{alg}}}\sum_{B\in\mathcal{B}(O_{j})}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(B)}^{p}\\\
&\lesssim\sum_{O_{j}\in\mathcal{O}_{j,\mathrm{alg}}}\sum_{B\in\mathcal{B}(O_{j})}\Big{(}\|H^{\lambda}g_{B,\mathrm{tang}}\|_{\mathrm{BL}_{k,A_{j+1}}^{p}(B)}^{p}+\|H^{\lambda}g_{B,\mathrm{trans}}\|_{\mathrm{BL}_{k,A_{j+1}}^{p}(B)}^{p}\Big{)}+\mathrm{RapDec}(r)\|g\|_{2}^{p}.\end{split}$

Note that by the failure of the stopping condition of [tang], it holds that

(8.46)
$\sum_{O_{j}}\sum_{B\in\mathcal{B}(O_{j})}\|H^{\lambda}g_{B,\mathrm{tang}}\|_{\mathrm{BL}_{k,A_{j+1}}^{p}(B)}^{p}\leq
C_{\mathrm{tang}}^{-1}\sum_{O_{j}\in\mathcal{O}_{j}}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j})}^{p}.$

Indeed, we take collections of grains
$\mathcal{S}(O_{j}):=\\{(Y(O_{j}),B):B\in\mathcal{B}(O_{j})\\}$ and
$\mathcal{S}:=\bigcup_{O_{j}}\mathcal{S}(O_{j})$, and take functions
$g_{(Y,B)}:=g_{B,\mathrm{tang}}$. By Lemma 5.5 and (8.43), the function
$g_{B,\mathrm{tang}}$ is tangent to $(Y(O_{j}),B)$. Also, one may see that
Condition II, III and IV of the stopping condition are satisfied. By this and
the failure of the stopping condition, Condition I fails and it gives (8.46).

Since we are in the algebraic case and the constant $C_{\mathrm{tang}}$ is
sufficiently large, the contribution from the tangential wave packets can be
absorbed into the left hand side of (8.45) and we obtain

(8.47)
$\sum_{O_{j}\in\mathcal{O}_{j,\mathrm{alg}}}\|H^{\lambda}g_{O_{j}}\|_{\mathrm{BL}_{k,A_{j}}^{p}(O_{j}\cap
N_{\rho^{1/2+\delta_{m}}}(Y))}^{p}\lesssim\sum_{O_{j}\in\mathcal{O}_{j,\mathrm{alg}}}\sum_{B\in\mathcal{B}(O_{j})}\|H^{\lambda}g_{B,\mathrm{trans}}\|_{\mathrm{BL}_{k,A_{j+1}}^{p}(B)}^{p}+\mathrm{RapDec}(r)\|g\|_{2}^{p}.$

We apply Lemma 7.9 to each $g_{B,\mathrm{trans}}$ and obtain a collection
$\mathcal{B}$ of points such that

(8.48)
$\|H^{\lambda}g_{B,\mathrm{trans}}\|_{\mathrm{BL}_{k,A_{j+1}}^{p}(B)}^{p}\lesssim(\log{r})^{2p}\sum_{b\in\mathcal{B}}\|H^{\lambda}{g}_{B,\mathrm{trans},b}\|_{\mathrm{BL}_{k,A_{k+1}}^{p}(B\cap
N_{\rho_{j+1}^{1/2+\delta_{m}}}(Z_{O_{j}}+b))}^{p}$

and

(8.49)
$\sum_{b\in\mathcal{B}}\|{g}_{B,\mathrm{trans},b}\|_{2}^{2}\lesssim\|g_{B,\mathrm{trans}}\|_{2}^{2},$

where ${g}_{B,\mathrm{trans},b}:=(g_{B,\mathrm{trans}})_{b}$.

We define the collection of step $j+1$ cells by

(8.50) $\mathcal{O}_{j+1}(O_{j}):=\\{B\cap
N_{\rho_{j+1}^{1/2+\delta_{m}}}(Z+{\bf
y}_{O_{j}}+b):B\in\mathcal{B}(O_{j})\;\;\mathrm{and}\;\;b\in\mathcal{B}\\},$
(8.51)
$\mathcal{O}_{j+1}:=\bigcup_{O_{j}\in\mathcal{O}_{j,\mathrm{alg}}}\mathcal{O}_{j+1}(O_{j}).$

For every $O_{j+1}\in\mathcal{O}_{j+1}$, we define a function
$g_{O_{j+1}}:={g}_{B,\mathrm{trans},b}$ and a point ${\bf y}_{O_{j+1}}:={\bf
y}_{O_{j}}+b$.

It remains to show that all these outputs satisfy the desired properties. We
will follow arguments in pages 259–261 of [HR19] for Property I, II, and III,
and pages 19–20 of [HZ20] for Property IV. These arguments are also similar to
the counterpart of the cellular-dominant case. Hence, we give only a sketch
here. First, it is straightforward to see that Property I follows from (8.39),
(8.47) and (8.48) together with Property 1 of the $j$th outputs. Before
proving Property II, we recall that our tubes are straight. We apply Lemma 5.7
of [Gut18] to the wave packets at scale $\rho_{j+1}$, and by the
$L^{2}$-orthogonality, we obtain

(8.52) $\sum_{O_{j+1}}\|g_{O_{j+1}}\|_{2}^{2}\lesssim
d^{n}\sum_{O_{j}}\|g_{O_{j}}\|_{2}^{2}.$

Property II now follows from the above inequality with Property II of the
$j$th outputs. To prove Property III, we apply Lemma 7.8 to the function
$g_{B,\mathrm{trans}}$ with
$\widetilde{\mathbb{W}}=\widetilde{\mathbb{T}}_{b}^{\prime}$ in defined (7.22)
and by the $L^{2}$-orthogonality, we obtain

(8.53) $\begin{split}\|g_{O_{j+1}}\|_{2}^{2}\lesssim
r^{O(\delta_{m})}(\frac{\rho_{j}}{\rho_{j+1}})^{-\frac{n-m}{2}}\|g_{O_{j}}\|_{2}^{2}+\mathrm{RapDec}(r)\|g\|_{2}^{2}.\end{split}$

It suffices to combine this inequality with Property III of the $j$th outputs.
Property IV also follows from an application of Lemma 7.8. We leave out the
details.

##  9\. A proof of Theorem 3.4

In this section, we prove Theorem 3.4, that is, we prove

(9.1)
$\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{R})}\lesssim_{\epsilon}R^{\epsilon}\|g\|_{L^{2}}^{2/p}\|g\|_{L^{\infty}}^{1-2/p}$

for every $1\leq R\leq\lambda$ and ball
$B_{R}\subset[-3C_{n}\lambda,3C_{n}\lambda]^{n-1}\times[R/C_{n},C_{n}\lambda]$.
We follow the proofs in Section 4, 6.3, and 6.4 of [HZ20]. Note that (9.1) is
obviously true unless $g$ satisfies the non-degenerate hypothesis:

(9.2) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{R})}\gtrsim
R^{\epsilon}\|g\|_{L^{2}}.$

Hence, in this section, we always assume that $g$ satisfies the non-degenerate
hypothesis.

Consider a family of Lebesgue exponents $p_{i}$ for $k\leq i\leq n$ satisfying

$p_{k}\geq p_{k+1}\geq\dots\geq p_{n}=:p\geq 2$

and define $0\leq\alpha_{i},\beta_{i}\leq 1$ in terms of the $p_{i}$ by

$\alpha_{i}:=\Big{(}\frac{1}{2}-\frac{1}{p_{i}}\Big{)}^{-1}\Big{(}\frac{1}{2}-\frac{1}{p_{i+1}}\Big{)}\quad\textrm{and}\quad\beta_{i}:=\Big{(}\frac{1}{2}-\frac{1}{p_{i}}\Big{)}^{-1}\Big{(}\frac{1}{2}-\frac{1}{p_{n}}\Big{)}$

for $k\leq i\leq n-1$ and $\alpha_{n}:=:\beta_{n}:=:\beta_{n+1}:=1$. All the
exponents $p_{i}$ will be determined later.

###  9.1. The second algorithm

Let us explain the second algorithm [alg 2].

Input The algorithm takes as its input:

  * •

A ball $B({\bf
x}_{0},R)\subset[-3C_{n}\lambda,3C_{n}\lambda]^{n-1}\times[R/C_{n},C_{n}\lambda]$.

  * •

An admissible large integer $A\in\mathbb{N}$.

  * •

A function $g\in L^{1}$ satisfying the non-degenerate hypothesis (9.2).

Output The $(n+1-l)$th step of the recursion will produce:

  * •

An $(n+1-l)$-tuple of:

    * –

Scales $\vec{r}_{l}=(r_{n},\dots,r_{l})$ satisfying
$R=r_{n}>r_{n-1}>\dots>r_{l}$;

    * –

Large and (in general) non-admissible parameters
$\vec{D}_{l}=(D_{n},\dots,D_{l})$;

    * –

Integers $\vec{A}_{l}=(A_{n},\ldots,A_{l})$ such that
$A=A_{n}>A_{n-1}>\cdots>A_{l}$.

  * •

For $l\leq l^{\prime}\leq n$ a family $\vec{\mathcal{S}}_{l^{\prime}}$ of
level $n-l^{\prime}$ multigrains. Each
$\vec{S}_{l^{\prime}}\in\vec{\mathcal{S}}_{l^{\prime}}$ has multiscale
$\vec{r}_{l^{\prime}}=(r_{n},\cdots,r_{l^{\prime}})$ and complexity
$O_{\epsilon}(1)$. The families have a nested structure in the sense that for
each $l\leq l^{\prime}<n$ and each
$\vec{S}_{l^{\prime}}\in\vec{\mathcal{S}}_{l^{\prime}}$, there exists some
$\vec{S}_{l^{\prime}+1}\in\vec{\mathcal{S}}_{l^{\prime}+1}$ such that
$\vec{S}_{l^{\prime}}\preceq\vec{S}_{l^{\prime}+1}$.

  * •

For $l\leq l^{\prime}\leq n$ an assignment of a function
$g_{\vec{S}_{l^{\prime}}}$ to each
$\vec{S}_{l^{\prime}}\in\vec{\mathcal{S}}_{l^{\prime}}$. Each
$g_{\vec{S}_{l^{\prime}}}$ is tangent to
$(S_{l^{\prime}},B_{r_{l^{\prime}}})$, the final component of
$\vec{S}_{l^{\prime}}$. Moreover, $S_{l^{\prime}}$ is of dimension
$l^{\prime}$.

All these outputs will be chosen so that the following properties hold true.

##### Property I

The inequality holds true

(9.3) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{R})}\lesssim
M(\vec{r}_{l},\vec{D}_{l})R^{O(\epsilon_{\circ})}\|g\|_{L^{2}(B^{n-1})}^{1-\beta_{l}}\Big{(}\sum_{\vec{S}_{l}\in\mathcal{\vec{S}}_{l}}\|H^{\lambda}g_{\vec{S}_{l}}\|_{\mathrm{BL}_{k,A_{l}}^{p_{l}}(B_{r_{l}})}^{p_{l}}\Big{)}^{\frac{\beta_{l}}{p_{l}}},$

where the pair $(S_{l},B_{r_{l}})$ is the last component of the multigrain
$\vec{S}_{l}$ and

$M(\vec{r}_{l},\vec{D}_{l}):=\Big{(}\prod_{i=l}^{n}D_{i}\Big{)}^{(n-l)\delta}\Big{(}\prod_{i=l}^{n}r_{i}^{\frac{1}{2}(\beta_{i+1}-\beta_{i})}D_{i}^{\frac{1}{2}(\beta_{i+1}-\beta_{l})}\Big{)}.$

##### Property II

(9.4)
$\sum_{\vec{S}_{l}\in\mathcal{\vec{S}}_{l}}\|g_{\vec{S}_{l}}\|_{2}^{2}\lesssim\Big{(}\prod_{i=l}^{n}D_{i}^{1+\delta}\Big{)}R^{O(\epsilon_{\circ})}\|g\|_{L^{2}(B^{n-1})}^{2}.$

##### Property III

For $l^{\prime}$ with $l+1\leq l^{\prime}\leq n$,

(9.5)
$\max_{\vec{S}_{l}\in\mathcal{\vec{S}}_{l}}\|g_{\vec{S}_{l}}\|_{2}^{2}\lesssim\Big{(}\prod_{i=l}^{l^{\prime}-1}\big{(}\frac{r_{i+1}}{r_{i}}\big{)}^{-\frac{n-i}{2}}D_{i}^{-i+\delta}\Big{)}R^{O(\epsilon_{\circ})}\max_{\vec{S}_{l^{\prime}}\in\vec{\mathcal{S}}_{l^{\prime}}}\|g_{\vec{S}_{l^{\prime}}}\|_{2}^{2}.$

To state the last property, we need to introduce some notations. Let us
consider a multigrain
$\vec{S}_{l}=(\mathcal{G}_{n},\ldots,\mathcal{G}_{l})\in\vec{\mathcal{S}}_{l}$
and denote $\mathcal{G}_{i}=(S_{i},B({\bf x}_{n-i},r_{i}))$. Given
$\widetilde{\mathbb{W}}\subseteq\widetilde{\mathbb{T}}[B({\bf
x}_{n-l},r_{l})]$, let $\uparrow\uparrow_{l}\\!\\!\widetilde{\mathbb{W}}$
denote the set of wave packets $T_{\theta,v}\in\mathbb{T}[B({\bf
x}_{n-l-1},r_{l+1})]$ for which there exists some
$\widetilde{T}_{\tilde{\theta},\tilde{v}}\in\widetilde{\mathbb{W}}$ satisfying

(9.6) $\text{dist}(\tilde{\theta},\theta)\leq
C_{\circ}r_{l}^{-1/2}\quad\textrm{and}\quad\text{dist}\big{(}\widetilde{T}_{\tilde{\theta},\tilde{v}}({\bf
x}_{n-l}),\,T_{\theta,v}({\bf x}_{n-l-1})\cap B({\bf
x}_{n-l},r_{l})\big{)}\leq C_{\circ}r_{l+1}^{1/2+\delta}.$

Here, the constant $C_{\circ}$ is the constant mentioned in the discussion
below the inequality (8.10).

##### Property IV

Let $l\leq l^{\prime}\leq n-1$. For every
$\vec{S}_{l^{\prime}}\in\vec{\mathcal{S}}_{l^{\prime}}$ ,
$\vec{S}_{l^{\prime}+1}\in\vec{\mathcal{S}}_{l^{\prime}+1}$ with
$\vec{S}_{l^{\prime}}\preceq\vec{S}_{l^{\prime}+1}$, and
$\widetilde{\mathbb{W}}\subset\widetilde{\mathbb{T}}[B({\bf
x}_{n-l^{\prime}},r_{l^{\prime}})]$, it holds that

(9.7)
$\|{g}_{\vec{S}_{l^{\prime}}}|_{\widetilde{\mathbb{W}}}\|_{L^{2}(B^{n-1})}^{2}\lesssim\big{(}\frac{r_{l^{\prime}+1}}{r_{l^{\prime}}}\big{)}^{-\frac{n-l^{\prime}}{2}}(D_{l^{\prime}})^{\delta}R^{O(\epsilon_{\circ})}\|g_{\vec{S}_{l^{\prime}+1}}|_{(\uparrow\uparrow_{l^{\prime}}\widetilde{\mathbb{W}})^{*}}\|_{2}^{2}+\mathrm{RapDec}(R)\|g\|_{L^{2}}^{2}.$

Here, the notation $*$ was introduced in (7.6)

##### Stopping conditions

Suppose that we have the outputs of the $(n+1-l)$th stage of [alg 2]. We
terminate our algorithm if the following condition [tiny-dom] is satisfied.

  * Stop:[tiny-dom]

The following inequality holds true:

(9.8)
$\sum_{\vec{S}_{l}\in\vec{\mathcal{S}}_{l}}\|H^{\lambda}g_{\vec{S}_{l}}\|_{\mathrm{BL}_{k,A_{l}}^{p_{l}}(B_{r_{l}})}^{p_{l}}\leq
2\sum_{\vec{S}_{l}\in\vec{\mathcal{S}}_{l,tiny}}\|H^{\lambda}g_{\vec{S}_{l}}\|_{\mathrm{BL}_{k,A_{l}}^{p_{l}}(B_{r_{l}})}^{p_{l}},$

where the right-hand summation is restricted to those
$\vec{S_{l}}\in\vec{\mathcal{S}}_{l}$ for which [alg 1] terminates due to the
stopping condition [tiny].

###  9.2. A construction of outputs of the second algorithm

In this subsection, we construct the outputs and show that they satisfy the
desired properties in the algorithm. We first define the initial outputs as
follows.

  * •

$r_{n}:=R,\;\;D_{n}:=1,\;\;A_{n}:=A$.

  * •

$\vec{\mathcal{S}}_{n}:=\\{\vec{S}_{n}\\}$ and
$\vec{S}_{n}:=(\mathbb{R}^{n},B({\bf x}_{0},R))$.

  * •

$g_{\vec{S}_{n}}:=g$.

These outputs vacuously satisfy the desired properties.

Let us now assume that we have the outputs of the $(n+1-l)$th step for some
$1\leq l\leq n$ and the stopping condition [tiny-dom] fails. We need to
construct the outputs of the $(n+2-l)$th step so that they satisfy the desired
properties. By the failure of the stopping condition [tiny-dom], we know that
[alg 1] stops due to [tang]. Hence,

(9.9)
$\sum_{\vec{S}_{l}\in\vec{\mathcal{S}}_{l}}\|H^{\lambda}g_{\vec{S}_{l}}\|_{\mathrm{BL}_{k,A_{l}}^{p_{l}}(B_{r_{l}})}^{p_{l}}\leq
2\sum_{\vec{S}_{l}\in\vec{\mathcal{S}}_{l,\mathrm{tang}}}\|H^{\lambda}g_{\vec{S}_{l}}\|_{\mathrm{BL}_{k,A_{l}}^{p_{l}}(B_{r_{l}})}^{p_{l}},$

where the right-hand summation is restricted to those
$\vec{S}_{l}\in\vec{\mathcal{S}}_{l}$ for which [alg 1] stops due to [tang].
By the definition of [tang] and the first three properties of [alg 1], for
each multigrain $\vec{S}_{l}\in\vec{\mathcal{S}}_{l,\mathrm{tang}}$, there
exist

  * •

a collection $\mathcal{S}_{l-1}[\vec{S}_{l}]$ of grains of dimension $l-1$,
some scale $r_{l-1}$ and degree $O(1)$

  * •

an assignment of a function $g_{(S,B_{r_{l-1}})}$ to each
$(S,B_{r_{l-1}})\in\mathcal{S}_{l-1}[\vec{S}_{l}]$ tangent to the grain
$(S,B_{r_{l-1}})$

  * •

some parameter $D_{l-1}:=d^{\\#_{\mbox{\scriptsize$\texttt{c}$}}(j_{0})}$
where [alg 1] terminates at the $j_{0}$th stage

  * •

some parameter $A_{l-1}=A_{l}/2^{\\#_{\mbox{\scriptsize$\texttt{a}$}}(j_{0})}$

such that

(9.10)
$\displaystyle\|H^{\lambda}g_{\vec{S}_{l}}\|_{\mathrm{BL}_{k,A_{l}}^{p}(B_{r_{l}})}^{p}$
$\displaystyle\lesssim
R^{O(\epsilon_{\circ})}\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum_{(S,B_{r_{l-1}})\in\mathcal{S}_{l-1}[\vec{S}_{l}]}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\|H^{\lambda}\big{(}(g_{\vec{S}_{l}})_{(S,B_{r_{l-1}})}\big{)}\|_{\mathrm{BL}_{k,A_{l-1}}^{p}(B_{r_{l-1}})}^{p}+\mathrm{RapDec}(R)\|g_{\vec{S}_{l}}\|_{2}^{p},$
(9.11)
$\displaystyle\sum_{(S,B_{r_{l-1}})\in\mathcal{S}_{l-1}[\vec{S}_{l}]}\|$
$\displaystyle(g_{\vec{S}_{l}})_{(S,B_{r_{l-1}})}\|_{2}^{2}\lesssim
D_{l-1}^{1+\delta}R^{O(\epsilon_{\circ})}\|g_{\vec{S}_{l}}\|_{2}^{2},$ (9.12)
$\displaystyle\max_{(S,B_{r_{l-1}})\in\mathcal{S}_{l-1}[\vec{S}_{l}]}\|$
$\displaystyle(g_{\vec{S}_{l}})_{(S,B_{r_{l-1}})}\|_{2}^{2}\lesssim\Big{(}\frac{r_{l}}{r_{l-1}}\Big{)}^{-\frac{n-l}{2}}D_{l-1}^{-(l-1)+\delta}R^{O(\epsilon_{\circ})}\|g_{\vec{S}_{l}}\|_{2}^{2},$
(9.13)
$\displaystyle\|({g}_{\vec{S}_{l}})_{(S,B_{r_{l-1}})}|_{\widetilde{\mathbb{W}}}$
$\displaystyle\|_{2}^{2}\lesssim\big{(}\frac{r_{l}}{r_{l-1}}\big{)}^{-\frac{n-l}{2}}D_{l-1}^{\delta}R^{O(\epsilon_{\circ})}\|g_{\vec{S}_{l}}|_{\uparrow^{l}(\uparrow\widetilde{\mathbb{W}})}\|_{2}^{2}+\mathrm{RapDec}(R)\|g_{\vec{S}_{l}}\|_{2}^{2},$

for every sub-collection $\widetilde{\mathbb{W}}$ of the wave packets at scale
$r_{l-1}$. Here, we recall that the notations $\uparrow^{l}$ and $\uparrow$
are defined in $\eqref{uparrowj}$ and $\eqref{uparrow1}$, respectively.

Note that the parameters $r_{l-1}$, $D_{l-1}$, and $A_{l-1}$ may depend on the
choice of the multigrain $\vec{S}_{l}$. To take uniform parameters independent
of the choice, we apply a pigeonholing argument by losing some
$(\log{R})^{C}$. By taking a sub-collection of $\vec{S}_{l,\mathrm{tang}}$ and
abusing the notation, we may say that for every
$\vec{S}_{l}\in\vec{S}_{l,\mathrm{tang}}$ the collection
$\mathcal{S}_{l-1}[\vec{S}_{l}]$ has the uniform parameters $r_{l-1}$,
$D_{l-1}$ and $A_{l-1}$.

We define a family of multigrains by

(9.14)
$\vec{\mathcal{S}}_{l-1}:=\big{\\{}\vec{S}_{l-1}:=(\vec{S}_{l},(S,B_{r_{l-1}})):(S,B_{r_{l-1}})\in\mathcal{S}_{l-1}[\vec{S}_{l}]\big{\\}}$

and the function $g_{\vec{S}_{l-1}}:=(g_{\vec{S}_{l}})_{(S,B_{r_{l-1}})}$. It
is elementary to see that Property II follows from (9.11) and Property III
follows from (9.12). Also, by using Hölder’s inequality (see pages 266–267 of
the paper of [HR19]), Property I follows from (9.11). We leave out the
details. It remains to show Property IV. Since our outputs at the $(n+1-l)$th
step satisfy Property IV, it suffices to prove for the case that
$l^{\prime}=l-1$. By (9.13) and Property III, it suffices to prove that

(9.15)
$\|g_{\vec{S}_{l}}|_{\uparrow^{l}(\uparrow\widetilde{\mathbb{W}})}\|_{L^{2}}^{2}\lesssim\|g_{\vec{S}_{l}}|_{(\uparrow\uparrow_{l-1}\widetilde{\mathbb{W}})^{*}}\|_{L^{2}}^{2}+\mathrm{RapDec}(R)\|g\|_{L^{2}}^{2},$

where the notation $\uparrow\uparrow_{l}\\!\\!\widetilde{\mathbb{W}}$ was
introduced in (9.6) and $\mathbb{W}^{\ast}$ was defined in (7.6). If we can
show
$\uparrow^{l}\\!\\!(\uparrow\\!\\!\widetilde{\mathbb{W}})\subset\uparrow\uparrow_{l-1}\\!\\!\widetilde{\mathbb{W}}$,
then the estimate above follows from Lemma 4.2 and Lemma 7.7. In fact, on page
20 of [HZ20], it is proved that
$\uparrow^{l}\\!\\!(\uparrow\\!\\!\widetilde{\mathbb{W}})\subset\uparrow^{l-1}\widetilde{\mathbb{W}}$.
By the definition of $\uparrow\uparrow_{l-1}\\!\\!\widetilde{\mathbb{W}}$, we
also know that
$\uparrow^{l-1}\widetilde{\mathbb{W}}\subset\uparrow\uparrow_{l-1}\\!\\!\widetilde{\mathbb{W}}$,
hence,
$\uparrow^{l}\\!\\!(\uparrow\\!\\!\widetilde{\mathbb{W}})\subset\uparrow\uparrow_{l-1}\\!\\!\widetilde{\mathbb{W}}$.
This gives Property IV and finishes the proof.

###  9.3. A proof of Theorem 3.4

Let us prove the broad norm estimate (9.1). We first state the vanishing
property of the broad norm.

######  Lemma 9.1.

Let $1<r\leq R$, and let $1\leq m<k\leq n$, and let ${Z}$ be an
$m$-dimensional transverse complete intersection. Suppose that $g$ is
concentrated on wave packets from $\mathbb{T}_{{Z}}[B(\widetilde{{\bf
x}}_{0},r)]$. Then for every ball $B(\widetilde{{\bf
x}}_{0},r)\subset[-3C_{n}\lambda,3C_{n}\lambda]^{n-1}\times[R/C_{n},C_{n}\lambda]$,
it holds that

(9.16) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B(\widetilde{{\bf
x}}_{0},r))}=\rm{RapDec}(r)\|g\|_{2}.$

The proof is straightforward and we leave out the details here. The interested
reader should consult the proof of the analogous result in Page 339 of
[GHI19].

As a consequence of [alg 2] and Lemma 9.1, we will obtain the following
multiscale grains decomposition, which is the counterpart of that in Section
4.1 of [HZ20].

Input The algorithm takes as its input:

  * •

A ball $B({\bf
x}_{0},R)\subset[-3C_{n}\lambda,3C_{n}\lambda]^{n-1}\times[R/C_{n},C_{n}\lambda]$.

  * •

An admissible large integer $A\in\mathbb{N}$.

  * •

A function $g\in L^{1}$ satisfying the non-degenerate hypothesis (9.2).

Output The algorithm produces

  * •

$\mathcal{O}$ a finite collection of open subsets of $\mathbb{R}^{n}$ of
diameter at most $R^{\epsilon_{\circ}}$

  * •

A dimension $m$ with $k\leq m\leq n$ and an integer parameter $1\leq
A_{m-1}\leq A$

  * •

Scales $\vec{r}_{m}=(r_{n},\dots,r_{m})$ satisfying
$R=r_{n}>r_{n-1}>\dots>r_{m}$

  * •

Large non-admissible parameters $\vec{D}_{m-1}=(D_{n},\dots,D_{m-1})$.

  * •

For $m\leq l\leq n$ a family $\vec{\mathcal{S}}_{m}$ of level $n-l$
multigrains. Each $\vec{S}_{l}\in\vec{\mathcal{S}}_{l}$ has multiscale
$\vec{r}_{l}=(r_{n},\cdots,r_{l})$ and complexity $O_{\epsilon}(1)$. The
families have a nested structure in the sense that for each $m\leq l\leq n$
and each $\vec{S}_{l}\in\vec{\mathcal{S}}_{l}$, there exists some
$\vec{S}_{l+1}\in\vec{\mathcal{S}}_{l+1}$ such that
$\vec{S}_{l}\preceq\vec{S}_{l+1}$.

  * •

For $m\leq l\leq n$ an assignment of a function $g_{\vec{S}_{l}}$ to each
$\vec{S}_{l}\in\vec{\mathcal{S}}_{l}$. Each $g_{\vec{S}_{l}}$ is tangent to
$(S_{l},B_{r_{l}})$, the final component of $\vec{S}_{l}$. Moreover, $S_{l}$
is of dimension $l$.

All these outputs will be chosen so that the following properties hold true.

##### Property I

The inequality holds true

(9.17) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{R})}\lesssim
M(\vec{r}_{m},\vec{D}_{m})R^{O(\epsilon_{\circ})}\|g\|_{L^{2}(B^{n-1})}^{1-\beta_{m}}\Big{(}\sum_{O\in\mathcal{O}}\|H^{\lambda}g_{O}\|_{\mathrm{BL}_{k,A_{m}}^{p_{m}}({O})}^{p_{m}}\Big{)}^{\frac{\beta_{m}}{p_{m}}},$

where

$M(\vec{r}_{m},\vec{D}_{m}):=\Big{(}\prod_{i=m}^{n}D_{i}\Big{)}^{(n-m)\delta}\Big{(}\prod_{i=m}^{n}r_{i}^{\frac{1}{2}(\beta_{i+1}-\beta_{i})}D_{i}^{\frac{1}{2}(\beta_{i+1}-\beta_{m})}\Big{)}.$

##### Property II

(9.18)
$\sum_{O\in\mathcal{O}}\|g_{O}\|_{2}^{2}\lesssim\Big{(}\prod_{i=m-1}^{n}D_{i}^{1+\delta}\Big{)}R^{O(\epsilon_{\circ})}\|g\|_{L^{2}(B^{n-1})}^{2}.$

##### Property III

For $m\leq l\leq n$

(9.19) $\max_{O\in\mathcal{O}}\|g_{O}\|_{2}^{2}\lesssim
r_{l}^{-\frac{n-l}{2}}\Big{(}\prod_{i=m-1}^{l-1}r_{i}^{-1/2}D_{i}^{-i+\delta}\Big{)}R^{O(\epsilon_{\circ})}\max_{\vec{S}_{l}\in\vec{\mathcal{S}}_{l}}\|g_{\vec{S}_{l}}\|_{2}^{2}.$

##### Property IV

For $m\leq l\leq n-1$

(9.20) $\|g_{\vec{S}_{l}}\|_{L^{2}(B^{n-1})}^{2}\lesssim
r_{l}^{\frac{n-l}{2}}\Big{(}\prod_{i=l}^{n-1}r_{i}^{-1/2}D_{i}^{\delta}\Big{)}R^{O(\epsilon_{\circ})}\|g_{\vec{S}_{l}}^{\\#}\|_{2}^{2},$

where

(9.21) $g_{\vec{S}_{l}}^{\\#}:=g|_{\mathbb{T}[\vec{S}_{l}]}.$

Here, $\mathbb{T}[\vec{S}_{l}]$ is defined in Definition 7.4.

Let us explain how we obtain the multiscale grains decomposition. We first
note that [alg 2] terminates at $(n+1-m)$th step with $m\geq k$. Otherwise,
[alg 2] does not terminate at $(n+1-k)$th step, and as an application of Lemma
9.1, we obtain that
$\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{R})}=\mathrm{RapDec}(R)\|g\|_{2}$.
However, since we are assuming that $g$ satisfies the non-degenerate
hypothesis (9.2), this does not take place.

By the stopping condition of [alg 2], we know that [alg 1] terminates due to
[tiny]. Let us denote by $\mathcal{O}$ a final collection of cells and define
$A_{m-1}$ and $D_{m-1}$ as in pages 267–268 of [HR19]. Then it is
straightforward to see that Property I, II and III follow from those of [alg
2]. Let us explain how Property IV can be deduced from that of [alg 2]. Let us
fix a $n-l$ level multigrain $\vec{S}_{l}$. Since $\vec{S}_{l}$ has a nested
structure, we can take $n-i$ level multigrains $\vec{S}_{i}$ such that

(9.22) $\vec{S}_{l}\preceq\vec{S}_{l+1}\preceq\cdots\preceq\vec{S}_{n}.$

For $l\leq i\leq n$, if $(S_{i},B({\bf x}_{n-i},r_{i}))$ denotes the
$(n-i+1)$th component of $\vec{S}_{l}$, then let
$\mathbb{T}_{\mathrm{tang}}[S_{i}]$ denote the set of all wave packets of
scale $r_{i}$ tangent to $S_{i}$ in $B({\bf x}_{n-i},r_{i})$. We construct
sets $\mathbb{W}_{i}\subset\mathbb{T}_{\mathrm{tang}}[S_{i}]$ for $l\leq i\leq
n$ as follows; We first set

(9.23) $\mathbb{W}_{l}:=\mathbb{T}_{\mathrm{tang}}[S_{l}],$

and define recursively

(9.24)
$\mathbb{W}_{i+1}:=\mathbb{T}_{\mathrm{tang}}[S_{l}]\cap(\uparrow\uparrow_{i}\\!\\!\mathbb{W}_{i})^{*}.$

By Property IV of [alg 2], we know that

(9.25)
$\|{g}_{\vec{S}_{i}}|_{\mathbb{W}_{i}}\|_{L^{2}(B^{n-1})}^{2}\lesssim\big{(}\frac{r_{i+1}}{r_{i}}\big{)}^{-\frac{n-i}{2}}D_{i}^{\delta}R^{O(\epsilon_{\circ})}\|g_{\vec{S}_{i+1}}|_{(\uparrow\uparrow_{i}\mathbb{W}_{i})^{*}}\|_{2}^{2}+\mathrm{RapDec}(R)\|g\|_{L^{2}}^{2}$

for $l\leq i\leq n$. Recall that $g_{\vec{S}_{i+1}}$ is concentrated on wave
packets belonging to $\mathbb{T}_{\mathrm{tang}}[S_{i+1}]$, and thus, we know
that

(9.26)
$g_{\vec{S}_{i+1}}=g_{\vec{S}_{i+1}}|_{\mathbb{T}_{\mathrm{tang}[S_{i+1}]}}+\mathrm{RapDec}(R)\|g_{\vec{S}_{i+1}}\|_{2}.$

By (9.24), (9.25), (9.26), Lemma 7.7, and Property III, we obtain that

(9.27)
$\|{g}_{\vec{S}_{i}}|_{\mathbb{W}_{i}}\|_{L^{2}(B^{n-1})}^{2}\lesssim\big{(}\frac{r_{i+1}}{r_{i}}\big{)}^{-\frac{n-i}{2}}D_{i}^{\delta}R^{O(\epsilon_{\circ})}\|g_{\vec{S}_{i+1}}|_{\mathbb{W}_{i+1}}\|_{2}^{2}+\mathrm{RapDec}(R)\|g\|_{L^{2}}^{2}.$

We iterate this inequality, and it suffices to set the function
$g^{\\#}_{\vec{S}_{l}}:=g|_{\mathbb{W}_{0}}$ and notice that this function
satisfies the nested tube hypothesis in Definition 7.4. We refer to pages
22-23 of [HZ20] for more details. This completes the proof of Property IV.

Let us now see how the multiscale grains decomposition can be applied to prove
Theorem 3.4. Recall that (9.1) is vacuously true unless $g$ satisfies the non-
degenerate hypothesis (9.2). Hence, we may assume that $g$ satisfies the non-
degenerate hypothesis. We now apply the above multiscale grains decomposition
and obtain

(9.28) $\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{R})}\lesssim
M(\vec{r}_{m},\vec{D}_{m})R^{O(\epsilon_{\circ})}\|g\|_{L^{2}(B^{n-1})}^{1-\beta_{m}}\Big{(}\sum_{O\in\mathcal{O}}\|H^{\lambda}g_{O}\|_{\mathrm{BL}_{k,A_{m}}^{p_{m}}({O})}^{p_{m}}\Big{)}^{\frac{\beta_{m}}{p_{m}}}.$

Since each element of $\mathcal{O}$ has a diameter at most
$R^{\epsilon_{\circ}}$, we obtain

(9.29) $\|H^{\lambda}g_{O}\|_{\mathrm{BL}_{k,A_{m}}^{p_{m}}({O})}\lesssim
R^{C\epsilon_{\circ}}\|g_{O}\|_{2}.$

By combining these two inequalities, we obtain

(9.30) $\begin{split}\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{R})}&\lesssim
R^{C\epsilon_{\circ}}M(\vec{r}_{m},\vec{D}_{m})\|g\|_{L^{2}(B^{n-1})}^{1-\beta_{m}}\Big{(}\sum_{O\in\mathcal{O}}\|g_{O}\|_{L^{2}}^{p_{m}}\Big{)}^{\frac{\beta_{m}}{p_{m}}}\\\
&\lesssim
R^{C\epsilon_{\circ}}M(\vec{r}_{m},\vec{D}_{m})\|g\|_{L^{2}(B^{n-1})}^{1-\beta_{m}}\Big{(}\underbrace{\sum_{O\in\mathcal{O}}\|g_{O}\|_{L^{2}}^{2}}_{\mathrm{Part\;I}}\Big{)}^{\frac{\beta_{m}}{p_{m}}}\big{(}\underbrace{\sup_{O\in\mathcal{O}}\|g_{O}\|^{2}_{{2}}}_{\mathrm{Part\;II}}\big{)}^{(\frac{1}{2}-\frac{1}{p_{m}}){\beta_{m}}}.\end{split}$

We apply (9.18) to Part I. Then by the definition of $\beta_{m}$, the right
hand side is bounded by

(9.31)
$\|H^{\lambda}g\|_{\mathrm{BL}_{k,A}^{p}(B_{R})}\lesssim\Big{(}\prod_{i=m-1}^{n}r_{i}^{\frac{1}{2}(\beta_{i+1}-\beta_{i})}D_{i}^{\frac{\beta_{i+1}}{2}-(\frac{1}{2}-\frac{1}{p_{n}})+C\delta}\Big{)}R^{C\epsilon_{\circ}}\|g\|_{2}^{\frac{2}{p_{n}}}\big{(}\underbrace{\sup_{O\in\mathcal{O}}\|g_{O}\|^{2}_{{2}}}_{\mathrm{Part\;II}}\big{)}^{\frac{1}{2}-\frac{1}{p_{n}}}$

where $r_{m-1}:=1$. This inequality is the counterpart of the last inequality
of Section 4.1 of [HZ20].

To deal with Part II, we need the following lemma, which is the counterpart of
Lemma 4.3 of [HZ20]. This lemma is a corollary of the nested polynomial Wolff
axioms.

######  Lemma 9.2 (cf. Lemma 4.3 of [HZ20]).

For $m\leq l\leq n$, and the functions $g^{\\#}_{\vec{S}_{l}}$ defined in
(9.21), it holds that

(9.32)
$\max_{\vec{S}_{l}\in\vec{\mathcal{{S}}}_{l}}\|g_{\vec{S}_{l}}^{\\#}\|_{L^{2}}^{2}\lesssim\Big{(}\prod_{i=l}^{n-1}r_{i}^{-1/2}\Big{)}R^{\epsilon_{\circ}}\|g\|_{L^{\infty}}^{2}.$

###### Proof.

By the $L^{2}$-orthogonality, we know that

(9.33)
$\|g_{\vec{S}_{l}}^{\\#}\|_{2}^{2}\lesssim\sum_{\theta\in\Theta[{\vec{S}_{l}}]}\sum_{v:T_{\theta,v}\in\mathbb{T}[\vec{S}_{l}]}\|g_{T_{\theta,v}}\|_{2}^{2}.$

Since $g_{T_{\theta,v}}$ is supported on $\theta$, by taking the maximum over
$\theta$, this is bounded by

(9.34) $\\#\Theta[\vec{S}_{l}]\max_{\theta\in\Theta_{R}}\Big{(}\sum_{v\in
R^{1/2}\mathbb{Z}^{n-1}}\|g_{T_{\theta,v}}\|_{L^{2}(\theta)}^{2}\Big{)}.$

By the $L^{2}$-orthogonality and replacing the $L^{2}$-norm by the
$L^{\infty}$-norm, it is further bounded by

(9.35) $\\#\Theta[\vec{S}_{l}]R^{-(n-1)/2}\|g\|_{\infty}^{2}.$

It suffices now to apply Lemma 7.5 and bound $\\#\Theta[\vec{S}_{l}]$. ∎

After applying (9.19), (9.20), and this lemma to Part II, we obtain

(9.36)
$\max_{O\in\mathcal{O}}\|g_{O}\|_{L^{2}}^{2}\lesssim_{\epsilon}\Big{(}\prod_{i=m-1}^{n-1}r_{i}^{-1/2}D_{i}^{\delta}\Big{)}\Big{(}\prod_{i=l}^{n-1}r_{i}^{-1/2}\Big{)}\Big{(}\prod_{i=m-1}^{l-1}D_{i}^{-i}\Big{)}R^{C\epsilon_{\circ}}\|g\|_{L^{\infty}}^{2}$

for every $m\leq l\leq n$. This inequality is the counterpart of the
inequality (4.2) of [HZ20]. We now combine (9.31) and (9.36) as in Section 4.3
of [HZ20] and obtain the obtain the desired estimate (9.1). Since the proof is
identical to theirs, we leave out the details.

##  10\. Appendix: a transversality lemma

The appendix is devoted to a transversality lemma . First, let us introduce
one more definition.

######  Definition 10.1.

Let $M,N$ be smooth manifolds. Assume that $f:M\to N$ and $A\subset N$ a
submanifold. Then $f$ is said to be transverse to $A$, which is denoted by
$f\pitchfork A$, if for any $x\in M$ with $f(x)=y\in A$, the tangent space
$T_{y}N$ is spanned by $T_{y}A$ and the image $Df_{x}(T_{x}M)$.

Now recall the follow version of the transversality theorem.

######  Theorem 10.2 ([GP10], Page 68).

Let $X,S,Y$ be smooth manifolds without boundary and $A\subset N$ a smooth
submanifold. Let $F:V\to C^{\infty}(M,N)$ satisfy the following condition:

  1. (1)

the evaluation map $F^{ev}:X\times S\to Y,(x,s)\to F_{s}(x)$ is $C^{\infty}$.

  2. (2)

$F^{ev}$ is transverse to A.

Then the complement of the set

(10.1) $\pitchfork(F;A):=\\{s\in S:F_{s}\pitchfork A\\}$

in $V$ has measure zero.

Let $\Phi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ be a smooth map and let
$Z\subset\mathbb{R}^{n}$ be a smooth submanifold. Fix $k$ vectors
$m_{1},\ldots,m_{k}\in\mathbb{R}^{n}$, $1\leq k\leq n$. Consider a family of
parallel affine subspaces $\\{\Pi_{c}\\}_{{c}\in\mathbb{R}^{k}}$ in
$\mathbb{R}^{n}$ formed by $(m_{1},\ldots,m_{k})$:

(10.2) $\Pi_{c}:\left\\{\begin{array}[]{c}m_{1}\cdot x-c_{1}=0,\\\ \ldots\\\
m_{k}\cdot x-c_{k}=0.\end{array}\right.$

We show that $\Phi^{-1}(\Pi_{c})$ is transvserse to $Z$ for generic $\Pi_{c}$.

######  Lemma 10.3.

The complement of the

(10.3)
${\mathcal{C}}_{\Phi}:=\\{c\in\mathbb{R}^{k}:\Phi^{-1}(\Pi_{c}){\rm{~{}is~{}transverse~{}to~{}}}Z\\}$

in $\mathbb{R}^{k}$ has measure zero.

###### Proof.

We first take $X=Z$, $S=\mathbb{R}^{k}$, $Y=\mathbb{R}^{k}$, $A=0$, and
$F^{ev}=(m_{1}\cdot\Phi(z)-v_{1},\ldots,m_{k}\cdot\Phi(z)-v_{k})$ be the
evaluation map in Theorem 10.2. Then the complement of the set

(10.4) ${\mathcal{C}}_{F}:=\\{c\in\mathbb{R}^{k}:F_{c}\pitchfork A\\}$

in $\mathbb{R}^{k}$ has measure zero. Then we take $X=\mathbb{R}^{n}$,
$S=\mathbb{R}^{k}$, $Y=\mathbb{R}^{k}$, $A=0$, and
$G^{ev}=(m_{1}\cdot\Phi(z)-v_{1},\ldots,m_{k}\cdot\Phi(z)-v_{k})$. One can
argue similarly to get that the complement of

(10.5) ${\mathcal{C}}_{G}:=\\{c\in\mathbb{R}^{k}:G_{c}\pitchfork A\\}$

in $\mathbb{R}^{k}$ has measure zero. Take
${\mathcal{C}}={\mathcal{C}}_{F}\cap{\mathcal{C}}_{G}$. We claim that
${\mathcal{C}}\subset{\mathcal{C}}_{\Phi}$, which proves the lemma.

To prove our claim above, first note that
$\Phi^{-1}(\Pi_{c})\subset\mathbb{R}^{n}$ is a smooth embedding of dimension
$n-k$ when $c\in{\mathcal{C}}$, since $G_{c}\pitchfork A$. Take any $z\in
Z\cap\Phi^{-1}(\Pi_{c})$. We need to show
$T_{z}Z+T_{z}\Phi^{-1}(\Pi_{c})=\mathbb{R}^{n}$. Notice that

  1. (1)

$G|_{Z}=F$, so $D_{z}G|_{T_{z}Z}=D_{z}F$.

  2. (2)

$D_{z}F$ is surjective since $F_{c}\pitchfork A$.

  3. (3)

$G(\Phi^{-1}(\Pi_{c}))=0$, which implies
$D_{z}G|_{T_{z}\Phi^{-1}(\Pi_{c})}=0$.

Thus, we have

  1. (1)

$D_{z}G$ is surjective on $T_{z}Z$.

  2. (2)

$\ker(D_{z}G)=T_{z}\Phi^{-1}(\Pi_{c})$, since both $\Phi^{-1}(\Pi_{c})$ and
$\ker(D_{z}G)$ have dimension $n-k$.

Hence $T_{z}Z$ and $\ker(D_{z}G)=T_{z}\Phi^{-1}(\Pi_{c})$ span the whole space
$\mathbb{R}^{n}$ as desired. ∎

## References

  * [BD15] Jean Bourgain and Ciprian Demeter.  The proof of the $l^{2}$ decoupling conjecture.  Ann. of Math. (2), 182(1):351–389, 2015.
  * [BG11] Jean Bourgain and Larry Guth.  Bounds on oscillatory integral operators based on multilinear estimates.  Geom. Funct. Anal., 21(6):1239–1295, 2011.
  * [BHS20] David Beltran, Jonathan Hickman, and Christopher D. Sogge.  Variable coefficient Wolff-type inequalities and sharp local smoothing estimates for wave equations on manifolds.  Anal. PDE, 13(2):403–433, 2020.
  * [Bou91a] J. Bourgain.  Besicovitch type maximal operators and applications to Fourier analysis.  Geom. Funct. Anal., 1(2):147–187, 1991.
  * [Bou91b] J. Bourgain.  $L^{p}$-estimates for oscillatory integrals in several variables.  Geom. Funct. Anal., 1(4):321–374, 1991.
  * [Car92] Anthony Carbery.  Restriction implies Bochner-Riesz for paraboloids.  Math. Proc. Cambridge Philos. Soc., 111(3):525–529, 1992.
  * [Chr88] Michael Christ.  Weak type $(1,1)$ bounds for rough operators.  Ann. of Math. (2), 128(1):19–42, 1988.
  * [CS72] Lennart Carleson and Per Sjölin.  Oscillatory integrals and a multiplier problem for the disc.  Studia Math., 44:287–299. (errata insert), 1972.
  * [Fef70] Charles Fefferman.  Inequalities for strongly singular convolution operators.  Acta Math., 124:9–36, 1970.
  * [Fef73] Charles Fefferman.  A note on spherical summation multipliers.  Israel J. Math., 15:44–52, 1973.
  * [GHI19] Larry Guth, Jonathan Hickman, and Marina Iliopoulou.  Sharp estimates for oscillatory integral operators via polynomial partitioning.  Acta Math., 223(2):251–376, 2019.
  * [GP10] Victor Guillemin and Alan Pollack.  Differential topology.  AMS Chelsea Publishing, Providence, RI, 2010.  Reprint of the 1974 original.
  * [Gut16] Larry Guth.  A restriction estimate using polynomial partitioning.  J. Amer. Math. Soc., 29(2):371–413, 2016.
  * [Gut18] Larry Guth.  Restriction estimates using polynomial partitioning ii.  Acta Math., 221(1):81–142, 09 2018.
  * [H7̈3] Lars Hörmander.  Oscillatory integrals and multipliers on $FL^{p}$.  Ark. Mat., 11:1–11, 1973.
  * [HR19] Jonathan Hickman and Keith M. Rogers.  Improved fourier restriction estimates in higher dimensions.  Camb. J. Math., 7(3):219–282, 2019.
  * [HRZ19] Jonathan Hickman, Keith Rogers, and Ruixiang Zhang.  Improved bounds for the kakeya maximal conjecture in higher dimensions.  arXiv:1908.05589, 2019.
  * [HZ20] Jonathan Hickman and Joshua Zahl.  A note on fourier restriction and nested polynomial wolff axioms.  arXiv:2010.02251, 2020.
  * [KR18] Nets Hawk Katz and Keith M. Rogers.  On the polynomial Wolff axioms.  Geom. Funct. Anal., 28(6):1706–1716, 2018.
  * [Lee04] Sanghyuk Lee.  Improved bounds for Bochner-Riesz and maximal Bochner-Riesz operators.  Duke Math. J., 122(1):205–232, 2004.
  * [Lee06] Sanghyuk Lee.  Linear and bilinear estimates for oscillatory integral operators related to restriction to hypersurfaces.  J. Funct. Anal., 241(1):56–98, 2006.
  * [Lee18] Sanghyuk Lee.  Square function estimates for the Bochner-Riesz means.  Anal. PDE, 11(6):1535–1586, 2018.
  * [Rog08] Keith M. Rogers.  A local smoothing estimate for the Schrödinger equation.  Adv. Math., 219(6):2105–2122, 2008.
  * [See96] Andreas Seeger.  Endpoint inequalities for Bochner-Riesz multipliers in the plane.  Pacific J. Math., 174(2):543–553, 1996.
  * [SS11] Elias M. Stein and Rami Shakarchi.  Functional analysis, volume 4 of Princeton Lectures in Analysis.  Princeton University Press, Princeton, NJ, 2011.  Introduction to further topics in analysis.
  * [Ste93] Elias M. Stein.  Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals, volume 43 of Princeton Mathematical Series.  Princeton University Press, Princeton, NJ, 1993.  With the assistance of Timothy S. Murphy, Monographs in Harmonic Analysis, III.
  * [Tao98] Terence Tao.  The weak-type endpoint Bochner-Riesz conjecture and related topics.  Indiana Univ. Math. J., 47(3):1097–1124, 1998.
  * [Tao99] Terence Tao.  The Bochner-Riesz conjecture implies the restriction conjecture.  Duke Math. J., 96(2):363–375, 1999.
  * [Tao03] Terence Tao.  A sharp bilinear restrictions estimate for paraboloids.  Geom. Funct. Anal., 13(6):1359–1384, 2003.
  * [Tao06] Terence Tao.  Nonlinear dispersive equations, volume 106 of CBMS Regional Conference Series in Mathematics.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2006.  Local and global analysis.
  * [Wan18] Hong Wang.  A restriction estimate in $\mathbb{R}^{3}$ using brooms.  arXiv:1802.04312, 2018.
  * [Won93] Richard Wongkew.  Volumes of tubular neighbourhoods of real algebraic varieties.  Pacific J. Math., 159(1):177–184, 1993.
  * [Wu20] Shukun Wu.  On the bochner-riesz operator in $\mathbb{R}^{3}$.  arXiv:2008.13043, 2020.
  * [Zah18] Joshua Zahl.  A discretized Severi-type theorem with applications to harmonic analysis.  Geom. Funct. Anal., 28(4):1131–1181, 2018.
  * [Zah21] Joshua Zahl.  New Kakeya estimates using Gromov’s algebraic lemma.  Adv. Math., 380:107596, 2021.


#  Computability-logic web: an alternative to deep learning

Keehang Kwon

Department of Computing Sciences, DongA University, Korea.
Email<EMAIL_ADDRESS>
###### Abstract

Computability logic (CoL) is a powerful, mathematically rigorous computational
model. In this paper, we show that CoL-web, a web extension to CoL, naturally
supports web programming where database updates are involved. To be specific,
we discuss an implementation of the AI ATM based on CoL (CL9 to be exact).

More importantly, we argue that CoL-web supports a general AI and, therefore,
is a good alternative to neural nets and deep learning. We also discuss how to
integrate neural nets into CoL-web.

Keywords: Computability logic; Web programming; Game semantics; AI;

##  1 Introduction

It is not dfficult to point out the weaknesses of neural nets and deep
learning. Simply put, neural nets are too weak to support general AI. They
receive inputs (numbers), perform simple arithmetic operations and produce
outputs (numbers). Consequently, they provide only primitive services such as
object classifications. Although object classification has some interesting
applications, the power of classification is in fact not much compared to all
the complex services a human can provide. Complex services – making a coffee,
withdrawing money from ATM, etc – are not well supported by neural nets. In
addition, their classification services are not perfect, as they are only
approximate.

A human can provide complex services to others. The notion of services and how
to complete them thus play a key role for an AI to imitate a human. In other
words, the right move towards general AI would be to find (a) a mathematical
notion for services, and (b) how an AI automatically generates a strategy for
completing the service calls.

Fortunately, Japaridze developed a theory for services/games involving complex
ones. Computability logic (CoL) [1]-[4], is an elegant theory of (multi-)agent
services. In CoL, services are seen as games between a machine and its
environment and logical operators stand for operations on games. It
understands interaction among agents in its most general — game-based — sense.

In this paper, we discuss a web programming model based on CoL and implement
an AI ATM. An AI ATM is different from a regular ATM in that the former
automatically generates a strategy for a service call, while the latter does
not.

We assume the following in our model:

  * •

Each agent corresponds to a web site with a URL. An agent’s knowledgebase(KB)
is described in its homepage.

  * •

Agents are initially inactive. An inactive agent becomes activated when
another agent invokes a query for the former.

  * •

Our model supports the query/knowledge duality, also known as querying
knowledge. That is, knowledge of an agent can be obtained from another agent
by invoking queries to the latter.

To make things simple, we choose CL9– a fragment of CoL – as our target
language. CL9 includes sequential operators: sequential disjunction
($\bigtriangledown$) and sequential conjunction ($\bigtriangleup$) operators.
These operators model knowledgebase updates. Imagine an ATM that maintains
balances on Kim. Balances change over time. Whenever Kim presses the deposit
button for $1, the machine must be able to update the balance of the person.
This can be represented by

$balance(\$0)\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}blance(\$1)\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}.$

In this paper, we present $\mbox{\bf CL9}^{\Phi}$ which is a web-based
implementation of CL9. This implementation is straightfoward and its
correctness is rather obvious. What is interesting is that CL9 is a novel web
programming model with possible database updates. It would provide a good
starting point for future high-level web programming.

##  2 Preliminaries

In this section a brief overview of CL9 is given.

There are two players: the machine $\top$ and the environment $\bot$.

There are two sorts of atoms: elementary atoms $p$, $q$, …to represent
elementary games, and general atoms $P$, $Q$, …to represent any, not-
necessarily-elementary, games.

Constant elementary games

$\top$ is always a true proposition, and $\bot$ is always a false proposition.

Negation

$\neg$ is a role-switch operation: For example, $\neg(0=1)$ is true, while
$(0=1)$ is false.

Choice operations

The choice operations model decision steps in the course of interaction, with
disjunction $\sqcup$ meaning the machine’s choice, and conjunction $\sqcap$
meaning choice by the environment.

Parallel operations

$A\wedge B$ means the parallel-and, while $A\vee B$ means the paralle-or. In
$A\wedge B$, $\top$ is considered the winner if it wins in both $A$ and $B$,
while in $A\vee B$ it is sufficient to win in one of $A$ and $B$.

Reduction

$\rightarrow$ is defined by $\neg A\vee B$.

Sequential operations

$A\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}B$ (resp.
$A\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}B$) is a game that starts and
proceeds as a play of $A$; it will also end as an ordinary play of $A$ unless,
at some point, $\top$ (resp. $\bot$) decides — by making a special switch move
— to abandon $A$ and switch to $B$.
$A\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}B$ is quite similar to
the $if$-$then$-$else$ in imperative languages.

We reserve $\S$ as a special symbol for switch moves. Thus, whenever $\bot$
wants to switch from a given component $A_{i}$ to $A_{i+1}$ in
$A_{0}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}A_{n}$,
it makes the move $\S$. Note that $\top$, too, needs to make switch moves in a
$\bigtriangleup$-game to “catch up” with $\bot$. The switches made by $\bot$
in a $\bigtriangleup$-game we call leading switches, and the switches made by
$\top$ in a $\bigtriangleup$-game we call catch-up switches.

##  3 Logic $\mbox{\bf CL9}^{\Phi}$

In this section we review the propositional system CL9 [5] and slightly extend
it. Our presentation closely follows the one in [5]. We assume that there are
infinitely many nonlogical elementary atoms, denoted by $p,q,r,s$ and
infinitely many nonlogical general atoms, denoted by $P,Q,R,S$.

Formulas, to which we refer as CL9-formulas, are built from atoms and
operators in the standard way.

###### Definition 3.1

The class of CL9-formulas is defined as the smallest set of expressions such
that all atoms are in it and, if $F$ and $G$ are in it, then so are $\neg F$,
$F\wedge G$, $F\vee G$, $F\rightarrow G$, $F\sqcap G$, $F\sqcup G$,
$F\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G$,
$F\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}G$.

Now we define $\mbox{\bf CL9}^{\Phi}$, a slight extension to CL9 with
environment parameters. Let $F$ be a CL9-formula. We introduce a new env-
annotated formula $F^{\omega}$ which reads as ‘play $F$ against an agent
$\omega$. For an $\sqcap$-occurrence or an $\bigtriangleup$-occurrence $O$ in
$F^{\omega}$, we say $\omega$ is the matching environment of $O$. For example,
$(p\sqcap(q\sqcap r))^{w}$ is an agent-annotated formula and $w$ is the
matching environment of both occurrences of $\sqcap$. Similarly for
$(p\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}(q\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}r))^{w}$.
We extend this definition to subformulas and formulas. For a subformula
$F^{\prime}$ of the above $F^{\omega}$, we say that $\omega$ is the matching
environment of both $F^{\prime}$ and $F$.

In introducing environments to a formula $F$, one issue is whether we allow
‘env-switching’ formulas of the form $(F[R^{u}])^{w}$. Here $F[R]$ represents
a formula with some occurrence of a subformula $R$. That is, the machine
initially plays $F$ against agent $w$ and then switches to play against
another agent $u$ in the course of playing $F$. For technical reasons, we
focus on non ‘env-switching’ formulas. This leads to the following definition:

###### Definition 3.2

The class of $\mbox{\bf CL9}^{\Phi}$-formulas is defined as the smallest set
of expressions such that (a) For any CL9-formula $F$ and any agent $\omega$,
$F^{\omega}$ are in it and, (b) if $H$ and $J$ are in it, then so are $\neg
H$, $H\wedge J$, $H\vee J$, $H\rightarrow J$.

###### Definition 3.3

Given a $\mbox{\bf CL9}^{\Phi}$-formula $J$, the skeleton of $J$ – denoted by
$skeleton(J)$ – is obtained by replacing every occurrence $F^{\omega}$ by $F$.

For example, $skeleton((p\sqcap(q\sqcap r))^{w})=p\sqcap(q\sqcap r)$.

We borrow the following definitions from [5]. They apply both to CL9 and
$\mbox{\bf CL9}^{\Phi}$.

An interpretation for CL9 is a function that sends each nonlogical elementary
atom to an elementary game, and sends each general atom to any, not-
necessarily-elementary, static game. This mapping extends to all formulas by
letting it respect all logical operators as the corresponding game operations.
That is, $\top^{*}=\top$,
$(E\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}F)^{*}=E^{*}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}F^{*}$,
etc. When $F^{*}=A$, we say that ∗ interprets $F$ as $A$.

A formula $F$ is said to be valid iff, for every interpretation ∗, the game
$F^{*}$ is computable. And $F$ is uniformly valid iff there is an HPM $\cal
H$, called a uniform solution for $F$, such that $\cal H$ wins $F^{*}$ for
every interpretation ∗.

A sequential (sub)formula is one of the form
$F_{0}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}F_{n}$
or
$F_{0}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\ldots\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}F_{n}$.
We say that $F_{0}$ is the head of such a (sub)formula, and
$F_{1},\ldots,F_{n}$ form its tail.

The capitalization of a formula is the result of replacing in it every
sequential subformula by its head.

A formula is said to be elementary iff it is a formula of classical
propositional logic.

An occurrence of a subformula in a formula is positive iff it is not in the
scope of $\neg$. Otherwise it is negative.

A surface occurrence is an occurrence that is not in the scope of a choice
connective and not in the tail of any sequential subformula.

The elementarization of a CL9-formula $F$ means the result of replacing in the
capitalization of $F$ every surface occurrence of the form
$G_{1}\sqcap\ldots\sqcap G_{n}$ by $\top$, every surface occurrence of the
form $G_{1}\sqcup\ldots\sqcup G_{n}$ by $\bot$, and every positive surface
occurrence of each general literal by $\bot$.

Finally, a formula is said to be stable iff its elementarization is a
classical tautology; otherwise it is instable.

The proof system of $\mbox{\bf CL9}^{\Phi}$ is identical to that CL9 in that
agent parameters play no roles. $\mbox{\bf CL9}^{\Phi}$ consists of the
following four rules of inference.

###### Definition 3.4

Wait:

$\vec{H}\mapsto F$, where $F$ is stable and $\vec{H}$ is the smallest set of
formulas satisfying the following two conditions:

  1. 1.

whenever $F$ has a surface occurrence of a subformula $G_{1}\sqcap\ldots\sqcap
G_{n}$ whose matching environment is $\omega$, for each
$i\in\\{1,\ldots,n\\}$, $\vec{H}$ contains the result of replacing that
occurrence in $F$ by $G_{i}^{\omega}$;

  2. 2.

whenever $F$ has a surface occurrence of a subformula
$G_{0}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{1}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{n}$
whose matching environment is $\omega$, $\vec{H}$ contains the result of
replacing that occurrence in $F$ by
$(G_{1}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{n})^{\omega}$.

Choose:

$H\mapsto F$, where $H$ is the result of replacing in $F$ a surface occurrence
of a subformula $G_{1}\sqcup\ldots\sqcup G_{n}$ whose matching environment is
$\omega$ by $G_{i}^{\omega}$ for some $i\in\\{1,\ldots,n\\}$.

Switch:

$H\mapsto F$, where $H$ is the result of replacing in $F$ a surface occurrence
of a subformula
$G_{0}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}G_{1}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\ldots\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}G_{n}$
whose matching environment is $\omega$ by
$(G_{1}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\ldots\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}G_{n})^{\omega}$.

Match:

$H\mapsto F$, where $H$ is the result of replacing in $F$ two — one positive
and one negative — surface occurrences of some general atom by a nonlogical
elementary atom that does not occur in $F$.

###### Example 3.5

The following is a CL9-proof of
$(b0\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{u}\rightarrow(b0\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{w}$:

$\begin{array}[]{ll}1.\ b2^{u}\rightarrow b2^{w}&\mbox{(from $\\{\\}$ by
Wait)};\\\ 2.\
b2^{u}\rightarrow(b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{w}&\mbox{(from
1 by Switch)};\\\ 3.\
(b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{u}\rightarrow(b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{w}&\mbox{(from
2 by Wait)};\\\ 4.\
(b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{u}\rightarrow(b0\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{w}&\mbox{(from
3 by Switch)};\\\ 5.\
(b0\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{u}\rightarrow(b0\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{w}&\mbox{(from
4 by Wait)};\\\ \end{array}$

##  4 Logic $\mbox{\bf CL9}^{\circ,\Phi}$

To facilitate the execution procedure, following [5], we modify $\mbox{\bf
CL9}^{\Phi}$ to obtain $\mbox{\bf CL9}^{\circ,\Phi}$. Unlike $\mbox{\bf
CL9}^{\Phi}$, this new language allows hyperformulas which contain the
following.

  * •

Hybrid atom: each hybrid atom is a pair consisting of a general atom $P$,
called its general component, and a nonlogical elementary atom $q$, called its
elementary component. We denote such a pair by $P_{q}$. It keeps track of the
exact origin of each such elementary atom $q$.

  * •

Underlined sequential formula: It is introduced for us not to forget the
earlier components of sequential subformulas when Switch or Wait are applied.
We now require that, in every sequential (sub)formula, one of the components
be underlined.

The formulas of this modified language we call hyperformulas. We borrow the
following definitions from [5].

By the general dehybridization of a hyperformula $F$ we mean the CL9-formula
that results from $F$ by replacing in the latter every hybrid atom by its
general component, and removing all underlines in sequential subformulas.

A surface occurrence of a subexpression in a given hyperformula $F$ means an
occurrence that is not in the scope of a choice operator, such that, if the
subexpression occurs within a component of a sequential subformula, that
component is underlined or occurs earlier than the underlined component.

An active occurrence is an occurrence such that, whenever it happens to be
within a component of a sequential subformula, that component is underlined.

An abandoned occurrence is an occurrence such that, whenever it happens to be
within a component of a sequential subformula, that component is to the left
of the underlined component of the same subformula.

An elementary hyperformula is one not containing choice and sequential
operators, underlines, and general and hybrid atoms.

The capitalization of a hyperformula $F$ is defined as the result of replacing
in it every sequential subformula by its underlined component, after which all
underlines are removed.

The elementarization

$\parallel F\parallel$

of a hyperformula $F$ is the result of replacing, in the capitalization of
$F$, every surface occurrence of the form $G_{1}\sqcap\ldots\sqcap G_{n}$ by
$\top$, every surface occurrence of the form $G_{1}\sqcup\ldots\sqcup G_{n}$
by $\bot$, every positive surface occurrence of each general literal by
$\bot$, and every surface occurrence of each hybrid atom by the elementary
component of that atom.

A hyperformula $F$ is stable iff its elementarization $\parallel F\parallel$
is a classical tautology; otherwise it is instable.

A hyperformula $F$ is said to be balanced iff, for every hybrid atom $P_{q}$
occurring in $F$, the following two conditions are satisfied:

  1. 1.

$F$ has exactly two occurrences of $P_{q}$, one positive and the other
negative, and both occurrences are surface occurrences;

  2. 2.

the elementary atom $q$ does not occur in $F$, nor is it the elementary
component of any hybrid atom occurring in $F$ other than $P_{q}$.

An active occurrence of a hybrid atom (or the corresponding literal) in a
balanced hyperformula is widowed iff the other occurrence of the same hybrid
atom is abandoned.

We extend $\mbox{\bf CL9}^{\Phi}$ to $\mbox{\bf CL9}^{\circ,\Phi}$. The
language of $\mbox{\bf CL9}^{\circ}$ allows any balanced hyperformulas, which
we also refer to as $\mbox{\bf CL9}^{\circ,\Phi}$-formulas.

###### Definition 4.1

Logic $\mbox{\bf CL9}^{\circ,\Phi}$ is given by the following rules for
balanced hyperformulas (below simply referred to as “(sub)formulas”):

Wait∘:

$\vec{H}\mapsto F$, where $F$ is stable and $\vec{H}$ is the smallest set of
formulas satisfying the following two conditions:

  1. 1.

whenever $F$ has an active surface occurrence of a subformula
$G_{1}\sqcap\ldots\sqcap G_{n}$ whose matching environment is $\omega$ , for
each $i\in\\{1,\ldots,n\\}$, $\vec{H}$ contains the result of replacing that
occurrence in $F$ by $G_{i}^{\omega}$;

  2. 2.

whenever $F$ has an active surface occurrence of a subformula
$G_{0}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\underline{G_{m}}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{m+1}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{n}$
whose matching environment is $\omega$, $\vec{H}$ contains the result of
replacing that occurrence in $F$ by
$(G_{0}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{m}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\underline{G_{m+1}}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{n})^{\omega}$.

Choose∘:

$H\mapsto F$, where $H$ is the result of replacing in $F$ an active surface
occurrence of a subformula $G_{1}\sqcup\ldots\sqcup G_{n}$ whose matching
environment is $\omega$ by $G_{i}^{\omega}$ for some $i\in\\{1,\ldots,n\\}$.

Switch∘:

$H\mapsto F$, where $H$ is the result of replacing in $F$ an active surface
occurrence of a subformula
$G_{0}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\ldots\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\underline{G_{m}}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}G_{m+1}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\ldots\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}G_{n}$
whose matching environment is $\omega$ by
$(G_{0}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\ldots\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}{G_{m}}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\underline{G_{m+1}}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\ldots\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}G_{n})^{\omega}.$

Match∘:

$H\mapsto F$, where $H$ has two — a positive and a negative — active surface
occurrences of some hybrid atom $P_{q}$, and $F$ is the result of replacing in
$H$ both occurrences by $P$.

An effective procedure that converts any $\mbox{\bf CL9}^{\Phi}$-proof of any
formula $G$ into a $\mbox{\bf CL9}^{\circ,\Phi}$-proof of $G$ is given in [5].

##  5 Execution Phase

The machine model of $\mbox{\bf CL9}^{\circ,\Phi}$ is designed to process only
one query/formula at one time. In distributed systems, however, it is natural
for an agent to receive/process multiple queries from different users. For
this reason, we introduce multiple queries to our machine. To do this, we
assume that an agent maintains two queues: the income queue $QI$ for storing a
sequence of new incoming queries of the form $(Q_{1},\ldots,Q_{n})$ and the
temporarily solved queue $QS$ for storing a sequence of temporarily solved
queries of the form $(KB_{1}\rightarrow Q_{1},\ldots,KB_{n}\rightarrow
Q_{n})$. Here each $Q_{i}$ is a query and each $KB_{i}$ is a knowledgebase. A
query $Q$ with respect to some knowledgebase is temporarily solved if $Q$ is
solved but $\top$ has a remaining switch move in $Q$. Otherwise $Q$ is said to
be completely solved.

As expected, processing real-time multiple queries causes some complications.
To be specific, we process $QI$ of the form $(Q_{1},\ldots,Q_{m})$ and $QS$ of
the form $(KB_{1}\rightarrow Q^{\prime}_{1},\ldots,KB_{n}\rightarrow
Q^{\prime}_{n})$ in the following way:

  1. 1.

First stage is to initialize a temporary variable $NewKB$ to $KB$,

  2. 2.

The second stage is to follow the $loop$ procedure:

procedure $loop$:

  * •

Case 1: $QI$ is not empty:

The machine tries to solve $Q_{1}$ by calling $Exec(NewKB\rightarrow Q_{1})$.

    * –

If it fails, then report a failure, remove $Q_{1}$ from $QI$ and repeat
$loop$.

    * –

Suppose it is a success and $NewKB$ and $Q_{1}$ evolve to $NewKB^{\prime}$ and
$Q^{\prime}_{1}$ after solving this query. We consider two cases.
(a) If it is completely solved, then report a success, remove $Q_{1}$ from
$QI$, update $NewKB$ to $NewKB^{\prime}$ and repeat $loop$. (b) If it is
temporarily solved, then report a success, remove $Q_{1}$ from $QI$, insert
$NewKB^{\prime}\rightarrow Q^{\prime}_{1}$ to $QS$, update $NewKB$ to
$NewKB^{\prime}$ and repeat $loop$.

  * •

Case 2. $QI$ is empty and $QS$ nonempty: The machine tries to solve the first
query $KB_{1}\rightarrow Q^{\prime}_{1}$ in $QS$.

    * –

If $KB=NewKB$, it means nothing has changed since the last check. Hence the
machine waits for any change such as the environment’s new move.

    * –

Otherwise, the machine tries to solve $Q^{\prime}_{1}$ with respect to
$NewKB$. It thus removes the above query from $QS$, adds $Q^{\prime}_{1}$ to
$QI$, and repeat $loop$.

  * •

Case 3. $QI$ is empty and $QS$ is empty: wait for new incoming service calls.

Below we will introduce an algorithm that executes a formula $J$. The
algorithm is a minor variant of the one in [5] and contains two stages:

Algorithm Exec(J): % $J$ is a $\mbox{\bf CL9}^{\circ,\Phi}$-formula

  1. 1.

Fix an interpretation ∗. First stage is to initialize a temporary variable $E$
to $J$, a position variable $\Omega$ to an empty position $\langle\rangle$.
Activate all the resource agents specified in $J$ by invoking proper queries
to them. That is, for each negative occurrence of an annotated formula
$F^{\omega}$ in $J$, activate $\omega$ by querying $F^{\mu}$ to $\omega$. Here
$\mu$ is the current machine; On the other hand, we assume that all the
querying agents – which appear positively in $J$ – are already active.

  2. 2.

The second stage is to play $J$ according to the following $mainloop$
procedure (which is a minor variant of [5]):

procedure $loop(Tree)$: % $Tree$ is a proof tree of $J$

If $E$ is derived by Choose∘ from $H$, the machine makes the move $\alpha$
whose effect is choosing $G_{i}$ in the $G_{1}\sqcup\ldots\sqcup G_{n}$
subformula of $E$. So, after making move $\alpha$, the machine call $loop$ on
$\langle\Omega\rangle H^{*}$. Let $\omega$ be the matching environment. Then
inform $\omega$ of the move $\alpha$.

If $E$ is derived by Switch∘ from $H$, then the machine makes the move
$\alpha$ whose effect is making a switch in the
$G_{0}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\ldots\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\underline{G_{m}}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}G_{m+1}\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}\ldots\mbox{\small\raisebox{1.70709pt}{$\bigtriangledown$}}G_{n}$
subformula. So, after making move $\alpha$, the machine calls $loop$ on
$\langle\Omega,\top\alpha\rangle H^{*}$.

If $E$ is derived by Match∘ from $H$ through replacing the two (active
surface) occurrences of a hybrid atom $P_{q}$ in $H$ by $P$, then the machine
finds within $\Omega$ and copies, in the positive occurrence of $P_{q}$, all
of the moves made so far by the environment in the negative occurrence of
$P_{q}$, and vice versa. This series of moves brings the game down to
$\langle\Omega^{\prime}\rangle E^{*}=\langle\Omega^{\prime}\rangle H^{*}$,
where $\Omega^{\prime}$ is result of adding those moves to $\Omega$. So, now
the machine calls $loop$ on $\langle\Omega^{\prime}\rangle H^{*}$.

Finally, suppose $E$ is derived by Wait∘. Our machine keeps granting
permission (“waiting”).

Case 1. $\alpha$ is a move whose effect is moving in some abandoned subformula
or a widowed hybrid literal of $E$. In this case, the machine calls $loop$ on
$\langle\Omega,\bot\alpha\rangle E^{*}$.

Case 2. $\alpha$ is a move whose effect is moving in some active surface
occurrence of a general atom in $E$. Again, in this case, the machine calls
$loop$ on $\langle\Omega,\bot\alpha\rangle E^{*}$.

Case 3. $\alpha$ is a move whose effect is making a catch-up switch in some
active surface occurrence of a $\bigtriangledown$-subformula. The machine
calls $loop$ on $\langle\Omega,\bot\alpha\rangle E^{*}$.

Case 4. $\alpha$ is a move whose effect is making a move $\gamma$ in some
active surface occurrence of a non-widowed hybrid atom. Let $\beta$ be the
move whose effect is making the same move $\gamma$ within the other active
surface occurrence of the same hybrid atom. In this case, the machine makes
the move $\beta$ and calls $loop$ on
$\langle\Omega,\bot\alpha,\top\beta\rangle E^{*}$.

Case 5: $\alpha$ is a move whose effect is a choice of the $i$th component in
an active surface occurrence of a subformula $G_{1}\sqcap\ldots\sqcap G_{n}$.
Then the machine calls $loop$ on $\langle\Omega\rangle H^{*}$, where $H$ is
the result of replacing the above subformula by $G_{i}$ in $E$.

Case 6: $\alpha$ signifies a (leading) switch move within an active surface
occurrence of a subformula

$G_{0}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\underline{G_{m}}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{m+1}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{n}.$

Then the machine makes the same move $\alpha$ (signifying making a catch-up
switch within the same subformula), and calls $exec$ on
$\langle\Omega,\bot\alpha,\top\alpha\rangle H^{*}$, where $H$ is the result of
replacing the above subformula by

$G_{0}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{m}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\underline{G_{m+1}}\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}\ldots\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}G_{n}.$

##  6 Examples

As an example of web system, we will look at the ATM of some bank. It is
formulated with the user, an ATM, a database, and a credit company. We assume
the following:

  * •

There are two kinds of agents: super agents and regular agents. Super agents
are prefixed with $\$$. For example, $\$kim$ is a super agent. While regular
agents behave according to the $Exec$ procedure, super agents behave
unpredictably.

  * •

For simplicity, we assume the bank has only one customer named Kim. Further,
the balance is restricted to one of the three amounts: $0, $1 or $2.

  * •

The database maintains balance information on Kim.

  * •

Both the credit company and the ATM request balance checking to the database.

  * •

The ATM has a ($1) deposit button. Whenever pressed, it adds $\$1$ to the
account.

The above can be implemented as follows:

$agent\ credit$. % credit company
---
$(b0\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{db}$.
% b0 means the balance is $0, and so on.

% Here, we assume that ATM usage charge is zero, meaning deposit = balance.

$agent\ db$. % database
---
$(d0\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}d1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}d2)^{m}$.
% d0 means the accumulated deposit is $0, and so on.
$d0\rightarrow b0$.
$d1\rightarrow b1$.
$d2\rightarrow b2$.

$agent\ m$. % ATM machine
---
$(d0\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}d1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}d2)^{\$kim}$.
% request deposit checking to kim
$(b0\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{db}$.
% request balance checking to DB

$agent\ \$kim$. % $\$kim$ is a super agent.
---
$(b0\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b1\mbox{\small\raisebox{0.0pt}{$\bigtriangleup$}}b2)^{m}$.
% request balance checking to ATM

Now let us consider the agent $kim$ and the agent $credit$. They both want to
know the balance of Kim’s account. The initial balance checking will return
$b0$, meaning zero dollars. Later, suppose Kim deposits $1. In this case, the
balance information on $db$ will be updated to one dollar and, subsequently,
the response to balance checking by ATM, kim and the credit company will be
updated to $b1$, as desired.

##  7 Adding neural networks

The integration of neural nets and symbolic AI is often beneficial. There are
several ambitious approaches such as DeepProblog[6] and these approaches try
to combine both worlds within a single agent. Unfortunately, these approaches
considerably increase the complexity of the machine.

Fortunately, in the multi-agent setting, this integration can be achieved in a
rather simple way by introducing a new kind of agents called
$\eta$-agent(neural-net agents).

There are now three kinds of agents:

  * •

regular agents who perform deductive reasoning, and

  * •

$\eta$-agents who perform inductive reasoning.

  * •

super agents who are able to create resources.

An $\eta$-agent is an agent which is designed to implement low-level
perceptions (visual data, etc) via trainig. That is, its knowledgebase is in
neural-net form for easy training. In the sequel, $\eta$-agents are prefixed
with $\eta$.

We assume the following:

(1) the input/output of a neural network is encapsulated in the form of an
atomic predicate,

(2) the output of a neural network is deterministic. Thus, we do not consider
probability here, and

(3) For simplicity, neural nets are specified in logical form ($\mbox{\bf
CL9}^{\Phi}$ to be exact), instead of in functional form.

An $\eta$-agent with its knowledgebase $N$ proceeds in two modes:

  * •

When there is a query $A$, it proceeds in deductive mode by processing $A$
using $N$ via $\mbox{\bf CL9}^{\Phi}$ deduction.

  * •

When it is idle, it trains itself on sample data by updating $N$.

As an example, we will look at the program which, given image of an animal,
identifies its habitat.

We assume the following:

  * •

The regular agent $a$ implements the predicate $habitat(j,h)$ where $j$ is an
image of an animal and $h$ is the main habitat of the animal. We consider two
kinds of animals: lion and tiger. We assume that $j$ belongs to
$S=\\{i_{1},\ldots,i_{3}\\}$ where $S$ is a set of three images of animals.

  * •

The $\eta$-agent $\eta d$ implements the predicate $animal(j,n)$ where $j$ is
image of an animal and $n$ is the corresponding animal.

The above can be implemented as follows:

$agent\ a$. % animal habitats
---
% Below is a query to $\eta d$.
$((animal(i_{1},lion)\sqcup animal(i_{1},tiger))\sqcap$
$(animal(i_{2},lion)\sqcup animal(i_{2},tiger))\sqcap$
$(animal(i_{3},lion)\sqcup animal(i_{3},tiger)))^{\eta d}$.
% Rules that maps animals to the corresponding habitats.
$animal(i_{1},tiger)\rightarrow habitat(i_{1},india)$.
$animal(i_{2},tiger)\rightarrow habitat(i_{2},india)$.
$animal(i_{3},tiger)\rightarrow habitat(i_{3},india)$.
$animal(i_{1},lion)\rightarrow habitat(i_{1},senegal)$.
$animal(i_{2},lion)\rightarrow habitat(i_{2},senegal)$.
$animal(i_{3},lion)\rightarrow habitat(i_{3},senegal)$.

% Given image $j$, the agent $\eta d$ produces the corresponding animal via
deep learning. We do not show the details here.

$agent\ \eta d$. % $\eta$-agent
---
$\vdots$.

When the agent $\eta d$ is idle, it trains itself and updates its
knowledgebase by adjusting weights. Now let us invoke a query
$habitat(i_{3},india)\sqcup habitat(i_{3},senegal)$ to the agent $a$ where
$i_{3}$ is the image of some animal. To solve this query, the agent $a$
invokes another query shown above to the agent $\eta d$. Now $\eta d$ switches
from training mode to deduction mode to solve this query. Let us assume that
the response from $\eta d$ is $animal(i_{3},lion)$. Using the rules related to
animal’s habitats, the agent $a$ will return $habitat(i_{3},senegal)$ to the
user. Note that our agents behave just like real-life agents. For example, a
doctor typically trains himself when he is idle. If there is a service
request, then he switches from training mode to deduction mode.

## References

  * [1] G. Japaridze. Introduction to computability logic. Annals of Pure and Applied Logic 123 (2003), pp. 1-99.
  * [2] G. Japaridze. Propositional computability logic I. ACM Transactions on Computational Logic 7 (2006), No.2, pp. 302-330.
  * [3] G. Japaridze. Propositional computability logic II. ACM Transactions on Computational Logic 7 (2006), No.2, pp. 331-362.
  * [4] G. Japaridze. In the beginning was game semantics. In: Games: Unifying Logic, Language and Philosophy. O. Majer, A.-V. Pietarinen and T. Tulenheimo, eds. Springer Verlag, Berlin (to appear). Preprint is available at http://arxiv.org/abs/cs.LO/0507045
  * [5] G. Japaridze. Sequential operators in computability logic. Information and Computation 206, No.12 (2008), pp. 1443-1475.
  * [6] R. Manhaeve et al. DeepProbLog: neural probabilistic logic programming, NIPS’18: Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018, pp.3753–3763.