# NUMAscope: Capturing and Visualizing Hardware Metrics on Large ccNUMA
Systems

Daniel J Blueman  Principal Software Engineer
Numascale AS
Oslo, Norway
<EMAIL_ADDRESS>Foivos Zakkak  Department of Computer Science
The University of Manchester
Manchester, United Kingdom
<EMAIL_ADDRESS>Christos Kotselidis  Department of Computer
Science
The University of Manchester
Manchester, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

Cache-coherent non-uniform memory access (ccNUMA) systems enable parallel
applications to scale-up to thousands of cores and many terabytes of main
memory. However, since remote accesses come at an increased cost, extra
measures are necessitated to scale the applications to high core-counts and
process far greater amounts of data than a typical server can hold. In a
similar manner to how applications are optimized to improve cache utilization,
applications also need to be optimized to improve data-locality on ccNUMA
systems to use larger topologies effectively. The first step to optimizing an
application is to understand what slows it down. Consequently, profiling
tools, or manual instrumentation, are necessary to achieve this. When
optimizing applications on large ccNUMA systems, however, there are limited
mechanisms to capture and present actionable telemetry. This is partially
driven by the proprietary nature of such interconnects, but also by the lack
of development of a common and accessible (read open-source) framework that
developers or vendors can leverage.

In this paper, we present an open-source, extensible framework that captures
high-rate on-chip events with low overhead (<10% single-core utilization). The
presented framework can operate in live or record mode, allowing both real-
time monitoring or capture for later post-workload or offline analysis. High-
resolution visualization is available either through a standards-based (web)
interactive graphical interface or through a convenient textual interface for
quick-look analysis.

###### Index Terms:

performance, architecture, monitoring, profiling, cache coherency

##  I Introduction

Cache-coherent non-uniform memory access (ccNUMA) architectures enable
applications to scale up to hundreds of cores and terabytes of memory without
the need of explicit synchronization or communication between the different
boards of the system. ccNUMA systems essentially provide a single system image
(SSI) to the software, abstracting away the memory hierarchy and thus easing
development. To achieve this, ccNUMA systems rely on cache-coherent
interconnects and memory-coherence protocols. This approach however may come
at a cost if applications do not account for the overheads of remote accesses
on a ccNUMA system.

Although memory-coherence is implemented in hardware and is transparent to the
software, it comes with overhead which need to be taken into account when
optimizing an application; the memory hierarchy is such that main memory
access time differs depending on the memory segment being accessed and the
core that performs the access. Figure 1 demonstrates how distant memory
accesses relate to the latencies of accessing different levels of the memory
hierarchy. As a result in a similar way that parallel applications should
avoid cache line sharing (so as to avoid excessive coherence traffic), they
should minimize writing cache lines frequently read among many NUMA nodes [1].

Figure 1: Latency of memory accesses depending on the distance between the
core performing the access and the memory being accessed

The first step in avoiding high latency accesses is to quantify them by
inspecting the system’s performance counters. However, when developing and
tuning software applications on systems large enough to warrant cache-coherent
interconnects, existing mechanisms to collect resource usage are limited to
the system’s core and uncore performance counters. For instance, existing
NUMA-aware profilers can attribute increased wait cycles to last level cache
(LLC) misses and even help developers understand whether those misses are
served by the local or remote NUMA-node. They fail to give any further insight
regarding the remote NUMA-nodes that are on a different board.

Furthermore, when developing cache-coherent interconnects outside a simulation
environment, there are no universal mechanisms available to capture
interconnect resource utilization. Consequently, high-rate capture of fine-
grained on-chip interconnect counters would present useful telemetry both to
guide interconnect and application development and tuning. As an example of
the first case, on-chip buffering is generally expensive; understanding how
much buffering is needed to cover the interconnect round-trip for optimal
throughput with appropriate counters, would allow allocation of just enough
resources. This mismatch occurs since relatively crude activity patterns can
be simulated in chip development, and latency isn’t modeled at all, with many
approximations for simulation speed. In the latter case, the impact of
algorithmic adjustments can be understood at a cache-coherent and high-level
ccNUMA viewpoint.

In this paper, we demonstrate the lightweight capture of very high-rate on-
chip events (up to $2\text{\times}{10}^{8}$ events per second), and
visualization in an interactive graphing environment, along with a convenient
textual interface for quick-look analysis. We present NUMAscope, a framework
that enables tools that capture events across different cache-coherent
interconnects in large ccNUMA systems. NUMAscope is open-source and based on a
modular software architecture, that makes it easily extendable. NUMAscope not
only enables the user to see at a high-level and quantify suboptimal
application (or the system as a whole) behavior, but it also enables
identification of why it is occurring, from the system’s perspective, e.g.
because some buffer queues are full. This information enables the observer to
understand whether a high rate of events observed using the tool also happens
to saturate some hardware resource, potentially leading to different
scheduling decisions or even different hardware configurations.

In detail, in this paper we make the following contributions:

  * •

We introduce NUMAscope, a framework that enables tools that perform real-time
and postmortem monitoring of cache-coherent interconnects, using a mechanism
for high-rate event capture; NUMAscope provides both a graphical and a textual
interface that visualize the captured events.

  * •

We present how using NUMAscope, we were able to detect a performance issue in
the GNU C Compiler 4.8.5 OpenMP implementation and compare its performance
before and after applying a fix.

  * •

We evaluate NUMAscope, on a 6-board ccNUMA system, using the NAS Parallel
Benchmarks (NPB) [2] EP benchmark, reporting its overhead for various sample
rates, starting from a high sample rate at 1000Hz and going down to 1Hz; our
evaluation shows that the overhead ranges from 0.27% at 1Hz sampling, to 5% at
1000Hz sampling.

##  II Related Work

###  II-A Hardware Counters Access

Various tools and libraries that enable gathering metrics from hardware
counters are readily available [3, 4, 5]. However these tools and libraries
are typically able to gather metrics only within a single board, failing to
support large ccNUMA systems. Furthermore, to get access to NUMA-related
metrics, e.g. number of remote accesses, the tools rely on processor-specific
events that users need to pass as parameters to the tool. Identifying and
understanding the events that are of interest is not trivial; it requires
careful studying of the architecture’s manual and understanding of the
architecture itself [6, §3]. To make matters worse, stable OS distributions
(e.g. CentOS) usually ship with older kernel versions. As a result, perf, the
most popular profiling tool shipped with Linux, usually lacks support for the
performance counters added to newer processors. For Intel processors PMU-tools
[7] have been developed to mitigate this issue. NUMAscope compared to perf is
more easily extendable and does not rely on the latest kernel to work, nor on
kernel patches to extend it. NUMAscope can also take advantage of the
community support for those tools and libraries and use them for gathering
metrics.

###  II-B Gathering Metrics About ccNUMA-interconnects

Prior work has also focused on gathering micro-architectural events from
ccNUMA interconnects [8, 9]. Both these works focus, each, on a single
proprietary hardware interconnect and are closed-source. NUMAscope, in
contrast to these approaches [8, 9], is open-source and designed to be modular
in order to support different hardware interconnects by implementing a simple
software interface.

###  II-C System Monitoring Tools

NUMAscope being able to monitor large ccNUMA systems is also related to system
monitoring tools. Most system monitoring tools focus on higher-level metrics
such as processor, disk, and network usage [10], as well as even higher-level
metrics including service availability. NUMAscope, providing lower-level
metrics, can complement such tools aiding developers to understand the root-
cause of deficiencies in their system.

###  II-D Profiling Tools

By using instruction-based and event-based sampling, prior works have also
built profiling tools that are able to correlate code segments with NUMA-
related events [11, 6, 12, 13, 14]. The main goal of these profilers is to
help developers detect bottlenecks in their applications, caused by cache
hierarchy effects. However, these tools rely on processor core counters and
lack support for large ccNUMA systems. As a result, profiling applications on
large ccNUMA systems gives limited insight into what is happening outside a
single board. Existing NUMA-aware profilers can only tell whether an LLC miss
is served by the local NUMA-node or a remote one, with lack of insight
regarding accesses to remote NUMA-nodes that are on different boards. Such
information is valuable, since different boards may have different
utilization, and a holistic view often aids in optimizing imbalanced
workloads. NUMAscope can be used in conjunction with such tools to determine
the source of excessive memory access time; that would occur when the cycle
misses in the local last level cache and the physical address corresponds to a
remote NUMA-node. Without NUMAscope, core profiling would simply reveal a
memory load taking significantly longer.

PMU-tools also feature the toplev tool that implements the top-down method
[15]. The top-down method groups performance counters to help developers
identify which part of the processor, e.g. front-end, back-end, etc. is being
stressed by their application and find potential bottlenecks. NUMAscope and
measurements obtained from the ccNUMA interconnects can be used to extend the
top-down methodology, and more specifically the External Memory Bound group.

Overall, NUMAscope differentiates itself from related work by: a) capturing
more diverse events and data, b) being easily extendable, enabling the
profiling of different platforms, c) being a framework that enables the
creation of specialized monitoring tools on a per case base, and d) being
open-source and readily available to the community. Furthermore, NUMAscope can
be used to complement existing NUMA-aware profiling tools as well as system
monitoring tools to aid developers trace the root cause of potential
deficiencies in their applications and deployments by exposing low-level
metrics obtained from ccNUMA-interconnects.

##  III Background

In this Section we shortly discuss large ccNUMA systems, the importance and
the role of ccNUMA interconnects, how they affect performance, and the
challenges in profiling applications on systems using them.

###  III-A Large ccNUMA Systems

Figure 2: An illustration of a ccNUMA system

Figure 2 illustrates the layout of a large ccNUMA system which consists of a
number of boards or discrete servers; sometimes also called nodes (4 in the
illustration). In general, by large ccNUMA systems we refer to systems larger
than what the processor natively supports without a cache-coherent NUMA
interconnect (see Section III-B). . Each board typically comprises 2–4
processor sockets (2 in the illustration) and a number of NUMA-nodes (4 in the
illustration). Each socket comprises a number of cores and hardware threads (4
and 8 respectively in the illustration). Typically each hardware thread has
it’s own level 1 cache and might share higher level caches with other hardware
threads on the same chip. As we move to higher levels in the cache hierarchy,
the communication means changes along with the access times (see Figure 1).
Additionally, each processing unit in a NUMA-node has fast access to the local
memory of its NUMA-node, while it can still access the rest of the system’s
memory with varying latency depending on the remote memory location (see
Figure 1).

###  III-B Cache-coherent NUMA interconnects

For processors to be optimized for maximum efficiency, they need a common
upper limit on the number of sockets they support. This dictates how many bits
are allocated to each entry in a cache directory, to track location and state
of cached lines. This is typically 8 NUMA-nodes (3 bits per cache line) [16,
17]. In addition, in some AMD processors an optimization called HT Assist
reserves a fixed amount of the level 3 cache as a cache directory, which
tracks which NUMA-node holds what cache line in what state [18]. In the AMD
Opteron 6000 series the reserved, by HT Assist, space amounts to 2MB out of
the 8MB of level 3 cache. Intel processors have a similar amount of level 3
cache partitioned when in multiprocessor mode.

When there is access to a cache line not tracked in the processor’s cache
directory, an eviction may have to occur to first invalidate a selected cache
line to make space for a new entry. Since it is not known which cache holds
state for the newly-tracked cache line, a probe broadcast must be sent to all
NUMA-nodes. As the number of NUMA-nodes in a system increases, this broadcast
incurs an increasing overhead, reducing application scaling [19].

