# Diverse Generation from a Single Video Made Possible

Niv Haim Ben Feinstein11footnotemark: 1 Niv Granot Assaf Shocher
Shai Bagon Tali Dekel Michal Irani

Weizmann Institute of Science, Rehovot, Israel These authors contributed
equally to this work.

###### Abstract

GANs are able to perform generation and manipulation tasks, trained on a
single video. However, these single video GANs require unreasonable amount of
time to train on a single video, rendering them almost impractical. In this
paper we question the necessity of a GAN for generation from a single video,
and introduce a non-parametric baseline for a variety of generation and
manipulation tasks. We revive classical space-time patches-nearest-neighbors
approaches and adapt them to a scalable unconditional generative model,
without any learning. This simple baseline surprisingly outperforms single-
video GANs in visual quality and realism (confirmed by quantitative and
qualitative evaluations), and is disproportionately faster (runtime reduced
from several days to seconds). Other than diverse video generation, we
demonstrate other applications using the same framework, including video
analogies and spatio-temporal retargeting. Our proposed approach is easily
scaled to Full-HD videos. These observations show that the classical
approaches, if adapted correctly, significantly outperform heavy deep learning
machinery for these tasks. This sets a new baseline for single-video
generation and manipulation tasks, and no less important – makes diverse
generation from a single video practically possible for the first time.

Project page: https://nivha.github.io/vgpnn

##  1 Introduction

Figure 1: Diverse Single Video Generation: Given an input video (red), VGPNN
is able to generate similarly looking videos (black) capturing both appearance
of objects as well as their dynamics. Note the high quality of our generated
videos. Please watch the full resolution videos in the project page.

Generation and editing of natural videos remain challenging, mainly due to
their large dimensionality and the enormous space of motion they span. Most
modern frameworks train generative models on a large collection of videos,
producing high quality results for only a limited class of videos. These
include extensions of GANs [23] to video data [63, 58, 2, 67, 48, 36] and
video-to-video translation [64, 65, 40, 66, 15, 72, 8], autoregressive
sequence prediction [7, 60, 6, 17, 61, 62, 3, 22] and more. While externally-
trained generative models produce impressive results, they are restricted to
the types of video dynamics in their training set. On the other side of the
spectrum are _single-video GANs_. These video generative models train on a
_single_ input video, learn its distribution of space-time patches, and are
then able to generate a diversity of new videos with the same patch
distribution [25, 5]. However, these take very long time to train for each
input video, making them applicable to only small spatial resolutions and to
very short videos (typically, very few small frames). Furthermore, their
output oftentimes shows poor visual quality and noticeable visual artifacts.
These shortcomings render existing single-video GANs impractical and
unscalable.

Video synthesis and manipulation of a single video sequence based on its
distribution of space-time patches dates back to classical pre-deep learning
methods. These classical methods demonstrated impressive results for various
applications, such as video retargeting [55, 46, 71, 31], video completion
[70, 39, 27], video texture synthesis [32, 33, 34, 14, 21, 28] and more. With
the rise of deep-learning, these methods gradually, perhaps unjustifiably,
became less popular. Recently, Granot et al. [24] revived classical patch-
based approaches for image synthesis, and was shown to significantly
outperform _single-image_ GANs in both run-time and visual quality.

In light of the above-mentioned deficiencies of single-video GANs, and
inspired by [24], we propose VGPNN (_Video Generative Patch Nearest
Neighbors_), a fast and practical method for video generation and manipulation
from a single video. In order to handle the huge amounts of space-time patches
in a single video sequence, we use and extend classical fast approximate
nearest neighbor search methods [9]. We also employ robust optical-flow-like
descriptors, which allow transferring highly different dynamics and motions
from one video to another. Finally, by adding stochastic noise to the process,
our approach can generate a large diversity of random different video outputs
from a single input video in an unconditional manner.

Like single-video GANs, our approach enables the diverse and random generation
of videos. However, in contrast to existing single-video GANs, VGPNN can
generate _high resolution_ videos, while reducing runtime by many orders of
magnitude, thus making diverse unconditional video generation from a single
video realistically possible for the first time.

Our contributions are as follows:

  * •

We observe that space-time patch nearest-neighbor approaches, when posed as an
unconditional generative model, outperform single-video GANs by a large
margin, both in runtime and in quality.

  * •

We provide a new baseline for comparing single-video generative models. Our
approach is practical to run and compare against (code will be released), and
scalable also to high resolution videos (spatial or temporal).

  * •

We demonstrate a variety of video synthesis tasks, all within a single unified
framework. These include: diverse unconditional video generation, video
analogies, sketch-to-video, spatio-temporal video retargeting and conditional
video inpainting.

##  2 Related work

Classical video generation methods, many of whom inspired by similar _image_
methods [20, 19, 68], include video texture synthesis [32, 33, 34], MRF-based
controllable synthesis [51], flow-guided synthesis [14, 34, 28, 41, 50, 49]
and more (see surveys by [69, 11]). While some used a generative model to
model patch distribution, none considered unconditional generation of natural
videos, beyond dynamic textures.

PatchMatch by Barnes et al. [9] is a fast method for finding an approximate
nearest-neighbor field (NNF). On natural images/videos, the algorithm
converges very quickly to a good approximated solution. PatchMatch was also
extended for k-nearest neighbors search [10], faster search [11] and being
differentiably learnable [18]. The main editing tool shown in [9] is image
summarization using bidirectional similarity (BDS). Introduced by Simakov et
al. [55], BDS ensures both visual “completeness” and “coherence” of the visual
summary (coherence is obtained when the generated output contains only patches
from the input, while completeness is obtained when all the patches in the
input can be found in the generated output). [24] proposed a normalized score
to encourage completeness by globally re-weighting the similarity score
between patches. Motivated by this similarity score, we utilize PatchMatch to
efficiently incorporate global patch-specific information.

##  3 Method

Figure 2: VGPNN Architecture: Given a single input video $x_{0}$, a spatio-
temporal pyramid is constructed and an output video $y_{0}$ is generated
coarse-to-fine. At each scale, VPNN module (see Fig. 3) is applied to transfer
an initial guess $Q_{n}$ to the output $y_{n}$ which shares the same space-
time patch distribution as the input $x_{n}$. At the coarsest scale, noise is
injected to induce spatial and temporal randomness.

Our goal is to generate diverse video samples based on a single input video.
We want our model to operate on natural input videos that can vary in their
appearance and dynamics. In order to capture both spatial and temporal
information of a single video, we start by building a spatio-temporal pyramid
and operate coarse-to-fine to capture the internal statistics of the input
video at multiple scales (Fig. 2). This multi-scale approach is extensively
used in classical image synthesis methods as well as in modern GANs [e.g., 30,
52, 25]). At each scale we employ a Video-Patch-Nearest-Neighbor module or
VPNN (VGPNN is in fact a sequence of VPNN layers). The inputs to each layer
depend on the application, where we first focus on our main application of
diverse video generation (see Sec. 5 for the specific details of the other
applications).

#### Multi-scale approach (Fig.2):

Given an input video $x$, we construct a spatio-temporal pyramid
$\left\\{x_{0}\dots,x_{N}\right\\}$, where $x_{0}=x$, and
$x_{n}=x_{n-1}{\downarrow_{r}}$ is a bicubically downscaled version of
$x_{n-1}$ by factor $r$ (${r=(r_{H},r_{W},r_{T})}$, where $r_{H}=r_{W}$ are
the spatial factors and $r_{T}$ is the temporal factor, which can be
different).

At the coarsest scale, the input to the first VPNN layer is an initial coarse
guess of the output video. This is created by adding random Gaussian noise
$z_{N}$ to $x_{N}$. The noise $z_{N}$ promotes high diversity in the generated
output samples from the single input. The global structure (e.g., a head is
above the body) and global motion (e.g., humans walk forward), is prompted by
$x_{N}$, where such structure and motion can be captured by _small space-time_
patches. The coarsest-scale output $y_{N}$ is generated by replacing each
space-time patch of the initial coarse guess ($x_{N}+z_{N}$) with its nearest
neighbor patch from the corresponding coarse input $x_{N}$. The resulting
patches are then folded to a video, by choosing at each space-time position
the median of all suggestions from neighboring patches.

At each subsequent scale, the input to the VPNN layer is the bicubically-
upscaled output of the previous layer (${y_{n+1}\uparrow}^{r}$). The output
$y_{n}$ is then generated by replacing each space-time patch with its nearest
neighbor patch from the corresponding input $x_{n}$ (using the same patch-size
as before, now capturing finer details). This way, the output $y_{n}$ in each
scale is similar in structure and in motion to the initial guess, but contains
the same space-time patch statistics of the corresponding input $x_{n}$.
Finally, the resulting patches are folded to a video.

To further improve the quality and sharpness of the generated output at each
pyramid scale ($y_{n}$), we iterate several times through the current scale
VPNN layer, each time using the current output $y_{n}$ as input to the next
iteration (similar to the EM-like approach employed in many patch-based works
[e.g., 24, 55, 9, 70]).

Figure 3: VPNN module gets as input RGB videos query, key and value (QKV
respectively). Q and K can be concatenated to additional auxiliary channels.
It outputs an RGB video. (a) Inputs are unfolded to patches (each position now
holds a concatenation of neighboring positions); (b) Each patch in Q finds its
nearest neighbor patch in K. This is achieved by solving the NNF using
PatchMatch [9]; (c) Each patch in Q is replaced with a patch from V, according
to the correspondences found in stage (b); (d) Resulting patches are folded
back to an RGB video output.

#### QKV scheme (Fig. 3):

Similar to [24], we adopt a QKV scheme (query, key and value, respectively; as
is common in the attention mechanism [59] nomenclature) for VPNN. Instead of
comparing two patches by only using their RGB values, in several cases it is
necessary to compare patches in another search space. For example, using the
aforementioned notations, we denote $V=x_{n}$ (the corresponding level from
the pyramid of the original video) and $Q={y_{n+1}\uparrow}$ (the upscaled
output of previous layer). Note that since $Q$ is an _upscaled_ version of
previous output, its patches are blurry. Seeking their nearest neighbors in
$V$ (whose patches are sharp) often results in improper matches. This is
mitigated by setting $K=x_{n+1}{\uparrow^{r}}$ (in the first iteration of each
scale of VGPNN), which has a similar degree of blur/degradation as $Q$. After
finding its match in $K_{j}$, each patch $Q_{i}$ is then replaced with a patch
$V_{j}$ (where $i,j$ are spatio-temporal positions. Also note that $K$ and $V$
are of the same shape).

The QKV scheme is especially important in our video analogies application
where it is used to include additional temporal information in the queries and
the keys. We discuss it in detail in Sec. 5.1.

#### Completeness score:

In the applications of video analogies, spatio-temporal video retargeting and
conditional video inpainting we use the normalized similarity score [24] that
encourages visual completeness. The score between a query patch $Q_{i}$ and a
key patch $K_{j}$ is defined as:

$\displaystyle
S\left(Q_{i},K_{j}\right)\coloneqq\frac{1}{\alpha+\min_{\ell}{D(Q_{\ell},K_{j})}}D(Q_{i},K_{j})\
\ ,$ (1)

where $D=MSE$, and $\alpha$ controls the degree of completeness (smaller
$\alpha$ encourages more completeness). $S$ is essentially a weighted version
of $D$, whose weights depend _globally_ on $K$ and $Q$.

