# Listening Between the Lines:
Synthetic Speech Detection Disregarding Verbal Content

###### Abstract

Recent advancements in synthetic speech generation have led to the creation of
forged audio data that are almost indistinguishable from real speech. This
phenomenon poses a new challenge for the multimedia forensics community, as
the misuse of synthetic media can potentially cause adverse consequences.
Several methods have been proposed in the literature to mitigate potential
risks and detect synthetic speech, mainly focusing on the analysis of the
speech itself. However, recent studies have revealed that the most crucial
frequency bands for detection lie in the highest ranges (above 6000 Hz), which
do not include any speech content. In this work, we extensively explore this
aspect and investigate whether synthetic speech detection can be performed by
focusing only on the background component of the signal while disregarding its
verbal content. Our findings indicate that the speech component is not the
predominant factor in performing synthetic speech detection. These insights
provide valuable guidance for the development of new synthetic speech
detectors and their interpretability, together with some considerations on the
existing work in the audio forensics field.

Index Terms—  Audio Forensics, Synthetic Speech, Background Noise,
Explainability

##  1 Introduction

In the last few years, the scientific community has made significant
advancements in the synthetic speech generation field. It is now possible to
generate highly realistic speech tracks that mimic a target speaker’s voice
using commonplace devices and open-access tools that operate with minimal
computational resources. This progress proves advantageous in contexts like
human-machine interaction and accessibility for individuals with speech
disorders [1]. Nonetheless, the ability to generate synthetic speech also
introduces ethical concerns, particularly regarding its potential misuse for
malicious purposes [2]. This is the case of audio deepfakes, synthetic speech
signals produced through AI-driven technologies that can clone a target
speaker’s voice, making them utter statements they never made. The potential
risks associated with this phenomenon have prompted the multimedia forensics
community to address this concern actively, working on developing systems
capable of verifying the authenticity of audio files [3]. Several synthetic
speech detection techniques have been introduced employing a diverse range of
approaches, including end-to-end methods [4, 5], and systems based on the
analysis of acoustic [6], and semantic features [7, 8]. The proposed detectors
leverage cutting-edge technologies in the AI field and show remarkable
performance, especially in controlled scenarios. However, due to their data-
driven nature, they are often used as black-boxes with limited
interpretability. This constraint restricts their application in real-world
scenarios where a comprehensive understanding of what is driving the detection
process is essential.

To overcome this limitation, the scientific community has increased its
attention towards Explainable AI (XAI), aiming to understand the critical
elements in an audio track that influence the predictions of a synthetic
speech detector. For instance, the authors of [9] and [10] employ the SHapley
Additive exPlanations (SHAP) method to analyze the artifacts produced by
synthetic speech generators, while those of [11] and [12] utilize GradCAM and
LIME algorithms to gain insight into the decision-making process of synthetic
speech detectors, respectively. Finally, other studies [13], have focused on
explaining the results obtained using specific audio features, focusing on
different frequency bands and speech formants.

In our latest study [14], we investigated which are the most critical
frequency bands to perform synthetic speech detection. We found that the most
significant one is located in the highest frequency range (above
$6000\text{\,}\mathrm{Hz}$), characterized by the absence of any verbal
content and comprising only background noise. This insight is crucial, as many
detectors are specifically designed to analyze speech nuances while
disregarding the noise component. Realizing that the meaningful content for
this task lies in the background allows us to develop detectors that are
informed of this fact, resulting in enhanced performance and reliability.
These findings are also motivated by the fact that the analysis of high-
frequency components is a well-established technique in multimedia forensics,
with this approach already being used for image processing and image splicing
detection [15]. However, to our knowledge, this methodology has never been
employed in the synthetic speech detection field, where its potential value
could be considerable.

In this paper we aim to deepen this investigation. Starting from an input
speech track, we separate its verbal and background noise components and use
them individually for synthetic speech detection. Our findings indicate that
analyzing the background noise alone leads to better classification results
across diverse scenarios. Furthermore, we show how the results obtained are
not significant only for one specific noise extractor but can also be extended
to other methods, providing valuable insights into the generalization
capabilities of the proposed method.

##  2 Synthetic Speech Detection

In this paper we consider the problem of synthetic speech detection and
investigate whether the signal components that are most relevant for this task
are predominantly present in the speech or the background noise. In our
previous work [14], we showed that the most crucial frequency band for
detection is the highest one (above $6000\text{\,}\mathrm{Hz}$), which does
not include any verbal content. Starting from these results, we aim to study
whether it is possible to discriminate between real and fake speech signals
solely by looking at the background noise component and disregarding any
verbal information. Previous studies in the field have explored synthetic
speech detection by analyzing only the silent portions of the speech signal,
leading to considerations regarding what we really need to analyze in an audio
track [16, 17].

The rationale behind this work is that synthetic speech generators have been
trained to replicate the voice of a target speaker, producing high-quality
results on this task. However, due to their emphasis on this specific element,
they may overlook the synthesis of other aspects of the signal, such as
background noise and high-frequency components, which may include some
artifacts. Therefore, we can leverage this aspect and perform a more accurate
synthetic speech detection by focusing only on these components.

###  2.1 Problem Formulation

The synthetic speech detection problem is formally defined as follows. Given a
discrete-time input speech signal $\mathbf{x}$ sampled with sampling frequency
$f_{\text{s}}$, the goal is to build a detector $\mathcal{D}$ able to predict
the class $y\in\\{Real,Fake\\}$ associated to $\mathbf{x}$. Here, Real
indicates authentic speech, while Fake means that the signal has been
generated through any speech synthesis technique. We represent the speech
signal $\mathbf{x}$ as the sum of two different components, such as

$\mathbf{x}=\mathbf{s}+\mathbf{n},$ (1)

where $\mathbf{s}$ and $\mathbf{n}$ are the speech (or verbal) and noise
components present in the audio track, respectively.

Our proposed approach extends beyond the standard synthetic speech detection
on the entire signal $\mathbf{x}$. Instead, we train three distinct synthetic
speech detectors, denoted as $\mathcal{D}_{\mathbf{x}}$,
$\mathcal{D}_{\mathbf{s}}$, and $\mathcal{D}_{\mathbf{n}}$, which take as
input the signals $\mathbf{x}$, $\mathbf{s}$, and $\mathbf{n}$, respectively,
and output an estimate of the class $y$ of the signal based on the input they
receive. We aim to assess and compare the performance of the three detectors
and determine which one leads to the most accurate predictions. Our findings
will contribute to a deeper understanding of synthetic speech generation and
detection tasks, helping the development of more accurate detectors in the
future.

###  2.2 Proposed Pipeline

The proposed pipeline consists of two distinct steps. The first one is the
noise extraction stage and involves the speech separator module $\mathcal{S}$,
which extracts the estimates of the two components $\mathbf{s}$ and
$\mathbf{n}$ from the input signal $\mathbf{x}$, such that

$\mathbf{s},\mathbf{n}=\mathcal{S}(\mathbf{x}).$ (2)

With a slight abuse of notation, since we do not have access to the original
verbal and noise components of the signal $\mathbf{x}$, we refer to their
estimates as $\mathbf{s}$ and $\mathbf{n}$. The second step is the synthetic
speech detection stage and involves the detectors $\mathcal{D}_{i}$, which
takes as input the signal $i$ and outputs the class estimate $\hat{y}_{i}$,
such that

$\hat{y}_{i}=\mathcal{D}_{i}(i),$ (3)

with $i\in\\{\mathbf{x},\mathbf{s},\mathbf{n}\\}$. We highlight that each
detector $\mathcal{D}_{i}$ is trained and tested only on one type of signal
(i.e., original $\mathbf{x}$, speech-only $\mathbf{s}$, noise-only
$\mathbf{n}$). Figure 1 shows a block diagram of the proposed pipeline.

Fig. 1: Pipeline of the proposed method.

####  2.2.1 Noise Extraction Stage

The noise extraction stage of the pipeline receives as input the original
signal $\mathbf{x}$ and outputs its speech and noise components $\mathbf{s}$
and $\mathbf{n}$. We implement this stage using two different approaches to
evaluate the generalization capabilities of the proposed method and
demonstrate that it is not reliant on a specific noise extractor system.

The first noise extractor we consider is the speech enhancement model
introduced in [18]. This follows an encoder-decoder architecture with skip
connections that return a speech-enhanced version of the input signal. We
utilize a version of the model trained on the Deep Noise Suppression (DNS)
Challenge dataset, presented at Interspeech 2020 [19]. We refer to this model
as Demucs $\mathcal{S}_{\text{DMCS}}$. The second approach we consider is
SepFormer, a speech separation model presented in [20]. This system is trained
on the WHAMR! dataset [21] to separate speech from background noise. Both the
models $\mathcal{S}_{\text{DMCS}}$ and $\mathcal{S}_{\text{SF}}$ take as input
the original signal $\mathbf{x}$ and directly output the two components
$\mathbf{s}$ and $\mathbf{n}$, as indicated in Equation 2.

####  2.2.2 Synthetic Speech Detection Stage

The synthetic speech detector $\mathcal{D}_{i}$ we consider in this study is
RawNet2 [4]. This is an end-to-end neural network for audio deepfake detection
that directly operates on raw waveform inputs. Originally presented in the
ASVspoof 2019 challenge [22] and included as a baseline in the ASVspoof 2021
challenge [23], RawNet2 features Sinc filters from SincNet [24] followed by
two Residual Blocks with skip connections on a GRU layer, aiming to extract
frame-level representations of the input signal. For our study, we use the
exact architecture proposed in the original paper, with the only modification
being the input size of the network from $4\text{\,}\mathrm{s}$ to
$2\text{\,}\mathrm{s}$. This adjustment makes the model more suitable to
address the latest challenges in synthetic speech detection, where there is a
need to have more punctual predictions of the authenticity of the signal over
time to detect counterfeit media that interleave real and fake speech
segments.

We consider the same model for all three detectors
($\mathcal{D}_{\mathbf{x}}$, $\mathcal{D}_{\mathbf{s}}$ and
$\mathcal{D}_{\mathbf{n}}$), with the only distinctions being the input signal
and the corresponding training strategy. This choice ensures that the
differences in performance of the models depend solely on the content of the
signals and allows us to understand which of them contains more relevant
information for the synthetic speech detection task.

Fig. 2: Spectrograms of the signals x (left), s (center) and n (right) of an
example track. The two tracks s and n have been computed using the
$\mathcal{S}_{\text{DMCS}}$ model.

##  3 Experimental Setup

