# Can denoising diffusion probabilistic models generate realistic
astrophysical fields?

Nayantara Mudur
Department of Physics
Harvard University
Cambridge, MA, 02138
<EMAIL_ADDRESS>
Douglas P. Finkbeiner
Departments of Astronomy and of Physics
Harvard University
Cambridge, MA, 02138
<EMAIL_ADDRESS>

###### Abstract

Score-based generative models have emerged as alternatives to generative
adversarial networks (GANs) and normalizing flows for tasks involving learning
and sampling from complex image distributions. In this work we investigate the
ability of these models to generate fields in two astrophysical contexts: dark
matter mass density fields from cosmological simulations and images of
interstellar dust. We examine the fidelity of the sampled cosmological fields
relative to the true fields using three different metrics, and identify
potential issues to address. We demonstrate a proof-of-concept application of
the model trained on dust in denoising dust images. To our knowledge, this is
the first application of this class of models to the interstellar medium.

##  1 Introduction

Generative models of astrophysical and cosmological fields can serve a
multitude of purposes. Cosmological simulations take several thousand CPU
hours to run and can only be generated for a limited set of parameters. There
thus exists a demand for emulators: frameworks that can generate summary
statistics (Heitmann et al., 2009) or the underlying cosmological fields
(Feder et al., 2020; Jamieson et al., 2022) conditional on an input
cosmological / astrophysical parameter set. This can accelerate parameter
inference approaches that require evaluating likelihoods at intermediate
values. In the context of observed astrophysical fields, statistical
descriptions capable of capturing the non-Gaussian nature of the interstellar
medium would aid component separation problems encountered in searches for the
B-mode of the Cosmic Microwave Background (Remazeilles et al., 2018) and
statistical regularization for interstellar dust mapping (Green et al., 2019;
Leike and Enßlin, 2019).

Score-based generative models (Song et al., 2020) have witnessed a surge in
interest because of findings that show that they surpass GANs in terms of
image fidelity (Dhariwal and Nichol, 2021) and their ability to produce
realistic images conditional on text inputs (Saharia et al., 2022). These
models learn the gradient of the probability density of the data to learn a
generative model of the data distribution. A subset of this class includes
denoising diffusion probabilistic models (DDPMs) (Ho et al., 2020). Smith et
al. (2022) used DDPMs to generate galaxy images. Rémy et al. (2020); Remy et
al. (2022) used the denoising score matching framework to learn the non-
Gaussian component of a prior on weak lensing convergence maps from
simulations.

In this work we investigate two applications of DDPMs – one to simulation data
products and one to images of interstellar dust. We train models to generate
dark matter density fields from a simulation suite on grids of 64x64 and
128x128 pixels. We then compare five summary statistics between samples from
the trained models and the real simulation fields. While we currently generate
these fields unconditionally, this benchmarking is an important step toward
using these models as emulators, and generating fields conditional on an input
parameter vector. We then turn our attention to the real sky, and train a
model to generate square patches from an interstellar dust map. We use the
trained model as a denoising model and examine how well it can reconstruct the
underlying image given a noisy input.

##  2 DDPM Background

In this section, we briefly review the denoising diffusion probabilistic model
formulation in Ho et al. (2020). A DDPM consists of a forward and a reverse
diffusion process, over a fixed number of time steps, T, where
$\mathbf{x}_{0}$ is a draw from the image distribution and
$\mathbf{x}_{T}\sim\mathcal{N}(0,1)$. The forward diffusion process is defined
according to a variance schedule {$\beta_{t}$}. Thus
$q(\mathbf{x}_{t}|\mathbf{x}_{t-1})=\mathcal{N}(\sqrt{1-\beta_{t}}\mathbf{x}_{t-1},\beta_{t}\mathbf{I})$
and
$q(\mathbf{x}_{t}|\mathbf{x}_{0})=\mathcal{N}(\sqrt{\bar{\alpha_{t}}}\mathbf{x}_{0},(1-\bar{\alpha_{t}})\mathbf{I})$,
where $\bar{\alpha_{t}}=\prod_{t^{\prime}=1}^{t}1-\beta_{t^{\prime}}$. The
neural network $\mathbf{\epsilon}_{\theta}(\mathbf{x}_{t},t)$ parameterizes
the reverse diffusion process:
$p_{\theta}(\mathbf{x}_{t-1}|\mathbf{x}_{t})=\mathcal{N}(\mu_{\theta}(\mathbf{x}_{t},t),\sigma_{t}^{2}\mathbf{I})$
where
$\mu_{\theta}(\mathbf{x}_{t},t)=\frac{1}{\sqrt{1-\beta_{t}}}\big{(}\mathbf{x}_{t}-\frac{\beta_{t}}{\sqrt{1-\bar{\alpha_{t}}}}\mathbf{\epsilon}_{\theta}(\mathbf{x}_{t},t)\big{)}$
and $\sigma_{t}^{2}=\frac{1-\bar{\alpha}_{t-1}}{1-\bar{\alpha}_{t}}\beta_{t}$.
A simplified loss function is minimized where
$L_{t-1}=||\mathbf{\epsilon}-\mathbf{\epsilon}_{\theta}(\sqrt{\bar{\alpha}_{t}}\mathbf{x}_{0}+\sqrt{1-\bar{\alpha}_{t}}\mathbf{\epsilon},t))||^{2}$
with $\epsilon\sim\mathcal{N}(0,\mathbf{I})$. Thus for each batch a set of
timesteps t is uniformly sampled from $t\sim U[1...T]$ to minimize $L_{t-1}$.

##  3 Generative Models for Dark Matter Density Fields

#### Dataset

The CAMELS Multifield Dataset (CMD) (Villaescusa-Navarro et al., 2022) from
the Cosmology and Astrophysics with MachinE-Learning Simulations (CAMELS)
dataset (Villaescusa-Navarro et al., 2021) was used for this application. The
CMD includes an ensemble of thirteen two-dimensional physical fields for 1000
different simulation parameter vectors where each vector consists of 2
cosmological and 4 astrophysical feedback parameters. Every unique parameter
vector has 15 samples and the full data set thus consists of 15000 samples of
each physical field. We work with the log (base 10) of the cold dark matter
mass density field from the IllustrisTNG hydrodynamical simulation at $z=0$,
at two grid sizes (64x64 and 128x128) binned down from the original 256x256.
Each side of an image corresponds to $25h^{-1}$ Mpc. For the 64x64 model, we
use fields corresponding to the first 60% of the parameters as our training
data. We augment our fields with rotations and flips, to yield 54000 (9000x6)
train fields. For the 128x128 model, we use fields corresponding to the first
70% of the parameters as our training data. We augment our data with
rotations, flips and translational shifts (since the data has periodic
boundary conditions). We thus have 252000 (10500x24) train fields. We apply a
minmax transform that scales the minimum and the maximum pixel intensity of
the full training set to [-1, 1].

#### Training Details

We train two models, one at each resolution, for 60k iterations (batch
updates). In both cases, we use a forward diffusion process parameterized by a
linear variance schedule lying in the range [$10^{-4},2\times 10^{-2}$],
T=2000, a batch size of 40 images, and the Huber loss in place of the L2 loss
with the Adam optimizer (Kingma and Ba, 2014). We used a learning rate of
$5\times 10^{-4}$ for the model at 64x64 and $2\times 10^{-4}$ for the model
at 128x128 and saved checkpoints every 2000 iterations, to enable sampling
from multiple models. For the 64x64 case, we train models with 3 different
seeds. We use code blocks and architecture from Hugging Face’s The Annotated
Diffusion model (Rogge and Rasul, 2022),
https://github.com/lucidrains/denoising-diffusion-pytorch and Ho et al.
(2020). The architecture we use is similar to that in Ho et al. (2020), and
consists of a U-Net (Ronneberger et al., 2015) with 4 down and up-sampling
blocks consisting of 2 ResNet blocks (Zagoruyko and Komodakis, 2016), group-
normalization (Wu and He, 2018), and attention (Vaswani et al., 2017; Shen et
al., 2021). We use the Weights and Biases framework (Biewald, 2020) for our
experiments. The code for experiments in this paper is available at the
following repository: https://github.com/nmudur/diffusion-models-
astrophysical-fields-mlps.

Figure 1: Four log cold dark matter mass density fields from the training data
(top left) and from the sampled model (top right) at 128x128. Four samples of
dust from the training data (bottom left) and from the trained model (bottom
right).

Figure 2: Power spectra, normalized pixel histograms and Minkowski functionals
for 100 draws from the real fields and the trained models at 64x64 (left) and
128x128 (right). The envelopes in the power spectra and the Minkowski
functionals’ panels represent the standard deviation of the value of the
statistic in each bin. The height of the bars in the pixel histogram is the
mean height of the histogram bin and the error bar is the standard error over
all 100 samples.

#### Summary Statistics

Four samples from the trained model at 128x128 are plotted in the top right
panel of Figure 1. We consider three summary statistics – the power spectrum,
the normalized pixel intensity histograms and the three Minkowski functionals
in Figure 2 to gauge consistency between the sampled fields and the true image
distribution. Minkowski functionals (Schmalzing et al., 1995; Schmalzing and
Górski, 1998) are topological descriptors of fields sensitive to correlation
functions beyond the second order and can be used as metrics to gauge how
similar the statistics of the generated fields are to those of fields from the
true distribution (e.g., Tamosiunas et al., 2021; Régaldo-Saint Blancard et
al., 2022). They are computed as integrals over excursion sets with pixels
whose intensity is greater than a value $g$. In 2D,
$\mathcal{M}_{0},\mathcal{M}_{1},\mathcal{M}_{2}$ reflect the number of pixels
in the excursion set (area), the length of its boundary (perimeter) and the
number of holes. We use QuantImPy (Boelens and Tchelepi, 2021) to compute
these functionals.