In large ccNUMA systems that span multiple boards, cache-coherent NUMA
interconnects are used to deliver the guarantees of coherency across the whole
system. ccNUMA interconnects overcome the above limitations by being optimized
for a considerably larger working set. This is achieved by tracking many more
cache lines and acting as a filter, able to respond to the processor with
directed probe responses. This improves scalability, and allows
interconnecting multiple smaller (e.g. 2–4 NUMA-node) topologies to offer more
processing.

ccNUMA interconnects are typically integrated onto the motherboard, or off-
board in a midplane that connects to the processor fabric. This results in
higher access times, compared to intra-board access times, yet significantly
lower than accessing storage. In addition to the cost of visiting a remote
memory due to the longer distance and the slower links in the network, the
number of cocurrent remote accesses that is supported by the interconnect can
also constrain the performance of the system. If the outstanding remote
accesses are less than the processor can generate, applications running on
ccNUMA systems may observe increased cache-coherency imposed overheads if not
carefully tuned.

###  III-C On-chip counters

On-chip counters are provided by chip designers to aid software developers to
debug and optimize their applications. These counters offer measurements
regarding the events occurring on different hardware modules, such as caches,
branch predictors and hardware prefetchers. For instance, on-chip counters can
measure the number of last-level cache misses which indicates the number of
memory accesses that end up going off-chip and thus result in higher latency.
Similarly, ccNUMA interconnects offer a variety of on-chip counters that count
events specific to the interconnect, such as the number of outstanding remote
accesses, the interconnect traffic, etc. This provides useful feedback to
application developers that execute their application at larger scales than
previously accessible, for example compared to a dual-socket development
system. On-chip counters may also drive configuration changes in the OS, BIOS
and/or firmware in the interconnect after the chip is finalized. Additionally,
they provide crucial feedback to the interconnect developers on how on-chip
resources should be allocated in future products.

###  III-D Challenges

As discussed in Sections III-A and III-B, minimizing remote accesses is
important for improving performance. Additionally, as discussed in Section
III-B it is also important to understand resource utilization in ccNUMA
interconnects so as to understand if it presents a bottleneck to the workload
and how this could be reduced.

The most common mechanism of accessing on-chip counters is to access
registers, directly or indirectly mapped into the application’s address space.
Access cycles are generated against this mapping which decode to one of the
interconnect chips. Since there are many interconnect chips within the same
logical system, the physical address space must have space reserved for access
to all chips. Since the cache-coherent interconnects in large ccNUMA systems
are proprietary, there are no standard register layouts, data formats, or even
list of counters. Any tool that implements such accesses is driven by
underlying implementation and design-specific details. As such, it is up to
each vendor to develop an interface, documentation, or write a specific tool
to access these internal counters. Finally, it is worth noting that outside
the processor cores, physical addresses are always used, preventing
understanding where DRAM accesses relate to.

In summary the challenges in profiling applications on large ccNUMA systems
are: a) getting access to all the on-chip counters, both from each board and
the interconnects; b) interpreting and normalizing the samples per unit time
and clock frequency; c) doing the above without imposing significant overhead;
d) exposing a way of capturing the data; and e) allowing useful mining and
interaction with the collected data, e.g. visually. Our work tackles these
challenges and provides a framework that eases the creation of tools able to
monitor large ccNUMA systems.

##  IV NUMAscope

NUMAscope is a framework that enables the creation of tools that gather and
visualize hardware events from different modules on large ccNUMA systems. To
enable extensibility, NUMAscope has been designed in a modular way, decoupling
operating modes, subsystems and capturing of hardware interfaces’ metrics,
though doesn’t need any kernel support. Figure 3 illustrates the software
architecture at a high-level. As shown, NUMAscope comprises five modules.

The core module is called the events module, responsible for capturing
hardware and software events through sampling. The rest of the modules are
optional depending on the usage. In a typical session, users would first
decide if they want to record the data for later analysis or not. If so, the
record mode would be used. Inspired by the usefulness of the UNIX vmstat
command, NUMAscope offers the stat mode which outputs the selected events to
the terminal, allowing the users to readily observe selected metrics. Finally,
the live mode can be used to start a web server to allow interactive graphing
of the data in real-time. The storage module is responsible for storing the
captured events when using the record mode. The CLI renderer module is
responsible for formatting the captured events on the command line when using
the stat mode. The web server module is responsible for interacting with the
HTML5 client with data in real-time when using the live mode. Finally, the
HTML5 client front-end is responsible for providing an interactive graphical
interface to visualize in real time the data transmitted by the webserver
module, or to visualize the data previously captured in record mode. In the
rest of this section, we further discuss each of these modules in more detail.

Figure 3: High-level architecture of NUMAscope

###  IV-A Events module: High-rate event capture

By design, in NUMAscope, event capture is a hot path, wherein all state has
been setup to allow reading event counters. NUMAscope can be extended to
support a variety of events, either from software or hardware. Out of the box,
NUMAscope is capable of capturing kernel virtual-memory events, which are not
exposed via standard UNIX tools, such as iostat, sar, vmstat and related, or
Linux-specific ones such as perf. These events aid in the identification of
additional overhead when the executing process needs to conduct work in the
kernel to take some action; for example, when accessing a page not yet faulted
in from a file, or reclaiming pages to satisfy an allocation. The kernel
outputs the event counters in a structured way when reading /proc/vmstat.
NUMAscope parses the structured text, using one lseek and one read systemcall,
and stores names and values in a dynamic hashtable to allow for $O(1)$ lookup.
When running in live mode with one HTTP client, NUMAscope’s memory footprint
is about 14MiB of pages, 5MiB of which is shared libraries.

####  IV-A1 Data Biasing and Interference

To avoid interfering with applications, NUMAscope pins its threads to the
first NUMA-node. NUMAscope uses a thread-pool to handle asynchronous events.
When running in live mode with one HTTP client, NUMAscope uses 20 threads
irrespective of what events are enabled or modules used. To avoid data-races,
mutexes are used to ensure one thread doesn’t request access while another
thread is changing state of the events. Additionally, to avoid affecting the
counters relating to coherent accesses, all accesses performed by NUMAscope to
remote interconnects for counter collection are only non-coherent register
access; this therefore doesn’t evict data in the cache hierarchy. The rate of
non-coherent requests is therefore in the order of thousands per second. The
volume of remote non-coherent accesses running can be quantified by examining
the metric packets with less than a full cache line sent; that is because IO
accesses to registers are always 32-bit. During benchmarking, NUMAscope
records a rate of $1.90\text{\times}{10}^{5}$ per second as compared to
millions of cache-coherent cycles per second, therefore the bias is
insignificant and approaching the noise threshold.

Listing 1: NUMAscope’s interface for adding hardware support

⬇

type Sensor interface {

// human-readable name of hardware

Name() string

// checks if hardware is present

Present() bool

// maximum sample value for percentages

Rate() uint

// number of hardware elements detected

Sources() uint

// supported events

Events() []Event

// activated enabled events

Enable(discrete bool)

// gets names of enabled events

Headings(mnemonic bool) []string

// returns samples

Sample() []int64

// used to prevent hardware access races

Lock()

Unlock()

}

####  IV-A2 The Sensor Interface

Regarding accessing hardware counters provided by chip developers, NUMAscope
relies on the Sensor interface listed in Listing 1 to get access to them.
Hardware counters may be platform specific, so there is no way to make
NUMAscope able to access the counters of all potential hardware platforms
without some form of extension. Since the design of NUMAscope is intentionally
modular, adding support for new hardware counters is achieved by adding a new
sub-module to NUMAscope’s events module that implements the given interface
for each target hardware platform.

Name() simply returns a human-readable description of the sensor, used in the
user interface. Present() is used to check whether the Sensor is supported on
the platform NUMAscope is running on. If present, it also gets set up, which
typically involves the memory-mapping of the corresponding hardware registers
into the process address space. Rate() returns the maximum number of events
per second, used to normalize counter rates to percentages. Sources() returns
the number of hardware elements detected and set up by Present(). Events()
returns an array of Events supported by the Sensor, for example cycles during
the sampling window and number of cache lines of data moved. Enable() updates
internal state to activate the events to be sampled. The boolean parameter
passed to it indicates whether NUMAscope should sample events per-board or sum
over all boards, to increase the brevity of the CLI renderer, or the amount of
data transmitted over websockets. Headings() returns either short event
mnemonics or full descriptions useful to the developer, based on the value of
the boolean parameter passed to it. Full descriptions aim to help developers
in selecting which events to capture. Sample() reads out the enabled Sensor
events, subtracting from the state held by the previous call to get a rate
over time, and returns a slice of the enabled event rates. Signed 64-bit
integers are used, since certain events can legitimately have a negative rate.
For example kernel virtual memory swapped-pages count will increase with VM
pressure, giving a positive rate, and decrease when swapped pages are read
back in, giving a negative rate.

####  IV-A3 Controlling NUMAscope Dynamically

The events module, can also be programmatically controlled by writing commands
into a UNIX FIFO at /run/numascope-ctl. This enables controlling NUMAscope
with ease from both shell scripts and programs themselves for finer-grained
profiling. The commands currently supported by NUMAscope are:

  1. 1.

record <filename> closes any existing recording file and starts recording to
given filename,

  2. 2.

label <string> inserts a label onto the graph or textual output to mark a
notable event for later analysis,

  3. 3.

pause suspends recording events without suspending capturing,

  4. 4.

resume continues recording events, and

  5. 5.

interval <number>ms adjusts the sampling rate of sensors in milliseconds.

.

###  IV-B Storage module: Storing data for offline analysis

Since data may be stored and used even years after gathering them [20], using
a simple and flexible but standards-compliant data storage format has very
strong rationale. As such, both CSV and JSON serve the purpose well, since
they are mature and well-supported by many frameworks and tools. Furthermore,
both formats are not dependent on additional information such as a schema as
may be expected with XML. JSON has three major advantages over CSV though.
Firstly, it can encode structured data, which may be advantageous if the
framework is expanded in the future. Secondly, it is native to JavaScript, so
has highly optimized support without requiring external JavaScript libraries.
Finally, this allows it to be consumed directly by graphing frameworks. In
order to avoid making disk IO a bottleneck, the storage module writes samples
in a buffer which is periodically flushed to disk by the OS; on Linux, this is
every 30 seconds. Sampling at 10Hz, 28KiB of JSON test are stored per second.

Due to the modular approach taken, additional storage modules may be developed
to send the data to other storage mechanisms or databases, such as InfluxDB,
TimescaleDB, or Apache Cassandra.

###  IV-C CLI renderer: Command-line data presentation

The stat mode of NUMAscope outputs the selected events to the terminal,
allowing the users to readily observe selected metrics, or pipe the output and
process it on-the-fly. The CLI also enables easy monitoring of remote systems
without any external dependencies. Listing 2 shows a snapshot of NUMAscope’s
CLI in action. In this snapshot, we see three interconnect events being
monitored; n2DirPrbRecv, n2CachelinesSent, and n2CacheRolloutRmpe. Each line
prints the values obtained by a single sample. Over time new lines are printed
with the latest samples. In this example, we observe how many cacheline probes
(snoops) and cache lines are sent over the interconnect per second, and how
many level-4 (internal to the interconnect) cache line evictions or rollouts
occurred per second; this it useful to see how much remote activity the
workload is generating to understand how the working set interacts with the
level-4 cache

Listing 2: Snapshot of NUMAscope’s CLI

⬇

$ numascope stat

n2DirPrbRecv n2CachelinesSent n2CacheRolloutRmpe ...

41 7357 6689 ...

103 21357 19092 ...

11560 115101 78575 ...

258872 944292 72099 ...

387750 598625 6843 ...

375612 583840 8220 ...

###  IV-D web server module: Live data streaming for interactive graphing