During all the experiments, we use RawNet2 as synthetic speech detector,
following the implementation proposed in [4]. As anticipated in Section 2.2.2,
we reduce the input length of the network from $4\text{\,}\mathrm{s}$ to
$2\text{\,}\mathrm{s}$, translating to a change from $64\,000$ to $32\,000$
samples, considering a sampling frequency equal to $f_{\text{s}}$ =
$16\text{\,}\mathrm{kHz}$. We follow the same training strategy for all
$\mathcal{D}_{\textbf{x}}$, $\mathcal{D}_{\textbf{s}}$ and
$\mathcal{D}_{\textbf{n}}$. The networks have been trained for $150$ epochs
with an early stopping of $15$ epochs, considering a batch size of $128$
samples and a learning rate of $10^{-4}$. We assumed Cross Entropy as loss
function with a label smoothing equal to $0.2$. During training, we balanced
each batch with equal samples for the Real and Fake classes.

The dataset used to train and test the models is ASVspoof 2019 [22], a speech
audio set created to develop antispoofing techniques for automatic speaker
verification. We consider the Logical Access (LA) partition of the dataset,
which contains both real and fake data generated with several synthesis
techniques. The speech generation algorithm employed in the training and
validation partitions of this dataset differs from the one utilized in the
test partition, allowing the testing of the synthetic speech detectors in an
open-set scenario.

To assess the generalization capabilities proposed approach, we test the
models also on other datasets released in the literature. These are ASVspoof
2021 [23], AISEC “In-the-Wild” [25], and FakeOrReal [26]. The reason why we do
so is to verify whether our findings are restricted to a single dataset or can
be generalized to more in the wild conditions. This is a crucial aspect in
multimedia forensics, where we want our detectors to be as performant as
possible even in conditions that are different from the ones seen during
training.

We also want to test the robustness of the proposed detectors against anti-
forensics attacks, i.e., operations applied to the signals to degrade their
quality and compromise the accuracy of deepfake detection systems. In
particular, we consider an MP3 compression attack, a processing operation that
is commonly applied to speech tracks on the web or social platforms. We also
want to test this particular attack because it directly affects the high-
frequency components of audio signals, potentially impacting the performance
of the proposed $\mathcal{D}_{\textbf{n}}$ detector. We simulate this attack
using the Python audiomentations library, considering three different
compression values (bitrate [$\mathrm{k}\mathrm{bit}\mathrm{/}\mathrm{s}$] =
[192, 128, 64]), applied prior to the noise extraction stage.

During all the experiments, we train and test the detector
$\mathcal{D}_{\mathbf{x}}$ on the original audio files released in the
datasets, while the detectors $\mathcal{D}_{\mathbf{s}}$ and
$\mathcal{D}_{\mathbf{n}}$ are trained on the signals $\mathbf{s}$ and
$\mathbf{n}$, extracted from $\mathbf{x}$ using one between the
$\mathcal{S}_{\text{DMCS}}$ and $\mathcal{S}_{\text{SF}}$ models presented in
Section 2.2.1. $\mathcal{D}_{\textbf{x}}$ also serves as a baseline for our
experiments, as it is a state-of-the-art detector trained and tested under the
same conditions for which it was originally designed.

##  4 Results

In this section, we evaluate the effectiveness of the proposed approach. We
aim to determine whether performing synthetic speech detection considering
only one of the two signal components, either $\mathbf{s}$ or $\mathbf{n}$,
leads to better results compared to using the original signal $\mathbf{x}$.
Figure 2 shows the spectrograms of the three signals, computed using
$\mathcal{S}_{\text{DMCS}}$ as noise extractor. We assess the performance of
the models across various conditions, investigating their generalization
capabilities on unseen data and robustness to MP3 compression.

Fig. 3: ROC curve showing the synthetic speech detection performances of
$\mathcal{D}_{\mathbf{x}}$, $\mathcal{D}_{\mathbf{s}}$ and
$\mathcal{D}_{\mathbf{n}}$ tested on the ASVspoof 2019 dataset, considering
$\mathcal{S}_{\text{DMCS}}$ as noise extractor.

Detection Results. In our initial experiment, we evaluate the performance of
the proposed pipeline by training and testing the detectors on the ASVspoof
2019 dataset. Figure 3 show the results of this experiment through Receiver
Operating Characteristic (ROC) curves, considering $\mathcal{S}_{\text{DMCS}}$
as noise extractor. $\mathcal{D}_{\mathbf{n}}$ consistently outperforms the
other two detectors, showcasing an Area Under the Curve (AUC) improvement of
$0.06$ compared to the baseline $\mathcal{D}_{\mathbf{x}}$.

As outlined in Section 2, our analysis extends beyond a single noise
extractor. We explore two different approaches to illustrate that the obtained
results are not confined to a specific model but rather can be generalized.
Table 1 presents the AUC and balanced accuracy values of the detectors when
considering both $\mathcal{S}_{\text{DMCS}}$ and $\mathcal{S}_{\text{SF}}$ as
noise extractors. In both cases, the best results are achieved by employing
the detector $\mathcal{D}_{\mathbf{n}}$ that works only on the background
noise signal n. This supports our initial hypothesis, emphasizing that the
primary information for synthetic speech detection predominantly resides in
the background noise rather than the speech itself.

Given that the pipeline featuring $\mathcal{S}_{\text{DMCS}}$ achieves
superior results, we exclusively present the results obtained with this model
in the following experiments.

Table 1: AUC and Balanced Accuracy values of $\mathcal{D}_{\mathbf{x}}$, $\mathcal{D}_{\mathbf{s}}$ and $\mathcal{D}_{\mathbf{n}}$ tested on the ASVspoof 2019 dataset, considering both $\mathcal{S}_{\text{DMCS}}$ and $\mathcal{S}_{\text{SF}}$ as noise extractors. | $\mathcal{S}_{\text{DMCS}}$ |  | $\mathcal{S}_{\text{SF}}$
---|---|---|---
| AUC | B. ACC. |  | AUC | B. ACC.
$\mathcal{D}_{\mathbf{x}}$ | $0.87$ | $0.82$ |  | $0.87$ | $0.82$
$\mathcal{D}_{\mathbf{s}}$ | $0.86$ | $0.81$ |  | $0.89$ | $0.79$
$\mathcal{D}_{\mathbf{n}}$ | $0.93$ | $0.83$ |  | $0.90$ | $0.82$

Generalization Capabilities. Given the results of the proposed approach when
tested on ASVspoof 2019, we want to extend the analysis by assessing its
performance on datasets other than the one seen in training. This experiment
aims to investigate whether our findings are dataset-specific or can be
generalized. Table 2 presents the obtained results employing balanced accuracy
as a metric. To compute these scores, we threshold the softmax output of the
network at $0.5$. In this experiment, $\mathcal{D}_{\mathbf{x}}$ serves as a
baseline, representing the state-of-the-art without influence from our
proposed method. In contrast, the performances of $\mathcal{D}_{\mathbf{s}}$
and $\mathcal{D}_{\mathbf{n}}$ models represent the outcomes of our pipeline.

Across all datasets examined, the $\mathcal{D}_{\mathbf{n}}$ model
consistently outperforms the other two, exhibiting accuracy improvements
ranging from $2$% in the case of ASVspoof 2021 to $35$% when considering the
FakeOrReal dataset, compared to the baseline $\mathcal{D}_{\mathbf{x}}$. While
acknowledging that the performance of $\mathcal{D}_{\mathbf{x}}$ may not be
exceptionally high, it represents the state-of-the-art benchmark and, for this
reason, we assume it as suitable for comparison. Given that our proposed
pipeline addresses only track preprocessing without impacting the detector
itself, we expect that our results can also be generalized to more performing
detectors.

Finally, the performance of $\mathcal{D}_{\mathbf{x}}$ and
$\mathcal{D}_{\mathbf{s}}$ are comparable, suggesting that the
$\mathcal{D}_{\mathbf{x}}$ detector relies its predictions primarily on the
verbal content of the signal.

Fig. 4: Balanced accuracy values scored by $\mathcal{D}_{\mathbf{x}}$,
$\mathcal{D}_{\mathbf{s}}$ and $\mathcal{D}_{\mathbf{n}}$ tested on the
ASVspoof 2019 dataset under varying MP3 compression bitrates.

Compression Robustness. As a final experiment, we test the robustness of the
proposed pipeline against anti-forensics attacks. Synthetic speech signals
typically preserve traces and artifacts from their generators, which can be
exploited for their discrimination. However, post-processing operations may
distort or eliminate these traces, making the detection process more
challenging. When such post-processing operations are employed intentionally
to inhibit forensic detectors, we refer to them as anti-forensics attacks. We
consider MP3 compression as an attack and examine its impact on detector
performance, testing the model on ASVspoof 2019 at various compression
bitrates.

Figure 4 shows the balanced accuracy values achieved in the considered cases.
$\mathcal{D}_{\mathbf{s}}$ proves to be the most robust method of the three,
exhibiting no tangible impact from the post-processing operation.
$\mathcal{D}_{\mathbf{x}}$ achieves acceptable results, with an accuracy drop
of only $3$%. In contrast, $\mathcal{D}_{\mathbf{n}}$ exhibits a notable
performance decrease, with a $15$% drop. This result is somehow expected, as
MP3 compression primarily affects the high frequencies and the non-speech
content, upon which $\mathcal{D}_{\mathbf{n}}$ bases its predictions. These
results underscore the importance of considering such factors in developing or
training synthetic speech detectors to prevent them from any bias.

Table 2: Balanced accuracy values scored by $\mathcal{D}_{\mathbf{x}}$, $\mathcal{D}_{\mathbf{s}}$ and $\mathcal{D}_{\mathbf{n}}$ tested on unseen datasets during training. | $\mathcal{D}_{\mathbf{x}}$ | $\mathcal{D}_{\mathbf{s}}$ | $\mathcal{D}_{\mathbf{n}}$
---|---|---|---
ASVspoof 2019 [22] | $0.82$ | $0.81$ | $0.83$
ASVspoof 2021 [23] | $0.72$ | $0.72$ | $0.73$
FakeOrReal [26] | $0.53$ | $0.54$ | $0.71$
AISEC ”In-the-Wild” [25] | $0.53$ | $0.53$ | $0.69$
ADD 2022 train [27] | $0.48$ | $0.44$ | $0.54$

Discussion. The obtained results provide a basis for comprehensive discussions
on multiple fronts. First, the superior performance of
$\mathcal{D}_{\mathbf{n}}$ compared to $\mathcal{D}_{\mathbf{s}}$ prompts
reflection about XAI in synthetic speech detection and the specific aspects of
the audio signals that the detectors analyze to that drive their predictions.
While common intuition might suggest that detectors primarily focus on verbal
content, our findings indicate this is not the case. Secondly, the consistency
of this trend across various datasets, combined with the limited
generalization capabilities of the detectors, makes us reflect on the quality
of the data and the models released in the state-of-the-art for synthetic
speech detection. This suggests the presence of potential dataset-specific
characteristics in the data or that the detectors may be prone to overfitting
on specific datasets, limiting their generalization capabilities. Finally, the
results of $\mathcal{D}_{\mathbf{n}}$ against anti-forensic attacks raise
concerns about the suitability of detectors that exclusively analyze specific
signal components for real-world scenarios. This leads to considerations about
the feasibility of implementing informed detectors capable of analyzing the
distinct components of the signal differently, extracting the most pertinent
information from each of them. In a broader context, we advocate for the
development of synthetic speech detectors under realistic conditions,
enhancing their generalization capabilities across various datasets and their
robustness against post-processed data. Prioritizing real-world applicability
is crucial for advancing the field and ensuring the practical effectiveness of
synthetic speech detection systems.

