# Diffusion On Syntax Trees For Program Synthesis

Shreyas Kapur
University of California, Berkeley
<EMAIL_ADDRESS>
&Erik Jenner
University of California, Berkeley
<EMAIL_ADDRESS>
&Stuart Russell
University of California, Berkeley
<EMAIL_ADDRESS>

###### Abstract

Large language models generate code one token at a time. Their autoregressive
generation process lacks the feedback of observing the program’s output.
Training LLMs to suggest edits directly can be challenging due to the scarcity
of rich edit data. To address these problems, we propose neural diffusion
models that operate on syntax trees of any context-free grammar. Similar to
image diffusion models, our method also inverts “noise” applied to syntax
trees. Rather than generating code sequentially, we iteratively edit it while
preserving syntactic validity, which makes it easy to combine this neural
model with search. We apply our approach to inverse graphics tasks, where our
model learns to convert images into programs that produce those images.
Combined with search, our model is able to write graphics programs, see the
execution result, and debug them to meet the required specifications. We
additionally show how our system can write graphics programs for hand-drawn
sketches. Video results can be found at https://tree-diffusion.github.io.

##  1 Introduction

Large language models (LLMs) have made remarkable progress in code generation,
but their autoregressive nature presents a fundamental challenge: they
generate code token by token, without access to the program’s runtime output
from the previously generated tokens. This makes it difficult to correct
errors, as the model lacks the feedback loop of seeing the program’s output
and adjusting accordingly. While LLMs can be trained to suggest edits to
existing code [6, 42, 17], acquiring sufficient training data for this task is
difficult.

In this paper, we introduce a new approach to program synthesis using _neural
diffusion_ models that operate directly on syntax trees. Diffusion models have
previously been used to great success in image generation [14, 22, 31]. By
leveraging diffusion, we let the model learn to iteratively refine programs
while ensuring syntactic validity. Crucially, our approach allows the model to
observe the program’s output at each step, effectively enabling a debugging
process.

In the spirit of systems like AlphaZero [29], the iterative nature of
diffusion naturally lends itself to search-based program synthesis. By
training a value model alongside our diffusion model, we can guide the
denoising process toward programs that are likely to achieve the desired
output. This allows us to efficiently explore the program space, making more
informed decisions at each step of the generation process.

We implement our approach for inverse graphics tasks, where we posit domain-
specific languages for drawing images. Inverse graphics tasks are naturally
suitable for our approach since small changes in the code produce semantically
meaningful changes in the rendered image. For example, a misplaced shape on
the image can be easily seen and fixed in program space.

Our main contributions for this work are (a) a novel approach to program
synthesis using diffusion on syntax trees and (b) an implementation of our
approach for inverse graphics tasks that significantly outperforms previous
methods.

Figure 1: Examples of programs recovered by our system. The top row shows a
hand-drawn sketch of an icon (left), the recovered program (middle), and the
compilation of the recovered program (right). The top two rows are for the
constructive solid geometry language (CSG2D-Sketch). The last row is an
example output from our TinySVG environment that learns to invert hierarchical
programs of shapes and colors. Video examples can be found at https://tree-
diffusion.github.io.

##  2 Background & Related Work

##### Neural program synthesis

Neural program synthesis is a prominent area of research, in which neural
networks generate programs from input-output examples. Early work, such as
Parisotto et al. [23], demonstrated the feasibility of this approach. While
modern language models can be directly applied to program synthesis, combining
neural networks with search strategies often yields better results and
guarantees. In this paradigm, the neural network guides the search process by
providing proposal distributions or scoring candidate programs. Examples of
such hybrid methods include Balog et al. [2], Ellis et al. [12], and Devlin et
al. [9]. A key difference from our work is that these methods construct
programs incrementally, exploring a vast space of partial programs. Our
approach, in contrast, focuses on _editing_ programs, allowing us to both grow
programs from scratch and make corrections based on the program execution.

##### Neural diffusion

Neural diffusion models, a class of generative models, have demonstrated
impressive results for modeling high-dimensional data, such as images [14, 22,
31]. A neural diffusion model takes samples from the data distribution (e.g.
real-world images), incrementally corrupts the data by adding noise, and
trains a neural network to incrementally remove the noise. To generate new
samples, we can start with random noise and iteratively apply the neural
network to denoise the input.

##### Diffusion for discrete data

Recent work extends diffusion to discrete and structured data like graphs
[35], with applications in areas such as molecule design [15, 27, 8]. Notably,
Lou et al. [20] proposed a discrete diffusion model using a novel score-
matching objective for language modeling. Another promising line of work for
generative modeling on structured data is generative flow networks (GFlowNets)
[3], where neural models construct structured data one atom at a time.

##### Diffusion for code generation

Singh et al. [30] use a diffusion model for code generation. However, their
approach is to first embed text into a continuous latent space, train a
_continuous_ diffusion model on that space, and then unembed at the end. This
means that intermediate stages of the latent representation are not trained to
correspond to actual code. The embedding tokens latch to the nearest
embeddings during the last few steps.

Direct code editing using neural models has also been explored. Chakraborty et
al. [6] use a graph neural network for code editing, trained on a dataset of
real-world code patches. Similarly, Zhang et al. [42] train a language model
to edit code by modifying or inserting [MASK] tokens or deleting existing
tokens. They further fine-tune their model on real-world comments and patches.
Unlike these methods, our approach avoids the need for extensive code edit
datasets and inherently guarantees syntactic validity through our pretraining
task.

##### Program synthesis for inverse graphics

We are inspired by previous work by Sharma et al. [28], Ellis et al. [10, 11],
which also uses the CSG2D language. Sharma et al. [28] propose a convolutional
encoder and a recurrent model to go from images to programs. Ellis et al. [11]
propose a method to provide a neural model with the intermediate program
execution output in a read–eval–print loop (REPL). Unlike our method, the
ability to execute partial graphics programs is a key requirement for their
work. Our system operates on complete programs and does not require a custom
partial compiler. As mentioned in their work, their policies are also brittle.
Once the policy proposes an object, it cannot undo that proposal. Hence, these
systems require a large number of particles in a Sequential Monte-Carlo (SMC)
sampler to make the system less brittle to mistakes.

##  3 Method

Figure 2: An overview of our method. Analogously to adding noise in image
diffusion, we randomly make small mutations to the syntax trees of programs.
We then train a conditional neural model to invert these small mutations. In
the above example, we operate in a domain-specific language (DSL) for creating
2D graphics using a constructive solid geometry language. The leftmost panel
($z_{0}$) shows the target image (bottom) alongside its program as a syntax
tree (top). The $y$ value of the circle gets mutated from $16$ to $10$ in the
second panel, making the black circle "jump" a little higher. Between $z_{1}$
and $z_{2}$, we see that we can mutate the Subtract ($-$) node to a Circle
node, effectively deleting it.

The main idea behind our method is to develop a form of denoising diffusion
models analogous to image diffusion models for syntax trees.

Consider the example task from Ellis et al. [11] of generating a constructive
solid geometry (CSG2D) program from an image. In CSG2D, we can combine simple
primitives like circles and quadrilaterals using boolean operations like
addition and subtraction to create more complex shapes, with the context-free
grammar (CFG),

$\displaystyle\texttt{S}\to\texttt{S}+\texttt{S}\ |\ \texttt{S}-\texttt{S}\ |\
\texttt{Circle}^{r}_{x,y}\ |\ \texttt{Quad}_{x,y,\theta}^{w,h}.$

In Figure 2, $z_{0}$ is our _target program_ , and $x_{0}$ is the rendered
version of $z_{0}$. Our task is to invert $x_{0}$ to recover $z_{0}$. Our
noising process randomly mutates y=16 to y=10. It then mutates the whole
$\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{-}{\bigcirc}}$ sub-tree with
two shapes with a new sub-tree with just one shape. Conditioned on the image
$x_{0}$, and starting at $z_{3},x_{3}$, we would like to train a neural
network to reverse this noising process to get to $z_{0}$.

In the following sections, we will first describe how “noise” is added to
syntax trees. Then, we will detail how we train a neural network to reverse
this noise. Finally, we will describe how we use this neural network for
search.

###  3.1 Sampling Small Mutations

Let $z_{t}$ be a program at time $t$. Let $p_{\mathcal{N}}(z_{t+1}|z_{t})$ be
the distribution over randomly mutating program $z_{t}$ to get $z_{t+1}$. We
want $p_{\mathcal{N}}$ mutations to be: (1) small and (2) produce
syntactically valid $z_{t+1}$’s.

To this end, we turn to the rich computer security literature on grammar-based
fuzzing [41, 13, 32, 36]. To ensure the mutations are small, we first define a
function $\sigma(z)$ that gives us the “size” of program $z$. For all our
experiments, we define a set of terminals in our CFG to be primitives. As an
example, the primitives in our CSG2D language are
$\\{\texttt{Quad},\texttt{Circle}\\}$. In that language, we use
$\sigma(z)=\sigma_{\text{primitive}}(z)$, which counts the number of
primitives. Other generic options for $\sigma(z)$ could be the depth, number
of nodes, etc.

We then follow Luke [21] and Zeller et al. [41] to randomly sample programs
from our CFG under exact constraints,
$\sigma_{\min}<\sigma(z)\leq\sigma_{\max}$. We call this function
$\texttt{ConstrainedSample}(\sigma_{\min},\sigma_{\max})$. Setting a small
value for $\sigma_{\max}$ allows us to sample small programs randomly. We set
$\sigma_{\max}=\sigma_{\text{small}}$ when generating small mutations.

To mutate a given program $z$, we first generate a set of candidate nodes in
its tree under some $\sigma_{\text{small}}$,

$\displaystyle\mathcal{C}$
$\displaystyle=\\{n\in\texttt{SyntaxTree}(z)\mid\sigma(n)\leq\sigma_{\text{small}}\\}.$

Then, we uniformly sample a mutation node from this set,

$\displaystyle m$ $\displaystyle\sim\text{Uniform}[\mathcal{C}].$

Since we have access to the full syntax tree and the CFG, we know which
production rule produced $m$, and can thus ensure syntactically valid
mutations. For example, if $m$ were a number, we know to replace it with a
number. If $m$ were a general subexpression, we know we can replace it with
any general subexpression. Therefore, we sample $m^{\prime}$, which is $m$’s
replacement as,

$\displaystyle
m^{\prime}\sim\texttt{ConstrainedSample}(\texttt{ProductionRule}(m),\sigma_{\text{small}}).$

###  3.2 Policy

####  3.2.1 Forward Process

