11institutetext: 1\. University of Calgary
2\. Huazhong University of Science and Technology

# Synchronous Image-Label Diffusion Probability Model with Application to
Stroke Lesion Segmentation on Non-contrast CT

Jianhai Zhang1 Tonghua Wan2 Ethan MacDonald1 Bijoy Menon1
Aravind Ganesh1 Qiu Wu2

###### Abstract

Stroke lesion volume is a key radiologic measurement for assessing the
prognosis of Acute Ischemic Stroke (AIS) patients, which is challenging to be
automatically measured on Non-Contrast CT (NCCT) scans. Recent diffusion
probabilistic models have shown potentials of being used for image
segmentation. In this paper, a novel Synchronous image-label Diffusion
Probability Model (SDPM) is proposed for stroke lesion segmentation on NCCT
using Markov diffusion process. The proposed SDPM is fully based on a Latent
Variable Model (LVM), offering a complete probabilistic elaboration. An
additional net-stream, parallel with a noise prediction stream, is introduced
to obtain initial noisy label estimates for efficiently inferring the final
labels. By optimizing the specified variational boundaries, the trained model
can infer multiple label estimates for reference given the input images with
noises. The proposed model was assessed on three stroke lesion datasets
including one public and two private datasets. Compared to several U-net and
transformer based segmentation methods, our proposed SDPM model is able to
achieve state-of-the-art performance. The code is publicly available.

###### Keywords:

Diffusion probability model Medical image segmentation Coupled Markov
stochastic process

##  1 Introduction

Stroke lesion volume is a key radiologic measurement in assessing prognosis of
Acute Ischemic Stroke (AIS) patients [1]. Early assessment of patient outcome
is beneficial to inform patients about future perspectives as soon as
possible, and to enable treating physician to adapt and personalize the
treatments and rehabilitation plans. Ischemic stroke lesions, such as
hemorrhagic and ischemic infarct, are typically measured on post treatment
Non-Contrast CT (NCCT) scans. Manual contouring of stroke lesions are still
clinically deemed as gold standard for volume measurement even though it is
time consuming and observer dependent [2, 3]. Regardless of many attempts to
automate segmentation for stroke lesions [4, 5, 6], there are still no methods
well-established for NCCT, as cerebral CT is limited due to low signal to
noise ratio, low contrast of soft tissues, partial volume effects, and
acquisition variability across different scanners [7].

This study aims to develop a Diffusion Probabilistic Model (DPM) based
approach [8] to accurately segmenting ischemic or hemorrhagic lesion on NCCT.
Recently, the methods [9, 10, 11] based on DPM have received increasing
attention for medical image segmentation. The attention is warranted because
of the powerful denoising mechanism against even high degrees of noise
contamination. In essence, a progressive denoising process [12] for image
generation (or potential image labels) is foundationally different from the
previous techniques outputting results immediately. Moreover, the introduction
of denoising for training indeed improves the robustness of the prediction
because of the massive observations with different degrees of noises. Thus,
the stability of segmentation performance is able to be guaranteed.
Nevertheless, the current diffusion models for medical image segmentation [10,
11] are simply treating the image as the conditional input fed to the models
without probabilistic interpretability.

Figure 1: Synchronous diffusion and reverse processes utilized in our proposed
SDPM

In this paper, based on a fully generative Latent Variable Model (LVM), a
Synchronous image-label Diffusion Probability Model (SDPM) is proposed for
efficiently inferring segmentation labels. To this end, we developed a
specified variant of variational inference method and a set of related
strategies, including synchronous image-label diffusion process illustrated in
Fig.1 and a two-stream network of predicting initial noisy label where the
inference process starts, to fit our segmentation task, efficiently restoring
the segmentation labels from noisy initials. Accordingly, the label inference
methods are implemented in four different ways with their own strength, making
SDPM more flexible and applicable. Our contributions briefly include:

1) SDPM is proposed using a synchronous Markov diffusion process for medical
image segmentation task. SDPM is based on the fully generative latent variable
model with derivational interpretability.

2) A specified variational inference and the involved strategies are proposed
for training SDPM. Four inference algorithms in different ways are proposed to
efficiently obtain final labels.

##  2 Methodology

###  2.1 Revisit diffusion model

As a LVM, diffusion model[8, 13] has been successfully applied to the field of
image generation with the form $p_{\theta}(x_{0})\triangleq\int
p_{\theta}(x_{0:T})d{x_{1:T}}$, where $x_{1:T}$ are the latent variables,
$x_{0}$ follows an approximately sampled distribution $q(x_{0})$. The joint
distribution $p_{\theta}(x_{0:T})$ is called the reverse process [14] modeled
by a first-order Markov chain starting at
$x_{T}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$. The diffusion process
$q(x_{1:T}|x_{0})$ is also a Markov chain, which adds standard normal noise
with a variance schedule $\beta_{t}$. All the mathematical notations are as
same as in the paper [13]:

$p_{\theta}(x_{0:T})\\!\triangleq
p(x_{T})\\!\prod\nolimits_{t=1}^{T}p_{\theta}(x_{t-1}|x_{t}),\texttt{
}q(x_{1:T}|x_{0})\triangleq\prod\nolimits_{t=1}^{T}q(x_{t}|x_{t-1})$ (1)

Minimizing the Kullback-Leibler (KL) Divergence between $q(x_{1:T}|x_{0})$ and
$p_{\theta}(x_{0:T})$ will optimize the variational boundary on the negative
log-likelihood. To efficiently implement this minimization, two properties are
utilized: 1) the observation $x_{t}$ is sampled at any time in a closed form:

$q(x_{t}|x_{0})\triangleq\mathcal{N}(x_{t}|\sqrt{\bar{\alpha}_{t}}x_{0},\gamma_{t}\mathbf{I}),\texttt{
}\bar{\alpha}_{t}=\prod\nolimits_{k=1}^{t}\alpha_{k},\alpha_{t}=1-\beta_{t},\gamma_{t}=1-\bar{\alpha}_{t}$
(2)

2) a vicarious posterior $q(x_{t-1}|,x_{t},x_{0})$ with condition $x_{0}$ is
used for an intractable posterior $q(x_{t-1}|x_{t})$ when training the model:

$\displaystyle
q(x_{t-1}|,x_{t},x_{0})\triangleq\mathcal{N}(x_{t-1}|\tilde{\mu}_{t}(x_{t},x_{0}),\tilde{\beta}_{t}\mathbf{I})$
where
$\displaystyle\tilde{\mu}_{t}(x_{t},x_{0})={\sqrt{\bar{\alpha}_{t-1}}\beta_{t}\gamma_{t}^{-1}}x_{0}+{\sqrt{{\alpha}_{t}}\gamma_{t-1}\gamma_{t}^{-1}}x_{t}\texttt{
and }\tilde{\beta}_{t}={\beta_{t}\gamma_{t-1}\gamma_{t}^{-1}}$ (3)

After simplifying the loss function, the optimization process is equivalent to
predict the noise $\varepsilon_{t}$ from the diffused image $x_{t}$ using a
neural network:

$\mathcal{L}=\mathbb{E}_{x_{t},\varepsilon_{t}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\big{[}{2\sigma^{2}_{t}{\alpha}_{t}{\beta}_{t}^{-2}\gamma_{t}}\|\varepsilon_{t}-\hat{\varepsilon}_{t}(x_{t},t)\|^{2}\big{]}$
(4)

The convergent model is capable of inferring the unseen images from the random
noise following the standard normal distribution.

###  2.2 SDPM for Semantic Segmentation

We extend the diffusion model to segmentation tasks with the form
$p_{\theta}(y_{0}|x_{0})=p_{\theta}(y_{0},x_{0})/p_{\theta}(x_{0})\propto
p_{\theta}(y_{0},x_{0})$, where $p_{\theta}(y_{0},x_{0})\triangleq\int
p_{\theta}(x_{0:T},y_{0:T})dx_{1:T},y_{1:T}$, and $y_{1:T}$ are new members of
latent variables. In the new model, the joint distribution
$p_{\theta}(x_{0:T},y_{0:T})$ is defined as the reverse process, and it can be
factorized as an original DDPM [13] part $p_{\theta}(x_{0:T})$ and a
conditional reverse process $p_{\theta}(y_{0:T}|x_{0:T})$, which is a series
of terms by Markov chains starting at $p_{\theta}(y_{T}|x_{T})$:

$p_{\theta}(y_{0:T}|x_{0:T})=p_{\theta}(y_{T}|x_{T})\prod\nolimits_{t=1}^{T}p_{\theta}(y_{t-1}|y_{t},x_{t-1})$
(5)

The diffusion process is an approximate conditional posterior
$q(y_{1:T}|y_{0},x_{0:T})$:

$q_{(}y_{1:T}|y_{0},x_{0:T})=\prod\nolimits_{t=1}^{T}q(y_{t}|y_{t-1},x_{t})$
(6)

A KL Divergence is defined between the diffusion process
$q_{(}y_{1:T}|y_{0},x_{0:T})$ and the reverse process
$p_{\theta}(y_{0:T}|x_{0:T})$ to obtain the variational upper bound on the
negative log likelihood because of the non-negative property of KL divergence
[15]:

$\mathbb{KL}\big{(}q(y_{1:T}|y_{0},x_{0:T})\|p_{\theta}(y_{1:T}|y_{0},x_{0:T})\big{)}-\mathbb{E}_{q}[\texttt{log}p_{\theta}(y_{0}|x_{0})]\geqslant
0$ (7)

The loss function is then defined as minimizing the KL divergence of the
conditional posterior and the unnormalized distribution:

$\displaystyle\\!\\!\\!\\!\\!\mathcal{L}$ $\displaystyle\\!\\!\triangleq$
$\displaystyle\\!\mathbb{E}_{q}\Big{[}\texttt{log}\frac{p_{\theta}(y_{0}|x_{0})}{p_{\theta}(y_{T}|x_{T})}+\sum\nolimits_{t=1}^{T}\texttt{log}\frac{q(y_{t}|y_{t-1},x_{t})}{p_{\theta}(y_{t-1}|y_{t},x_{t-1})}-\texttt{log}p_{\theta}(y_{0}|x_{0})\Big{]}$
(8) $\displaystyle\\!\\!=$
$\displaystyle\\!\\!\\!\mathbb{E}_{q}\Big{[}\texttt{log}q(y_{T}|y_{0})+\\!\sum_{t=2}^{T}\texttt{log}\frac{q(y_{t-1}|y_{t},y_{0},x_{t})}{p_{\theta}(y_{t-1}|y_{t},x_{t-1})}\Big{]}-\\!\texttt{log}p_{\theta}(y_{0}|y_{1},x_{0})p_{\theta}(y_{T}|x_{T})$

Eq.(8) indicates the acquisition of $y_{0}$ could be the traditional way of
outputting the label $x_{0}\mapsto y_{0}$, or a generative way of Markov
chains by inference $x_{T}\mapsto y_{0}$. Namely, as long as an initial label
estimate $y_{T}$ exists, the trained diffusion model can infer back and get
the label $y_{0}$. To this end, an additional sub-network for estimating the
noisy label $y_{T}$ from the image $x_{T}$ is introduced into the network.

Unfortunately, it is difficult to estimate a proper initial $y_{T}$ for the
subsequent inference, because image information is severely destroyed. It is
less likely to predict $y_{T}$ from the image $x_{T}$ nearly following the
distribution $\mathcal{N}(\mathbf{0},\mathbf{I})$. Thus,
$-\texttt{log}p_{\theta}(y_{T}|x_{T})$ is a very strong restriction for
predicting the initial $y_{T}$. Using the final initial $y_{T}$ could produce
a poor result and degrade the segmentation performance notably. To obtain a
good initial $y_{t}$ for inferring $y_{0}$, we add a time window of length
$T_{p}$ to train the model at each time (the loss $\mathcal{L}_{p}$ in
Eq.(9)), guaranteeing that the label $y_{0}$ could be efficiently restored.
Introducing the prospect to predict an initial $y_{t}$, the acquisitions of
$y_{t-1}$ do not solely depend on the immediate outputs of the network fed by
the noisy image $x_{t-1}$ any longer. The term
$\mathbb{E}_{q}\big{[}\texttt{log}q(y_{T}|y_{0})\big{]}$ is constant and thus
can be omitted. Therefore, the loss function is further simplified as:

$\\!\mathcal{L}=\\!\underbrace{\mathbb{E}_{q}\Big{[}\sum\nolimits_{t=2}^{T}\texttt{log}\frac{q(y_{t-1}|y_{t},y_{0},x_{t})}{p_{\theta}(y_{t-1}|y_{t})}\Big{]}}_{\mathcal{L}_{d}}-\underbrace{\sum\nolimits_{t=0}^{T_{p}}\texttt{log}p_{\theta}(y_{t}|x_{t})}_{\mathcal{L}_{p}}-\underbrace{\texttt{log}p_{\theta}(y_{0}|y_{1})}_{\mathcal{L}_{d_{0}}}$
(9)

For the loss $\mathcal{L}_{d}$, the term $p_{\theta}(y_{t-1}|y_{t})$ in
reverse process is still compared using KL divergence by the conditional
posterior $q(y_{t-1}|y_{t},y_{0},x_{t})$ in the diffusion process introduced
in [13]. To make the distribution $q(y_{t-1}|y_{t},y_{0},x_{t})$ tractable, a
further assumption is made that images and labels are both overlain by the
same Gasussian noise during the diffusion process, i.e., synchronous image-
label diffusion process. Thus, the posterior $q(y_{t-1}|y_{t},y_{0},x_{t})$ is
degenerated as $q(y_{t-1}|y_{0},\varepsilon_{t})$, which only relies on the
noise at time $t$ and $y_{0}$:

$\displaystyle
q(y_{t-1}|y_{0},\varepsilon_{t})=\mathcal{N}(y_{t-1}|\tilde{\mu}_{t},\tilde{\beta}_{t}\mathbf{I})$
where
$\displaystyle\tilde{\mu}_{t}=\sqrt{\bar{\alpha}_{t-1}}y_{0}+{\sqrt{\alpha_{t}}({\gamma}_{t-1}\gamma_{t}^{-\frac{1}{2}})}\varepsilon_{t},\texttt{
}\tilde{\beta}_{t}=\beta_{t}{\gamma_{t-1}}\gamma_{t}^{-1}$ (10)

Since the diffusion process for images and labels are shared with the same
noise $\varepsilon_{t}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$, the images and
labels at time $t$ can thus be sampled as:

$x_{t}=\sqrt{\bar{\alpha}_{t}}x_{0}+\sqrt{\gamma_{t}}\varepsilon_{t},\texttt{
}y_{t}=\sqrt{\bar{\alpha}_{t}}y_{0}+\sqrt{\gamma_{t}}\varepsilon_{t}$ (11)

The loss $\mathcal{L}_{d_{0}}$ is for optimizing the last step of generating
$y_{0}$. Some cumbersome discrete segmentation points might degrade the
performance to some degree. To refrain from the influence from those points,
in addition to applying the same strategy of stopping adding the uncertainty
inference of variance $\tilde{\beta}_{1}$ in [13], we also append a self-
attention module with a convolutional layer of frozen parameters of all ones
to get rid of the discrete points with a proper threshold, as illustrated in
Fig.2.

Figure 2: The training process of the proposed SDPM with the supervised loss
functions

###  2.3 Optimizing SDPM

The choice for the transition term $p_{\theta}(y_{t-1}|y_{t})$ in the reverse
process is still a Gaussian distribution, i.e.,
$\mathcal{N}\big{(}\mu_{\theta}(y_{t},t),\sigma_{t}^{2}\mathbf{I}\big{)}$,
where $\theta$ is the trainable parameters and $\sigma_{t}^{2}=\beta_{t}$ or
$\sigma_{t}^{2}=\tilde{\beta_{t}}$ are suggested in [13]. The loss
$\mathcal{L}_{d}$ is reparameterized as:

$\mathcal{L}_{d}=\mathbb{E}_{q}\Big{[}\frac{1}{2\sigma_{t}^{2}}\|\tilde{\mu}_{t}(y_{0},\varepsilon_{t})-\mu_{\theta}(y_{0},\varepsilon_{t})\|^{2}\Big{]}-\underbrace{{2^{-1}D}\texttt{log}\tilde{\beta}+D\texttt{log}\sigma_{t}}_{C}$
(12)

where $D$ is image dimensionality. The loss function reveals that as long as
the model $\mu_{\theta}$ is able to predict $\tilde{\mu}_{t}$ given the label
$y_{0}$ with the shared $\varepsilon_{t}$ in the posterior, the final label
$y_{0}$ is able to be inferred by Markov process.

To further reduce the uncertainty of inferring $y_{0}$ through stochastic
samplings of $q(y_{t-1}|y_{0},\varepsilon_{t})$, different from the original
DDPM [13], SDPM adds another loss function to restrict the difference between
the true and predicted final labels $y_{0}$:

$\mathcal{L}_{d}=\mathbb{E}_{y_{0},\varepsilon_{t}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\Big{[}\underbrace{\frac{{\bar{\alpha}_{t-1}}}{2\sigma^{2}_{t}}\|y_{0}-\hat{y}_{0}(\hat{y}_{t},\hat{\varepsilon}_{t},t)\|^{2}}_{\mathcal{L}_{d_{1}}}+\underbrace{\frac{{{\alpha}_{t}\gamma_{t-1}^{2}}}{2\sigma^{2}_{t}\gamma_{t}}\|\varepsilon_{t}-\hat{\varepsilon}_{t}(y_{t},t)\|^{2}}_{\mathcal{L}_{d_{2}}}\Big{]}+\xi$
(13)

where
$\hat{y}_{0}=\hat{y}_{t}/{\sqrt{\bar{\alpha}_{t}}}-\sqrt{\gamma_{t}/\bar{\alpha}_{t}}\hat{\varepsilon}_{t}$
and $\xi$ is a binomial residue term. As the losses $\mathcal{L}_{d_{1}}$ and
$\mathcal{L}_{d_{2}}$ are getting optimized, the $\xi$ is also getting
optimized and thus has been ignored for now. Notice that it is impossible to
predict $\varepsilon_{t}$ from the label $y_{t}$,

because there is no image information from $y_{t}$ at all. Fortunately, from
[9, 16], the network predicting the noise at each diffusion process also
carries the label information. Thus, the model can utilize $x_{t}$ to predict
the shared noise $\hat{\varepsilon}_{t}(x_{t},t)$.

For the loss $\mathcal{L}_{p}$, since the network can predict stochastic
noise, the noisy labels $y_{t}$ can thus be predicted with the supervision of
the noised label:

$\mathcal{L}_{p}=\mathbb{E}_{x_{t}\sim
q(x_{t}|x_{0})}\Big{[}\|y_{t}-\hat{y}_{t}(x_{t},t)\|^{2}\Big{]}$ (14)

To further improve the segmentation performance, a classic dice loss can also
be applied to this composite loss function with the treatment of adding an
activation function of sigmoid directly at the last layer of outputting
$y_{0}$. The supervised loss functions are illustrated in Fig.2.

###  2.4 Inferring the Labels by SDPM

The final label $y_{0}$ can be inferred in four ways. The first is the fast
and easy way by directly outputting: $\hat{y}_{0}^{\mathbf{avg}}=\hat{y}_{0}$,
where $\hat{y}_{0}$ is the output of the trained network given the clean image
$x_{0}$. The second is based on the salient weight $\psi_{t}$ over the time
window $T_{i}$:
$\hat{y}_{0}^{\mathbf{sal}}=\frac{1}{N}\sum_{n=1}^{N}\big{(}\sum_{t=0}^{T_{i}<T}\hat{y}_{0}\psi_{t}\big{)}$,
where $\psi_{t}=1-(\frac{t}{T_{i}})^{\nu}$, $\nu>1$ are gradually degraded
coefficients. The third is based on the Markov chain inference starting at
time $T_{i}$:
$\hat{y}_{0}^{\mathbf{infer}}=\frac{1}{N}\sum_{n=1}^{N}\big{(}\mathbf{IL}(d_{i},T_{i})\big{)}$,
where $d_{i}\in\mathbb{R}^{(0,1)},T_{i}\in\\{0,\cdots,T\\}$ and
$\mathbf{IL}(\cdot)$ is the Algorithm 1. The last is the union of all the
results:
$\hat{y}_{0}^{\mathbf{all}}=\hat{y}_{0}^{\mathbf{avg}}\cup\hat{y}_{0}^{\mathbf{sal}}\cup\hat{y}_{0}^{\mathbf{infer}}$.
Note that the second and third inferences are performed $N$ times because of
the randomness of noise. The average value of $N$ time is used as the final
result.

Algorithm 1 Inferencing Labels(IL) in Reverse Process

1:Input: image $x_{0}$,  Parameters: $d_{i}\in\mathbb{R}^{(0,1)}$, $T_{i}<T$

2:Initialization: noised image $\hat{x}_{T_{i}}=x_{T_{i}}$ and noised label
$\hat{y}_{T_{i}}$ using (11)

3:noise estimate $\hat{\varepsilon}_{T_{i}}$ using trained neural network

4:for $t=T_{i},\cdots,1$ do

5: estimate $\hat{x}_{0}$, $\hat{y}_{0}$ using (11)

6: if $t>1$ then

7: sampling ${\varepsilon}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$: estimate
$\hat{x}_{t-1}=\sqrt{\bar{\alpha}_{t-1}}\hat{x}_{0}+\frac{\sqrt{\alpha_{t}}\gamma_{t-1}}{\sqrt{\gamma_{t}}}\hat{\varepsilon}_{t}+\frac{\beta_{t}\gamma_{t-1}}{\gamma_{t}}\varepsilon$

8: and
$\hat{y}_{t-1}=\sqrt{\bar{\alpha}_{t-1}}\hat{y}_{0}+\frac{\sqrt{\alpha_{t}}\gamma_{t-1}}{\sqrt{\gamma_{t}}}\hat{\varepsilon}_{t}+\frac{d_{i}\beta_{t}\gamma_{t-1}}{\gamma_{t}}\varepsilon$

9: update next loop noise $\hat{\varepsilon}_{t-1}$ from $\hat{x}_{t-1}$ using
trained neural network

10: else if $t=1$ then

11: estimate $\hat{y}_{0}$ using (11),
$\hat{y}_{0}^{\mathbf{final}}=\sqrt{\bar{\alpha}_{t-1}}\hat{y}_{0}+\frac{\sqrt{\alpha_{t}}\gamma_{t-1}}{\sqrt{\gamma_{t}}}\hat{\varepsilon}_{t}$

12:Output: label estimate $\hat{y}_{0}^{\mathbf{final}}$

##  3 Experiments and Results

Datasets and Pre-cessing: Two datasets were involved: 1) A private dataset,
named Infarct, containing 195 AIS patient NCCT scans (5 mm) were included. Of
195 patients, 123 images were used for training while the remained 72 for
testing. 2) Another private dataset comprising of 331 patients with acute
intracranial hemorrhage confirmed by NCCT (2.5mm), called Hemorrhage, was also
included patients with acute ICH confirmed by NCCT (2.5 mm thickness). Of 331
patient scans, 241 scans were used for training and validation, and 90 were
used for testing.