##  5 Conclusion

In this paper, we addressed the problem of synthetic speech detection and
investigated the possibility of performing this task by exclusively examining
the background component of the signal while disregarding its verbal content.
Utilizing two distinct noise extraction methods, we validated our initial
hypothesis and assessed its generalization capabilities and robustness to MP3
compression. The obtained results led to interesting considerations regarding
XAI in synthetic speech detection, the quality of state-of-the-art data, and
the approaches used in synthetic speech detectors. Future research will focus
on enhancing the pipeline’s robustness against anti-forensic attacks and
exploring more effective implementation approaches.

## References

  * [1] J. Yamagishi, C. Veaux, S. King, and S. Renals, “Speech synthesis technologies for individuals with vocal disabilities: Voice banking and reconstruction,” _Acoustical Science and Technology_ , vol. 33, no. 1, pp. 1–5, 2012.
  * [2] N. Y. Times, “‘A.I. Obama’ and Fake Newscaster: How A.I. Audio is Swarming TikTok,” https://www.nytimes.com/2023/10/12/technology/tiktok-ai-generated-voices-disinformation.html.
  * [3] L. Cuccovillo, C. Papastergiopoulos, A. Vafeiadis, A. Yaroshchuk, P. Aichroth, K. Votis, and D. Tzovaras, “Open challenges in synthetic speech detection,” in _IEEE International Workshop on Information Forensics and Security (WIFS)_ , 2022.
  * [4] H. Tak, J. Patino, M. Todisco, A. Nautsch, N. Evans, and A. Larcher, “End-to-end anti-spoofing with RawNet2,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2021.
  * [5] K. Ma, Y. Feng, B. Chen, and G. Zhao, “End-to-end dual-branch network towards synthetic speech detection,” _IEEE Signal Processing Letters_ , vol. 30, pp. 359–363, 2023.
  * [6] A. Hamza, A. R. R. Javed, F. Iqbal, N. Kryvinska, A. S. Almadhor, Z. Jalil, and R. Borghol, “Deepfake audio detection via mfcc features using machine learning,” _IEEE Access_ , vol. 10, pp. 134 018–134 028, 2022.
  * [7] E. Conti, D. Salvi, C. Borrelli, B. Hosler, P. Bestagini, F. Antonacci, A. Sarti, M. C. Stamm, and S. Tubaro, “Deepfake Speech Detection Through Emotion Recognition: a Semantic Approach,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2022.
  * [8] L. Attorresi, D. Salvi, C. Borrelli, P. Bestagini, and S. Tubaro, “Combining Automatic Speaker Verification and Prosody Analysis for Synthetic Speech Detection,” in _International Conference on Pattern Recognition (ICPR)_ , 2022.
  * [9] W. Ge, J. Patino, M. Todisco, and N. Evans, “Explaining deep learning models for spoofing and deepfake detection with SHapley Additive exPlanations,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022.
  * [10] W. Ge, M. Todisco, and N. Evans, “Explainable deepfake and spoofing detection: an attack analysis using SHapley Additive exPlanations,” _arXiv preprint arXiv:2202.13693_ , 2022.
  * [11] B. M. Halpern123, F. Kelly, R. van Son12, and A. Alexander, “Residual networks for resisting noise: analysis of an embeddings-based spoofing countermeasure,” in _Speaker and Language Recognition Workshop (Odyssey)_ , 2020.
  * [12] B. Chettri, S. Mishra, B. L. Sturm, and E. Benetos, “Analysing the predictions of a CNN-based replay spoofing detection system,” in _IEEE Spoken Language Technology Workshop_ , 2018.
  * [13] H. Tak, J. Patino, A. Nautsch, N. Evans, and M. Todisco, “An explainability study of the constant Q cepstral coefficient spoofing countermeasure for automatic speaker verification,” in _Speaker and Language Recognition Workshop (Odyssey)_ , 2020.
  * [14] D. Salvi, P. Bestagini, and S. Tubaro, “Towards frequency band explainability in synthetic speech detection,” in _2023 31st European Signal Processing Conference (EUSIPCO)_. IEEE, 2023, pp. 620–624.
  * [15] D. Cozzolino, G. Poggi, and L. Verdoliva, “Splicebuster: A new blind image splicing detector,” in _IEEE International Workshop on Information Forensics and Security (WIFS)_. IEEE, 2015.
  * [16] N. M. Müller, F. Dieckmann, P. Czempin, R. Canals, K. Böttinger, and J. Williams, “Speech is silver, silence is golden: What do asvspoof-trained models really learn?” in _Conference of the International Speech Communication Association (INTERSPEECH)_ , 2021.
  * [17] D. Mari, F. Latora, and S. Milani, “The sound of silence: Efficiency of first digit features in synthetic audio detection,” in _2022 IEEE International Workshop on Information Forensics and Security (WIFS)_. IEEE, 2022, pp. 1–6.
  * [18] A. Défossez, G. Synnaeve, and Y. Adi, “Real time speech enhancement in the waveform domain,” in _Conference of the International Speech Communication Association (INTERSPEECH)_ , 2020.
  * [19] C. K. Reddy, V. Gopal, R. Cutler, E. Beyrami, R. Cheng, H. Dubey, S. Matusevych, R. Aichner, A. Aazami, S. Braun _et al._ , “The interspeech 2020 deep noise suppression challenge: Datasets, subjective testing framework, and challenge results,” in _Conference of the International Speech Communication Association (INTERSPEECH)_ , 2020.
  * [20] C. Subakan, M. Ravanelli, S. Cornell, M. Bronzi, and J. Zhong, “Attention is all you need in speech separation,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2021.
  * [21] M. Maciejewski, G. Wichern, and J. Le Roux, “Whamr!: Noisy and reverberant single-channel speech separation,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , May 2020.
  * [22] M. Todisco, X. Wang, V. Vestman, M. Sahidullah, H. Delgado, A. Nautsch, J. Yamagishi, N. Evans, T. Kinnunen, and K. A. Lee, “ASVspoof 2019: Future horizons in spoofed and fake audio detection,” in _Conference of the International Speech Communication Association (INTERSPEECH)_ , 2019.
  * [23] J. Yamagishi, X. Wang, M. Todisco, M. Sahidullah, J. Patino, A. Nautsch, X. Liu, K. A. Lee, T. Kinnunen, N. Evans _et al._ , “ASVspoof 2021: accelerating progress in spoofed and deepfake speech detection,” in _Automatic Speaker Verification and Spoofing Countermeasures Challenge_ , 2021.
  * [24] M. Ravanelli and Y. Bengio, “Speaker Recognition from Raw Waveform with SincNet,” in _IEEE Spoken Language Technology Workshop (SLT)_ , 2018.
  * [25] N. M. Müller, P. Czempin, F. Dieckmann, A. Froghyar, and K. Böttinger, “Does audio deepfake detection generalize?” in _Conference of the International Speech Communication Association (INTERSPEECH)_ , 2022.
  * [26] R. Reimao and V. Tzerpos, “For: A dataset for synthetic speech detection,” in _International Conference on Speech Technology and Human-Computer Dialogue (SpeD)_. IEEE, 2019.
  * [27] J. Yi, R. Fu, J. Tao, S. Nie, H. Ma, C. Wang, T. Wang, Z. Tian, Y. Bai, C. Fan _et al._ , “ADD 2022: the First Audio Deep Synthesis Detection Challenge,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2022.