#### Finding Correspondences:

We find the nearest neighbors between $Q$ and $K$ (Fig. 3b) using PatchMatch
(Barnes et al. [9]). To cope with the completeness score, we apply PatchMatch
twice. First we find a “rareness” score for the keys - for each _key_ we find
its closest _query_. Then, for each _query_ we find its closest _key_ while
factoring in the rareness of the keys as weights in the PatchMatch search.
Namely, we solve for:

$\displaystyle\text{NNF}(\mathbf{p})=\text{arg}\min_{\mathbf{v}}W(\mathbf{p+v})\cdot
D(Q(\mathbf{p}),K(\mathbf{p+v}))$ (2)

Where $D$ is a distance function, $W$ are per-patch weights,
$\mathbf{p}=(t,x,y)$ a position in $Q$ and
$\mathbf{v}=(t^{\prime},x^{\prime},y^{\prime})$ are possible NNF candidates
(such as the NNF at the current position $\text{NNF}(t,x,y)$ or at a neighbor
position $\text{NNF}(t,x-1,y)$ in the propagation step).

This requires a slight modification of PatchMatch to support per-key weights.
This additional support makes it possible to approximately solve Eq. 1 with
two passes of PatchMatch. Even though this gives an approximation of Eq. 1, we
do not suffer loss in quality or lack of completeness, as apparent from our
results.

The algorithm is implemented on GPU using PyTorch [42], with time complexity
$O(n\times d)$ and $O(n)$ additional memory (where $n$ is the video size and
$d$ is the patch size; also see Fig. 5).

#### Temporal Diversity and Consistency:

To enhance the temporal diversity of our samples we set the temporal dimension
of the output to be slightly smaller than that of the input video. Thus,
motions in different spatial positions in the generated output are taken from
different temporal positions in the input video, increasing the overall
temporal diversity (see for example the generated dancers in Fig. 1 that are
not synced). We also found that the temporal consistency is best preserved in
the generated output when the initial noise $z_{N}$ is randomized for each
spatial position, but is the same (replicated) in the temporal dimension.

##  4 Experimental Results

In this section we evaluate and compare the performance of our main
application – diverse video generation from a single input video. Figs.
LABEL:fig:teaser and 1 illustrate diverse videos generated from a single input
video, all sharing the same space-time patch distribution. The diversity is
both spatially (e.g., number of dancers and their positions are different from
the input video) and temporally (generated dancers are not synced). Please
refer to the supplementary material to view the full resolution videos and
many more examples.

#### Comparison to other methods for video generation from a single video:

We compare our method to recently published methods for diverse video
generation from single video: HP-VAE-GAN [25] and SinGAN-GIF [5]. We show that
our results are both qualitatively and quantitatively superior while reducing
the runtime by a factor of $3\times 10^{4}$ (from 8 days training on one video
to 18 seconds for new generated video). Since SinGAN-GIF did not make their
code available, and the training time of HP-VAE-GAN for a single video (13
frames of size $144{\times}256$) is roughly $8$ days, we are only able to
compare to the videos published by these methods. “HP-VAE-GAN dataset”
comprises of 10 input videos with 13 frames each, and of spatial resolution of
$144{\times}256$ pixels. “SinGAN-GIF dataset” has 5 input videos with maximal
resolution of $168{\times}298$ pixels and 8-16 frames.

#### Qualitative comparison:

In Fig. 4 we show a side-by-side comparison of representative generated frames
of our method to frames generated by HP-VAE-GAN [25] and SinGAN-GIF [5]. Note
that while [25, 5] are limited to generated outputs of small resolution
($144{\times}256$), we can generate outputs in the same resolution of the
input video (full-HD $1280{\times}1920$, shown in the figure). The full videos
(as well as a comparison to our generated outputs of similar low resolution)
can be viewed in the supplementary material. As can be seen, our generated
samples (in low and high resolution) are more spatially and temporally
coherent, as well as having higher visual quality. It is evident that
generating videos using the space-time patches of the original input video,
rather than regressing output RGB values, gives rise to high quality outputs.

Figure 4:  Comparing Visual Quality between our generated frames and those of
HP-VAE-GAN [25] and SinGAN-GIF [5] (please zoom in on the frames). Note that
our generated frames are sharper and also exhibit more coherent and plausible
arrangements of the scene. For details see Section 4. Please find the full
videos and more comparisons in the supplementary material.
---
Figure 5: Comparing Generation Runtime between our approach (VGPNN), a naïve
extension of GPNN [24] from 2D to 3D and HP-VAE-GAN [25]. We compared the
generation time of 13-frames videos with different spatial resolutions
(X-axis). All videos have 16:9 aspect ratio (e.g., 144p is 144x256 and 1080p
is 1080x1920 – full-HD). See Section 4 for details.

#### Quantitative comparison:

In Table 1 we report the Single-Video-FID (SVFID) [5] of our generated
samples, compared to those generated by HP-VAE-GAN [25] and SinGAN-GIF
[5]111All quantitative comparisons were done on generated samples of the same
resolution and video length as that of the other method.. SVFID was proposed
by [25] to measure the patch statistics similarity between the input video and
a generated video. It computes the Fréchet distance between the statistics of
the input video and the generated video using pre-computed C3D [57] features
(Lower SVFID is better). As can be seen in Table 1, our generated samples bear
more substantial similarity to the input videos (indicated by lower SVFID).
[52] proposed a diversity index to make sure that generated outputs are indeed
different (and not simply “copying” the input). We adapt the index for videos.
The index is zero if all generated outputs are the same, and higher otherwise.
While our and HP-VAE-GAN generated samples have similar index ($0.45/0.41$
respectively), those of SinGAN-GIF have higher index ($0.86$ vs. our $0.6$).
Such high diversity is not an advantage, when paired with SVFID about twice
worse than ours. It stems from low quality appearance with out-of-distribution
patches. All inputs and generated videos can be found in the supplementary
material.

#### User study:

We conducted a user study evaluation using Amazon Mechanical Turk (AMT). For
each dataset, 100 subjects were shown multiple pairs of videos, each
consisting of a video generated by our method, and a video generated by the
other method (both were generated from the same input video). The subjects
were asked to judge which sample is better in terms of sharpness, natural look
and coherence. In Table 1 we report the percentage of users who favored our
method over the other. Compared to videos generated from HP-VAE-GAN dataset,
there is a clear preference in favor of our patch-based method. The results on
the SinGAN-GIF dataset are not that clear-cut, this might be due to the
somewhat restricted nature of the videos in that particular dataset (as
mentioned above, it was not possible to check SinGAN-GIF on other samples,
since the authors did not publish their code, nor stated the amount of time it
took to generate their samples).

#### Reducing running times:

In Fig. 5 we show a comparison of the runtime taken to generate random video
samples using our method, compared to a naïve extension of GPNN [24] (from 2D
to 3D patches) and compared to the training time of HP-VAE-GAN [25]. As
discussed in Sec. 3, the use of efficient PatchMatch algorithm for nearest
neighbors search, as opposed to the exhaustive search done in GPNN,
dramatically reduces both run time and memory footprint used for video
generation, making it possible to generate high-resolution videos (including
Full-HD 1080p). All experiments were conducted on Quadro RTX 8000 GPU.

Method SVFID Head-on comparison Runtime [25] $\downarrow$ (User study)
[$\%$]$\uparrow$ $\downarrow$ HP-VAE-GAN [25] 0.0081 67.84$\pm$1.77 7.625 days
VGPNN (Ours) 0.0072 18 secs SinGAN-GIF [5] 0.0119 50.57$\pm$ 3.27 Unpublished
VGPNN (Ours) 0.0058 10 secs

Table 1: Quantitative Evaluation: A comparison of our generated video samples
to that of HP-VAE-GAN [25] and SinGAN-GIF [5], conducted on input videos
provided in their papers. Our diverse samples have more resemblance to the
input videos (indicated by lower SVFID). In a user study, users scored in
favor of our method (see Section 4 for details).

##  5 Applications

Other than unconditional diverse generation, we demonstrate the utility of the
proposed unified framework on several other video manipulation applications.

Figure 6:  Video Analogies: Left: an example of video analogies between all
pairs of three input videos (red). Each generated video (black) takes the
spatio-temporal layout from the input video in its row, and the appearance and
dynamics of the input video from its column. Right: an example of sketch-to-
video – the generated video (bottom) takes its spatio-temporal layout from the
sketch video of morphed MNIST digits (middle) and its appearance and dynamics
from the input video of parading soldiers (top). Please find full videos and
additional examples in the supplementary material.

###  5.1 Video analogies

Inspired by Image Analogies [26, 38, 12] we propose Video Analogies where we
generate a new video whose spatio-temporal layout is taken from a content
video $C$, and overall appearance and dynamics are taken from a style video
$S$ (see Fig. 6).

Our goal is to find a mapping of dynamic elements (patches) between the two
videos, which can be very different in their appearance (RGB space). This is
achieved by using the magnitude of the optical flow (extracted via RAFT [56]),
quantized into few bins (using k-means)222Each cluster has an integer cluster
index. We divide each index by the total number of clusters/bins to be in
$[0,1]$. We term this the dynamic structure of the video. By concatenating the
dynamic structure to the RGB values of the video (along the channels axis),
each patch can now be compared using its RGB values and its dynamic values.
This provides a good mapping between the dynamic elements of the two input
videos.

Given the dynamic structures of both input videos $\text{dyn}(C)$,
$\text{dyn}(S)$, we compute their spatio-temporal pyramids and that of the
style video $S$. The output video is generated by setting $Q,K,V$ at each
scale as follows:

$\begin{array}[]{@{}l|lll}\text{Scale}&Q&K&V\\\ \hline\cr\text{N
(coarsest)}&\text{dyn}(C)_{N}&\text{dyn}(S)_{N}&S_{N}\\\ \text{n (any
other)}&\text{dyn}(C)_{n}\|Q_{n+1}\uparrow&\text{dyn}(S)_{n}\|S_{n}&S_{n}\end{array}$

where $\|$ denotes concatenation along the channels axis, and $n$ denote the
current scale in the pyramid. Note that in the coarsest scale, the two videos
are only compared by their dynamic structure. In finer scales, the dynamic
structure of $C$ (the content video) is used to “guide” the output to the
desired spatio-temporal layout.

In Fig. LABEL:fig:teaser we show a snapshot of the analogies between a
waterfall and a lava stream, and in Fig. 6 we show snapshots of the analogies
of all possible pairs between three videos (the lava stream, a waterfall and a
meat grinder). The full videos are in the supplementary material.

We can use the above mentioned mechanism for “sketch-to-video” transfer, where
the dynamic structure is given by a sketch video instead of an actual video.
See Fig. 6 for a few snapshots of transferring the motion of morphed MNIST
[35] digits to a video of marching soldiers, and please see the full videos
and many more results in the supplementary material.

Related to us are works for video style transfer from a style image [e.g. 13,
47, 29, 16], general video-to-video translation trained on large datasets or
conditioned on human poses or keypoint detection [e.g. 64, 65, 40, 66] or
human motion transfer methods [e.g. 1, 15, 72, 53, 54, 44, 37] that involve
some kind of human model knowledge. Flow-based appearance transfer of fluids
has been studied by [14, 34, 28, 41, 50, 49]. Most similar to us is [28] that
uses a patch nearest neighbor approach to transfer the appearance of a fluid
exemplar (a still image) into a video given a human annotated flow+alpha mask.
Our method differs in how we model the flow guidance and in the mapping we
have between two flows of two videos (instead of a still image exemplar).