NUMAscope provides a standalone graphical interface, directly served via the
built-in HTTP web server to allow immediate live updates to be observed.
Additionally to HTTP webserving, data is exposed to clients via websockets, on
top of which runs a simple yet custom protocol. This way, two-way interaction
between clients and the web server is possible, overcoming the one way
limitation with HTTP. One example where this is useful, is given multiple live
sessions capturing data from NUMAscope, to control options that are global to
all clients. This is chiefly the rate at which NUMAscope latches the on-chip
counters and reads them out. Since these can’t be interpolated, all clients
must use the same sample interval. Websockets allow the client to send data
back to the web server, which in turn informs all clients of a configuration
change. Since events can be captured at a higher rate than the network round-
trip would easily accommodate when in live mode, events are batched and sent
down all client websockets at 400 millisecond intervals; this is a good trade-
off of network and processing overhead, particularly as the client which needs
to re-render graph traces frequently.

###  IV-E HTML5 client: Interactive graphing of data

For the interactive visualization of the measurements, NUMAscope offers a
graphical user interface (GUI) realized through web technologies. Given the
ubiquity of web technologies, how standardized and optimized they are today,
developing a native client application would present comparatively an
intractable engineering and support burden. Since the rate of events is
graphed, the cycles counter is used to measure the time period that sampling
was running; the values are divided by the time period to get an accurate rate
over the unit of time. This data is transferred either via websocket or JSON
file, and optionally reducd over all the boards to conserve bandwidth or
space. Finally, it is passed to the graphing framework, which renders the
graph traces.

Figure 4: Screenshot of NUMAscope’s GUI

Figure 4 shows a screenshot from NUMAscope’s GUI in action. At the top of the
interface there is a panel with controls allowing the user to adjust the
visualization of the data. The user may control the recording of the data, the
sampling rate, and the visualization itself. Additionally, there is a load
button for loading data from a file instead of the web server. Directly below
the control pane, there is an interactive plot visualizing the gathered events
in a time-series. The typical representation of such time-series data is by
using one or more line graphs. The interactive plot allows the user to select
which events to be visualized, to focus on a specific time window, and even
see the exact value of an event by hovering over the corresponding line on the
plot. Finally, the user can toggle the visibility of traces in the graph by
clicking them in the legend.

##  V Evaluation

To evaluate NUMAscope, we deploy it on a 6-board, 18-socket AMD Opteron system
with 6 ccNUMA interconnects and use the Embarrassingly Parallel (EP) benchmark
from the NASA Parallel Benchmark (NPB) suite [2] to:

  1. 1.

Demonstrate how NUMAscope helped us find a performance deficiency in GNU C
compiler’s (GCC) OpenMP implementation.

  2. 2.

Assess the overhead imposed by NUMAscope.

(a) NUMA, one board

(b) Interconnect, all boards

Figure 5: Topology at different levels

Each board on the system comprises three AMD Opteron 6328 processors, each
featuring 8 cores. The NUMA topology is shown in Figure 5a. The boards are
connected using Numascale’s NumaConnect2 cache-coherent interconnect, in a
point-to-point configuration for single-hop latency, as shown in Figure 5b.
The links between the NUMA-nodes in the processors supports 6.4GT/s (Giga
Transfers) peak throughput; the links between the processors and interconnect
supports 3.2GT/s. Table I summarizes the hardware and software configuration
of the evaluation platform.

TABLE I: Hardware and Software Configuration CPUs | 18 (3 per board) AMD Opteron 6328
---|---
NUMA-nodes | 36 (6$\times$6 per board)
Memory | 2304GiB (384GiB$\times$6 per board)
Boards | 6
CC-interconnect | NumaConnect2
OS | CentOS 7.6
Linux Kernel | 4.14.146-NUMASCALE [21]
GCC | 4.8.5 (w/ and w/o patch)

In our benchmarking, we use thread pinning to minimize non-determinism so
results are stable and repeatable, and to prevent the kernel scheduler from
waking threads up in different areas of the cache hierarchy. Part of the
reason the latter occurs, is from the increased clock jitter due to different
boards in the larger ccNUMA system that are driven by different on-board
clocks. One strategy to partially mitigate this is to boot Linux with the
relax_domain parameter set to 3 [22]; this restricts the kernel’s process
scheduler to limit the search for an unused core to a particular level in the
hierarchy (a super-set of the NUMA hierarchy). To pin the application threads
linearly to the core numbers with OpenMP, the environment variable
OMP_PIN_THREADS is set to TRUE. Since the evaluation is performed on a
dedicated system, in conjunction with thread pinning, the only measurement
noise comes from OS housekeeping activities.

###  V-A Numascale NumaConnect2 support

The Numascale NumaConnect2 ccNUMA interconnect allows interconnecting multiple
AMD Opteron 6300 processor boards, providing a level-4 cache and full
directory to reduce global traffic. It allows point-to-point, 3D torus or
arbitrary fabric topology which it load-balances over, using open-source
firmware [23]. NumaConnect2 lists all the types of cycles entering and leaving
the card, and has counters at most interfaces between functional blocks to
accrue how many clock cycles were consumed by waiting. This includes cache
line probes, cache line transfers, IO transfers, as well as level-4 cache
hits, misses, evictions and time spent waiting for resources internally in the
interconnect. To expose to NUMAscope the hardware events gathered by
NumaConnect2 we implement the Sensor interface described in Section IV-A as a
new submodule.

The NumaConnect2 counters profiled by NUMAscope fall into two categories.
Firstly, extrinsic events, which include the types of traffic going into the
NumaConnect2 from both the processor and interconnect fabric sides.
Understanding this traffic may reveal if an application is exploiting or
thrashing the cache hierarchy, which is useful in algorithm design and
application tuning. Workloads thrashing the cache hierarchy would result in
considerably more access over the interconnect, for example random access to a
working set somewhat larger than the caches. Applications exploiting the cache
hierarchy would generate considerably less activity on the interconnect either
by accessing a working set that fits in the caches, or by accessing local
data. Secondly, the intrinsic events which includes internal resource usage,
or counting cycles for which a request is stalled waiting for resources. This
helps understand if and when bottlenecks occur in the interconnect.

###  V-B Workloads and metrics

The NASA Parallel Benchmarks [2] present a range of numerical problems with
varying characteristics. Additionally, varying problem sizes can be configured
and the number of threads of execution can be arbitrarily specified, so as to
make full use of resources.

Using the NPB EP benchmark allows us a means to validate NUMAscope. The EP
class D benchmark generates $2\text{\times}{10}^{36}$ pairs of pseudorandom
numbers with a Gaussian distribution in a 1.1GiB distributed memory array. In
this paper, we analyze the amount of time the interconnect is waiting for
internal resources.

From a whole-system perspective, it would be intuitive to measure the number
of remote outstanding transactions at the interconnect. Since this is limited
in hardware to 16, we can not get insight into the end-to-end queuing
occurring from the processor cores to the remote DRAM. Instead, a linear
measure of queuing is “wait cycles for requests from SIU to RMPE”; this
measures the number of clock cycles spent for cache-coherent requests
traveling from the NumaConnect2 Scalable Coherent Interface (SCI) Interface
Unit to the Remote Memory Processing Engine; this shows exactly how long
memory access was stalled because the interconnect was busy.

(a) Without stack fix

(b) With stack fix [24]

Figure 6: NPB EP class D pinned OpenMP wait cycles

###  V-C GCC’s OpenMP implementation deficiency

During execution of the NASA Parallel benchmarks, we observed using NUMAscope,
that the benchmarks were causing an unexpectedly high number of cycles waiting
for resources in the interconnect, even with the NPB Embarrassingly Parallel
(EP) benchmark. As implied by its name, the EP benchmark has no data
dependencies among parallel threads, so minimal communication is expected to
take place, and memory accesses should be mostly local or cached. Figure 6a
plots, on the y-axis, the number of cache-lines transferred over the
interconnects (blue line), along with the percentage of the “wait cycles for
requests from SIU to RMPE” over the theoretical maximum of the system (brown
line); the x-axis is time in seconds. Given the 200MHz core clock speed of
NumaConnect2 the maximum number of “wait cycles for requests from SIU to RMPE”
that can be observed is $0.2\text{\times}{10}^{9}$ per interconnect. To
calculate the plotted percentage we use the following equation:

$100\times\sum_{n=1}^{\\#interconnects}\frac{\mathrm{wait\\_cycles}_{n}}{0.2e9}$
(1)

where $\mathrm{wait\\_cycles}_{n}$ is the “wait cycles for requests from SIU
to RMPE” measurement obtained from interconnect $n$. As shown in Figure 6a,
there is a constant rate of about 99% (out of the maximum 600%) of the total
number of clock cycles spent waiting for resources across all six boards. This
observation suggests that one of the six interconnects is acting as the
bottleneck, at constant saturation.

Disabling the grouping of the boards in the user interface, we reveal the wait
cycles per board, as shown in Figure 7. In a well-balanced workload like EP,
we would expect similar values for each board. However, from Figure 7, it can
be seen that the wait cycles are almost all from the second board. The second
board sees about 97% time spend in wait cycles, while the first board sees
about 2.5%, with the other boards experiencing negligible contribution. This
illustrates a highly imbalanced access pattern, perhaps one that would fit
with a software placement bug. This ultimately led to the discovery that GNU C
compiler’s OpenMP thread pinning was working, but was touching each thread’s
stack in the parent thread. This resulted in stack pages being page-faulted on
the parent-thread’s NUMA-node. Since the stack is intensively used, this
generates considerable cross-interconnect traffic. To mitigate this a
workaround was prepared to identify the correct NUMA-node and pin the stack
explicitly [24].

Recompiling EP with the patched GCC and rerunning the benchmark, run-time
dropped from $634.4$s to $112.1$s; a factor of $5.7\times$ speedup.
Correspondingly, the interconnect traffic dropped from a total of 17.8GiB to
1.14GiB; a factor of $15.6\times$ less interconnect traffic. Figure 6b shows
the corresponding plot. We see that in the patched run, number of cache-line
transfers reaches $6\text{\times}{10}^{6}$ per second during initialization
and when the parallel work starts they drop to $3.80\text{\times}{10}^{5}$
steady-state. Correspondingly, the wait time drops to about 2%.

Figure 7: NPB EP class D pinned OpenMP wait cycles per board Figure 8:
NUMAscope overhead with various sampling rates

###  V-D Tool overhead

To determine the overhead of NUMAscope, we execute the NPB EP class D
benchmark without using NUMAscope, and again using NUMAscope in record mode.
We demonstrate the overhead in record mode since this is the only mode
expected to be used for long periods of time, e.g. in production. Figure 8
plots the slowdown of the benchmark as we increase the sampling interval from
1ms to 1s. We observe that the maximum overhead on average is about 5% with a
sample interval of 1ms (1KHz), while the minimum is 0.27% with a sample
interval of 1s (1Hz). In typical use scenarios, for short period, a sample
interval of 100ms gives sufficient resolution for helping to understand
application and interconnect behavior, and gives low overhead due to the noise
mitigation steps detailed previously, and the access to remote NumaConnect
adapters being with non-coherent cycles, therefore cache oblivious. Note that
the sampling interval can be dynamically changed the /run/numascope-ctl UNIX
FIFO. That said NUMAscope can be initially configured to sample at a 100ms
interval and if something alerting is observed the sampling interval can be
further increased to investigate.

##  VI Conclusions

NUMAscope is an open-source [25] framework that enables the creation of tools
that allow the monitoring of large ccNUMA systems. NUMAscope is designed to be
modular and hardware agnostic, to support a number of ccNUMA interconnects in
the market. By implementing a simple interface, vendors can add support for
newer interconnets and expose measurements from hardware counters. NUMAscope
can then capture various events, from kernel events, to hardware events and
visualize them in an interactive GUI. As demonstrated in this work, tools
based on NUMAscope can help developers understand their applications’
bottlenecks and fix them. NUMAscope’s overhead is shown to be negligible when
used with a high sampling interval (1s), and it can go up to about 5% for a
sampling interval of 1ms. That makes NUMAscope-based tools production-ready.

## References

  * [1] D. Hackenberg, D. Molka, and W. E. Nagel, “Comparing cache architectures and coherency protocols on x86-64 multicore smp systems,” in _2009 42nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2009, pp. 413–422.
  * [2] D. Bailey, T. Harris, W. Saphir, R. Van Der Wijngaart, A. Woo, and M. Yarrow, “The nas parallel benchmarks 2.0,” Technical Report NAS-95-020, NASA Ames Research Center, Tech. Rep., 1995.
  * [3] “Perf tools.” [Online]. Available: https://github.com/torvalds/linux/tree/master/tools/perf
  * [4] D. Terpstra, H. Jagode, H. You, and J. Dongarra, “Collecting performance data with papi-c,” in _Tools for High Performance Computing 2009_ , M. S. Müller, M. M. Resch, A. Schulz, and W. E. Nagel, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 157–173.
  * [5] “Likwid.” [Online]. Available: https://github.com/RRZE-HPC/likwid
  * [6] C. McCurdy and J. Vetter, “Memphis: Finding and fixing numa-related performance problems on multi-core platforms,” in _2010 IEEE International Symposium on Performance Analysis of Systems Software (ISPASS)_ , March 2010, pp. 87–96.
  * [7] A. Kleen, “Pmu tools.” [Online]. Available: https://github.com/andikleen/pmu-tools
  * [8] U. Prestor and A. L. Davis, “An application-centric ccnuma memory profiler,” in _Proceedings of the Fourth Annual IEEE International Workshop on Workload Characterization. WWC-4 (Cat. No.01EX538)_ , Dec 2001, pp. 101–110.
  * [9] J. S. Gibson, “Memory profiling on shared-memory multiprocessors,” Ph.D. dissertation, Stanford University, 2002.
  * [10] K. Fatema, V. C. Emeakaroha, P. D. Healy, J. P. Morrison, and T. Lynn, “A survey of cloud monitoring tools: Taxonomy, capabilities and objectives,” _Journal of Parallel and Distributed Computing_ , vol. 74, no. 10, pp. 2918–2933, 2014.
  * [11] X. Liu and J. Mellor-Crummey, “A tool to analyze the performance of multithreaded programs on numa architectures,” in _Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_ , ser. PPoPP ’14. New York, NY, USA: ACM, 2014, pp. 259–272. [Online]. Available: http://doi.acm.org/10.1145/2555243.2555271
  * [12] R. Lachaize, B. Lepers, and V. Quema, “Memprof: A memory profiler for NUMA multicore systems,” in _Presented as part of the 2012 USENIX Annual Technical Conference (USENIX ATC 12)_. Boston, MA: USENIX, 2012, pp. 53–64. [Online]. Available: https://www.usenix.org/conference/atc12/technical-sessions/presentation/lachaize
  * [13] M. Selva, L. Morel, and K. Marquet, “numap: A portable library for low-level memory profiling,” in _2016 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation (SAMOS)_ , July 2016, pp. 55–62.
  * [14] X. Liu and B. Wu, “Scaanalyzer: A tool to identify memory scalability bottlenecks in parallel programs,” in _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ , ser. SC ’15. New York, NY, USA: Association for Computing Machinery, 2015. [Online]. Available: https://doi.org/10.1145/2807591.2807648
  * [15] A. Yasin, “A top-down method for performance analysis and counters architecture,” in _2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)_ , March 2014, pp. 35–44.
  * [16] J. P. Shen and M. H. Lipasti, _Modern processor design: fundamentals of superscalar processors_. Waveland Press, 2013.
  * [17] A. M. Devices, “Opteron family 15h bios and kernel developer guide.” [Online]. Available: https://www.amd.com/system/files/TechDocs/42301_15h_Mod_00h-0Fh_BKDG.pdf
  * [18] P. Conway, N. Kalyanasundharam, G. Donley, K. Lepak, and B. Hughes, “Blade computing with the amd opteron™ processor (" magny-cours"),” in _2009 IEEE Hot Chips 21 Symposium (HCS)_. IEEE, 2009, pp. 1–19.
  * [19] N. Agarwal, L. Peh, and N. K. Jha, “In-network coherence filtering: Snoopy coherence without broadcasts,” in _2009 42nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_ , Dec 2009, pp. 232–243.
  * [20] S. Kanev, J. P. Darago, K. Hazelwood, P. Ranganathan, T. Moseley, G.-Y. Wei, and D. Brooks, “Profiling a warehouse-scale computer,” in _Proceedings of the 42Nd Annual International Symposium on Computer Architecture_ , ser. ISCA ’15. New York, NY, USA: ACM, 2015, pp. 158–169. [Online]. Available: http://doi.acm.org/10.1145/2749469.2750392
  * [21] D. J. Blueman, “Numascale kernels.” [Online]. Available: https://resources.numascale.com/kernels/
  * [22] ——, “Numascale wiki.” [Online]. Available: https://wiki.numascale.com/tips/os-tips
  * [23] ——, “Numaconnect firmware.” [Online]. Available: https://github.com/numascale/firmware
  * [24] S. Persvold, “Gcc 4.9 openmp off-stack fix.” [Online]. Available: https://resources.numascale.com/gcc49-local-stack.patch
  * [25] D. J. Blueman, “Numascope.” [Online]. Available: https://github.com/numascale/numascope


# Ramanujan congruences for overpartitions with restricted odd differences

Michael Hanson and Jeremiah Smith

###### Abstract.

We investigate Ramanujan congruences for the function $\overline{t}(n)$, which
counts the overpartitions of $n$ with restricted odd differences. In
particular, we show that only one such congruence exists. Our method involves
using the theory of modular forms to prove a more general theorem which bounds
the number of primes possible for Ramanujan congruences in certain eta-
quotients. This generalizes work done by Jonah Sinick. We also provide two
congruences modulo 5 for $\overline{t}(n)$.

##  1\. Introduction

Perhaps one of the most famous results of Ramanujan was his collection of
congruences for the partition function $p(n)$. For a positive integer $n$,
$p(n)$ denotes the number of partitions of $n$, i.e. the number of ways to
write $n$ as a non-increasing sum of positive integers. For example, there are
five partitions of the integer 4, those being $4,3+1$, $2+2$, $2+1+1$,
$1+1+1+1$, and so $p(4)=5$. Here we define $p(0):=1$ and $p(n)=0$ when $n<0$.
It is common notation to write a partition
$n=\lambda_{1}+\lambda_{2}+\cdots+\lambda_{r}$ of $n$ in the concatenated form
$\lambda_{1}\lambda_{2}\ldots\lambda_{r}$. Ramanujan’s famous result on $p(n)$
is the collection of congruences

(1) $\displaystyle\begin{cases}p(5n+4)\equiv 0\pmod{5},\\\ p(7n+5)\equiv
0\pmod{7},\\\ p(11n+6)\equiv 0\pmod{11}.\end{cases}$

These are proven starting with the fact that the generating function for
$p(n)$ takes the form $\sum_{n\geq 0}p(n)q^{n}=\prod_{n\geq 1}(1-q^{n})^{-1}$
with $q:=e^{2\pi iz}$, which is essentially the inverted Dedekind’s eta-
function $\eta(z):=q^{1/24}\prod_{n\geq 1}(1-q^{n})$. Ramanujan’s congruences
for $p(n)$ all take the form $p(\ell n+a)\equiv 0\pmod{\ell}$ for some prime
$\ell$, hence all such congruences are called Ramanujan congruences. It is
natural to ask whether there are other primes $\ell$ for which $p(n)$ has
Ramanujan congruences. But as it turns out, work of Ahlgren and Boylan [AB03]
show that the Ramanujan congruences (1) are the only ones for $p(n)$.

Ramanujan’s work has inspired many others to consider such congruences for
other modified partition functions. In this work, we consider the modified
partition function $\overline{t}(n)$ that counts “overpartitions with
restricted odd parts,” as originally described in [BDLM15]. An overpartition
of $n$ is a partition of $n$ in which the final occurrence of a number may be
overlined. We let $\overline{p}(n)$ be the number of overpartitions of $n$.
Thus, for example, $\overline{p}(4)=14$, with the 14 partitions given as

$\displaystyle 4,\quad\overline{4},\quad 3+1,\quad\overline{3}+1,\quad
3+\overline{1},\quad\overline{3}+\overline{1},\quad 2+2,\quad
2+\overline{2},\quad 2+1+1,$ $\displaystyle\overline{2}+1+1,\quad
2+1+\overline{1},\quad\overline{2}+1+\overline{1},\quad 1+1+1+1,\quad
1+1+1+\overline{1}.$

Our function of interest $\overline{t}(n)$ counts the number of overpartitions
of $n$ with the following restrictions.

  1. (i)

The difference between two successive parts may be odd only if the larger part
is overlined.

  2. (ii)

If the smallest part is odd, then it is overlined.

For example, using $n=4$ again we have $\overline{t}(4)=8$, with the 8 such
partitions given as

$\displaystyle 4,\quad\overline{4},\quad
3+\overline{1},\quad\overline{3}+\overline{1},\quad 2+2,\quad
2+\overline{2},\quad\overline{2}+1+\overline{1},\quad 1+1+1+\overline{1}.$

The authors of [BDLM15] show that the generating function for
$\overline{t}(n)$ is given by

$\sum_{n\geq 0}\overline{t}(n)q^{n}=\frac{\eta(3z)}{\eta(2z)\eta(z)}.$

This is a weakly holomorphic modular form of weight $-1/2$ for the congruence
subgroup $\Gamma_{1}(144)$. Many congruences have been proven for
$\overline{t}(n)$. In particular, congruences modulo 2, 3, and 5 have been
found:

  * •

Theorem 1.1 of [HS19]: For $n\geq 0$ we have

$\overline{t}(n)\equiv\begin{cases}(-1)^{k+1}\pmod{3}&n=k^{2}\text{ some
$k$,}\\\ 0\pmod{3}&\text{else.}\end{cases}$

  * •

Theorem 1.2 of [HS19]: For $n\geq 1$ we have

$\overline{t}(2n)\equiv\begin{cases}1\pmod{2}&n=(3k+1)^{2}\text{ some $k$,}\\\
0\pmod{2}&\text{else.}\end{cases}$

  * •

Theorem 1.1 of [LLWX20]: For all $\alpha,n\geq 0$ we have

$\overline{t}(9^{\alpha}(45n+30))\equiv 0\pmod{5}.$

More congruences can be found in [CjH19, HS19, LLWX20, NG19]. We provide two
more congruences modulo 5, proven in Section 7 using the theory of modular
forms.

######  Theorem 1.

The following congruences hold for all $n\geq 0$:

(2) $\displaystyle\bar{t}(80n+40)$ $\displaystyle\equiv 0\pmod{5},$ (3)
$\displaystyle\bar{t}(80n+60)$ $\displaystyle\equiv 0\pmod{5}.$

However, one might question if any Ramanujan congruences hold for
$\overline{t}(n)$ (i.e. congruences of the form $\overline{t}(\ell n+a)\equiv
0\pmod{\ell}$ for a prime $\ell$). The results of [HS19] above show that the
only Ramanujan congruence mod 2 or 3 is $\overline{t}(3n+2)\equiv 0\pmod{3}$,
and one can check that there are no Ramanujan congruences mod 5. In fact, we
have the following.