We cast the program synthesis problem as an inference problem. Let $p(x|z)$ be
our observation model, where $x$ can be any kind of observation. For example,
we will later use images $x$ produced by our program, but $x$ could also be an
execution trace, a version of the program compiled to bytecode, or simply a
syntactic property. Our task is to invert this observation model, i.e. produce
a program $z$ given some observation $x$.

We first take some program $z_{0}$, either from a dataset,
$\mathcal{D}=\\{z^{0},z^{1},\ldots\\}$, or in our case, a randomly sampled
program from our CFG. We sample $z_{0}$’s such that
$\sigma(z_{0})\leq\sigma_{\max}$. We then add noise to $z_{0}$ for
$s\sim\text{Uniform}[1,s_{\max}]$, steps, where $s_{\max}$ is a hyper-
parameter, using,

$\displaystyle z_{t+1}\sim p_{\mathcal{N}}(z_{t+1}|z_{t}).$

We then train a conditional neural network that models the distribution,

$\displaystyle q_{\phi}(z_{t-1}|z_{t},x_{t};x_{0}),$

where $\phi$ are the parameters of the neural network, $z_{t}$ is the current
program, $x_{t}$ is the current output of the program, and $x_{0}$ is the
target output we are solving for.

####  3.2.2 Reverse Mutation Paths

Since we have access to the ground-truth mutations, we can generate targets to
train a neural network by simply reversing the sampled trajectory through the
forward process Markov-Chain, $z_{0}\to z_{1}\to\ldots$. At first glance, this
may seem a reasonable choice. However, training to simply invert the last
mutation can potentially create a much noisier signal for the neural network.

Consider the case where, within a much larger syntax tree, a color was mutated
as,

$\displaystyle{\color[rgb]{1,0,0}\texttt{Red}}\to{\color[rgb]{0,0,1}\texttt{Blue}}\to{\color[rgb]{0.23046875,0.58984375,0.48828125}\texttt{Green}}.$

The color in our target image, $x_{0}$, is  Red, while the color in our
mutated image, $x_{2}$, is  Green. If we naively teach the model to invert the
above Markov chain, we are training the network to turn the  Green to a  Blue,
even though we could have directly trained the network to go from  Green to a
Red.

Therefore, to create a better training signal, we compute an _edit path_
between the target tree and the mutated tree. We use a tree edit path
algorithm loosely based on the tree edit distance introduced by Pawlik and
Augsten [25, 24]. The general tree edit distance problem allows for the
insertion, deletion, and replacement of any node. Unlike them, our trees can
only be edited under an action space that only permits small mutations. For
two trees, $z_{A}$ and $z_{B}$, we linearly compare the syntax structure. For
changes that are already $\leq\sigma_{\text{small}}$, we add that to our
mutation list. For changes that are $>\sigma_{\text{small}}$, we find the
first mutation that reduces the distance between the two trees. Therefore, for
any two programs, $z_{A}$ and $z_{B}$, we can compute the first step of the
mutation path in $O(|z_{A}|+|z_{B}|)$ time.

###  3.3 Value Network & Search

We additionally train a value network, $v_{\phi}(x_{A},x_{B})$, which takes as
input two rendered images, $x_{A}$ and $x_{B}$, and predicts the edit distance
between the underlying programs that generated those images. Since we have
already computed edit paths between trees during training, we have direct
access to the ground-truth program edit distance for any pair of rendered
images, allowing us to train this value network in a supervised manner.

Using our policy, $q_{\phi}(z_{t-1}|z_{t},x_{t};x_{0})$, and our value,
$v_{\phi}(x_{t_{A}},x_{t_{B}})$, we can perform beam-search for a given target
image, $x_{0}$, and a randomly initialized program $z_{t}$. At each iteration,
we maintain a collection of nodes in our search tree with the most promising
values and only expand those nodes.

###  3.4 Architecture

Figure 3: We train $q_{\phi}(z_{t-1}|z_{t},x_{t};x_{0})$ as a decoder only
vision-language transformer following Tsimpoukelli et al. [33]. We use an NF-
ResNet as the image encoder, which is a normalizer-free convolutional
architecture proposed by Brock et al. [4]. The image encoder encodes the
current image, $x_{t}$, and the target images, $x_{0}$. The current program is
tokenized according to the vocabulary in our context-free grammar. The decoder
first predicts an edit location in the current program, and then tokens that
replace what the edit location should be replaced by. We constrain the
autoregressive decoding by our context-free grammar by masking only the valid
token logits.

Figure 3 shows an overview of our neural architecture. We use a vision-
language model described by Tsimpoukelli et al. [33] as our denoising model,
$q_{\phi}(z_{t-1}|z_{t},x_{t};x_{0})$. We use an off-the-shelf implementation
[38] of NF-ResNet-26 as our image encoder, which is a normalizer-free
convolutional architecture proposed by Brock et al. [4] to avoid test time
instabilities with Batch-Norm [40]. We implement a custom tokenizer, using the
terminals of our CFG as tokens. The rest of the edit model is a small decoder-
only transformer [34, 26].

We add two additional types of tokens: an <EDIT> token, which serves as a
start-of-sentence token for the model; and <POS x> tokens, which allow the
model to reference positions within its context. Given a current image, a
target image, and a current tokenized program, we train this transformer model
to predict the edit position and the replacement text autoregressively. While
making predictions, the decoding is constrained under the grammar. We mask out
the prediction logits to only include edit positions that represent nodes in
the syntax tree, and only produce replacements that are syntactically valid
for the selected edit position.

We set $\sigma_{\text{small}}=2$, which means the network is only allowed to
produce edits with fewer than two primitives. For training data, we sample an
infinite stream of random expressions from the CFG. We choose a random number
of noise steps, $s\in[1,5]$, to produce a mutated expression. For some
percentage of the examples, $\rho$, we instead sample a completely random new
expression as our mutated expression. We trained for $3$ days for the
environments we tested on a single Nvidia A6000 GPU.

##  4 Experiments

###  4.1 Environments

We conduct experiments on four domain-specific graphics languages, with
complete grammar specifications provided in Appendix B.

##### CSG2D

A 2D constructive solid geometry language where primitive shapes are added and
subtracted to create more complex forms, as explored in our baseline methods
[11, 28]. We also create CSG2D-Sketch, which has an added observation model
that simulates hand-drawn sketches using the algorithm from Wood et al. [39].

##### TinySVG

A language featuring primitive shapes with color, along with Arrange commands
for horizontal and vertical alignment, and Move commands for shape offsetting.
Figure 1 portrays an example program. Unlike the compositional nature of
CSG2D, TinySVG is hierarchical: sub-expressions can be combined into compound
objects for high-level manipulation. We also create, Rainbow, a simplified
version of TinySVG without Move commands for ablation studies due to its
reduced computational demands.

We implemented these languages using the Lark [19] and Iceberg [16] Python
libraries, with our tree-diffusion implementation designed to be generic and
adaptable to any context-free grammar and observation model.

###  4.2 Baselines

We use two prior works, Ellis et al. [11] and CSGNet [28] as baseline methods.

##### CSGNet

Sharma et al. [28] employed a convolutional and recurrent neural network to
generate program statements from an input image. For a fair comparison, we re-
implemented CSGNet using the same vision-language transformer architecture as
our method, representing the modern autoregressive approach to code
generation. We use rejection sampling, repeatedly generating programs until a
match is found.

##### REPL Flow

Ellis et al. [11] proposed a method to build programs one primitive at a time
until all primitives have been placed. They also give a policy network access
to a REPL, i.e., the ability to execute code and see outputs. Notably, this
current image is rendered from the current partial program. As such, we
require a custom partial compiler. This is straightforward for CSG2D since it
is a compositional language. We simply render the shapes placed so far. For
TinySVG, it is not immediately obvious how this partial compiler should be
written. This is because the rendering happens bottom-up. Primitives get
arranged, and those arrangements get arranged again (see Figure 1). Therefore,
we only use this baseline method with CSG2D. Due to its similarities with
Generative Flow Networks [3], we refer to our modified method as “REPL Flow”.

##### Test tasks

For TinySVG we used a held-out test set of randomly generated expressions and
their images. For the CSG2D task, we noticed that all methods were at ceiling
performance on an in-distribution held-out test set. In Ellis et al. [11], the
authors created a harder test set with more objects. However, simply adding
more objects in an environment like CSG2D resulted in simpler final scenes,
since sampling a large object that subtracts a large part of the scene becomes
more likely. Instead, to generate a hard test set, we filtered for images at
the $95th$ percentile or more on incompressibility with the LZ4 [7, 37]
compression algorithm.

##### Evaluation

In CSG2D, we accepted a predicted program as matching the specification if it
achieved an intersection-over-union (IoU) of $0.99$ or more. In TinySVG, we
accepted an image if $99\%$ of the pixels were within
$0.005\approx\frac{1}{256}$.

All methods were trained with supervised learning and were not fine-tuned with
reinforcement learning. All methods used the grammar-based constrained
decoding method described in Section 3.4, which ensured syntactically correct
outputs. While testing, we measured performance based on the number of
compilations needed for a method to complete the task.

Figure 4: Performance of our approach in comparison to baseline methods in
CSG2D and TinySVG languages. We give the methods $n=256$ images from the test
set and measure the number of nodes expanded to find a solution. The auto-
regressive baseline was queried with rejection sampling. Our policy
outperforms previous methods, and our policy combined with search helps boost
performance further. Error bars show standard deviation across 5 random seeds.

Figure 4 shows the performance of our method compared to the baseline methods.
In both the CSG2D and TinySVG environments, our tree diffusion policy rollouts
significantly outperform the policies of previous methods. Our policy combined
with beam search further improves performance, solving problems with fewer
calls to the renderer than all other methods. Figure 6 shows successful
qualitative examples of our system alongside outputs of baseline methods. We
note that our system can fix smaller issues that other methods miss. Figure 7
shows some examples of recovered programs from sketches in the CSG2D-Sketch
language, showing how the observation model does not necessarily need to be a
deterministic rendering; it can also consist of stochastic hand-drawn images.

###  4.3 Ablations

(a)  (b)

Figure 5: Effects of changing several design decisions of our system. We train
smaller models on the Rainbow environment. We give the model $n=256$ test
problems to solve. In (a), for No Reverse Path, we train the model without
computing an explicit reverse path, only using the last step of the noising
process as targets. For No Current Image, we train a model that does not get
to see the compiled output image of the program it is editing. For No Noising,
instead of using our noising process, we generate two random expressions and
use the path between them as targets. In (b) we examine the effect of training
mixture between forward diffusion ($\rho=0.0$) and pure random initialization
($\rho=1.0$) further. Error bars show standard deviation across $5$ random
seeds.