* [49] C. Mairy, J. Hillairet, and D. Schumacher.  Energie de formation et concentration d’équilibre des lacunes dans le magnésium.  Acta Metall., 15(7):1258–1261, 1967.
  * [50] V. Michaud-Rioux, L. Zhang, and H. Guo.  RESCU: A real space electronic structure method.  J. Comput. Phys., 307:593–613, 2016.
  * [51] P. Motamarri.  Personal Commun., 2021.
  * [52] P. Motamarri, S. Das, S. Rudraraju, K. Ghosh, D. Davydov, and V. Gavini.  DFT-FE – A massively parallel adaptive finite-element code for large-scale density functional theory calculations.  Comput. Phys. Commun., 246:106853, 2020.
  * [53] P. Motamarri and V. Gavini.  Subquadratic-scaling subspace projection method for large-scale Kohn-Sham density functional theory calculations using spectral finite-element discretization.  Phys. Rev. B, 90:115127, Sep 2014.
  * [54] P. Motamarri and V. Gavini.  Configurational forces in electronic structure calculations using Kohn-Sham density functional theory.  Phys. Rev. B, 97:165132, Apr 2018.
  * [55] P. Motamarri, V. Gavini, K. Bhattacharya, and M. Ortiz.  Spectrum-splitting approach for Fermi-operator expansion in all-electron Kohn-Sham DFT calculations.  Phys. Rev. B, 95:035111, Jan 2017.
  * [56] P. Motamarri, M. Nowak, K. Leiter, J. Knap, and V. Gavini.  Higher-order adaptive finite-element methods for Kohn-Sham density functional theory.  J. Comput. Phys., 253:308–343, 2013.
  * [57] T. Mura.  Micromechanics of Defects in Solids.  Nijhoff Publishers, 1987.
  * [58] A. M. N. Niklasson.  Implicit purification for temperature-dependent density matrices.  Phys. Rev. B, 68:233104, Dec 2003.
  * [59] R. Parr and W. Yang.  Density-Functional Theory of Atoms and Molecules.  Oxford Univ. Press, 1994.
  * [60] J. Pask and N. Sukumar.  Partition of unity finite element method for quantum mechanical materials calculations.  Extreme Mech. Lett., 11:8–17, 2017.
  * [61] J. E. Pask, B. M. Klein, C. Y. Fong, and P. A. Sterne.  Real-space local polynomial basis for solid-state electronic-structure calculations: A finite-element approach.  Phys. Rev. B, 59:12352–12358, 1999.
  * [62] J. E. Pask and P. A. Sterne.  Finite element methods in ab initio electronic structure calculations.  Modell. Simul. Mater. Sci. Eng., 13(3):R71, 2005.
  * [63] R. Phillips.  Crystals, defects and microstructures: Modeling across scales.  Cambridge Univ. Press, 2001.
  * [64] M. Ponga, K. Bhattacharya, and M. Ortiz.  A sublinear-scaling approach to density-functional-theory analysis of crystal defects.  J. Mech. Phys. Solids, 95:530–556, oct 2016.
  * [65] M. Ponga, K. Bhattacharya, and M. Ortiz.  Large scale ab-initio simulations of dislocations.  In press, J. Comput. Phys., pages 1–25, 2020.
  * [66] P. P. Pratapa, P. Suryanarayana, and J. E. Pask.  Spectral Quadrature method for accurate $\mathcal{O}(N)$ electronic structure calculations of metals and insulators.  Comput. Phys. Commun., 200:96–107, 2016.
  * [67] E. Prodan and W. Kohn.  Nearsightedness of electronic matter.  PNAS, 102(33):11635–11638, 2005.
  * [68] W. Rudin.  Functional Analysis.  McGraw-Hill, Boston, 1991.
  * [69] N. D. Rufus, B. Kanungo, and V. Gavini.  Fast and robust all-electron density functional theory calculations in solids using orthogonalized enriched finite elements.  Phys. Rev. B, 104:085112, Aug 2021.
  * [70] A. Sharma, S. Hamel, M. Bethkenhagen, J. E. Pask, and P. Suryanarayana.  Real-space formulation of the stress tensor for $\mathcal{O}(N)$ density functional theory: Application to high temperature calculations.  J. Chem. Phys., 153(3):034112, 2020.
  * [71] D. Singh and L. Nordström.  Plane waves, pseudopotentials and the LAPW method.  Springer Verlag, 2006.
  * [72] S. P. Suetin.  Padé approximants and efficient analytic continuation of a power series.  Russian Math. Surv., 57(1):43, 2002.
  * [73] P. Suryanarayana.  On spectral quadrature for linear-scaling Density Functional Theory.  Chem. Phys. Lett., 584:182–187, 2013.
  * [74] P. Suryanarayana.  Optimized purification for density matrix calculation.  Chem. Phys. Lett., 555:291–295, 2013.
  * [75] P. Suryanarayana.  On nearsightedness in metallic systems for $\mathcal{O}(N)$ Density Functional Theory calculations: A case study on aluminum.  Chem. Phys. Lett., 679:146–151, 2017.
  * [76] P. Suryanarayana, K. Bhattacharya, and M. Ortiz.  Coarse-graining Kohn–Sham Density Functional Theory.  J. Mech. Phys. Solids, 61(1):38–60, 2013.
  * [77] P. Suryanarayana, P. P. Pratapa, A. Sharma, and J. E. Pask.  SQDFT: Spectral Quadrature method for large-scale parallel $\mathcal{O}(N)$ Kohn–Sham calculations at high temperature.  Comput. Phys. Commun., 224:288–298, 2018.
  * [78] E. B. Tadmor, M. Ortiz, and R. Phillips.  Quasicontinuum analysis of defects in solids.  Philos. Mag. A, 73(6):1529–1563, 1996.
  * [79] L. N. Trefethen.  Is Gauss quadrature better than Clenshaw–Curtis?  SIAM Rev., 50(1):67–87, 2008.
  * [80] L. N. Trefethen.  Approximation Theory and Approximation Practice, Extended Edition.  SIAM, 2019.
  * [81] E. Tsuchida and M. Tsukada.  Electronic-structure calculations based on the finite-element method.  Phys. Rev. B, 52:5573–5578, 1995.
  * [82] E. Tsuchida and M. Tsukada.  Adaptive finite-element method for electronic-structure calculations.  Phys. Rev. B, 54:7602–7605, Sep 1996.
  * [83] P. Tzanetakis, J. Hillairet, and G. Revel.  The formation energy of vacancies in aluminium and magnesium.  Phys. Status Solidi B, 75(2):433–439, 1976.
  * [84] M. Valiev, E. Bylaska, N. Govind, K. Kowalski, T. Straatsma, H. V. Dam, D. Wang, J. Nieplocha, E. Apra, T. Windus, and W. de Jong.  NWChem: A comprehensive and scalable open-source solution for large scale molecular simulations.  Comput. Phys. Commun., 181(9):1477–1489, 2010.
  * [85] W. Van Assche.  Padé and Hermite-Padé approximation and orthogonality.  Surv. in Approx. Theory, 2:61–91, 2006.
  * [86] D. Vanderbilt.  Soft self-consistent pseudopotentials in a generalized eigenvalue formalism.  Phys. Rev. B, 41:7892–7895, Apr 1990.
  * [87] A. Vehanen and K. Rytsölä.  Proceed. Int. School Phys., 1981.
  * [88] X.-C. Wang, T. Blesgen, K. Bhattacharya, and M. Ortiz.  A Variational Framework for Spectral Approximations of Kohn–Sham Density Functional Theory.  Arch. Ration. Mech. Anal., 221(2):1035–1075, 2016.
  * [89] C. Woodward.  First-principles simulations of dislocation cores.  Mater. Sci. Eng. A, 400?401:59?67, 2005.
  * [90] C. J. Wu, P. C. Myint, J. E. Pask, C. J. Prisbrey, A. A. Correa, P. Suryanarayana, and J. B. Varley.  Development of a multiphase beryllium equation of state and physics-based variations.  J. Phys. Chem. A, 125(7):1610–1636, 2021.
  * [91] Q. Xu, A. Sharma, and P. Suryanarayana.  M-SPARC: Matlab-simulation package for ab-initio real-space calculations.  SoftwareX, 11:100423, 2020.
  * [92] S. Yamakawa and S.-a. Hyodo.  Gaussian finite-element mixed-basis method for electronic structure calculations.  Phys. Rev. B, 71:035113, Jan 2005.
  * [93] S. Zhang, A. Lazicki, B. Militzer, L. H. Yang, K. Caspersen, J. A. Gaffney, M. W. Däne, J. E. Pask, W. R. Johnson, A. Sharma, et al.  Equation of state of boron nitride combining computation, modeling, and experiment.  Phys. Rev. B, 99(16):165103, 2019.
  * [94] X. Zhang, G. Lu, and W. Curtin.  Multiscale quantum/atomistic coupling using constrained density functional theory.  Phys. Rev. B, 87:054113, 2013.
  * [95] Y. Zhou, Y. Saad, M. L. Tiago, and J. R. Chelikowsky.  Parallel self-consistent-field calculations via Chebyshev-filtered subspace acceleration.  Phys. Rev. E, 74:066704, Dec 2006.
  * [96] Y. Zhou, Y. Saad, M. L. Tiago, and J. R. Chelikowsky.  Self-consistent-field calculations using Chebyshev-filtered subspace iteration.  J. Comput. Phys., 219(1):172–184, Nov. 2006.


††copyright: none

##  1\. Preliminaries

Need to make sure the tree is binary, and every leaf contains at least one
job.

##  2\. The Algorithm

###  2.1. Linear Program

The linear program is LP (1), which is given in Figure 1. In the LP, $x(i)$
denotes the number of time slots opened in node $i$, and $y(i,j)$ denotes the
amount of job $j$ that is scheduled in node $i$. In the LP, $\text{OPT}_{i}$
denotes the smallest number of slots to schedule the jobs in
$J(\mathsf{Des}(i))$.

(1) $\textbf{min}\quad\sum_{i\in[m]}x(i)\quad\textbf{s.t.}$

(2) $\displaystyle\sum_{i\in\mathsf{Des}(K(j))}y(i,j)$ $\displaystyle\geq
p_{j},$ $\displaystyle\forall j$ (3) $\displaystyle\sum_{j\in
J(Anc(i))}y(i,j)$ $\displaystyle\leq g\cdot x(i)$ $\displaystyle\forall i$ (4)
$\displaystyle x(i)$ $\displaystyle\leq L(i)$ $\displaystyle\forall i$ (5)
$\displaystyle y(i,j)$ $\displaystyle\leq x(i)$ $\displaystyle\forall i,j$ (6)
$\displaystyle y(i,j)$ $\displaystyle=0$ $\displaystyle\forall i,j\notin
J(Anc(i))$ (7) $\displaystyle\sum_{i^{\prime}\in\mathsf{Des}(i)}x(i^{\prime})$
$\displaystyle\geq 2$ $\displaystyle\forall i,\text{OPT}_{i}\geq 2$ (8)
$\displaystyle\sum_{i^{\prime}\in\mathsf{Des}(i)}x(i^{\prime})$
$\displaystyle\geq 3$ $\displaystyle\forall i,\text{OPT}_{i}\geq 3$

Figure 1. Linear program for active time scheduling. By default we restrict
$i\in[m]$ and $j\in J$.

The objective is to minimize $\sum_{i\in[m]}x(i)$. (2) ensures that every job
$j$ is scheduled in at least $p_{j}$ time slots. (3) ensures that the total
number of jobs scheduled in $x(i)$ is at most $g\cdot x(i)$, for each node
$i\in[m]$. (4) requires that the number of open time slots in a node $x(i)$ is
at most the interval length $L(i)$ of node $i$. (5) says that we could give at
most $x(i)$ time slots for a job $j$. (6) restricts that for each job $j\in
J$, $j$ can only be put into nodes in $\mathsf{Des}(K(j))$. (7) and (8) are
the key constraints that makes the LP stronger. They are clearly valid;
moreover, checking if $\text{OPT}_{i}\geq 2$ ($\text{OPT}_{i}\geq 3$) can be
done easily.

For simplicity, given a node set $V\subset[m]$ and $J^{\prime}\subset J$,
$y(V,J^{\prime})=\sum_{i\in V,j\in J^{\prime}}y(i,j)$; If either $V$ or
$J^{\prime}$ is a singleton, we can replace it by the unique element in it.
Let $x(S)=\sum_{i\in S}x(i)$ for every $S\subseteq[m]$.

After running the LP and getting a solution $(x,y)$, we will perform a
transformation on the solution.

###  2.2. Transformation of LP Solution

###### Lemma 1.

Given a feasible LP solution, we can efficiently output another feasible LP
solution such that for any pair of nodes $i_{1}$, $i_{2}$ such that
$i_{2}\in\mathsf{Des}^{+}(i_{1})$, if $x(i_{2})<L(i_{2})$, then $x(i_{1})=0$.

###### Proof.

Suppose there are nodes $i_{1},i_{2}$ with $i_{2}\in\mathsf{Des}^{+}(i_{1})$
and $x(i_{2})<L(i_{2})$ and $x(i_{1})>0$. Then let
$\theta=\min\\{L(i_{2})-x(i_{2}),x(i_{1})\\}>0$. We can move $\theta$
fractional open slots from $i_{1}$ to $i_{2}$. For every job $j$, we move
$\frac{\theta}{x(i_{1})}y(i_{1},j)$ fractional assignment of $j$ from $i_{1}$
to $i_{2}$. More specifically, let $(x^{\prime},y^{\prime})=(x,y)$ initially.
We decrease $x^{\prime}(i_{1})$ by $\theta$ and increase $x^{\prime}(i_{2})$
by $\theta$. For every $j\in J$, we decrease $y^{\prime}(i_{1},j)$ to
$\frac{x^{\prime}(i_{1})}{x(i_{1})}y(i_{1},j)$ and increase
$y^{\prime}(i_{2},j)$ to
$y^{\prime}(i_{2},j)+\frac{\theta}{x(i_{1})}y(i_{1},j)$. Notice that every job
$j$ that can be assigned to $i_{1}$ can also be assigned to $i_{2}$. It is not
hard to show that all constraints remain satisfied by the new solution
$(x^{\prime},y^{\prime})$. Finally we update
$(x,y)\leftarrow(x^{\prime},y^{\prime})$.