The loss function used to train these models does not directly enforce the
summary statistics of the generated images to exactly match the summary
statistics of the training distribution. Thus, while the mean of the
statistics of the generated samples across checkpoints typically lie within
the one standard deviation envelope of the power spectra and Minkowski
functionals of the true distribution, convergence in terms of the loss does
not imply that the converged models are stationary with respect to the
distribution of the summary statistics of the generated images. We thus draw
100 samples from each of the last 10 checkpoints of the trained diffusion
models and from the real (train) dataset. Since the variability across
checkpoints is similar across all three seeds for the 64x64 models, we train a
single model for the 128x128 case and sample from its last 10 checkpoints. For
the samples across all 10 checkpoints, the mean absolute fractional difference
in the power spectrum is typically around 10% (std. dev. 5% for 64x64) and 15%
(std. dev. 10% for 128x128) and is higher at the lowest and highest $k-$bins,
which are most affected by cosmic variance and noise, respectively. For both
the 128x128 model and all 3 runs of the 64x64 model, at least one checkpoint
with a mean (over all bins) absolute fractional difference of less than 5%
could be found. As in Mustafa et al. (2019) and Tamosiunas et al. (2021) that
use adherence to summary statistics as a model selection criterion, we
identify the checkpoints with the lowest absolute fractional error in the
power spectrum and the best agreement with the Minkowski functionals. The
statistics plotted in Figure 2 correspond to these models. For the 64x64 case,
we plot the statistics for the worst of the three best-case models (one for
each seed). While the mean and the spread of the power spectra appear to be
largely consistent for these models, the Minkowski functionals are more
sensitive to differences between the true and the generated samples. We intend
to explore whether these differences and the lack of convergence to a
distribution stable with respect to the summary statistics can be mitigated
with different design choices, or whether more fundamental changes to the
method are required.

##  4 A Generative Model for Interstellar Medium Fields

#### Dataset and Training Details

The dataset consists of 12482 images from the Schlegel-Finkbeiner-Davis (SFD)
(Schlegel et al., 1998) map of interstellar dust extinction inferred from
emission at 100 microns. We restrict ourselves to images with extinction
$E_{SFD}<3$. Each image is 128x128 and spans an area of $(6.4^{\circ})^{2}$ on
the sky. The validation set consists of images lying in Galactic longitude
$0^{\circ}<l<42^{\circ}$ and the test set (held out for future validation)
consists of images lying between $200^{\circ}<l<240^{\circ}$. All other images
(roughly 69%) belong to the train distribution. The train images are augmented
with rotations and flips, yielding 68048 images (8506x8). We apply a minmax
transform that scales the minimum and the maximum pixel intensity of each
image to [-1, 1]. We peg the transform to each image because images of
interstellar dust span a larger dynamic range and pixel intensities in two
images are much more likely to be dissimilar than for the cosmic web. We train
our models for 42k iterations with a learning rate of $6\times 10^{-5}$. All
other training details are the same as in Section 3. Four sampled images are
plotted in the bottom right panel of Figure 1. For both the generated cosmic
web images and the dust images we see that the models are able to capture a
rich variety of structure.

#### Denoising Tests

We select a filamentary field from the validation dataset, whose standard
deviation corresponds to roughly the $50^{th}$ percentile of the standard
deviation across all images in the validation set. We add
$\mathcal{N}(0,\sigma^{2})$ noise such that $\sigma$ is 20% of the mean of the
intensity in the image. The noisy input is scaled to [-1, 1] and the timestep
at which $\sqrt{1-\bar{\alpha_{t}}}$ is closest to the corresponding scaled
sigma $\sigma_{tr}$ is identified for each image. We then iteratively sample
from $p_{\theta}(x_{t-1}|x_{t})$ from $t=t_{\sigma_{tr}}$ to $t=0$ to derive
the denoised image. As a baseline, we find the corresponding Gaussian filter
that would reduce the RMSE in the low-signal portion on the bottom right of
the image by the same factor (3.3). Figure 3 plots the denoised images with
the model and the baseline. The correlation of the residual with filaments is
significantly lower with the diffusion model than with the baseline.

Figure 3: Ground truth, noised input, denoised image and its residual
(denoised - truth), smoothed baseline and its residual (smoothed - truth).

##  5 Conclusions and Future Work

In this work, we investigated whether DDPMs are able to learn and sample from
the image distribution for two astrophysical fields — one from simulations and
the other from real interstellar dust maps — in a ‘physically meaningful’ way,
gauged by two different yardsticks. In the case of models trained to generate
images of interstellar dust, the models are able to denoise highly filamentary
images of interstellar dust while recovering underlying structure better than
a smoothing baseline. Approaches such as Régaldo-Saint Blancard et al. (2022)
involve learning generative models of interstellar dust using the wavelet
statistics of a single image, whereas our description learns a prior using
multiple images. The former approach can be useful in cases where limited
training data is available while the latter approach is more likely to account
for diversity and multiple modes of the image distribution. In the context of
dark matter density fields from simulations, we examined three sets of summary
statistics of cosmological significance. The ability to generate images with
the same statistics is an important first step toward deploying these models
as emulators. While DDPMs show promise in terms of our ability to find models
that generate samples that are consistent up to 10% in the power spectrum, we
intend to work on finding architectures or models with inductive biases that
prioritize convergence to distributions that are stationary with respect to
these summary statistics.

##  6 Broader Impact

Several papers have examined and improved the performance of score-based
generative models for standard machine learning datasets using standardized
metrics such as the Fréchet Inception Distance (Heusel et al., 2017),
demonstrated their ability to generate photo-realistic images conditional on
text inputs (Ramesh et al., 2022) and identified issues to work on, such as
their slower sampling speed, relative to GANs. This raises the question – how
can these models help accelerate science? As a first demonstration of the use
of these models to generate fields from the interstellar medium, we hope that
this paper can motivate both potential use cases for these models in
astrophysics and cosmology as well as work on imbuing these models with
physical inductive biases that make them more suitable for applications where
practitioners care about recovering specific summary statistics. While our
focus here has been on astrophysics, the questions we consider and the desire
for high-fidelity generative models capable of sampling distributions of
images faster than simulations have wider applications across the physical
sciences (Kasim et al., 2021) — from the geophysical sciences to high energy
physics (Paganini et al., 2018).

##  7 Acknowledgements

We thank Shuchin Aeron, Carolina Cuesta-Lazaro, Tanveer Karim, Andrew K.
Saydjari, and Justina R. Yang for helpful discussions. This work was supported
by the National Science Foundation under Cooperative Agreement PHY2019786 (The
NSF AI Institute for Artificial Intelligence and Fundamental Interactions).