To understand the impact of our design decisions, we performed ablation
studies on the simplified Rainbow environment using a smaller transformer
model.

First, we examined the effect of removing the current image (no REPL) from the
policy network’s input. As shown in Figure 5(a), this drastically hindered
performance, confirming the importance of a REPL-like interface observed by
Ellis et al. [11].

Next, we investigated the necessity of our reverse mutation path algorithm.
While training on the last mutation step alone provides a valid path, it
introduces noise by potentially targeting suboptimal intermediate states.
Figure 5(a) demonstrates that utilizing the reverse mutation path
significantly improves performance, particularly in finding solutions with
fewer steps. However, both methods eventually reach similar performance
levels, suggesting that a noisy path, while less efficient, can still lead to
a solution.

Finally, we explored whether the incremental noise process is crucial, given
our tree edit path algorithm. Couldn’t we directly sample two random
expressions, calculate the path, and train the network to imitate it? We
varied the training data composition between pure forward diffusion
($\rho=0.0$) and pure random initialization ($\rho=1.0$) as shown in Figure
5(b). We found that a small proportion ($\rho=0.2$) of pure random
initializations combined with forward diffusion yielded the best results. This
suggests that forward diffusion provides a richer training distribution around
target points, while random initialization teaches the model to navigate the
program space more broadly. The emphasis on fine-grained edits from forward
diffusion proves beneficial for achieving exact pixel matches in our
evaluations.

Figure 6: Qualitative examples of our method and baselines on two inverse
graphics languages, CSG2D (top two rows) and TinySVG (bottom two rows). The
leftmost column shows the ground-truth rendered programs from our test set.
The next columns show rendered programs from various methods. Our methods are
able to finely adjust and match the ground-truth programs more closely. Figure
7: Examples of programs recovered for input sketches in the CSG2D-Sketch
language. The input sketches are from our observation model that simulates
hand-drawn sketches (top-row). The output programs rendered (bottom row) are
able to match the input sketches by adding and subtracting basic shapes. Video
results for these sketches can be found at https://tree-diffusion.github.io.

##  5 Conclusion

In this work, we proposed a neural diffusion model that operates on syntax
trees for program synthesis. We implemented our approach for inverse graphics
tasks, where our task is to find programs that would render a given image.
Unlike previous work, our model can construct programs, view their output, and
in turn edit these programs, allowing it to fix its mistakes in a feedback
loop. We quantitatively showed how our approach outperforms our baselines at
these inverse graphics tasks. We further studied the effects of key design
decisions via ablation experiments.

##### Limitations

There are several significant limitations to this work. First, we operate on
expressions with no variable binding, loops, strings, continuous parameters,
etc. While we think our approach can be extended to support these, it needs
more work and careful design. Current large-language models can write
complicated programs in many domains, while we focus on a very narrow task.
Additionally, the task of inverse graphics might just be particularly suited
for inverse graphics where small mutations make informative changes in the
image output.

##### Future Work

In the future, we hope to be able to leverage large-scale internet data on
programs to train our system, making small mutations to their syntax tree and
learning to invert them. We would also like to study this approach in domains
other than inverse graphics. Additionally, we would like to extend this
approach to work with both the discrete syntax structure and continuous
floating-point constants.

##### Impact

Given the narrow scope of the implementation, we don’t think there is a direct
societal impact, other than to inform future research direction in machine-
assisted programming. We hope future directions of this work, specifically in
inverse graphics, help artists, engineering CAD modelers, and programmers with
a tool to convert ideas to precise programs for downstream use quickly.

## Acknowledgments and Disclosure of Funding

We would like to thank Kathy Jang, David Wu, Cam Allen, Sam Toyer, Eli
Bronstein, Koushik Sen, and Pieter Abbeel for discussions, feedback, and
technical support. Shreyas was supported in part by the AI2050 program at
Schmidt Futures (Grant G-22-63471). Erik was supported by fellowships from the
Future of Life Institute and Open Philanthropy.

## References

  * Ansel et al. [2024] Jason Ansel, Edward Yang, Horace He, Natalia Gimelshein, Animesh Jain, Michael Voznesensky, Bin Bao, Peter Bell, David Berard, Evgeni Burovski, Geeta Chauhan, Anjali Chourdia, Will Constable, Alban Desmaison, Zachary DeVito, Elias Ellison, Will Feng, Jiong Gong, Michael Gschwind, Brian Hirsh, Sherlock Huang, Kshiteej Kalambarkar, Laurent Kirsch, Michael Lazos, Mario Lezcano, Yanbo Liang, Jason Liang, Yinghai Lu, CK Luk, Bert Maher, Yunjie Pan, Christian Puhrsch, Matthias Reso, Mark Saroufim, Marcos Yukio Siraichi, Helen Suk, Michael Suo, Phil Tillet, Eikan Wang, Xiaodong Wang, William Wen, Shunting Zhang, Xu Zhao, Keren Zhou, Richard Zou, Ajit Mathews, Gregory Chanan, Peng Wu, and Soumith Chintala.  PyTorch 2: Faster Machine Learning Through Dynamic Python Bytecode Transformation and Graph Compilation.  In _29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (ASPLOS ’24)_. ACM, April 2024.  doi: 10.1145/3620665.3640366.  URL https://pytorch.org/assets/pytorch2-2.pdf.
  * Balog et al. [2016] Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow.  Deepcoder: Learning to write programs.  _arXiv preprint arXiv:1611.01989_ , 2016.
  * Bengio et al. [2023] Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J Hu, Mo Tiwari, and Emmanuel Bengio.  Gflownet foundations.  _Journal of Machine Learning Research_ , 24(210):1–55, 2023.
  * Brock et al. [2021] Andy Brock, Soham De, Samuel L Smith, and Karen Simonyan.  High-performance large-scale image recognition without normalization.  In _International Conference on Machine Learning_ , pages 1059–1071. PMLR, 2021.
  * Catmull and Rom [1974] Edwin Catmull and Raphael Rom.  A class of local interpolating splines.  In _Computer aided geometric design_ , pages 317–326. Elsevier, 1974.
  * Chakraborty et al. [2020] Saikat Chakraborty, Yangruibo Ding, Miltiadis Allamanis, and Baishakhi Ray.  Codit: Code editing with tree-based neural models.  _IEEE Transactions on Software Engineering_ , 48(4):1385–1399, 2020.
  * Collet et al. [2013] Yann Collet et al.  Lz4: Extremely fast compression algorithm.  _code. google. com_ , 2013.
  * Corso et al. [2022] Gabriele Corso, Hannes Stärk, Bowen Jing, Regina Barzilay, and Tommi Jaakkola.  Diffdock: Diffusion steps, twists, and turns for molecular docking.  _arXiv preprint arXiv:2210.01776_ , 2022.
  * Devlin et al. [2017] Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel rahman Mohamed, and Pushmeet Kohli.  RobustFill: Neural program learning under noisy I/O.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 990–998. PMLR, 06–11 Aug 2017.
  * Ellis et al. [2018] Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Josh Tenenbaum.  Learning to infer graphics programs from hand-drawn images.  _Advances in neural information processing systems_ , 31, 2018.
  * Ellis et al. [2019] Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama.  Write, execute, assess: Program synthesis with a repl.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Ellis et al. [2021] Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua B Tenenbaum.  Dreamcoder: Bootstrapping inductive program synthesis with wake-sleep library learning.  In _Proceedings of the 42nd acm sigplan international conference on programming language design and implementation_ , pages 835–850, 2021.
  * Godefroid et al. [2008] Patrice Godefroid, Adam Kiezun, and Michael Y Levin.  Grammar-based whitebox fuzzing.  In _Proceedings of the 29th ACM SIGPLAN conference on programming language design and implementation_ , pages 206–215, 2008.
  * 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.
  * Hoogeboom et al. [2022] Emiel Hoogeboom, Vıctor Garcia Satorras, Clément Vignac, and Max Welling.  Equivariant diffusion for molecule generation in 3d.  In _International conference on machine learning_ , pages 8867–8887. PMLR, 2022.
  * IceBerg Contributors [2023] IceBerg Contributors.  IceBerg – Compositional Graphics and Diagramming.  _github_ , July 2023.  URL https://github.com/revalo/iceberg.
  * Jin et al. [2023] Matthew Jin, Syed Shahriar, Michele Tufano, Xin Shi, Shuai Lu, Neel Sundaresan, and Alexey Svyatkovskiy.  Inferfix: End-to-end program repair with llms.  In _Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , pages 1646–1656, 2023.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Lark Contributors [2014] Lark Contributors.  Lark - a parsing toolkit for Python.  _github_ , August 2014.  URL https://github.com/lark-parser/lark.
  * Lou et al. [2023] Aaron Lou, Chenlin Meng, and Stefano Ermon.  Discrete diffusion language modeling by estimating the ratios of the data distribution.  _arXiv preprint arXiv:2310.16834_ , 2023.
  * Luke [2000] Sean Luke.  Two fast tree-creation algorithms for genetic programming.  _IEEE Transactions on Evolutionary Computation_ , 4(3):274–283, 2000.
  * Nichol et al. [2021] Alex Nichol, Prafulla Dhariwal, Aditya Ramesh, Pranav Shyam, Pamela Mishkin, Bob McGrew, Ilya Sutskever, and Mark Chen.  Glide: Towards photorealistic image generation and editing with text-guided diffusion models.  _arXiv preprint arXiv:2112.10741_ , 2021.
  * Parisotto et al. [2016] Emilio Parisotto, Abdel rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli.  Neuro-symbolic program synthesis, 2016.
  * Pawlik and Augsten [2015] Mateusz Pawlik and Nikolaus Augsten.  Efficient computation of the tree edit distance.  _ACM Transactions on Database Systems (TODS)_ , 40(1):1–40, 2015.
  * Pawlik and Augsten [2016] Mateusz Pawlik and Nikolaus Augsten.  Tree edit distance: Robust and memory-efficient.  _Information Systems_ , 56:157–173, 2016.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Schneuing et al. [2022] Arne Schneuing, Yuanqi Du, Charles Harris, Arian Jamasb, Ilia Igashov, Weitao Du, Tom Blundell, Pietro Lió, Carla Gomes, Max Welling, et al.  Structure-based drug design with equivariant diffusion models.  _arXiv preprint arXiv:2210.13695_ , 2022.
  * Sharma et al. [2018] Gopal Sharma, Rishabh Goyal, Difan Liu, Evangelos Kalogerakis, and Subhransu Maji.  Csgnet: Neural shape parser for constructive solid geometry.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5515–5523, 2018.
  * Silver et al. [2018] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  _Science_ , 362(6419):1140–1144, 2018.
  * Singh et al. [2023] Mukul Singh, José Cambronero, Sumit Gulwani, Vu Le, Carina Negreanu, and Gust Verbruggen.  Codefusion: A pre-trained diffusion model for code generation, 2023.
  * 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.
  * Srivastava and Payer [2021] Prashast Srivastava and Mathias Payer.  Gramatron: Effective grammar-aware fuzzing.  In _Proceedings of the 30th acm sigsoft international symposium on software testing and analysis_ , pages 244–256, 2021.
  * Tsimpoukelli et al. [2021] Maria Tsimpoukelli, Jacob L Menick, Serkan Cabi, SM Eslami, Oriol Vinyals, and Felix Hill.  Multimodal few-shot learning with frozen language models.  _Advances in Neural Information Processing Systems_ , 34:200–212, 2021.
  * 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.
  * Vignac et al. [2022] Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard.  Digress: Discrete denoising diffusion for graph generation.  _arXiv preprint arXiv:2209.14734_ , 2022.
  * Wang et al. [2019] Junjie Wang, Bihuan Chen, Lei Wei, and Yang Liu.  Superion: Grammar-aware greybox fuzzing.  In _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_ , pages 724–735. IEEE, 2019.
  * Welch [1984] Terry A. Welch.  A technique for high-performance data compression.  _Computer_ , 17(06):8–19, 1984.
  * Wightman [2019] Ross Wightman.  Pytorch image models.  https://github.com/rwightman/pytorch-image-models, 2019.
  * Wood et al. [2012] Jo Wood, Petra Isenberg, Tobias Isenberg, Jason Dykes, Nadia Boukhelifa, and Aidan Slingsby.  Sketchy rendering for information visualization.  _IEEE transactions on visualization and computer graphics_ , 18(12):2749–2758, 2012.
  * Wu et al. [2023] David Xing Wu, Chulhee Yun, and Suvrit Sra.  On the training instability of shuffling sgd with batch normalization.  In _International Conference on Machine Learning_ , pages 37787–37845. PMLR, 2023.
  * Zeller et al. [2023] Andreas Zeller, Rahul Gopinath, Marcel Böhme, Gordon Fraser, and Christian Holler.  Efficient grammar fuzzing.  In _The Fuzzing Book_. CISPA Helmholtz Center for Information Security, 2023.  URL https://www.fuzzingbook.org/html/GrammarFuzzer.html.  Retrieved 2023-11-11 18:18:06+01:00.
  * Zhang et al. [2022] Jiyang Zhang, Sheena Panthaplackel, Pengyu Nie, Junyi Jessy Li, and Milos Gligoric.  Coditt5: Pretraining for source code and natural language editing.  In _Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering_ , pages 1–12, 2022.