Notice that after the operation, we have either $x(i_{1})=0$ or
$x(i_{2})=L(i_{2})$. By repeating the procedure polynomial number of times, we
can find a solution $(x,y)$ satisfying the property of the lemma. ∎

An example of of the LP transformation is shown in Figure
LABEL:fig:LPtransformation.  PUT THE FIGURE BACK. Lemma 1 implies that for any
$i$ with $x(i)>0$, all of its strict descendants are fully open. We let $I$ be
the set of topmost nodes $i$ with $x(i)>0$; those are the nodes $i$ with
$x(i)>0$ but all its strict ancestors $i^{\prime}$ have $x(i^{\prime})=0$.

###### Claim 2.

The following properties hold for $I$:

  1. (2a)

No node in $I$ is a strict ancestor of another node in $I$.

  2. (2b)

$\mathsf{Des}(I)$ contains all leaves.

  3. (2c)

Every $i\in I$ has $x(i)>0$.

  4. (2d)

For any $i\in I$ and $i^{\prime}\in\mathsf{Des}^{+}(i)$, we have
$x(i^{\prime})=L(i^{\prime})$.

  5. (2e)

For any $i\in I$ and $i^{\prime}\in\mathsf{Anc}^{+}(i)$, we have
$x(i^{\prime})=0$.

We make two modifications to the tree that do not change the instance. First,
for every $i\in\mathsf{Anc}^{+}(I)$, we can assume that $i$ has exactly two
children: if $i$ has only one child, we remove it from the tree and connect
its parent directly to its children. This does not change the instance since
$x(i)=0$.

If a node $i$ has $x(\mathsf{Des}(i))\in(1,2)$, then $i$ is either a leaf, or
a node with exactly one child $i^{\prime}$, which is a leaf with
$\tilde{x}(i^{\prime})=x(i^{\prime})=L(i^{\prime})=1$. The second modification
is to make sure that the former case does not happen. For a leaf $i$ with
$x(i)\in(1,2)$, we create a child $i^{\prime}$ of $i$ with
$x(i^{\prime})=\tilde{x}(i)=L(i^{\prime})=1$, and then decrease
$x(i),x^{\prime}(i)$ and $L(i)$ by 1. For each $j$, we can split the $y(i,j)$
amount of job $j$ assigned to $i$, to $i$ and $i^{\prime}$, with a ratio of
$x(i):x(i^{\prime})$. This does not affect our instance, except for the
property that every leaf is associated with at least one job. But this is used
only to guarantee that $x(i)\geq 1$ for every leaf $i$, which still holds.

###  2.3. Rounding Algorithm to Obtain an Integral Vector
$\tilde{x}\in\\{0,1\\}^{[m]}$

The rounding algorithm that constructs our integral $\tilde{x}$ is given in
Algorithm 1.

Algorithm 1 Rounding Algorithm

1:let $\tilde{x}(i)\leftarrow\left\lfloor x(i)\right\rfloor,\forall i\in I$
and $\tilde{x}(i)\leftarrow x(i),\forall i\in[m]\setminus I$.

2:for every node $i\in\mathsf{Anc}(I)$ from bottom to top do

3: while $\frac{9x(\mathsf{Des}(i))}{5}\geq\tilde{x}(\mathsf{Des}(i))+1$ do

4: if $\exists i^{\prime}\in\mathsf{Des}(i)$ with
$\tilde{x}(i^{\prime})<x(i^{\prime})$ then

5: choose such an $i^{\prime}$ arbitrarily

6: let $\tilde{x}(i^{\prime})\leftarrow\left\lceil x(i^{\prime})\right\rceil$

7: else

8: break

Clearly, the number of open slots is at most $\frac{5x([m])}{3}$.

##  3\. Feasibility of $\tilde{x}$

In this section, we show that the rounded time slot $\tilde{x}$ is a feasible
solution.

###  3.1. A Necessary and Sufficient Condition

First we will give an if-and-only-if condition. From now on, for any set
$J^{\prime}\subseteq J$, we define $J^{\prime}(i)=J(i)\cap J^{\prime}$ for
every $i\in[m]$ and $J^{\prime}(S)=J(S)\cap J^{\prime}$ for every
$S\subseteq[m]$.

###### Lemma 1.

Given an integer solution $\tilde{x}$ for the LP, $\tilde{x}$ is feasible if
and only for every subset $J^{\prime}\subseteq J$ of jobs, we have

(9)
$\displaystyle\sum_{i\in[m]}\min\\{|J^{\prime}(\mathsf{Anc}(i))|,g\\}\cdot\tilde{x}(i)\geq
p(J^{\prime}).$

###### Proof.

The only if part is easy to see. Any node $i$ can hold at most
$\min\\{|J^{\prime}(\mathsf{Anc}(i))|,g\\}\cdot\tilde{x}(i)$ volume of jobs in
$J^{\prime}$. All the jobs in $J^{\prime}$ should be assigned. If $\tilde{x}$
is feasible, then
$\sum_{i\in[m]}\min\\{|J^{\prime}(\mathsf{Anc}(i))|,g\\}\cdot\tilde{x}(i)\geq
p(J^{\prime})$.

Now we prove the if part, by considering the contra-positive of the statement
and applying the maximum-flow-minimum cut theorem. Assume $\tilde{x}$ is not
feasible. We construct a 4-layer directed network $H=(V_{H},E_{H})$, where the
nodes from left to right are $\\{s\\},J,[m]$ and $\\{t\\}$. There is an edge
from $s$ to every $j\in J$ with capacity $p_{j}$, an edge from every $j\in J$
to every $i\in\mathsf{Des}(k(j))$ with capacity $\tilde{x}(i)$, and an edge
from every $i\in[m]$ to $t$ with capacity $g\cdot\tilde{x}(i)$. For a subsets
$V^{\prime}\subseteq V_{H}$ and a node $v\in V_{H}\setminus V^{\prime}$, we
use $E_{H}(V^{\prime},v)$ to denote the set of edges from $V^{\prime}$ to $v$.

As $\tilde{x}$ is not feasible, there is a $s$-$t$ cut in the network has
capacity less than $p(J)$. Let $(A,B)$ be the cut: $s\in A,t\in B$ and
$A\uplus B=V_{H}$ . Its cut value, which is $p(B\cap J)+\sum_{i\in
B\cap[m]}|E_{H}(A\cap J,i)|\cdot\tilde{x}(i)+g\cdot\tilde{x}(A\cap[m])$, is
less than $p(J)$. This is equivalent to $\sum_{i\in B\cap[m]}|E_{H}(A\cap
J,i)|\cdot\tilde{x}(i)+g\cdot\tilde{x}(A\cap[m])<p(A\cap J)$. Let
$J^{\prime}=A\cap J$. Then the contribution of a node $i\in[m]$ to the left-
side is either $|E_{H}(J^{\prime},i)|\cdot\tilde{x}(i)$ (if $i\in B$), or
$g\cdot\tilde{x}(i)$ (if $i\in A$), which is lower bounded by
$\min\\{|E_{H}(J^{\prime},i)|,g\\}\cdot\tilde{x}(i)$. Noticing
$|E_{H}(J^{\prime},i)|=|J^{\prime}(\mathsf{Anc}(i))|$, we have
$\sum_{i\in[m]}\min\\{|J^{\prime}(\mathsf{Anc}(i))|,g\\}\cdot\tilde{x}(i)<p(J^{\prime})$.
This finishes the proof of the if part. ∎

###### Lemma 2.

In Lemma 1, it is sufficient to consider the sets $J^{\prime}\subseteq J$
satisfying the following property:

  1. (2a)

$p_{j}>\tilde{x}\Big{(}\big{\\{}i\in\mathsf{Des}(K(j)):|J^{\prime}(\mathsf{Anc}(i))|\leq
g\big{\\}}\Big{)},\forall j\in J^{\prime}$.

###### Proof.

Suppose $J^{\prime}$ does not satisfy the property. Then for some $j\in
J^{\prime}$ we have
$\tilde{x}\Big{(}\big{\\{}i\in\mathsf{Des}(K(j)):|J^{\prime}(\mathsf{Anc}(i))|\leq
g\big{\\}}\Big{)}\geq p_{j}$. Then removing $j$ from $J^{\prime}$ will
decrease the left side of (9) by
$\tilde{x}\Big{(}\big{\\{}i\in\mathsf{Des}(K(j)):|J^{\prime}(\mathsf{Anc}(i))|\leq
g\big{\\}}\Big{)}$, and the right side by $p_{j}$. Thus, the inequality (9)
for $J^{\prime}$ will be implied by the inequality for
$J^{\prime}\setminus\\{j\\}$. ∎

Once we have the if-and-only-if condition for the feasibility, the main lemma
we need to prove is the following:

###### Theorem 3.

For every subset $J^{\prime}\subseteq J$ of jobs satisfying the property in
Lemma 2, we have (9).

The rest of the section is dedicated to the proof of Theorem 3. From now on we
fix a subset $J^{\prime}\subseteq J$ satisfying the property of Lemma 2. Our
goal is to prove (9).

For notational convenience, let
$u_{i}=\min\\{|J^{\prime}(\mathsf{Anc}(i))|,g\\}$ and $w_{i}=u_{i}x(i)$ and
$\tilde{w}_{i}=u_{i}\tilde{x}(i)$ for every $i\in[m]$. Thus, (9) is simply
written as $p(J^{\prime})\leq\tilde{w}([m])$. Recall that
$y(V,J^{\prime})=\sum_{i\in V,j\in J^{\prime}}y(i,j)$ for a given
$V\subseteq[m],J^{\prime}\subseteq J$. We have
$p(J^{\prime})=y([m],J^{\prime})=y(\mathsf{Des}(I),J^{\prime})$ and
$\tilde{w}([m])=\tilde{w}(\mathsf{Des}(I))$. Thus, we need to prove

(10) $\displaystyle
y(\mathsf{Des}(I),J^{\prime})\leq\tilde{w}(\mathsf{Des}(I)),$

for every $J^{\prime}\subseteq J$ satisfying the property in Lemma 2.

The following simple claim will be used multiple times:

###### Claim 4.