######  Theorem 2.

The only Ramanujan congruence for $\overline{t}(n)$ is

$\overline{t}(3n+2)\equiv 0\pmod{3}.$

In order to prove Theorem 2, it suffices to show that there are no Ramanujan
congruences for primes $\ell>5.$ This is an immediate consequence of Theorem 3
below, which is a generalization of work done by Sinick in [Sin10].

######  Theorem 3.

Let $\lambda=\lambda_{1}\lambda_{2}\ldots\lambda_{r}$ and
$\mu=\mu_{1}\mu_{2}\ldots\mu_{s}$ be partitions of $u\in\mathbb{N}$ and
$v\in\mathbb{N}$, respectively, where we assume without loss of generality
that $\lambda_{i}\neq\mu_{j}$ for all $i,j.$ Define

$f(z):=\prod_{n\geq
1}\frac{(1-q^{\lambda_{1}n})(1-q^{\lambda_{2}n})\cdots(1-q^{\lambda_{r}n})}{(1-q^{\mu_{1}n})(1-q^{\mu_{2}n})\cdots(1-q^{\mu_{s}n})}=:\sum_{n\geq
0}c(n)q^{n}.$

Let $N:=\text{lcm}(\lambda_{1},\ldots,\lambda_{r},\mu_{1},\ldots,\mu_{s})$,
and let $\gamma$ be the number of occurrences of the smallest element of
$\\{\lambda_{1},\ldots,\lambda_{r},\mu_{1},\ldots,\mu_{s}\\}.$ Let $\ell$ be
prime such that $\ell>\max(5,|s-r|+4)$ and $(\ell,\gamma N)=1$. If either
$s-r\in 2\mathbb{N}_{0}$ or $u\equiv v\pmod{\ell}$ and $r-s\neq 1,3$, then
$c(n)$ does not obey a Ramanujan congruence modulo $\ell$.

This theorem identifies an explicit upper bound for the primes that could
result in a Ramanujan congruence.

In Section 2, we provide a brief introduction to modular forms modulo $\ell$,
and we give a few results within the theory that will be used in later
sections. Section 3 provides motivation and an outline for the proof of
Theorem 3. Section 4 proves the most interesting and essential result for the
proof of Theorem 3. Section 5 disposes of some necessary calculations needed
for Section 6 which complete the proofs of Theorems 3 and 2, respectively.
Section 7 proves Theorem 1. Section 8 provides a helpful example pertaining to
the discussion following Proposition 2.

##  2\. Modular forms modulo $\ell$

In this section, we introduce the notion of “modular forms mod $\ell$” as well
as some preliminary results that will be used in later sections. We refer the
reader to [Ono04] for a more detailed account of this material.

We denote the $\mathbb{C}$-vector space of weakly holomorphic modular forms of
integer weight $k$ on the congruence subgroup $\Gamma_{1}(N)$ of
$\text{SL}_{2}(\mathbb{Z})$ by $M^{!}_{k}(\Gamma_{1}(N))$. Let
$M_{k}(\Gamma_{1}(N))$ denote the subspace of those forms which are
holomorphic at the cusps of $\Gamma_{1}(N)$, and let $S_{k}(\Gamma_{1}(N))$
denote its corresponding subspace of cusp forms. Given
$M=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}\in\text{SL}_{2}(\mathbb{Z})$, define
the usual weight-$k$ slash operator on holomorphic functions $f$ on the upper
half plane $\mathbb{H}$ as

$f\mid_{k}M:=(cz+d)^{-k}f\left(\frac{az+b}{cz+d}\right).$

We will sometimes drop the subscript $k$ for notational convenience. Now
define $\theta:=\frac{1}{2\pi i}\frac{d}{dz}=q\frac{d}{dq}$, where $q:=e^{2\pi
iz}$, so that on Fourier series we have

$\theta\left(\sum_{n\geq 0}a(n)q^{n}\right)=\sum_{n\geq 0}na(n)q^{n}.$

Also define the $m$-th $U$-operator on Fourier series as

$\sum_{n\geq 0}a(n)q^{n}\mid U_{m}:=\sum_{n\geq 0}a(mn)q^{n}.$

Eisenstein series are canonical examples of modular forms for
$\text{SL}_{2}(\mathbb{Z})$, and they play an important role in Lemma 1 below.
For even $k>2$, the weight-$k$ Eisenstein series for
$\text{SL}_{2}(\mathbb{Z})$ is

$E_{k}(z):=1-\frac{2k}{B_{k}}\sum_{n\geq 1}\sigma_{k-1}(n)q^{n},$

where $B_{k}$ is the $k$-th Bernoulli number, and $\sigma_{k-1}(n)=\sum_{d\mid
n}d^{k-1}$. When $k=2$, $E_{2}(z)\coloneqq 1-24\sum_{n\geq
1}\sigma_{1}(n)q^{n}$ is not a modular form, but rather a “quasi-modular
form.” It has the transformation law

(4) $\displaystyle E_{2}(z)\mid M=E_{2}(z)-\frac{6ic}{\pi(cz+d)},$

for $M=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}\in\text{SL}_{2}(\mathbb{Z})$. We
also have the Delta function

$\Delta(z)=\eta(z)^{24}=q\prod_{n=1}^{\infty}(1-q^{n})^{24}\in
M_{12}(\text{SL}_{2}(\mathbb{Z})),$

which vanishes at the cusp $\infty$ of $\text{SL}_{2}(\mathbb{Z})$.

Given a modular form $f\in M_{k}(\Gamma_{1}(N))\cap\mathbb{Z}\llbracket
q\rrbracket$, one can reduce the Fourier coefficients of $f$ modulo a prime
$\ell$, giving an element $\tilde{f}$ of $\mathbb{F}_{\ell}\llbracket
q\rrbracket$. We call $\tilde{f}$ a modular form modulo $\ell$ for
$\Gamma_{1}(N)$. The filtration of $f$ is defined as

$w_{\ell}(f):=\min\\{k^{\prime}:\tilde{f}\in\widetilde{M}_{k^{\prime}}(\Gamma_{1}(N))\\},$

where

$\widetilde{M}_{k^{\prime}}(\Gamma_{1}(N)):=\\{\tilde{g}:g\in
M_{k^{\prime}}(\Gamma_{1}(N))\\}.$

We will also refer to preimages of $\tilde{f}$ under the reduction map as
“modular forms modulo $\ell$”.

By using (4), one can easily generalize Lemma 3 of [SD77] for $N>1$ to
conclude that if $f\in M_{k}(\Gamma_{1}(N))$ then $12\theta f-kE_{2}f\in
M_{k+2}(\Gamma_{1}(N))$. Theorem 2(i) from [SD77] implies that
$E_{\ell-1}\equiv 1\pmod{\ell}$ and $E_{\ell+1}\equiv E_{2}\pmod{\ell}$. These
facts come together to prove Lemma 1.

######  Lemma 1 (Lemma 2.1 of [Sin10]).

If $f\in M_{k}(\Gamma_{1}(N))\cap\mathbb{Z}\llbracket q\rrbracket$, then
defining $R$ to be

(5) $\displaystyle R:=\left(\theta
f-\frac{k}{12}E_{2}f\right)E_{\ell-1}+\frac{k}{12}E_{\ell+1}f,$

$R$ is a modular form of weight $k+\ell+1$ such that $R\equiv\theta
f\pmod{\ell}$. In particular, $\theta f$ is a modular form $\pmod{\ell}$ for
$\Gamma_{1}(N)$. It follows that if $\tilde{f}\not\equiv 0\pmod{\ell}$, then
$w_{\ell}(\theta f)\leq w_{\ell}(f)+\ell+1$.

We will also need the following facts about filtrations.

######  Lemma 2.

Let $N\geq 4$, let $f,g\in M(\Gamma_{1}(N))\cap\mathbb{Z}\llbracket
q\rrbracket$, and let $\ell\geq 5$ be prime. Then:

  1. (i)

We have $w_{\ell}(\theta f)=w_{\ell}(f)+\ell+1$ if and only if
$w_{\ell}(f)\not\equiv 0\pmod{\ell}$.

  2. (ii)

If $f$ and $g$ have weights $k_{1}$ and $k_{2}$ respectively and
$\tilde{f}\equiv\tilde{g}\not\equiv 0\pmod{\ell}$, then $k_{1}\equiv
k_{2}\pmod{\ell-1}$.

  3. (iii)

If $\ell\nmid N$ then for $i\geq 0$ we have $w_{\ell}(f^{i})=i\cdot
w_{\ell}(f)$.

The proofs of (ii) and the reverse implication of (i) are given directly in
Section 4 of [Gro90]. The remaining facts are quick consequences of the
results given in the same section.

The following elementary fact will be useful in Section 6: if $f\in
M_{k}(\Gamma_{1}(N))\cap\mathbb{Z}\llbracket q\rrbracket$ and $\ell$ is a
prime, then $(f\mid U_{\ell})^{\ell}\equiv f-\theta^{\ell-1}f\pmod{\ell}$. It
follows that

$f\mid U_{\ell}\equiv 0\pmod{\ell}\iff\theta^{\ell-1}f\equiv f\pmod{\ell}.$

##  3\. Keys to the Proof of Theorem 3

The statement of Theorem 3 concerns the existence of Ramanujan congruences for
a particular type of eta-quotient. We hope to apply the following proposition
originally due to I. Kiming and J. Olsson [KO92] and then corrected by J.
Sinick [Sin10, Proposition 3.2].

######  Proposition 1.

Let $\ell\geq 5$ be prime and $N\geq 4$, $\ell\nmid N$. Suppose that $f(z)\in
M_{k}(\Gamma_{1}(N))$ has $\ell$-integral Fourier coefficients,
$w_{\ell}(f(z))\not\equiv 0\pmod{\ell}$, and $\theta(f(z))\not\equiv
0\pmod{\ell}$. Suppose further that $w_{\ell}(\theta^{m}f(z))\geq
w_{\ell}(f(z))$. Then if the Fourier coefficients $d(n)$ of $f(z)$ satisfy
$d(\ell n+b)\equiv 0\pmod{\ell}$, one of the following is true: $b=0$,
$w_{\ell}(f(z))\equiv(\ell+1)/2\pmod{\ell}$, or
$w_{\ell}(f(z))\equiv(\ell+3)/2\pmod{\ell}.$

There is a glaring problem with naively applying this proposition to the eta-
quotient in Theorem 3: the fact that the eta-quotient is not necessarily an
integer weight holomorphic modular form. We will fix this by defining an
integer weight modular form for each prime $\ell$ for which a Ramanujan
congruence exists mod $\ell$ if and only if a Ramanujan congruence exists mod
$\ell$ for the given eta-quotient. This definition is given below.

Let $N:=\text{lcm}(\lambda_{1},\ldots,\lambda_{r},\mu_{1},\ldots,\mu_{s})$.
Define

$F_{\ell}(z):=\Delta(z)^{\ell^{t}}\left(\frac{\Delta(\mu_{1}z)\Delta(\mu_{2}z)\cdots\Delta(\mu_{s}z)}{\Delta(\lambda_{1}z)\Delta(\lambda_{2}z)\cdots\Delta(\lambda_{r}z)}\right)^{\delta_{\ell}}=:\sum_{n\geq
0}D(n)q^{n},$

where $\delta_{\ell}:=\frac{\ell^{2}-1}{24}$, and where $t\geq 2$ is the
smallest integer such that $F_{\ell}$ is holomorphic at the cusps of
$\Gamma_{1}(N)$.

######  Remark 1.