Also similar to us is Recycle-GAN by Bansal et al. [8] that pose unsupervised
video-to-video translation as a domain transfer problem (each video is a
domain). They train convolutional encoders to map between the two videos using
adversarial loss with cyclic constraints. We provide a comparison to [8] in
the supplementary material. As can be seen for the sketch to videos examples,
RecycleGAN’s outputs fail to capture the finer motions of the soldiers, and in
the fluid-like examples it quickly converges to the style video. On top of
that, the overall visual quality is diminished due to the model being
parametric.

###  5.2 Spatial Retargeting

The goal of video retargeting is to change the dimensions of a video without
distorting its visual contents (e.g., fit a portrait video to a wide screen
display). It can be performed in a very similar manner to our video generation
described in Sec.3. Given a target shape, we first resize (bicubically) the
input video to the target shape, then compute two pyramids (for the input and
resized videos) with the same depth and downscale factor. The initial guess at
the coarsest scale $Q_{N}$ would be the coarsest scale of the resized pyramid
(without any additional noise). We then compute the rest of the output video
in the same manner as in Sec.3. Note that at each scale, $V_{n}$ are
unchanged, hence no distortion is introduced to the patches reconstructing the
retargeted video.

As can be seen in Fig. LABEL:fig:teaser and in the supplementary material, the
results preserve the original size and aspect ratio of objects from the input
videos while keeping the overall appearance coherent even though the aspect
ratio is significantly altered. The dynamics and motions in the videos are
also preserved. For instance, the balloons are not “squashed” but rather
packed more compactly in the sky and more members were added to the choir
instead of stretching them. Nevertheless, the motion of the balloons or the
sway of the choir members are preserved. Other classical works for video
retargeting, such as [55, 71, 46, 31] did not make their implementation
available, therefore we were unable to provide a comparison.

###  5.3 Temporal Retargeting

Similar to spatial retargeting, one can generate a realistic video with a
different _temporal_ length. One possible use is generating a shorter summary
of the video. While most deep video summarization techniques are achieved by
selecting a subset of frames (see survey [4]), classical methods have
demonstrated summaries that consist of _novel frames_ in which dynamics that
are originally sequential can be parallelized or vice versa [43, 55]. By
applying the retargeting approach to the temporal dimension, VGPNN generates
summaries with novel frames. The _temporal retargeting section in the
supplementary material_ shows several examples. For example, in the dog
training summarized video, the trainer and dog turn around simultaneously as
opposed to sequentially in the original video. Moreover, we can, in a similar
manner, extend the temporal duration of a video creating longer dynamics while
preserving the speed of the individual actions. In the ballet dancer video for
example, the choreography is longer, but the pace of the dance motions remains
the same.

###  5.4 Video conditional inpainting

In this task we are given an input video with some occluded space-time volume,
where the missing parts should be completed based on crude color cues placed
by the user in the occluded space (similar to conditional image inpainting
[24]). Here we set the number of levels in the pyramid such that the occluded
part in the coarsest scale is roughly in the size of a single patch. The
masked part is then coherently reconstructed using other space-time patches of
similar colors to that of the cue. In finer scales, details and dynamic
elements are added correctly. Fig. 7 shows how different cues are completed
with different elements from the non-occluded parts. See for instance, how a
blue cue will be replaced by a player from Barcelona while a white cue by a
player from Real Madrid. See more examples in the supplementary material.

Figure 7: Conditional Video Inpainting. Colored occluded masks in the input
video (red) are completed, conditioned on the color cue. The completion
persists through the video dynamics. Please see full videos in the
supplementary material.

##  6 Limitations

Generation of local patches, as in VGPNN but also as in single video GANs,
lacks global geometric consistency. This is apparent when scenes with
significant depth variations are introduced with large camera motion. While
each frame is plausible, different patches are not being transformed
consistently, resulting in non-rigid deformations to entities that are
realistically rigid. See the generated videos of mountains in the
supplementary.

##  7 Conclusion

We demonstrated that random diverse video generation from a single video can
be efficiently done by simple patch-based methods. We also demonstrated how
small modifications to our framework give rise to other tasks such as video
analogies and spatio-temporal retargeting. We showed that our non-parametric
approach outperforms existing single-video GANs in the visual quality of the
generated outputs, while being orders of magnitude faster. The low run time
required for generating videos using our approach makes it a good baseline for
future works in the field.

## Acknowledgements

This project received funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (grant
agreement No 788535), from the D. Dan and Betty Kahn Foundation, and from the
Israel Science Foundation (grant 2303/20). Dr. Bagon is a Robin Chemers
Neustein AI Fellow.

