(eccv) Package eccv Warning: Package ‘hyperref’ is loaded with option
‘pagebackref’, which is *not* recommended for camera-ready version

11institutetext: Alibaba Group 11email:
<EMAIL_ADDRESS>
# EffiVED:Efficient Video Editing via Text-instruction Diffusion Models

Zhenghao Zhang 11 Zuozhuo Dai 11 Long Qin and Weizhi Wang 1111

###### Abstract

Large-scale text-to-video models have shown remarkable abilities, but their
direct application in video editing remains challenging due to limited
available datasets. Current video editing methods commonly require per-video
fine-tuning of diffusion models or specific inversion optimization to ensure
high-fidelity edits. In this paper, we introduce EffiVED, an efficient
diffusion-based model that directly supports instruction-guided video editing.
To achieve this, we present two efficient workflows to gather video editing
pairs, utilizing augmentation and fundamental vision-language techniques.
These workflows transform vast image editing datasets and open-world videos
into a high-quality dataset for training EffiVED. Experimental results reveal
that EffiVED not only generates high-quality editing videos but also executes
rapidly. Finally, we demonstrate that our data collection method significantly
improves editing performance and can potentially tackle the scarcity of video
editing data. The datasets will be made publicly available upon publication.

###### Keywords:

Video editing Diffusion model Efficient

##  1 Introduction

The advent of text-to-image diffusion models[39, 35, 17, 30] has propelled the
advancement of text-driven video editing[1, 2, 9, 16]. For example, Tune-A-
Video[52] exemplifies this by initially fine-tuning a diffusion model with an
input video and corresponding text description to establish the correspondence
between the two modalities. Video-P2P[25] optimizes a shared unconditional
embedding to attain precise video inversion and utilizes attention swap in
diffusion model for detailed editing. On another front, CoDeF[32] edits
canonical image and propagates the changes temporally using deformation field
extracted from a neural video field. This method delivers superior temporal
coherence along with high-fidelity synthesized frames compared to the
aforementioned methods. However, these methods all entail considerable
computational costs because they require tailored processing for each video.

Figure 1:  On the left: EffiVED offers users a versatile range of video
editing capabilities, including modifications to objects, backgrounds and
style transfer. On the right: Temporal Consistency & Text Alignment _vs_.
Runtime(s) comparison on the TGVE dataset[51]. For runtime, all methods are
evaluated by editing a 60-frame, 512p$\times$512p video using A100 GPUs with
the official implementation. EffiVED achieves an impressive inference speed of
47 seconds, offering a 6 to 28 times speed boost compared to existing methods
without compromising the quality of editing.

To address the aforementioned problem, we propose EffiVED, an open-domain
video editing framework that seamlessly edits input videos according to human
language instructions without necessitating any specific fine-tuning. EffiVED
is a conditional diffusion model that employs a conditional 3D U-Net[41]
architecture at its core. This design enables it to generate edited video
content directly from the provided input video and associated textual
instructions.

To achieve direct video editing, we need a diverse training dataset that pairs
input videos with instructions and edited results. This dataset must maintain
temporal consistency and precisely execute the instructed changes.
Unfortunately, no current readily available dataset or model meets these
specific needs, and collecting real-world video-instruction pairs for training
is laborious and costly due to the meticulous alignment required between
visuals and text descriptions.

Inspired by Instruct-Pix2Pix[5] that integrates multiple foundational
models[6, 40] to create the image editing pairs, we have created a synthetic
video dataset that pairs instructions with their before-and-after visual
counterparts. To maximize the utilization of extensive instruction-based image
editing datasets[5, 59], we apply augmentations such as random affine
transformations to source and target images, simulating camera movements. This
strategy enables us to seamlessly generate video triplets. These synthetic
data instances provide rich visual context and enhance alignment between the
visual and textual domains. To expand the variety of motion patterns, we also
incorporate a large language model (LLM)[31] and the CoDeF technique
specifically designed for real-world video content. Specially, we first
leverage an example-driven approach to guide the LLM, empowering it to
generate accurate descriptions that align with both videos and editing
instructions. Subsequently, we train a CoDeF model to generate the
corresponding edited counterparts, taking advantage of its demonstrated
superior fidelity.

Employing video editing pairs from these methodologies, we create a robust
training foundation for EffiVED. During training, we first extract video
latents with a Variational Autoencoder (VAE) [23]. These latents are then
combined with their noisy versions and denoised back to the edited video
latents. We separate classifier-free guidance into two distinct components:
vision-conditioned and text-conditioned guidance. This separation allows each
part to independently control the editing process based on visual or textual
information. Consequently, it ensures generated videos more accurately adhere
to both the original video content and the given text instructions.

In summary, our principal contributions are as follows:(i) we introduce two
workflows for the collection of video editing pairs. This process effectively
converts large-scale image editing datasets and open-world videos into a high-
quality training set for video editing. With this workflow, we (ii) train a
video editing model EffiVED that is capable of performing a broad range of
editing tasks at an impressively fast speed, as evidenced in Fig. 1. (iii) To
investigate how our data collection approach impacts editing performance, we
carry out several domain-specific experiments. These experiments explore
strategies such as using data augmentations for image editing data, assessing
video caption quality, and integrating multiple vision-language models in real
videos. These may help overcome the data scarcity observed in the video
editing domain.

##  2 Related Work

###  2.1 Text-to-Video Generation

Recent advancements in diffusion models have shown great promise in video
generation [29, 43, 40, 34, 36]. The Video Diffusion Model (VDM) [18] pioneers
this domain by adapting the image diffusion U-Net architecture [41] into a 3D
structure for joint image and video training. Imagen Video [15] employs a
series of video diffusion models for high-resolution, temporally coherent
video synthesis. Make-A-Video [44] innovatively learns motion patterns from
unlabeled video data, while Tune-A-Video [52] explores one-shot video
generation by fine-tuning LDMs with a single text-video pair. Text2Video-Zero
[22] tackles zero-shot video generation using pretrained LDMs without further
training. ControlVideo [61] introduces a hierarchical sampler and memory-
efficient framework to craft extended videos swiftly. Despite these
innovations, capturing complex motion and camera dynamics remains challenging.
VideoComposer [50] and DragNUWA [56] propose motion trajectory-based control
for video generation, yet they fall short in interactive animation with
multiple objects. I2VGen-XL[60] reduces the reliance on well-aligned text-
video pairs by utilizing a single static image as the primary condition.
AnimateAnything[10] additionally incorporates motion masks and motion strength
to precisely manipulate individual objects within an image, thus facilitating
more user-centric interactive animation generation. Building upon the
significant advancements in those above video generation models, our approach
focuses on enhancing the fidelity of VDMs, particularly in the realm of video
content translation.

###  2.2 Text-Guidance Image Editing

Text-Guidance Image Editing[1, 2, 9, 16] is a sophisticated process that
modifies images according to precise text instructions. Early methods
concentrated on adjusting the reverse diffusion process to maintain
faithfulness. SDEdit[26] pioneers as the first diffusion-based technique,
applying varied noise levels to source images and generating edited results
through diffusion sampling directed by edit prompts. Plug-and-Play[46] starts
with DDIM inversion[45] to sample edited videos, copying selected visual
features during diffusion. Prompt-to-Prompt(P2P) [14] allows for a variety of
edits by substituting the attention mechanisms in generated images with those
from source images during the diffusion process. Other methods use
optimization techniques for better editing. For instance, Imagic [21] employs
textual inversion concepts from a specific source [38], while Null-text
Inversion[27] extends P2P to regulate cross-attention behavior by optimizing
null text embeddings, thereby enabling more accurate reconstruction of the
original image. However, these methods typically necessitate time-consuming
because of per-image optimization. Recently, approaches like Instruct-
Pix2Pix[5] have treated image editing as a supervised learning task,
collecting paired synthetic data and fine-tuning text-to-image models[39, 35].
InstructDiffusion[5] consolidates multiple vision tasks under this framework.

###  2.3 Text-Guidance Video Editing

Video editing is a substantially more challenging task [12, 62, 48, 11] than
image editing, particularly due to the need for frame-to-frame consistency and
addressing temporal inconsistencies. Current approaches mainly focus on
effectively steering large pre-trained models and can be broadly grouped into
three categories: zero-shot, one-shot, and feature propagation techniques.
Zero-shot approaches typically involve incorporating cross-frame attention or
token flow mechanisms to ensure temporal coherence. For instance,
Video-P2P[25] employs a decoupled guidance strategy for real-world video
editing tasks, utilizing cross-attention control. Similarly, Pix2Video[7] and
FateZero[37] both propose distinct variations on replacing self-attention with
cross-frame attention mechanisms. However, given that these models are not
specifically trained on real-world videos, they tend to struggle with
preserving temporal consistency in complex video scenarios. Moreover, the per-
frame application of cross-attention comes with an additional computational
cost. One-shot methods utilize fine-tuned diffusion models on a given video,
which then sample new content conditioned upon specific edit prompts. For
instance, Tune-A-Video[53] and SimDA[54] generate videos based on textual
prompts through the process of one-shot fine-tuning of pre-trained stable
diffusion models. Dreamix[28] introduces a groundbreaking mixed fine-tuning
model that notably enhances the quality of motion edits. Meanwhile,
AnimateDiff[13] leverages customized model weights to incorporate conditional
content, achieved either by using LoRA[19] or DreamBooth[42]. Recently, Neural
Layered Atlases[20] have gained popularity for their ability to decompose
input into consistent layered representations. Text2Live[3] augments atlases
with extra edit layers and trains a dedicated generator for them.
StableVideo[8] improves temporal consistency through an atlas aggregation
network. CoDeF[32] estimates canonical images and temporal deformation fields
using optical flow from source videos. Despite its ability to produce high-
quality edited videos with similar motion patterns, this approach inherently
involves repetitive and laborious fine-tuning for each individual video input,
which restricts its scalability across broader applications. In contrast, our
method leverages VDM to execute video editing tasks directly by using our
synthetic dataset, thus ensuring temporal coherence without additional fine-
tuning.

##  3 Method

In this section, we first introduce the preliminaries of the LDM in Sec. 3.1.
Next, we present the workflow of the dataset collection used for training in
Sec. 3.2. Finally, we describe the architecture of EffiVED in Sec. 3.3.

###  3.1 Preliminaries of LDM

In this section, we present the foundational concepts of Latent Diffusion
Models (LDM) [40]. Given an image sample $x_{0}\in\mathbb{R}^{3\times H\times
W}$, LDM initially employs a pre-trained VAE to compress $x_{0}$ into a lower-
resolution latent representation $z_{0}\in\mathbb{R}^{c\times h\times w}$. The
forward process in LDM can be depicted as a Markov chain that progressively
adds Gaussian noise to the latent representation step by step:

$q(z_{t}|z_{t-1})=\mathcal{N}(z_{t};\sqrt{1-\beta_{t}}z_{t-1},\beta_{t}I),$
(1)

where $t=1,...,T$, $T$ is the total number of timesteps. $\beta_{t}$ denotes a
coefficient that controls the intensity of the noise in step $t$. The
iterative noise adding can be simplified as:

$z_{t}=\sqrt{\bar{\alpha}_{t}}z_{0}+\sqrt{1-\bar{\alpha}_{t}}\epsilon,\quad\epsilon\sim\mathcal{N}(0,I),$
(2)

where $\bar{\alpha}_{t}=\prod_{i=1}^{t}(1-\beta_{t})$. During training, the
LDM learns to approximate the latent space distribution of authentic data by
predicting the noise $\epsilon$ applied to $z_{t}$, thereby reducing
computational complexity compared to conventional diffusion models. The
objective function for this learning process can be formulated as:

$l_{\epsilon}=||\epsilon-\epsilon_{\theta}(z_{t},t,c)||^{2}_{2},$ (3)

where $\epsilon_{\theta}(\cdot)$ denotes the noise prediction function of
diffusion models. LDM simplifies flexible control of generation by converting
user conditions $c$ with a domain-specific encoder into an intermediate
format, which is then incorporated into the UNet via cross-attention.

Video diffusion models like [18, 44, 50] build upon image LDMs by
incorporating a 3D U-Net structure, thereby allowing them to adeptly process
video content. This 3D U-Net adds temporal convolutions after each spatial one
and follows every spatial attention layer with a temporal attention block. To
ensure it retains the capacity to generate from image data, the 3D U-Net is
trained simultaneously using both image and video datasets.

###  3.2 Training Data Construction