Hyper-parameters Settings: Online data augmentations was performed, including
adding noise, rotations, scalings, inplane flipping, etc. Learning rate was
reduced non-linearly from 1e-4 to 6e-5 with the Adam optimizer, where
$lr=lr_{init}*(1-i_{c}/i_{max})^{0.9}+lr_{min}*(i_{c}/i_{max})^{0.9}$, $i_{c}$
is the current iteration and $i_{max}$ is the maximum number of iteration. The
variance schedule $\beta_{t}$ is the sigmoid curve[17]. P2 Weighting
coefficients during the training suggested in [18]. The repeated times are 100
and 50 for $\hat{y}_{0}^{\mathbf{sal}}$ and $\hat{y}_{0}^{\mathbf{infer}}$ in
the inference process. Diffusion period $T$ is 500 and the initial time
$T_{i}=T/2$.

Evaluation Metrics: Three metrics[19] including Dice, Volume Correlation(VC)
based on the Pearson product-moment correlation coefficient, and Volume
Difference Percentages(VDP), were used to quantitatively assess the
performance of the model prediction at a voxel level compared to manual
contouring. Five other methods, including SegResNet, UNETR, SwinUNETR, nnUNet,
nnUnet++, were also applied on the same three datasets. For fair comparisons,
the best performance with the optimized parameters for each method was
reported.

Results: A few segmentation examples are visualized in Fig.3. Quantitative
results in Table.1 show SDPM with four inferences obtained the best
performance on the whole with Dice, VC and VDP. The method ’CDPM w/o noise’ is
with the same neural network architecture but without diffusion process. In
our private Infarct dataset, although SDPM w/o noise and
$\hat{y}_{0}^{\mathbf{all}}$ have obtained nearly same dice of 0.4,
SDPM-$\hat{y}_{0}^{\mathbf{all}}$ have better VC-0.619 and lower VDP-0.545. In
hemorrhage dataset, the best performance by $\hat{y}_{0}^{\mathbf{infer}}$ is
Dice-0.931, VC-0.985 and VDP-0.032. Additionally, Table.1 also suggested that
our method was able to greatly reduce the VDP scores across three datasets.

Table 1: Quantitative performance on Infarct and Hemorrhage. Datasets | Infarct | Hemorrhage
---|---|---
Methods | Dice | VC | VDP | Dice | VC | VDP
SegResNet[20] | 0.334 | 0.409 | 0.574 | 0.926 | 0.976 | 0.086
UNETR[21] | 0.304 | 0.392 | 0.709 | 0.910 | 0.967 | 0.100
SwinUNETR[22] | 0.366 | 0.455 | 0.656 | 0.908 | 0.965 | 0.101
nnUNet[23] | 0.337 | 0.488 | 0.692 | 0.922 | 0.978 | 0.096
nnUNet++[24] | 0.376 | 0.507 | 0.639 | 0.915 | 0.968 | 0.070
SegDiff[11] | 0.389 | 0.482 | 0.658 | 0.927 | 0.976 | 0.066
MedSegDiff[10] | 0.396 | 0.540 | 0.657 | 0.930 | 0.976 | 0.069
SDPM w/o noise[13] | 0.400 | 0.557 | 0.633 | 0.927 | 0.961 | 0.074
SDPM-$\hat{y}_{0}^{\mathbf{avg}}$ | 0.378 | 0.544 | 0.641 | 0.929 | 0.972 | 0.078
SDPM-$\hat{y}_{0}^{\mathbf{infer}}$ | 0.374 | 0.531 | 0.652 | 0.931 | 0.985 | 0.067
SDPM-$\hat{y}_{0}^{\mathbf{sal}}$ | 0.397 | 0.581 | 0.540 | 0.928 | 0.980 | 0.032
SDPM-$\hat{y}_{0}^{\mathbf{all}}$ | 0.399 | 0.619 | 0.545 | 0.928 | 0.980 | 0.032

##  4 Discussion and Conclusion

A novel probabilistic SDPM is proposed to automatically segment stroke lesions
of hemorrhage and infarct on NCCT, in order to alleviate the tedious manual
contouring currently used in clinic [25]. The segmentation labels are output
by SDPM in a fully probabilistic generative way. With the proposed several
inference methods, the model was able to efficiently recover the lesion
labels. Compared to the reference standard of manual contouring, quantitative
evaluations demonstrate the efficacy of the proposed SDPM, outperforming
several CNN and transformer based methods.

Figure 3: Qualitative results for infarct and hemorrhage segmentations on two
datasets

This study represents the first study to use a completely probabilistic
inference model based on DPM to automatically segment infarct and hemorrhage
on NCCT. Table.1 has shown the proposed SDPM with four inference methods
obtained the start-of-the-art performance on two datasets. All the ablation
studies in Table.1 revealed every inference method has its own strength, where
salient weighting estimate $\hat{y}_{0}^{\mathbf{all}}$ reached the best VDP
of 0.540 and 0.032, $\hat{y}_{0}^{\mathbf{sal}}$ obtained the best Dice in two
infarct datasets. In the hemorrhage dataset, inference method
$\hat{y}_{0}^{\mathbf{infer}}$ reached the best results of Dice and VC.
Generally, the inference of immediately outputting the labels performed worse
than other three inference methods.

This study has several limitations. First, our datasets are limited. More
training samples may further improve the segmentation accuracy and
generalizability. Second, the final label inference is slightly influenced by
stochastic factors. It is time-consuming to get an average prediction based on
several inferences. Third, the predicted labels generated by different
inference methods were simply averaged. More advanced label fusion techniques
may improve the performance.

In conclusion, a synchronous image-label diffusion model by a LVM is proposed
to segment stroke lesion of infarct and hemorrhage on NCCT. Experiments on
three datasets demonstrate the efficacy of the proposed method, suggesting its
potentials of being used for stroke lesion volume measurement.