## References

  * Aberman et al. [2020] K. Aberman, Y. Weng, D. Lischinski, D. Cohen-Or, and B. Chen.  Unpaired motion style transfer from video to animation.  _ACM Transactions on Graphics (TOG)_ , 39(4):64–1, 2020.
  * Aigner and Körner [2018] S. Aigner and M. Körner.  Futuregan: Anticipating the future frames of video sequences using spatio-temporal 3d convolutions in progressively growing gans.  _arXiv preprint arXiv:1810.01325_ , 2018.
  * Aksan and Hilliges [2019] E. Aksan and O. Hilliges.  Stcn: Stochastic temporal convolutional networks.  _arXiv preprint arXiv:1902.06568_ , 2019.
  * Apostolidis et al. [2021] E. Apostolidis, E. Adamantidou, A. I. Metsai, V. Mezaris, and I. Patras.  Video summarization using deep neural networks: A survey.  _arXiv preprint arXiv:2101.06072_ , 2021.
  * Arora and Lee [2021] R. Arora and Y. J. Lee.  Singan-gif: Learning a generative video model from a single gif.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 1310–1319, 2021.
  * Babaeizadeh et al. [2017] M. Babaeizadeh, C. Finn, D. Erhan, R. H. Campbell, and S. Levine.  Stochastic variational video prediction.  _arXiv preprint arXiv:1710.11252_ , 2017.
  * Ballas et al. [2015] N. Ballas, L. Yao, C. Pal, and A. Courville.  Delving deeper into convolutional networks for learning video representations.  _arXiv preprint arXiv:1511.06432_ , 2015.
  * Bansal et al. [2018] A. Bansal, S. Ma, D. Ramanan, and Y. Sheikh.  Recycle-gan: Unsupervised video retargeting.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 119–135, 2018.
  * Barnes et al. [2009] C. Barnes, E. Shechtman, A. Finkelstein, and D. B. Goldman.  Patchmatch: A randomized correspondence algorithm for structural image editing.  _ACM Trans. Graph._ , 28(3):24, 2009.
  * Barnes et al. [2010] C. Barnes, E. Shechtman, D. B. Goldman, and A. Finkelstein.  The generalized patchmatch correspondence algorithm.  In _European Conference on Computer Vision_ , pages 29–43. Springer, 2010.
  * Barnes et al. [2015] C. Barnes, F.-L. Zhang, L. Lou, X. Wu, and S.-M. Hu.  Patchtable: Efficient patch queries for large datasets and applications.  _ACM Transactions on Graphics (ToG)_ , 34(4):1–10, 2015.
  * Benaim et al. [2021] S. Benaim, R. Mokady, A. Bermano, and L. Wolf.  Structural analogy from a single image pair.  In _Computer Graphics Forum_ , volume 40, pages 249–265. Wiley Online Library, 2021.
  * Bénard et al. [2013] P. Bénard, F. Cole, M. Kass, I. Mordatch, J. Hegarty, M. S. Senn, K. Fleischer, D. Pesare, and K. Breeden.  Stylizing animation by example.  _ACM Transactions on Graphics (TOG)_ , 32(4):1–12, 2013.
  * Bhat et al. [2004] K. S. Bhat, S. M. Seitz, J. K. Hodgins, and P. K. Khosla.  Flow-based video synthesis and editing.  In _ACM SIGGRAPH 2004 Papers_ , pages 360–363. 2004.
  * Chan et al. [2019] C. Chan, S. Ginosar, T. Zhou, and A. A. Efros.  Everybody dance now.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 5933–5942, 2019.
  * Chen et al. [2017] D. Chen, J. Liao, L. Yuan, N. Yu, and G. Hua.  Coherent online video style transfer.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 1105–1114, 2017.
  * Denton and Fergus [2018] E. Denton and R. Fergus.  Stochastic video generation with a learned prior.  In _International Conference on Machine Learning_ , pages 1174–1183. PMLR, 2018.
  * Duggal et al. [2019] S. Duggal, S. Wang, W.-C. Ma, R. Hu, and R. Urtasun.  Deeppruner: Learning efficient stereo matching via differentiable patchmatch.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 4384–4393, 2019.
  * Efros and Freeman [2001] A. A. Efros and W. T. Freeman.  Image quilting for texture synthesis and transfer.  In _Proceedings of the 28th annual conference on Computer graphics and interactive techniques_ , pages 341–346, 2001.
  * Efros and Leung [1999] A. A. Efros and T. K. Leung.  Texture synthesis by non-parametric sampling.  In _Proceedings of the seventh IEEE international conference on computer vision_ , volume 2, pages 1033–1038. IEEE, 1999.
  * Fišer et al. [2016] J. Fišer, O. Jamriška, M. Lukáč, E. Shechtman, P. Asente, J. Lu, and D. Sỳkora.  Stylit: illumination-guided example-based stylization of 3d renderings.  _ACM Transactions on Graphics (TOG)_ , 35(4):1–11, 2016.
  * Franceschi et al. [2020] J.-Y. Franceschi, E. Delasalles, M. Chen, S. Lamprier, and P. Gallinari.  Stochastic latent residual video prediction.  In _International Conference on Machine Learning_ , pages 3233–3246. PMLR, 2020.
  * Goodfellow et al. [2014] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio.  Generative adversarial networks.  _arXiv preprint arXiv:1406.2661_ , 2014.
  * Granot et al. [2021] N. Granot, B. Feinstein, A. Shocher, S. Bagon, and M. Irani.  Drop the gan: In defense of patches nearest neighbors as single image generative models.  _arXiv preprint arXiv:2103.15545_ , 2021.
  * Gur et al. [2020] S. Gur, S. Benaim, and L. Wolf.  Hierarchical patch vae-gan: Generating diverse videos from a single sample.  _arXiv preprint arXiv:2006.12226_ , 2020.
  * Hertzmann et al. [2001] A. Hertzmann, C. E. Jacobs, N. Oliver, B. Curless, and D. H. Salesin.  Image analogies.  In _Proceedings of the 28th annual conference on Computer graphics and interactive techniques_ , pages 327–340, 2001.
  * Huang et al. [2016] J.-B. Huang, S. B. Kang, N. Ahuja, and J. Kopf.  Temporally coherent completion of dynamic video.  _ACM Transactions on Graphics (TOG)_ , 35(6):1–11, 2016.
  * Jamriška et al. [2015] O. Jamriška, J. Fišer, P. Asente, J. Lu, E. Shechtman, and D. Sỳkora.  Lazyfluids: appearance transfer for fluid animations.  _ACM Transactions on Graphics (TOG)_ , 34(4):1–10, 2015.
  * Jamriška et al. [2019] O. Jamriška, Š. Sochorová, O. Texler, M. Lukáč, J. Fišer, J. Lu, E. Shechtman, and D. Sỳkora.  Stylizing video by example.  _ACM Transactions on Graphics (TOG)_ , 38(4):1–11, 2019.
  * Karras et al. [2017] T. Karras, T. Aila, S. Laine, and J. Lehtinen.  Progressive growing of gans for improved quality, stability, and variation.  _arXiv preprint arXiv:1710.10196_ , 2017.
  * Krähenbühl et al. [2009] P. Krähenbühl, M. Lang, A. Hornung, and M. Gross.  A system for retargeting of streaming video.  In _ACM SIGGRAPH Asia 2009 papers_ , 2009.
  * Kwatra et al. [2003] V. Kwatra, A. Schödl, I. Essa, G. Turk, and A. Bobick.  Graphcut textures: Image and video synthesis using graph cuts.  _Acm transactions on graphics (tog)_ , 22(3):277–286, 2003.
  * Kwatra et al. [2005] V. Kwatra, I. Essa, A. Bobick, and N. Kwatra.  Texture optimization for example-based synthesis.  In _ACM SIGGRAPH 2005 Papers_ , pages 795–802. 2005.
  * Kwatra et al. [2007] V. Kwatra, D. Adalsteinsson, T. Kim, N. Kwatra, M. Carlson, and M. Lin.  Texturing fluids.  _IEEE transactions on visualization and computer graphics_ , 13(5):939–952, 2007.
  * LeCun [1998] Y. LeCun.  The mnist database of handwritten digits.  _http://yann. lecun. com/exdb/mnist/_ , 1998.
  * Lee et al. [2018] A. X. Lee, R. Zhang, F. Ebert, P. Abbeel, C. Finn, and S. Levine.  Stochastic adversarial video prediction.  _arXiv preprint arXiv:1804.01523_ , 2018.
  * Lee et al. [2019] J. Lee, D. Ramanan, and R. Girdhar.  Metapix: Few-shot video retargeting.  _arXiv preprint arXiv:1910.04742_ , 2019.
  * Liao et al. [2017] J. Liao, Y. Yao, L. Yuan, G. Hua, and S. B. Kang.  Visual attribute transfer through deep image analogy.  _arXiv preprint arXiv:1705.01088_ , 2017.
  * Liu et al. [2009] M. Liu, S. Chen, J. Liu, and X. Tang.  Video completion via motion guided spatial-temporal global optimization.  In _Proceedings of the 17th ACM international conference on Multimedia_ , pages 537–540, 2009.
  * Mallya et al. [2020] A. Mallya, T.-C. Wang, K. Sapra, and M.-Y. Liu.  World-consistent video-to-video synthesis.  _arXiv preprint arXiv:2007.08509_ , 2020.
  * Okabe et al. [2009] M. Okabe, K. Anjyo, T. Igarashi, and H.-P. Seidel.  Animating pictures of fluid using video examples.  In _Computer Graphics Forum_ , volume 28, pages 677–686. Wiley Online Library, 2009.
  * Paszke et al. [2019] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc., 2019.  URL http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.
  * Rav-Acha et al. [2006] A. Rav-Acha, Y. Pritch, and S. Peleg.  Making a long video short: Dynamic video synopsis.  In _2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06)_ , volume 1, pages 435–441. IEEE, 2006.
  * Ren et al. [2020] J. Ren, M. Chai, S. Tulyakov, C. Fang, X. Shen, and J. Yang.  Human motion transfer from poses in the wild.  In _European Conference on Computer Vision_ , pages 262–279. Springer, 2020.
  * Rong and Tan [2006] G. Rong and T.-S. Tan.  Jump flooding in gpu with applications to voronoi diagram and distance transform.  In _Proceedings of the 2006 symposium on Interactive 3D graphics and games_ , pages 109–116, 2006.
  * Rubinstein et al. [2008] M. Rubinstein, A. Shamir, and S. Avidan.  Improved seam carving for video retargeting.  _ACM transactions on graphics (TOG)_ , 27(3):1–9, 2008.
  * Ruder et al. [2016] M. Ruder, A. Dosovitskiy, and T. Brox.  Artistic style transfer for videos.  In _German conference on pattern recognition_ , pages 26–36. Springer, 2016.
  * Saito et al. [2017] M. Saito, E. Matsumoto, and S. Saito.  Temporal generative adversarial nets with singular value clipping.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2830–2839, 2017.
  * Sato et al. [2018a] S. Sato, Y. Dobashi, T. Kim, and T. Nishita.  Example-based turbulence style transfer.  _ACM Transactions on Graphics (TOG)_ , 37(4):1–9, 2018a.
  * Sato et al. [2018b] S. Sato, Y. Dobashi, and T. Nishita.  Editing fluid animation using flow interpolation.  _ACM Transactions on Graphics (TOG)_ , 37(5):1–12, 2018b.
  * Schödl et al. [2000] A. Schödl, R. Szeliski, D. H. Salesin, and I. Essa.  Video textures.  In _Proceedings of the 27th annual conference on Computer graphics and interactive techniques_ , pages 489–498, 2000.
  * Shaham et al. [2019] T. R. Shaham, T. Dekel, and T. Michaeli.  Singan: Learning a generative model from a single natural image.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 4570–4580, 2019.
  * Siarohin et al. [2019a] A. Siarohin, S. Lathuilière, S. Tulyakov, E. Ricci, and N. Sebe.  Animating arbitrary objects via deep motion transfer.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2377–2386, 2019a.
  * Siarohin et al. [2019b] A. Siarohin, S. Lathuilière, S. Tulyakov, E. Ricci, and N. Sebe.  First order motion model for image animation.  _Advances in Neural Information Processing Systems_ , 32:7137–7147, 2019b.
  * Simakov et al. [2008] D. Simakov, Y. Caspi, E. Shechtman, and M. Irani.  Summarizing visual data using bidirectional similarity.  In _2008 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 1–8. IEEE, 2008.
  * Teed and Deng [2020] Z. Teed and J. Deng.  Raft: Recurrent all-pairs field transforms for optical flow.  In _European conference on computer vision_ , pages 402–419. Springer, 2020.
  * Tran et al. [2015] D. Tran, L. Bourdev, R. Fergus, L. Torresani, and M. Paluri.  Learning spatiotemporal features with 3d convolutional networks.  In _Proceedings of the IEEE international conference on computer vision_ , pages 4489–4497, 2015.
  * Tulyakov et al. [2018] S. Tulyakov, M.-Y. Liu, X. Yang, and J. Kautz.  Mocogan: Decomposing motion and content for video generation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1526–1535, 2018.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008, 2017.
  * Villegas et al. [2017] R. Villegas, J. Yang, S. Hong, X. Lin, and H. Lee.  Decomposing motion and content for natural video sequence prediction.  _arXiv preprint arXiv:1706.08033_ , 2017.
  * Villegas et al. [2018] R. Villegas, D. Erhan, H. Lee, et al.  Hierarchical long-term video prediction without supervision.  In _International Conference on Machine Learning_ , pages 6038–6046. PMLR, 2018.
  * Villegas et al. [2019] R. Villegas, A. Pathak, H. Kannan, D. Erhan, Q. V. Le, and H. Lee.  High fidelity video prediction with large stochastic recurrent neural networks.  _arXiv preprint arXiv:1911.01655_ , 2019.
  * Vondrick et al. [2016] C. Vondrick, H. Pirsiavash, and A. Torralba.  Generating videos with scene dynamics.  _arXiv preprint arXiv:1609.02612_ , 2016.
  * Wang et al. [2018] T.-C. Wang, M.-Y. Liu, J.-Y. Zhu, G. Liu, A. Tao, J. Kautz, and B. Catanzaro.  Video-to-video synthesis.  _arXiv preprint arXiv:1808.06601_ , 2018.
  * Wang et al. [2019] T.-C. Wang, M.-Y. Liu, A. Tao, G. Liu, J. Kautz, and B. Catanzaro.  Few-shot video-to-video synthesis.  _arXiv preprint arXiv:1910.12713_ , 2019.
  * Wang et al. [2020] Y. Wang, P. Bilinski, F. Bremond, and A. Dantcheva.  Imaginator: Conditional spatio-temporal gan for video generation.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 1160–1169, 2020.
  * Wang et al. [2021] Y. Wang, F. Bremond, and A. Dantcheva.  Inmodegan: Interpretable motion decomposition generative adversarial network for video generation.  _arXiv preprint arXiv:2101.03049_ , 2021.
  * Wei and Levoy [2000] L.-Y. Wei and M. Levoy.  Fast texture synthesis using tree-structured vector quantization.  In _Proceedings of the 27th annual conference on Computer graphics and interactive techniques_ , pages 479–488, 2000.
  * Wei et al. [2009] L.-Y. Wei, S. Lefebvre, V. Kwatra, and G. Turk.  State of the art in example-based texture synthesis.  In _Eurographics 2009, State of the Art Report, EG-STAR_ , pages 93–117. Eurographics Association, 2009.
  * Wexler et al. [2004] Y. Wexler, E. Shechtman, and M. Irani.  Space-time video completion.  In _Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004._ , volume 1, pages I–I. IEEE, 2004.
  * Wolf et al. [2007] L. Wolf, M. Guttmann, and D. Cohen-Or.  Non-homogeneous content-driven video-retargeting.  In _Proceedings of the Eleventh IEEE International Conference on Computer Vision (ICCV)_ , 2007.
  * Yang et al. [2020] Z. Yang, W. Zhu, W. Wu, C. Qian, Q. Zhou, B. Zhou, and C. C. Loy.  Transmomo: Invariance-driven unsupervised video motion retargeting.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5306–5315, 2020.

##  Appendix A Implementation Details

All RGB values in the videos are scaled to $[-1,1]$. All runs were conducted
on Quadro RTX 8000 GPU.

#### Creating the Spatio-Temporal Pyramid

Given a downscaling factor $r$ (where $r=(r_{H},r_{W},r_{T})$) and a minimal
size $m_{S},m_{T}$, we keep downscaling the input video in all dimensions
until it “hits” the minimal size in the spatial or temporal dimensions. Assume
we hit the minimal spatial dimension first, we keep on downscaling the
temporal dimension until reaching its minimal size, while keeping the spatial
dimensions fixed on its minimal size (and the opposite goes if we first hit
the temporal dimension, keeping on downscaling the spatial dimensions while
keeping the temporal fixed). The minimal size of the spatial dimensions,
$m_{S}$, is the minimum between both height and width (namely, no spatial
dimension will be smaller than $m_{S}$).

We use cubic downscaling interpolation for both temporal and sptial
dimensions. We tried to use nearest interpolation on the temporal dimension,
because it might make more sense sometimes, but found that in most
applications it performed the same or worse.

#### Diverse Generation

We used Gaussian noise with standard deviation of $2-5$. Downscaling factor is
$0.82$ for the spatial dimensions (height and width) and $0.87$ for the
temporal dimension. The minimal size of the pyramid is set to $3$ frames with
minimal spatial dimension of $15$ pixels. We use patch size $(3\times 7\times
7)$, where 3 is in the temporal dimension. We use $5$ EM-like iterations in
each scale of the pyramid. When the number of voxels ($T\times H\times W$) is
larger than $3,000,000$ we change the number of EM-like iterations to $1$, and
the patch-size to $(3\times 5\times 5)$. This change reduce runtime without
hurting the quality of the results.