Given source video $V_{s}$ and instruction $c$, we aim to generate target
video $V_{t}$ without per-video fine-tuning. We achieve this by assembling
video triplets of various editing situations for training, then conditionally
translate $V_{s}$ into $V_{t}$ based on $c$. This section discusses our
strategy for collecting datasets.

Figure 2:  An example of generating training data from image editing dataset.
Given pairs of original and edited images, we randomly select and apply a set
of affine transformations (e.g., rotation, crop, translation, or shearing) to
both images. This approach generates a sequence of frames that simulate camera
movement for each image.

Generating with image editing datasets. InstructPix2Pix [5] leverages LLM to
generate a large dataset of image editing examples. Given the relative
scarcity of videos compared to images, we capitalize on the following insight
to synthesize videos that simulate camera movements using these image samples.
In particular, if a frame $I_{t}$ differs from previous frame $I_{t-1}$ only
in the camera position, then the edited frame $E_{t}$ and $E_{t-1}$ should
only be different in the camera position as well.

Given a pair of images, namely the original and the edited, represented as
($I$, $E$), we randomly select and apply a set of affine transformations or
random crops $\\{F\\}_{t=1}^{T}$ to both images. As shown in Fig. 2, this
process results in the generation of the pseudo video sequence with a length
of $T$:

$V_{I}=\\{F(I)\\}_{t=1}^{T},V_{E}=\\{F(E)\\}_{t=1}^{T}$ (4)

We set random rotations degrees to < 5 , random translation to [$-$0.05,0.05],
random scaling factor to [0.95,1.05], and random shear degrees to
$[-5^{\circ},5^{\circ}]$ on both axis. For the random resized crop, we scale
the original image to 288 pix, and randomly crop a square image with 256 pix.

Figure 3:  An overview of generating training data with open-world videos. (i)
First, we leverage CoCa and VideoBLIP to extract caption from both keyframes
and the entire video content, which are then synthesized into a comprehensive
summary by ChatGPT. (ii) Next, we utilize ChatGPT to generate editing
instruction and edited caption by providing manually examples. (iii) Finally,
the generated instruction and the original video feed an individual CoDeF
model to produce edited video.

Generating with open-world videos. While generating from image editing
datasets can indeed offer strong alignment between text and visual content, it
inherently lacks the natural motion dynamics found in real-world videos. In
this section, we will illustrate a pipeline that leverages model composition
to generate instructions and corresponding edited counterparts from open-world
videos. This is achieved by integrating multiple fundamental models including
ChatGPT[31], CoCa[57], V-BLIP[58] and CoDeF[32].

As shown in Fig. 3, the first step is to generate video captions for open-
world video clips. Motivated by SVD[4], we follow a multi-step approach for
generating an accurate and comprehensive video caption. In a nutshell, we
uniformly extract four key-frames from the video and use CoCa to generate
captions for each. Subsequently, V-BLIP generates a full-video caption by
interpreting context across these frames. Finally, ChatGPT consolidates all
five captions into a concise summary that captures the essence of the entire
video content.

Based on the generated video captions, we utilize ChatGPT to craft
instructions and edited captions accordingly. This AI tool can ingeniously
derive contextually logical instructions and captions based on a minimal
number of manual examples. For more instances showcasing ChatGPT’s in-context
learning capabilities, please refer to the supplementary materials.

Finally, we employ a modified CoDeF to create edited videos that follow given
instructions while preserving subtle motions. This method involves fine-tuning
per video to construct a canonical content field that consolidates the static
contents throughout the entire video and a temporal deformation field which
records the transformations from the canonical image to every frame over time.
These two fields are model by dynamic Neural Radiance Fields (NeRFs)[33]. To
enhance the modeling of complex motion, we augment dynamic NeRFs with an
increased hash table size to accommodate more grids at varying resolutions.
This allows us to capture more high-frequency details, thereby improving the
quality of edited videos. Upon training, CoDeF saves the canonical image and
its corresponding deformation field for each video. When it comes to
generating the edited video, an image-editing model such as InstructPix2Pix[5]
is applied to the canonical image based on the modified caption to produce the
edited canonical image. Then, this edited canonical image is propagated to all
frames using the saved deformation fields, thereby creating the final edited
video with maintained consistency and structure.

Through these automated processes, we can systematically generate multiple
sets of input videos, instructions, and their corresponding edited videos.
These triplets serve as the valuable training data set for our EffiVED model,
enhancing its capability to understand and execute editing instructions
effectively on different videos.

###  3.3 EffiVED Model

Training pipeline of EffiVED. The detailed training pipeline for EffiVED is
depicted in Fig. 4. Given the input video $V_{I}$ and the editing video
$V_{E}$, we utilize a pre-trained VAE encoder to transform these videos into
their latent space representations $x_{I}$ and $x_{E}$. Then, the sampled
noisy latent $\epsilon$ is concatenated with the latent representation of the
input video along the channel dimension and fed into the 3D U-Net. Throughout
this process, the text embedding serves to guide the cross-attention
mechanism. Here, both the input video $x_{I}$ and the provided instruction $c$
act as conditions that control the denoising process, thereby steering the
translation towards the editing video $x_{E}$. We minimize the following
latent diffusion objective:

$\mathbb{E}_{x_{I},x_{E},\epsilon\sim\mathcal{N}(0,1),t}\left[\left|\epsilon-\epsilon_{\theta}(\left[x_{I},x_{E}\right],c,t)\right|_{2}^{2}\right],$
(5)

where $t$ is the denoising step, the optimization objective centers on
accurately estimating the introduced noise while concurrently maintaining
temporal coherence among neighboring frames.

Figure 4:  Overview of our training pipeline. We adopt the widely used 3D
U-Net based video diffusion model [50] for video editing. To enable vision
conditioning, we augment the 3D-UNet’s input by appending extra channels to
its initial convolutional layers. The input is essentially a channel-wise
concatenation of video latents and noise.

Decoupled Classifier-Free Guidance. Given that our method accepts both
instructions and videos as input, it needs to balance the probability mass of
these two streams when guiding the output. Inspired by [50] that skillfully
combines multiple prompts for accurate score estimates, we randomly choose
either the input video latent $x_{I}$ or the text prompt $c$ as the only
input. During inference, the predicted noise at step $t$ can be computed as:

$\begin{split}\widetilde{\epsilon}(x_{I},c,t)=\widetilde{\epsilon}(\phi,\phi,t)+\lambda_{1}(\widetilde{\epsilon}(x_{I},c,t)-\widetilde{\epsilon}(\phi,c,t))\\\
+\lambda_{2}(\widetilde{\epsilon}(x_{I},c,t)-\widetilde{\epsilon}(x_{I},\phi,t)),\end{split}$
(6)

where $\lambda_{1}$ and $\lambda_{2}$ denote the text and vision guidance
scales, respectively. A higher value of either $\lambda_{1}$ or $\lambda_{2}$
will exert a stronger influence on directing the edited video to adhere more
closely to the corresponding condition.

##  4 Experiments

###  4.1 Experiments Setup

Dataset. For our evaluation, we use the Text-Guided Video Editing (TGVE)[51]
competition dataset that contains 76 videos. Every video in the dataset comes
with one original prompt that describes the video and four prompts that
suggest different edits for each video. Three editing prompts pertain to
modifications in style, background, or object within the video. Additionally,
a multiple editing prompt is provided that may incorporate all three types of
edits simultaneously.

Metrics. Following previous works, we assess the edited videos based on two
main aspects: text-video alignment and video quality. The text-video alignment
measures how closely the edited video adheres to the provided text
instructions. This is calculated by averaging the text-image similarity in the
embedding space of CLIP image models across all frames in the video. We also
utilize PickScore[24] to gauge whether the structural integrity of the
original video has been successfully maintained after editing. Regarding video
quality, we examine frame consistency, which is estimated by calculating the
average cosine similarity between CLIP image embeddings for each pair of
edited frames. This helps us understand how well the visual coherence is
maintained.

Implementation Details. We first collect 131k training clips, each containing
eight frames, from InstructPix-Pix[5] and MagicBrush[59] using the proposed
method. For generating instructions and edit prompts from open-world videos,
we follow the approach outlined in InstructPix-Pix to guide ChatGPT. We
utilize the official repositories of CoDeF and only increase the hash table
size for better reconstruction of high-frequency details. During this process,
we collect 24k training clips. The EffiVED model is initialized with
Modelscope T2V[47]. Our training strategy employs a two-stage methodology.
Initially, the model undergoes training for 30k iterations on a dataset of
131k clips with a batch size of 4, enabling it to effectively align with
editing instructions and adeptly manage various editing tasks. In the
subsequent phase, refinement continues by training the model on open-world
videos for an additional 10k iterations, which thereby enhances its temporal
consistency. To further optimize performance, during this latter stage, we
implement multi-frame rate sampling, extracting training clips of 8-frames
from a variety of frame rates (e.g., 4, 6, and 8).

###  4.2 Evaluation Results

In Tab. 1, we present the quantitative results of several mainstream video
editing models. It is evident that the majority of these methods rely on one-
shot tuning or inversion optimization, significantly impeding practical
application. CoDeF attains the highest level of editing quality due to its
superior reconstruction. By training on our dataset, our method sustains a
comparable performance in terms of fidelity and temporal consistency.
Regarding runtime efficiency, it is worth noting that our method does not
require any finetuning or inversion, and as a result, it operates around 6
times faster than Render-A-Video[55] and an impressive 20 times faster than
CoDeF. This substantial difference in speed effectively showcases the high
level of efficiency inherent in our proposed method.

Method | Text Alignment | Frame Consistency | PickScore | Runtime(s)
---|---|---|---|---
Text2Video-Zero[22] | 25.9 | 92.1 | 19.9 | -
Render-A-Video[55] | 32.6 | 90.9 | 19.6 | 294
Vid2Vid-Zero[49] | 40.0 | 92.6 | 20.4 | -
Video-P2P[25] | 35.5 | 93.5 | 20.1 | 1385
Tune-A-Video[53] | 27.1 | 92.4 | 20.3 | 1026
TokenFlow[12] | 28.7 | 94.0 | 20.5 | 394
CoDeF[32] | 40.2 | 94.2 | 20.8 | 827
EffiVED | 39.7 | 93.7 | 20.6 | 47
Table 1: Comparision of editing quality and runtime on TGVE dataset. We
measured the running time of 60 frames.  Figure 5:  A/B Comparison with
current methods. Our method not only effectively aligns edited videos with
instructions but also consistently preserves the video’s structure.

We also conduct an A/B testing to evaluate the superiority of our method
against three techniques: Tune-A-Video, Video-P2P, and TokenFlow. We engage
five human evaluators to assess the quality of a sample of 100 generated
videos. The evaluation is based on three criteria. The first criterion
assesses visual quality, encompassing clarity and absence of flicker. The
second metric evaluates prompt faithfulness, determining how well the output
video reflects and executes the content in the editing instructions. Lastly,
input faithfulness checks if the edited videos retain the original video’s
structure. As shown in Fig. 5, in terms of visual quality, our method are
notably better than Tuna-A-Video and Video-P2P. This improvement can be
attributed to the synthesis video data for training, our model learn better to
keep the temporal consistency and maintains the structural integrity with the
condition of the origin video latent. For faithfulness, our method are notably
better than all compared methods, showing that the efficiency of the fully use
of the image editing dataset and the generating captions can better align the
origin videos.

Figure 6:  Qualitative Comparison. EffiVED outperforms baseline methods by
demonstrating superior consistency and a heightened adherence to the provided
instructions. Figure 7:  Qualitative results of EffiVED. EffiVED offers
flexible editing capabilities, including changes to backgrounds, objects, and
styles.

Moreover, we present a qualitative comparison in Fig. 6 with these methods.
Note that Video-P2P, untrained on video data and adjusting cross-attention
solely between prompts, often fails to preserve object consistency across
frames (as evidenced by the astronaut and fox). Tune-A-Video struggles with
generating coherent motion when handling multiple edits, as seen in the
astronaut’s actions. TokenFlow, while adept at maintaining structural
continuity, suffers from a ’feature-level smoothing’ drawback, causing
blurring in static areas, evident in the fox where backgrounds are blurred
compared to the original versions. In contrast, our method stands out by
preserving global consistency throughout the edited videos, ensuring alignment
with the given text prompt, and upholding high editing quality—all achieved
within a shorter time compared to previous methods. In Fig. 7, we show more
editing cases including stylization(e.g. watercolor style, Van Gogh style),
background(e.g replacing the highway with snow trail), multiple objects (e.g.
transforming several goldfish into sharks).