## References

  * [1] A. Bucker, A. M. Boers, J. C. Bot, O. A. Berkhemer, H. F. Lingsma, A. J. Yoo, W. H. Van Zwam, R. J. Van Oostenbrugge, A. Van der Lugt, D. W. Dippel _et al._ , “Associations of ischemic lesion volume with functional outcome in patients with acute ischemic stroke: 24-hour versus 1-week imaging,” _Stroke_ , vol. 48, no. 5, pp. 1233–1240, 2017.
  * [2] J. M. Ospel, W. Qiu, B. K. Menon, A. Mayank, A. Demchuk, R. McTaggart, R. G. Nogueira, A. Y. Poppe, M. Jayaraman, B. Buck _et al._ , “Radiologic patterns of intracranial hemorrhage and clinical outcome after endovascular treatment in acute ischemic stroke: results from the escape-na1 trial,” _Radiology_ , vol. 300, no. 2, pp. 402–409, 2021.
  * [3] J. M. Ospel, B. K. Menon, W. Qiu, N. Kashani, A. Mayank, N. Singh, P. Cimflova, M. Marko, R. G. Nogueira, R. A. McTaggart _et al._ , “A detailed analysis of infarct patterns and volumes at 24-hour noncontrast ct and diffusion-weighted mri in acute ischemic stroke due to large vessel occlusion: results from the escape-na1 trial,” _Radiology_ , vol. 300, no. 1, pp. 152–159, 2021.
  * [4] A. Dobshik, S. Verbitskiy, I. Pestunov, K. Sherman, Y. N. Sinyavskiy, A. Tulupov, and V. Berikov, “Acute ischemic stroke lesion segmentation in non-contrast ct images using 3d convolutional neural networks,” _arXiv:2301.06793_ , 2023.
  * [5] R. Gauriau, B. C. Bizzo, D. S. Comeau, J. M. Hillis, C. P. Bridge, J. K. Chin, J. Pawar, A. Pourvaziri, I. Sesic, E. Sharaf _et al._ , “Head ct deep learning model is highly accurate for early infarct estimation,” _Scientific Reports_ , vol. 13, no. 1, p. 189, 2023.
  * [6] K. Liang, K. Han, X. Li, X. Cheng, Y. Li, Y. Wang, and Y. Yu, “Symmetry-enhanced attention network for acute ischemic infarct segmentation with non-contrast ct images,” in _Medical Image Computing and Computer Assisted Intervention–MICCAI 2021: 24th International Conference, Strasbourg, France, September 27–October 1, 2021, Proceedings, Part VII 24_. Springer, 2021, pp. 432–441.
  * [7] L. Liu, L. Kurgan, F.-X. Wu, and J. Wang, “Attention convolutional neural network for accurate segmentation and quantification of lesions in ischemic stroke disease,” _Medical Image Analysis_ , vol. 65, p. 101791, 2020.
  * [8] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli, “Deep unsupervised learning using nonequilibrium thermodynamics,” in _International Conference on Machine Learning_. PMLR, 2015, pp. 2256–2265.
  * [9] D. Baranchuk, I. Rubachev, A. Voynov, V. Khrulkov, and A. Babenko, “Label-efficient semantic segmentation with diffusion models,” _arXiv:2112.03126_ , 2021.
  * [10] J. Wu, H. Fang, Y. Zhang, Y. Yang, and Y. Xu, “Medsegdiff: Medical image segmentation with diffusion probabilistic model,” _arXiv:2211.00611_ , 2022\.
  * [11] T. Amit, E. Nachmani, T. Shaharbany, and L. Wolf, “Segdiff: Image segmentation with diffusion probabilistic models,” _arXiv:2112.00390_ , 2021.
  * [12] Y. Song and S. Ermon, “Generative modeling by estimating gradients of the data distribution,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [13] J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 6840–6851, 2020.
  * [14] S. Sommer, “Anisotropic distributions on manifolds: Template estimation and most probable paths,” in _Information Processing in Medical Imaging: 24th International Conference, IPMI 2015, Sabhal Mor Ostaig, Isle of Skye, UK, June 28-July 3, 2015, Proceedings 24_. Springer, 2015, pp. 193–204.
  * [15] R. Lopez, J. Regier, M. I. Jordan, and N. Yosef, “Information constraints on auto-encoding variational bayes,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [16] A. Voynov, K. Aberman, and D. Cohen-Or, “Sketch-guided text-to-image diffusion models,” _arXiv:2211.13752_ , 2022.
  * [17] A. Q. Nichol and P. Dhariwal, “Improved denoising diffusion probabilistic models,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 8162–8171.
  * [18] J. Choi, J. Lee, C. Shin, S. Kim, H. Kim, and S. Yoon, “Perception prioritized training of diffusion models,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 11 472–11 481.
  * [19] A. A. Taha and A. Hanbury, “Metrics for evaluating 3d medical image segmentation: analysis, selection, and tool,” _BMC medical imaging_ , vol. 15, no. 1, pp. 1–28, 2015.
  * [20] A. Myronenko, “3d mri brain tumor segmentation using autoencoder regularization,” in _Brainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries: 4th International Workshop, BrainLes 2018, Held in Conjunction with MICCAI 2018, Granada, Spain, September 16, 2018, Revised Selected Papers, Part II 4_. Springer, 2019, pp. 311–320.
  * [21] A. Hatamizadeh, Y. Tang, V. Nath, D. Yang, A. Myronenko, B. Landman, H. R. Roth, and D. Xu, “Unetr: Transformers for 3d medical image segmentation,” in _Proceedings of the IEEE/CVF winter conference on applications of computer vision_ , 2022, pp. 574–584.
  * [22] A. Hatamizadeh, V. Nath, Y. Tang, D. Yang, H. R. Roth, and D. Xu, “Swin unetr: Swin transformers for semantic segmentation of brain tumors in mri images,” in _Brainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries: 7th International Workshop, BrainLes 2021, Held in Conjunction with MICCAI 2021, Virtual Event, September 27, 2021, Revised Selected Papers, Part I_. Springer, 2022, pp. 272–284.
  * [23] F. Isensee, P. F. Jaeger, S. A. Kohl, J. Petersen, and K. H. Maier-Hein, “nnu-net: a self-configuring method for deep learning-based biomedical image segmentation,” _Nature methods_ , vol. 18, no. 2, pp. 203–211, 2021.
  * [24] Z. Zhou, M. M. Rahman Siddiquee, N. Tajbakhsh, and J. Liang, “Unet++: A nested u-net architecture for medical image segmentation,” in _Deep Learning in Medical Image Analysis and Multimodal Learning for Clinical Decision Support: 4th International Workshop, DLMIA 2018, and 8th International Workshop, ML-CDS 2018, Held in Conjunction with MICCAI 2018, Granada, Spain, September 20, 2018, Proceedings 4_. Springer, 2018, pp. 3–11.
  * [25] N. Samuels, K. C. Compagne, N. A. van der Ende, V. Chalos, P. R. Konduri, P. J. van Doormaal, W. H. van Zwam, C. B. Majoie, H. A. Marquering, B. Roozenbeek _et al._ , “Infarct volume after ischemic stroke as a mediator of the effect of endovascular thrombectomy on early postprocedural neurologic deficit,” _Journal of Stroke and Cerebrovascular Diseases_ , vol. 32, no. 2, p. 106906, 2023.


&\equiv(\eta_{v_{1}}(u_{1})+\dots+\eta_{v_{8}}(u_{8}))-(\eta_{v_{9}}(u_{9})+\dots+\eta_{v_{16}}(u_{16}))\\\
&\equiv(\eta_{v_{0}}(u_{1})+\dots+\eta_{v_{0}}(u_{8}))-(\eta_{v_{0}}(u_{9})+\dots+\eta_{v_{0}}(u_{16}))+(g_{v_{1}}+\dots+g_{v_{8}})-(g_{v_{9}}+\dots+g_{v_{16}})\\\
&\equiv(\eta_{v_{0}}(u_{1})+\dots+\eta_{v_{0}}(u_{8}))-(\eta_{v_{0}}(u_{9})+\dots+\eta_{v_{0}}(u_{16}))\equiv
0\mod J^{M^{\prime}}_{u_{1},\dots,u_{15}}.\end{split}$

Note that any polynomial $f$ in $\text{HP}_{d^{\prime\prime}}(s)$ can be
lifted to a polynomial $\tilde{f}$ in $\text{HP}_{d}(s)$ given by
$\tilde{f}(x_{1},\dots,x_{d}):=f(x_{d^{\prime}+1},\dots,x_{d})$. So we my lift
$\eta$ to a map $\tilde{\eta}\colon H^{\prime}\to\text{HP}_{d}(s)$. So it
follows from (8.8) that

$\begin{split}\tilde{\eta}(h_{1})+\dots+\tilde{\eta}(h_{8})\equiv\tilde{\eta}(h_{9})+\dots+\tilde{\eta}(h_{16})\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{u_{1},\dots,u_{15}\\}+T}\end{split}$

for all $h_{1},\dots,h_{16}\in H^{\prime}$ with
$h_{1}+\dots+h_{8}=h_{9}+\dots+h_{16}$. On the other hand for all
$h=v+\phi(u)\in H^{\prime}$ with $v\in T_{5}$ and $u\in U^{\prime}_{v}$,

$\sigma(\xi(h))=\eta_{v}(u)=\eta_{v_{0}}(u)+g_{v}=\eta(h)\mod
J^{M^{\prime}}_{u}.$

So $\xi(h)=\tilde{\eta}(h)\mod J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{h\\}+T}$.
This completes the proof of Proposition 8.2.

##  9\. Proof of the main theorem

We are now ready to complete the proof of Theorem 1.5. Our first task is to
remove the additional modulo over $J^{M}_{T}$ in Proposition 8.2. To this end,
we need to use the following lemma to find many structure-obstacle
decompositions (which allows us to use the intersection method):

######  Lemma 9.1 (Abundance of structure-obstacle decompositions).

Let $C,d^{\prime},d^{\prime\prime},D,K,s\in\mathbb{N}$, $d,R\in\mathbb{N}_{+}$
with $d=d^{\prime}+d^{\prime\prime}$, $p\gg_{C,d,K,s}1$ be a prime,
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form, and
$(\mathcal{C}_{0},Y)\subseteq\text{HP}_{d}(s)\times\mathbb{F}_{p}^{d}$ be a
$(K,C,D)$-structure-obstacle pair. If
$d^{\prime}\geq\max\\{D,3\\},d^{\prime\prime}\geq(R-1)d^{\prime}$ and $d\geq
4$, then there exist
$(\mathcal{C}_{0},Y,M,d^{\prime},d^{\prime\prime})$-structure-obstacle
decompositions $(T_{i},U_{i}),1\leq i\leq R$ such that $T_{1},\dots,T_{R}$ are
linearly independent.

###### Proof.

Let $A$ be the matrix associated to $M$. Suppose that for some $0\leq r\leq
R-1$ we have chosen
$(\mathcal{C}_{0},Y,M,d^{\prime},d^{\prime\prime})$-structure-obstacle
decompositions $(T_{i},U_{i}),1\leq i\leq r$ such that $T_{1},\dots,T_{r}$ are
linearly independent. We continue to construct $(T_{r+1},U_{r+1})$. Since
$(r+1)d^{\prime\prime}\leq Rd^{\prime\prime}\leq d$ (because
$d\geq(R-1)d^{\prime\prime}$), one can find a subspace $T_{r+1}$ of
$\mathbb{F}_{p}^{d}$ of dimension $d^{\prime\prime}$ such that
$T_{1},\dots,T_{r+1}$ are linearly independent. It then suffices to find a
subspace $U_{r+1}$ of $\mathbb{F}_{p}^{d}$ of dimension $d^{\prime}$ such that
$U_{r+1}\cap T_{r+1}=\\{\mathbb{0}\\}$,
$\text{rank}(M|_{U_{r+1}})=d^{\prime}$, $U_{r+1}\cap Y=\\{\mathbb{0}\\}$ and
$J^{M}_{U}\cap\mathcal{C}_{0}=\\{\mathbb{0}\\}$.

Assume that $Y=\cup_{i=1}^{C}V_{i}$ and
$\mathcal{C}_{0}=\\{{0},f_{1},\dots,f_{K}\\}$ for some subspaces $V_{i}$ of
dimension at most $D$ and $f_{j}\in\text{HP}_{d}(s)\backslash J^{M}$. Let
$\mathcal{B}$ denote the set of subspaces $U$ of $\mathbb{F}_{p}^{d}$ of
dimension $d^{\prime\prime}$ such that $U\cap T_{r+1}=\\{\mathbb{0}\\}$,
$\mathcal{B}^{\prime}$ the set of $U\in\mathcal{B}$ such that
$\text{rank}(M|_{U})<d^{\prime\prime}$, $\mathcal{B}_{i}$ the set of subspaces
$U\in\mathcal{B}\backslash\mathcal{B}^{\prime}$ such that $U\cap
V_{i}=\\{\mathbb{0}\\}$, and $\mathcal{B}^{\prime}_{j}$ the set of subspaces
$U\in\mathcal{B}\backslash\mathcal{B}^{\prime}$ such that $f_{j}\in
J^{M}_{U}$. To show the existence of $U_{k+1}$, it suffices to show that
$|\mathcal{B}|>|\mathcal{B}^{\prime}|+\sum_{i=1}^{C}|\mathcal{B}_{i}|+\sum_{j=1}^{K}|\mathcal{B}^{\prime}_{j}|$.

Let $b_{1},\dots,b_{d^{\prime}}\in\mathbb{F}_{p}^{d}$ be a basis of $T_{k+1}$.
We may complete it into a basis of $\mathbb{F}_{p}^{d}$ be adding some vectors
$b^{\prime}_{1},\dots,b^{\prime}_{d^{\prime\prime}}\in\mathbb{F}_{p}^{d}$.
Then each $U\in\mathcal{B}$ is uniquely determined by a linear transformation
$\alpha\colon\mathbb{F}_{p}^{d^{\prime\prime}}\to\mathbb{F}_{p}^{d^{\prime}}$
by setting