Note that $F_{\ell}$ is a modular form of weight
$\frac{(\ell^{2}-1)(s-r)}{2}+12\ell^{t}$ for $\Gamma_{1}(N)$. In what follows,
we sometimes need $N\geq 4$. We can substitute $4N$ for $N$ without loss of
generality when $N<4$.

The fact that the Ramanujan congruences for $F_{\ell}$ are in correspondence
with those of $f$ is the following lemma.

######  Lemma 3.

With notation as above, we have that $D(\ell n+b)\equiv 0\pmod{\ell}$ if and
only if $c(\ell n+a)\equiv 0\pmod{\ell}$, where $b$ is defined by $24a\equiv
24b+(u-v)\pmod{\ell}$.

The proof of this will be given later in Section 5. Notice that if $u\equiv
v\mod{\ell}$, then $a\equiv b\pmod{\ell}$ (recall $\ell>5$). Now that we have
defined an appropriate modular form, we need to proceed by checking that
$F_{\ell}$ satisfies the other assumptions of Proposition 1. The fact that
$\theta F_{\ell}\not\equiv 0\pmod{\ell}$ is a simple calculation (see
Proposition 3) which will be done in Section 5. On a technical note, the
necessity of $\gamma$ in the statement of Theorem 3 comes from this
calculation. The most difficult assumptions to verify in Proposition 1 are
precisely those which deal with the filtrations. This will be accomplished in
Section 4. By these calculations, we will see that the two congruences
$w_{\ell}(F_{\ell}(z))\equiv(\ell+1)/2\pmod{\ell}$ and
$w_{\ell}(F_{\ell}(z))\equiv(\ell+3)/2\pmod{\ell}$ are impossible. Lastly, in
order to get the full strength of Theorem 3, we must dispose of the
possibility that $b=0$ in the statement of Proposition 1. This is a technical
point which is resolved in Section 6.

##  4\. Calculating the Filtrations

In this section, we show that $w_{\ell}(\theta^{m}F_{\ell})\geq
w_{\ell}(F_{\ell})=\frac{(\ell^{2}-1)(s-r)}{2}+12\ell^{t}$ by proving the more
general Proposition 2.

######  Proposition 2.

Let $F\in M_{k}(\Gamma_{1}(N))\cap\mathbb{Z}[[q]]$, $\ell\geq 5$ prime,
$\ell\nmid N$, $\theta F\not\equiv 0\pmod{\ell}$, and suppose that $F$ does
not vanish on $\mathbb{H}$. Then $w_{\ell}(F)=k$ and
$w_{\ell}(\theta^{m}F)\geq w_{\ell}(F)$.

Following the discussion below Lemma 4.1 of [Sin10], we enumerate the cosets
of $\Gamma_{1}(N)$ in $\text{SL}_{2}(\mathbb{Z})$ by $\\{i\\}_{1\leq i\leq
2d_{N}}$. Let $M_{i}$ be a representative of the $i$-th coset. Let
$\alpha_{i}$ be the cusp that $M_{i}$ sends to $\infty$. Denote the minimal
period of $F\mid M_{i}$ by $t_{i}$. Then $F\mid M_{i}$ has a Fourier expansion
in powers of $q_{t_{i}}:=e^{2\pi iz/t_{i}}$, and the order of vanishing of $F$
at $\alpha_{i}$ is the index of the first non-vanishing Fourier coefficient of
$F$ in powers of $q_{t_{i}}$, denoted $\text{ord}_{\alpha_{i}}(F)$. Though
these $q_{t_{i}}$-Fourier expansions of $F$ need not have coefficients in
$\mathbb{Z}$, Corollary 5.3 of [Rad12] tells us that they lie in
$\mathbb{Z}[\zeta_{N}]$ with $\zeta_{N}$ a primitive $N$-th root of unity.

Instead of considering modular forms modulo $\ell$, one may choose an
algebraic number field $L$ and look at forms $g\in M_{k}(\Gamma_{1}(N))\cap
L\llbracket q\rrbracket$. We can then reduce $g$ modulo $v$ for any prime
$v\in\mathcal{O}_{L}$ such that the $v$-adic valuation of $g$ is $0$. This
allows us to define the notion of “modular form modulo $v$”, and we can define
the filtration $w_{v}$ for nonvanishing forms $\pmod{v}$ in the obvious way.
Hence we can define the $v$-adic valuation of the corresponding power series
to be the minimum of the $v$-adic valuations of the coefficients. Defining
$\widetilde{\text{ord}}_{\alpha_{i}}(f)$ to be the order of vanishing of
$f\pmod{v}$ at the cusp $\alpha_{i}$ (this is well-defined; see for example
Remark 2.4 of [Dew11]), we have Lemma 4.2 of [Sin10], stated below.

######  Lemma 4.

Let $m\geq 1$ be an integer and let $v$ be a prime in $\mathbb{Z}[\zeta_{N}]$
such that $v\nmid 2,3,N$. Let $f(z)$ be a modular form for $\Gamma_{1}(N)$
such that $f(z)\mid M_{i}$ has coefficients in $\mathbb{Q}(\zeta_{N})$ and
$v$-adic valuation $0$. Let $\alpha_{i}$ be a cusp of $\Gamma_{1}(N)$. Then

$\widetilde{\text{ord}}_{\alpha_{i}}(\theta^{m}f)\geq\widetilde{\text{ord}}_{\alpha_{i}}(f).$

######  Remark 2.

Sinick’s proof states, “Since $v\nmid N$ and $f(z)\mid M_{i}$ has $v$-adic
valuation 0, the Fourier expansion of $\theta(f\mid M_{i})$ has $v$-adic
valuation 0.” However, this statement is false by taking a prime above $5$ in
$\mathbb{Z}[\zeta_{7}]$ and considering $E_{4}(z)$ as a modular form for
$\Gamma_{1}(7)$ for example. One needs the additional assumption that $\theta
f\not\equiv 0\pmod{v}$.

###### Proof of Proposition 2.

We let $M_{i}$, $\alpha_{i}$, $t_{i}$, and $v\in\mathbb{Z}[\zeta_{N}]$ be as
above, $v$ being a prime above $\ell$. Since $\theta F\not\equiv 0\pmod{\ell}$
by assumption, $F\not\equiv 0\pmod{\ell}$. In particular, $F\not\equiv
0\pmod{v}$, and so Theorem 12.3.4 and Remark 12.3.5 of [DI95] assert that
$F\mid M_{i}\not\equiv 0\pmod{v}$. Define

$G(z):=\prod_{i=1}^{2d_{N}}(F\mid M_{i}),$

a modular form for $\text{SL}_{2}(\mathbb{Z})$ of weight $2d_{N}k$. As $F$ is
zero-free on $\mathbb{H}$, so is $G$, and so by the valence formula we have
that $G$ is a non-zero constant multiple of $\Delta(z)^{e}$ with
$e:=\frac{2d_{N}k}{12}=\frac{d_{N}k}{6}$. It follows that $w_{v}(G)=12e$ since
if there existed a modular form of smaller weight which is congruent to $G,$
Sturm’s Theorem [Ono04, Theorem 2.58] would imply that it would have to vanish
mod $v.$ Thus $w_{v}(F)=k,$ and since $F\in\mathbb{Z}\llbracket q\rrbracket$,
we in fact have that $w_{\ell}(F)=k$, as desired.

Now we show that $w_{\ell}(\theta^{m}F)\geq w_{\ell}(F)$. Notice that
$\widetilde{\text{ord}}_{\infty}(G)=e$, whence
$\widetilde{\text{ord}}_{\infty}(F\mid
M_{i})=\frac{\widetilde{\text{ord}}_{\alpha_{i}}(F)}{t_{i}}$. Thus

$\sum_{i=1}^{2d_{N}}\frac{\widetilde{\text{ord}}_{\alpha_{i}}(F)}{t_{i}}=\widetilde{\text{ord}}_{\infty}(G)=e.$

Define

$H:=\prod_{i=1}^{2d_{N}}(\theta^{m}F)\mid M_{i}.$

Notice that $H$ is a modular form modulo $v$ for $\text{SL}_{2}(\mathbb{Z})$
by the modified version of Lemma 1, where we replace $\ell$ with $v$. Then

$\widetilde{\text{ord}}_{\infty}(H)=\sum_{i=1}^{2d_{N}}\frac{\widetilde{\text{ord}}_{\alpha_{i}}(\theta^{m}F)}{t_{i}}\geq\sum_{i=1}^{2d_{N}}\frac{\widetilde{\text{ord}}_{\alpha_{i}}(F)}{t_{i}}=e,$

the inequality being a consequence of Lemma 4. Since $\theta^{m}F$ is a
modular form modulo $v$ which does not vanish, Theorem 12.3.4 and Remark
12.3.5 of [DI95] assert that $(\theta^{m}F)\mid M_{i}\not\equiv 0\pmod{v}$.
This shows that $H\not\equiv 0\pmod{v}$. Sturm’s Theorem [Ono04, Theorem 2.58]
now tells us that $w_{v}(H)\geq 12e$, and so
$w_{v}(\theta^{m}F)=w_{\ell}(\theta^{m}F)\geq k=w_{\ell}(F)$, the first
equality coming from the fact that $F$ has integral Fourier coefficients. ∎

##  5\. Necessary Calculations

In this section, we produce two calculations that are necessary for the
application of Proposition 1.

######  Proposition 3.

We have that $\theta F_{\ell}\not\equiv 0\pmod{\ell}$.

###### Proof.

We note that by definition of $\theta$ it is sufficient to compute the Fourier
expansion modulo $\ell$. We have

$\displaystyle F_{\ell}(z)$
$\displaystyle=\Delta(z)^{\ell^{t}}\left(\frac{\Delta(\mu_{1}z)\Delta(\mu_{2}z)\cdots\Delta(\mu_{s}z)}{\Delta(\lambda_{1}z)\Delta(\lambda_{2}z)\cdots\Delta(\lambda_{r}z)}\right)^{\delta_{\ell}}$
$\displaystyle=q^{\ell^{t}+(v-u)\delta_{\ell}}\prod_{n=1}^{\infty}\left[(1-q^{n})^{\ell^{t}}\left(\prod_{i}(1-q^{\mu_{i}n})^{\ell^{2}-1}\right)\left(\prod_{j}\frac{1}{(1-q^{\lambda_{j}n})^{\ell^{2}-1}}\right)\right].$

Using a geometric series expansion, we have

$\displaystyle F_{\ell}(z)$
$\displaystyle=q^{\ell^{t}+(v-u)\delta_{\ell}}\prod_{n=1}^{\infty}\left[(1-q^{n})^{\ell^{t}}\left(\prod_{i}(1-q^{\mu_{i}n})^{\ell^{2}-1}\right)\left(\prod_{j}\left(\sum_{k=0}^{\infty}q^{\lambda_{j}nk}\right)^{\ell^{2}-1}\right)\right]$
$\displaystyle=q^{\ell^{t}+(v-u)\delta_{\ell}}\prod_{n=1}^{\infty}\left[(1-q^{n})^{\ell^{t}}\left(\prod_{i}(1-q^{\mu_{i}n})^{\ell^{2}-1}\right)\left(\prod_{j}(1+q^{\lambda_{j}n}+\ldots)^{\ell^{2}-1}\right)\right]$
$\displaystyle=q^{\ell^{t}+(v-u)\delta_{\ell}}\prod_{n=1}^{\infty}\left[(1-q^{n})^{\ell^{t}}\left(\prod_{i}(1-(\ell^{2}-1)q^{\mu_{i}n}+\ldots)\right)\left(\prod_{j}(1+(\ell^{2}-1)q^{\lambda_{j}n}+\ldots)\right)\right]$
$\displaystyle\equiv
q^{\ell^{t}+(v-u)\delta_{\ell}}\prod_{n=1}^{\infty}\left[(1-q^{n})^{\ell^{t}}\left(\prod_{i}(1+q^{\mu_{i}n}+\ldots)\right)\left(\prod_{j}(1-q^{\lambda_{j}n}+\ldots)\right)\right]\pmod{\ell}$
$\displaystyle\equiv
q^{\ell^{t}+(v-u)\delta_{\ell}}\prod_{n=1}^{\infty}\left[(1-q^{\ell^{t}n})(1+\alpha
q^{\mu_{r}n}+\ldots)(1-\beta q^{\lambda_{s}n}+\ldots)\right]\pmod{\ell},$