###  4.3 Ablation Studies

In this section, we perform several ablation studies to validate the
effectiveness of our data collection strategies. All results are evaluated on
TGVE datasets.

The source and scale of training data. We train EffiVED with separate
datasets: the 131k synthetic pairs from an image editing dataset and the 23k
samples from open-world videos. We also conduct training with mixed datasets
of varying sizes from both sources to analyze performance fluctuations. The
results of these experiments are presented in Tab. 2.

Training Data | Text Alignment | Frame Consistency | PickScore
---|---|---|---
131k from image editing | 37.7 | 91.6 | 20.1
23k from open-world video | 35.6 | 92.3 | 19.4
Mixed data(20k) | 32.6 | 68.7 | 18.9
Mixed data(50k) | 35.7 | 81.3 | 19.7
Mixed data(80k) | 37.9 | 89.6 | 20.3
Mixed data(120k) | 38.8 | 92.9 | 20.4
Mixed data(all) | 39.1 | 93.7 | 20.6
Table 2: Ablation studies on the source and scale of training data. The mixed
data refers to the combination of datasets from both sources, and we adopt a
sampling ratio of 5:1 to collect the sub-dataset.

Training solely on image editing pairs yields good alignment with instructions
but may suffer from temporal inconsistency due to unrealistic motion
simulation. Open-world video data, while enhancing temporal coherence, can
result in a less diverse and potentially less instruction-sensitive dataset.
EffiVED effectively strikes a balance by leveraging both datasets, thereby
ensuring accurate text-to-video alignment and maintaining robust temporal
consistency. In terms of the training data volume, we observe a significant
enhancement in performance as the size increases from 20k to 80k. This
considerable improvement substantiates that our dataset indeed boosts the
editing capabilities of the pretrained video diffusion model effectively. Upon
further expansion of the dataset, the performance improvement diminishes and
eventually plateaus. Based on these empirical observations, we conclude that a
total of 154k video samples is sufficient for attaining competitive results
within our training process.

Augmentation strategies. To validate the effectiveness of different
augmentation techniques, we randomly select identical edited pairs and apply
various augmentations to them. The results are depicted in Fig. 8(a). It’s
evident that applying only translation achieves convergence after using 30k
training samples; however, it fails to yield a satisfactory temporal
consistency. In contrast, rotation and random cropping significantly improve
performance as the training data volume increases. We attribute this to the
fact that random cropping more closely mimics real-world camera movements than
mere translation. Additionally, rotation can simulate some degree of rigid
motion. When these augmentations are combined, we demonstrates its excellence
by achieving the best consistency.

Figure 8:  (a) The Frame consistency _vs_ training size of different
augmentation strategies. (b) The Text alignment _vs_ training size of
different captions generation methods. (c) The effectiveness of different
classifier-free guidance strategies.

Caption quality. We also conduct ablation studies on the quality of the
generating captions from open-world videos. We utilize VideoBLIP as the sole
baseline to generate the captions, and the comparative results are presented
in Fig. 8 (b). Our method integrates key-frame captions from Coca and video
captions from VideoBLIP, which describe spatial and temporal aspects
respectively. It is apparent that our approach achieves an average of
approximately 2$\%$ better text alignment compared to the baseline, and this
difference widens as the training data size increases. More caption generation
results can be found in the supplementary materials.

Classifier-free guidance strategy. We evaluate the performance of various
classifier-free guidance strategies. As depicted in Fig. 8(c), setting only
text conditions with null embeddings for classifier-free guidance achieves a
relatively higher text alignment score of 38.5$\%$, but this method struggles
to maintain structural consistency in edited videos. In contrast, when only
vision conditions are set with null embeddings, it fails to deliver high-
fidelity results, scoring just 37.9$\%$ in text alignment. By decoupling the
classifier-free guidance into separate text and vision guidance components, we
observe significant improvements. This modification has led to an average
improvement of 1$\%$ across both text-alignment accuracy and temporal
consistency metrics compared to utilizing either text or vision guidance
independently.

##  5 Conclusion

This paper introduces EffiVED, an efficient instruction-based video editing
technique. We develop two innovative strategies to convert existing image
editing datasets and real-world videos into a vast collection of video editing
data. Through training on this amassed dataset, EffiVED can edit open-world
videos directly without requiring per-video fine-tuning or inversion.
Moreover, we integrate classifier-free guidance into both the video and text
conditions. Experimental results demonstrate that our method significantly
speeds up the editing process by approximately 6 to 28 times compared to
current methods while maintaining a competitive level of editing quality. We
hope our insights can help mitigate the challenge of data scarcity in the
video editing.

## References

  * [1] Abdal, R., Qin, Y., Wonka, P.: Image2stylegan: How to embed images into the stylegan latent space? In: 2019 IEEE/CVF International Conference on Computer Vision. pp. 4431–4440 (2019)
  * [2] Avrahami, O., Lischinski, D., Fried, O.: Blended diffusion for text-driven editing of natural images. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 18187–18197 (2022)
  * [3] Bar-Tal, O., Ofri-Amar, D., Fridman, R., Kasten, Y., Dekel, T.: Text2live: Text-driven layered image and video editing. In: Avidan, S., Brostow, G.J., Cissé, M., Farinella, G.M., Hassner, T. (eds.) Computer Vision - ECCV 2022 - 17th European Conference, Tel Aviv. Lecture Notes in Computer Science, vol. 13675, pp. 707–723 (2022)
  * [4] Blattmann, A., Dockhorn, T., Kulal, S., Mendelevitch, D., Kilian, M., Lorenz, D., Levi, Y., English, Z., Voleti, V., Letts, A., Jampani, V., Rombach, R.: Stable video diffusion: Scaling latent video diffusion models to large datasets. arxiv abs/2311.15127 (2023)
  * [5] Brooks, T., Holynski, A., Efros, A.A.: Instructpix2pix: Learning to follow image editing instructions. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 18392–18402 (2023)
  * [6] Brown, T.B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D.M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., Amodei, D.: Language models are few-shot learners. In: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020 (2020)
  * [7] Ceylan, D., Huang, C.P., Mitra, N.J.: Pix2video: Video editing using image diffusion. CoRR abs/2303.12688 (2023)
  * [8] Chai, W., Guo, X., Wang, G., Lu, Y.: Stablevideo: Text-driven consistency-aware diffusion video editing. CoRR abs/2308.09592 (2023)
  * [9] Crowson, K., Biderman, S., Kornis, D., Stander, D., Hallahan, E., Castricato, L., Raff, E.: VQGAN-CLIP: open domain image generation and editing with natural language guidance. In: Avidan, S., Brostow, G.J., Cissé, M., Farinella, G.M., Hassner, T. (eds.) Computer Vision - ECCV 2022 - 17th European Conference, Tel Aviv. Lecture Notes in Computer Science, vol. 13697, pp. 88–105 (2022)
  * [10] Dai, Z., Zhang, Z., Yao, Y., Qiu, B., Zhu, S., Qin, L., Wang, W.: Fine-grained open domain image animation with motion guidance. arxiv (2023). https://doi.org/10.48550/ARXIV.2311.12886, https://doi.org/10.48550/arXiv.2311.12886
  * [11] Fu, T., Wang, X.E., Grafton, S.T., Eckstein, M.P., Wang, W.Y.: M${}^{\mbox{3}}$l: Language-based video editing via multi-modal multi-level transformers. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 10503–10512 (2022)
  * [12] Geyer, M., Bar-Tal, O., Bagon, S., Dekel, T.: Tokenflow: Consistent diffusion features for consistent video editing. CoRR abs/2307.10373 (2023)
  * [13] Guo, Y., Yang, C., Rao, A., Wang, Y., Qiao, Y., Lin, D., Dai, B.: Animatediff: Animate your personalized text-to-image diffusion models without specific tuning. CoRR abs/2307.04725 (2023)
  * [14] Hertz, A., Mokady, R., Tenenbaum, J., Aberman, K., Pritch, Y., Cohen-Or, D.: Prompt-to-prompt image editing with cross-attention control. In: The Eleventh International Conference on Learning Representations (2023)
  * [15] Ho, J., Chan, W., Saharia, C., Whang, J., Gao, R., Gritsenko, A., Kingma, D.P., Poole, B., Norouzi, M., Fleet, D.J., et al.: Imagen video: High definition video generation with diffusion models. arXiv preprint arXiv:2210.02303 (2022)
  * [16] Ho, J., Saharia, C., Chan, W., Fleet, D.J., Norouzi, M., Salimans, T.: Cascaded diffusion models for high fidelity image generation. J. Mach. Learn. Res. 23, 47:1–47:33 (2022)
  * [17] Ho, J., Salimans, T.: Classifier-free diffusion guidance. CoRR abs/2207.12598 (2022)
  * [18] Ho, J., Salimans, T., Gritsenko, A., Chan, W., Norouzi, M., Fleet, D.J.: Video diffusion models. In: NeurIPS (2022)
  * [19] Hu, E.J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., Chen, W.: Lora: Low-rank adaptation of large language models. In: The Tenth International Conference on Learning Representations (2022)
  * [20] Kasten, Y., Ofri, D., Wang, O., Dekel, T.: Layered neural atlases for consistent video editing. ACM Trans. Graph. 40(6), 210:1–210:12 (2021)
  * [21] Kawar, B., Zada, S., Lang, O., Tov, O., Chang, H., Dekel, T., Mosseri, I., Irani, M.: Imagic: Text-based real image editing with diffusion models. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 6007–6017 (2023)
  * [22] Khachatryan, L., Movsisyan, A., Tadevosyan, V., Henschel, R., Wang, Z., Navasardyan, S., Shi, H.: Text2video-zero: Text-to-image diffusion models are zero-shot video generators. arXiv preprint arXiv:2303.13439 (2023)
  * [23] Kingma, D.P., Welling, M.: Auto-encoding variational bayes. In: Bengio, Y., LeCun, Y. (eds.) 2nd International Conference on Learning Representations, ICLR 2014 (2014)
  * [24] Kirstain, Y., Polyak, A., Singer, U., Matiana, S., Penna, J., Levy, O.: Pick-a-pic: An open dataset of user preferences for text-to-image generation. arxiv abs/2305.01569 (2023)
  * [25] Liu, S., Zhang, Y., Li, W., Lin, Z., Jia, J.: Video-p2p: Video editing with cross-attention control. CoRR abs/2303.04761 (2023)
  * [26] Meng, C., He, Y., Song, Y., Song, J., Wu, J., Zhu, J., Ermon, S.: Sdedit: Guided image synthesis and editing with stochastic differential equations. In: The Tenth International Conference on Learning Representations, ICLR 2022 (2022)
  * [27] Mokady, R., Hertz, A., Aberman, K., Pritch, Y., Cohen-Or, D.: Null-text inversion for editing real images using guided diffusion models. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 6038–6047 (2023)
  * [28] Molad, E., Horwitz, E., Valevski, D., Rav-Acha, A., Matias, Y., Pritch, Y., Leviathan, Y., Hoshen, Y.: Dreamix: Video diffusion models are general video editors. CoRR abs/2302.01329 (2023)
  * [29] Nichol, A., Dhariwal, P., Ramesh, A., Shyam, P., Mishkin, P., McGrew, B., Sutskever, I., Chen, M.: Glide: Towards photorealistic image generation and editing with text-guided diffusion models. arXiv preprint arXiv:2112.10741 (2021)
  * [30] Nichol, A.Q., Dhariwal, P., Ramesh, A., Shyam, P., Mishkin, P., McGrew, B., Sutskever, I., Chen, M.: GLIDE: towards photorealistic image generation and editing with text-guided diffusion models. In: Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., Sabato, S. (eds.) International Conference on Machine Learning, ICML 2022. Proceedings of Machine Learning Research, vol. 162, pp. 16784–16804
  * [31] OpenAI: GPT-4 technical report. arXiv abs/2303.08774 (2023)
  * [32] Ouyang, H., Wang, Q., Xiao, Y., Bai, Q., Zhang, J., Zheng, K., Zhou, X., Chen, Q., Shen, Y.: Codef: Content deformation fields for temporally consistent video processing. CoRR abs/2308.07926 (2023). https://doi.org/10.48550/ARXIV.2308.07926
  * [33] Park, K., Sinha, U., Barron, J.T., Bouaziz, S., Goldman, D.B., Seitz, S.M., Martin-Brualla, R.: Nerfies: Deformable neural radiance fields. In: 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021. pp. 5845–5854 (2021)
  * [34] Peebles, W., Xie, S.: Scalable diffusion models with transformers. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 4195–4205 (2023)
  * [35] Podell, D., English, Z., Lacey, K., Blattmann, A., Dockhorn, T., Müller, J., Penna, J., Rombach, R.: SDXL: improving latent diffusion models for high-resolution image synthesis. CoRR abs/2307.01952 (2023)
  * [36] Podell, D., English, Z., Lacey, K., Blattmann, A., Dockhorn, T., Müller, J., Penna, J., Rombach, R.: Sdxl: improving latent diffusion models for high-resolution image synthesis. arXiv preprint arXiv:2307.01952 (2023)
  * [37] Qi, C., Cun, X., Zhang, Y., Lei, C., Wang, X., Shan, Y., Chen, Q.: Fatezero: Fusing attentions for zero-shot text-based video editing. In: IEEE/CVF International Conference on Computer Vision, ICCV 2023. pp. 15886–15896 (2023)
  * [38] R, G., Y, A., Y, A.: An image is worth one word: Personalizing text-to-image generation using textual. arXiv preprint arXiv:2208.01618 (2022)
  * [39] Rombach, R., Blattmann, A., Lorenz, D., Esser, P., Ommer, B.: High-resolution image synthesis with latent diffusion models. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 10674–10685 (2022)
  * [40] Rombach, R., Blattmann, A., Lorenz, D., Esser, P., Ommer, B.: High-resolution image synthesis with latent diffusion models. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 10684–10695 (2022)
  * [41] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18. pp. 234–241. Springer (2015)
  * [42] Ruiz, N., Li, Y., Jampani, V., Pritch, Y., Rubinstein, M., Aberman, K.: Dreambooth: Fine tuning text-to-image diffusion models for subject-driven generation. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023. pp. 22500–22510 (2023)
  * [43] Saharia, C., Chan, W., Saxena, S., Li, L., Whang, J., Denton, E.L., Ghasemipour, K., Gontijo Lopes, R., Karagol Ayan, B., Salimans, T., et al.: Photorealistic text-to-image diffusion models with deep language understanding. Advances in Neural Information Processing Systems 35, 36479–36494 (2022)
  * [44] Singer, U., Polyak, A., Hayes, T., Yin, X., An, J., Zhang, S., Hu, Q., Yang, H., Ashual, O., Gafni, O., et al.: Make-a-video: Text-to-video generation without text-video data. arXiv preprint arXiv:2209.14792 (2022)
  * [45] Song, J., Meng, C., Ermon, S.: Denoising diffusion implicit models. In: 9th International Conference on Learning Representations (2021)
  * [46] Tumanyan, N., Geyer, M., Bagon, S., Dekel, T.: Plug-and-play diffusion features for text-driven image-to-image translation. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 1921–1930 (2023)
  * [47] Wang, J., Yuan, H., Chen, D., Zhang, Y., Wang, X., Zhang, S.: Modelscope text-to-video technical report. arXiv abs/2308.06571 (2023)
  * [48] Wang, T., Liu, M., Tao, A., Liu, G., Catanzaro, B., Kautz, J.: Few-shot video-to-video synthesis. In: Wallach, H.M., Larochelle, H., Beygelzimer, A., d’Alché-Buc, F., Fox, E.B., Garnett, R. (eds.) Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019. pp. 5014–5025 (2019)
  * [49] Wang, W., Xie, K., Liu, Z., Chen, H., Cao, Y., Wang, X., Shen, C.: Zero-shot video editing using off-the-shelf image diffusion models. arxiv abs/2303.17599 (2023)
  * [50] Wang, X., Yuan, H., Zhang, S., Chen, D., Wang, J., Zhang, Y., Shen, Y., Zhao, D., Zhou, J.: Videocomposer: Compositional video synthesis with motion controllability. arXiv preprint arXiv:2306.02018 (2023)
  * [51] Wu, J.Z., Fang, G., Wu, H., Wang, X., Ge, Y., Cun, X., Zhang, D.J., Liu, J., Gu, Y., Zhao, R., Lin, W., Hsu, W., Shan, Y., Shou, M.Z.: Towards A better metric for text-to-video generation. arxiv abs/2401.07781 (2024)
  * [52] Wu, J.Z., Ge, Y., Wang, X., Lei, S.W., Gu, Y., Shi, Y., Hsu, W., Shan, Y., Qie, X., Shou, M.Z.: Tune-a-video: One-shot tuning of image diffusion models for text-to-video generation. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 7623–7633 (2023)
  * [53] Wu, J.Z., Ge, Y., Wang, X., Lei, S.W., Gu, Y., Shi, Y., Hsu, W., Shan, Y., Qie, X., Shou, M.Z.: Tune-a-video: One-shot tuning of image diffusion models for text-to-video generation. In: IEEE/CVF International Conference on Computer Vision. pp. 7589–7599 (2023)
  * [54] Xing, Z., Dai, Q., Hu, H., Wu, Z., Jiang, Y.: Simda: Simple diffusion adapter for efficient video generation. CoRR abs/2308.09710 (2023)
  * [55] Yang, S., Zhou, Y., Liu, Z., Loy, C.C.: Rerender A video: Zero-shot text-guided video-to-video translation. In: SIGGRAPH Asia 2023 Conference Papers, SA 2023, Sydney, NSW, Australia. pp. 95:1–95:11 (2023)
  * [56] Yin, S., Wu, C., Liang, J., Shi, J., Li, H., Ming, G., Duan, N.: Dragnuwa: Fine-grained control in video generation by integrating text, image, and trajectory. arXiv preprint arXiv:2308.08089 (2023)
  * [57] Yu, J., Wang, Z., Vasudevan, V., Yeung, L., Seyedhosseini, M., Wu, Y.: Coca: Contrastive captioners are image-text foundation models. Trans. Mach. Learn. Res. (2022)
  * [58] Yu, K.P.: Videoblip: Supercharged blip-2 that can handle videos. (2023), https://github.com/yukw777/VideoBLIP
  * [59] Zhang, K., Mo, L., Chen, W., Sun, H., Su, Y.: Magicbrush: A manually annotated dataset for instruction-guided image editing. arxiv abs/2306.10012 (2023)
  * [60] Zhang, S., Wang, J., Zhang, Y., Zhao, K., Yuan, H., Qin, Z., Wang, X., Zhao, D., Zhou, J.: I2vgen-xl: High-quality image-to-video synthesis via cascaded diffusion models. arxiv abs/2311.04145 (2023)
  * [61] Zhang, Y., Wei, Y., Jiang, D., Zhang, X., Zuo, W., Tian, Q.: Controlvideo: Training-free controllable text-to-video generation. arXiv preprint arXiv:2305.13077 (2023)
  * [62] Zhuo, L., Wang, G., Li, S., Wu, W., Liu, Z.: Fast-vid2vid: Spatial-temporal compression for video-to-video synthesis. In: Avidan, S., Brostow, G.J., Cissé, M., Farinella, G.M., Hassner, T. (eds.) Computer Vision - ECCV 2022 - 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part XV. vol. 13675, pp. 289–305 (2022)