(9.1)
$U=\text{span}_{\mathbb{F}_{p}}\Bigl{\\{}\sum_{j=1}^{d^{\prime}}\alpha_{j}(x)b_{j}+\sum_{j=1}^{d^{\prime\prime}}x_{j}b^{\prime}_{j}\colon
x\in\mathbb{F}_{p}^{d^{\prime\prime}}\Bigr{\\}},$

where $x:=(x_{1},\dots,x_{d^{\prime\prime}})$ and
$\alpha(x):=(\alpha_{1}(x),\dots,\alpha_{d^{\prime}}(x))$. Each such linear
transformation is uniquely determined by the values
$\alpha(e_{1}),\dots,\alpha(e_{d^{\prime\prime}})$. So
$|\mathcal{B}|=p^{d^{\prime}d^{\prime\prime}}$.

Next we compute $|\mathcal{B}^{\prime}|$. Let $B$ be the $d\times d$ matrix
whose row vectors from top to bottom are
$b_{1},\dots,b_{d^{\prime}},b^{\prime}_{1},\dots,b^{\prime}_{d^{\prime\prime}}$
respectively. Then $BAB^{T}$ is invertible. So there exists a
$d^{\prime\prime}\times d$ matrix $J$ of rank $d^{\prime\prime}$ such that
$\det(JBAB^{T}J^{T})\neq 0$. Since $J$ is of rank $d^{\prime\prime}$, there
exist a $d^{\prime\prime}\times d^{\prime\prime}$ invertible matrix $C$ and a
$d^{\prime\prime}\times d^{\prime}$ matrix $E$ such that
$J=C[E,I_{d^{\prime\prime}\times d^{\prime\prime}}]$. Since
$\det(JBAB^{T}J^{T})\neq 0$, we have that

(9.2) $\det([E,I_{d^{\prime\prime}\times
d^{\prime\prime}}]BAB^{T}[E,I_{d^{\prime\prime}\times
d^{\prime\prime}}]^{T})\neq 0.$

For any $\mathbb{t}=(t_{i,j})_{1\leq i\leq d^{\prime\prime},1\leq j\leq
d^{\prime}}\in\mathbb{F}_{p}^{d^{\prime}d^{\prime\prime}}$, let
$B(\mathbb{t})$ denote the $d^{\prime\prime}\times d^{\prime}$ matrix whose
$(i,j)$-th entry equals to $t_{i,j}$. Denote

$F(\mathbb{t}):=\det([B(\mathbb{t}),I_{d^{\prime\prime}\times
d^{\prime\prime}}]BAB^{T}[B(\mathbb{t}),I_{d^{\prime\prime}\times
d^{\prime\prime}}]^{T}).$

Clearly $F$ is a polynomial of $\mathbb{t}$ of degree $O_{d}(1)$, and $F$ is
not constant zero by (9.2). By Lemma A.4, if $p\gg_{d}1$, then the number of
$\mathbb{t}\in\mathbb{F}_{p}^{d^{\prime}d^{\prime\prime}}$ with
$F(\mathbb{t})=0$ is $O_{d}(p^{d^{\prime}d^{\prime\prime}-1})$.

Note that each $\mathbb{t}=(t_{i,j})_{1\leq i\leq d^{\prime\prime},1\leq j\leq
d^{\prime}}\in\mathbb{F}_{p}^{d^{\prime}d^{\prime\prime}}$ uniquely determines
a linear transformation
$\alpha\colon\mathbb{F}_{p}^{d^{\prime\prime}}\to\mathbb{F}_{p}^{d^{\prime}}$
such that $\alpha_{j}(e_{i})=t_{i,j}$, and vice versa. Fix any
$\mathbb{t}\in\mathbb{F}_{p}^{d^{\prime}d^{\prime\prime}}$ and let $\alpha$ be
the linear transformation induced by $\mathbb{t}$. Let $U$ be given by (9.1).
Then the rows of the matrix $[B(\mathbb{t}),I_{d^{\prime\prime}\times
d^{\prime\prime}}]B$ is a basis of $U$.

By Lemma A.1, $U\in\mathcal{B}^{\prime}$ if and only if $U\cap
U^{\perp_{M}}\neq\\{\mathbb{0}\\}$. It is not hard to check that this is
equivalent of saying that $F(\mathbb{t})=0$. Since the number of
$\mathbb{t}\in\mathbb{F}_{p}^{d^{\prime}d^{\prime\prime}}$ with
$F(\mathbb{t})=0$ is $O_{d}(p^{d^{\prime}d^{\prime\prime}-1})$, we have that
$|\mathcal{B}^{\prime}|=O_{d}(p^{d^{\prime}d^{\prime\prime}-1})$.

Fix $1\leq i\leq C$. Since $V_{i}\cap U=\\{\mathbb{0}\\}$, $V_{i}$ is uniquely
determined by a subspace $V^{\prime}_{i}$ of
$\mathbb{F}_{p}^{d^{\prime\prime}}$ of dimension at most $D$ and a linear
transformation $\beta\colon V^{\prime}_{i}\to\mathbb{F}_{p}^{d^{\prime}}$ such
that

$V_{i}=\text{span}_{\mathbb{F}_{p}}\Bigl{\\{}\sum_{j=1}^{d^{\prime}}\beta_{j}(x)b_{j}+\sum_{j=1}^{d^{\prime\prime}}x_{j}b^{\prime}_{j}\colon
x\in V^{\prime}_{i}\Bigr{\\}}.$

If $U\cap V_{i}\neq\\{\mathbb{0}\\}$, then there exists some nontrivial $x\in
V^{\prime}_{i}$ whose first nonzero entry is 1 such that $\alpha(x)=\beta(x)$,
where $\beta(x):=(\beta_{1}(x),\dots,\beta_{d^{\prime}}(x))$. For each
nontrivial $x\in V^{\prime}_{i}$ whose first nonzero entry is 1, completing
$x$ into a basis of $\mathbb{F}_{p}^{d^{\prime\prime}}$, it is not hard to see
that number of linear transformations
$\alpha\colon\mathbb{F}_{p}^{d^{\prime\prime}}\to\mathbb{F}_{p}^{d^{\prime}}$
with $\alpha(x)=\beta(x)$ is $p^{(d^{\prime\prime}-1)d^{\prime}}$. Since the
number of nontrivial $x\in V^{\prime}_{i}$ whose first nonzero entry is 1 is
at most $p^{D^{\prime}-1}$. We have that $|\mathcal{B}_{i}|\leq
p^{d^{\prime}d^{\prime\prime}+(D-1-d^{\prime})}$.

Fix $1\leq j\leq K$. Let $P$ be the set of $n\in\mathbb{F}_{p}^{d}$ such that
$f_{j}(n)=(nA)\cdot n=0$. Since $f_{j}\notin J^{M}$, by Lemma A.5 and
Proposition A.7, we have $|P|=O_{d,s}(p^{d-2})$ since $d\geq 4$. For
$U\in\mathcal{B}\backslash\mathcal{B}^{\prime}$, let $P_{U}$ be the set of
$n\in\mathbb{F}_{p}^{d}$ such that $f_{j}(n)=(nA)\cdot n=(hA)\cdot n=0$ for
all $h\in U$. In other words, $P_{U}$ is the intersection of $P$ and the
subspace

$U^{\perp_{M}}:=\\{n\in\mathbb{F}_{p}^{d}\colon(hA)\cdot n=0\text{ for all
}h\in U\\}$

which is of dimension $d-\text{rank}(M|_{U})=d^{\prime}\geq 3$.

If $f_{j}\in J^{M}_{U}$ for some $U\in\mathcal{B}$, then $P_{U}$ is the
intersection of $V(M)$ and the subspace $U^{\perp}$. By Lemma A.5,
$|P_{U}|=p^{d-d^{\prime\prime}-1}(1+O(p^{-1/2}))$. Therefore, in order to
estimate $|\mathcal{B}^{\prime}_{j}|$, it suffices to study the number of
$U\in\mathcal{B}$ such that $|P_{U}|\gg_{\delta,d,s}p^{d-d^{\prime\prime}-1}$.

Fix $n\in P$. By (9.1), we may write
$n=\sum_{i=1}^{d^{\prime}}c_{i}b_{i}+\sum_{j=1}^{d^{\prime\prime}}c^{\prime}_{j}b^{\prime}_{j}$
for some $c_{i},c^{\prime}_{j}\in\mathbb{F}_{p}$. Note that the number of
$U\in\mathcal{B}$ such that $n\in U^{\perp_{M}}$ is equal to the number of
linear transformations
$\alpha\colon\mathbb{F}_{p}^{d^{\prime\prime}}\to\mathbb{F}_{p}^{d^{\prime}}$
such that

$((c_{1},\dots,c_{d^{\prime}},c^{\prime}_{1},\dots,c^{\prime}_{d^{\prime\prime}})\tilde{A})\cdot(\alpha_{1}(e_{j}),\dots,\alpha_{d^{\prime\prime}}(e_{j}),0,\dots,0,1,0,\dots,0)=0\text{
for all }1\leq j\leq d^{\prime\prime},$

where $\tilde{A}$ in the invertible matrix for $M$ under the basis
$b_{1},\dots,b^{\prime}_{d^{\prime\prime}}$, and the entry 1 appears in the
$(d^{\prime}+j)$-th coordinate. Suppose that

$(c_{1},\dots,c_{d^{\prime}},c^{\prime}_{1},\dots,c^{\prime}_{d^{\prime\prime}})\tilde{A}:=(a_{1},\dots,a_{d^{\prime}},a^{\prime}_{1},\dots,a^{\prime}_{d^{\prime\prime}}).$

If $(a_{1},\dots,a_{d^{\prime}})\neq\mathbb{0}$, then by the knowledge of
linear algebra, the number of $U\in\mathcal{B}$ such that $n\in U^{\perp_{M}}$
is $p^{(d^{\prime}-1)d^{\prime\prime}}$; if
$(a_{1},\dots,a_{d^{\prime}})=\mathbb{0}$ but
$(a^{\prime}_{1},\dots,a^{\prime}_{d^{\prime\prime}})\neq\mathbb{0}$, then
such $U$ does not exist. If
$(a_{1},\dots,a^{\prime}_{d^{\prime\prime}})=\mathbb{0}$, then the number of
$U\in\mathcal{B}$ such that $n\in U^{\perp_{M}}$ is $|\mathcal{B}|$. In
conclusion, we have that

$\sum_{n\in P}|\\{U\in\mathcal{B}\colon n\in U^{\perp_{M}}\\}|\leq|P|\cdot
p^{(d^{\prime}-1)d^{\prime\prime}}+|\mathcal{B}|=O_{d,s}(p^{d^{\prime}d^{\prime\prime}+d^{\prime}-2}).$

Therefore,