#### Video Analogies

For all examples we use patch size $(3\times 5\times 5)$ and $\alpha=1$ (for
completeness score). For all-pairs examples we use downscaling factor is $0.9$
for all dimensions. The minimal size of the pyramid is set to $3$ frames with
minimal spatial dimension of $20$ pixels. $1$ EM-like iterations per scale.
For sketch-to-video examples we use downscaling factor of $0.78$ for all
dimensions and minimal size is $5$ frames and minimal spatial dimension of
$35$. $3$ EM-like iterations per scale (and $1$ for the last two scales, to
save runtime). Runtime per result is about 1 minute.

#### Layout-Appearance Tradeoff in Video Analogies

Since we are trying to create a new video whose spatio-temporal layout
(modeled with the dynamic structure) taken from one video and its appearance
from another, there’s an inherent tradeoff of which of the two we want to be
better preserved in the result. The dynamic structure is “enforced” by using
the auxiliary channels in $Q$ and $K$. Removing these channels would generate
a video that is much more similar in its appearance to $S$ but bears less
resemblance to the spatio-temporal layout of $C$. We can control this tradeoff
by setting an upper limit in the pyramid from which we stop using the
auxiliary channels. In our results it was best to set the maximal scale at
half the pyramid height.

##  Appendix B PatchMatch Implementation Details

In all applications we use $L2$ as the distance function between. In Fig. 8 we
show another more detailed comparison between our PatchMatch implementation
and the exhaustive nearest-neighbor search used by GPNN. Our implementation
has time complexity of $O(n\times d)$ and $O(n)$ additional memory (where $n$
is the video size and $d$ is the patch size), compared to GPNN, with time
complexity of $O(n^{2}\times d)$ and memory footprint $O(n\times d)$. This is
easily seen in the figure. We use the same propagation and random search steps
as in the original PatchMatch paper [9], using the “jump flood” scheme [45].
In each PatchMatch iteration we look at 4 neighbors at distance $step$ (with
additional small noise for the exact position of the neighbor, and without)
and a random search. However, we only use 15 PatchMatch iterations per VPNN
usage, this is done by searching for $step=8,4,1$ 5 times.

---
Figure 8: Nearest Neighbor Search Comparison using PatchMatch (in our method)
vs. exhaustive search (used by GPNN [24]). GPNN exceeds GPU memory at medium
resolution (480p) with the original patch size $(3,7,7)$. The dashed line with
smaller patch size $(3,5,5)$ is intended to show the quadratic trend with more
data points.
---
Figure 9:  Generation Time Note y-axis is in log-scale. This is the same graph
as in Fig. 5, shown here in log-scale so it would be easier to get a sense of
the actual runtime needed to generate a random 13-frames video in the relevant
resolution (x-axis).

##  Appendix C Comparison details

For each input video in HP-VAE-GAN and SinGAN-GIF datasets we generated the
same number of random sample as publicly available (10 generations for each
video in HP-VAE-GAN dataset, and 6 generations for each video in SinGAN-GIF
dataset), and compared their SVFID and diversity.

#### Video Diversity Index

The video adaptation of the diversity index (originally proposed for images by
[52]) is: given an input video, the standard deviation of each video position
(3D RGB element in the video, converted to grayscale) is calculated across all
generated samples, and then averaged across all pixels. This is then divided
by the standard deviation of the voxels in the input video.


# Cyclic groups with the same Hodge series

Daryl R. DeFord  Peter G. Doyle

(Version dated 8 April 2014
No Copyright††thanks:  The authors hereby waive all copyright and related or
neighboring rights to this work, and dedicate it to the public domain. This
applies worldwide. )

###### Abstract

The Hodge series of a finite matrix group is the generating function
$\sum_{k,p}x^{k}y^{p}$ for invariant exterior forms of specified order $p$ and
degree $k$. Lauret, Miatello, and Rossetti gave examples of pairs of non-
conjugate cyclic groups having the same Hodge series; the corresponding space
forms are isospectral for the Laplacian on $p$-forms for all $p$, but not for
all natural operators. Here we explain, simplify, and extend their
investigations.

##  0 Terminology and notation

We adopt terminology and notation to avoid some common headaches.

### ‘Just if’.

We follow John Conway in using ‘just if’ in place of the more cumbersome ‘if
and only if’.

### Modular arithmetic.

$a\equiv_{q}b$ means $a$ is equivalent to $b$ mod $q$. We write
$\mathbf{Z}_{q}$ for $\mathbf{Z}/q\mathbf{Z}$, and $\mathbf{Z}^{\star}_{q}$
for its invertible elements, taking $\mathbf{Z}^{\star}_{1}=\\{0\\}$. For
$a\in\mathbf{Z}_{q}$, $b\in\mathbf{Z}^{\star}_{q}$ we write $a/_{q}\,b$ for
the quotient mod $q$.

### Angles; roots of unity.

We use $\tau=2\pi$ in representing angles, because as Vi Hart [5] has so
persuasively argued, _$\pi$ is wrong_. We write

$\omega_{q}=\exp(i\tau/q)$

for the standard $q$th root of unity, so that

$\omega_{q}^{k}=\exp(i\tau k/q)=e^{i\tau\frac{k}{q}}.$

### Unitary and orthogonal groups; conjugacy.

As usual we write $U_{n}\subset GL_{n}(\mathbf{C})$ for the $n$-by-$n$ unitary
matrices, and $O_{n}=U_{n}\cap GL_{n}(\mathbf{R})$ for the orthogonal
matrices.

When we say that two matrices or groups are ‘conjugate’, we mean that they are
conjugate within $GL_{n}(\mathbf{C})$, so that the conjugating matrix can be
any invertible complex matrix. Allowing this generality for the conjugating
matrix is no big deal, because unitary matrices or groups that are conjugate
within $GL_{n}(\mathbf{C})$ are already conjugate within $U_{n}$; real
matrices or groups that are conjugate within $GL_{n}(\mathbf{R})$ are already
conjugate within $GL_{n}(\mathbf{R})$; orthogonal matrices or groups that are
conjugate within $GL_{n}(\mathbf{C})$ are already conjugate within $O_{n}$.

We will be dealing with finite groups of matrices, which we will be interested
in only up to conjugacy. Any finite group of complex matrices is conjugate to
a subgroup of $U_{n}$; any finite group of real matrices is conjugate to a
subgroup of $O_{n}$. So we may take our groups to be unitary—and if real,
orthogonal—without sacrificing generality.

##  1 Hodge series

Let $G\subset U_{n}$ be a finite group of $n$-by-$n$ complex matrices, assumed
to be unitary. Any $g\in G$ is diagonalizable, with the roots
$\lambda_{1},\ldots,\lambda_{n}$ of its characteristic polynomial

$\chi_{g}(x)=\det(I_{n}-xg)=\prod_{i}(x-\lambda_{i})$

being roots of unity.

Define the _Hodge series_

$\displaystyle\Lambda_{G}(x,y)$ $\displaystyle=$
$\displaystyle\frac{1}{|G|}\sum_{g}\frac{\det(I_{n}+yg)}{\det(I_{n}-xg)}$
$\displaystyle=$
$\displaystyle\frac{1}{|G|}\sum_{g}\frac{y^{n}\chi_{g}(-1/y)}{x^{n}\chi_{g}(1/x)}.$

This series is a particular kind of _Molien series_ : Crass [1, p. 31] calls
it the ‘exterior Molien series’. By a generalization of Molien’s theorem (cf.
Molien [9], Stanley [11]) this is the generating function for $G$-invariant
exterior forms:

$\Lambda_{G}(x,y)=\sum_{p,k}P_{k}^{p}x^{k}y^{p},$

where $P_{k}^{p}$ is the dimension of the space of $G$-invariant $p$-forms
whose coefficients are homogeneous polynomials of degree $k$ in
$x_{1},\ldots,x_{n}$.

For example we have

$\Lambda_{\\{I_{n}\\}}=\frac{(1+y)^{n}}{(1-x)^{n}}$

and

$\displaystyle\Lambda_{\\{\pm I_{n}\\}}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(\frac{(1+y)^{n}}{(1-x)^{n}}+\frac{(1-y)^{n}}{(1+x)^{n}}\right)$
$\displaystyle=$
$\displaystyle\frac{\frac{1}{2}((1+x^{n})(1+y^{n})+(1-x^{n})(1-y^{n}))}{(1-x^{2})^{n}}.$

Aside. Here’s a more interesting example. The group $G_{120}$ of proper and
improper symmetries of the icosahedron in Euclidean 3-space has Hodge series

$\Lambda_{G_{120}}=\frac{(1+xy)(1+x^{5}y)(1+x^{9}y)}{(1-x^{2})(1-x^{6})(1-x^{10})}.$

As this might suggest, the algebra of invariant forms is generated by
polynomial invariants of degrees $2,6,10$ and their exterior derivatives of
degrees $1,5,9$. For the index-2 subgroup $G_{60}$ of proper symmetries we
have

$\Lambda_{G_{60}}=\frac{(1+x^{15})(1+y^{3})+(x+x^{5}+x^{6}+x^{9}+x^{10}+x^{14})(y+y^{2})}{(1-x^{2})(1-x^{6})(1-x^{10})}.$

This is a little harder to decipher, though the generating function for
invariant polynomials, obtained by setting $y=0$, is clear enough:

$\Lambda_{G_{60}}(x,0)=\frac{1+x^{15}}{(1-x^{2})(1-x^{6})(1-x^{10})}.$

Here we see the $G_{120}$-invariants of degrees 2,6,10, together with a new
invariant of degree $15$ (the product of the linear forms determining the $15$
planes of symmetry of the icosahedron) whose square is $G_{120}$-invariant,
though it itself is only $G_{60}$-invariant.

######  Exercise 1.

Compute these two Hodge series.

Hint. Resist the temptation to consult Klein [7] or Doyle and McMullen [2]:
You do not need to know the matrix groups explicitly, because the contribution
of a matrix to the Hodge series depends only on its conjugacy class. This fact
is the basis of the notion of ‘almost-conjugacy’ of groups, which we’ll get to
in a jiffy.

##  2 Hodge equivalence

We are interested in pairs of groups $G,H\subset U_{n}$ (and in particular,
pairs of real groups $G,H\subset O_{n}$) having the same Hodge series, meaning
that they have the same dimensions of spaces of invariant forms. We call such
pairs _Hodge-equivalent_ , and write $G\equiv_{\Lambda}H$.

Of course if the groups $G$ and $H$ are conjugate then they are Hodge-
equivalent. More generally, say that $G$ and $H$ are _almost conjugate_ if
there is a bijection $\sigma:G\rightarrow H$ such that $g$ and $\sigma(g)$ are
conjugate. This is the same as requiring that $g$ and $\sigma(g)$ have the
same eigenvalues, so that they make the same contribution to the Hodge series.
Thus almost conjugate groups are Hodge-equivalent.

It is relatively easy to find non-conjugate pairs $(G,H)$ that are almost
conjugate, and hence Hodge-equivalent. (See Gilkey [4], Ikeda [6].) Here we
are interested in pairs (and specifically, real pairs) that are Hodge-
equivalent without being almost conjugate. The first such examples were given
in [8] by Lauret, Miatello, and Rossetti (henceforth ‘LMR’). They exhibited a
multitude of examples arising already among cyclic groups. For cyclic groups,
conjugacy is the same as almost-conjugacy, so their examples can be briefly
described as being Hodge-equivalent without being conjugate. Our goal here is
to explain, simplify, and extend their findings.