#  Mixed Hegselmann-Krause Dynamics
—nondeterministic case

Hsin-Lun Li<EMAIL_ADDRESS>
###### Abstract.

The original Hegselmann-Krause (HK) model is composed of a finite number of
agents characterized by their opinion, a number in $[0,1]$. An agent updates
its opinion via taking the average opinion of its neighbors whose opinion
differs by at most $\epsilon$ for $\epsilon>0$ a confidence bound. An agent is
absolutely stubborn if it does not change its opinion while update, and
absolutely open-minded if its update is the average opinion of its neighbors.
There are two types of HK models–the synchronous HK model and the asynchronous
HK model. The paper is about a variant of the HK dynamics, called the mixed
model, where each agent can choose its degree of stubbornness and mix its
opinion with the average opinion of its neighbors at all times. The mixed
model reduces to the synchronous HK model if all agents are absolutely open-
minded all the time, and the asynchronous HK model if only one uniformly
randomly selected agent is absolutely open-minded and the others are
absolutely stubborn at all times. In [1], we discuss the mixed model
deterministically. Point out some properties of the synchronous HK model, such
as finite-time convergence, do not hold for the mixed model. In this topic, we
study the mixed model nondeterministically. List some properties of the
asynchronous model which do not hold for the mixed model. Then, study
circumstances under which the asymptotic stability holds.

###### Key words and phrases:

mixed Hegselmann-Krause model, Cheeger’s inequality, Perron-Frobenius for
Laplacians, Courant-Fischer formula, asymptotic stability

###### 1991 Mathematics Subject Classification:

37N99, 05C50, 91C20, 93D20, 94C15

Hsin-Lun Li

School of Mathematical and Statistical Sciences,

Arizona State University, Tempe, AZ 85287, USA

##  1\. introduction

The original Hegselmann-Krause (HK) model involves a finite number of agents
characterized by their opinion, a number in $[0,1].$ Agent $i$ updates its
opinion $x_{i}$ via taking the average opinion of its neighbors whose opinion
differs by at most $\epsilon$ from $x_{i}$ for $\epsilon>0$ a confidence
bound. There are two types of HK models–the synchronous HK model and the
asynchronous HK model. For the synchronous HK model, all agents update their
opinion at each time step, whereas for the asynchronous HK model, only one
agent chosen uniformly at random updates its opinion at each time step. The
mixed model in [1] is a variant of the HK model. For the mixed model, each
agent can choose its degree of stubbornness and mix its opinion with the
average opinion of it neighbors at each update. Let $[n]=\\{1,2,\ldots,n\\}$.
The mixed model is as follows:

$x_{i}(t+1)=\alpha_{i}(t)x_{i}(t)+\frac{1-\alpha_{i}(t)}{|N_{i}(t)|}\sum_{j\in
N_{i}(t)}x_{j}(t)$ (1)

where

$\begin{array}[]{rcl}\displaystyle x_{i}(t)&=&\hbox{opinion of agent $i$ at
time $t$,}\vspace{4pt}\\\ \displaystyle
N_{i}(t)&=&\\{j\in[n]:\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\}\hbox{ is the
neighborhood of agent $i$ at time $t$},\vspace{4pt}\\\
\displaystyle\alpha_{i}(t)&\in&[0,1]\hbox{ is the degree of stubbornness of
agent $i$}\end{array}$

for all $i\in[n]$ and $t\in\mathbf{N}$. Written in matrix form,

$x(t+1)=\big{(}\operatorname{diag}(\alpha(t))+(I-\operatorname{diag}(\alpha(t)))A(t)\big{)}x(t)$

where

$\begin{array}[]{rcl}\displaystyle
x(t)&=&(x_{1}(t),\ldots,x_{n}(t))^{\prime}=\hbox{transpose of
}(x_{1}(t),\ldots,x_{n}(t)),\vspace{4pt}\\\
\displaystyle\alpha(t)&=&(\alpha_{1}(t),\ldots,\alpha_{n}(t))^{\prime}=\hbox{transpose
of }(\alpha_{1}(t),\ldots,\alpha_{n}(t)),\vspace{4pt}\\\ \displaystyle
A_{ij}(t)&=&\mathbbm{1}\\{j\in N_{i}(t)\\}/|N_{i}(t)|.\end{array}$

In particular, (1) reduces to

  * •

the synchronous HK model if $\alpha(t)=\vec{0}$ for all $t\geq 0$, and

  * •

the asynchronous HK model if $\alpha(t)=(\mathbbm{1}\\{k\neq
i(t)\\})_{k=1}^{n}$ for all $t\geq 0$ and for some uniformly randomly selected
$i(t)\in[n]$.

Say agent $i$ at time $t$ is

  * •

absolutely stubborn if $\alpha_{i}(t)=1$,

  * •

not absolutely stubborn, or open-minded if $\alpha_{i}(t)<1$, and

  * •

absolutely open-minded if $\alpha_{i}(t)=0$.

In [1], we study the mixed model deterministically and point out some
properties of the synchronous HK model, such as finite-time convergence, do
not hold for the mixed model. Here, we assume that

$U_{t}=\\{i\in[n]:\alpha_{i}(t)<1\\}\hbox{ for all }t\geq 0$

are independent and identically distributed random variables with a support
$S\subset\mathscr{P}([n])$ containing a partition of $[n]$, say
$\\{K_{i}\\}_{i=1}^{s}$, where $\mathscr{P}([n])$ is the power set of $[n]$.
Let $(\Omega,\mathscr{F},P)$ be a probability space for
$\mathscr{F}\subset\mathscr{P}(\Omega)$ a $\sigma$-algebra and $P$ a
probability measure. Observe that the asynchronous HK model is a particular
case where the support $S=\\{\\{i\\}\\}_{i=1}^{n}$ is also a partition of
$[n]$ and $U_{t}$ are uniform random variables on $S$, denoted by
$U_{t}=\operatorname{uniform}{(S)}$, for all $t\geq 0$.