## Appendix

##  Appendix A Mutation Algorithm

Figure 8: An example expression from CSG2D represented as a tree to help
illustrate the mutation algorithm. The green nodes are candidate nodes with
primitives count $\sigma(z)\leq 2$. Our mutation algorithm only mutates these
nodes.

Here we provide additional details on how we sample small mutations for tree
diffusion. We will first repeat the algorithm mentioned in Section 3 in more
detail.

Our goal is to take some syntax tree and apply a small random mutation. The
only type of mutation we consider is a replacement mutation. We first collect
a set of candidate nodes that we are allowed to replace. If we select a node
too high up in the tree, we end up replacing a very large part of the tree. To
make sure we only change a small part of the tree we only select nodes with
$\leq\sigma_{\text{small}}$ primitives. In Figure 8, if we set
$\sigma_{\text{small}}=2$, we get all the  green nodes. We sample a node, $m$,
uniformly from this  green set. We know the production rule for $m$ from the
CFG. For instance, if we selected node $15$, the only replacements allowed are
$+$ or $-$. If we selected node $46$, we can only replace it with an angle. If
we selected node $11$, we can replace it with any subexpression. When we
sample a replacement, we ensure that the replacement is
$\leq\sigma_{\text{small}}$, and that it is different than $m$. Here we show
$4$ random mutation steps on a small expression,

    (+ (+ (+ (Circle A D 4) (Quad F E 4 6 K)) (Quad 3 E C 2 M)) (Circle C 2 1))
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ --> (Circle 0 8 A)
    (+ (+ (Circle 0 8 A) (Quad 3 E C 2 M)) (Circle C 2 1))
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ --> (Quad 1 0 A 3 H)
    (+ (Quad 1 0 A 3 H) (Circle C 2 1))
                                ^ --> 4
    (+ (Quad 1 0 A 3 H) (Circle 4 2 1))
                                ^ --> 8
    (+ (Quad 1 0 A 3 H) (Circle 8 2 1))

During our experiments we realized that this style of random mutations biases
expression to get longer on average, since there are many more leaves than
parents of leaves. This made the network better at going from very long
expressions to target expressions, but not very good at editing shorter
expressions into longer ones. This also made our model’s context window run
out frequently when expressions got too long. To make the mutation length
effects more uniform, we add a slight modification to the algorithm mentioned
above and in Section 3.

For each of the candidate nodes, we find the set of production rules for the
candidates. We then select a random production rule, $r$, and then select a
node from the candidates with the production rule $r$, as follows,

$\displaystyle C$
$\displaystyle=\\{n\in\text{SyntaxTree}(z)\mid\sigma(n)\leq\sigma_{\text{small}}\\}$
$\displaystyle R$ $\displaystyle=\\{\text{ProductionRule}(n)\mid n\in C\\}$
$\displaystyle r$ $\displaystyle\sim\text{Uniform}[R]$ $\displaystyle M$
$\displaystyle=\\{n\in C\mid\text{ProductionRule}(n)=r\\}$ $\displaystyle m$
$\displaystyle\sim\text{Uniform}[M]$

For CSG2D, this approach empirically biased our method to make expressions
shorter $30.8\%$, equal $49.2\%$, and longer $20.0\%$ of the times
($n=10,000$).

##  Appendix B Context-Free Grammars

Here we provide the exact context-free grammars of the languages used in this
work.

(a)

(b)

Figure 9: Examples of images drawn with the (a) CSG2D and (b) TinySVG
languages.

###  B.1 CSG2D

    s: binop | circle | quad
    binop: (op s s)
    op: + | -

    number: [0 to 15]
    angle: [0 to 315]

    // (Circle radius x y)
    circle: (Circle r=number x=number y=number)

    // (Quad x y w h angle)
    // quad: (Quad x=number y=number
                   w=number h=number
                   theta=angle)

###  B.2 TinySVG

    s: arrange | rect | ellipse | move
    direction: v | h
    color: red | green | blue | yellow | purple | orange | black | white | none
    number: [0 - 9]
    sign: + | -

    rect: (Rectangle w=number h=number fill=color stroke=color border=number)

    ellipse: (Ellipse w=number h=number fill=color stroke=color border=number)

    // Arrange direction left right gap
    arrange: (Arrange direction s s gap=number)

    move: (Move s dx=sign number dy=sign number)

##  Appendix C Sketch Simulation

Figure 10: Examples of the same scene being called multiple times by our
sketch observation model.

As mentioned in the main text, we implement the CSG2D-Sketch environment,
which is the same as CSG2D with a hand-drawn sketch observation model. We do
this to primarily show how this sort of a generative model can possibly be
applied to a real-world task, and that observations do not need to be
deterministic. Our sketch algorithm can be found in our codebase, and is based
off the approach described in Wood et al. [39].

Our compiler uses Iceberg [16] and Google’s 2D Skia library to perform boolean
operations on primitive paths. The resulting path consists of line and cubic
bézier commands. We post-process these commands to generate sketches. For each
command, we first add Gaussian noise to all points stated in those commands.
For each line, we randomly pick a point near the $50\%$ and $75\%$ of the
line, add Gaussian noise, and fit a Catmull-Rom spline [5]. For all curves, we
sample random points at uniform intervals and fit Catmull-Rom splines. We have
a special condition for circles, where we ensure that the start and end points
are randomized to create the effect of the pen lifting off. Additionally we
randomize the stroke thickness.

Figure 10 shows the same program rendered multiple times using our randomized
sketch simulator.

##  Appendix D Complexity Filtering

(a)

(b)

Figure 11: Examples of thresholding scene images using the LZ4 compression
algorithm. The left represents our test set, the right represents our training
distribution.

As mentioned in Section 4, while testing our method alongside baseline
methods, we reached ceiling performance for all our methods. Ellis et al. [11]
got around this by creating a “hard” test case by sampling more objects. For
us, when we increased the number of objects to increase complexity, we saw
that it increased the probability that a large object would be sampled and
subtract from the whole scene, resulting in simpler scenes. This is shown by
Figure 11(b), which is our training distribution. Even though we sample a
large number of objects, the scenes don’t look visually interesting. When we
studied the implementation details of Ellis et al. [11], we noticed that
during random generation of expressions, they ensured that each shape did not
change more that $60\%$ or less than $10\%$ of the pixels in the scene.
Instead of modifying our tree sampling method, we instead chose to rejection
sample based on the compressibility of the final rendered image.

##  Appendix E Tree Path Algorithm

Algorithm 1 TreeDiff: Find the first set of mutations to turn one tree to
another.

0: treeA: source tree, treeB: target tree, max_primitives: maximum primitives

0: List of mutations to transform treeA into treeB

1: if NodeEq(treeA, treeB) then

2: mutations $\leftarrow$ []

3: for each $(\texttt{childA},\texttt{childB})$ in zip(treeA.children,
treeB.children) do

4: mutations $\leftarrow$ mutations \+ TreeDiff(childA, childB,
max_primitives)

5: end for

6: return mutations

7: else

8: if treeA.primitive_count $\leq$ max_primitives and treeB.primitive_count
$\leq$ max_primitives then

9: return [Mutation(treeA.start_pos, treeA.end_pos, treeB.expression)]

10: else

11: new_expression $\leftarrow$ GenerateNewExpression(treeA.production_rule,
max_primitives)

12: tightening_diffs $\leftarrow$ TreeDiff(new_expression, treeB,
max_primitives)

13: new_expression $\leftarrow$ ApplyAllMutations(new_expression,
tightening_diffs)

14: return [Mutation(treeA.start_pos, treeA.end_pos, new_expression)]

15: end if

16: end if

Algorithm 1 shows the high-level pseudocode for how we find the first step of
mutations to transform tree $A$ into tree $B$. We linearly walk down both
trees until we find a node that is different. If the target node is small,
i.e., its $\sigma(z)\leq\sigma_{\text{small}}$, then we can simply mutate the
source to the target. If the target node is larger, we sample a random small
expression with the correct production rule, and compute the path from this
small expression to the target. This gives us the first step to convert the
source node to the target node. Repeatedly using Algorithm 1 gives us the full
path to convert one expression to another. We note that this path is not
necessarily the optimal path, but a valid path that is less noisy than the
path we would get by simply chasing the last random mutation.