## References

  * Heitmann et al. [2009] Katrin Heitmann, David Higdon, Martin White, Salman Habib, Brian J. Williams, and Christian Wagner.  The Coyote Universe II: Cosmological Models and Precision Emulation of the Nonlinear Matter Power Spectrum.  _Astrophys. J._ , 705:156–174, 2009.  doi: 10.1088/0004-637X/705/1/156.
  * Feder et al. [2020] Richard M. Feder, Philippe Berger, and George Stein.  Nonlinear 3d cosmic web simulation with heavy-tailed generative adversarial networks.  _Phys. Rev. D_ , 102:103504, Nov 2020.  doi: 10.1103/PhysRevD.102.103504.  URL https://link.aps.org/doi/10.1103/PhysRevD.102.103504.
  * Jamieson et al. [2022] Drew Jamieson, Yin Li, Renan Alves de Oliveira, Francisco Villaescusa-Navarro, Shirley Ho, and David N Spergel.  Field level neural network emulator for cosmological n-body simulations.  _arXiv preprint arXiv:2206.04594_ , 2022.
  * Remazeilles et al. [2018] Mathieu Remazeilles, Anthony J Banday, Carlo Baccigalupi, S Basak, A Bonaldi, G De Zotti, J Delabrouille, C Dickinson, HK Eriksen, J Errard, et al.  Exploring cosmic origins with core: B-mode component separation.  _Journal of Cosmology and Astroparticle Physics_ , 2018(04):023, 2018.
  * Green et al. [2019] Gregory M Green, Edward Schlafly, Catherine Zucker, Joshua S Speagle, and Douglas Finkbeiner.  A 3d dust map based on gaia, pan-starrs 1, and 2mass.  _The Astrophysical Journal_ , 887(1):93, 2019\.
  * Leike and Enßlin [2019] RH Leike and TA Enßlin.  Charting nearby dust clouds using gaia data only.  _Astronomy & Astrophysics_, 631:A32, 2019.
  * Song et al. [2020] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  _arXiv preprint arXiv:2011.13456_ , 2020.
  * Dhariwal and Nichol [2021] Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat gans on image synthesis.  _Advances in Neural Information Processing Systems_ , 34:8780–8794, 2021.
  * Saharia et al. [2022] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S Sara Mahdavi, Rapha Gontijo Lopes, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  _arXiv preprint arXiv:2205.11487_ , 2022.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Advances in Neural Information Processing Systems_ , 33:6840–6851, 2020.
  * Smith et al. [2022] Michael J Smith, James E Geach, Ryan A Jackson, Nikhil Arora, Connor Stone, and Stéphane Courteau.  Realistic galaxy image simulation via score-based generative models.  _Monthly Notices of the Royal Astronomical Society_ , 511(2):1808–1818, 2022.
  * Rémy et al. [2020] Benjamin Rémy, Francois Lanusse, Zaccharie Ramzi, Jia Liu, Niall Jeffrey, and Jean-Luc Starck.  Probabilistic mapping of dark matter by neural score matching.  _arXiv preprint arXiv:2011.08271_ , 2020.
  * Remy et al. [2022] Benjamin Remy, Francois Lanusse, Niall Jeffrey, Jean-Luc Starck, Ken Osato, and Tim Schrabback.  Probabilistic mass mapping with neural score estimation.  _arXiv preprint arXiv:2201.05561_ , 2022.
  * Villaescusa-Navarro et al. [2022] Francisco Villaescusa-Navarro, Shy Genel, Daniel Angles-Alcazar, Leander Thiele, Romeel Dave, Desika Narayanan, Andrina Nicola, Yin Li, Pablo Villanueva-Domingo, Benjamin Wandelt, et al.  The camels multifield data set: Learning the universe’s fundamental parameters with artificial intelligence.  _The Astrophysical Journal Supplement Series_ , 259(2):61, 2022.
  * Villaescusa-Navarro et al. [2021] Francisco Villaescusa-Navarro, Daniel Anglés-Alcázar, Shy Genel, David N Spergel, Rachel S Somerville, Romeel Dave, Annalisa Pillepich, Lars Hernquist, Dylan Nelson, Paul Torrey, et al.  The camels project: Cosmology and astrophysics with machine-learning simulations.  _The Astrophysical Journal_ , 915(1):71, 2021\.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Rogge and Rasul [2022] Niels Rogge and Kashif Rasul.  The annotated diffusion model, 2022.  URL https://huggingface.co/blog/annotated-diffusion.
  * Ronneberger et al. [2015] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In _International Conference on Medical image computing and computer-assisted intervention_ , pages 234–241. Springer, 2015.
  * Zagoruyko and Komodakis [2016] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  _arXiv preprint arXiv:1605.07146_ , 2016.
  * Wu and He [2018] Yuxin Wu and Kaiming He.  Group normalization.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 3–19, 2018.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Shen et al. [2021] Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li.  Efficient attention: Attention with linear complexities.  In _Proceedings of the IEEE/CVF winter conference on applications of computer vision_ , pages 3531–3539, 2021.
  * Biewald [2020] Lukas Biewald.  Experiment tracking with weights and biases, 2020.  URL https://www.wandb.com/.  Software available from wandb.com.
  * Schmalzing et al. [1995] Jens Schmalzing, Martin Kerscher, and Thomas Buchert.  Minkowski functionals in cosmology.  _arXiv preprint astro-ph/9508154_ , 1995.
  * Schmalzing and Górski [1998] Jens Schmalzing and Krzysztof M Górski.  Minkowski functionals used in the morphological analysis of cosmic microwave background anisotropy maps.  _Monthly Notices of the Royal Astronomical Society_ , 297(2):355–365, 1998.
  * Tamosiunas et al. [2021] Andrius Tamosiunas, Hans A Winther, Kazuya Koyama, David J Bacon, Robert C Nichol, and Ben Mawdsley.  Investigating cosmological gan emulators using latent space interpolation.  _Monthly Notices of the Royal Astronomical Society_ , 506(2):3049–3067, 2021.
  * Régaldo-Saint Blancard et al. [2022] Bruno Régaldo-Saint Blancard, Erwan Allys, Constant Auclair, François Boulanger, Michael Eickenberg, François Levrier, Léo Vacher, and Sixin Zhang.  Generative models of multi-channel data from a single example–application to dust emission.  _arXiv e-prints_ , pages arXiv–2208, 2022.
  * Boelens and Tchelepi [2021] Arnout MP Boelens and Hamdi A Tchelepi.  Quantimpy: Minkowski functionals and functions with python.  _SoftwareX_ , 16:100823, 2021.
  * Mustafa et al. [2019] Mustafa Mustafa, Deborah Bard, Wahid Bhimji, Zarija Lukić, Rami Al-Rfou, and Jan M Kratochvil.  Cosmogan: creating high-fidelity weak lensing convergence maps using generative adversarial networks.  _Computational Astrophysics and Cosmology_ , 6(1):1–13, 2019.
  * Schlegel et al. [1998] David J Schlegel, Douglas P Finkbeiner, and Marc Davis.  Maps of dust infrared emission for use in estimation of reddening and cosmic microwave background radiation foregrounds.  _The Astrophysical Journal_ , 500(2):525, 1998\.
  * Heusel et al. [2017] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  _Advances in neural information processing systems_ , 30, 2017.
  * Ramesh et al. [2022] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ , 2022.
  * Kasim et al. [2021] MF Kasim, D Watson-Parris, L Deaconu, S Oliver, P Hatfield, DH Froula, G Gregori, M Jarvis, S Khatiwala, J Korenaga, et al.  Building high accuracy emulators for scientific simulations with deep neural architecture search.  _Machine Learning: Science and Technology_ , 3(1):015013, 2021.
  * Paganini et al. [2018] Michela Paganini, Luke de Oliveira, and Benjamin Nachman.  Accelerating science with generative adversarial networks: an application to 3d particle showers in multilayer calorimeters.  _Physical review letters_ , 120(4):042003, 2018\.
  * Nichol and Dhariwal [2021] Alexander Quinn Nichol and Prafulla Dhariwal.  Improved denoising diffusion probabilistic models.  In _International Conference on Machine Learning_ , pages 8162–8171. PMLR, 2021.

##  Appendix A Appendix

###  A.1 Experiments and Compute Time

The 64x64 model took 1.25h to train for 60k iterations while the 128x128
models took 13.5 hours to train for the same number of iterations. We used an
NVIDIA A100 for most experiments and runs. We ran most experiments on the
64x64 model, since it took 1.25 hours to train for 60k iterations. The
cumulative compute time spent on experiments was around 5 days. Sampling 10
images from the trained diffusion models took $\sim 40$ seconds for the 64x64
model and $\sim 110$ seconds for the 128x128 model on the A100. We gauged
whether other hyperparameter choices were better by plotting the summary
statistics of samples from the generated model (as in Figure 2).

  * •

We tried the cosine learning schedule proposed in [Nichol and Dhariwal, 2021]
and found the linear schedule to work better, for the number of iterations we
experimented with.

  * •

We chose a lower learning rate for the dust images since we found this to be
more stable.

  * •

We also tried learning rates of [$6\times 10^{-5}$, $2\times 10^{-4}$,
$1\times 10^{-3}$] for the 64x64 model and did not find any of the other
learning rates to improve performance.

  * •

We examined the summary statistics for samples from the 64x64 runs described
in Section 3 for the last 15 checkpoints and did not find significant
differences in the quality of the summary statistics.


$b=\pm\sqrt{2}c$, and this is illustrated in Fig. 1(b).

It follows that $\text{BE}(4)=\sqrt{2}$.

###  8.4. Darga 5

The general form is $p(x)=b\sigma\\!_{5,1}+c\sigma\\!_{5,2}$.

It is well known that $\cos\frac{2\pi}{5}=\frac{\sqrt{5}-1}{4}$, and
$\cos\frac{4\pi}{5}=\frac{-\sqrt{5}-1}{4}$. So, from Eq. 15, defining
$\gamma=\frac{3+\sqrt{5}}{2}$, we find that the interlace fan comprises the
cones:

$\begin{array}[]{l@{\,}r@{\,}r@{\;}l}C_{0}\\!\\!:&-b-\gamma c\geq 0,&-\gamma
b-c\geq 0,&\text{on which}\
\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=-(b+c).\\\ C_{1}\\!\\!:&b+\gamma
c\geq 0,&-b+c\geq 0,&\text{on which}\
\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=\left((b+c)+\sqrt{5}(c-b)\right)/4.\\\
C_{2}\\!\\!:&\gamma b+c\geq 0,&b-c\geq 0,&\text{on which}\
\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=\left((b+c)+\sqrt{5}(b-c)\right)/4.\end{array}$

In order to compute $\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)$ and
$\text{b\\!e}\\!\mspace{-1.5mu}\left(p\right)$, we use Theorem 6.13. Up to a
constant factor,
$H\left(S_{1}\left(\frac{p_{\alpha}}{x+1}\right)\right)=(\alpha+b+c)x^{2}+(-10\alpha-2b+2c)x+5\alpha-3b+c$,
its discriminant (ditto) is $5\alpha^{2}-(4c-2b)\alpha+b^{2}$, and
$\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)$ is the largest of

$r_{1}=-b-c,\quad r_{2}=\frac{3b-c}{5},\quad
r_{3}=\frac{1}{5}\left(2c-b+2\sqrt{c^{2}-bc-b^{2}}\right),$

where $r_{3}$ can only contribute to the circle number if $c^{2}-bc-b^{2}\geq
0$.

We analyze each cone separately:

$C_{0}:$ Here all polynomials are exact, so there is nothing interesting to be
said.

$C_{2}:$ Here, $b>0$ is a valid inequality for all nonzero polynomials, so we
scale, making $b=1$. Hence, we have $p(x)=\sigma\\!_{5,1}+c\sigma\\!_{5,2}$,
$-\frac{3+\sqrt{5}}{2}\leq c\leq 1$, and
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=\frac{1}{4}\left((1-\sqrt{5})c+1+\sqrt{5}\right)$.
Also, $r_{3}$ exists either for $c\geq(1+\sqrt{5})/2$, which is out of
$C_{2}$, or for $c\leq(1-\sqrt{5})/2$, on which $r_{3}<0$. So, it turns out
that $\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)=\max\\{r_{1},r_{2}\\}$.
Each of them can be the largest, so we have:

$\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)=\begin{cases}{\scriptstyle-1-c}&\text{if}\quad\;\,c\leq-2\\\
\phantom{.}\frac{3-c}{5}&\text{if}\ -2\leq\phantom{-}c,\end{cases}$

and it happens to be continuous. Computing
$\text{b\\!e}\\!\mspace{-1.5mu}\left(p\right)$ in each case, we find that its
maximum in $C_{2}$ is attained at $c=-2$ and its value is
$\frac{3\sqrt{5}-5}{4}\cdot$