######  Definition 1.

A _profile_ at time $t$ is an undirected graph $\mathscr{G}(t)$ with the
vertex set and edge set

$\mathscr{V}(t)=[n]\quad\hbox{and}\quad\mathscr{E}(t)=\\{ij:i\neq j\hbox{ and
}\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\}.$

######  Definition 2.

A profile $\mathscr{G}(t)$ is $\delta$-trivial if any two of its vertices are
at a distance of at most $\delta$ apart.

Denote almost surely by a.s., which may be omitted for simplicity. The
theorems and corollary in [1] can be interpreted nondeterministically as
follows.

######  Theorem 1 ([1]).

Let

$\beta_{t}:=\max_{i,j\in[n],\alpha_{i}(t)\geq\alpha_{j}(t)}\bigg{(}\alpha_{i}(t)-\frac{\alpha_{i}(t)-\alpha_{j}(t)}{n}\bigg{)}.$

Assume that $\limsup_{t\to\infty}\beta_{t}<1$ a.s. and that $\mathscr{G}(t)$
is $\epsilon$-trivial a.s.. Then,

$\lim_{t\to\infty}\max_{i,j\in[n]}\|x_{i}(t)-x_{j}(t)\|=0\hbox{ a.s.}.$

For an $\epsilon$-trivial profile, agents need not play open-minded all the
time. As long as there are infinitely many $\beta_{t}$ having an upper bound
less than 1, eventually can a consensus be achieved. Given an
$\epsilon$-trivial profile of the synchronous HK model, it is clear that a
consensus can be achieved at the next time step. Observe that
$\limsup_{t\to\infty}\beta_{t}<1$ automatically holds for the asynchronous HK
model; therefore a consensus can be achieved eventually given an
$\epsilon$-trivial profile.

######  Theorem 2 ([1]).

Define $d_{t}^{i}=\max_{j\in N_{i}(t)}\|x_{i}(t)-x_{j}(t)\|$. If

$\sum_{t=0}^{\infty}\
(1-\alpha_{i}(t))\bigg{(}1-\frac{1}{|N_{i}(t)|}\bigg{)}d_{t}^{i}<\infty\hbox{
a.s.},\ \hbox{then}\ x_{i}(t)\to x_{i}\in\mathbf{R^{d}}\ \hbox{as}\
t\to\infty\hbox{ a.s..}$

It is difficult to track the dynamics trajectories. Nevertheless, $\alpha_{i}$
is controllable and $\big{(}1-\frac{1}{|N_{i}(t)|}\big{)}d_{t}^{i}$ is
bounded. Therefore, the assumption of Theorem 2 holds as long as $\sum_{t\geq
0}(1-\alpha_{i}(t))<\infty.$ Namely, an agent can achieve its opinion limit
without considering the others.

######  Theorem 3 ([1]).

Assume that $\limsup_{t\to\infty}\max_{i\in[n]}\alpha_{i}(t)<1$ a.s.. Then,
for any $\delta>0$, every component of a profile is $\delta$-trivial in finite
time a.s., i.e.,

$\tau_{\delta}:=\inf\\{t\geq 0:\hbox{every component of $\mathscr{G}(t)$ is
$\delta$-trivial}\\}<\infty\hbox{ a.s.}.$

All components of a profile is $\delta$-trivial in finite time as long as all
agents are open-minded infinitely many times and their degree of stubbornness
has an upper bound less than 1.

######  Corollary 1 ([1]).

Assume that $\sup_{t\in\mathbf{N}}\max_{i\in[n]}\alpha_{i}(t)<1$ a.s.. Then,
$\tau_{\delta}$ is bounded from above a.s.. Also, letting
$\hat{\tau}_{m}=\tau_{\epsilon/m}$ for $m\geq 4$, there is no interactions
between any two components of $\mathscr{G}(t)$ at the next time step for some
$M\geq 4$ and for all $t\geq\hat{\tau}_{M}$ a.s., i.e.,

$\mathscr{G}(t)=\mathscr{G}(\hat{\tau}_{M})\quad\hbox{for some}\quad M\geq
4\quad\hbox{and for all}\quad t\geq\hat{\tau}_{M}\hbox{ a.s.}.$

In particular, $x$ in (1) is asymptotically stable a.s..

All components of a profile are $\delta$-trivial by some finite time given
that all agents are open-minded and their degree of stubbornness has an upper
bound less than 1 all the time.

##  2\. main results

For Theorems 1, 3 and Corollary 1, the assumptions involve the whole agents.
However, the following results, such as asymptotic stability, hold without
considering the absolutely stubborn who can vary over time. In particular, the
following results can interpret the asynchronous HK model.

######  Theorem 4.

Assume that $0\leq\limsup_{t\to\infty}\sup\\{\alpha_{i}(t):i\in[n]\hbox{ and
}\alpha_{i}(t)<1\\}<\gamma<1$ for some $\gamma$ constant a.s.. Then, for any
$\delta>0,$ all components of a profile are $\delta$-trivial in finite time
a.s., i.e.,

$\tau_{\delta}:=\inf\\{t\geq 0:\hbox{all components of $\mathscr{G}(t)$ is
$\delta$-trivial}\\}<\infty\hbox{ a.s.}.$

All components of a profile are $\delta$-trivial in finite time given that
there are open-minded agents infinitely many times and their degree of
stubbornness has a constant upper bound less than 1.

######  Corollary 2.

Assume that $0\leq\sup\\{\alpha_{i}(t):i\in[n]\hbox{ and
}\alpha_{i}(t)<1\\}\leq\gamma<1$ for some $\gamma$ constant a.s.. Then,
$E(\tau_{\delta})$ is bounded from above. Also, letting
$\hat{\tau}_{m}=\tau_{\epsilon/m}$ for $m\geq 4$, there is no interactions
between any two components of $\mathscr{G}(t)$ at the next time step for some
$M\geq 4$ and for all $t\geq\hat{\tau}_{M}$ a.s., i.e.,

$\mathscr{G}(t)=\mathscr{G}(\hat{\tau}_{M})\quad\hbox{for some}\quad M\geq
4\quad\hbox{and for all}\quad t\geq\hat{\tau}_{M}\hbox{ a.s.}.$

In particular, $x$ in (1) is asymptotically stable a.s..

The expected number of time steps until all components of a profile is
$\delta$-trivial is bounded from above. It turns out that for nondeterministic
mixed model, still can the results, such as asymptotic stability, hold without
considering the absolutely stubborn.

##  3\. the mixed model

######  Definition 3.

The _termination time_ of $n$ agents, $T_{n}$, is the maximum number of
iterations in (1) by reaching a steady state over all initial profiles, i.e.,

$T_{n}=\inf\\{t\geq 0:x(t)=x(s)\ \hbox{for all}\ s\geq t\\}.$

######  Definition 4.

A _merging time_ is a time $t$ that two agents with different opinions at time
$t-1$ have the same opinion at time $t$, i.e.,

$x_{i}(t)=x_{j}(t)\quad\hbox{and}\quad x_{i}(t-1)\neq x_{j}(t-1)\quad\hbox{for
some}\quad i,j\in[n].$

######  Definition 5.

The _convex hull_ generated by $v_{1},v_{2},\ldots,v_{n}\in\mathbf{R^{d}}$ is
the smallest convex set containing $v_{1},v_{2},\ldots,v_{n}$, i.e.,

$C(\\{v_{1},v_{2}\ldots,v_{n}\\})=\\{v:v=\sum_{i=1}^{n}\lambda_{i}v_{i}\
\hbox{where}\ (\lambda_{i})_{i=1}^{n}\ \hbox{is stochastic}\\}.$

######  Definition 6.

For $\delta>0$, $x(t)$ in (1) is a _$\mathbf{\delta}$ -equilibrium_ if there
is a partition

$\\{G_{1},G_{2},\ldots,G_{m}\\}\ \hbox{of the set}\
\\{x_{1}(t),x_{2}(t),\ldots,x_{n}(t)\\}$

such that the following two conditions hold:

$\operatorname{dist}(C(G_{i}),C(G_{j}))>\epsilon\ \hbox{for all}\ i\neq
j\quad\hbox{and}\quad\operatorname{diam}(C(G_{i}))\leq\delta\ \hbox{for all}\
i\in[m].$

[1] lists three properties distinct from the synchronous HK model.

  1. (1)

The termination time is not finite.

  2. (2)

Agents merging at time $t$ may depart at time $t+1$. In particular,
$\mathscr{G}(t)$ $\epsilon$-trivial may not imply that $x(t+1)$ in (1) is a
steady state.

  3. (3)

A $\delta$-equilibrium may not exist for all $0<\delta\leq\epsilon$.

The following are properties differing from the asynchronous HK model.

######  Property 1.

Merging can exist.

######  Example 1.

Consider $x_{1}(0)=0,\ x_{2}(0)=\epsilon,\ \alpha_{1}(0)=0\hbox{ and
}\alpha_{2}(0)=0$. Then, $x_{1}$ and $x_{2}$ merge at time $t=1$.

######  Property 2.

A $\delta$-equilibrium may not exist for all $0<\delta\leq\epsilon.$

######  Example 2.

See Example 3 in [1].

######  Lemma 1 ([1]).

Let $Z(t)=\sum_{i,j\in[n]}\|x_{i}(t)-x_{j}(t)\|^{2}\wedge\epsilon^{2}.$ Then,
$Z$ is nonincreasing with respect to $t$. In particular,

$\begin{array}[]{rcl}\displaystyle Z(t)-Z(t+1)&\geq&\displaystyle
4\sum_{i=1}^{n}\bigg{(}1+|N_{i}(t)|\frac{\alpha_{i}(t)}{1-\alpha_{i}(t)}\mathbbm{1}\\{\alpha_{i}(t)<1\\}\bigg{)}\|x_{i}(t)-x_{i}(t+1)\|^{2}.\end{array}$

######  Definition 7.

A symmetric matrix $M$ is called a _generalized Laplacian_ of a graph
$G=(V,E)$ if for $x,y\in V$, the following two conditions hold:

$M_{xy}=0\ \hbox{for}\ x\neq y\ \hbox{and}\ xy\notin E\quad\hbox{and}\quad
M_{xy}<0\ \hbox{for}\ x\neq y\ \hbox{and}\ xy\in E.$

Let $d_{G}(x)$ = degree of $x$ in $G$, let $V(G)$ = vertex set of $G$, and let
$E(G)$ = edge set of $G$. Then, the _Laplacian_ of $G$ is defined as
$\mathscr{L}=D_{G}-A_{G}$ where

$D_{G}=\operatorname{diag}((d_{G}(x))_{x\in V(G)})\quad\hbox{and}\quad A_{G}=\
\hbox{the adjacency matrix}.$

In particular, $(A_{G})_{xy}=\mathbbm{1}\\{xy\in E(G)\\}$ when the graph $G$
is simple.

Observe that there is no restrictions on the diagonal entries of the matrix
$M$. Moreover, the Laplacian of $G$ is a generalized Laplacian.

###### Proof of Theorem 4.

By the assumption, there is $(t_{k})_{k\geq 1}\subset\mathbf{N}$ strictly
increasing such that $\max\\{\alpha_{i}(t_{k}):i\in[n]\hbox{ and
}\alpha_{i}(t_{k})<1\\}<\gamma_{1}$ for some $\gamma<\gamma_{1}<1$ constant
and for all $k\geq 1$. For all $m\geq 1$,

$n^{2}\epsilon^{2}>Z(0)\geq Z(0)-Z(m)=\sum_{t=0}^{m-1}[Z(t)-Z(t+1)].$ (2)

Letting $m\to\infty$ and applying Lemma 1,

$n^{2}\epsilon^{2}\geq\sum_{t\geq 0}[Z(t)-Z(t+1)]\geq 4\sum_{t\geq
0}\sum_{i\in[n],\alpha_{i}(t)<1}\|x_{i}(t)-x_{i}(t+1)\|^{2}.$

Set $\tau=\tau_{\delta}$. Assume by contradiction that $\tau=\infty$ on some
$E\in\mathscr{F}$ with $P(E)>0$. Taking expectation on both sides on $E$,
denoted by $E_{E}$,