For every $i\in[m]$, we have $y(i,J^{\prime})\leq w_{i}=u_{i}x(i)$.

###### Proof.

If $u_{i}=g$, we use the (3) in the LP. If $u_{i}<g$, then we use (5) and (6).
∎

###  3.2. Construction of Triples

For nodes $i\in[m]\in I$, we have $\tilde{x}(i)=x(i)$. For nodes $i\in I$ with
$x(\mathsf{Des}(i))\notin(1,\frac{10}{9})$, we have $\tilde{x}(i)=\left\lceil
x(i)\right\rceil$ since $\frac{5x(\mathsf{Des}(i))}{3}\geq\left\lceil
x(\mathsf{Des}(i))\right\rceil$. Thus, for these nodes $i$, Claim 4 implies
$y(i,J^{\prime})\leq\tilde{w}_{i}$. The critical nodes are those $i\in I$ with
$x(\mathsf{Des}(i))\in(1,\frac{10}{9})$.

With this in mind, we classify nodes in $I$ into two types: a node $i\in I$ is
of

  * •

type-$\mathsf{B}$ if $x(\mathsf{Des}(i))\in\\{1\\}\cup[\frac{4}{3},\infty)$,
and

  * •

type-$\mathsf{C}$ if $x(\mathsf{Des}(i))\in(1,\frac{4}{3})$.

In the definition, we use $\frac{4}{3}$ instead of $\frac{10}{9}$ to create
some buffers. Furthermore, a type-$\mathsf{C}$ node $i\in I$ is of

  * •

type-$\mathsf{C}_{1}$ if $\tilde{x}(\mathsf{Des}(i))=1$, and

  * •

type-$\mathsf{C}_{2}$ if $\tilde{x}(\mathsf{Des}(i))=2$.

(Later, we may use types $\mathsf{A}$ and $\mathsf{B}$. But this is not
important.)

Notice that a type-$\mathsf{C}$ node $i$ is

The goal of this section is to create disjoint triples of type-$\mathsf{C}$
nodes. Each triple contains 1 type-$\mathsf{C}_{1}$ node, and 2
type-$\mathsf{C}_{2}$ nodes. Moreover, all the type-$\mathsf{C}_{1}$ nodes are
contained in these triples. Later for each triple $(i_{1},i_{2},i_{3})$ we
constructed, we shall prove
$y(\mathsf{Des}(\\{i_{1},i_{2},i_{3}\\}),J^{\prime})\leq\tilde{w}(\mathsf{Des}(\\{i_{1},i_{2},i_{3}\\}))$.
This will prove (10).

The construction of triples are given in Algorithm 2. Notice that this is not
a part of our algorithm for solving the active time scheduling problem; it is
only used in the analysis. If we have a type-$\mathsf{C}_{1}$ node $i_{1}$ and
a type-$\mathsf{C}_{2}$ node $i_{2}$ as brothers, then we say $(i_{1},i_{2})$
is a $\mathsf{C}_{1}\mathsf{C}_{2}$-brother-pair. In our triples, we make sure
that we do not break $\mathsf{C}_{1}\mathsf{C}_{2}$-brother-pairs: for such a
pair $(i_{1},i_{2})$, there must be some $\mathsf{C}_{2}$-node $i_{3}$ such
that $(i_{1},i_{2},i_{3})$ is a triple we constructed.

Algorithm 2 Construction of Triples

1:$\mathsf{triples}\leftarrow\emptyset$, set all type-$\mathsf{C}_{1}$ nodes
as uncovered, and all type-$\mathsf{C}_{2}$ nodes as unused.

2:for every node $i\in\mathsf{Anc}(I)$ with $|\mathsf{Des}(i)\cap I|\geq 3$
from bottom to top do

3: while $\exists$ an uncovered type-$\mathsf{C}_{1}$ node
$i_{1}\in\mathsf{Des}(i)$ do

4: choose two unused type-$\mathsf{C}_{2}$ nodes
$i_{2},i_{3}\in\mathsf{Des}(i)$, without breaking
$\mathsf{C}_{1}\mathsf{C}_{2}$-brother-pairs $\triangleright$ See Lemma 5

5: add $(i_{1},i_{2},i_{3})$ to $\mathsf{triples}$, claim $i_{1}$ is covered,
and $i_{2}$ and $i_{3}$ are used.

###### Lemma 5.

In Step 4 of Algorithm 2, there are at least two unused type-$\mathsf{C}_{2}$
nodes in $\mathsf{Des}(i)$.

###### Proof.

Let $n_{1}$ and $n_{2}$ be the number of type-$\mathsf{C}_{1}$ and
type-$\mathsf{C}_{2}$ nodes in $\mathsf{Des}(i)\cap I$ respectively. Let
$n^{\prime}=n_{1}+n_{2}$. We shall prove $n_{2}\geq 2n_{1}$, which implies
that we will not run out of type-$\mathsf{C}_{2}$ nodes and proves the lemma.

First, we consider the case where there is no type-$\mathsf{B}$ node in
$\mathsf{Des}(i)\cap I$. Then $n^{\prime}=|\mathsf{Des}(i)\cap I|\geq 3$.
Moreover, $n_{1}+2n_{2}\geq\left\lfloor\frac{9n^{\prime}}{5}\right\rfloor$ or
$n_{1}=0$ by our rounding algorithm in Algorithm 1. In the latter case we
clearly have $n_{2}\geq 2n_{1}$. So, we assume the former. Then
$n_{2}\geq\left\lfloor\frac{4n^{\prime}}{5}\right\rfloor$. Notice that
$\left\lfloor\frac{4n^{\prime}}{5}\right\rfloor\geq\frac{4n^{\prime}}{5}-\frac{4}{5}$
and thus
$\left\lfloor\frac{4n^{\prime}}{5}\right\rfloor\geq\frac{2n^{\prime}}{3}$
whenever $n^{\prime}\geq 6$. One can check that when
$n^{\prime}\in\\{3,4,5\\}$ we have
$\left\lfloor\frac{4n^{\prime}}{5}\right\rfloor\geq\frac{2n^{\prime}}{3}$.
Therefore if $n^{\prime}\geq 3$, we have
$\left\lfloor\frac{4n^{\prime}}{5}\right\rfloor\geq\frac{2n^{\prime}}{3}$. So
$n_{2}\geq 2n_{1}$.

Now we consider the other case where there is at least one type-$\mathsf{B}$
node in $\mathsf{Des}(i)\cap I$. If $n_{1}=0$, then $n_{2}\geq 2n_{1}$ and
thus we assume $n_{1}>0$. Then we have
$n_{1}+2n_{2}\geq\left\lfloor\frac{9n^{\prime}}{5}+\frac{2}{5}\right\rfloor$,
as the type $\mathsf{B}$ node $i^{*}$ have
$\frac{9x(\mathsf{Des}(i^{*}))}{5}\geq\left\lceil
x(\mathsf{Des}(i^{*}))\right\rceil+\frac{2}{5}$. This implies
$n_{2}\geq\left\lfloor\frac{4n^{\prime}}{5}+\frac{2}{5}\right\rfloor$. Then
$n_{2}\geq\frac{2n^{\prime}}{3}$ as
$\left\lfloor\frac{4n^{\prime}}{5}+\frac{2}{5}\right\rfloor\geq\frac{2n^{\prime}}{3}$
for every integer $n^{\prime}\geq 0$. Thus, $n_{2}\geq 2n_{1}$. ∎

###  3.3. Proof of (10) Using the Triples

In this section, we prove (10) by using the constructed triples. First, we
show that they satisfy some good properties:

###### Lemma 6.

For every $(i_{1},i_{2},i_{3})\in\mathsf{triples}$, one of the following two
conditions hold:

  1. (6a)

$i_{2},i_{3}\in\mathsf{Des}^{+}(\mathsf{par}(i_{1}))$.

  2. (6b)

$i_{1}$ and $i_{2}$ are brothers, and
$i_{3}\in\mathsf{Des}^{+}(\mathsf{par}(\mathsf{par}(i_{1})))$.

###### Proof.

Consider any type-$\mathsf{C}_{1}$ node $i_{1}$. Let $i^{*}$ and $i^{\prime}$
be the parent and brother of $i_{1}$ respectively.

First consider the case that $i^{\prime}\notin I$. By (2a) and (2b), we have
$|\mathsf{Des}(i^{*})\cap I|\geq 3$. By Algorithm 2 and Lemma 5, $i^{\prime}$
will be covered when we are at the iteration $i=i^{*}$ in Algorithm 2. So, the
second property holds.

Then consider the other case that $i^{\prime}\in I$. Then $i^{\prime}$ can not
be of type-$\mathsf{B}$ since otherwise $i_{1}$ should be of
type-$\mathsf{C}_{2}$. $i^{\prime}$ can not be of type-$\mathsf{C}_{1}$ since
we could open $3$ slots in $\mathsf{Des}(i^{*})$. Therefore $i^{\prime}$ must
be of type-$\mathsf{C}_{1}$ and $(i_{1},i^{\prime})$ is a
$\mathsf{C}_{1}\mathsf{C}_{2}$-brother-pair. In this case the first property
holds. ∎

Figure 2. The two cases in Lemma 6 and 7.

.

See Figure 2 for the two cases obtained in Lemma 6, which will be used again
in the proof of the following Lemma:

###### Lemma 7.

For every $(i_{1},i_{2},i_{3})\in\mathsf{triples}$, we have

$\displaystyle
y(\mathsf{Des}(\\{i_{1},i_{2},i_{3}\\}),J^{\prime})\leq\tilde{w}(\mathsf{Des}(\\{i_{1},i_{2},i_{3}\\})).$

###### Proof.

Recall that $i_{1}$ is of type $\mathsf{C}_{1}$ and $i_{2}$ and $i_{3}$ are of
type-$\mathsf{C}_{2}$. Let $i^{\prime}_{1},i^{\prime}_{2}$ and
$i^{\prime}_{3}$ be the children of $i_{1},i_{2}$ and $i_{3}$ respectively. By
Lemma 6, either (6a) or (6b) holds.

We first assume (6a). Let $i=\mathsf{par}(i_{1})$. See Figure 2(a) for all
illustration of nodes used in this case.

By (7) in the LP, $J(\mathsf{Des}(i_{1}))$ can be scheduled in the one slot in
$i^{\prime}_{1}$ since $x(\mathsf{Des}(i_{1}))<2$. That is, all the jobs in
the set has size 1 and there are at most $g$ of them. So, we have