$C_{1}:$ Here, $c>0$ is a valid inequality for all nonzero polynomials, so we
scale, making $=1$. Hence, we have $p(x)=b\sigma\\!_{5,1}+\sigma\\!_{5,2}$,
$-\frac{3+\sqrt{5}}{2}\leq b\leq 1$, and
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=\frac{1}{4}((1-\sqrt{5})b+1+\sqrt{5})$.
There exists an $r_{3}$ in the interval
$\left[-\frac{3+\sqrt{5}}{2},-\frac{1+\sqrt{5}}{2}\right]$, and this splits
the interval $[-({3+\sqrt{5}})/{2},1]$ into three parts, as follows:

  * $-\frac{3+\sqrt{5}}{2}\leq b<-\frac{1+\sqrt{5}}{2}$: $r_{1}=-b-1$ is the largest root; so, as $b\rightarrow-\frac{1+\sqrt{5}}{2}$, $\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)\rightarrow\frac{\sqrt{5}-1}{2}$ and $\text{b\\!e}\rightarrow\sqrt{5}+1$; further, be is increasing and bounded above by the value shown.

  * $-\frac{1+\sqrt{5}}{2}\leq b\leq\frac{\sqrt{5}-1}{2}$: in this interval $r_{3}$ exists, and it is the largest root. Note that for $b=-\frac{1+\sqrt{5}}{2}$, $\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)=\frac{5+\sqrt{5}}{10}$ and $\text{b\\!e}\\!\mspace{-1.5mu}\left(p\right)=\frac{1+\sqrt{5}}{4}$; for $b=\frac{\sqrt{5}-1}{2}$, $\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)=\frac{5-\sqrt{5}}{10}$ and $\text{b\\!e}\\!\mspace{-1.5mu}\left(p\right)=\sqrt{5}-1$, which is maximum in the interval.

Also, in this interval, there exists a single exact polynomial (just find $b$
such that $\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=r_{3}$), specified by
$b=\frac{1-\sqrt{5}}{6}$ (see Example 7.1).

  * $\frac{\sqrt{5}-1}{2}<b\leq 1$: here $r_{2}=\frac{3b-1}{5}$ is largest; as $b\rightarrow\frac{\sqrt{5}-1}{2}$, $\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)\rightarrow\frac{3\sqrt{5}-5}{10}$ and $\text{b\\!e}\rightarrow\frac{3+\sqrt{5}}{2}$, which is an upper bound for be, but not attained.

(a) All numbers, darga 5

(b) Darga 5, $\text{c\\!n}/\text{i\\!l}$

Figure 2. Darga 5 polynomials

So, we note that cn and be have two rays of discontinuity, spanned by
$\frac{-1\pm\sqrt{5}}{2}\sigma\\!_{5,1}+\sigma\\!_{5,2}$. Figure 2(a) follows
the same conventions as Figure 1(a). Figure 2(b) shows
$\text{c\\!n}/\text{i\\!l}$, along with the fan rays, discontinuity rays and
the exceptional exact polynomial.

The whole analysis also implies that $\text{BE}(5)=\frac{3+\sqrt{5}}{2}\cdot$

###  8.5. Darga 6

The FOIC corresponding to darga 6 has been explicitly described in Example
5.3, and it happens to be a rational cone. Unfortunately, a general study of
the circle number seems to be too complicated to be worth it. We just recall
our recurring example $p(x)=50x^{5}+86x^{4}+99x^{3}+86x^{2}+50x$, which lies
in $C_{1}$ and has bounding error exactly $4$. It would be really nice if it
was maximum, but numerical experimentation led to $23p-x^{3}$, whose bounding
error yields: $\text{BE}(6)\geq 4.00645161290323$. We also used SageMath and
QepCAD [8] to find out about the exact polynomials in cones $C_{1}$ and
$C_{2}$, using the characterization in Theorem 7.4. The result was two
components on each cone, with rather complicated descriptions.

##  9\. Some interesting families

Here we present some families of polynomials for which something nontrivial
can be said about interlace or circle numbers. The first three sections have a
number-theoretic flavor, the other ones are more analytic.

###  9.1. Gcd polynomials

This family of polynomials was the starting point for the research being
presented here. [14] studied the following family of polynomials

$\text{gcd}_{n}^{(k)}(x)=\sum_{j=0}^{n}\gcd(n,j)^{k}x^{j}.$

At that time, the notions of interlace and circle numbers had not yet come up;
the main result there can be stated as

$\text{i\\!l}\\!\mspace{-2.0mu}\left(\text{tgcd}_{n}^{(k)}(x)\right)\leq
n^{k},$

where $\text{tgcd}_{n}^{(k)}(x)=\operatorname{trim}{\text{gcd}_{n}^{(k)}(x)}$,
but one can extract a more precise result from what is proved there.

Jordan’s totient function is

$J_{k}(n)=n^{k}\\!\\!\\!\\!\prod_{\begin{subarray}{c}p|n\\\ p\
\text{prime}\end{subarray}}\left(1-\frac{1}{p^{k}}\right),$

and, in particular, $J_{1}(n)=\varphi(n)$.

It is stated as Prop.1 of [14] that for every $m$

$n^{k}+\text{tgcd}_{n}^{(k)}\left(\IfSubStr{m;n}{;}{\text{e}^{\frac{2\pi
i\StrBefore{m;n}{;}}{\raisebox{2.0pt}{$\scriptscriptstyle\StrBehind{m;n}{;}$}}}}{\text{e}^{2i\pi
m;n}}\right)=\sum_{d|\gcd(m,n)}dJ_{k}\left(\frac{n}{d}\right).$

It is easy to see that the sum on the right is minimized if $\gcd(m,n)=1$,
where its value is simply $J_{k}(n)$. It follows that

(16)
$\text{i\\!l}\\!\mspace{-2.0mu}\left(\text{tgcd}_{n}^{(k)}(x)\right)=\frac{n^{k}-J_{k}(n)}{2}\mathbin{\raisebox{2.15277pt}{,}}$

and the interlace certs are precisely the elements of $V_{n}$ that generate
the group $U_{n}$. Notice that the interlace number is an integer if $n$ is
even. Moreover, this value is generally much smaller than the upper bounds
provided in Section 4. Also, if $n$ is prime,
$\text{tgcd}_{n}^{(k)}(x)=\operatorname{ge}_{n}(x)$, and indeed Eq. 16 yields
the value $\frac{1}{2}$ for the interlace number, as expected. The next result
ties in with the following section.

######  Proposition 9.1.

Let $a(x)=\sum_{k=0}^{m}a_{k}x^{k}$ be a polynomial with nonnegative real
coefficients. Then,

$\text{i\\!l}\\!\mspace{-2.0mu}\left(\sum_{j=0}^{n}a(\gcd(n,j))x^{j}\right)=\frac{1}{2}\left(a(n)-\sum_{k=0}^{m}a_{k}J_{k}(n)\right).$

###### Proof.

First, note that $J_{0}(n)=0$ if $n>1$, and Eq. 16 holds true if $k=0$.
Furthermore, $\IfSubStr{;n}{;}{\text{e}^{\frac{2\pi
i\StrBefore{;n}{;}}{\raisebox{2.0pt}{$\scriptscriptstyle\StrBehind{;n}{;}$}}}}{\text{e}^{2i\pi;n}}$
is an interlace cert for all $\text{tgcd}_{n}^{(k)}$, so all these polynomials
are in the cone $C_{1}$ of the interlace fan. So are all nonnegative linear
combinations of those polynomials, and, as the interlace number is linear on
$C_{1}$, the result follows from Eq. 16. ∎

We have no idea on how to express
$\text{c\\!n}\\!\mspace{-2.0mu}\left(\text{tgcd}_{n}(x)\right)$, but
experiments suggest that
$\text{b\\!e}\\!\mspace{-1.5mu}\left(\text{tgcd}_{n}(x)\right)$ is always
positive, and goes to 0 with $n$.

###  9.2. Interlace rational polynomials

We will use, exclusively in this section, the notation $(r,k)$ to stand for
$\gcd(r,k)$; $n$ will be fixed throughout. Recall that for every $1\leq r<n$,
${\theta_{n}\\!}^{r}$ is a primitive $\frac{n}{d}$th root of unity, where
$d=(r,n)$, and its conjugates over $\mathbb{Q}$ are
$\left\\{\left.{\theta_{n}\\!}^{kd}\,\right|\;(k,n/d)=1\right\\}$. We refer to
those sets as _conjugate classes_ of roots of unity; these classes can be
indexed by the divisors of $n$, the $d$-class being
$\left\\{\left.{\theta_{n}\\!}^{k}\,\right|\;(k,n)=d\right\\}$.

The _coprime-support polynomials_ are the stars of this section and are
defined as:

$R_{n}(x)=\sum_{\begin{subarray}{c}0<k<n\\\ (k,n)=1\end{subarray}}x^{k}.$

Clearly, $R_{n}(1)=\varphi(n)$. More generally, for every $j$,
$c_{n}(j)=R_{n}({\theta_{n}\\!}^{j})$ is called a _Ramanujan sum_ [36]. This
is known to be integer, and indeed

(17)
$c_{n}(j)=\mu\left(\frac{n}{(n,j)}\right)\frac{\varphi(n)}{\varphi\left(\frac{n}{(n,j)}\right)}\cdot$

The following lower bound for the interlace number turns out to be racional if
the polynomial has racional coefficients.

######  Proposition 9.2.

Let $p$ be a darga $n$ trim palindromic polynomial. Then,

(18)
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)\geq\max_{d|n}\frac{-1}{\varphi(d)}\sum_{j=1}^{\lfloor
n/2\rfloor}\tilde{p}_{j}c_{d}(j).$

###### Proof.

We know, by the Interlace Formula, that
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)\geq-\frac{1}{2}p(\omega)$ for
every $\omega\in U_{n}$. For each $d$, consider the class of primitive
$d$-roots of unity; averaging those inequalities over the class gives
$-\frac{1}{2\varphi(d)}\sum_{j=1}^{n-1}p_{j}c_{d}(j)$. Noticing that
$c_{d}(n-j)=c_{d}(j)$, the last step (to the $\sigma\\!$-representation)
follows. ∎