$\displaystyle n^{2}\epsilon^{2}\ $ $\displaystyle\geq\ 4\sum_{t\geq
0}\sum_{j=1}^{s}E_{E}\bigg{(}\sum_{i\in[n],\alpha_{i}(t)<1}\|x_{i}(t)-x_{i}(t+1)\|^{2}\bigg{|}U_{t}=K_{j}\bigg{)}P(U_{t}=K_{j})$
$\displaystyle=\ 4\sum_{t\geq
0}\sum_{j=1}^{s}P(U_{t}=K_{j})E_{E}\bigg{(}\sum_{i\in
K_{j}}\|x_{i}(t)-x_{i}(t+1)\|^{2}\bigg{)}$ $\displaystyle\geq\
4\min_{j\in[s]}P(U_{0}=K_{j})\sum_{t\geq
0}E_{E}\bigg{(}\sum_{j=1}^{s}\sum_{i\in
K_{j}}\|x_{i}(t)-x_{i}(t+1)\|^{2}\bigg{)}$ $\displaystyle=\
4\min_{j\in[s]}P(U_{0}=K_{j})\sum_{t\geq
0}E_{E}\bigg{(}\sum_{i=1}^{n}\|x_{i}(t)-x_{i}(t+1)\|^{2}\bigg{)}$
$\displaystyle>\ 4\min_{j\in[s]}P(U_{0}=K_{j})\sum_{t\geq
0}E_{E}\bigg{(}\frac{2\delta^{2}(1-\max_{i\in[n]}\alpha_{i}(t))^{2}}{n^{8}}\bigg{)}$
(+) $\displaystyle\geq\ 4\min_{j\in[s]}P(U_{0}=K_{j})E_{E}\bigg{(}\sum_{k\geq
1}\frac{2\delta^{2}(1-\max_{i\in[n]}\alpha_{i}(t_{k}))^{2}}{n^{8}}\bigg{)}$
$\displaystyle\geq\ 4\min_{j\in[s]}P(U_{0}=K_{j})\sum_{k\geq
1}E_{E}\bigg{(}\frac{2\delta^{2}(1-\gamma_{1})^{2}}{n^{8}}\bigg{)}=\infty,\hbox{
a contradiction,}$

where (+ ‣ 3) refers to the proof of Theorem 3 in [1]. Therefore, $\tau$ is
finite.

∎

###### Proof of Corollary 2.

Since the assumption of Corollary 2 meets that of Theorem 4, $\tau$ is finite
a.s.. Setting $m=\tau$ in (2) and applying Lemma 1,

$n^{2}\epsilon^{2}>\sum_{t=0}^{\tau-1}[Z(t)-Z(t+1)]\geq
4\sum_{t=0}^{\tau-1}\sum_{i\in[n],\alpha_{i}(t)<1}\|x_{i}(t)-x_{i}(t+1)\|^{2}.$

Similarly as (+ ‣ 3),

$\displaystyle n^{2}\epsilon^{2}>$ $\displaystyle\
4\min_{j\in[s]}P(U_{0}=K_{j})E\bigg{(}\sum_{t=0}^{\tau-1}\frac{2\delta^{2}(1-\max_{i\in[n]}\alpha_{i}(t))^{2}}{n^{8}}\bigg{)}$
$\displaystyle\geq$ $\displaystyle\
4\min_{j\in[s]}P(U_{0}=K_{j})E\bigg{(}\frac{2\tau\delta^{2}(1-\gamma)^{2}}{n^{8}}\bigg{)}$

therefore

$E(\tau)<\frac{n^{10}}{8(1-\gamma)^{2}\min_{j\in[s]}P(U_{0}=K_{j})}(\frac{\epsilon}{\delta})^{2}.$

Hence, $E(\tau)$ is bounded from above.

To show the asymptotic stability of $x$, first observe that $\hat{\tau}_{m}$
is finite and nondecreasing with respect to $m$. For all
$0<\delta\leq\epsilon/4$ and $t\geq 0$, the following conditions are
equivalent given that every component of $\mathscr{G}(t)$ is $\delta$-trivial:

  1. (1)

Some component of $\mathscr{G}(t+1)$ is $\delta$-nontrivial.

  2. (2)

Some components of $\mathscr{G}(t)$ interact at time $t+1$.

  3. (3)

Some component of $\mathscr{G}(t+1)$ is $\epsilon/2$-nontrivial.

It is clear that 1 $\Rightarrow$ 2 and 3 $\Rightarrow$ 1; therefore we show 2
$\Rightarrow$ 3.

###### Proof of 2 $\Rightarrow$ 3.

Let the convex hull of a component $G$ be

$Cv(G)=C(\\{x_{j}:j\in V(G)\\}).$

The fact that some components of $\mathscr{G}(t)$ interact at time $t+1$
implies that there exist

$i,j\in[n]\quad\hbox{with}\quad ij\in\mathscr{E}(t+1),\quad\quad i\in
V(G_{\tilde{i}})\quad\hbox{and}\ j\in V(G_{\tilde{j}})$

for some distinct components $G_{\tilde{i}}$ and $G_{\tilde{j}}$ of
$\mathscr{G}(t)$. Therefore,

$x_{i}(t+1)\in Cv(G_{\tilde{i}})\quad\hbox{and}\quad x_{j}(t+1)\in
Cv(G_{\tilde{j}}).$

Hence,

$\displaystyle\epsilon\ <\ $ $\displaystyle\|x_{i}(t)-x_{j}(t)\|$
$\displaystyle\ \leq\ $
$\displaystyle\|x_{i}(t)-x_{i}(t+1)\|+\|x_{i}(t+1)-x_{j}(t+1)\|+\|x_{j}(t+1)-x_{j}(t)\|$
$\displaystyle\ \leq\ $
$\displaystyle\delta+\|x_{i}(t+1)-x_{j}(t+1)\|+\delta=\|x_{i}(t+1)-x_{j}(t+1)\|+2\delta.$

This implies that

$\|x_{i}(t+1)-x_{j}(t+1)\|>\epsilon-2\delta\geq\epsilon-2\cdot\frac{\epsilon}{4}=\frac{\epsilon}{2}\quad\hbox{for
all}\quad 0<\delta\leq\frac{\epsilon}{4}$

so the component of $\mathscr{G}(t+1)$ containing $ij$ is
$\epsilon/2$-nontrivial. ∎

Let

$A_{m}=\\{t\in[\hat{\tau}_{m},\hat{\tau}_{m+1}):\hbox{some component of
$\mathscr{G}(t)$ is $\epsilon/m$-nontrivial}\\}$

and $t_{m}=\inf A_{m}$.

$\hbox{Claim:}\quad\hbox{the set}\
\mathscr{A}:=\\{t_{k}:A_{k}\neq\varnothing\\}\ \hbox{is finite a.s.}.$

For $t_{m}\in\mathscr{A}$, since some component of $\mathscr{G}(t_{m})$ is
$\epsilon/m$-nontrivial and all components of $\mathscr{G}(t_{m}-1)$ are
$\epsilon/m$-trivial, by 1$\Rightarrow$ 3, some component of
$\mathscr{G}(t_{m})$ is $\epsilon/2$-nontrivial. Similarly as (+ ‣ 3), we get

$\displaystyle n^{2}\epsilon^{2}\ \geq\ $ $\displaystyle
4\min_{j\in[s]}P(U_{0}=K_{j})E\bigg{(}\sum_{t\in\mathscr{A}}\frac{2(\epsilon/2)^{2}(1-\max_{i\in[n]}\alpha_{i}(t))^{2}}{n^{8}}\bigg{)}$
$\displaystyle\geq\ $ $\displaystyle
4\min_{j\in[s]}P(U_{0}=K_{j})E\bigg{(}\sum_{t\in\mathscr{A}}\frac{2(\epsilon/2)^{2}(1-\gamma)^{2}}{n^{8}}\bigg{)}$
$\displaystyle=\ $ $\displaystyle
E(|\mathscr{A}|)\frac{2\epsilon^{2}(1-\gamma)^{2}}{n^{8}}\min_{j\in[s]}P(U_{0}=K_{j}),$

from which it follows that

$E(|\mathscr{A}|)\leq\frac{n^{10}}{2(1-\gamma)^{2}\min_{j\in[s]}P(U_{0}=K_{j})}.$

Hence, the set $\mathscr{A}$ is finite a.s.. By the fact that $\mathscr{A}$ is
finite and that 2$\Rightarrow$ 1, there is no interactions between any two
components of $\mathscr{G}(s)$ at the next time step for some $M\geq 4$ and
for all $s\geq\hat{\tau}_{M}$. Hence, all components of
$\mathscr{G}(\hat{\tau}_{M})$ are independent systems. Therefore, $x$ in (1)
is asymptotically stable.

∎

Note that Corollary 2 particularly verifies that the asymptotic stability
holds for the asynchronous HK model. Theorem 5 in [2] states that the expected
number of steps until all agents in the asynchronous HK model reach a
$\delta$-equilibrium is bounded from above. Therefore, asymptotic stability
holds for the asynchronous HK model. In fact, a $\delta$-equilibrium is not
necessary for asymptotic stability. Since the assumption of Theorem 3
automatically holds for the asynchronous HK model, there is no interactions
between any two components of $\mathscr{G}(t)$ at the next time step for some
$M\geq 4$ and for all $t\geq\hat{\tau}_{M}$ a.s.; therefore asymptotic
stability holds. Also, the assumption of Corollary 2 automatically holds for
the asynchronous HK model; therefore $E(\hat{\tau}_{M})$ is bounded from
above.

##  4\. conclusion

The mixed model covers both the synchronous HK model and the asynchronous HK
model. Each agent can decide its degree of stubbornness and mix its opinion
with the average opinion of its neighbors at all times. Compared to the HK
dynamics in which an agent is either absolutely stubborn or absolutely open-
minded, agents for the mixed model are more flexible and closer to reality,
making it harder to attain asymptotic stability. We elaborate in [1] that the
synchronous HK model is in fact a particular case of the deterministic mixed
model. In this theme, we illustrate that the asynchronous model is in fact a
particular case of the nondeterministic mixed model. Furthermore, under some
circumstances the asymptotic stability can hold without considering the
absolutely stubborn for the nondeterministic mixed model.

## References

  * [1] H. Li,  Mixed Hegselmann-Krause Dynamics,  _Discrete and Continuous Dynamical Systems-B_ , (2021), https://arxiv.org/abs/2010.03050
  * [2] S. R. Etesami and T. Basar,  Game-theoretic analysis of the Hegselmann-Krause model for Opinion dynamics in finite dimensions,  _IEEE Transactions on Automatic Control_ , 60 (2015), 1886–1897.
  * [3] L. W. Beineke, P. J. Cameron and R. J. Wilson,  _Topics in Algebraic Graph Theory_ ,  Cambridge University Press, Cambridge, UK, 2004.
  * [4] T. Biyikoglu, J. Leydold and P. F. Stadler,  _Laplacian Eigenvectors of Graphs: Perron-Frobenius and Faber-Krahn Type Theorems,_ Springer-Verlag, Berlin Heidelberg, 2007.
  * [5] R. A. Horn and C. R. Johnson,  _Matrix Analysis,_ Cambridge University Press, Cambridge, 2013.


# Equivalent characterizations
of non-Archimedean uniform spaces

Daniel Windisch  Institut für Analysis und Zahlentheorie
Technische Universität Graz
Kopernikusgasse 24/II
8010 Graz
Austria<EMAIL_ADDRESS>
###### Abstract.

In this paper, we deal with uniform spaces whose diagonal uniformity admits a
basis consisting of equivalence relations. Such non-Archimedean uniform spaces
are particularly interesting for applications in commutative ring theory,
because uniformities stemming from valuations or directed systems of ideals
are of this type.
In general, apart from diagonal uniformities, there are two further approaches
to the concept of uniform spaces: covering uniformities and systems of pseudo-
metrics. For each of these ways of defining a uniformity, we isolate a non-
Archimedean special case and show that these special cases themselves are
equivalent to the notion of non-Archimedean diagonal uniformities.
Moreover, we formulate a seperation axiom for topological spaces $X$ that
tells exactly when the topology on $X$ is induced by a non-Archimedean
uniformity. In analogy to the classical metrizability theorems, we
characterize when a non-Archimedean uniformity comes from a single pseudo-
metric.

D. Windisch is supported by the Austrian Science Fund (FWF): P 30934

Mathematics subject classification: primary: 54E15; secondary 13J99, 22A99