where $\alpha$ is the number of occurrences of $\mu_{r}$ in $\mu$ and $\beta$
is the number of occurrences of $\lambda_{s}$ in $\lambda$. Hence,

$\displaystyle F_{\ell}(z)$ $\displaystyle\equiv
q^{\ell^{t}+(v-u)\delta_{\ell}}(1\pm\cdots\pm\gamma q^{m}\pm\cdots)$
$\displaystyle\equiv q^{\ell^{t}+(v-u)\delta_{\ell}}\pm\cdots\pm\gamma
q^{m+\ell^{t}+(v-u)\delta_{\ell}}\pm\cdots\pmod{\ell},$

where $m=\min(\mu_{r},\lambda_{s})$. So, by applying the theta operator,

$\displaystyle\theta F_{\ell}(z)$
$\displaystyle\equiv(\ell^{t}+(v-u)\delta_{\ell})q^{\ell^{t}+(v-u)\delta_{\ell}}\pm\cdots\pm\gamma(m+\ell^{t}+(v-u)\delta_{\ell})q^{m+\ell^{t}+(v-u)\delta_{\ell}}\pm\cdots\pmod{\ell}.$

One of these coefficients does not vanish mod $\ell$ because either
$(v-u)\delta_{\ell}$ is divisible by $\ell$ or not, and from the fact that
$(\gamma m,\ell)=1$ the result follows. ∎

We also provide the proof of the correspondence of Ramanujan congruences of
the eta-quotient to an integer weight modular form.

###### Proof of Lemma 3.

We have

$\displaystyle\sum_{n\geq 0}c(n)q^{n}$ $\displaystyle=\prod_{n\geq
1}\frac{(1-q^{\lambda_{1}n})\cdots(1-q^{\lambda_{r}n})}{(1-q^{\mu_{1}n})\cdots(1-q^{\mu_{s}n})}$
$\displaystyle=\prod_{n\geq
1}\left(\frac{(1-q^{\mu_{1}n})\cdots(1-q^{\mu_{s}n})}{(1-q^{\lambda_{1}n})\cdots(1-q^{\lambda_{r}n})}\right)^{-\ell^{2}}\left(\frac{(1-q^{\mu_{1}n})\cdots(1-q^{\mu_{s}n})}{(1-q^{\lambda_{1}n})\cdots(1-q^{\lambda_{r}n})}\right)^{\ell^{2}-1}$
$\displaystyle=\prod_{n\geq
1}\left[\left(\frac{(1-q^{\mu_{1}n})\cdots(1-q^{\mu_{s}n})}{(1-q^{\lambda_{1}n})\cdots(1-q^{\lambda_{r}n})}\right)^{-\ell^{2}}\frac{q^{\delta_{\ell}(\lambda_{1}+\cdots+\lambda_{r})}}{q^{\delta_{\ell}(\mu_{1}+\cdots+\mu_{s})}}\left(\frac{q^{\frac{1}{24}(\mu_{1}+\cdots+\mu_{s})}(1-q^{\mu_{1}n})\cdots(1-q^{\mu_{s}n})}{q^{\frac{1}{24}(\lambda_{1}+\cdots+\lambda_{r})}(1-q^{\lambda_{1}n})\cdots(1-q^{\lambda_{r}n})}\right)^{\ell^{2}-1}\right]$
$\displaystyle=\left(\prod_{n\geq
1}\frac{(1-q^{\mu_{1}n})\cdots(1-q^{\mu_{s}n})}{(1-q^{\lambda_{1}n})\cdots(1-q^{\lambda_{r}n})}\right)^{-\ell^{2}}q^{\delta_{\ell}(u-v)}\left(\frac{\Delta(\mu_{1}z)\cdots\Delta(\mu_{s}z)}{\Delta(\lambda_{1}z)\cdots\Delta(\lambda_{r}z)}\right)^{\delta_{\ell}}.$

Hence,

$\displaystyle
q^{\delta_{\ell}(u-v)}\left(\frac{\Delta(\mu_{1}z)\cdots\Delta(\mu_{s}z)}{\Delta(\lambda_{1}z)\cdots\Delta(\lambda_{r}z)}\right)^{\delta_{\ell}}=\left(\prod_{n\geq
1}\frac{(1-q^{\mu_{1}n})\cdots(1-q^{\mu_{s}n})}{(1-q^{\lambda_{1}n})\cdots(1-q^{\lambda_{r}n})}\right)^{\ell^{2}}\sum_{n\geq
0}c(n)q^{n}.$

Multiply both sides by $\Delta(z)^{\ell^{t}}$ to get

(6) $\displaystyle
q^{\delta_{\ell}(u-v)}F_{\ell}(z)=\Delta(z)^{\ell^{t}}\left(\prod_{n\geq
1}\frac{(1-q^{\mu_{1}n})\cdots(1-q^{\mu_{s}n})}{(1-q^{\lambda_{1}n})\cdots(1-q^{\lambda_{r}n})}\right)^{\ell^{2}}\sum_{n\geq
0}c(n)q^{n}.$

Now we apply $U_{\ell}$ to equation (6), reduce modulo $\ell$, and multiply
both sides by $q^{-a}$ to get

$\displaystyle\sum_{n\geq 0}D\left(\ell n+\delta_{\ell}(u-v)+a\right)q^{n}$
$\displaystyle\equiv q^{-a}\Delta(z)^{\ell^{t-1}}\left(\prod_{n\geq
1}\frac{(1-q^{\mu_{1}n})\cdots(1-q^{\mu_{s}n})}{(1-q^{\lambda_{1}n})\cdots(1-q^{\lambda_{r}n})}\right)^{\ell}\sum_{n\geq
0}c(\ell n)q^{n}\pmod{\ell}.$

Applying Proposition (3) of [Ono96] to the right-hand side, we get

$\sum_{n\geq 0}D\left(\ell n+\delta_{\ell}(u-v)+a\right)q^{n}\equiv
0\pmod{\ell}\iff\sum_{n\geq 0}c(\ell(n-\ell^{t-1})+a)q^{n}\equiv
0\pmod{\ell}.$

Since $c(n)=0$ for $n<0$ this proves the lemma. ∎

##  6\. Proof of Theorem 3

By using the results in Sections 4 and 5, we may apply Proposition 1 to
$F_{\ell}$. Notice that the two congruences
$w_{\ell}(F_{\ell}(z))\equiv(\ell+1)/2\pmod{\ell}$ and
$w_{\ell}(F_{\ell}(z))\equiv(\ell+3)/2\pmod{\ell}$ are impossible given the
lower bound on $\ell$ and also the fact that $r-s\neq 1,3$. This shows that if
$F_{\ell}$ has a Ramanujan congruence, then $b=0$. Thus, checking that $f$ has
no Ramanujan congruences modulo $\ell$ is equivalent to checking that
$\sum_{n\geq 0}D(\ell n)q^{n}\not\equiv 0\pmod{\ell}$. In the case that
$u\equiv v\pmod{\ell}$, we have that $F_{\ell}=q^{\ell M}(1+\cdots)$ for some
$M$ and therefore $\sum_{n\geq 0}D(\ell n)q^{n}\not\equiv 0\pmod{\ell}$.

The case $u\neq v$ and $s-r\in 2\mathbb{N}_{0}$ is more subtle, but luckily
the proof of Theorem 1.2 in [Sin10] works just as well in our situation. We
start by stating Proposition 5.1 of [Sin10].

######  Proposition 4 (Proposition 5.1 of [Sin10]).

Let $\ell\geq 5$ be prime and $N\geq 4$, $\ell\nmid N$. Suppose that $f(z)\in
M_{k}(\Gamma_{1}(N))$ has $\ell$-integral Fourier coefficients,
$w_{\ell}(f(z))\not\equiv 0\pmod{\ell}$, and $\theta f\not\equiv
0\pmod{\ell}$. Suppose further that $w_{\ell}(\theta^{m}f(z))\geq
w_{\ell}(f(z))$. Let $i_{1}<i_{2}<\cdots<i_{c}$ be those
$i\in\\{0,1,\ldots,\ell-1\\}$ for which $w_{\ell}(\theta^{i}f)\equiv
0\pmod{\ell}$. Write
$w_{\ell}(\theta^{i_{j}+1}f)=w_{\ell}(\theta^{i_{j}}f)+(\ell+1)-s_{j}(\ell-1)$.
Write $k=w_{\ell}(f)$ and let $k_{0}\in\\{1,\ldots,\ell-1\\}$ be such that
$k\equiv-k_{0}\pmod{\ell}$. Then one of the four cases below holds:

  1. (I)

$k\equiv 1\pmod{\ell}$, $c=1$, $i_{1}=\ell-1$, and $s_{1}=\ell+1$.

  2. (II)

$k\equiv 2\pmod{\ell}$, $c=1$, $i_{1}=\ell-2$, and $s_{1}=\ell+1$.

  3. (III)

$k\not\equiv 1\pmod{\ell}$, $c=2$, $(i_{1},i_{2})=(k_{0},\ell-1)$, and
$(s_{1},s_{2})=(k_{0}+1,\ell-k_{0})$.

  4. (IV)

$k\not\equiv 1\pmod{\ell}$, $c=2$, $(i_{1},i_{2})=(k_{0},\ell-2)$, and
$(s_{1},s_{2})=(k_{0}+2,\ell-k_{0}-1)$.

We have $w_{\ell}(f)=w_{\ell}(\theta^{\ell-1}f)$ if and only if case (II) or
case (IV) holds.

We proceed by contradiction by assuming $D(\ell n)\equiv 0\pmod{\ell}$ for all
$n$ which implies that $\theta^{\ell-1}F_{\ell}\equiv F_{\ell}\pmod{\ell}$. So
by the last statement in Proposition 4, we are in cases (II) or (IV). But in
case (II) we have

$w_{\ell}(F_{\ell})=\frac{(s-r)(\ell^{2}-1)}{2}+12\ell^{t}\equiv
2\pmod{\ell}\iff r-s\equiv 4\pmod{\ell},$

which contradicts that $\ell>s-r+4$. So we are in case (IV). Here, we have

$k_{0}\equiv-k\equiv\frac{s-r}{2}\pmod{\ell}.$

Using Lemma 2, the identity
$w_{\ell}(\theta^{i_{j}+1}f)=w_{\ell}(\theta^{i_{j}}f)+(\ell+1)-s_{j}(\ell-1)$
with $s_{j}=s_{1}=k_{0}+2$ becomes

$\displaystyle w_{\ell}(\theta^{k_{0}+1}F_{\ell})$
$\displaystyle=w_{\ell}(F_{\ell})+(\ell+1)(k_{0}+1)-(k_{0}+2)(\ell-1)$ (7)
$\displaystyle=w_{\ell}(F_{\ell})+2k_{0}+3-\ell.$

Now, $2k_{0}\equiv s-r\pmod{\ell}$. Since $s-r$ is even and
$\ell>s-r\in\mathbb{N}_{0}$, we must have that