A trim palindromic polynomial with rational coefficients will be said to be
_interlace rational_ provided its interlace number is rational. If such a
polynomial has integer $\sigma\\!$-coefficients,
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)$ is an algebraic integer, hence,
an integer. Clearly, any rational polynomial in $C_{0}$ or $C_{n/2}$ is
interlace rational. More generally:

######  Proposition 9.3.

If $p$ is interlace rational of darga $n$, then the set of interlace certs of
$p$ is a union of conjugate classes. Furthermore,

(19)
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=\max_{d|n}\frac{-1}{\varphi(d)}\sum_{j=1}^{\lfloor
n/2\rfloor}\tilde{p}_{j}c_{d}(j).$

###### Proof.

Lemma 9.4 implies that if $\omega$ is an interlace cert, so are all its
conjugates. Proposition 9.2 tells us that the right hand side is a lower
bound. Now, choose $d|n$ such that
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=-\frac{1}{2}p({\theta_{n}\\!}^{n/d})$
and apply Eq. 20 to see that it is attained. ∎

######  Lemma 9.4.

Let $p$ be a polynomial of with rational coefficients. If for some $r$,
$p({\theta_{n}\\!}^{r})\in\mathbb{Q}$, then
$p({\theta_{n}\\!}^{kd})=p({\theta_{n}\\!}^{r})$ for all $k$ such that
$(k,n/d)=1$, where $d=(n,r)$. Moreover,

(20)
$p({\theta_{n}\\!}^{d})=\frac{1}{\varphi\left(n/d\right)}\sum_{j}p_{j}c_{n/d}(j).$

###### Proof.

Since ${\theta_{n}\\!}^{r}$ is a root of $p(x)-p({\theta_{n}\\!}^{r})$, so are
all its conjugates, hence $p(\omega)=p({\theta_{n}\\!}^{d})$ for all $\omega$
in the conjugate class of ${\theta_{n}\\!}^{d}$. Averaging this equation over
the conjugate class, we get Eq. 20. ∎

Coprime-support polynomials afford a simple formula for the interlace number:

######  Proposition 9.5.

Let $q$ be the smallest prime factor of $n$. Then
$\text{i\\!l}\\!\mspace{-2.0mu}\left(R_{n}\right)=\frac{\varphi(n)}{2(q-1)}=\frac{R_{n}(1)}{2(q-1)}$,
and its interlace certs are the primitive $q$-roots of unity.

###### Proof.

From the Interlace Formula,
$\text{i\\!l}\\!\mspace{-2.0mu}\left(R_{n}\right)\\!=\\!-\frac{1}{2}\min_{j}c_{n}(j)\\!=\\!-\frac{1}{2}\min_{j|n}c_{n}(j)$.
The last equality follows from Eq. 17, which implies $c_{n}(j)=c_{n}((n,j))$,
so the values of $c_{n}$ are attained at divisors of $n$. If $j$ is such that
$c_{n}(j)$ is minimum, one must have $\mu(n/j)=-1$, so $n/j$ is a product of
an odd number of distinct primes; also, $\varphi(n/j)$ must be minimum. Those
two conditions imply that $n/j=q$, and the result follows from the fact that
$\varphi(q)=q-1$, and that the interlace certs are the proper powers of
${\theta_{n}\\!}^{j}$. ∎

Here, again, $n$ prime get us back to the geometric polynomial, with the
expected result.

Let $p$ be a trim darga $n$ polynomial. Trivially,

$p(x)=\sum_{d|n}\sum_{\begin{subarray}{c}d\leq j<n\\\
(j,n)=d\end{subarray}}p_{j}x^{j}=\sum_{d|n}\sum_{\begin{subarray}{c}1\leq
j<n/d\\\ (j,n/d)=1\end{subarray}}p_{jd}x^{jd}.$

An arithmetic function $f:\mathbb{N}\rightarrow\mathbb{C}$ is said to be _$n$
-even_ ([36],[38]) if for all $j$, $f(j)=f((j,n))$. We attach the same name to
polynomials $p$ of degree $\leq n$ such that for all $j$, $p_{j}=p_{(j,n)}$.
Then, we can write

(21) $\displaystyle p(x)$
$\displaystyle=\sum_{d|n}\>p_{d}\\!\\!\\!\\!\sum_{\begin{subarray}{c}d\leq
j<n\\\ (j,n)=d\end{subarray}}x^{j}$ (22)
$\displaystyle=\sum_{d|n}\>p_{d}\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}1\leq
j<n/d\\\ (j,n/d)=1\end{subarray}}x^{jd}$ (23)
$\displaystyle=\sum_{d|n}p_{d}R_{n/d}(x^{d}).$

So, for every $k$,

(24) $p({\theta_{n}\\!}^{k})=\sum_{d|n}p_{d}c_{n/d}(k),$

which is the main result in [35].

It follows from Theorem 4.2 and Eq. 24 that rational $n$-even polynomials are
interlace rational. The converse is not true. On one hand, $n$-even
polynomials lie in a rational linear subspace of dimension equal to the number
of divisors of $n$; on the other hand, $C_{0}$ and $C_{n/2}$ are $\left\lfloor
n/2\right\rfloor$-dimensional cones whose rational points are all interlace
rational. However, those cones are quite special, and Proposition 9.3
restricts the faces of the FOIC that contain interlace rational polynomials.
We show next how to construct some of those polynomials in thinner faces.

######  Example 9.1:

Let $n$ be an odd number and $q$ be its smallest prime factor. Let $g$ be any
rational darga $n/q$ trim palindromic polynomial such that $q(1)=0$. Consider
now $p(x)=R_{n}(x)+\lambda g(x^{q})$, where $\lambda$ is a positive rational.
Proposition 9.5 tells us that any primitive $q$-root of unity $\omega$ is an
interlace cert for $R_{n}(x)$. The choice of $g$ implies that
$p(\omega)=R_{n}(\omega)$, and with $\lambda$ small enough we can guarantee
that $p(\omega)=\min_{r}p({\theta_{n}\\!}^{r})$, so it follows that
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=\text{i\\!l}\\!\mspace{-2.0mu}\left(R_{n}\right)$,
with the same interlace certs. For concreteness, choose an odd prime $q$ and
an integer $n$ such that $q$ is the smallest prime factor of $qn$ and let
$p(x)=R_{qn}(x)+\sigma\\!_{n,1}(x^{q})-\sigma\\!_{n,2}(x^{q})$. One can show
(exercise for the reader) that, provided $\varphi(n)-\varphi(q)\geq 4$, $p(x)$
is interlace rational; also, the same construction, but violating the
inequality, yields polynomials which are not interlace rational.

A further consequence of Eq. 24 is that if the coefficients of $p$ are
integers, so are the coefficients of $\hat{p}$, hence
$2\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)$ is an integer.

######  Example 9.2:

The geometric polynomial is is trivially $n$-even, and
$\operatorname{ge}_{n}(x)=\sum_{d|n}R_{n/d}(x^{d})$. It follows that

$R_{n}(x)=\sum_{d|n}\mu(d)\operatorname{ge}_{n/d}(x^{d}).$

######  Example 9.3:

The trimmed gcd polynomials are $n$-even, and can be simply written as

$\text{tgcd}_{n}^{(k)}(x)=\sum_{d|n}d^{k}R_{n/d}(x^{d}).$

######  Example 9.4:

Suppose $n=q^{m}$, with $q$ prime, and that $p$ is $n$-even; write
$a_{j}=p_{q^{j}}$. Then from Eq. 23

$p(x)=\sum_{j=1}^{m}a_{j}R_{q^{m-j}}(x^{q^{j}}).$

From Proposition 9.5,
$\text{i\\!l}\\!\mspace{-2.0mu}\left(R_{n}\right)=\frac{1}{2}q^{m-1}$, and its
interlace certs are the $q$-th roots of unity. Exponent scaling implies that
$\text{i\\!l}\\!\mspace{-2.0mu}\left(R_{q^{m-j}}(x^{q^{j}})\right)\\!=\frac{1}{2}q^{m-j-1}$,
and, further, the $q$-th roots of unity are also interlace certs of all those
polynomials. Hence the polynomials are all in the face of the interlace fan
corresponding to all those roots, so that, provided the $a_{j}$ are
nonnegative,

$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=\frac{1}{2}\sum_{j=1}^{m}a_{j}q^{m-j-1}.$

######  Example 9.5:

This is a more general form of the previous example. Start with a positive
integer $n$, and denote by $q$ its smallest prime divisor. Let reals
$a_{d}\geq 0$ be given for every $d$ such that $q|d$ and $d|n$. Then, if
$p(x)=\sum_{q|d|n}a_{d}R_{\frac{n}{d}}(x^{d})$, its interlace number is
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=\frac{1}{2(q-1)}p(1)$.

Given the special role of the coprime-support polynomials, one are tempted to
ask about their circle number. Half of the task is easy: if $n$ is even,
$R_{n}(x)$ is an odd polynomial, so $-1$ is an interlace cert and $p$ is
exact, with
$\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)=\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=\frac{\varphi(n)}{2}\cdot$
The other half we cannot do, and is left to the reader. Computations up to
$n=40$ suggest that $\text{b\\!e}\\!\mspace{-1.5mu}\left(R_{n}\right)$ is
positive, but vanishingly small.

###  9.3. Fekete polynomials

For prime $n$, $n$-even polynomials are just geometric polynomials and give us
nothing new. Fekete polynomials are interesting examples of prime degree
polynomials whose interlace number and certs have a nice description; they are
defined by

(25) $f_{n}(x):=\sum_{j=1}^{n-1}\left(\frac{j}{n}\right)x^{j},$