$\displaystyle y(\mathsf{Des}(i_{1}),J^{\prime}(\mathsf{Des}(i_{1})))$ (11)
$\displaystyle\qquad\leq|J^{\prime}(\mathsf{Des}(i_{1}))|\leq
u_{i^{\prime}_{1}}x(i^{\prime}_{1}).$ $\displaystyle
y(\mathsf{Des}(i_{1}),J^{\prime}(\mathsf{Anc}^{+}(i_{1})))$
$\displaystyle\qquad\leq\frac{10}{9}\min\\{|J^{\prime}(\mathsf{Anc}^{+}(i_{1}))|,g\\}$
$\displaystyle\qquad\leq(\tilde{x}(i_{2})-x(i_{2})+\tilde{x}(i_{3})-x(i_{3}))\min\\{|J^{\prime}(\mathsf{Anc}^{+}(i_{1}))|,g\\}$
(12)
$\displaystyle\qquad\leq(\tilde{x}(i_{2})-x(i_{2}))u_{i_{2}}+(\tilde{x}(i_{3})-x(i_{3}))u_{i_{3}}$
$\displaystyle y(\mathsf{Des}(\\{i_{2},i_{3}\\}),J^{\prime})$ (13)
$\displaystyle\qquad\leq
u_{i_{2}}x(i_{2})+u_{i^{\prime}_{2}}x(i^{\prime}_{2})+u_{i_{3}}x(i_{3})+u_{i^{\prime}_{3}}x(i^{\prime}_{3})$

The first inequality of (11) is by that all jobs in
$J^{\prime}(\mathsf{Des}(i_{1}))$ have size $1$, and the second one is by
$u_{i^{\prime}_{1}}=\min\\{|J^{\prime}(\mathsf{Anc}(i^{\prime}_{1}))|,g\\}\geq|J^{\prime}(\mathsf{Des}(i_{1}))|$
and $x(i^{\prime}_{1})=1$. The first inequality of (12) is by that
$x(\mathsf{Des}(i_{1}))<\frac{10}{9}$. The second one follows from
$\tilde{x}(i_{2})-x(i_{2})\geq\frac{2}{3}$ and
$\tilde{x}(i_{3})-x(i_{3})\geq\frac{2}{3}$. The last one used that every job
in $J^{\prime}(\mathsf{Anc}^{+}(i_{1}))$ can be assigned to $i_{2}$ and
$i_{3}$. (13) is by Claim 4.

Adding (11), (12) and (13), we have

$\displaystyle\quad y(\mathsf{Des}(\\{i_{1},i_{2},i_{3}\\}),J^{\prime})$
$\displaystyle\leq
u_{i^{\prime}_{1}}x(i^{\prime}_{1})+u_{i_{2}}\tilde{x}(i_{2})+u_{i^{\prime}_{2}}x(i^{\prime}_{2})+u_{i_{3}}\tilde{x}(i_{3})+u_{i^{\prime}_{3}}x(i^{\prime}_{3})$
$\displaystyle=\tilde{w}(\mathsf{Des}(\\{i_{1},i_{2},i_{3}\\}))$

Now we consider the case that (6b) holds. Let
$i=\mathsf{par}(i_{1})=\mathsf{par}(i_{2})$. See Figure 2(b) for illustration
of the nodes.

First, if $u_{i_{2}}=g$, then we have
$(\tilde{x}(i_{2})-x(i_{2}))u_{i_{2}}\geq(x(i_{1})-\tilde{x}(i_{1}))u_{i_{1}}$
as $\tilde{x}(i_{2})-x(i_{2})\geq\frac{2}{3}$ and
$x(i_{1})-\tilde{x}(i_{1})<\frac{1}{9}$. This is
$\tilde{w}(i_{1})+\tilde{w}(i_{2})\geq w(i_{1})+w(i_{2})$. Thus,
$y(\mathsf{Des}(\\{i_{1},i_{2},i_{3}\\}),J^{\prime})\leq
w(\mathsf{Des}(\\{i_{1},i_{2},i_{3}\\}))\leq\tilde{w}(\mathsf{Des}(\\{i_{1},i_{2},i_{3}\\}))$
as $\forall
i^{\prime}\in\\{i_{3},i^{\prime}_{1},i^{\prime}_{2},i^{\prime}_{3}\\}$ we have
$w(i^{\prime})\leq\tilde{w}(i^{\prime})$.

So assume $u_{i_{2}}<g$. As we assumed $J^{\prime}$ satisfies (2a), every job
$j\in J^{\prime}(i)$ has $p_{j}>1$. But all jobs in $J(i)$ have $p_{j}\leq 2$
since otherwise we would have $x(\mathsf{Des}(i))\geq 3$ by LP constraint (8).
So all jobs in $J^{\prime}(i)$ have size $2$.

Then we have

$\displaystyle
y(\mathsf{Des}(i_{1}),J^{\prime}(\mathsf{Des}(i_{1})))+|J^{\prime}(i)|$ (14)
$\displaystyle\qquad\leq|J^{\prime}(\mathsf{Des}(i_{1}))|+|J^{\prime}(i)|\leq
u_{i^{\prime}_{1}}x(i^{\prime}_{1}).$ $\displaystyle
y(\mathsf{Des}(i_{1}),J^{\prime}(\mathsf{Anc}^{+}(i)))$ (15)
$\displaystyle\qquad\leq(\tilde{x}(i_{2})-x(i_{2}))u_{i_{2}}+(\tilde{x}(i_{3})-x(i_{3}))u_{i_{3}}$
$\displaystyle y(\mathsf{Des}(\\{i_{2},i_{3}\\}),J^{\prime}\setminus
J^{\prime}(i))+|J^{\prime}(i)|$ $\displaystyle\qquad\leq|J^{\prime}(i_{2})\cup
J^{\prime}(\mathsf{Anc}^{+}(i))|\cdot
x(i_{2})+u_{i^{\prime}_{2}}x(i^{\prime}_{2})+u_{i_{3}}x(i_{3})$
$\displaystyle\qquad\quad+u_{i^{\prime}_{3}}x(i^{\prime}_{3})+|J^{\prime}(i)|\cdot
x(i_{2})$ (16)
$\displaystyle\qquad=u_{i_{2}}x(i_{2})+u_{i^{\prime}_{2}}x(i^{\prime}_{2})+u_{i_{3}}x(i_{3})+u_{i^{\prime}_{3}}x(i^{\prime}_{3})$

The first inequality of (14) all jobs in $J^{\prime}(\mathsf{Des}(i_{1}))$
have size 1, and the second inequality is by that
$|J^{\prime}(\mathsf{Des}(i_{1}))|+|J^{\prime}(i)|\leq g$ since otherwise
$\text{OPT}_{i}\geq 3$. The proof of (15) is the same as that of (12), except
that we use $J^{\prime}(\mathsf{Anc}^{+}(i))$ instead of
$J^{\prime}(\mathsf{Anc}^{+}(i_{1}))$. Notice that every job in
$J^{\prime}(\mathsf{Anc}^{+}(i))$ can be assigned to $i_{2}$ and $i_{3}$. The
inequality in (16) used Claim 4 for $i^{\prime}_{2},i_{3}$ and
$i^{\prime}_{3}$. The equality used that $g\geq
u_{i_{2}}=|J^{\prime}(\mathsf{Anc}(i_{2}))|=|J^{\prime}(i_{2})\cup
J(\mathsf{Anc}^{+}(i))|+|J^{\prime}(i)|$.

Adding (14), (15) and (16), we get

$\displaystyle\quad y(\mathsf{Des}(i_{1},i_{2},i_{3}),J^{\prime}\setminus
J^{\prime}(i))+2|J^{\prime}(i)|$ $\displaystyle\leq
u_{i^{\prime}_{1}}x(i^{\prime}_{1})+u_{i_{2}}\tilde{x}(i_{2})+u_{i^{\prime}_{2}}x(i^{\prime}_{2})+u_{i_{3}}\tilde{x}(i_{3})+u_{i^{\prime}_{3}}x(i^{\prime}_{3})$
$\displaystyle=\tilde{w}(\mathsf{Des}(i_{1},i_{2},i_{3})).$

Notice that
$y(\mathsf{Des}(i_{1},i_{2},i_{3}),J^{\prime}(i))=p(J^{\prime}(i))=2|J^{\prime}(i)|$,
we have
$y(\mathsf{Des}(i_{1},i_{2},i_{3}),J^{\prime})\leq\tilde{w}(\mathsf{Des}(i_{1},i_{2},i_{3}))$.
∎

With Lemma 7, we can prove (10). First
$\sum_{i\in*}y(\mathsf{Des}(i),J^{\prime})\leq\sum_{i\in*}\tilde{w}(\mathsf{Des}(i))$,
where $i\in*$ is over all nodes in the triples we constructed. For all the
other nodes $i\in I$, we have $y(\mathsf{Des}(i),J^{\prime})\leq
w(\mathsf{Des}(i))\leq\tilde{w}(\mathsf{Des}(i))$. Therefore we have
$y(\mathsf{Des}(I),J^{\prime})\leq\tilde{w}(\mathsf{Des}(I))$, which is
exactly (10).


For $i=1$, by the definition of solution, $H^{-1}\big{(}n^{-1}\big{)}$ is a
limit cycle of (4.50) for $n=1,2,3,\cdots$, which is asymptotically orbitally
stable from the exterior and asymptotically orbitally unstable from the
interior. These limit cycles accumulate on the homoclinic cycle, a figure-
eight curve. Using $H$ as a Lyapunov function, we can prove that limit set of
$\Psi_{t}(x)$ lies on the zero set of $F(H)|\nabla H|^{2}$ (see Figure 8).

Figure 8: The phase portrait of system (4.50) for $i=1$.

Thus $B(\Psi)=\bigcup_{n=1}^{+\infty}H^{-1}\big{(}n^{-1}\big{)}\cup
H^{-1}(0)\cup\\{(\pm 1,0)\\}$. This shows that (4.50) possesses infinitely
many equivalent classes because each $H^{-1}\big{(}n^{-1}\big{)}$ is a
periodic orbit.

Let $\mu^{\varepsilon_{k}}$ converge weakly to $\mu$ as
$\varepsilon_{k}\rightarrow 0$. Then $\mu$ is supported on $B(\Psi)$ by [4,
Theorem 3.1]. Using $H+\frac{1}{4}$ as a Lyapunov function, we can verify that
both $(1,0)$ and $(-1,0)$ are repellers. Theorem 3.3 implies that $\mu$ is not
supported on the equilibria $(\pm 1,0)$. Again using the Lyapunov method, we
can prove that $H^{-1}\big{(}[-4^{-1},n^{-1}]\big{)}$ is an attractor for each
$n$. Utilizing Theorem 3.3 to semistable limit cycles
$\\{H^{-1}\big{(}m^{-1}\big{)}:\ m=1,2,3,\cdots,n-1\\}$ and the attractor
$H^{-1}\big{(}[-4^{-1},n^{-1}]\big{)}$, we conclude that $\mu$ is not
supported on semistable limit cycles $\\{H^{-1}\big{(}m^{-1}\big{)}:\
m=1,2,3,\cdots,n-1\\}$. Since $n$ is arbitrary, we obtain that ${\rm
supp}(\mu)\subset H^{-1}(0)$. Since $H^{-1}(0)$ consists of two homoclinic
orbits connecting the origin $O$, it follows from the invariance of $\mu$ with
respect to $\Psi$ that $\mu$ must be $\delta_{O}(\cdot)$. This proves that
$\mu^{\varepsilon}$ converges weakly to $\delta_{O}(\cdot)$ as
$\varepsilon\rightarrow 0$.