Figure 12 conceptually shows why computing this tree path might be necessary.
The circle represents the space of programs. Consider a starting program
$z_{0}$. Each of the black arrows represents a random mutation that kicks the
program to a slightly different program, so $z_{0}\to z_{1}$, then $z_{2}\to
z_{3}\ldots$. If we provide the neural network the supervised target to go
from $z_{5}$ to $z_{4}$, we are teaching the network to take an inefficient
path to $z_{0}$. The green path is the direct path from $z_{5}\to z_{0}$.

Figure 12: A conceptual illustration of why we need tree path-finding. The red
path represents the naive target for the neural network. The green path
represents the path-finding algorithm’s target.

##  Appendix F Implementation Details

We implement our architecture in PyTorch [1]. For our image encoder we use the
NF-ResNet26 [4] implementation from the open-sourced library by Wightman [38].
Images are of size $128\times 128\times 1$ for CSG2D and $128\times 128\times
3$ for TinySVG. We pass the current and target images as a stack of image
planes into the image encoder. Additionally, we provide the absolute
difference between current and target image as additional planes.

Our decoder-only transformer [34, 26] uses $8$ layers, $16$ heads, with an
embedding size of $256$. We use batch size $32$ and optimize with Adam [18]
with a learning rate of $3\times 10^{-4}$. The image embeddings are of the
same size as the transformer embeddings. We use $4$ prefix tokens for the
image embeddings. We used a maximum context size of $512$ tokens. For both
environments, we sampled expressions with at most $8$ primitives. Our method
and all baseline methods used this architecture. We did not do any
hyperparameter sweeps or tuning.

For the autoregressive (CSGNet) baseline, we trained the model to output
ground-truth programs from target images, and provided a blank current image.
For tree diffusion methods, we initialized the search and rollouts using the
output of the autoregressive model, which counted as a single node expansion.
For our re-implementation of Ellis et al. [11], we flattened the CSG2D tree
into shapes being added from left to right. We then randomly sampled a
position in this shape array, compiled the output up until the sampled
position, and trained the model to output the next shape using constrained
grammar decoding.

This is a departure from the pointer network architecture in their work. We
think that the lack of prior shaping, departure from a graphics specific
pointer network, and not using reinforcement learning to fine-tune leads to a
performance difference between their results and our re-implementation. We
note that our method does not require any of these additional features, and
thus the comparison is fairer. For tree diffusion search, we used a beam size
of $64$, with a maximum node expansion budget of $5000$ nodes.


# Seiberg-Witten Theory and Monstrous Moonshine

Shun’ya<EMAIL_ADDRESS>Theory Center, Institute of
Particle and Nuclear Studies, KEK
Tsukuba, Ibaraki, 305-0801, Japan  SOKENDAI (The Graduate University for
Advanced Studies)
Tsukuba, Ibaraki, 305-0801, Japan

(August 22, 2022)

###### Abstract

We study the relation between the instanton expansion of the Seiberg-Witten
prepotential for $D=4$, ${\cal N}=2$ $SU(2)$ SUSY gauge theory for $N_{f}=0$
and $1$ and the monstrous moonshine. By utilizing a newly developed simple
method to obtain the SW prepotential, it is shown that the coefficients of the
expansion of $q=e^{2\pi\tau}$ in terms of $A^{2}=\frac{\Lambda^{2}}{16a^{2}}$
($N_{f}=0$) or $\frac{\Lambda^{2}}{16\sqrt{2}a^{2}}$ ($N_{f}=1$) are all
integer coefficient polynomials of the moonshine coefficients of the modular
$j$-function. A relationship between the AGT $c=25$ Liouville CFT and the
$c=24$ vertex operator algebra CFT of the moonshine module is also suggested.

††preprint: KEK-TH-2446

“Seiberg-Witten (SW) theory” SW1 ; SW2  is a method, or the entire framework
thereof, for solving analytically (and/or geometrically) the low-energy
strongly coupled dynamics of $D=4$, ${\cal N}=2$ (originally $SU(2)$) SUSY
gauge theory, based on the idea that, after all, the complexified gauge
coupling can be identified (for the $SU(2)$ case) as the complex structure
modulus of an elliptic fibration (see Tachikawalecture  for a review). It
succeeded to determine the exact low-energy effective prepotential including
the full instanton contributions NekrasovOkounkov  in terms of some integrals
on the “Seiberg-Witten curve”. It has developed in connection with various
research areas of modern string theory and mathematical physics, such as
embedding into M-theory/Gaiotto duality MtheoryGaiottoduality , 7-brane
system/F-theory 7-braneFtheory , E-strings Estrings , AGT 4d/2d correspondence
AGT  and matrix models (e.g.)matrixmodels .

“Monstrous moonshine”, on the other hand, refers to the curious fact, first
noticed by John McKay in 1979, that the Fourier coefficients of the modular
$j$-function can be written as a simple linear combination of dimensions of
irreducible representations of the monster group MonstrousMoonshine  (see
McKayessay  for a review including interesting anecdotes about the monstrous
moonshine). The reasoning for this coincidence was given by constructing
$c=24$ vertex operator algebra CFT whose character is the $j$-function such
that the monster group acts on this module as a symmetry FLM . Later it was
shown that this was a $\hbox{\mybb Z}_{2}$ asymmetric orbifold DGH .

In this paper, we study the relation between the two. In fact, the fact that
the two are related is not in itself surprising. This is because a SW curve is
a rational elliptic surface over the $u$-plane and the $j$-function is a
fundamental function in the theory of elliptic functions. However, the details
of this specific relationship have not been known until now. This paper fills
this gap.

We use a newly developed method for easily deriving the $SU(2)$ SW
prepotential to show that the coefficients of the instanton expansion of the
prepotential are related to the monstrous moonshine in a way specifically
explained in the text. In particular, it is shown that, in the $N_{f}=0$ case,
the coefficients of the expansion of $q=e^{2\pi\tau}$ in terms of
$A^{2}=\frac{\Lambda^{2}}{16a^{2}}$ are all integer coefficient polynomials of
the moonshine coefficients. A similar thing holds for $N_{f}=1$.

The idea of the new method is very simple. The modular $j$-function has an
expansion in terms of $q=e^{2\pi i\tau}$ as 111All the series expansions
performed in this paper have been assisted by Mathematica.

$\displaystyle j(\tau)$ $\displaystyle=$
$\displaystyle\frac{1}{q}+744+196884q+21493760q^{2}+864299970q^{3}+20245856256q^{4}+O\left(q^{5}\right).$
(1)

Thus $q$ is conversely expanded in terms of $\frac{1}{j}$ as

$\displaystyle q$ $\displaystyle=$
$\displaystyle{\textstyle\frac{1}{j}+a_{0}\left(\frac{1}{j}\right)^{2}+\left(a_{0}^{2}+a_{1}\right)\left(\frac{1}{j}\right)^{3}+\left(a_{0}^{3}+3a_{1}a_{0}+a_{2}\right)\left(\frac{1}{j}\right)^{4}+O\left(\left(\frac{1}{j}\right)^{5}\right)},$
(2)

where $a_{0}=744$, $a_{1}=196884$, $a_{2}=21493760$,… are the coefficients of
the expansion (1). Note that the coefficient of the $(\frac{1}{j})^{k}$ term
in (2) is an integer given by a $(k-1)$th order homogeneous polynomial of
$a_{i}$ if the “degree” of $a_{i}$ is counted as $i+1$. Since $q=e^{2\pi
i\tau}$, we can obtain $2\pi i$ times the prepotential by taking its logarithm
and integrating it with respect to $a$ twice. On the other hand, suppose that
the SW curve is given in the Weierstrass form

$\displaystyle Y^{2}$ $\displaystyle=$ $\displaystyle X^{3}+f(u)X+g(u),$ (3)

then its complex structure modulus $\tau$ is found by inversely solving the
equation

$\displaystyle j(\tau)$ $\displaystyle=$ $\displaystyle\frac{12^{3}\cdot
4f(u)^{3}}{4f(u)^{3}+27g(u)^{2}}.$ (4)

We expand the rhs of this equation (4) by $u$ around $u=\infty$, thereby
obtain a $1/j$-expansion of $1/u$. Furthermore, since the $1/a$-expansion of
$1/u$ is obtained by the period integral on the SW curve, we end up with the
$1/a$-expansion of $q$, from which the $1/a$-expansion of the prepotential
${\cal F}$ is obtained.

As a concrete example, let us consider the pure ($N_{f}=0$) $SU(2)$ ${\cal
N}=2$ SYM theory. The SW curve is given in the quartic-polynomial
representation as HananyOz

$\displaystyle y^{2}$ $\displaystyle=$ $\displaystyle
C(x)^{2}-G(x),~{}~{}~{}C(x)=x^{2}-u,~{}~{}~{}G(x)=\Lambda^{4}.$ (5)

The is equivalent to the Weierstrass form

$\displaystyle Y^{2}$ $\displaystyle=$ $\displaystyle
X^{3}+f(u)X+g(u),~{}~{}~{}$ $\displaystyle f(u)$ $\displaystyle=$
$\displaystyle-\frac{16}{3}u^{2}+4\Lambda^{4},~{}~{}~{}$ (6) $\displaystyle
g(u)$ $\displaystyle=$
$\displaystyle-\frac{128}{27}u^{3}+\frac{16}{3}\Lambda^{4}u$

The integral of the holomorphic differential along the cycle that collapses as
$u\rightarrow\infty$ yields $\frac{\partial a}{\partial u}$, which can be
obtained by, for instance, solving the Picard-Fuchs equation KLT . The result
is

$\displaystyle\frac{\partial a}{\partial u}$ $\displaystyle=$
$\displaystyle\frac{\sqrt{2}}{4\sqrt{u}}F\left(\frac{1}{4},\frac{3}{4},1;\frac{\Lambda^{4}}{u^{2}}\right).$
(7)

Integrating it with respect to $u$, we find

$\displaystyle a$ $\displaystyle=$
$\displaystyle-\frac{\sqrt{u}}{\sqrt{2}}\sum_{n=0}^{\infty}\frac{(4n-3)!!}{4^{2n}(n!)^{2}}\left(\frac{\Lambda^{4}}{u^{2}}\right)^{n},$
(8)

where we have used the infinite series representation of the hyperelliptic
function.