$\begin{split}\sum_{U\in\mathcal{B}}|P_{U}|=\sum_{U\in\mathcal{B}}|P\cap
U^{\perp_{M}}|=\sum_{n\in P}|\\{U\in\mathcal{B}\colon n\in
U^{\perp_{M}}\\}|=O_{d,s}(p^{d^{\prime}d^{\prime\prime}+d^{\prime}-2}),\end{split}$

which implies that the number of $U\in\mathcal{B}$ with
$|P_{U}|\gg_{\delta,d,s}p^{d-d^{\prime\prime}-1}$ is at most
$O_{d,s}(p^{d^{\prime}d^{\prime\prime}-1})$. So
$|\mathcal{B}^{\prime}_{j}|\leq O_{d,s}(p^{d^{\prime}d^{\prime\prime}-1})$ for
any $1\leq j\leq K$.

Combining the estimates of the cardinalities of $\mathcal{B}$,
$\mathcal{B}^{\prime}$, $\mathcal{B}_{i}$ and $\mathcal{B}^{\prime}_{j}$
above, since $d^{\prime}\geq D$ and $p\gg_{C,d,K,s}1$, we have
$|\mathcal{B}|>|\mathcal{B}^{\prime}|+\sum_{i=1}^{C}|\mathcal{B}_{i}|+\sum_{j=1}^{K}|\mathcal{B}^{\prime}_{j}|$.
This completes the proof. ∎

We are now ready to prove Theorem 1.5.

###### Proof of Theorem 1.5.

Throughout the proof we assume that $p\gg_{\delta,d}1$. Since
$d\geq(2s+16)(15s+453)$, we may write $d=d^{\prime}+d^{\prime\prime}$ for some
$d^{\prime}\geq 15s+453$ and
$d^{\prime\prime}\geq(2s+15)d^{\prime}\geq(2s+15)(15s+453)$. By assumption,
the $M$-energy of $(\xi_{1},\xi_{2},\xi_{3},\xi_{4})$ is at least
$\delta^{4}p^{3d}$. Using the Cauchy-Schwartz inequality (Theorem 5.6) twice
and the fact that $(\xi_{1},\xi_{2},\xi_{1},\xi_{2})$ has the same $M$-energy
as $(\xi_{1},\xi_{1},\xi_{2},\xi_{2})$, we have that the $M$-energy of
$(\xi_{1},\xi_{1},\xi_{1},\xi_{1})$ is $\gg_{\delta,d}p^{3d}$. From now on we
write $\xi:=\xi_{1}$ for convenience, and denote
$\tilde{\xi}(h)=(h,J^{M}_{h}+\xi(h))$ for all $h\in H$.

By Theorem 5.9, since $d\geq 2s+15$, there exists a subset $H_{1}$ of $H$ of
cardinality $\gg_{\delta,d}p^{d}$ such that
${\\#}_{\text{dd}}(\tilde{\xi}(H_{1})\hat{+}\tilde{\xi}(H_{1}))=O_{\delta,d}(1)$.
By Proposition 5.19, since $d\geq\max\\{s+32,69\\}$, there exists a subset
$H_{2}$ of $H_{1}$ of cardinality $\gg_{\delta,d}p^{d}$ such that
${\\#}_{\text{dd}}(8\tilde{\xi}(H_{2})\hat{-}8\tilde{\xi}(H_{2}))=O_{\delta,d}(1)$.
Since
$8\tilde{\xi}(H_{2})\hat{-}8\tilde{\xi}(H_{2})\subseteq\Gamma^{s}_{16}(M)$ and
$d\geq 28s+95$, by Proposition 6.6,
$\pi^{-1}(\mathbb{0})\cap(8\tilde{\xi}(H_{2})\hat{-}8\tilde{\xi}(H_{2}))$
admits an $(O_{\delta,d}(1),O_{\delta,d}(1),15s+450)$-classification for some
$(O_{\delta,d,s}(1)$, $O_{\delta,d,s}(1),15s+450)$-structure-obstacle pair
$(\mathcal{C}_{0},Y)$. By Lemma 9.1, since $d^{\prime}\geq
15s+450,d^{\prime\prime}\geq(s+15)d^{\prime}$, there exist
$(\mathcal{C}_{0},Y,M,d^{\prime},d^{\prime\prime})$-structure-obstacle
decompositions $(T_{i},U_{i})$, $1\leq i\leq s+16$ such that
$T_{1},\dots,T_{s+16}$ are linearly independent. By repeatedly using
Proposition 8.2, since $d^{\prime}\geq 15s+453$ and
$d^{\prime\prime}\geq\max\\{4s+23,35\\}$, there exist subset $H_{3}$ of
$H_{2}$ of cardinality $\gg_{\delta,d}p^{d}$ and maps $\eta_{i}\colon
H_{3}\to\text{HP}_{d}(s),1\leq i\leq s+16$ such that for all $1\leq i\leq
s+16$,

  * •

for all $h_{1},\dots,h_{16}\in H_{3}$ with
$h_{1}+\dots+h_{8}=h_{9}+\dots+h_{16}$, we have that

$\eta_{i}(h_{1})+\dots+\eta_{i}(h_{8})\equiv\eta_{i}(h_{9})+\dots+\eta_{i}(h_{16})\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{h_{1},\dots,h_{15}\\}+T_{i}};$

  * •

$\xi(h)\equiv\eta_{i}(h)\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{h\\}+T_{i}}$ for all $h\in H_{3}$.

Then for all $h_{1},\dots,h_{16}\in H_{3}$ with
$h_{1}+\dots+h_{8}=h_{9}+\dots+h_{16}$, and $1\leq i\leq s+16$, we have that

$\begin{split}&\quad\xi(h_{1})+\dots+\xi(h_{8})\equiv\eta_{i}(h_{1})+\dots+\eta_{i}(h_{8})\\\
&\equiv\eta_{i}(h_{9})+\dots+\eta_{i}(h_{16})\equiv\xi(h_{9})+\dots+\xi(h_{16})\mod
J^{M}_{\text{span}_{\mathbb{F}_{p}}\\{h_{1},\dots,h_{15}\\}+T_{i}}.\end{split}$

Since $T_{1},\dots,T_{s+16}$ are linearly independent and $d\geq
37+2(s+6)(d^{\prime}-1)$ (or equivalently
$d^{\prime\prime}\geq(2s+5)d^{\prime}+2s+25$), by Proposition 3.6 (setting
$m=15$ and $r=d^{\prime}$), we have that

$\begin{split}\xi(h_{1})+\dots+\xi(h_{8})\equiv\xi(h_{9})+\dots+\xi(h_{16})\mod
J^{M}_{h_{1},\dots,h_{15}}\end{split}$

and so $\xi$ is a Freiman $M$-homomorphism of order 16 on $H_{3}$.

Let $0<c<1$ be a universal constant to be chosen later. Since
$d\geq\max\\{4s+19,35\\}$, there exist $0<\rho=\rho(\delta,d)<1/4$, a
homogeneous proper generalized arithmetic progression

$P=\\{x_{1}v_{1}+\dots+x_{D}v_{D}\colon
x_{i}\in\mathbb{Z}\cap(-L_{i},L_{i}),1\leq i\leq D\\}$

in $\mathbb{F}_{p}^{d}$ of rank $D=O_{\delta,d}(1)$ and cardinality
$\gg_{\delta,d}p^{d}$, a set $S\subseteq\hat{\mathbb{F}_{p}^{d}}$ of
cardinality $D^{\prime}=O_{\delta,d}(1)$, and a Freiman $M$-homomorphism of
order 4 $\omega\colon P\to\text{HP}_{d}(s)$ satisfying the conclusions of
Proposition 7.2:

  1. (i)

$B(S,c\rho)\subseteq P(c)\subseteq P\subseteq B(S,1/4)\subseteq
2H_{3}-2H_{3}$;

  2. (ii)

For all $h\in P$, the set $R(H_{3},h):=\\{(h_{1},h_{2},h_{3},h_{4})\in H\colon
h_{1}+h_{2}-h_{3}-h_{4}=h\\}$ is of cardinality $\gg_{\delta,d}p^{3d}$;

  3. (iii)

there exists $H_{4}\subseteq H_{3}$ with $|H_{4}|\gg_{\delta,d}p^{d}$ such
that $2H_{4}-2H_{4}\subseteq P(c)$;

  4. (iv)

the vectors $(\\{\alpha\cdot v_{i}\\})_{\alpha\in
S}\in\mathbb{R}^{D^{\prime}},1\leq i\leq D$ are linearly independent over
$\mathbb{R}$;

  5. (v)

for all $h_{1},h_{2},h_{3},h_{4}\in H_{3}$ with $h_{1}+h_{2}-h_{3}-h_{4}\in
P$, we have

(9.3)
$\xi(h_{1})+\xi(h_{2})-\xi(h_{3})-\xi(h_{4})\equiv\omega(h_{1}+h_{2}-h_{3}-h_{4})\mod
J^{M}_{h_{1},h_{2},h_{3},h_{4}};$

  6. (vi)

for all $h_{1},h_{2},h_{3},h_{4}\in P$ with $h_{1}+h_{2}=h_{3}+h_{4}$, we have

$\omega(h_{1})+\omega(h_{2})\equiv\omega(h_{3})+\omega(h_{4})\mod
J^{M}_{h_{1},h_{2},h_{3}},$

i.e. the map $\omega\colon P\to\text{HP}_{d}(s)$ is a Freiman $M$-homomorphism
of order 4.

By Theorem 4.3, since $d\geq\max\\{s+10,11\\}$, for an appropriately chosen
$0<c\leq 1$ depending only on $s$, there exists a locally linear map $T\colon
P(c)\to\text{HP}_{d}(s)$ such that $\omega(u)\equiv T(u)\mod J^{M}_{u}$ for
all $u\in P(c)$.

Our next goal is to provide an explicit formula for the locally linear map
$T$. Suppose that

$T(x_{1}v_{1}+\dots+x_{D}v_{D})=u_{0}+x_{1}u_{1}+\dots+x_{D}u_{D}\text{ for
all }x_{i}\in\mathbb{Z}\cap(-cL_{i},cL_{i}),1\leq i\leq D$

for some $u_{0},\dots,u_{D}\in\text{HP}_{d}(s)$. We may naturally extend $T$
to a locally linear map on $P$ by setting

$T(x_{1}v_{1}+\dots+x_{D}v_{D})=u_{0}+x_{1}u_{1}+\dots+x_{D}u_{D}\text{ for
all }x_{i}\in\mathbb{Z}\cap(-L_{i},L_{i}),1\leq i\leq D.$

For convenience we also denote this map by $T$. Let $\Phi\colon
P\to\mathbb{R}^{D^{\prime}}$ be the map given by

$\Phi(x):=(\\{\alpha\cdot x\\})_{\alpha\in S}.$