$k_{0}=\frac{s-r}{2}.$

Thus, (7) becomes

$w_{\ell}(F_{\ell})+s-r+3-\ell.$

But $\ell>s-r+3$, so this implies that

$w_{\ell}(\theta^{k_{0}+1}F_{\ell})=w_{\ell}(F_{\ell})+s-r+3-\ell<w_{\ell}(F_{\ell}),$

contradicting Proposition 2. This concludes the proof of Theorem 3.

##  7\. Proof of Theorem 1

In this section we use modular forms of half-integral weight. See [Ono04] for
background. We follow in the same theme as Ono [Ono96]. We first define the
eta-quotient

$f(z)\coloneqq\frac{\eta(3z)}{\eta(2z)\eta(z)}\ \eta^{12}(80z)=\sum_{m\geq
0}b(m)q^{m}.$

Using the appropriate theorems for eta-quotients (see for example [Ono04,
Theorem 1.64]), one can see that $f\in
M^{!}_{\frac{11}{2}}(\Gamma_{1}(1440))$. To make this holomorphic at the
cusps, we introduce the factor $\eta^{5}(z)/\eta(5z)$. We make the following
definition:

$F(z)\coloneqq f(z)\
\frac{\eta^{5}(z)}{\eta(5z)}=\sum_{m=0}^{\infty}c(m)q^{m}\in
S_{\frac{15}{2}}(\Gamma_{1}(1440)).$

Notice $\eta^{5}(z)/\eta(5z)\equiv 1\pmod{5}$. So, $F(z)\equiv f(z)\pmod{5}$.
Also, we have $\eta^{12}(80z)/q^{40}=1+\sum_{m>0}a(80m)q^{80m}$. Thus, if we
can show that

(8) $b(80n)\equiv 0\pmod{5}\text{ for all }n\geq 1,$

then $(\ref{congruence 1})$ holds. Since $80\mid 1440$, we have

$F(z)\mid U_{80}=\sum_{n=0}^{\infty}c(80n)q^{n}\in
S_{\frac{15}{2}}(\Gamma_{1}(1440)).$

Recall that $b(80n)\equiv c(80n)\pmod{5}$. By Sturm’s Criterion, we need to
verify that $c(80n)\equiv 0\pmod{5}$ for $0\leq
n\leq\frac{15}{24}[\text{SL}_{2}(\mathbb{Z}):\Gamma_{0}(1440)]+1=2161$. We do
this by using SAGE and computing the series $\sum_{m\geq 0}b(m)q^{m}$ up to
$80\cdot 2161=172,880$ terms and then focusing on the coefficients whose index
is divisible by 80. This proves the first congruence.

The second congruence is proved in a nearly identical fashion. First, we
define the eta-quotient

$g(z)\coloneqq\frac{\eta(3z)}{\eta(2z)\eta(z)}\eta^{6}(80z)=\sum_{m\geq
0}\beta(m)q^{m}\in M_{\frac{5}{2}}^{!}(\Gamma_{1}(2880)).$

Define

$G(z)\coloneqq g(z)\frac{\eta^{5}(z)}{\eta(5z)}\in
S_{\frac{9}{2}}(\Gamma_{1}(2880)).$

We notice that $G(z)\equiv g(z)\pmod{5}$. Also,
$\eta^{6}(80z)/q^{20}=q+\sum_{m>0}\alpha(80m)q^{80m}$. Thus, if we can show
that

(9) $\beta(80n)\equiv 0\pmod{5}\text{ for all }n\geq 1,$

then $(\ref{congruence 2})$ holds. Since $80\mid 2880$, then we have

$G(z)\mid U_{80}=\sum_{n=0}^{\infty}\gamma(80n)q^{n}\in
S_{\frac{9}{2}}(\Gamma_{1}(2880)).$

Hence, $\beta(80n)\equiv\gamma(80n)\pmod{5}$. By Sturm’s Criterion, we need to
verify that $\gamma(80n)\equiv 0\pmod{5}$ for $0\leq n\leq
9/24[\text{SL}_{2}(\mathbb{Z}:\Gamma_{0}(2880)]+1=2593$. We do this by using
SAGE and computing the series $\sum_{m\geq 0}\beta(m)q^{m}$ up to $80\cdot
2593=207440$ terms and then focus on the coefficients whose index is divisible
by 80. This completes the proof.

##  8\. Example of Proposition 2

In this section, we give an explicit example of Proposition 2 by following the
steps outlined in the proof. Let $\ell=7$ and

$f(z)=\frac{\eta(3z)}{\eta(2z)\eta(z)}.$

The corresponding $F_{7}$ as defined in $\eqref{keys to theorem}$ is

$F_{7}(z)=\Delta^{49}(z)\left(\frac{\eta(z)\eta(2z)}{\eta(3z)}\right)^{48},$

which is a holomorphic modular form for $\Gamma_{1}(6)$. We need to find a set
of coset representatives for $\Gamma_{1}(6)$ in $\text{SL}_{2}(\mathbb{Z})$.
The following lemma will make this easier.

######  Lemma 5.

Let $\gamma,\gamma^{\prime}\in\text{SL}_{2}(\mathbb{Z})$.

$\Gamma_{1}(N)\gamma=\Gamma_{1}(N)\gamma^{\prime}\iff|(c,d)|=|(c^{\prime},d^{\prime})|=N\text{
and }(c,d)\neq(c^{\prime},d^{\prime})\text{ in }(\mathbb{Z}/N\mathbb{Z})^{2},$

where $\gamma=\begin{bmatrix}a&b\\\ c&d\end{bmatrix}$ and
$\gamma^{\prime}=\begin{bmatrix}a^{\prime}&b^{\prime}\\\
c^{\prime}&d^{\prime}\end{bmatrix}$.

######  Remark 3.

One needs to be slightly careful when applying the above lemma. For instance,
when $N=6$, $|(5,5)|=6$ but since $c$ and $d$ in this case are not relatively
prime, then one cannot construct a matrix $\begin{bmatrix}a&b\\\
5&5\end{bmatrix}\in\text{SL}_{2}(\mathbb{Z})$. However,
$(5,5)\equiv(5,-1)\pmod{6}$ and this problem is resolved. The fact that this
can always be resolved is Lemma 3.8.4 of [DS05].

The above lemma states that all we must find is the pairs $(c,d)$ in
$(\mathbb{Z}/6\mathbb{Z})^{2}$ with order $6$. Furthermore, by consulting the
formulas for computing $q$-expansions of eta-quotients in [RSST19] and using
the fact that we are raising the eta-quotient to the 48th power, we notice
that the $q$-expansions are only dependent on these two matrix entries. There
are 24 such elements of $(\mathbb{Z}/6\mathbb{Z})^{2}$, however, not all of
these elements produce unique $q$-expansions. This is because $(c,d)$ and
$(-c,-d)$ give rise to the same expansion and are not equivalent because
$3\nmid\gcd(c,d)=1$. Thus, there are twelve expansions to compute. For
example,

$F_{7}(z)\mid\begin{bmatrix}1&0\\\
1&1\end{bmatrix}=\Delta^{51}(z)\frac{1}{2^{24}}q\left[\prod_{n=1}^{\infty}(1-(-q^{1/2})^{n})\right]^{48}3^{24}\zeta_{3}q^{-2/3}\left[\prod_{n=1}^{\infty}(1-(\zeta_{3}q^{1/3})^{n})\right]^{-48}.$

By multiplying all of these expansions together, we obtain a formula for $G$
as in the proof of Proposition 2,

$G(z)=\frac{3^{432}}{2^{384}}q^{4}\frac{\Delta^{1224}(z)\Delta^{16}(2z)}{\Delta^{12}(3z)}\prod_{n=1}^{\infty}\frac{(1-q^{n/2})^{384}(1-(-q^{1/2})^{n})^{384}}{(1-q^{n/3})^{288}(1-(\zeta_{3}q^{1/3})^{n})^{288}(1-(\zeta_{3}^{2}q^{1/3})^{n})^{288}},$

which (as expected) is equal to $C\Delta^{1224}(z)$ where
$C=\frac{3^{432}}{2^{384}}$. We will also show that $H$ (as in Proposition 2
with $m=1$) does not vanish mod $7$. To accomplish this, we use the fact
$\theta(F_{7}\mid M)\equiv(\theta F_{7})\mid M\pmod{7}$ which comes from the
proof of Lemma 4.2 in [Sin10]. Using SAGE, we obtain

$H\equiv 2q^{1252}+5q^{1253}+q^{1254}+2q^{1255}+2q^{1256}+\cdots\pmod{7}$

which is clearly not equivalent to 0.

## References

  * [AB03] Scott Ahlgren and Matthew Boylan.  Arithmetic properties of the partition function.  Inventiones mathematicae, 153:487–502, 2003.
  * [BDLM15] Kathrin Bringmann, Jehanne Dousse, Jeremy Lovejoy, and Karl Mahlburg.  Overpartitions with restricted odd differences.  Electron. J. Combin., 22(3):Paper 3.17, 16, 2015.
  * [CjH19] Shane Chern and Li jun Hao.  Congruences for two restricted overpartitions.  Proceedings - Mathematical Sciences, 129:1–16, 2019.
  * [Dew11] Michael Dewar.  Non-existence of Ramanujan congruences in modular forms of level four.  Canad. J. Math., 63(6):1284–1306, 2011.
  * [DI95] Fred Diamond and John Im.  Modular forms and modular curves.  In Seminar on Fermat’s Last Theorem (Toronto, ON, 1993–1994), volume 17 of CMS Conf. Proc., pages 39–133. Amer. Math. Soc., Providence, RI, 1995.
  * [DS05] Fred Diamond and Jerry Shurman.  A first course in modular forms.  Springer, 1 edition, 2005.
  * [Gro90] B. Gross.  A tameness criterion for galois representations associated to modular forms $\pmod{p}$.  Duke Mathematical Journal, 61:445–517, 1990.
  * [HS19] Michael D. Hirschhorn and James A. Sellers.  Congruences for overpartitions with restricted odd differences.  The Ramanujan Journal, 2019.
  * [KO92] Ian Kiming and Jørn B. Olsson.  Congruences like ramanujan’s for powers of the partition function.  Archiv der Mathematik, 59:348–360, 1992.
  * [LLWX20] Bernard L. S. Lin, Jian Liu, Andrew Y. Z. Wang, and Jiejuan Xiao.  Infinite families of congruences for overpartitions with restricted odd differences.  Bull. Aust. Math. Soc., 102(1):59–66, 2020.
  * [NG19] M. S. Mahadeva Naika and D. S. Gireesh.  Congruences for overpartitions with restricted odd differences.  Afrika Matematika, 30:1–21, 2019.
  * [Ono96] Ken Ono.  Congruences for frobenius partitions.  Journal of Number Theory, 57:170–180, 1996.
  * [Ono04] Ken Ono.  The web of modularity: arithmetic of the coefficients of modular forms and $q$-series, volume 102 of CBMS Regional Conference Series in Mathematics.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2004.
  * [Rad12] Cristian-Silviu Radu.  A proof of Subbarao’s conjecture.  J. Reine Angew. Math., 672:161–175, 2012.
  * [RSST19] Nathan C. Ryan, Zachary Scherr, Nicolás Sirolli, and Stephanie Treneer.  Congruences satisfied by eta-quotients.  arXiv: Number Theory, 2019.
  * [SD77] H. P. F. Swinnerton-Dyer.  On $\ell$-adic representations and congruences for coefficients of modular forms (ii).  1977\.
  * [Sin10] Jonah Sinick.  Ramanujan congruences for a class of eta quotients.  Int. J. Number Theory, 6(4):835–847, 2010.