Looking at this, it might appear that, except its prefactor, $a$ has a series
expansion in $\frac{\Lambda^{4}}{u^{2}}$ with rational-number coefficients
whose denominators are integers containing very many prime factors. This is
not case, however, as all the factors of powers of odd prime integers in
$(n!)^{2}$ are contained in $(4n-3)!!$ and hence cancel out, leaving only
powers of $2$ in the denominator. Moreover, these factors of powers of 2 turn
out to be absorbed if we take the expansion parameter to be
$\frac{\Lambda^{4}}{8u^{2}}$ instead of $\frac{\Lambda^{4}}{u^{2}}$.
Therefore, defining

$\displaystyle
A\equiv\frac{\Lambda}{4a},~{}~{}~{}U\equiv\frac{\Lambda^{2}}{8u},$ (9)

$A^{2}$ is expanded by $U$ as

$\displaystyle A^{2}$ $\displaystyle=$
$\displaystyle\frac{U}{\left(\sum_{n=0}^{\infty}\frac{(4n-3)!!}{(n!)^{2}}(4U^{2})^{n}\right)^{2}}$
(10) $\displaystyle=$ $\displaystyle
U+8U^{3}+168U^{5}+5056U^{7}+184040U^{9}+7525440U^{11}+332612800U^{13}$
$\displaystyle+15538219520U^{15}+756483502440U^{17}+38023703291200U^{19}$
$\displaystyle+1960287432256832U^{21}+103165644665826816U^{23}+O\left(U^{25}\right),$

where the coefficients are all positive integers. Note that the factor of $8$
in the denominator of $U$ is the smallest one that can absorb all the factors
of powers of $2^{-1}$ in the expansion. This $U$ is inversely expanded by
$A^{2}$ as

$\displaystyle U$ $\displaystyle=$ $\displaystyle
A^{2}-8A^{6}+24A^{10}-448A^{14}-4520A^{18}-151872A^{22}-4095296A^{26}$ (11)
$\displaystyle-124070400A^{30}-3886030632A^{34}-126167064640A^{38}-4206822732736A^{42}$
$\displaystyle-143383813565952A^{46}+O\left(A^{50}\right).$

On the other hand, by plugging (6) into (4), we have

$\displaystyle\frac{1}{j}$ $\displaystyle=$
$\displaystyle\frac{U^{4}\left(1-64U^{2}\right)}{\left(1-48U^{2}\right)^{3}}$
$\displaystyle=$ $\displaystyle
U^{4}+80U^{6}+4608U^{8}+221184U^{10}+8847360U^{12}+254803968U^{14}-782757789696U^{18}$
$\displaystyle-84537841287168U^{20}-6763027302973440U^{22}-476117122129330176U^{24}+O(U^{25}).$

Thus, using this in (11), we obtain an $A^{2}$-expansion of $\frac{1}{j}$.
This expansion can be further used in (2) to finally obtain an
$A^{2}$-expansion of $q$. We can see from (2), (LABEL:1/jbyU) and (11) that
its expansion coefficients are all integer-coefficient polynomials of
$a_{i}$’s. Though we do not present the explicit expression for this expansion
of $q$, we instead show the expansion of its logarithm:

$\displaystyle 2\pi i\tau$ $\displaystyle=$ $\displaystyle\log
A^{8}+48A^{4}+(a_{0}+96)A^{8}+48(a_{0}-304)A^{12}$
$\displaystyle+\frac{1}{2}\left(a_{0}^{2}+2496a_{0}+2a_{1}-1570368\right)A^{16}+\frac{48}{5}\left(5a_{0}^{2}+880a_{0}+10a_{1}-3352464\right)A^{20}$
$\displaystyle+\frac{1}{3}\left(a_{0}^{3}+7200a_{0}^{2}+6a_{1}a_{0}-3447648a_{0}+14400a_{1}+3a_{2}-3648416256\right)A^{24}$
$\displaystyle+\frac{48}{7}\left(7a_{0}^{3}+9968a_{0}^{2}+42a_{1}a_{0}-12245520a_{0}+19936a_{1}+21a_{2}-6513833472\right)A^{28}$
$\displaystyle+\frac{1}{4}\left(a_{0}^{4}+14208a_{0}^{3}+12a_{1}a_{0}^{2}+140160a_{0}^{2}+85248a_{1}a_{0}+12a_{2}a_{0}\right.$
$\displaystyle\left.-15707695104a_{0}+6a_{1}^{2}+280320a_{1}+42624a_{2}+4a_{3}-6519374734464\right)A^{32}+O\left(A^{34}\right).$

Thus we can find the expansion of $2\pi i$ times the prepotential ${\cal F}$
by integrating (LABEL:2piitau) with respect to $a$ twice. For example, if we
integrate the second term $48A^{4}$ with respect to $a$ twice, we get

$\displaystyle 48A^{4}$ $\displaystyle\stackrel{{\scriptstyle(\int
da)^{2}}}{{\rightarrow}}$ $\displaystyle\frac{48}{4^{4}\cdot 3\cdot
2}\frac{\Lambda^{4}}{a^{2}}=\frac{1}{32}\frac{\Lambda^{4}}{a^{2}},$ (14)

which agrees with the $k=1$ term of the known $N_{f}=0$ prepotential

$\displaystyle{\cal F}={i\,a^{2}\over 2\pi}\left(4\log{a\over\Lambda}-6+8\log
2-\sum_{k=1}^{\infty}{\cal F}_{k}\left(\Lambda\over a\right)^{4k}\right)$ (15)

(Table 1). From the third term $(a_{0}+96)A^{8}$ we can compute the $k=2$
term. By using $a_{0}=744$ we find

$\displaystyle(a_{0}+96)A^{8}$ $\displaystyle\stackrel{{\scriptstyle(\int
da)^{2}}}{{\rightarrow}}$ $\displaystyle\frac{a_{0}+96}{4^{8}\cdot 7\cdot
6}=\frac{5}{16384}\frac{\Lambda^{8}}{a^{6}}=\frac{5}{2^{14}}\frac{\Lambda^{8}}{a^{6}},$
(16)

which is also the correct result.

In fact, $a_{0}=744$ ($=3\times\mbox{dim}E_{8}$) has nothing to do with the
monster; the first Fourier coefficient $a_{1}$ related to monster
representations appears for the first time in the $A^{16}$ term. From this, by
using $a_{0}=744$, $a_{1}=196884$ and integrating with respect to $a$ twice,
we find

$\displaystyle\frac{1}{2}(-1570368+2496a_{0}+a_{0}^{2}+2a_{1})A^{16}$
$\displaystyle\stackrel{{\scriptstyle(\int da)^{2}}}{{\rightarrow}}$
$\displaystyle\frac{\frac{1}{2}(-1570368+2496a_{0}+a_{0}^{2}+2a_{1})}{4^{16}\cdot
15\cdot 14}\frac{\Lambda^{16}}{a^{14}}$ (17) $\displaystyle=$
$\displaystyle\frac{1469}{2^{31}}\frac{\Lambda^{16}}{a^{14}},$

which is a correct answer. In this way, all the known results can be correctly
recovered. Incidentally, since this method directly determines $\tau$, it also
correctly produces the perturbative part of ${\cal F}$ (15). Indeed,
$\frac{1}{2\pi i}\times$

$\displaystyle\int da\int da\log A^{8}$ $\displaystyle=$ $\displaystyle
6a^{2}+\frac{1}{2}a^{2}\log\left(\frac{\Lambda^{8}}{2^{16}a^{8}}\right)$ (18)

coincides with the perturbative part.

$k$ | Rational-coefficient polynomial of $a_{i}$’s | ${\cal F}_{k}$
---|---|---
1 | $\frac{48}{4^{4}\cdot 3\cdot 2}$ | $1\over 2^{5}$
2 | $\frac{a_{0}+96}{4^{8}\cdot 7\cdot 6}$ | $5\over 2^{14}$
3 | $\frac{48(a_{0}-304)}{4^{12}\cdot 11\cdot 10}$ | $3\over 2^{18}$
4 | $\frac{\frac{1}{2}\left(a_{0}^{2}+2496a_{0}+2a_{1}-1570368\right)}{4^{16}\cdot 15\cdot 14}$ | $1469\over 2^{31}$
5 | $\frac{\frac{48}{5}\left(5a_{0}^{2}+880a_{0}+10a_{1}-3352464\right)}{4^{20}\cdot 19\cdot 18}$ | $4471\over 2^{34}\cdot 5$
6 | $\frac{\frac{1}{3}\left(a_{0}^{3}+7200a_{0}^{2}+6a_{1}a_{0}-3447648a_{0}+14400a_{1}+3a_{2}-3648416256\right)}{4^{24}\cdot 23\cdot 22}$ | $40397\over 2^{43}$
7 | $\frac{\frac{48}{7}\left(7a_{0}^{3}+9968a_{0}^{2}+42a_{1}a_{0}-12245520a_{0}+19936a_{1}+21a_{2}-6513833472\right)}{4^{28}\cdot 27\cdot 26}$ | $441325\over 2^{47}\cdot 7$
8 | $\frac{\frac{1}{4}\left(a_{0}^{4}+14208a_{0}^{3}+12a_{1}a_{0}^{2}+140160a_{0}^{2}+85248a_{1}a_{0}+12a_{2}a_{0}-15707695104a_{0}+6a_{1}^{2}+280320a_{1}+42624a_{2}+4a_{3}-6519374734464\right)}{4^{32}\cdot 31\cdot 30}$ | $866589165\over 2^{64}$
$\vdots$ | $\vdots$ | $\vdots$
Table 1:  The instanton expansion of the prepotential for $N_{f}=0$ and the
monstrous moonshine. If we use the actual values of the Fourier coefficients
$a_{i}$’s of the $j$-function in the middle column, we re-derive the correct
${\cal F}_{k}$ in the right column on the corresponding row. Since each
$a_{i}$ is a integer-coefficient linear combination of the dimensions of
irreducible representations of the monster, ${\cal F}_{k}$ is also a rational-
coefficient polynomial of them.

The similar is true for $N_{f}=1$. The SW curve for $N_{f}=1$ is

$\displaystyle y^{2}$ $\displaystyle=$ $\displaystyle
C(x)^{2}-G(x),~{}~{}~{}C(x)=x^{2}-u,~{}~{}~{}G(x)=\Lambda^{3}(x+m)$ (19)

in the quartic-polynomial representation, whose equivalent Weierstrass form
reads

$\displaystyle Y^{2}$ $\displaystyle=$ $\displaystyle
X^{3}+f(u,m)X+g(u,m),~{}~{}~{}$ $\displaystyle f(u,m)$ $\displaystyle=$
$\displaystyle-\frac{16}{3}u^{2}+4\Lambda^{3}m,~{}~{}~{}$ (20) $\displaystyle
g(u,m)$ $\displaystyle=$
$\displaystyle-\frac{128}{27}u^{3}+\frac{16}{3}\Lambda^{3}mu-\Lambda^{6}.$