Since $P\subseteq B(S,\rho)$, $\Phi(P)$ lies inside
$[-\rho,\rho]^{D^{\prime}}$. Since $\rho<1/4$, it is easy to check that

$\Phi(x_{1}v_{1}+\dots+x_{D}v_{D})=x_{1}\Phi(v_{1})+\dots+x_{D}\Phi(v_{D})\text{
for all }x_{i}\in(-L_{i},L_{i}),1\leq i\leq D.$

Claim. For all $1\leq i\leq D$, there exists
$w_{i}=(w_{i,1},\dots,w_{i,D^{\prime}})=(p_{i,1}/q_{i},\dots,p_{i,D^{\prime}}/q_{i})\in\mathbb{Q}^{D^{\prime}}$
for some $p_{i,j},q_{i}\in\mathbb{Z}$ with $|q_{i}|=O_{\delta,d}(1)$ such that
$w_{i}\cdot\Phi(v_{i})=1$ and $w_{i}\cdot\Phi(v_{j})=0$ for all $j\neq i$.

Since $\Phi(v_{i}),1\leq i\leq D$ are linearly independent over $\mathbb{R}$,
it is easy to see the existences of $w_{i}\in\mathbb{Q}^{D^{\prime}}$ such
that $w_{i}\cdot\Phi(v_{i})=1$ and $w_{i}\cdot\Phi(v_{j})=0$ for all $j\neq
i$. The difficulty of the claim is to bound the value of $q_{i}$.

Since $\Phi(v_{i}),1\leq i\leq D$ are linearly independent over $\mathbb{R}$
and $P$ is a proper generalized arithmetic progression, the $D$-dimensional
volume of the convex hull of $\Phi(P)$ as a subset of
$\mathbb{R}^{D^{\prime}}$ is at most $1/2^{D}$ (since it lies inside
$[-1/4,1/4]^{D^{\prime}}$). So the $D$-dimensional volume of $D$-dimensional
cube in $\mathbb{R}^{D^{\prime}}$ generated by $p\Phi(v_{i}),1\leq i\leq D$ is
at most $\frac{p^{d}\text{vol}(\Phi(P))}{|P|}=O_{\delta,d}(1)$. By the Cauchy-
Binet formula, there exists a $D\times D$ sub-matrix $B$ of the $D\times
D^{\prime}$ real matrix $(p\Phi(v_{i}))_{1\leq i\leq D}$ (where each
$\Phi(v_{i})$ is viewed as a $D^{\prime}$-dimensional horizontal vector) such
that $0<\det(B)=O_{\delta,d}(1)$. Since
$p\Phi(v_{i})\in\mathbb{Z}^{D^{\prime}}$, the claim follows from the knowledge
of linear algebra.

Let $w_{1},\dots,w_{D}$ be given by the claim. Then

$\Phi(x_{1}v_{1}+\dots+x_{D}v_{D})\cdot
w_{i}=(x_{1}\Phi(v_{1})+\dots+x_{D}\Phi(v_{D}))\cdot w_{i}=x_{i}.$

Then for all $x=x_{1}v_{1}+\dots+x_{D}v_{D}\in P$, we have that

$T(x)=u_{0}+x_{1}u_{1}+\dots+x_{D}u_{D}=u_{0}+\sum_{i=1}^{D}(\Phi(x)\cdot
w_{i})u_{i}.$

Enumerate $S=\\{\alpha_{1},\dots,\alpha_{D^{\prime}}\\}$ and write
$w_{i}=(w_{i,1},\dots,w_{i,D^{\prime}})$ for some $w_{i,j}\in\mathbb{Q}$. Fix
$m\in\mathbb{N}^{d}$ with $|m|=s$, and let
$T_{m}(x),u_{i,m}(x)\in\mathbb{F}_{p}$ be the $n^{m}$ coefficients of the
polynomials $T(x)(n)$ and $u_{i}(x)(n)$. Let $T^{\prime}_{m}\colon
P(c)\to\mathbb{Z}/p$ be the map given by
$T^{\prime}_{m}(x)=\frac{1}{p}\tau\circ T_{m}(x)$. Then

$\begin{split}&\quad
T^{\prime}_{m}(x)=\frac{1}{p}\tau(u_{0,m})+\frac{1}{p}\sum_{i=1}^{D}(\Phi(x)\cdot
w_{i})\tau(u_{i,m})\\\
&=\frac{1}{p}\tau(u_{0,m})+\frac{1}{p}\sum_{i=1}^{D}(\sum_{j=1}^{D^{\prime}}\\{\alpha_{j}\cdot
x\\}w_{i,j})\tau(u_{i})=\frac{1}{p}\tau(u_{0,m})+\frac{1}{p}\sum_{j=1}^{D^{\prime}}\\{\alpha_{j}\cdot
x\\}r_{j,m},\end{split}$

where $r_{j,m}:=\sum_{i=1}^{D}w_{i,j}\tau(u_{i,m})\in\mathbb{Q}$. By the
claim, there exists $L=O_{\delta,d}(1)$ such that $r_{j,m}=r^{\prime}_{j,m}/L$
for some $r^{\prime}_{j,m}\in\mathbb{Z}$ for all $1\leq j\leq D^{\prime}$ and
$m\in\mathbb{N}^{d}$. Since $p>L$, there exists $L^{\ast}\in\mathbb{N}$ such
that $LL^{\ast}\equiv 1\mod p^{2}\mathbb{Z}$. Let

$T^{\prime\prime}_{m}(x):=\frac{1}{p}\tau(u_{0,m})LL^{\ast}+\frac{1}{p}\sum_{j=1}^{D^{\prime}}\\{\alpha_{j}\cdot
x\\}r^{\prime}_{j,m}L^{\ast}.$

Since $\\{\alpha_{j}\cdot x\\}\in\mathbb{Z}/p$, we have that

$T^{\prime}_{m}(x)-T^{\prime\prime}_{m}(x)=\Bigl{(}\frac{L}{p}\tau(u_{0,m})+\frac{1}{p}\sum_{j=1}^{D^{\prime}}\\{\alpha_{j}\cdot
x\\}r^{\prime}_{j,m}\Bigr{)}\frac{(1-L^{\ast}L)}{L}\in\mathbb{Z}/L.$

On the other hand, since $T^{\prime}_{m}(x)\in\mathbb{Z}/p$, we have that
$T^{\prime\prime}_{m}(x)=LL^{\ast}T^{\prime}_{m}(x)\in\mathbb{Z}/p$. So
$T^{\prime}_{m}(x)-T^{\prime\prime}_{m}(x)\in(\mathbb{Z}/p)\cap(\mathbb{Z}/L)=\mathbb{Z}$.
Therefore, letting

$T^{\prime\prime}(x)(n):=\sum_{m\in\mathbb{N}^{d},|m|=s}T^{\prime\prime}_{m}(x)n^{m},$

we have that $T^{\prime}(x)\equiv T^{\prime\prime}(x)\mod\mathbb{Z}$, and thus

$T(x)=\iota\circ\tau\circ
T(x)=\iota(pT^{\prime}(x))=\iota(pT^{\prime\prime}(x)).$

Since $T^{\prime\prime}$ is a $p$-almost linear function on $P(c)$ of
complexity $D^{\prime}=O_{\delta,d}(1)$, we have that $T$ is an almost linear
function on $P(c)$ of complexity $O_{\delta,d}(1)$.

We are now ready to find out the expression for $\xi$. For all $h_{1},h_{2}\in
H_{4}$, since $h_{1}-h_{2}\in H_{4}-H_{4}\subseteq P(c)$, setting
$h_{2}=h_{3}=h_{4}$ in (9.3), we have

$\xi(h_{1})-\xi(h_{2})\equiv T(h_{1}-h_{2})\mod J^{M}_{h_{1},h_{2}}.$

Since $\\{\alpha\\}+\\{\beta\\}-\\{\alpha+\beta\\}\in\\{0,1\\}^{d}$ for all
$\alpha,\beta\in\mathbb{R}^{d}$ and $T$ is an almost linear function on $P(c)$
of complexity $O_{\delta,d}(1)$, we may find a set $\Omega\in\mathbb{R}^{d}$
of cardinality $O_{\delta,d}(1)$ such that
$T(h_{1}-h_{2})-(T(h_{1})-T(h_{2}))\in\Omega$ for all $h_{1},h_{2}\in H_{4}$.
So writing $\theta:=\xi-T$, we have that

$\theta(h_{1})-\theta(h_{2})\equiv g(h_{1},h_{2})\mod J^{M}_{h_{1},h_{2}}$

for some $g(h_{1},h_{2})\in\Omega$ for all $h_{1},h_{2}\in H_{4}$.

We need to use the intersection method. Since $|H_{4}|\gg_{\delta,d}p^{d}$ and
$d\geq s+3$, we may find some linearly independent $h_{1},\dots,h_{s+3}\in
H_{4}$. By the Pigeonhole principle, there exists a subset $H_{5}$ of $H_{4}$
with $|H_{5}|\gg_{\delta,d}p^{d}$ such that for all $h\in H_{5}$ and $1\leq
i\leq s+3$, $g(h,h_{i})$ takes the same value $g(h_{i})$. Then for all
$h,h^{\prime}\in H_{5}$,

$\theta(h)-\theta(h^{\prime})\equiv(\theta(h)-\theta(h_{i}))-(\theta(h^{\prime})-\theta(h_{i}))\equiv
g(h_{i})-g(h_{i})\equiv 0\mod J^{M}_{h,h^{\prime},h_{i}}$

for all $1\leq i\leq s+3$. By Proposition 3.6 (setting $m=2$ and $r=1$), since
$d\geq 11$, we have that

$\theta(h)\equiv\theta(h^{\prime})\mod J^{M}_{h,h^{\prime}}$

for all $h,h^{\prime}\in H_{5}$. This means that

$X:=\\{(\mathbb{0},J^{M}_{h}+\theta(h))\colon h\in
H_{5}\\}\subseteq\Gamma_{2}^{s}(M)$

is a weak equivalence class. Since $d\geq s+2$, it is impossible for all of
$h\in H_{5}$ to lie in a common subspace of $\mathbb{F}_{p}^{d}$ of dimension
$s+1$. By Proposition 5.4 (setting $k=2$), $X$ is a strong equivalence class
since $d\geq 9$. So there exists $g\in\text{HP}_{d}(s)$ such that
$g\equiv\theta(h)\mod J^{M}_{h}$ for all $h\in H_{5}$. In conclusion, we have
that

$\xi(h)\equiv T(h)+g\mod J^{M}_{h}$

for all $h\in H_{5}$. Since
$\\{\alpha\\}+\\{\beta\\}-\\{\alpha+\beta\\}\in\\{0,1\\}^{d}$ for all
$\alpha,\beta\in\mathbb{R}^{d}$ and $T$ is an almost linear function of
complexity $O_{\delta,d}(1)$, there exits a subset $H_{6}$ of $H_{5}$ with
$|H_{6}|\gg_{\delta,d}p^{d}$ such that $T$ is an almost linear Freiman
homomorphism on $H_{6}$. We are done. ∎