for each prime $n$, and we note that the darga of $f_{n}(x)$ is equal to $n$.
Here $\left(\frac{j}{n}\right)$ is the usual Legendre symbol, defined to be
equal to $+1$ when $j$ is a quadratic residue mod $n$, and $-1$ when $j$ is a
non-quadratic residue mod $n$. We recall that Gauss proved (in his 1811 paper)
the following closed form for the Gauss sum, which is by definition equal to
$f_{n}(\IfSubStr{k;n}{;}{\text{e}^{\frac{2\pi
i\StrBefore{k;n}{;}}{\raisebox{2.0pt}{$\scriptscriptstyle\StrBehind{k;n}{;}$}}}}{\text{e}^{2i\pi
k;n}})$

(26) $f_{n}(\IfSubStr{k;n}{;}{\text{e}^{\frac{2\pi
i\StrBefore{k;n}{;}}{\raisebox{2.0pt}{$\scriptscriptstyle\StrBehind{k;n}{;}$}}}}{\text{e}^{2i\pi
k;n}})=\epsilon_{n}\sqrt{n}\left(\frac{k}{n}\right),$

for all $k=0,1,2,\dots,n-1$, where

$\epsilon_{n}:=\begin{cases}1,\text{ if }n\equiv 1\text{ mod }4,\\\ i,\text{
if }n\equiv 3\text{ mod }4.\end{cases}$

The polynomials $f_{n}(x)$ are trim, palindromic polynomials provided $n\equiv
1\mod 4$. In that case, it follows from (26) that
$\left|f_{n}(x)\left(\IfSubStr{k;n}{;}{\text{e}^{\frac{2\pi
i\StrBefore{k;n}{;}}{\raisebox{2.0pt}{$\scriptscriptstyle\StrBehind{k;n}{;}$}}}}{\text{e}^{2i\pi
k;n}}\right)\right|=\sqrt{n}$, for all $k=0,1,\dots,n-1$, and we may therefore
read from the latter identity the interlace number of the Fekete polynomials,
by using the Interlace Formula:

(27)
$\text{i\\!l}\\!\mspace{-2.0mu}\left(f_{n}(x)\right)=\frac{\sqrt{n}}{2}\cdot$

It follows from Proposition 5.5 that, as every primitive $n$th root of unity
is a cert for $f_{n}(x)$, it lives in the same face of the FOIC as
$\text{tgcd}_{n}(x)$.

###  9.4. Half monotonic polynomials

Consider a trim palindromic polynomial $p$ of darga $n$. If the sequence
$p_{1},p_{2},\ldots,p_{\left\lfloor n/2\right\rfloor}$ is monotonic,
increasing or decreasing, we say that the polynomial is _half monotonic_ ,
increasing or decreasing, respectively, and strictly so if all those
coefficients are distinct.

######  Proposition 9.6.

If $p$ is strictly increasing, then

$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)\leq\frac{1}{2}p(1)-2\sum_{j=1}^{\lfloor
n/4\rfloor-1}p_{j}-c(n)p_{\left\lfloor\frac{n}{4}\right\rfloor},$

where $c(n)=1,2,2,3$ according to $n$ being $\equiv 0,1,2,3\mod 4$.

###### Proof.

We refer to Corollary 4.8, and notice that
$m(p)=p_{\left\lfloor\frac{n}{4}\right\rfloor}$,
$|M|=\left\lfloor\frac{n}{4}\right\rfloor-1$. Hence,

$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)\leq\frac{1}{2}p(1)-2\sum_{j=1}^{\lfloor
n/4\rfloor-1}p_{j}-\left(\left\lfloor\frac{n-1}{2}\right\rfloor-2\left\lfloor\frac{n}{4}\right\rfloor+2\right)p_{\left\lfloor\frac{n}{4}\right\rfloor}.$

The result now follows from a case analysis. ∎

A theorem of [10], extended by [18, Theorem 7 ], can be stated as:

######  Theorem 9.7.

If $p$ is decreasing and has nonnegative coefficients, then $cn(p)\leq p_{1}$.

A natural conjecture was that actually
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)\leq p_{1}$, at least when the
coefficients are nonnegative. Alas, this is false, in general. A brute force
search using SageMath produced several counterexamples. Here are two examples,
of odd and even dargas:

$15x^{8}+14x^{7}+12x^{6}+2x^{5}+2x^{4}+12x^{3}+14x^{2}+15x,$
$80x^{9}+75x^{8}+73x^{7}+11x^{6}+2x^{5}+11x^{4}+73x^{3}+75x^{2}+80x.$

For the first one, the interlace number is $15.018885\ldots$ and the circle
number is $\frac{23}{3}$; for the second one, the values are $90.6139\ldots$
and $68$.

In spite of these examples, there is something positive that can be said.
Proposition 5.10 implies that if $p_{1}$ is sufficiently larger than the
remaining coefficients,
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=-\frac{1}{2}p(-1)<\frac{1}{2}p_{1}$.

In Joyner’s article [18], the author asks about nonnegative increasing
polynomials; that is, for which values of $\alpha\in[0,p_{1}]$ $p_{\alpha}$ is
circle rooted.

We do not expect the concepts of circle and interlace number to be of help
here. Experiments show that $\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)$ is
much larger than $p_{1}$, and we can actually prove that for
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)$:

######  Proposition 9.8.

Suppose that $p\in\mathscr{T}^{(n)}$ is monotonic increasing, and let
$m=\lfloor\frac{n}{2}\rfloor$. Then

$\displaystyle\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)\geq$
$\displaystyle\;\tilde{p}_{m}+(\tilde{p}_{m-1}-\tilde{p}_{1})(1-5m^{-2})$
$\displaystyle\text{if $n$ is even},$
$\displaystyle\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)\geq$
$\displaystyle\;(\tilde{p}_{m}-\tilde{p}_{1})(1-5n^{-2})$
$\displaystyle\text{if $n$ is odd}.$

###### Proof.

Let us write $s_{j}=\sum_{k=1}^{m}-\tilde{p}_{k}\cos\frac{2\pi jk}{n}$, for
$j=0,1,\ldots,m$. The Interlace Formula says that
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)=\max_{j}s_{j}$, so, for any $j$,
$\text{i\\!l}\\!\mspace{-2.0mu}\left(p\right)\geq s_{j}$. We will compute
lower bounds for $s_{1}$.

Case 1: $n=2m$ is even. We can rewrite
$s_{1}=\sum_{k=1}^{m}-\tilde{p}_{k}\cos\frac{\pi k}{m}$. Noticing that
$\cos\frac{\pi k}{m}=-\cos\frac{\pi(m-k)}{m}$ is positive for
$k\leq\frac{m}{2}$, we can rewrite: $s_{1}=\tilde{p}_{m}+\sum_{1\leq
k\leq\frac{m}{2}}(\tilde{p}_{m-k}-\tilde{p}_{k})\cos\frac{\pi k}{m}$, and,
since $p$ is increasing, all terms in the sum are nonnegative. So,
$s_{1}\geq\tilde{p}_{m}+(\tilde{p}_{m-1}-\tilde{p}_{1})\cos\frac{\pi}{m}$.
From the Taylor series, $\cos x\geq 1-x^{2}/2$, so $\cos\frac{\pi}{m}\geq
1-\pi^{2}/{2m^{2}}\geq 1-5/m^{2}$, and this case is done.

Case 2: $n=2m+1$ is odd. Notice that for $1\leq k\leq\frac{m}{2}$ we have
$\cos 2\pi(m-k+1)/n\leq 0$ , and $-\cos 2\pi(m-k+1)/n\geq\cos 2\pi k/n$.
Rewrite $s_{1}=\sum_{1\leq k\leq\frac{m}{2}}\big{(}-\tilde{p}_{m-k+1}\cos
2\pi(m-k+1)/n-\tilde{p}_{k}\cos 2\pi k/n\big{)}$ (actually, if $m$ is odd,
there is an additional negative term). Using the inequalities on cosines at
the beginning of the paragraph, we can bound $s_{1}\geq\sum_{1\leq
k\leq\frac{m}{2}}(\tilde{p}_{m-k+1}-\tilde{p}_{k})(-\cos 2\pi(m-k+1)/n)$, and,
as all summands are nonnegative, we can bound
$s_{1}\geq(\tilde{p}_{m}-\tilde{p}_{1})\cos 2\pi/n$. We bound $\cos 2\pi/n$ as
in Case 1 to get the result. ∎

###  9.5. Binomial polynomials

An interesting case study of half-monotonic increasing polynomial is that of
$B_{n}(x)=(1+x)^{n}-(1+x^{n})$, trimmed binomial polynomials, which will also
be relevant in the next subsection. Here we can calculate the exact value

(28)
$\text{i\\!l}\\!\mspace{-2.0mu}\left(B_{n}\right)=2^{n-1}\cos^{n}\frac{\pi}{n}-1.$

Since $\cos\frac{\pi}{n}=1-O(1/n^{2})$, we have the asymptotics
$\text{i\\!l}\\!\mspace{-2.0mu}\left(B_{n}\right)=2^{n-1}(1-O(1/n))$.

###### Proof of (28).

We show that $\min_{\omega\in V_{n}}(1+\omega)^{n}=-(2\cos\frac{\pi}{n})^{n}$,
and then apply the Interlace Formula. Let $\omega\in V_{n}\backslash\\{1\\}$,
and let $\zeta\in V_{2n}$ be such that $\zeta^{2}=\omega$. Then,
$(1+\omega)^{n}=(1+\zeta^{2})^{n}=2^{n}\zeta^{n}\Re(\zeta)^{n}$. Since
$\zeta^{n}=\pm 1$, the last value is minimized at
$\zeta=\IfSubStr{;n}{;}{\text{e}^{\frac{2\pi
i\StrBefore{;n}{;}}{\raisebox{2.0pt}{$\scriptscriptstyle\StrBehind{;n}{;}$}}}}{\text{e}^{2i\pi;n}}$,
as $\zeta^{n}=-1$ and it has the largest real part, attaining the value
$-2^{n}\cos^{n}\frac{\pi}{n}\cdot$ ∎