Key words and phrases: uniform space, non-Archimedean uniformity, non-
Archimedean pseudo-metric, separation axiom, metrizability, $I$-adic topology

##  1\. Introduction

Throughout this work, let $X$ be a set. Recall that a diagonal uniformity
$\mathfrak{D}$ on $X$ is a non-empty collection of relations (called
entourages) on $X$ satisfying certain axioms. A basis $\mathcal{B}$ of
$\mathfrak{D}$ is a subset of $\mathfrak{D}$ such that every entourage in
$\mathfrak{D}$ contains an element of $\mathcal{B}$. For a general
introduction to uniform spaces, see [5].
Following Monna [4], who noticed that a non-Archimedean metric induces the
following special type of uniformity, a diagonal uniformity $\mathfrak{D}$ on
$X$ is called non-Archimedean, if it has a basis $\mathcal{B}$ consisting of
equivalence relations. In many settings, especially in commutative algebra and
Abelian group theory, non-Archimedean uniformities are used extensively. For
instance, the completion of a commutative ring $R$ with respect to a valuation
or a directed system of ideals is a special case of the more general concept
of completions of uniform spaces, and the original uniformity defined on $R$
is non-Archimedean (cf. [1, Chapter 10]). In this context, one often freely
uses the correspondence of diagonal uniformities, covering uniformities and
systems of pseudometrics. So the following question arises naturally:

Question. Is it possible to characterize those covering uniformities and
systems of pseudo-metrics, respectively, that correspond to non-Archimedean
diagonal uniformities?

One goal of this article is therefore to isolate special cases in the
definitions of uniform structures via uniform covers and systems of pseudo-
metrics, respectively, such that these special cases are equivalent to the
notion of non-Archimedean diagonal uniformities. A main result is

######  Theorem 1.

For a diagonal uniformity $\mathfrak{D}$ on $X$ the following are equivalent:

  * (A)

$\mathfrak{D}$ is non-Archimedean.

  * (B)

There exists a system $M$ of non-Archimedean pseudo-metrics on $X$ that
induces the uniformity $\mathfrak{D}$ (see Remark 2.3).

  * (C)

The corresponding covering uniformity $\mu_{\mathfrak{D}}$ of $\mathfrak{D}$
(see Remark 2.1) has a basis consisting of partitions of $X$.

It is well-known that uniformizability for a topological space is equivalent
to T${}_{3\frac{1}{2}}$ (Willard [5] uses the term completely regular for
T${}_{3\frac{1}{2}}$). We give a similar theorem for non-Archimedean
uniformizability using a stronger version of this seperation axiom:

######  Theorem 2.

A topological space $X$ is uniformizable by a non-Archimedean uniformity if
and only if it satisfies $\text{T}_{\text{A}}$, i.e. for every closed subset
$A\subseteq X$ and every $x\in X\setminus A$ there are open sets
$U_{1},U_{2}\subseteq X$ such that

  * (i)

$U_{1}\cap U_{2}=\emptyset$, $U_{1}\cup U_{2}=X$,

  * (ii)

$A\subseteq U_{1}$, $x\in U_{2}$.

Moreover, we are able to characterize the case when a non-Archimedean uniform
space is pseudo-metrizable by a single non-Archimedian pseudo-metric. Results
closely related to ours were given by Monna [4, Théorème 13], Banaschewski [2,
Satz 6] and De Groot [3, Theorem II], but these authors assume uniformities to
be seperating (i.e., the induced topology is Hausdorff) and therefore
formulate stronger results dealing with metrizability. Our theorem is similar
to the general case, where a uniform space is pseudo-metrizable if and only if
there is a countable system of pseudo-metrics inducing the uniformity (cf. [5,
Theorem 38.3]), but the method used there does not apply to our set-up.

######  Theorem 3.

A uniformity is pseudo-metrizable by a single non-Archimedean pseudo-metric if
and only if it is induced by a countable system of non-Archimedean pseudo-
metrics.

Overview of Results
---
|  General uniform space |  non-Arch. uniform space
Diagonal uniformity |  Basis of relations |  Basis of equivalence rel.
Covering uniformity |  Basis of covers |  Basis of partitions
Pseudo-metrics |  System of pseudo-metrics |  System of non-Arch. pseudo-metrics
Uniformizability |  $\text{T}_{3\frac{1}{2}}$ |  $\text{T}_{\text{A}}$
Pseudo-metrizability |  countable system of pseudo-metrics |  countable system of non-Arch. pseudo-metrics

##  2\. Equivalent approaches to non-Archimedean uniform spaces

###  2.1. Covering uniformities

The isolation of the desired special case is very easy in the setting of
covering uniformities, as we can explicitly write down a bijection between
diagonal uniformities and covering uniformities on $X$.

######  Remark 2.1.

How to construct a covering uniformity out of a diagonal uniformity and vice
versa.

  * (1)

Let $\mathfrak{D}$ be a diagonal uniformity on $X$, and let $\mathcal{B}$ be a
basis of $\mathfrak{D}$. For $x\in X$ and $D\in\mathcal{B}$, let
$D[x]:=\\{y\in X\mid(x,y)\in D\\}$ and $\mathcal{U}_{D}:=\\{D[x]\mid x\in
X\\}$. Then $\beta_{\mathfrak{D}}:=\\{\mathcal{U}_{D}\mid D\in\mathcal{B}\\}$
is a basis of a covering uniformity $\mu_{\mathfrak{D}}$ on $X$, and
$\mu_{\mathfrak{D}}$ is independent of the choice of $\mathcal{B}$.

  * (2)

Let $\beta$ be a basis of a covering uniformity $\mu$ on $X$. For
$\mathcal{U}\in\beta$, we define $D_{\mathcal{U}}:=\\{(x,y)\in X\times
X\mid\exists U\in\mathcal{U}:x,y\in U\\}$. Then
$\mathcal{B}_{\mu}:=\\{D_{\mathcal{U}}\mid\mathcal{U}\in\beta\\}$ is a basis
of a diagonal uniformity $\mathfrak{D}_{\mu}$ on $X$, and $\mathfrak{D}_{\mu}$
is independent of the choice of $\beta$.

  * (3)

The maps $\mathfrak{D}\mapsto\mu_{\mathfrak{D}}$,
$\mu\mapsto\mathfrak{D}_{\mu}$ are bijections of the set of all diagonal
uniformities on $X$ and the set of all covering uniformities on $X$ which are
inverse to each other.

######  Lemma 2.2.

  * (1)

If $\mathfrak{D}$ is non-Archimedean, then $\mu_{\mathfrak{D}}$ has a basis
consisting of partitions.

  * (2)

If $\mu$ has a basis consisting of partitions, then $D_{\mu}$ is non-
Archimedean.

  * (3)

The maps in remark 2.1.1 restrict to bijections of non-Archimedean diagonal
uniformities and covering uniformities having a basis consisting of
partitions.

###### Proof.

  * (1)

Let $\mathcal{B}\subseteq\mathfrak{D}$ be a basis consisting of equivalence
relations. Then, for all $D\in\mathcal{B}$, we have that
$\mathcal{U}_{D}=\\{D[x]\mid x\in X\\}$ is a partition of $X$.

  * (2)

Let $\beta\subseteq\mu$ be a basis consisting of partitions of $X$. For
$\mathcal{U}\in\beta$, $D_{\mathcal{U}}=\\{(x,y)\in X\times X\mid\exists
U\in\mathcal{U}:x,y\in U\\}$ is an equivalence relation.

  * (3)

is an immediate consequence of (1) and (2).

∎

###  2.2. Pseudo-metrics

The systems of pseudo-metrics on $X$ are not in general in one-to-one
correspondence with the diagonal uniformities on $X$. Anyway, we can consider
systems of pseudo-metrics up to equivalence:

######  Remark 2.3.

  * (1)

Let $M$ be a system of pseudo-metrics on $X$. For every $d\in M$ and every
$\varepsilon\in\mathbb{R}_{>0}$ we consider the binary relation
$D_{\varepsilon}^{d}:=\\{(x,y)\in X\times X\mid d(x,y)<\varepsilon\\}$. The
set $\mathcal{B}_{M}:=\\{D_{\varepsilon}^{d}\mid d\in M,\
\varepsilon\in\mathbb{R}_{>0}\\}$ is a basis of a diagonal uniformity on $X$,
denoted by $\mathfrak{D}_{M}$.

  * (2)

Two systems $M$ and $N$ of pseudo-metrics on $X$ are said to be equivalent, if
$\mathfrak{D}_{M}=\mathfrak{D}_{N}$.

  * (3)

A pseudo-metric $d$ on $X$ is said to be non-Archimedean if it satisfies the
non-Archimedean triangle inequality, i.e. for all $x,y,z\in X$ we have

$\displaystyle d(x,y)\leq max(d(x,z),d(z,y)).$

######  Proposition 2.4.

  * (1)

If $d_{1}$ and $d_{2}$ are non-Archimedean pseudo-metrics on $X$, then so is
$d=sup(d_{1},d_{2})$.

  * (2)

If $M$ is a system of non-Archimedean pseudo-metrics, then $\mathcal{B}_{M}$
consists of equivalence relations. In particular, $\mathfrak{D}_{M}$ is non-
Archimedean.

###### Proof.

  * (1)

Let $x,y,z\in X$. Then we have

$\displaystyle d(x,y)$ $\displaystyle=max(d_{1}(x,y),d_{2}(x,y))$
$\displaystyle\leq max(max(d_{1}(x,z),d_{1}(z,y)),max(d_{2}(x,z),d_{2}(z,y)))$
$\displaystyle=max(d_{1}(x,z),d_{2}(x,z),d_{1}(z,y),d_{2}(z,y))$
$\displaystyle=max(max(d_{1}(x,z),d_{2}(x,z)),max(d_{1}(z,y),d_{2}(z,y)))$
$\displaystyle=max(d(x,z),d(z,y)).$

So $d$ is non-Archimedean.

  * (2)

Let $\varepsilon\in\mathbb{R}_{>0}$ and $d\in M$. Clearly,
$D_{\varepsilon}^{d}$ is reflexive and symmetric. So let $(x,z),(z,y)\in
D_{\varepsilon}^{d}$. Then $d(x,y)\leq max(d(x,z),d(z,y))<\varepsilon$, which
means that $(x,y)\in D_{\varepsilon}^{d}$.

∎

The next proposition in particular shows that every system of pseudo-metrics,
that induces a non-Archimedean diagonal uniformity, is equivalent to a system
of non-Archimedean pseudo-metrics. In the proof, we give an explicit
construction of a system of pseudo-metrics using a basis consisting of
equivalence relations which is very intuitive. In the general case, the
construction of pseudo-metrics based on relations is much more involved, since
the relations need not even be symmetric.

######  Proposition 2.5.

If $\mathfrak{D}$ is a non-Archimedean diagonal uniformity on $X$, then there
exists a system $M$ of non-Archimedean pseudo-metrics on $X$ such that
$\mathfrak{D}=\mathfrak{D}_{M}$.

###### Proof.

Let $\mathcal{B}\subseteq\mathfrak{D}$ be a basis consisting of equivalence
relations and consider the set

$\displaystyle AK(\mathcal{B}):=\\{(D_{n})_{n\in\mathbb{N}}\mid D_{1}=X\times
X\land\forall n\in\mathbb{N}_{\geq 2}:D_{n}\in\mathcal{B}\land\forall
n\in\mathbb{N}:D_{n+1}\subseteq D_{n}\\}$

of all countable descending chains in $\mathcal{B}$ starting at $X\times X$.
For $\kappa=(D_{n})_{n\in\mathbb{N}}\in AK(\mathcal{B})$, we define

$\displaystyle d_{\kappa}:X\times X$ $\displaystyle\to\mathbb{R}_{\geq 0}$
$\displaystyle(x,y)$ $\displaystyle\mapsto\begin{cases}0\text{ if }\forall
n\in\mathbb{N}:(x,y)\in D_{n}\\\ \frac{1}{n}\text{ if
}n=max\\{m\in\mathbb{N}\mid(x,y)\in D_{m}\\}.\end{cases}$