##  3 Isospectrality

We discuss here the connection to spectral theory, which is what motivated LMR
to construct their examples. This is meant for background only: In the
approach taken here, spectral theory plays no role. In this section we
restrict to real groups, which we may assume to be orthogonal.

A finite real group $G\subset O_{n}$ is classified up to conjugacy by the
isometry type of the quotient orbifold $Q_{G}=G\backslash S^{n-1}$. According
to Ikeda [6], $G$ and $H$ are Hodge-equivalent just if the quotients $Q_{G}$
and $Q_{H}$ are isospectral for the Hodge Laplacian on $p$-forms for
$p=0,\ldots,n-1$. According to Pesce [10], $Q_{G}$ and $Q_{H}$ are _strongly
isospectral_ (isospectral for all natural operators of a certain kind) just if
$G$ and $H$ are almost conjugate. Using this dictionary, looking for Hodge-
equivalent groups that are not almost conjugate is the same as looking for
Hodge-isospectral orbifolds that are not strongly isospectral. This is why LMR
were interested in this question.

Ikeda, Pesce, and LMR restricted their investigations to the case of groups
whose action on $S_{n-1}$ is fixed-point free (no $g\neq 1$ has $1$ as an
eigenvalue). In this case $Q_{G}$ is a manifold, called a _spherical space
form_. For $n$ odd (i.e. $n-1$ even) we have only the sphere
$\\{I_{n}\\}\backslash S^{n-1}$ and projective space $\\{\pm
I_{n}\\}\backslash S^{n-1}$. So the restriction to fixed-point free actions
effectively limits us to the case of even $n$.

When $G$ is cyclic, as in the LMR examples, $Q_{G}$ is a _lens space_. As
observed above, for cyclic groups almost-conjugacy is the same as conjugacy,
which is the same as isometry of the corresponding lens space. So we can
briefly describe the LMR examples as Hodge-isospectral lens spaces that are
not isometric, hence not almost conjugate, hence not strongly isospectral.

This ends our discussion of isospectrality. The rest is algebra.

##  4 Cyclic groups

For any $q$ and $s=(s_{1},\ldots,s_{n})$, write

$\omega_{q}^{s}=(\omega_{q}^{s_{1}},\ldots,\omega_{q}^{s_{n}}).$

Consider the finite cyclic group

$L(q,s)=\langle\mathrm{diag}(\omega_{q}^{s})\rangle=\\{\mathrm{diag}(\omega_{q}^{ks}):k\in\mathbf{Z}_{q}\\}.$

This group has order $q$ if $\gcd(q,s_{1},\ldots,s_{n})=1$. Up to conjugacy,
any finite cyclic subgroup of $U_{n}$ can be written in this way.

The cyclic group $L(q,s)$ doesn’t change (up to conjugacy) when you rearrange
the entries of $s$, or multiply them all by an element of the multiplicative
group $\mathbf{Z}^{\star}_{q}$. Conversely, the groups $L(q,s)$ and
$L(q,s^{\prime})$ are conjugate just if, when viewed as multisets mod $q$,
$s^{\prime}$ can be obtained from $s$ by multiplying by an invertible element.

Now take $n=2m$, and let $\rho:GL_{m}(\mathbf{C})\mapsto GL_{2m}(\mathbf{R})$
be the standard embedding, so that $\rho(\omega_{q}^{s})$ is the diagonal sum
of the 2-by-2 matrices

$\displaystyle\rho(((\omega_{q}^{s_{i}})))$ $\displaystyle=$
$\displaystyle\exp(\tau\frac{s_{i}}{q}((0,-1),(1,0)))$ $\displaystyle=$
$\displaystyle((\cos(\tau s_{i}/q),-\sin(\tau s_{i}/q)),(\sin(\tau
s_{i}/q),\cos(\tau s_{i}/q))).$

Up to conjugacy in $U_{n}$,

$\rho(L(q,s))\equiv L(q,{s^{\pm}})$

where

${s^{\pm}}=(s_{1},-s_{1},\ldots,s_{m},-s_{m}).$

Let us write

$L^{\pm}(q,s)=L(q,{s^{\pm}})\equiv\rho(L(q,s)).$

For the Hodge series we have

$\displaystyle\Lambda_{L^{\pm}(q,s)}$ $\displaystyle=$
$\displaystyle\frac{1}{q}\sum_{k}\prod_{i}\frac{(1+y\omega_{q}^{ks_{i}})(1+y\omega_{q}^{-ks_{i}})}{(1-x\omega_{q}^{ks_{i}})(1-x\omega_{q}^{-ks_{i}})}$
$\displaystyle=$ $\displaystyle\frac{1}{q}\sum_{k}\prod_{i}\frac{1+2\cos(\tau
ks_{i}/q)y+y^{2}}{1-2\cos(\tau ks_{i}/q)x+x^{2}}.$

##  5 The LMR construction

The LMR examples involve cyclic subgroups of $O_{2m}$ of the form

$\rho(L(r^{2}t,rta+1))\equiv L^{\pm}(r^{2}t,rta+1),$

where $r>2$, $t\geq 1$, $a=(a_{1},\ldots,a_{m})\in\mathbf{Z}^{m}$. Since we
prefer to keep our matrices diagonal we’ll define

$\displaystyle\mathrm{LMR}(r,t,a)$ $\displaystyle=$ $\displaystyle
L^{\pm}(r^{2}t,rta+1)$ $\displaystyle=$ $\displaystyle
L(r^{2}t,(rta_{1}+1,-rta_{1}-1,\ldots,rta_{m}+1,-rta_{m}-1)).$

Note. You may wish to mentally set $t=1$: All evidence indicates that what
works for $t=1$ works in general, and in particular the criterion in Theorem 1
below does not involve $t$.

As we will be seeing, what’s special about the LMR construction is the
following fact:

$(rtc+1)(rtd+1)\equiv_{r^{2}t}rt(c+d)+1.$

Thus the multiplicative subgroup
$\\{rtc+1:c\in\mathbf{Z}_{r}\\}\subset\mathbf{Z}^{\star}_{r^{2}t}$ is cyclic
of order $r$, generated by $rt+1$; the map $rtc+1\mapsto c$ takes the
logarithm of $rtc+1$ base $rt+1$, and gives an isomorphism to the additive
group $\mathbf{Z}_{r}$.

As a first consequence of this, notice that we can add a constant $c$ to the
entries of $a$ without changing the conjugacy class:

$\mathrm{LMR}(r,t,a)\equiv\mathrm{LMR}(r,t,a+c).$

In fact, this characterizes all such coincidences: Let us write

$a\equiv_{S_{m}\times\mathbf{Z}_{r}}a^{\prime}$

if for some $c$, $a+c$ and $a^{\prime}$ are the same as multisets mod $r$.
Then $\mathrm{LMR}(r,t,a)\equiv\mathrm{LMR}(r,t,a^{\prime})$ just if
$a\equiv_{S_{m}\times\mathbf{Z}_{r}}a^{\prime}$.

All the LMR pairs are (conjugate to) pairs of the special form

$(\mathrm{LMR}(r,t,a),\mathrm{LMR}(r,t,-a)).$

Not all such pairs are Hodge-equivalent, however.

##  6 Theorem

In this section we formulate a criterion for Hodge-equivalence of the LMR pair
$(\mathrm{LMR}(r,t,a),\mathrm{LMR}(r,t,-a))$. While this criterion has not
been shown to be necessary, it holds in all the cases (thousands and
thousands!) where the LMR construction has been found to succeed.

######  Definition 1.

Say that $a=(a_{1},\ldots,a_{m})$ is:

  * •

_univalent mod $r$_ if its entries are distinct mod $r$;

  * •

_reversible mod $r$_ if $a\equiv_{S_{m}\times\mathbf{Z}_{r}}-a$;

  * •

_good mod $r$_ if it is univalent or reversible mod $r$;

  * •

_hereditarily good mod $r$_ if it is good mod $d$ for all $d$ dividing $r$;

  * •

_useful mod $r$_ if it is hereditarily good and irreversible mod $r$.

Any $a$ is reversible (hence good) mod $1$ or $2$. So in checking hereditary
goodness we need only check divisors $d>2$.

In section 8 below we will prove the following:

######  Theorem 1.

If $a$ is hereditarily good mod $r$ then for any $t$,

$\mathrm{LMR}(r,t,a)\equiv_{\Lambda}\mathrm{LMR}(r,t,-a).$

If $a$ is reversible mod $r$ then $a$ is hereditarily good mod $r$, but in
this case $\mathrm{LMR}(r,t,a)$ and $\mathrm{LMR}(r,t,-a)$ are conjugate. So
this result tells us something useful only if $a$ is hereditarily good without
being reversible, which is our definition of ‘useful’.

##  7 Examples

$(0,1,3)$ is:

  * •

univalent mod $4,5,6,\ldots$;

  * •

reversible mod $1,2,4,5$;

  * •

good mod any $r\neq 3$;

  * •

hereditarily good mod any $r$ not divisible by $3$;

  * •

useful mod any $r\geq 7$ not divisible by $3$.

Putting $r=7,8,10$, $t=1$, we get Hodge-equivalent but non-conjugate pairs of
orders $49,64,100$; Putting $r=7$, $t=2$ we get a pair of order $98$.

$(0,1,4)$ is:

  * •

univalent mod $5,6,7,\ldots$;

  * •

reversible mod $1,2,5,7$;

  * •

good mod any $r\neq 3,4$;

  * •

hereditarily good mod any $r$ not divisible by $3$ or $4$;

  * •

useful mod any $r\geq 10$ not divisible by $3$ or $4$.

Putting $r=10$, $t=1$ gives a pair of order 100. Together with the four pairs
coming from $(0,1,3)$ above, this gives us all five inequivalent pairs with
$m=3$, $q\leq 100$ (see Table 1 of LMR [8]).

We’ll call the simplest of these pairs the _$49$ -pair_:

$\displaystyle(\mathrm{LMR}(7,1,(0,1,3)),\mathrm{LMR}(7,1,(0,-1,-3)))$
$\displaystyle=$ $\displaystyle(L^{\pm}(49,(1,8,22)),L^{\pm}(49,(1,-6,-20))$
$\displaystyle=$
$\displaystyle(L(49,(1,-1,8,-8,22,-22)),L(49,(1,-1,-6,6,-20,20)))$
$\displaystyle\equiv$
$\displaystyle(L(49,(-6,6,1,-1,15,-15)),L(49,(1,-1,-6,6,-20,20)))$
$\displaystyle\equiv$
$\displaystyle(L^{\pm}(49,(1,6,15)),L^{\pm}(49,(1,6,20))).$

Here at the next-to-last step we’ve multiplied the list $(1,-1,8,-8,22,-22)$
by $-6$ mod $49$ so as to get the lexicographically least representation that
the computer spits out in its search for Hodge-equivalent pairs.

##  8 Proof

It is easy enough to verify that the members of the $49$-pair are Hodge-
equivalent by explicit computation of their Hodge series. The same goes for as
many other pairs as you like, but this only gets you a finite number of
examples.

Using a very explicit representation theory argument, LMR proved Hodge-
equivalence of the 49-pair in a way that extends to cover all pairs of the
form

$(\mathrm{LMR}(r,t,(0,1,3)),\mathrm{LMR}(r,t,(0,-1,-3)))$

with $r$ not divisible by $3$. As we have seen, this infinite family is just
what we get out of Theorem 1 if we take $a=(0,1,3)$. It includes $19$ of the
$62$ examples in the list given by LMR of all pairs with $m=3$ and $q\leq
300$.

To prove Theorem 1 in its full generality, we’re going to show that the two
Hodge series involved are identical as rational functions of $x$ and $y$. This
comes down to a bunch of manipulations with partial fraction expansions. It
all starts with the following familiar identity.

######  Lemma 1.

$\prod_{i=1}^{n}\frac{1}{x-\lambda_{i}}=\sum_{i=1}^{n}\frac{1}{x-\lambda_{i}}\prod_{j\neq
i}\frac{1}{\lambda_{i}-\lambda_{j}}.$

Proof. This follows from the theory of partial fractions.

Alternatively, combine terms on the right over the common denominator
$\prod_{i}(x-\lambda_{i})$. The numerator is

$\sum_{i}\prod_{j\neq i}\frac{x-\lambda_{j}}{\lambda_{i}-\lambda_{j}}.$

This is a polynomial of degree $n-1$ which takes the value $1$ for
$x=\lambda_{1},\ldots,\lambda_{n}$. These $n$ values of $x$ are distinct
(thinking of the $\lambda_{i}$’s as indeterminates), so the numerator is
identically $1$. $\quad\qed$

Proof of Theorem 1. For general $q$, $s\in(\mathbf{Z}_{q})^{m}$ put

$H_{q,s}(x,y)=\sum_{k\in\mathbf{Z}_{q}}\prod_{i}\frac{y-\omega_{q}^{ks_{i}}}{x-\omega_{q}^{ks_{i}}}$

so that

$\Lambda_{L(q,s)}(x,y)=\frac{1}{q}\frac{y^{n}}{x^{n}}H_{q,s}(-1/y,1/x).$

Separate the sum for $H_{q,s}$ into pieces according to $\gcd(k,q)$ by putting

$H^{\star}_{d,s}=\sum_{k\in\mathbf{Z}^{\star}_{d}}\prod_{i}\frac{y-\omega_{d}^{ks_{i}}}{x-\omega_{d}^{ks_{i}}}$

so that

$H_{q,s}=\sum_{d\,|\,q}H^{\star}_{d,s}.$

To prove the theorem, we must show that if $a$ is hereditarily good mod $r$
then

$H_{r^{2}t,{(rta+1)^{\pm}}}=H_{r^{2}t,{(-rta+1)^{\pm}}}.$

Our strategy will be to show that for all $d\,|\,r^{2}t$ we have

$H^{\star}_{d,{(rta+1)^{\pm}}}=H^{\star}_{d,{(-rta+1)^{\pm}}}.$

We dispose first of the case where ${(rta+1)^{\pm}}$ is not univalent mod $d$.
This is taken care of by the assumption that $a$ is hereditarily good, but
things are not quite as straight-forward as you might be expecting, because
that condition deals with divisors of $r$, and here $d$ is any divisor of
$r^{2}t$.

We pass over the trivial cases $d=1,2$. Mod any $d>2$, there is no overlap
between $rta+1$ and $-(rta+1)$, so if ${(rta+1)^{\pm}}$ is not univalent mod
$d$ then neither is $rta$.

We pause for a lemma.

######  Lemma 2.

For $d,\alpha,\beta\in\mathbf{Z}$, suppose $d\,|\,\alpha\beta$. Let
$d^{\prime}=d/\gcd(d,\beta)$. Then $d^{\prime}\,|\,\alpha$ and

$\forall\gamma\in\mathbf{Z}\;(d\,|\,\beta\gamma\iff d^{\prime}\,|\,\gamma).$

Proof. Let $e=\gcd(d,\beta)$, so that $d^{\prime}=d/e$.

$d\,|\,\alpha\beta\Rightarrow d^{\prime}=d/e\,|\,\alpha\beta/e$

and $\gcd(d^{\prime},\beta/e)=1$ so $d^{\prime}\,|\,\alpha$, and for any
$\gamma$

$d\,|\,\beta\gamma\iff d^{\prime}\,|\,\beta/e\gamma\iff
d^{\prime}\,|\,\gamma.$

(Pretty standard stuff, admittedly.) $\quad\qed$

So suppose $d\,|\,r^{2}t$ and $d\,|\,rt(a_{i}-a_{j})$ for $i\neq j$. Putting
$\alpha=r$, $\beta=rt$, $\gamma=a_{i}-a_{j}$ in the lemma we get

$d^{\prime}=d/\gcd(d,rt)\,|\,\alpha=r$

and

$d^{\prime}\,|\,\gamma=a_{i}-a_{j}.$

This tells us that $a$ is not univalent mod $d^{\prime}$, but since by
assumption it is good mod any divisor of $r$, it must be reversible mod
$d^{\prime}$:

$a\equiv_{S_{m}\times\mathbf{Z}_{d^{\prime}}}-a.$

By the lemma, this is equivalent to

$rta\equiv_{S_{m}\times\mathbf{Z}_{d}}-rta$

hence

$rta+1\equiv_{S_{m}\times\mathbf{Z}_{d}}-rta+1.$

From this we get

$H^{\star}_{d,{(ra+1)^{\pm}}}=H^{\star}_{d,{(-ra+1)^{\pm}}}.$

So from here on we may assume that ${(rta+1)^{\pm}}$ (and hence also
${(-rta+1)^{\pm}}$) is univalent mod $d$, with $d\,|\,r^{2}t$.

Returning for a moment to the case of $H^{\star}_{d,s}$ for general $d,s$,
suppose $s\in(\mathbf{Z}^{\star}_{d})^{m}$ with all the $s_{i}$’s distinct mod
$q$, so that the mod-$d$ quotient $s_{j}/_{d}\,s_{i}$ is defined for all
$i,j$, and different from $1$ for $i\neq j$. With this restriction, for
$k\in\mathbf{Z}^{\star}_{d}$ we have

$\prod_{i}\frac{y-\omega_{d}^{ks_{i}}}{x-\omega_{d}^{ks_{i}}}=\sum_{i}\frac{y-\omega_{d}^{ks_{i}}}{x-\omega_{d}^{ks_{i}}}\prod_{j\neq
i}\frac{y-\omega_{d}^{ks_{j}}}{\omega_{d}^{ks_{i}}-\omega_{d}^{ks_{j}}}.$

So

$\displaystyle H^{\star}_{d,s}$ $\displaystyle=$
$\displaystyle\sum_{k\in\mathbf{Z}^{\star}_{d}}\sum_{i}\frac{y-\omega_{d}^{ks_{i}}}{x-\omega_{d}^{ks_{i}}}\prod_{j\neq
i}\frac{y-\omega_{d}^{ks_{j}}}{\omega_{d}^{ks_{i}}-\omega_{d}^{ks_{j}}}$
$\displaystyle=$
$\displaystyle\sum_{l\in\mathbf{Z}^{\star}_{d}}\frac{y-\omega_{d}^{l}}{x-\omega_{d}^{l}}\sum_{i}\prod_{j\neq
i}\frac{y-\omega_{d}^{ls_{j}/s_{i}}}{\omega_{d}^{l}-\omega_{d}^{ls_{j}/_{d}\,s_{i}}}$
$\displaystyle=$
$\displaystyle\sum_{l\in\mathbf{Z}^{\star}_{d}}Y_{d,s}(x,y,\omega_{d}^{l}),$

where

$Y_{d,s}(x,y,w)=\frac{y-w}{x-w}\sum_{i}\prod_{j\neq
i}\frac{y-w^{s_{j}/_{d}\,s_{i}}}{w-w^{s_{j}/_{d}\,s_{i}}}.$

Now recall our notation

${s^{\pm}}=(s_{1},-s_{1},\ldots,s_{m},-s_{m}).$

Assuming the entries of ${s^{\pm}}$ are all invertible and distinct mod $d$,

$Y_{d,{s^{\pm}}}=\frac{(y-w)(y-w^{-1})}{(x-w)(x-w^{-1})}\sum_{i}\prod_{j\neq
i}\frac{(y-w^{s_{j}/_{d}\,s_{i}})(y-w^{-s_{j}/_{d}\,s_{i}})}{(w-w^{s_{j}/_{d}\,s_{i}})(w-w^{-s_{j}/_{d}\,s_{i}})}.$

Specializing finally to the case at hand, take

$s=rta+1=(rta_{1}+1,\ldots,rta_{m}+1)$

so that

${s^{\pm}}=(rta_{1}+1,-rta_{1}-1,\ldots,rta_{m}+1,-rta_{m}-1),$

and assume that these entries are all distinct mod $d$.

Here comes the magic: For any $d\,|\,r^{2}t$ we have

$s_{j}/_{d}\,s_{i}\equiv_{d}rt(a_{j}-a_{i})+1.$

As the entries of ${s^{\pm}}$ are distinct mod $d$, putting

$x_{i}=w^{rta_{i}}$

we have

$w^{s_{j}/_{d}\,s_{i}}=\frac{x_{j}}{x_{i}}w$

and

$w^{-s_{j}/_{d}\,s_{i}}=\frac{x_{i}}{x_{j}}w^{-1}$

so

$Y_{d,{(ra+1)^{\pm}}}=\frac{(y-w)(y-w^{-1})}{(x-w)(x-w^{-1})}\sum_{i}\prod_{j\neq
i}\frac{(y-\frac{x_{j}}{x_{i}}w)(y-\frac{x_{i}}{x_{j}}w^{-1})}{(w-\frac{x_{j}}{x_{i}}w)(w-\frac{x_{i}}{x_{j}}w^{-1})}.$

Setting $u=y/w$, $v=w^{-2}$, we get

$Y_{r^{2}t,{(rta+1)^{\pm}}}=\frac{(y-w)(y-w^{-1})}{(x-w)(x-w^{-1})}F((x_{1},\ldots,x_{m}),u,v)$

where

$F((x_{1},\ldots,x_{m}),u,v)=\sum_{i=1}^{m}\prod_{j\neq
i}\frac{(u-\frac{x_{j}}{x_{i}})(u-\frac{x_{i}}{x_{j}}v)}{(1-\frac{x_{j}}{x_{i}})(1-\frac{x_{i}}{x_{j}}v)}.$

Simultaneously we have

$Y_{r^{2}t,{(-rta+1)^{\pm}}}=\frac{(y-w)(y-w^{-1})}{(x-w)(x-w^{-1})}F((1/x_{1},\ldots,1/x_{m}),u,v).$

In the next section we will prove the identity

$F((x_{1},\ldots,x_{m}),u,v)=F((1/x_{1},\ldots,1/x_{m}),u,v),$

from which we conclude

$H^{\star}_{d,{(rta+1)^{\pm}}}=H^{\star}_{d,{(-rta+1)^{\pm}}}.$

We have now established this last equality for every $d\,|\,r^{2}t$, so

$H_{d,{(ra+1)^{\pm}}}=H_{d,{(-ra+1)^{\pm}}}.\quad\qed$

##  9 The main identity

Define the rational function

$\displaystyle F((x_{1},\ldots,x_{m}),u,v)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{m}\prod_{j\neq
i}\frac{(u-\frac{x_{j}}{x_{i}})(u-\frac{x_{i}}{x_{j}}v)}{(1-\frac{x_{j}}{x_{i}})(1-\frac{x_{i}}{x_{j}}v)}$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{m}\prod_{j\neq
i}\frac{(x_{i}u-x_{j})(x_{j}u-x_{i}v)}{(x_{i}-x_{j})(x_{j}-x_{i}v)}.$

Now look at what you get by replacing the variables $x_{1},\ldots,x_{m}$ by
their reciprocals:

$\displaystyle G((x_{1},\ldots,x_{m}),u,v)$ $\displaystyle=$ $\displaystyle
F((1/x_{1},\ldots,1/x_{m}),u,v)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{m}\prod_{j\neq
i}\frac{(u-\frac{x_{i}}{x_{j}})(u-\frac{x_{j}}{x_{i}}v)}{(1-\frac{x_{i}}{x_{j}})(1-\frac{x_{j}}{x_{i}}v)}$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{m}\prod_{j\neq
i}\frac{(x_{j}u-x_{i})(x_{i}u-x_{j}v)}{(x_{j}-x_{i})(x_{i}-x_{j}v)}$

######  Proposition 1.

$F=G$.

Proof. The right way to prove this identity is presumably via invariant
theory. (Or maybe it’s just somehow obvious?) But here we are going to prove
it by considering the two sides as rational functions of $v$, expanding their
individual terms in partial fractions, and seeing that the parts on the two
sides agree.

The tricky case turns out to be the polynomial term, corresponding to the pole
at $v=\infty$. We’ll deal with that later, after we address the finite poles.

Let’s look at the case $m=3$, which is sufficient to show what is going on.
Each side of the identity has three terms. On the left the first term is

$\frac{(x_{1}u-x_{2})(x_{2}u-x_{1}v)(x_{1}u-x_{3})(x_{3}u-x_{1}v)}{(x_{1}-x_{2})(x_{2}-x_{1}v)(x_{1}-x_{3})(x_{3}-x_{1}v)}.$

This term is the only one on the left with non-zero residue at
$v=x_{2}/x_{1}$, and its residue there is

$\displaystyle\frac{(x_{1}u-x_{2})(x_{2}u-x_{1}x_{2}/x_{1})(x_{1}u-x_{3})(x_{3}u-x_{1}x_{2}/x_{1})}{(x_{1}-x_{2})(-x_{1})(x_{1}-x_{3})(x_{3}-x_{1}x_{2}/x_{1})}$
$\displaystyle=$
$\displaystyle\frac{(x_{1}u-x_{2})x_{2}(u-1)(x_{1}u-x_{3})(x_{3}u-x_{2})}{(x_{1}-x_{2})(-x_{1})(x_{1}-x_{3})(x_{3}-x_{2})}.$

On the right the only term with a non-zero residue at $v=x_{2}/x_{1}$ is the
second term, namely

$\frac{(x_{1}u-x_{2})(x_{2}u-x_{1}v)(x_{3}u-x_{2})(x_{2}u-x_{3}v)}{(x_{1}-x_{2})(x_{2}-x_{1}v)(x_{3}-x_{2})(x_{2}-x_{3}v)},$

and the residue there is

$\displaystyle\frac{(x_{1}u-x_{2})(x_{2}u-x_{1}x_{2}/x_{1})(x_{3}u-x_{2})(x_{2}u-x_{3}x_{2}/x_{1})}{(x_{1}-x_{2})(-x_{1})(x_{3}-x_{2})(x_{2}-x_{3}x_{2}/x_{1})}$
$\displaystyle=$
$\displaystyle\frac{(x_{1}u-x_{2})x_{2}(u-1)(x_{3}u-x_{2})(x_{1}u-x_{3})}{(x_{1}-x_{2})(-x_{1})(x_{3}-x_{2})(x_{1}-x_{3})},$

which is the same as we found for the left side.

In this way we see that the residues of $v$ at the finite poles all match
between left and right. That leaves the pole at $v=\infty$. Taking the limit
$v\rightarrow\infty$ of

$F((x_{1},\ldots,x_{m}),u,v)=\sum_{i=1}^{m}\prod_{j\neq
i}\frac{(x_{i}u-x_{j})(x_{j}u-x_{i}v)}{(x_{i}-x_{j})(x_{j}-x_{i}v)}$

yields

$\sum_{i=1}^{m}\prod_{j\neq i}\frac{(x_{i}u-x_{j})}{(x_{i}-x_{j})}.$

In the next section, we will prove that this limit is $1+u+\ldots+u^{m-1}$,
which as it is independent of $(x_{1},x_{2},x_{3})$ must agree with the limit
of

$G((x_{1},\ldots,x_{m}),u,v)=F((1/x_{1},\ldots,1/x_{m}),u,v),$

so the residues at $v=\infty$ of the two sides of your identity match, and the
proof is complete. Well, it’s not a proof, exactly, since it doesn’t really
explain what is going on there. Call it a ‘verification’, which persuades us
that the identity is true, at least when coupled with a symbolic computation
checking the identity up through $m=4$. $\quad\qed$

##  10 The subsidiary identity

Define the rational function

$f((x_{1},\ldots,x_{m}),u)=\sum_{i=1}^{m}\prod_{j\neq
i}\frac{u-\frac{x_{j}}{x_{i}}}{1-\frac{x_{j}}{x_{i}}}=\sum_{i=1}^{m}\prod_{j\neq
i}\frac{x_{i}u-x_{j}}{x_{i}-x_{j}}.$

######  Proposition 2.

$f((x_{1},\ldots,x_{m}),u)=1+u+\ldots+u^{m-1}.$

Proof. We use induction on $m$. The cases $m=0,1$ are trivial, and $m=2$ is so
easy as not to illustrate the method. So we will look at the case $m=3$, and
take that as representative. We want to show that

$\frac{(x_{1}u-x_{2})(x_{1}u-x_{3})}{(x_{1}-x_{2})(x_{1}-x_{3})}+\frac{(x_{2}u-x_{1})(x_{2}u-x_{3})}{(x_{2}-x_{1})(x_{2}-x_{3})}+\frac{(x_{3}u-x_{1})(x_{3}u-x_{2})}{(x_{3}-x_{1})(x_{3}-x_{2})}=1+u+u^{2}.$

Expand the terms on the left in partial fractions with respect to the variable
$x_{3}$. The possible poles are at $x_{3}=x_{1}$, $x_{3}=x_{2}$, and
$x_{3}=\infty$. For the coefficient of $\frac{1}{x_{3}-x_{1}}$ we get

$-\frac{(x_{1}u-x_{2})(x_{1}u-x_{1})}{x_{1}-x_{2}}+0+\frac{(x_{1}u-x_{1})(x_{1}u-x_{2})}{x_{1}-x_{2}}.$

So this coefficient vanishes (as it would have to, if our identity is to
hold). Similarly for the coefficient of $\frac{1}{x_{3}-x_{2}}$. This leaves
the pole at $x_{3}=\infty$. Taking the limit of the terms on the left as
$x_{3}\rightarrow\infty$, we get

$\frac{x_{1}u-x_{2}}{x_{1}-x_{2}}+\frac{x_{2}u-x_{1}}{x_{2}-x_{1}}+u^{2}=f((x_{1},x_{2}),u)+u^{2}=1+u+u^{2},$

where in the last step we are using the induction hypothesis. $\quad\qed$

##  11 Open questions

  1. 1.

What is the right way to prove these two identities?

  2. 2.

LMR showed that in their construction, the full Hodge series agree just if
they agree after setting $w=0$. Surely we can prove this algebraically.

  3. 3.

Is the condition in Theorem 1 for Hodge-equivalence of LMR groups necessary as
well as sufficient? If true, this might not be so hard to prove. To start
with, we could prove that what works for $t=1$ works for any $t$.

  4. 4.

It seems that the representation-theoretic proof of LMR might give an explicit
matchup between spaces of invariant forms. Can we extract such a matchup from
the algebra in the proof of Theorem 1?

  5. 5.

Not all Hodge-isospectral pairs emerge directly from the LMR construction. For
example, you append a $0$ to the list $rta+1$ on both sides, or put in
everything congruent to $2$ mod $rt$. It’s tempting to figure out just what
variations are possible. And then we could ask whether all possible pairs
arise as variations of this kind.

  6. 6.

Doyle and Rossetti [3] conjectured that in spherical geometry or hyperbolic
geometry, spaces that are $p$-isospectral for all $p$ are almost conjugate,
and hence isospectral for all natural operators. The LMR examples show that
this is false in spherical geometry, but the hyperbolic case remains open, and
the intuition for this conjecture, born in the hyperbolic case and
incautiously extended to the spherical case, remains more or less intact.

## Acknowledgements

We thank Emilio Lauret for extensive correspondence.

## References

  * [1] Scott Crass.  Solving the sextic by iteration: A study in complex geometry and dynamics.  Experimental Mathematics, 8, 1999, arXiv:math/9903111 [math.DS].  http://arxiv.org/abs/math/9903111.
  * [2] Peter Doyle and Curt McMullen.  Solving the quintic by iteration.  Acta Mathematica, 163:151–180, 1989.  http://www.math.harvard.edu/~ctm/papers/home/text/papers/icos/icos.pdf.
  * [3] Peter G. Doyle and Juan Pablo Rossetti.  Laplace-isospectral hyperbolic 2-orbifolds are representation-equivalent (Version 1), 2011, arXiv:1103.4372v1 [math.DG].  http://arxiv.org/abs/1103.4372v1.
  * [4] Peter B. Gilkey.  On spherical space forms with metacyclic fundamental groups which are isospectral but not equivariant cobordant.  Compositio Math., 56:171–200, 1985.
  * [5] Vi Hart.  Pi is (still) wrong.  https://www.youtube.com/watch?v=jG7vhMMXagQ.
  * [6] Akira Ikeda.  Riemannian manifolds $p$-isospectral but not $(p+1)$-isospectral.  In Geometry of Manifolds, pages 383–417. Academic Press, 1989.
  * [7] Felix Klein.  Vorlesungen über das Ikosaeder und die Auflösung der Gleichungen vom fünften Grade.  B.G. Teubner, 1884.  http://www.math.dartmouth.edu/~doyle/docs/ikos/scan/ikos.pdf.
  * [8] Emilio A. Lauret, Roberto J. Miatello, and Juan Pablo Rossetti.  Lens spaces isospectral on $p$-forms for every $p$, 2013, arXiv:1311.7167v2 [math.DG].  http://arxiv.org/abs/1311.7167v2.
  * [9] Theodor Molien.  Über die Invarianten der linearen Substitutionsgruppen.  Sitzungber. König. Preuss. Akad. Wiss. (J. Berl. Ber.), 52:1152–1156, 1897.  http://books.google.com/books?id=EIxK-opAmJYC&pg=PA1152.
  * [10] Hubert Pesce.  Variétés hyperboliques et elliptiques fortement isospectrales.  J. Funct. Anal., 134(2):363–391, 1995.
  * [11] Richard P. Stanley.  Invariants of finite groups and their applications to combinatorics.  Bull. Amer. Math. Soc. (N.S.), 1(3):475–511, 1979.  http://math.mit.edu/~rstan/pubs/pubfiles/38.pdf.