Computation up to $n=40$ suggests that
$\text{c\\!n}\\!\mspace{-2.0mu}\left(B_{n}\right)$ is just above
$2^{n-1}\cos^{n+3}\frac{\pi}{n}$, so
$\text{b\\!e}\\!\mspace{-1.5mu}\left(B_{n}\right)<\frac{1}{\cos^{3}\frac{\pi}{n}}-1=O(\frac{1}{n^{2}})$.

The “Hadamard inverse” $B_{n}^{H}=\sum_{k=1}^{n-1}\binom{n}{k}^{-1}x^{k}$ is
decreasing, so we have some information provided at the previous section;
actually, a much more precise results follow from Proposition 5.10. Writing
$p_{k}=\binom{n}{k}^{-1}$, one can show that for $k\geq 3$,
$k^{2}\tilde{p}_{k}<3^{2}\tilde{p}_{3}$; one way to verify this is to note
that $(k-1)^{2}\tilde{p}_{k-1}<k^{2}\tilde{p}_{k}$ for $k\leq n/2$ (the case
$k=n/2$ requires special attention). Now,

(29) $\displaystyle\tilde{p}_{1}-\sum_{k=2}^{\left\lfloor
n/2\right\rfloor}k^{2}|\tilde{p}_{k}|$ $\displaystyle\geq
p_{1}-4p_{2}-(\left\lfloor n/2\right\rfloor-2)\cdot 3^{2}p_{3}$ (30)
$\displaystyle=\frac{1}{n}-\frac{8}{n(n-1)}-\frac{27(n-4)}{n(n-1)(n-2)}$ (31)
$\displaystyle\geq\frac{1}{n}\left(1-\frac{35}{n-1}\right)$

and this is positive if $n\geq 36$. So, by Proposition 5.10, for those $n$,
$-1$ is an interlace cert of $B_{n}^{H}$ if $n$ is even, so $B_{n}^{H}$ is
exact. For $n$ odd, ${\theta_{n}\\!}^{\left\lfloor n/2\right\rfloor}$ is an
interlace cert and it _looks like_ $-1$ is a circle cert. Computer
verification extends the same conclusions to $2\leq n\leq 35$. Curiously, the
expression on the left of Eq. 29 is negative for $6\leq n\leq 17$, so
Proposition 5.10 cannot be applied to handle these cases.

###  9.6. Cut polynomials

Let $A$ be an $n\times n$ Hermitian matrix, define its _cut polynomial_ (see
[2]) by

$\text{Cut}_{A}(x)=\sum_{S\subseteq\\{1,\ldots,n\\}}x^{|S|}\prod_{\begin{subarray}{c}i\in
S\\\ j\not\in S\end{subarray}}a_{ij},$

and let $\text{TCut}_{A}(x)=\operatorname{trim}\text{Cut}_{A}(x)$.

The celebrated Lee-Yang Theorem [28] states that

> _if $|a_{ij}|\leq 1$ for all $i,j$, then $\text{Cut}_{A}(x)$ is circle
> rooted_.

One easily sees that the cut polynomial is self-inversive, hence the question
comes to mind as whether the Lee-Yang Theorem has any relation to either
interlace number or circle number.

The answer is, nothing much, in general. Consider, for instance, the matrix
$J$ of all 1’s. It is easy to see that $\text{Cut}_{J}(x)=(1+x)^{n}$, so
$\text{TCut}_{J}(x)=B_{n}(x$). As we have seen, both
$\text{i\\!l}\\!\mspace{-2.0mu}\left(B_{n}\right)$ and
$\text{c\\!n}\\!\mspace{-2.0mu}\left(B_{n}\right)$ are very large, and say
nothing about the monic cut polynomial.

But all is not lost. Suppose we restrict a little the set of matrices,
requiring that all $|a_{ij}|\leq\lambda$, for some $0<\lambda(n)<1$. Then,
each product in the definition of $\text{Cut}_{A}(x)$ has absolute value at
most $\lambda^{k(n-k)}$, where $k=|S|$, and we can apply Theorem 4.6 to
conclude that

$\text{i\\!l}\\!\mspace{-2.0mu}\left(\text{TCut}_{A}\right)\leq\frac{1}{2}\sum_{k=1}^{n-1}\binom{n}{k}\lambda^{k(n-k)}\leq\sum_{k=1}^{\lfloor
n/2\rfloor}\binom{n}{k}\lambda^{k(n-k)}$

Denote $LY(x)=\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{k}x^{k(n-k)}$; if
$LY(\lambda)\leq 1$, then it follows that $\text{Cut}_{A}(x)$ angle interlaces
$U_{n}$, so in this case we have a stronger conclusion than in Lee-Yang. For
$n>2$, $LY(1)>0$, $LY(0)=-1$, and $LY(x)$ is increasing for positive $x$. So,
the best possible value for $\lambda$ is the only positive root of $LY(x)-1$,
which probably does not have a neat closed form.

Let us show that $\lambda=1/(cen)^{2/n}$ is a lower bound for the root, for
some $c>1$.

Indeed, for $1\leq k\leq n/2$,

$\binom{n}{k}\lambda^{k(n-k)}\leq\binom{n}{k}\lambda^{kn/2}\leq\left(\frac{ne}{k}\right)^{k}(cen)^{-k}=\frac{1}{c^{k}k^{k}}\cdot$

Hence, $LY(\lambda)\leq\sum_{k\geq
1}\frac{1}{(ck)^{k}}\leq\frac{1}{c}\sum_{k\geq
1}\frac{1}{k^{k}}\leq\frac{1}{c}\sum_{k\geq 1}\frac{1}{4^{k-1}}\leq 1$ for
$c\geq 4/3$ (although $5/4$ seems to be more accurate); that is,
$\lambda=\text{e}^{-2\frac{\log n}{n}-h}$, where $h$ is a constant, slightly
larger than 1.

Anyway, we have shown that
$\text{i\\!l}\\!\mspace{-2.0mu}\left(\text{TCut}_{A}\right)\leq 1$ if
$|a_{ij}|\leq\text{e}^{-2\frac{\log n}{n}-h}$. The actual root of $LY(x)-1$
seems to grow as $\text{e}^{-\alpha\frac{\log n}{n}}$, where $1<\alpha<2$.

##  10\. Open problems

Here we delve into some open questions that are scattered throughout the
paper, and we present future research directions in which we hope more people
can join us.

The general theory of the interlace number seems quite satisfactory at this
point. The circle number is a different ball game. There is some hope that a
concerted attack on the semi-algebraic side will yield new insights. The same
comments hold for exact polynomials.

######  Problem 1.

What is the geometry (maybe just the topology) of the set of exact
polynomials, for each darga $\geq 6$? Is it connected? In particular, what
happens within each $C_{j}$, where the exact polynomials fall into distinct
components; can these polynomials be parameterized?

######  Problem 2.

What about the growth of $\text{BE}(n)$? We have shown a linear lower bound,
and the construction used for it is intuitively (for us) best possible, but we
have no proof of that. In Section 8 we have shown that BE(4) and BE(5) are not
attained by any polynomial. Does this happen for all larger values of $n$?

Polynomials with rational coefficients give rise to several questions; in most
of them, there is no loss of generality in considering only integer
polynomials.

######  Problem 3.

What are the minimal faces of the FOIC that contain rational points? Most rays
clearly do not (except in darga 6). On the other hand, Section 9.2 gives
several examples of faces that do. Are there interlace rational polynomials in
those minimal faces?

######  Problem 4.

We repeat the same question as above, but for exact polynomials. Outside of
the polyhedral cones $C_{0}$ and $C_{n/2}$ in the FOIC, what do exact rational
polynomials look like? In Example 7.1, we present a family of exact rational
polynomials. Does every component of the set of exact polynomial contain a
rational point? Are there interlace rational exact polynomials?

######  Problem 5.

Proposition 5.10 can be unwound into an inequalities description of a rational
cones contained in the cone $C_{n/2}$. Can we get, for each $j$, interesting
rational cones contained in $C_{j}$?

######  Problem 6.

Is there an algorithm involving only rational arithmetic for finding out all
the interlace certs of a given rational polynomial, describing them as
appropriate powers of $\theta_{n}$ ?

######  Problem 7.

What are the ranges of il, cn and be, computed over integer polynomials?
Are all nonnegative real algebraic numbers attainable? For il, there is
already a restriction: it must belong to a cyclotomic field.

######  Problem 8.

The gcd polynomials empirically share the following properties: they are never
exact, but their bounding error is $O(1/n)$ for darga $n$. In particular, this
includes the geometric polynomials of prime darga, for which this is a known
fact (Example 7.4). Is it always true?

######  Problem 9.

A global view of rational polynomials could be provided by the development of
Erhart theory for the interlace simplex, and for the cones in the FOIC. That
is highly developed and well understood in case of rational polyhedral cones,
but little is known for cones that are not rational. The FOIC cones are, in a
sense, just shy of being rational, and may be still treatable.

Finally, here is a different type of question, which was already hinted at in
Example 6.3:

######  Problem 10.

Is there a family polynomials $p$ for which the set of values $\alpha$ for
which $p_{\alpha}$ is circle rooted fall into increasingly many disjoint
intervals?

## Glossary

circle-number

    for $p$ trim self-inversive,
$\text{c\\!n}\\!\mspace{-2.0mu}\left(p\right)=\inf\left\\{\left.\beta\,\right|\;p_{\alpha}\
\text{is circle rooted for all}\ \alpha\geq\beta\right\\}$