For $i=3$, the annular region $H^{-1}\big{(}[a_{n},b_{n}]\big{)}$ is full of
nontrivial periodic orbits of (4.50) for $n=1,2,3,\cdots$, which is
asymptotically orbitally stable from the exterior and asymptotically orbitally
unstable from the interior. These annular regions accumulate on the homoclinic
cycle. Similarly,
$B(\Psi)=\bigcup_{n=1}^{+\infty}H^{-1}\big{(}[a_{n},b_{n}]\big{)}\bigcup
H^{-1}(0)\bigcup\\{(\pm 1,0)\\}$.

Let $\mu^{\varepsilon_{k}}$ converge weakly to $\mu$ as
$\varepsilon_{k}\rightarrow 0$. Then $\mu$ is supported on $B(\Psi)$ by [4,
Theorem 3.1]. In the same manner we can prove that there is no concentration
of $\mu$ on the equilibria $(\pm 1,0)$ and that
$H^{-1}\big{(}[-4^{-1},b_{n}]\big{)}$ is an attractor for each $n$. By [36,
Proposition 5.5], the annular region $H^{-1}\big{(}[a_{n},b_{n}]\big{)}$ is an
equivalent class for each $n$. Applying Theorem 3.3 to the annular regions
$\\{H^{-1}\big{(}[a_{m},b_{m}]\big{)}:\ m=1,2,3,\cdots,n-1\\}$ and the
attractor $H^{-1}\big{(}[-4^{-1},b_{n}]\big{)}$, we conclude that there is no
concentration of $\mu$ on the annular regions
$\\{H^{-1}\big{(}[a_{m},b_{m}]\big{)}:\ m=1,2,3,\cdots,n-1\\}$. Since $n$ is
arbitrary, we obtain that ${\rm supp}(\mu)\subset H^{-1}(0)$ and
$\mu^{\varepsilon}$ converges weakly to $\delta_{O}(\cdot)$ as
$\varepsilon\rightarrow 0$.

Suppose that $i=2,4$. Then, using the same procedure we can show that there is
no concentration of $\mu$ on both $H^{-1}\big{(}n^{-1}\big{)}$ and
$H^{-1}\big{(}[a_{n},b_{n}]\big{)}$ for each $n$. Again using $H+\frac{1}{4}$
as a Lyapunov function, we can verify that $(\pm 1,0)$ are attractors for both
cases. Since every trajectory of $\Psi$ in the interior of $H^{-1}(0)$ other
than $(\pm 1,0)$ converges to $H^{-1}(0)$ as $t\rightarrow-\infty$ and to
$(\pm 1,0)$ as $t\rightarrow+\infty$ (see Figure 9).

Figure 9: The phase portraits of system (4.50) for $i=2$.

Applying Theorem 3.3 to $H^{-1}(0)$ and $(\pm 1,0)$, we get that
$\mu\big{(}H^{-1}(0)\big{)}=0$. Finally, we must have ${\rm supp}(\mu)=\\{(\pm
1,0)\\}$, which proves that $\mu^{\varepsilon}$ converges weakly to
$\lambda_{1}\delta_{(1,0)}(\cdot)+\lambda_{2}\delta_{(-1,0)}(\cdot)$ with
$\lambda_{1}+\lambda_{2}=1$ as $\varepsilon\rightarrow 0$. ∎

Acknowledgements
This work is partially supported by National Key R&D Program of
China(No.2022YFA1006001), and by NSFC (No. 12171321, 12371151, 12131019,
11721101), School Start-up Fund (USTC) KY0010000036, the Fundamental Research
Funds for the Central Universities(USTC) (No. WK3470000031).

## References

  * [1] A. Budhiraja, P. Dupuis, V. Maroulas. Large deviations for infinite dimensional stochastic dynamical systems. Ann. Probab. 36 (4) (2008), 1390-1420.
  * [2] A. Budhiraja, P. Dupuis, V. Maroulas. Analysis and Approximation of Rare Events. Representations and Weak Convergence Methods. Series Prob. Theory and Stoch. Modelling, 2019, 94.
  * [3] L. Chen, Z. Dong, J. Jiang, L. Niu and J. Zhai. Decomposition formula and stationary measures for stochastic Lotka-Volterra system with applications to turbulent convection. J. Math. Pures Appl. 125 (2019) 43-93.
  * [4] L. Chen, Z. Dong, J. Jiang, J. Zhai. On limiting behavior of stationary measures for stochastic evolution systems with small noise intensity. Sci. China Math. 63 (8) (2020), 1463-1504.
  * [5] M.L. Cartwright, J.E. Littlewood. On nonlinear differential equations of the second order, I: the equation $\ddot{y}+k(y^{2}-1)\dot{y}+y=b\lambda kcos(\lambda t+a)$, $k$ large. J. London Math. Soc. 20(1945), 180-189.
  * [6] M.L. Cartwright, J.E. Littlewood. Some fixed point theorems. With appendix by H. D. Ursell. Ann. of Math. 54 (2) (1951), 1-37.
  * [7] L. Chua, M. Komuro, and T. Matsumoto. The double scroll family. IEEE Trans. on Circuits and Systems. 33 (1986), 1073.
  * [8] W. E, T. Li, E. Vanden-Eijnden. Applied Stochastic Analysis. Graduate Studies in Mathmatics. AMS Providence Rhode Island. 2019.
  * [9] M. Freidlin, A. Wentzell. Random Perturbations of Dynamical Systems. Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, Heidelberg, third edition, 2012. Translated from the 1979 Russian original by Joseph Sz$\rm\ddot{u}$cs.
  * [10] M. Freidlin, L. Koralov. On stochastic perturbations of slowly changing dynamical systems. Nonlinearity. 30 (2017), 445-453.
  * [11] M. Freidlin, L. Koralov. Metastability for nonlinear random perturbations of dynamical systems. Stochastic Process. Appl. 120 (2010), 1194-1214
  * [12] M. Freidlin. Long-time influence of small perturbations and motion on the simplex of invariant probability measures. Pure Appl. Funct. Anal. 7 (2) (2022), 551-592.
  * [13] W. Huang, M. Ji, Z. Liu, Y. Yi. Steady states of Fokker-Planck equations: I. Existence. J. Dynam. Differential Equations 27 (3-4) (2015), 721-742.
  * [14] C. Hwang. Laplace’s method revisited: weak convergence of probability measures. Ann. Probab. 1980: 1177-1182.
  * [15] C. Hwang, S. Sheu. Large-time behavior of perturbed diffusion Markov processes with applications to the second eigenvalue problem for Fokker-Planck operators and simulated annealing. Acta Appl. Math. 19 (3) (1990), 253-295.
  * [16] R. Z. Khasminskii, The averaging principle for parabolic and elliptic differential equations and Markov processes with small diffusion. Teor. Verojatnost. i Primenen. 8(1963), 3-25.
  * [17] R. Z. Khasminskii, Stochastic Stability of Differential Equations, Stochastic Modelling and Applied Probability 66, Springer-Verlag Berlin Heidelberg, 2012.
  * [18] J. R. León, A. Samson. Hypoelliptic stochastic FitzHugh-Nagumo neuronal model: mixing, up-crossing and estimation of the spike rate. Ann. Appl. Probab. 28 (4) (2018), 2243-2274.
  * [19] N. Levinson. A second-order differential equation with singular solutions. Annals of Mathematics. 50(1949), 127-153.
  * [20] E. N. Lorenz. Deterministic non-periodic flow. J. Atmos. Sci. 20 (1963), 130-141.
  * [21] A. Matoussi, W. Sabbagh, T. S. Zhang. Large deviation principles of obstacle problems for quasilinear stochastic PDEs. Appl. Math. Optim. 83 (2) (2021), 849-879.
  * [22] R. M. May, W. J. Leonard. Nonlinear aspect of competition between three species. SIAM J. Appl. Math. 29 (2) (1975), 243-253.
  * [23] J. K. Moser, Bistable systems of differential equations with applications to tunnel diode circuits. IBM J. Res. Develop. 5 (1961), 226-240.
  * [24] E. Olivieri, M. Vares. Large Deviations and Metastability. Cambridge Univ. Press, 2005.
  * [25] O. E. Rössler. An equation for continuous chaos. Phys. Lett. A. 57 (1976), 397.
  * [26] M. Salins, A. Budhiraja, P. Dupuis. Uniform large deviation principles for Banach space valued stochastic evolution equations. Trans. Amer. Math. Soc. 372 (12) (2019), 8363-8421.
  * [27] M. Salins. Equivalences and counterexamples between several definitions of the uniform large deviations principle. Probab. Surv. 16 (2019), 99-142.
  * [28] Ya. G. Sinai, Kolmogorov’s work on ergodic theory. Ann. Probab., 17 (3) (1989), 833-839.
  * [29] S. Smale. Finding a horseshoe on the beaches of Rio. Math. Intelligencer 20 (1) (1998), 39-44.
  * [30] Smale, S. On the mathematical foundations of electrical circuit theory. J. Differential Geometry 7 (1972), 193-210.
  * [31] B. van der Pol, B. van der Mark. Frequency demultiplication. Nature, 120, 363-364, 1927.
  * [32] E. Vanden-Eijnden, J. Weare. Rare event simulation of small noise diffusions. Comm. Pure Appl. Math. 65 (12) (2012), 1170-1803.
  * [33] J. Wang, H. Yang, J. Zhai, T. Zhang. Large deviation principles for sdes under locally weak monotonicity conditions. Bernoulli 30 (2024), no. 1, 332-345.
  * [34] A. Wentzell, M. Freidlin. Small random perturbations of dynamical systems. Uspehi Mat. Nauk, 25 (1) (1970), 3-55.
  * [35] J. Xu, B. Xie, S. Liao, et al. Online assessment of conservation voltage reduction effects with micro-perturbation. IEEE Transactions on Smart Grid. 12 (3) (2020), 2224-2238.
  * [36] T. Xu, L. Chen, J. Jiang. On limit measures and their supports for stochastic ordinary differential equations. J. Differ. Equations. 365 (2023), 72-99.
  * [37] Z. Zhang, T. Ding, W. Huang, Z. Dong. Qualitative Theory of Differential Equations, Science Press, Beijing, 1992 (in Chinese); English ed., Qualitative Theory of Differential Equations, Transl. Math. Monogr., vol. 101, Amer. Math. Soc., Providence, RI, 1992.