From these data, $1/j$ can be computed as

$\displaystyle\frac{1}{j}$ $\displaystyle=$
$\displaystyle\frac{U^{3}\left(\left(64\hat{m}^{3}+432\right)U^{3}-72\hat{m}U^{2}-\hat{m}^{2}U+1\right)}{\left(48\hat{m}U^{2}-1\right)^{3}}$
(21) $\displaystyle=$
$\displaystyle-U^{3}+\hat{m}^{2}U^{4}-72\hat{m}U^{5}+\left(80\hat{m}^{3}-432\right)U^{6}-3456\hat{m}^{2}U^{7}$
$\displaystyle+\left(13824\hat{m}^{4}-144\hat{m}\left(64\hat{m}^{3}+432\right)\right)U^{8}-110592\hat{m}^{3}U^{9}$
$\displaystyle+\left(1105920\hat{m}^{5}-13824\hat{m}^{2}\left(64\hat{m}^{3}+432\right)\right)U^{10}$
$\displaystyle+\left(79626240\hat{m}^{6}-1105920\hat{m}^{3}\left(64\hat{m}^{3}+432\right)\right)U^{12}+382205952\hat{m}^{5}U^{13}$
$\displaystyle+\left(5350883328\hat{m}^{7}-79626240\hat{m}^{4}\left(64\hat{m}^{3}+432\right)\right)U^{14}+42807066624\hat{m}^{6}U^{15}$
$\displaystyle+\left(342456532992\hat{m}^{8}-5350883328\hat{m}^{5}\left(64\hat{m}^{3}+432\right)\right)U^{16}+O\left(U^{17}\right),$

where $U\equiv\frac{\Lambda^{2}}{16u}$, $\hat{m}\equiv\frac{4m}{\Lambda}$ in
this $N_{f}=1$ case.

On the other hand, $\frac{\partial a}{\partial u}$ is given by using the
quadratic and cubic transformations of the hypergeometric functions
MasudaSuzuki

$\displaystyle\frac{\partial a}{\partial u}$ $\displaystyle=$
$\displaystyle\frac{F\left(\frac{1}{12},\frac{5}{12},1;\frac{12^{3}}{j}\right)}{\sqrt{2}(-3f(u,m))^{\frac{1}{4}}}.$
(22)

Plugging (20), (21) in this equation, we find

$\displaystyle\frac{\partial a}{\partial u}$ $\displaystyle=$
$\displaystyle\frac{1}{2\sqrt{2u}}(1+12\hat{m}U^{2}-60U^{3}+420\hat{m}^{2}U^{4}-5040\hat{m}U^{5}+\left(18480\hat{m}^{3}+13860\right)U^{6}$
(23)
$\displaystyle-360360\hat{m}^{2}U^{7}+\left(900900\hat{m}^{4}+2162160\hat{m}\right)U^{8}+\left(-24504480\hat{m}^{3}-4084080\right)U^{9}$
$\displaystyle+\left(46558512\hat{m}^{5}+232792560\hat{m}^{2}\right)U^{10}+\left(-1629547920\hat{m}^{4}-931170240\hat{m}\right)U^{11}$
$\displaystyle+\left(2498640144\hat{m}^{6}+21416915520\hat{m}^{3}+1338557220\right)U^{12}$
$\displaystyle+\left(-107084577600\hat{m}^{5}-133855722000\hat{m}^{2}\right)U^{13}$
$\displaystyle+\left(137680171200\hat{m}^{7}+1807052247000\hat{m}^{4}+401567166000\hat{m}\right)U^{14}+O\left(U^{15}\right)).$

Integrating this with respect to $u$, we derive a $u$-expansion of $a$, from
which the expansion of $U\equiv\frac{\Lambda^{2}}{16u}$ in terms of
$A\equiv\frac{\Lambda}{4\sqrt{2}a}$ is found as follows:

$\displaystyle U$ $\displaystyle=$ $\displaystyle
A^{2}-8A^{6}\hat{m}+24A^{8}+24A^{10}\hat{m}^{2}+64A^{12}\hat{m}-8A^{14}\left(56\hat{m}^{3}+81\right)+6960A^{16}\hat{m}^{2}$
$\displaystyle-40A^{18}\left(\hat{m}\left(113\hat{m}^{3}+1128\right)\right)+384A^{20}\left(449\hat{m}^{3}+268\right)-1344A^{22}\left(\hat{m}^{2}\left(113\hat{m}^{3}+1517\right)\right)$
$\displaystyle+128A^{24}\hat{m}\left(46735\hat{m}^{3}+77976\right)-8A^{26}\left(511912\hat{m}^{6}+11530560\hat{m}^{3}+2197485\right)+O\left(A^{27}\right).$

Thus $\frac{1}{j}$ is expanded by $A^{2}$, whose coefficients are this time
integer-coefficient polynomials of $\hat{m}$. This yields

$\displaystyle q$ $\displaystyle=$
$\displaystyle-A^{6}+A^{8}\hat{m}^{2}-48A^{10}\hat{m}+A^{12}\left(a_{0}+48\hat{m}^{3}-504\right)-2A^{14}\left((a_{0}+372)\hat{m}^{2}\right)$
(25)
$\displaystyle+A^{16}\left((a_{0}+1248)\hat{m}^{4}+96(a_{0}-512)\hat{m}\right)$
$\displaystyle+A^{18}\left(-192(a_{0}-212)\hat{m}^{3}-a_{0}^{2}+1008a_{0}-a_{1}-61992\right)$
$\displaystyle+3A^{20}\hat{m}^{2}\left(32(a_{0}+88)\hat{m}^{3}+a_{0}^{2}+928a_{0}+a_{1}-939920\right)$
$\displaystyle-3A^{22}\left(\hat{m}\left(\left(a_{0}^{2}+2864a_{0}+a_{1}-1343656\right)\hat{m}^{3}+48a_{0}^{2}-48896a_{0}+48(a_{1}+67320)\right)\right)$
$\displaystyle+A^{24}\left(\left(a_{0}^{2}+4800a_{0}+a_{1}-1149216\right)\hat{m}^{6}+48\left(9a_{0}^{2}-3264a_{0}+9a_{1}-2473280\right)\hat{m}^{3}\right.$
$\displaystyle\left.+a_{0}^{3}-1512a_{0}^{2}-1512a_{1}+3a_{0}(a_{1}+126000)+a_{2}-2282112\right)$
$\displaystyle-4A^{26}\left(\hat{m}^{2}\left(12\left(9a_{0}^{2}+2640a_{0}+9a_{1}-4424600\right)\hat{m}^{3}+a_{0}^{3}+1530a_{0}^{2}\right.\right.$
$\displaystyle\left.\left.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+3(a_{1}-915340)a_{0}+1530a_{1}+a_{2}+215271600\right)\right)$
$\displaystyle+6A^{28}\left(8\left(3a_{0}^{2}+2848a_{0}+3(a_{1}-583120)\right)\hat{m}^{7}+\left(a_{0}^{3}+4572a_{0}^{2}+3(a_{1}-1279560)a_{0}\right.\right.$
$\displaystyle\left.\left.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+4572a_{1}+a_{2}-632801280\right)\hat{m}^{4}+32\left(a_{0}^{3}-1524a_{0}^{2}+3(a_{1}+130008)a_{0}\right.\right.$
$\displaystyle\left.\left.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-1524a_{1}+a_{2}-2995968\right)\hat{m}\right)$
$\displaystyle+A^{30}\left(-4\left(a_{0}^{3}+7614a_{0}^{2}+3(a_{1}-966660)a_{0}+7614a_{1}+a_{2}-2146774992\right)\hat{m}^{6}\right.$
$\displaystyle\left.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-768\left(a_{0}^{3}-498a_{0}^{2}+(3a_{1}-670444)a_{0}-498a_{1}+a_{2}+73856560\right)\hat{m}^{3}\right.$
$\displaystyle\left.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-a_{0}^{4}+2016a_{0}^{3}-2a_{1}^{2}-948024a_{1}-6a_{0}^{2}(a_{1}+158004)\right.$
$\displaystyle\left.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+a_{0}(6048a_{1}-4a_{2}+67052160)+2016a_{2}-a_{3}-146853000\right)$
$\displaystyle+O\left(A^{32}\right),$

whose coefficients are again integer-coefficient polynomials of $a_{i}$’s and
$\hat{m}$. The $a_{1}$, $a_{2}$ and $a_{3}$ related to the monster group
representation appear for the first time in the coefficients of $A^{18}$,
$A^{26}$ and $A^{30}$, respectively. Taking the logarithm and integrating with
respect to $a$ twice, we can derive $2\pi i$ times the $N_{f}=1$ prepotential

$\displaystyle{\cal F}^{N_{f}=1}$ $\displaystyle=$
$\displaystyle{i\,a^{2}\over
2\pi}\left(3\log\frac{a}{\Lambda}+\frac{1}{2}\left(-9+15\log 2+\pi
i\right)-\frac{m^{2}\log\frac{a}{\Lambda}}{2a^{2}}-\sum_{k=2}^{\infty}{\cal
F}^{N_{f}=1}_{k}\left(\Lambda\over a\right)^{2k}\right)$ (26)

with ${\cal F}^{N_{f}=1}_{k}$’s shown in Table 2.