## References

  * [1] I. Area, E. Godoy, R.. Lamblém and A. Sri Ranga  “Basic hypergeometric polynomials with zeros on the unit circle”  In _Appl. Math. Comput._ 225, 2013, pp. 622–630  DOI: 10.1016/j.amc.2013.09.060
  * [2] Alexander Barvinok  “Combinatorics and complexity of partition functions” 30, Algorithms and Combinatorics  Springer, Cham, 2016, pp. vi+303  DOI: 10.1007/978-3-319-51829-9
  * [3] Saugata Basu, Richard Pollack and Marie-Françoise Roy  “Algorithms in real algebraic geometry” 10, Algorithms and Computation in Mathematics  Springer-Verlag, Berlin, 2006, pp. x+662
  * [4] V. Botta, L.. Marques and M. Meneguette  “Palindromic and perturbed polynomials: zeros location”  In _Acta Math. Hungar._ 143.1, 2014, pp. 81–87  DOI: 10.1007/s10474-013-0382-0
  * [5] Petter Brändén  “Unimodality, log-concavity, real-rootedness and beyond”  In _Handbook of enumerative combinatorics_ , Discrete Math. Appl. (Boca Raton)  CRC Press, Boca Raton, FL, 2015, pp. 437–483
  * [6] Petter Brändén, James Haglund, Mirkó Visontai and David G. Wagner  “Proof of the monotone column permanent conjecture”  In _Notions of positivity and the geometry of polynomials_ , Trends Math.  Birkhäuser/Springer Basel AG, Basel, 2011, pp. 63–78  DOI: 10.1007/978-3-0348-0142-3_5
  * [7] David Bremner et al.  “Computing symmetry groups of polyhedra”  In _LMS J. Comput. Math._ 17.1, 2014, pp. 565–581  DOI: 10.1112/S1461157014000400
  * [8] Christopher W. Brown  “QEPCAD B: a program for computing with semi-algebraic sets using CADs”  In _ACM SIGSAM Bulletin_ 37, 2002, pp. 97–108
  * [9] Winfried Bruns and Joseph Gubeladze  “Polytopes, rings, and $K$-theory”, Springer Monographs in Mathematics  Springer, Dordrecht, 2009, pp. xiv+461  DOI: 10.1007/b105283
  * [10] Weiyu Chen  “On the polynomials with all their zeros on the unit circle”  In _J. Math. Anal. Appl._ 190.3, 1995, pp. 714–724  DOI: 10.1006/jmaa.1995.1105
  * [11] Maria Chudnovsky and Paul Seymour  “The roots of the independence polynomial of a clawfree graph”  In _J. Combin. Theory Ser. B_ 97.3, 2007, pp. 350–357  DOI: 10.1016/j.jctb.2006.06.001
  * [12] Henri Cohen  “A course in computational algebraic number theory” 138, Graduate Texts in Mathematics  Springer-Verlag, Berlin, 1993, pp. xii+534  DOI: 10.1007/978-3-662-02945-9
  * [13] K. Conrad  “Roots on a Circle”  URL: http://www.math.uconn.edu/~kconrad/blurbs/galoistheory/numbersoncircle.pdf
  * [14] Karl Dilcher and Sinai Robins  “Zeros and irreducibility of polynomials with gcd powers as coefficients”  In _Ramanujan J._ 36.1-2, 2015, pp. 227–236  DOI: 10.1007/s11139-014-9579-2
  * [15] Günter Ewald  “Combinatorial convexity and algebraic geometry” 168, Graduate Texts in Mathematics  Springer-Verlag, New York, 1996, pp. xiv+372  DOI: 10.1007/978-1-4612-4044-0
  * [16] Steve Fisk  “Polynomials, roots, and interlacing”  In _arXiv Mathematics e-prints_ , 2006, pp. math/0612833  arXiv:math/0612833 [math.CA]
  * [17] Juan B. Gil and Sinai Robins  “Hecke operators on rational functions. I”  In _Forum Math._ 17.4, 2005, pp. 519–554  DOI: 10.1515/form.2005.17.4.519
  * [18] David Joyner  “Zeros of some self-reciprocal polynomials”  In _Excursions in harmonic analysis. Volume 1_ , Appl. Numer. Harmon. Anal.  Birkhäuser/Springer, New York, 2013, pp. 329–348  DOI: 10.1007/978-0-8176-8376-4_17
  * [19] David Joyner and Tony Shaska  “Self-inversive polynomials, curves, and codes”  In _Higher genus curves in mathematical physics and arithmetic geometry_ 703, Contemp. Math.  Amer. Math. Soc., Providence, RI, 2018, pp. 189–208  DOI: 10.1090/conm/703/14138
  * [20] David C. Kurtz  “A sufficient condition for all the roots of a polynomial to be real”  In _Amer. Math. Monthly_ 99.3, 1992, pp. 259–263  DOI: 10.2307/2325063
  * [21] D.. Kwon  “Reciprocal polynomials with all zeros on the unit circle”  In _Acta Math. Hungar._ 131.3, 2011, pp. 285–294  DOI: 10.1007/s10474-011-0090-6
  * [22] Piroska Lakatos and László Losonczi  “Circular interlacing with reciprocal polynomials”  In _Math. Inequal. Appl._ 10.4, 2007, pp. 761–769  DOI: 10.7153/mia-10-71
  * [23] Piroska Lakatos and László Losonczi  “On zeros of reciprocal polynomials of odd degree”  In _JIPAM. J. Inequal. Pure Appl. Math._ 4.3, 2003, pp. Article 608 pp. (electronic)
  * [24] Piroska Lakatos and László Losonczi  “Polynomials with all zeros on the unit circle”  In _Acta Math. Hungar._ 125.4, 2009, pp. 341–356  DOI: 10.1007/s10474-009-9028-7
  * [25] Piroska Lakatos and László Losonczi  “Self-inversive polynomials whose zeros are on the unit circle”  In _Publ. Math. Debrecen_ 65.3-4, 2004, pp. 409–420
  * [26] Matilde N. Lalín and Mathew D. Rogers  “Variations of the Ramanujan polynomials and remarks on $\zeta(2j+1)/n^{2j+1}$”  In _Funct. Approx. Comment. Math._ 48.part 1, 2013, pp. 91–111  DOI: 10.7169/facm/2013.48.1.8
  * [27] Matilde N. Lalín and C.. Smyth  “Unimodularity of zeros of self-inversive polynomials”  In _Acta Math. Hungar._ 138.1-2, 2013, pp. 85–101  DOI: 10.1007/s10474-012-0225-4
  * [28] T.. Lee and C.. Yang  “Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model”  In _Physical Rev. (2)_ 87, 1952, pp. 410–419
  * [29] Arnaldo Mandel  “Large finite products of small fractions”  In _arXiv e-prints_ , 2019, pp. arXiv:1908.00839  arXiv:1902.04231 [math.CA]
  * [30] Morris Marden  “Geometry of polynomials”, Second edition. Mathematical Surveys, No. 3  American Mathematical Society, Providence, R.I., 1966, pp. xiii+243
  * [31] Kathleen L. Petersen and Christopher D. Sinclair  “Conjugate reciprocal polynomials with all roots on the unit circle”  In _Canad. J. Math._ 60.5, 2008, pp. 1149–1167  DOI: 10.4153/CJM-2008-050-8
  * [32] Q.. Rahman and G. Schmeisser  “Analytic theory of polynomials” 26, London Mathematical Society Monographs. New Series  The Clarendon Press, Oxford University Press, Oxford, 2002, pp. xiv+742
  * [33] The Sage Developers  “SageMath, the Sage Mathematics Software System (Version 8.2)” http://www.sagemath.org, 2018
  * [34] Carla D. Savage and Mirkó Visontai  “The $\mathbf{s}$-Eulerian polynomials have only real roots”  In _Trans. Amer. Math. Soc._ 367.2, 2015, pp. 1441–1466  DOI: 10.1090/S0002-9947-2014-06256-9
  * [35] Wolfgang Schramm  “The Fourier transform of functions of the greatest common divisor”  In _Integers_ 8, 2008, pp. A507
  * [36] Wolfgang Schwarz and Jürgen Spilker  “Arithmetical functions” An introduction to elementary and analytic properties of arithmetic functions and to some of their almost-periodic properties 184, London Mathematical Society Lecture Note Series  Cambridge University Press, Cambridge, 1994, pp. xx+367  DOI: 10.1017/CBO9781107359963.014
  * [37] T. Sheil-Small  “Complex polynomials” 75, Cambridge Studies in Advanced Mathematics  Cambridge University Press, Cambridge, 2002, pp. xx+428  DOI: 10.1017/CBO9780511543074
  * [38] László Tóth and Pentti Haukkanen  “The discrete Fourier transform of $r$-even functions”  In _Acta Univ. Sapientiae Math._ 3.1, 2011, pp. 5–25
  * [39] Ricardo S. Vieira  “How to count the number of zeros that a polynomial has on the unit circle?”  In _arXiv e-prints_ , 2019, pp. arXiv:1902.04231  arXiv:1902.04231 [math.CV]
  * [40] Ricardo S. Vieira  “Polynomials with Symmetric Zeros”  In _Polynomials - Theory and Application_ IntechOpen, 2019  DOI: 10.5772/intechopen.82728
  * [41] Yi Wang and Yeong-Nan Yeh  “Polynomials with real zeros and Pólya frequency sequences”  In _J. Combin. Theory Ser. A_ 109.1, 2005, pp. 63–74  DOI: 10.1016/j.jcta.2004.07.008
  * [42] Doron Zeilberger  “A one-line high school algebra proof of the unimodality of the Gaussian polynomials $[^{n}_{k}]$ for $k<20$”  In _$q$ -series and partitions (Minneapolis, MN, 1988)_ 18, IMA Vol. Math. Appl.  Springer, New York, 1989, pp. 67–72  DOI: 10.1007/978-1-4684-0637-5_6
  * [43] Günter M. Ziegler  “Lectures on polytopes” 152, Graduate Texts in Mathematics  Springer-Verlag, New York, 1995, pp. x+370  DOI: 10.1007/978-1-4613-8431-1