##  10\. Open questions

We collection of open questions in this section. Since the lower bound $d\geq
N(s)$ obtained in Theorem 1.5 is rather coarse, it is natural to ask:

######  Question 10.1.

What is the optimal lower bound for $d$ in Theorem 1.5?

The major cause of the coarse lower bound for $d$ in Theorem 1.5 is the error
term $X_{b}$ appearing in Proposition 6.3, which has nontrivial intersections
with some subspaces of $\mathbb{F}_{p}^{d}$ of rather large dimensions (see
also Remark 6.4). Therefore, it is natural to ask:

######  Question 10.2.

Can we make the set $X_{b}$ in Proposition 6.3 to be empty (or to have a small
cardinality)?

A positive answer the Question 10.2 will greatly improve the lower bound for
$d$ in Theorem 1.5. Recall that this question is connection to Conjecture 6.2,
which we restate below:

######  Question 10.3.

Let $d,k\in\mathbb{N}_{+}$, $s\in\mathbb{N}$, $p$ be a prime and
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form. Let $G$ be the relation graph of a subset of $\Gamma^{s}_{k}(M)$. If
$d\gg_{k,s}1$ and $p\gg_{d}1$, then is it true that
${\\#}_{\text{cc}}(G)=O_{d,{\\#}_{\text{dd}}(G)}(1)$?

Although we have demonstrated in Section 5 that shifted ideals enjoy many
additive combinatorial properties similar to the abelian group case, some
results in Section 5 are not proved in full generality. For example, one can
ask:

######  Question 10.4.

Does Proposition 5.15 hold for $B\subseteq\Gamma^{s}_{k}(M)$ (instead of
$B\subseteq\Gamma^{s}_{1}(M)$)? Can we upgrade Proposition 5.15 from a quasi
triangle inequality to a genial triangle inequality?

######  Question 10.5.

Does Conjecture 5.17 (an improvement of Proposition 5.18) hold?

Finally, it is interesting to ask about the connection between the
conventional independence number of a graph and the density dependent number
defined in this paper. This is Question 2.12 which we restate below:

######  Question 10.6.

For any graph, is the independent number equal to ${\\#}_{\text{dd}}(G)$? If
not, then is the independent number bounded below by a constant depending on
${\\#}_{\text{dd}}(G)$?

##  Appendix A Basic properties for quadratic forms

In this appendix, we collect some results proved in [7] on quadratic forms
which is used in this paper.

###  A.1. The rank of quadratic forms

Let $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form
associated with the matrix $A$ and $V$ be a subspace of $\mathbb{F}_{p}^{d}$.
Let $V^{\perp_{M}}$ denote the set of
$\\{n\in\mathbb{F}_{p}^{d}\colon(mA)\cdot n=0\text{ for all }m\in V\\}$. A
subspace $V$ of $\mathbb{F}_{p}^{d}$ is _$M$ -isotropic_ if $V\cap
V^{\perp_{M}}\neq\\{\mathbb{0}\\}$. We say that a tuple $(h_{1},\dots,h_{k})$
of vectors in $\mathbb{F}_{p}^{d}$ is _$M$ -isotropic_ if the span of
$h_{1},\dots,h_{k}$ is an $M$-isotropic subspace. We say that a subspace or
tuple of vectors is _$M$ -non-isotropic_ if it is not $M$-isotropic.

######  Lemma A.1 (Proposition 4.8 of [7]).

Let $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form and $V$
be a subspace of $\mathbb{F}_{p}^{d}$ of co-dimension $r$, and
$c\in\mathbb{F}_{p}^{d}$.

  1. (i)

We have $\dim(V\cap V^{\perp_{M}})\leq\min\\{d-\text{rank}(M)+r,d-r\\}$.

  2. (ii)

The rank of $M|_{V+c}$ equals to $d-r-\dim(V\cap V^{\perp_{M}})$ (i.e.
$\dim(V)-\dim(V\cap V^{\perp_{M}})$).

  3. (iii)

The rank of $M|_{V+c}$ is at most $d-r$ and at least $\text{rank}(M)-2r$.

  4. (iv)

$M|_{V+c}$ is non-degenerate (i.e. $\text{rank}(M|_{V+c})=d-r$) if and only if
$V$ is not an $M$-isotropic subspace.

######  Lemma A.2 (Lemma 4.9 of [7]).

Let $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form, $V$ be a subspace of $\mathbb{F}_{p}^{d}$ of dimension $r$, and
$V^{\prime}$ be a subspace of $\mathbb{F}_{p}^{d}$ of dimension $r^{\prime}$.
Suppose that $\text{rank}(M|_{V^{\perp_{M}}})=d-r$. Then
$\text{rank}(M|_{(V+V^{\prime})^{\perp_{M}}})\geq d-r-2r^{\prime}$.

######  Lemma A.3 (Lemma 4.11 of [7]).

Let $d,k\in\mathbb{N}_{+}$, $p$ be a prime, and
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form.

  1. (i)

The number of tuples $(h_{1},\dots,h_{k})\in(\mathbb{F}_{p}^{d})^{k}$ such
that $h_{1},\dots,h_{k}$ are linearly dependent is at most $kp^{(d+1)(k-1)}$.

  2. (ii)

The number of $M$-isotropic tuples
$(h_{1},\dots,h_{k})\in(\mathbb{F}_{p}^{d})^{k}$ is at most
$O_{d,k}(p^{kd-1})$.

###  A.2. Some basic counting properties

We refer the readers to Section 1.2 for the notations used in this section.

######  Lemma A.4 (Lemma 4.10 of [7]).

Let $P\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p})$ be of degree at
most $r$. Then $|V(P)|\leq O_{d,r}(p^{d-1})$ unless $P\equiv 0$.

######  Lemma A.5 (Corollary 4.14 of [7]).

Let $d,r\in\mathbb{N},d\geq 1$ and $p$ be a prime number. Let
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic form and $V+c$ be
an affine subspace of $\mathbb{F}_{p}^{d}$ of co-dimension $r$.

  1. (i)

If $s:=\text{rank}(M|_{V+c})\geq 3$, then

$|V(M)\cap(V+c)|=p^{d-r-1}(1+O(p^{-\frac{s-2}{2}})).$

  2. (ii)

If $\text{rank}(M)-2r\geq 3$, then

$|V(M)\cap(V+c)|=p^{d-r-1}(1+O(p^{-\frac{1}{2}})).$

######  Lemma A.6 (Corollary 4.16 of [7]).

Let $d,r\in\mathbb{N}_{+}$ and $p$ be a prime number. Let
$M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a non-degenerate quadratic
form and $h_{1},\dots,h_{r}$ be linearly independent vectors. If $d-2r\geq 3$,
then

$|V(M)^{h_{1},\dots,h_{r}}|=p^{d-r-1}(1+O(p^{-\frac{1}{2}})).$

###  A.3. Irreducible properties for quadratic forms

######  Proposition A.7 (Lemma 6.1 and Proposition 6.3 of [7]).

Let $d\in\mathbb{N}_{+},s\in\mathbb{N}$ and $p$ be a prime such that
$p\gg_{d,s}1$. Let $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$ be a quadratic
form of rank at least 3. For any
$P\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p})$ of degree at most $s$,
either $|V(P)\cap V(M)|\leq O_{d,s}(p^{d-2})$ or $V(M)\subseteq V(P)$.

Moreover, if $V(M)\subseteq V(P)$, then $P=MR$ for some
$R\in\text{poly}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p})$ of degree at most
$s-2$.

######  Proposition A.8 (Corollary 6.4 of [7]).

Let $d,k\in\mathbb{N}_{+}$, $s\in\mathbb{N}$, $p\gg_{d,k,s}1$ be a prime
number, $P\in\text{poly}_{p}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p})$ be a
polynomial of degree at most $s$, $M\colon\mathbb{F}_{p}^{d}\to\mathbb{F}_{p}$
be a non-degenerate quadratic form, and
$h_{1},\dots,h_{k}\in\mathbb{F}_{p}^{d}$ be linearly independent. Let $V$ be
the span of $h_{1},\dots,h_{k}$. Suppose that
$\text{rank}(M|_{V^{\perp_{M}}})\geq 3$. Then either
$|V(M)^{h_{1},\dots,h_{k}}\cap V(P)|\leq O_{d,k,s}(p^{d-k-2})$ or
$V(M)^{h_{1},\dots,h_{k}}\subseteq V(P)$.

Moreover, if $V(M)^{h_{1},\dots,h_{k}}\subseteq V(P)$, then

$P(n)=M(n)P_{0}(n)+\sum_{i=1}^{k}(M(n+h_{i})-M(n))P_{i}(n)$

for some polynomials
$P_{0},\dots,P_{k}\in\text{poly}_{p}(\mathbb{F}_{p}^{d}\to\mathbb{F}_{p})$
with $\deg(P_{0})\leq s-2$ and $\deg(P_{i})\leq s-1,1\leq i\leq k$.

In particular, the conclusion of this corollary holds if $d\geq k+\dim(V\cap
V^{\perp_{M}})+3$, or if $d\geq 2k+3$.

## References

  * [1] A. Balog and E. Szemerédi.  A statistical theorem of set addition.  Combinatorica, 14:263–268, 1994.
  * [2] M. Chang.  On problems of Erdös and Rudin.  Journal of Functional Analysis, 207:444–460, 2004.
  * [3] B. Green and T. Tao.  An inverse theorem for the Gowers $\text{U}^{3}$-norm, with applications.  Proc. Edinburgh Math. Soc., 51:71–153, 2008.
  * [4] B. Green, T. Tao, and T. Ziegler.  An inverse theorem for the Gowers $\text{U}^{s+1}$-norm.  Ann. of Math., 176(2):1231–1372, 2012.
  * [5] H. Plünnecke.  Eigenschaften un Abschätzungen von Wirkingsfunktionen.  BMwF-GMD-22 Gesellschaft für Mathematik und Datenverarbeitung, 1969.
  * [6] I. Ruzsa.  An application of graph theory to additive number theory.  Scientia, Ser. A.(3):97–109, 1989.
  * [7] W. Sun.  Spherical higher order Fourier analysis over finite fields I: equidistribution for nilsequences.  arXiv: 2312.06651.
  * [8] W. Sun.  Spherical higher order Fourier analysis over finite fields III: a spherical Gowers inverse theorem.  arXiv: 2312.06636.
  * [9] W. Sun.  Spherical higher order Fourier analysis over finite fields IV: an application to the geometric Ramsey conjecture.  arXiv: 2312.06649.
  * [10] T. Tao and V. Vu.  Additive combinatorics.  Cambridge Stud. Adv. Math. 105, Cambridge Univ. Press, Cambridge, 2006.