We first show that $d_{\kappa}$ is a non-Archimedean pseudo-metric for all
$\kappa=(D_{n})_{n\in\mathbb{N}}\leavevmode\nobreak\ \in\leavevmode\nobreak\
AK(\mathcal{B})$. Let $x,y,z\in X$. Clearly, $d_{\kappa}(x,x)=0$. Since all
relation in $\mathcal{B}$ are symmetric, we have
$d_{\kappa}(x,y)=d_{\kappa}(y,x)$.
For the proof of the non-Archimedean triangle inequality, first assume that
$d_{\kappa}(x,y)=d_{\kappa}(y,z)=0$. Since all $D_{n}$ are transitive, we have
that $d_{\kappa}(x,z)=0$. If $d_{\kappa}(x,y)=0$ and
$d_{\kappa}(y,z)=\frac{1}{l}$ for some $l\in\mathbb{N}$, then by the
transitivity of $D_{l}$ we have $(x,z)\in D_{l}$. Therefore
$d_{\kappa}(x,z)\leq\frac{1}{l}$.
Finally, if $d_{\kappa}(x,y)=\frac{1}{l}$ and $d_{\kappa}(y,z)=\frac{1}{k}$
for some $l,k\in\mathbb{N}$, we assume without loss of generality that $l\geq
k$, so $\frac{1}{l}\leq\frac{1}{k}$. Therefore, we have that $(x,y),(y,z)\in
D_{k}$, so $(x,z)\in D_{k}$ and hence
$d_{\kappa}(x,z)\leq\frac{1}{k}=d_{\kappa}(y,z)$.
Now let

$\displaystyle M:=\\{sup(d_{\kappa_{1}},...,d_{\kappa_{n}})\mid
n\in\mathbb{N},\kappa_{1},...,\kappa_{n}\in AK(\mathcal{B})\\}.$

By Proposition 2.2.2(1), $M$ is a system of non-Archimedean pseudo-metrics. We
prove that $\mathfrak{D}=\mathfrak{D}_{M}$, which splits into the following
two assertions:

  * (i)

Given $D\in\mathcal{B}$, there exist $d\in M$ and $\varepsilon>0$ such that
$D^{d}_{\varepsilon}\subseteq D$.

  * (ii)

Given $d\in M$ and $\varepsilon>0$, there exists $D\in\mathfrak{D}$ such that
$D\subseteq D^{d}_{\varepsilon}$.

For the proof of (i), let $D\in\mathcal{B}$. Then
$\kappa:=(D_{n})_{n\in\mathbb{N}}$ with $D_{1}=X\times X$ and $D_{n}=D$, for
all $n\geq 2$, is an element of $AK(B)$. Now let $\varepsilon>0$ such that
$\varepsilon<\frac{1}{2}$ and define $d=d_{\kappa}$. For $(x,y)\in
D_{\varepsilon}^{d}$ we have $d(x,y)<\varepsilon<\frac{1}{2}$, so $(x,y)\in
D_{2}=D$.
Now consider $d=sup(d_{1},...,d_{n})$ where $d_{i}=d_{\kappa_{i}}$ and
$\kappa_{i}=(D_{m}^{(i)})_{m\in\mathbb{N}}\in AK(\mathcal{B})$ for all
$i\in\\{1,...,n\\}$. Moreover, let $\varepsilon>0$ and $k\in\mathbb{N}$ such
that $\frac{1}{k}<\varepsilon$. The desired relation is

$\displaystyle D:=\bigcap\limits_{i=1}^{n}D_{k}^{(i)}\in\mathfrak{D}.$

To see this, let $(x,y)\in D$. Then we have
$d_{i}(x,y)\leq\frac{1}{k}<\varepsilon$ for all $i\in\\{1,...,n\\}$, so
$d(x,y)<\varepsilon$, i.e. $(x,y)\in D^{\varepsilon}_{d}$.
So $M$ is a system of non-Archimedean pseudo-metrics such that
$\mathfrak{D}=\mathfrak{D}_{M}$. ∎

######  Theorem 1.

For a diagonal uniformity $\mathfrak{D}$ on $X$ the following are equivalent:

  * (A)

$\mathfrak{D}$ is non-Archimedean.

  * (B)

There exists a system $M$ of non-Archimedean pseudo-metrics on $X$ that
induces the uniformity $\mathfrak{D}$.

  * (C)

The corresponding covering uniformity $\mu_{\mathfrak{D}}$ of $\mathfrak{D}$
has a basis consisting of partitions of $X$.

###### Proof.

The equivalence of (A) and (C) follows immediately from Lemma 2.1.2.
That (B) implies (A) follows from Proposition 2.2.2.
The implication from (A) to (B) was just proven in Proposition 2.2.3. ∎

##  3\. An equivalent seperation axiom

######  Definition 3.1.

Let $(X,\tau)$ be a topological space.

  * (1)

$X$ is called uniformizable by a non-Archimedean uniformity if there exists a
non-Archimedean uniformity on $X$ that induces $\tau$.

  * (2)

$X$ is said to satisfy $\text{T}_{\text{A}}$ if for every closed subset
$A\subseteq X$ and every $x\in X\setminus A$ there are open sets
$U_{1},U_{2}\subseteq X$ such that

    * (i)

$U_{1}\cap U_{2}=\emptyset$, $U_{1}\cup U_{2}=X$,

    * (ii)

$A\subseteq U_{1}$, $x\in U_{2}$.

  * (3)

$X$ is said to be zero-dimensional (with respect to the small inductive
dimension), if it has a basis of clopen sets.

The equivalence of (1) and (3) in the following theorem has already been shown
by Banaschewski [2] for Hausdorff spaces.

######  Theorem 3.2.

For a topological space $(X,\tau)$, the following are equivalent:

  * (1)

$X$ is uniformizable by a non-Archimedean uniformity.

  * (2)

$X$ satisfies $\text{T}_{\text{A}}$.

  * (3)

$X$ is zero-dimensional.

###### Proof.

"(2) $\Rightarrow$ (1)" Now assume that $X$ satisfies $\text{T}_{\text{A}}$.
Let $S=\\{f:X\to\\{0,1\\}\mid f\text{ is continuous}\\}$, where $\\{0,1\\}$
carries the discrete topology. For every $f\in S$, we define an equivalence
relation

$\displaystyle D_{f}=\\{(x,y)\in X\times X\mid f(x)=f(y)\\}.$

It is immediate that $\mathcal{B}:=\\{D_{f_{1}}\cap...\cap D_{f_{n}}\mid
f_{i}\in S\\}$ is a basis consisting of equivalence relations for a non-
Archimedean uniformity $\mathfrak{D}$ on $X$. We denote by $\sigma$ the
topology on $X$ induced by $\sigma$ and assert that $\tau=\sigma$.
Let $A\subseteq X$ be closed with respect to $\tau$ and $x\in X\setminus A$.
Let $U_{1},U_{2}\subseteq X$ open with respect to $\tau$ such that $U_{1}\cap
U_{2}=\emptyset$, $U_{1}\cup U_{2}=X$, $x\in U_{2}$, $A\subseteq U_{1}$ and
let $f_{x}:X\to\\{0,1\\}$ be such that $f_{x}$ takes the value $0$ on $U_{2}$
and the value $1$ on $U_{1}$. Then clearly $f_{x}$ is continuous with respect
to $\tau$. Per definition,

$\displaystyle D_{f_{x}}[x]=\\{y\in X\mid f_{x}(y)=f_{x}(x)=0\\}=U_{2}$

is open with respect to $\sigma$ and disjoint from $A$. Since $x\in X\setminus
A$ was arbitrarily chosen, we conclude that

$\displaystyle A=X\setminus\bigcup\limits_{x\in X\setminus A}D_{f_{x}}[x]$

is closed with respect to $\sigma$. So $\sigma$ is finer than $\tau$.
For the reverse direction, it suffices to show that $D[x]$ is open with
respect to $\tau$ for all $x\in X$ and $D\in\mathcal{B}$. But since
$D=D_{f_{1}}\cap...\cap D_{f_{n}}$ for some $f_{1},...,f_{n}\in S$ and
$D[x]=D_{f_{1}}[x]\cap...\cap D_{f_{n}}[x]$ for all $x\in X$, we just have to
show this for $D_{f}$ with $f\in S$. There, for every $x\in X$, we have
$D_{f}[x]=\\{y\in X\mid f(x)=f(y)\\}=f^{-1}(\\{f(x)\\})$. Since $f$ is
continuous and $\\{f(x)\\}$ is open, it follows that $D_{f}[x]\in\tau$.
So $X$ is uniformizable by a non-Archimedean uniformity.
"(3) $\Rightarrow$ (2)" Let $A\subseteq X$ be closed and $x\in X\setminus A$.
Since $X\setminus A$ is open and therefore a union of clopen sets, there
exists some $U_{2}\subseteq X\setminus A$ that is clopen and contains $x$. Set
$U_{1}=X\setminus U_{2}$. ∎

Note that, although $\text{T}_{\text{A}}$ implies $\text{T}_{3\frac{1}{2}}$,
it does not fit into the classical hierachy of seperation axioms, as normal
spaces are not necessarily $\text{T}_{\text{A}}$. Consider for instance
$\mathbb{R}$ carrying the canonical topology. This space is normal, but it is
connected, hence does not satisfy $\text{T}_{\text{A}}$.

##  4\. Pseudo-metrizability

We now proceed with a characterization of the case where a uniform space is
pseudo-metrizable by a single non-Archimedean pseudo-metric.

######  Theorem 4.1.

Let $(X,\mathfrak{D})$ be a uniform space. Then the following are equivalent:

  * (A)

$(X,\mathfrak{D})$ is pseudo-metrizable by a non-Archimedean pseudo-metric.

  * (B)

$\mathfrak{D}$ is induced by a countable system of non-Archimedean pseudo-
metrics.

  * (C)

$\mathfrak{D}$ possesses a countable basis consisting of equivalence
relations.

###### Proof.

(A)$\Rightarrow$(B) is trivial.
For (B)$\Rightarrow$(C), let $(d_{n})_{n\in\mathbb{N}}$ be a countable system
of non-Archimedean pseudo-metrics inducing $\mathfrak{D}$. Then
$(D^{d_{n}}_{1/m})_{n,m\in\mathbb{N}}$ is a countable basis of $\mathfrak{D}$
consisting of equivalence relations.
Now let $(E_{n})_{n\in\mathbb{N}}$ be a basis for $\mathfrak{D}$ consisting of
equivalence relations and assume without restriction that $E_{1}=X\times X$.
We get another countable basis $(D_{n})_{n\in\mathbb{N}}$ (of equivalence
relations) by applying the properties of a basis of a uniformity and iterating
the following recursion:

$D_{1}:=E_{1}$

$\text{Choose }D_{i+1}\in\\{E_{n}\mid n\in\mathbb{N}\\}\text{ such that
}D_{i+1}\subseteq D_{i}\cap E_{i+1},$

$\text{for }i\in\mathbb{N}.$

Note that $(D_{n})_{n\in\mathbb{N}}$ is a decreasing chain, i.e. $X\times
X=D_{1}\supseteq D_{2}\supseteq D_{3}\supseteq...$, what allows us to define a
non-Archimedean pseudo-metric as follows:

$\displaystyle d:X\times X$ $\displaystyle\to\mathbb{R}_{\geq 0}$
$\displaystyle(x,y)$ $\displaystyle\mapsto\begin{cases}0\text{ if }\forall
n\in\mathbb{N}:(x,y)\in D_{n}\\\ \frac{1}{n}\text{ if
}n=max\\{m\in\mathbb{N}\mid(x,y)\in D_{m}\\}.\end{cases}$

To see that $d$ induces $\mathfrak{D}$, let $\varepsilon>0$ and
$n\in\mathbb{N}$ such that $\frac{1}{n}<\varepsilon$. For $(x,y)\in D_{n}$, we
have $d(x,y)\leq\frac{1}{n}<\varepsilon$, which implies $(x,y)\in
D_{\varepsilon}^{d}$.
On the other hand, let $n\in\mathbb{N}$. For $(x,y)\in D^{d}_{\frac{1}{n+1}}$,
it follows that $d(x,y)\leq\frac{1}{n+1}<\frac{1}{n}$, hence $(x,y)\in D_{n}$.
∎

## References

  * [1] M.F. Atiyah, I.G. MacDonald, Introduction to Commutative Algebra. Addison-Wesley Publishing Company, Reading, MA (1969).
  * [2] B. Banaschewski, Über nulldimensionale Räume. Math. Nachr. 13 (1955), 129-140.
  * [3] J. de Groot, Non-Archimedean metrics in topology. Proc. Am. Math. Soc. 7:5 (1956), 948–953.
  * [4] A.F. Monna, Rémarques sur les métrique non-archimédiennes I - II. Indag. Math. 12 (1950), 122-133, 179-191.
  * [5] St. Willard, General Topology. Addison-Wesley Publishing Company, Reading, MA (1970).