$k$ | Rational-coefficient polynomial of $a_{i}$’s | ${\cal F}^{N_{f}=1}_{k}$
---|---|---
2 | $\frac{\frac{1}{2}(96{\hat{m}}-{\hat{m}}^{4})}{(4\sqrt{2})^{4}\cdot 3\cdot 2}$ | $\frac{\tilde{m}}{32}-\frac{\tilde{m}^{4}}{48}$
3 | $\frac{\frac{1}{3}(1512-3a_{0}-{\hat{m}}^{6})}{(4\sqrt{2})^{6}\cdot 5\cdot 4}$ | $-\frac{3}{8192}-\frac{\tilde{m}^{6}}{480}$
4 | $\frac{\frac{1}{4}((4a_{0}+384)\hat{m}^{2}-{\hat{m}}^{8})}{(4\sqrt{2})^{8}\cdot 7\cdot 6}$ | $\frac{5\tilde{m}^{2}}{16384}-\frac{\tilde{m}^{8}}{2688}$
5 | $\frac{\frac{1}{5}((-240a_{0}+124800)\hat{m}-{\hat{m}}^{10})}{(4\sqrt{2})^{10}\cdot 9\cdot 8}$ | $-\frac{7\tilde{m}}{393216}-\frac{\tilde{m}^{10}}{11520}$
6 | $\frac{\frac{1}{6}(-390096-3024a_{0}+3a_{0}^{2}+6a_{1}+(-87552+288a_{0})\hat{m}^{3}-\hat{m}^{12})}{(4\sqrt{2})^{12}\cdot 11\cdot 10}$ | $\frac{153}{536870912}+\frac{3\tilde{m}^{3}}{262144}-\frac{\tilde{m}^{12}}{42240}$
7 | $\frac{\frac{1}{7}((7382760-5208a_{0}-7a_{0}^{2}-14a_{1})\hat{m}^{2}-\hat{m}^{14})}{(4\sqrt{2})^{14}\cdot 13\cdot 12}$ | $-\frac{715\tilde{m}^{2}}{536870912}-\frac{\tilde{m}^{14}}{139776}$
8 | $\frac{\frac{1}{8}((-46891008-393216a_{0}+384a_{0}^{2}+768a_{1})\hat{m}+(-6281472+9984a_{0}+4a_{0}^{2}+8a_{1})\hat{m}^{4}-\hat{m}^{16})}{(4\sqrt{2})^{16}\cdot 15\cdot 14}$ | $\frac{1131\tilde{m}}{21474836480}+\frac{1469\tilde{m}^{4}}{2147483648}-\frac{\tilde{m}^{16}}{430080}$
9 | $\frac{{\scriptsize\begin{array}[]{c}\frac{1}{9}\left(-864a_{0}^{2}\hat{m}^{3}+366336a_{0}\hat{m}^{3}-1728a_{1}\hat{m}^{3}-3a_{0}^{3}+4536a_{0}^{2}-557928a_{0}\right.\\\\[-5.0pt] \left.-18a_{0}a_{1}+9072a_{1}-9a_{2}-\hat{m}^{18}+381411072\hat{m}^{3}+123415488\right)\end{array}}}{(4\sqrt{2})^{18}\cdot 17\cdot 16}$ | $-\frac{385}{549755813888}-\frac{525\tilde{m}^{3}}{4294967296}-\frac{\tilde{m}^{18}}{1253376}$
$\vdots$ | $\vdots$ | $\vdots$
Table 2:  The instanton expansion of the prepotential for $N_{f}=1$ and the
monstrous moonshine. We have defined $\tilde{m}\equiv\frac{m}{\Lambda}$ and
$\hat{m}\equiv\frac{4m}{\Lambda}$. Note that ${\cal F}^{N_{f}=1}_{k}$ in this
Table is related to ${\cal F}^{1}_{k}$ in Appendix D of Ohta  as ${\cal
F}^{1}_{k}=-\frac{1}{2}\Lambda^{2k}{\cal F}^{N_{f}=1}_{k}$(here),
$\Lambda_{1}=\Lambda$(here).

In this paper, we have shown that, in both $N_{f}=0$ and $1$ cases, $q$ is
expanded by $A^{2}$ whose coefficients are integer-coefficient polynomials of
$a_{i}$’s (as well as $\hat{m}$ for $N_{f}=1$) if $A\propto a^{-1}$ is
appropriately defined. As a result, the coefficients of the instanton
expansion of the prepotential are expressed as rational-coefficient
polynomials of the “moonshine coefficients” $a_{i}$’s (as well as $\hat{m}$
for $N_{f}=1$) as shown in Tables 1 and 2. We expect a similar relationship to
hold for $N_{f}=2$ and $3$, and perhaps even for E-string theory.

From these tables, we can see that in both cases the polynomials contain
“inhomogeneous terms”, that is, the terms that remain after all $a_{i}$’s are
set to $0$. Of course, these numbers are not arbitrarily determined, but are
determined by the given SW curves. In fact, setting all $a_{i}$’s to $0$ in
(1) amounts to approximating $j(\tau)$ by $\frac{1}{q}$. Since

$\displaystyle
j(\tau)=\left(\frac{\vartheta_{3}^{8}+\vartheta_{4}^{8}+\vartheta_{2}^{8}}{2\eta^{8}}\right)^{3},$
(27)

this implies that the whole affine $E_{8}$ character is replaced solely by the
contribution of the ground state. Thus we may conclude that these inhomogenous
terms represent information on the ground state of the moonshine module.

We note that something similar occurs with the asymptotic behavior of the
Atiyah-Hitchin (AH) metric, where the similar replacements
$\vartheta_{3}\rightarrow 1$, $\vartheta_{4}\rightarrow 1$,
$\vartheta_{2}\rightarrow 0$ and $\eta\rightarrow q^{\frac{1}{24}}$ lead to
the Taub-NUT metric with a negative NUT charge AH . The AH space is known to
be the moduli space of $D=3$ ${\cal N}=2$ $SU(2)$ SUSY gauge theory SWD=3 ,
and the instanton corrections resolves the singularity of the negative-charge
Taub-NUT. Since the Taub-NUT space is the transverse space of the M-theory
lift of a D6-brane and the AH-space corresponds to an O6-plane, our results in
the present analysis may be considered to show the corresponding facts in the
D7/O7 system.

The results in Tables 1 and 2 also show that the coefficients of the
polynomials of $a_{i}$’s contain large integers (unlike the moonshine). Since
each term of the instanton expansion of the prepotential is known to be
expressed as a $c=25$ Liouville correlation function AGT , while the moonshine
module is a $\hbox{\mybb Z}_{2}$ orbifold of $c=24$ vertex operator algebra
CFT DGH , we suspect that these mysterious large numbers may be interpreted as
a contribution coming from the missing $c=1$ CFT.

The author thanks Kazunobu Maruyoshi, Sota Nakajima, Kazuhiro Sakai and Taro
Tani for valuable discussions.

## References

  * (1) N. Seiberg and E. Witten, Nucl. Phys. B 426 (1994) 19 [Erratum-ibid. B 430 (1994) 485] [arXiv:hep-th/9407087].
  * (2) N. Seiberg and E. Witten, Nucl. Phys. B 431 (1994) 484 [hep-th/9408099].
  * (3) Y. Tachikawa, “N=2 supersymmetric dynamics for pedestrians,” [arXiv:1312.2684 [hep-th]].
  * (4) N. Nekrasov and A. Okounkov, Prog. Math. 244, 525-596 (2006) [arXiv:hep-th/0306238 [hep-th]].
  * (5) E. Witten, Nucl. Phys. B 500, 3-42 (1997) [arXiv:hep-th/9703166 [hep-th]].
D. Gaiotto, JHEP 08, 034 (2012) [arXiv:0904.2715 [hep-th]].

  * (6) A. Sen, Nucl. Phys. B 475, 562-578 (1996) [arXiv:hep-th/9605150 [hep-th]].
O. DeWolfe, A. Hanany, A. Iqbal and E. Katz, JHEP 03, 006 (1999) [arXiv:hep-
th/9902179 [hep-th]].
Y. Yamada and S. K. Yang, Nucl. Phys. B 566, 642 (2000) [hep-th/9907134].

  * (7) W. Lerche, P. Mayr and N. P. Warner, Nucl. Phys. B 499, 125-148 (1997) [arXiv:hep-th/9612085 [hep-th]].
J. A. Minahan, D. Nemeschansky and N. P. Warner, Nucl. Phys. B 508, 64-106
(1997) [arXiv:hep-th/9705237 [hep-th]].
T. Eguchi and K. Sakai, JHEP 05, 058 (2002) [arXiv:hep-th/0203025 [hep-th]].
T. Eguchi and K. Sakai, Adv. Theor. Math. Phys. 7, no.3, 419-455 (2003)
[arXiv:hep-th/0211213 [hep-th]].

  * (8) L. F. Alday, D. Gaiotto and Y. Tachikawa, Lett. Math. Phys. 91, 167 (2010) [arXiv:0906.3219 [hep-th]].
  * (9) R. Dijkgraaf and C. Vafa, Nucl. Phys. B 644, 21-39 (2002) [arXiv:hep-th/0207106 [hep-th]].
R. Dijkgraaf and C. Vafa, arXiv:0909.2453 [hep-th].
A. Mironov and A. Morozov, Phys. Lett. B 680, 188 (2009) [arXiv:0908.2190
[hep-th]].
H. Itoyama, K. Maruyoshi and T. Oota, Prog. Theor. Phys. 123, 957 (2010)
[arXiv:0911.4244 [hep-th]].
T. Eguchi and K. Maruyoshi, JHEP 1002, 022 (2010) [arXiv:0911.4797 [hep-th]].

  * (10) J. H. Conway and S. P. Norton, Bull. London Math. Soc. 11, no.3, 308-339 (1979).
  * (11) J. McKay and Y. H. He, ICCM Not. 10, no.1, 71-88 (2022) [arXiv:2106.01162 [math.HO]].
  * (12) I. B. Frenkel, J. Lepowsky and A. Meurman, Proc. Natl. Acad. Sci. U.S.A. 81 (1984) 32566.
I. B. Frenkel, J. Lepowsky and A. Meurman, in “Vertex Operators in Mathematics
and Physics,” Springer-Verlag, New York (1985) 231.

  * (13) L. J. Dixon, P. H. Ginsparg and J. A. Harvey, Commun. Math. Phys. 119, 221-241 (1988).
  * (14) A. Hanany and Y. Oz, Nucl. Phys. B 452, 283-312 (1995) [arXiv:hep-th/9505075 [hep-th]].
  * (15) A. Klemm, W. Lerche and S. Theisen, Int. J. Mod. Phys. A 11, 1929-1974 (1996) [arXiv:hep-th/9505150 [hep-th]].
  * (16) T. Masuda and H. Suzuki, Int. J. Mod. Phys. A 12, 3413-3431 (1997) [arXiv:hep-th/9609066 [hep-th]].
  * (17) Y. Ohta, J. Math. Phys. 37, 6074-6085 (1996) [arXiv:hep-th/9604051 [hep-th]].
  * (18) M. F. Atiyah and N. J. Hitchin, “The Geometry And Dynamics Of Magnetic Monopoles. M. B. Porter Lectures.” Princeton University Press (1988).
G. W. Gibbons and N. S. Manton, Nucl. Phys. B 274, 183 (1986).
E. J. Weinberg and P. Yi, Phys. Rept. 438, 65 (2007) [arXiv:hep-th/0609055].
H. Imazato, S. Mizoguchi and M. Yata, Int. J. Mod. Phys. A 26, 5143-5169
(2011) [arXiv:1107.3557 [hep-th]].

  * (19) N. Seiberg and E. Witten, “Gauge dynamics and compactification to three-dimensions,” [arXiv:hep-th/9607163 [hep-th]].