# On Blowback Traffic on the Internet

Dallan Goldblatt  Case Western Reserve University<EMAIL_ADDRESS>,  Calvin
Vuong  Case Western Reserve University<EMAIL_ADDRESS>and  Michael Rabinovich
Case Western Reserve University<EMAIL_ADDRESS>
###### Abstract.

This paper considers the phenomenon where a single probe to a target generates
multiple, sometimes numerous, packets in response – which we term ”blowback”.
Understanding blowback is important because attackers can leverage it to
launch amplified denial of service attacks by redirecting blowback towards a
victim. Blowback also has serious implications for Internet researchers since
their experimental setups must cope with bursts of blowback traffic. We find
that tens of thousands, and in some protocols, hundreds of thousands, of hosts
generate blowback, with orders of magnitude amplification on average. In fact,
some prolific blowback generators produce millions of response packets in the
aftermath of a single probe. We also find that blowback generators are fairly
stable over periods of weeks, so once identified, many of these hosts can be
exploited by attackers for a long time.

Security, Internet measurement, DDoS

††copyright: none

##  1\. Introduction

Indiscriminately scanning the Internet’s address space has become a well-used
approach to studying various facets of the network, for example, to find open
DNS resolvers (e.g., (kuhrer2015going, ; al2019look, ; yazdani2022matter, ;
park2021large, )) or to study the SSL certificate ecosystem (e.g.,
(durumeric2013analysis, ; brubaker2014using, ; rapid7, ). When using this
approach in our past work, we have noticed that not only do we receive valid
responses to our probes, but also responses that are unexpected in some
fashion. The weirdness in the responses manifests in different ways—from
responses that do not match the probe’s protocol to large volumes of packets
whereby the standard protocol would suggest only a single packet response. In
informal discussions with colleagues we have come to understand that this
phenomena has been noticed in many contexts. We have termed these unexpected
responses “blowback”. This paper draws attention to the blowback phenomenon,
as well as providing initial characterization and insights of this traffic.

As a concrete anecdote to build intuition we sent a single TCP SYN segment to
IP address 103.40.65.97 and target port 80. We received a multitude of
responses to our single probe, including: TCP SYN/ACKs, other TCP packets,
ICMP redirections and ICMP TTL exceeded messages. Most of these responses
would have been reasonable if we had received only one, but all told we
recorded over 32K response packets that total to more than 1.6MB over the
course of the 2.3 seconds after we sent the probe. Further, the responses came
from not only the above address we probed, but two other addresses as well
(103.57.177.61 and 43.225.214.58). This was also not a one-time event, as we
observed the same basic phenomena over six different probes to the same target
(103.40.65.97:80) sent over the course of two and a half weeks.

At a minimum this traffic is a nuisance when scanning the Internet.
Researchers must engineer their measurement instrumentation to cope with
blowback bursts and wade through the incoming traffic to discard the blowback
in order to focus on the traffic that is germane to their study (e.g.,
harvesting SSL certificates). However, more problematic than mere nuisance is
that the blowback responses can be used as part of distributed denial-of-
service (DDoS) attacks. Once identified, a target that triggers blowback can
be used to reflect and amplify an attacker’s traffic. For instance, consider
the example above. By spoofing the source IP of the TCP SYN probe, an attacker
can trigger 32K packets to be sent towards some victim. Previous work has
shown the potential for this type of attack within specific protocols, where a
request may generate a larger and/or multi-packet response according to the
protocol specification and their responses – e.g., a number of UDP-based
protocols (rossow2014amplification, ), TCP (kuhrer2014exit, ), and IGMP
(SKPA17, ). In this paper we note that out-of-spec blowback traffic can be
leveraged in a similar manner—and sometimes with a tremendous amplification
factor. This moves blowback from a nuisance to a potentially dangerous
problem. Independent from our study, Nosyk et al. recently reported similar
findings for the DNS protocol (RoutingLoops_DNS_Amplifiers_PAM2010, ). We show
that these problems extend beyond DNS to a number of other widely used
protocols on the Internet and provide an initial characterization of blowback
traffic generators and their behavior.

##  2\. Methodology and High Level Results

In this section we will ($i$) detail our general scanning methodology in §2.1,
($ii$) describe how we match incoming responses to individual probes in §2.2
and ($iii$) provide a high-level overview of our resulting dataset in §2.3.
However, first we provide three definitions.

Response::

We consider all traffic triggered by a single probe to be part of the
“response” to that probe—regardless of the protocol or source IP address of
the incoming traffic.

Responder Group and Responder Group Generator::

A probe to a destination IP address $A$ can trigger responses from $A$ or a
set of IP addresses that may or may not contain $A$. We refer to all IP
addresses returning traffic triggered by a single probe to be part of the
probe’s “responder group” (RG). We refer to the target of a probe that
produced the response packet(s) from a responder group a ”responder group
generator (RGG)” or simply ”generator”. Note that, as mentioned above, the RGG
may not be contained in its RG.

Blowback and Blowback Generator::

A response to a probe will be called “blowback” if the response contains at
least four packets. (We will discuss this choice of constant in §2.3.) The
generator of the corresponding response group is referred to as a ”blowback
generator (BBG)”.

###  2.1. Scanning

To understand the blowback phenomenon we employ scans of the IPv4 address
space using zmap (durumeric2013zmap, ). For each probe we send we record a
timestamp, destination IP address, and certain protocol-specific
information—e.g., TCP sequence number. In addition, we use tcpdump to record
all incoming packets. We post-process the outgoing and incoming sets of
packets to match probes with their response traffic using the method outlined
in §2.2. We used six different probe types in our experiments: DNS queries for
a hostname from our own domain, ICMP echo requests, NTP time requests, as well
as TCP SYNs to ports 25, 80 and 443. With the exception of TCP responders,
which may resend SYN/ACK packets (kuhrer2014exit, ), none of our probes should
produce multi-packet responses. Further, none of the responses we received
indicated packet fragmentation.

Our scanning begins with a full scan of all IPv4 addresses for the six probe
types we use. We denote these full scans as $F^{proto}$ where
$proto=\\{DNS,ICMP,NTP,TCP25,TCP80,TCP443\\}$. The $F^{ICMP}$ scan was
conducted at a rate of 100K pps, while the remaining full scans were capped at
40K pps.111The scanning rates have been negotiated with our campus network
operators and the rates are not specific to this experiment. We record
incoming traffic for at least 7–20 minutes after our scanning is complete.

Once the full scans are complete we use the procedure described in §2.2 to
match outgoing probes with incoming responses. We then initiate a series of
re-probes to the targets found to be blowback generators in the full scans,
aiming to gain an understanding of the blowback phenomenon over time. We
conduct six rounds of re-probing for each probe type. We denote these re-scans
as $R^{proto}_{i}$, where $proto$ gives the probe type and $i=\\{1,\ldots
6\\}$ which indicates the re-probe instance. For instance, $R^{NTP}_{3}$
denotes the third re-scan using NTP probes. The first re-probe started 6–9
days after the full scan. Each subsequent re-probe started three days after
the previous re-probe. Ultimately, this gives us data on blowback generators
from six probe types over roughly 21–25 days. To mitigate the chances of
blowback overwhelming our measurement infrastructure we re-probe at 100 pps
since we know the probe targets will send responses—which differs from the
full scan, during which the vast majority of targets do not trigger responses.
Each re-scan was completed in under one hour. In the rest of the paper, we
refer to all targets re-probed in the rescans as blowback generators because
they were found as such during full scans – regardless of their response
during rescans.

Note: we repeated the entire process of a full scan followed by six re-scans a
second time for each probe type. For simplicity, we only report on one of
these iterations in this paper as the resulting insights are similar across
both iterations.

###  2.2. Response-to-Probe Matching

After scanning the Internet we must match the individual probes we sent with
the resulting incoming traffic we received. This task is complicated because
responses may not match the probed protocol or IP address. For instance, we
may send a TCP SYN packet to IP address $X$ and receive an ICMP Host
Unreachable response from IP address $Y$. Therefore, we cannot simply look for
a TCP SYN/ACK from IP address $X$. Further, this process is complicated by
naturally occurring background radiation (pang2004characteristics, ) that
arrives at our server but is unrelated to our probing.

Our matching process works by effectively merging our ledger of outgoing
probes and the packet trace of incoming packets in chronological order. We
keep a list $P$ of recently sent probes in memory. A probe is removed from $P$
once no matching response packets have arrived for 10 minutes. That is, each
matched response extends the probe’s time in $P$ by 10 minutes. The 10 minute
expiry time is derived from the amount of memory required to store $P$; this
turns out to be reasonable choice (see results below). Additionally, any
missed matches by expiring a probe prematurely reduces the amount of blowback
detected and thus makes our analysis conservative. We thus match incoming
packets to responses using two approaches, as follows.

We first use protocol-specific (PS) matching based on the probe type. These
criteria take into account some facet of the probe such that the matching is
quite strong and it would be nearly impossible for natural background
radiation to meet these tests. In particular we use one of these criteria:

PS.1: For DNS scans we match incoming packets that contain the (random) query
string222We use case-insensitive matching. included in a DNS probe within $P$.
This general rule covers normal DNS responses, ICMP messages that include the
query string in their quotation and other random packets.

PS.2: For TCP SYN scans we match incoming SYN/ACKs that have an acknowledgment
number that matches the (random) sequence number of a packet in $P$.

PS.3: For ICMP scans we match incoming echo replies based on the (random) ICMP
ID in the ICMP echo probes within $P$.

Note: There is nothing in our NTP probes that would concretely distinguish
incoming NTP responses triggered by our probes from some random background
radiation. Therefore, we rely on the more generic tests below to match NTP
packets.

When applying the protocol-specific criteria does not allow us to match an
incoming packet to a probe within $P$, we move on to a protocol-agnostic (PA)
process.

PA.1: For incoming ICMP packets, we examine the quotation portion of the
packet and attempt to match the destination IP address in the quotation to the
destination IP address of a probe in $P$.

PA.2: We match incoming TCP and UDP packets333In principle there could be
traffic using additional transport protocols triggered by our probes. However,
across all our scans we found less than 100 packets that were something other
than ICMP, UDP or TCP. We leave these as “unmatched” and do not include them
in our further analysis. Given their small number, this will not bias our
results. when both ($i$) the source IP address in the incoming packet matches
the destination IP of a probe packet in $P$ and ($ii$) the ephemeral port
number of the incoming packet is 55000—which is the static ephemeral port
number we use on probe packets.

Incoming packets that are not matched based on the PS or PA criteria are left
as “unmatched” and not included in our analysis. Our approach matches 95–99%
of the incoming traffic across all our scans and probe types. We are highly
confident in the matches made using our process. Based on the criteria above
it is highly unlikely that an incoming packet would be matched if that packet
was not in fact triggered by our probe. Further, ignoring the relatively few
($<5\%$) unmatched packets in our analysis is conservative in that the
blowback phenomenon can only be worse than we find below.

###  2.3. Dataset

Scan | All | Multipacket | Blowback | % of Multipacket
---|---|---|---|---
| RGGs | RGGs | RGGs | Response Traffic due
|  |  |  | to Blowback RGs
$F^{DNS}$ | 150M | 593K | 61K | 70.0%
$F^{ICMP}$ | 443M | 281K | 108K | 99.8%
$F^{TCP443}$ | 221M | 1.6M | 241K | 61.3%
$F^{TCP25}$ | 198M | 836K | 86K | 65.9%
$F^{TCP80}$ | 204M | 2.1M | 298K | 58.3%
$F^{NTP}$ | 148M | 497K | 56K | 95.0%
Table 1. Overview of full scan results

Table 1 provides a high-level overview of our full scans. The second column
shows the number of responder group generators—i.e., the number of probe
targets that generated some sort of response—that send at least one packet in
response to our probes. These RGGs include hosts that respond to our probes as
expected, e.g., DNS servers responding to our DNS queries or hosts responding
to our ICMP pings. The third column shows the number of RGGs that produce a
response with more than one packet – these can be viewed as problematic
because of their traffic amplification. The next column shows the number of
RGGs that generate at least four packets in response to a single probe while
the last column shows the percentage of multi-packet response traffic for
which these RGGs are responsible. Our analysis focuses on these RGGs because
of their higher potential for disruption and because by focusing on these
RGGs, as the table shows, we cut the number of targets (and hence, the amount
of probing in rescans) by an order of magnitude in most cases while still
covering a majority (at least 58%) of multi-packet response traffic. As
mentioned earler, we call these RGGs ”blowback generators (BBG)”, their
responses traffic ”blowback traffic”, and their individual responses ”blowback
responses”. While BBGs are a minority of the RGGs that send multiple packet
responses, their absolute number is large—ranging from 56K to nearly 300K
depending on the protocol.

##  3\. Blowback Characterization

###  3.1. Blowback Volumes

Scan | Probe | Probe | Avg. Response | Avg. Response | Avg. Packet | Avg. Volume
---|---|---|---|---|---|---
| Packets (K) | Volume (MB) | Packets (M) | Volume (MB) | Amplification | Amplification
$R^{DNS}_{*}$ | 60,511 | 6.1 | 1.8 | 132.6 | 30x | 22x
$R^{ICMP}_{*}$ | 107,912 | 3.0 | 103.5 | 7,271.6 | 959x | 2,424x
$R^{TCP443}_{*}$ | 241,353 | 9.7 | 2.7 | 144.2 | 11x | 15x
$R^{TCP25}_{*}$ | 85,687 | 3.4 | 1.6 | 89.0 | 19x | 26x
$R^{TCP80}_{*}$ | 298,379 | 11.9 | 3.2 | 167.7 | 11x | 14x
$R^{NTP}_{*}$ | 56,149 | 4.3 | 21.0 | 1,585.2 | 374x | 369x
Table 2. Average amount of blowback traffic received during rescans.

Table 2 represents a first look at the average amount of blowback our probes
triggered across all rescans. The second and third columns of the table show
the number of probes and their corresponding size for each rescan, as dictated
by the analysis of the full scans. The next two columns show the average
number and size of the responses across our six rescans for each probe type.
The final two columns illustrate the packet and volume amplification factors
between the transmitted and received traffic. We find at least an order of
magnitude amplification—both in terms of packets and volume—across all probe
types. However, some probe types show significantly more amplification than
others. Our ICMP probes show the most amplification by receiving 959x more
packets and 2,424x bytes than we transmit. In the aggregate across all probe
types, sending 38.4 MB in 850K probes triggers nearly 134 million response
packets that add to nearly 9.4 GB. This suggests blowback could be harnessed
as in a significant DDoS attack.

###  3.2. BBG Stability

Figure 1.  BBG stability across rescans. Green solid bars represent the
prevalence range of BBGs found to generate blowback (at least four packets)
across the rescans. Blue hashed bars represent the prevalence range of BBGs
found to be active (generate at least one packet) across the rescans.

Next we study the extent to which BBGs remain stable over time. A stable set
allows prolonged use of the BBGs discovered via a full scan—by an attacker for
a persistent attack or by an experimenter for mitigating blowback
interference.

Figure 1 shows the stability of BBGs in our measurements. Across the six
rescans we find the minimum and maximum fraction of the original BBGs (i.e.,
the probe targets found to be BBGs in the full scan) still sending blowback
(i.e., generating at least four response packets) and use this to draw the
green solid box for each probe type.

These bars show that the BBG stability is high enough for there to be a
substantial number of blowback generators that persist across multiple rescans
over the course of multiple weeks. Recall that our first rescan occurs 6-9
days after the blowback responder discovery, and the entire scanning sequence
for a given protocol takes around three and a half weeks. Clearly, an attacker
has a large window to leverage blowback responders once they are identified.

At the same time, the stability of BBGs varies by probe type. TCP443 shows the
most stability with over 70% of the BBGs sending blowback in each rescan. On
the other hand, ICMP generally shows the least stability with around 35% of
the BBGs sending blowback in most rescans. While stability varies across probe
type, we find that for a given probe type the fraction of BBGs that send
blowback in rescans is fairly stable—within 10% across all probe types except
ICMP. For ICMP we found a drop-off of over 20% between the first and second
rescans after which the number of BBGs did not vary by more then 5% for the
remainder of the rescans.

The square dots on the plot indicate the fraction of BBGs sending blowback in
the first rescan. For most probe types the dot is at the top of the box,
indicating that the fraction of BBGs sending blowback tends to degrade over
time. However, this tendency is not absolute, and these fractions do not
always monotonically decrease over successive rescans. (In addition to the DNS
and NTP probes where the fraction of blowback-sending BBGs in the first rescan
is not the highest in the series, there were other instances of non-
monotonicity that the plot does not visualize.)

The non-monotonility observation above indicates churn among BBGs – some BBGs
come and go rather than simply aging out over time. Furthermore, we find that
many BBGs do not go away completely but continue to respond albeit with fewer
than the four packets required to be considered blowback. The blue hashed
boxes show the range of fractions of the BBGs that respond in the rescans
regardless of whether the response is blowback or not, with the square dots
reflecting the fractions of responsive BBGs in the first rescan. In all three
TCP types, at least 80% of BBGs identified in the full scan respond in some
fashion across all the rescans. For DNS and NTP, the prevalence is over 70%,
and even for ICMP, which shows less stability, it is over 75% in the first
rescan and around 55% in the rest of the rescans. These less active BBGs
provide additional ammunition for the attacker: even if these BBGs fail to
generate blowback, the attacker’s resources for probing these BBGs are not
wasted as each probe still produces at least one reflected packet towards the
victim.

###  3.3. BBG Activity Levels

(a) DNS

(b) ICMP

(c) NTP

(d) TCP443

Figure 2.  Distribution of response packets from blowback generators. Curves
labeled ”0” refer to the full scan; other curve labels correspond to the
rescan number reflected by the curve.

We consider how blowback generators differ in their activity levels. To this
end, we consider the distribution of activity levels (i.e., the number of
blowback packets and bytes generated) of persistent BBGs that responded in all
six rescans. Figure 2 provides cumulative counts of the packets generated by
the top-X (based on the activity observed in the full scan) BBGs to DNS, ICMP,
NTP, and TCP443 probes (other TCP probes, as well as byte activity
distributions, showed similar patterns). The common theme among all these
distributions is extremely uneven activity levels: relatively small numbers of
generators are responsible for disproportionately large amounts of blowback.
This is especially pronounced in the case of ICMP and NTP, where just a few
generators are responsible for vast majorities of blowback. Thus, an attacker
can obtain most of the attacking power from leveraging just a small fraction
of generators, which further lowers the bar for the attack. As an interesting
side note, there is no clear trend of decreasing blowback activity with time.
For instance, considering Figure 2b, the ICMP blowback activity level observed
in the first rescan exceeded that in the full scan, and the activity level in
the 5th rescan exceeded that in the 2nd rescan – as evidenced by the
cumulative packet counts reached in each rescan.

###  3.4. Blowback Origins

Date | Rescan | Tot. | Dominant | Packets from | Dominant | Packets from
---|---|---|---|---|---|---
|  | Packets | ANS | Dom. ASN | Country | Dom. Country
12/15-18/2020 | $R_{1,1-2}^{DNS}$ | 1.7–1.6M | 278 | 23.9–24.8% | US | 24.5–25.4%
12/21-31/2020 | $R_{1,3-6}^{DNS}$ | 1.7–2.1M | 5617 | 22.1–26.7% | Poland | 22.3–27.0%
12/16-19; 25-29/2020 | $R_{1,(1-2;4-5)}^{ICMP}$ | 68.1–239.0M | 8717 | 61.7-88.5% | Bulgaria | 61.7-88.5%
12/22/2020; 1/1/2021 | $R_{1,(3,6)}^{ICMP}$ | 31.2–34.8M | 8717 | 28.8-37.1% | Bulgaria | 28.8-37.2%
12/17/2020 | $R_{1,1}^{TCP443}$ | 2.3M | 3786 | 4.4% | US | 20.4%
12/20/2020-1/2/2021 | $R_{1,2-6}^{TCP443}$ | 2.7-2.8M | 5617 | 17.4-18.6% | Poland | 17.8-19.0%
2/21/2021-3/9/2021 | $R_{1,1-6}^{TCP80}$ | 2.9-3.6M | 5617 | 14.8–16.7% | US | 20.2–23.1%
2/23/2021-3/10/2021 | $R_{1,1-6}^{TCP25}$ | 1.5-1.7M | 5617 | 28.1–33.0% | Poland | 28.3-33.2%
2/24-27/2021 | $R_{1,1-2}^{NTP}$ | 8.2 – 10.1M | 2497 | 39.5–44.8% | Japan | 41.5 – 46.1%
3/02-08/2021 | $R_{1,3-6}^{NTP}$ | 25.3–36.0M | 2497 | 73.6–85.2% | Japan | 74.3–85.5%
Table 3.  Dominant origins of blowback traffic. Rescans with similar patterns
are grouped into one row. Note that the dominant AS may not be from the
dominant country.

We attempted to characterise geographical (i.e., country-level) and
topological (i.e., autonomous system-level) origins of blowback, based on the
volume of blowback traffic. We use pyasn (pyasn, ) (with RouteViews
(routeviews, ) data underneath) and GeoLite2 geolocation database from MaxMind
(geoip, ) (accessed through python-geoip (python-geoip, )), respectively, for
mapping an originator IP address to a country and autonomous system number
(ASN).

Table 3 shows blowback origins based on the volume of response packets, with
the origins attributed to the blowback generator (regardless of the sender of
a particular packet). Some protocols show distinct trends in geographical and
network origins of blowback. In particular, NTP blowback comes predominantly
from Japan from ASN 2497444While we focus on the first set of scanning series
in this paper, we note that two of the rescans in the second NTP series had
the US and ASN 33387 as the dominant traffic origins, with 25–26% (resp.,
16–17%) of traffic coming from this country (resp. AS)., and ICMP blowback
originates predominantly in Bulgaria’s ASN 8717. Poland and the US vie for the
top spot in the rest of the protocols, although their prevalence is in general
much lower than in some of the rescans with Japan’s and Bulgaria’s dominance.
Further, in the case of the US, it appears that its dominance comes from its
sheer size rather than a particular organization. Indeed, in all rescans with
the US dominance, it accounts for low-to-mid 20% of all response packets,
while having over 40% of all IP addresses according to MaxMind (geoip, ). This
contrasts with, e.g. Poland, which, in the rescan where it dominated with even
the lowest dominance, produced 17.8% of response packets vs. having only 0.6%
of all IP addresses, or Japan, producing 41.5-85.5% of response packets in
dominated rescans vs. having 5.4% of all IP addresses. Furthermore, the
dominant AS in rescans with US dominance actually belongs to another country
(ASN 278 from Mexico, 3786 from South Korea, and 5617 from Poland). In all
other cases, a single AS from the dominant country accounts for the
overwhelming majority of blowback from that country.

###  3.5. On Blowback Types

Protocol | Total | In-protocol | ICMP TTL | ICMP | ICMP | Other
---|---|---|---|---|---|---
| Packets | Packets | Expired | Redirect | Unreachable |
DNS | 4,686,571 | 4.34% | 36.66% | 29.25% | 26.18% | 3.57%
ICMP | 242,001,785 | 11.13% | 26.11% | 62.69% | 0.07% |  $\sim$0%
TCP443 | 7,210,796 | 53.02% | 21.60% | 20.35% | 4.71% | 0.32%
TCP25 | 4,532,306 | 39.14% | 20.47% | 33.69% | 6.65% | 0.05%
TCP80 | 9,018,095 | 58.79% | 16.18% | 20.39% | 4.15% | 0.49%
NTP | 24,614,773 | 55.70% | 33.97% | 4.46% | 5.19% | 0.68%
Table 4. Packet types of multipacket responses in the full scans.

In our incoming packet data, a significant number of response packets are ICMP
messages rather than in-protocol responses to our probes. This in itself is to
be expected as targets not operating a probed protocol can reasonably respond
with ICMP error messages such as ”Destination Unreachable” (various codes of
type-3 ICMP messages). However, we notice large fractions of ICMP messages
that we would not expect, namely ”TTL Expired” (type 11, code 0) and ”Host
Redirect” (type 5, code 1).

Table 4 depicts the proportions of the different types of response packets
received during our full scan, showing the above two ICMP message types to
represent from 36% (TCP80 scan) to as much as 89% (ICMP scan) of the blowback.
These messages, especially since they arrive in multiple copies, may indicate
routing misconfigurations.

Figure 3.  Routing loop prevalence among BBGs with persistent multipacket
response.

Given an unexpectedly large number of ”TTL Expired” ICMP messages, which
indicate a routing loop, we investigate directly the prevalence of routing
loops on the pathway to blowback generators. For each protocol, we ran
traceroutes to between 23,714 and 27,675 IP addresses randomly selected among
those that responded to all six of the corresponding rescans with multiple
packets, except for the NTP protocol, which only had 19,994 such responders so
we used all of them555The number of targets differ across the protocols
because we actually ran traceroutes to 30,000 random targets for each protocol
but later tightened the response-to-probe matching criteria to avoid potential
matching of unrelated background radiation, which disqualified different
number of targets for different protocols.. To reduce a change of an
incidental detection, we consider a path to have a loop when the same router
appears in the path three times. Figure 3 shows the prevalence of routing
loops to these hosts from our campus. It confirms a large incidence of routing
loops. At the extreme, over 60% of the NTP and ICMP targets had a routing loop
between our scanner and the destination. We consider these findings highly
unusual, especially taking into account that we collected the traceroute data
several weeks after the original scans and rescans. Although routing loops do
not explain the existence of blowback (since the loops still should not
produce multiple ICMP responses), the significant number of loops across all
protocols indicates the presence of misconfigurations in the destinations’
local networks – unless these messages are sent deliberately in response to
probing.

###  3.6. Examples of Response Timing Patterns

(a) DNS: 127,654 packets (b) DNS: 89,147 packets (c) ICMP: 56,232,930 packets
(d) ICMP: 2,791,675 packets

(e) NTP: 9,610,627 packets (f) NTP: 3,463,317 packets (g) TCP443: 48,189
packets (h) TCP443: 44,812 packets

Figure 4.  Examples of blowback responses.

The intrusiveness of blowback – whether in terms of the attack impact or the
experimental apparatus interference – depends on its timing patterns: more
concentrated blowback can have higher impact but for a shorter period of time.
Understanding blowback timing patterns might also provide insights for
distinguishing blowback from other traffic. We find that blowback generators
follow widely different timing patterns. This section provides some indicative
examples of some high-volume generators’ behaviors in this regard. Figure 4
illustrates these behaviors by showing the number of packets produced by a
certain generator in response to a given probe, in each second after the
probe.

Figures 4a and 4b present two DNS blowback generators producing roughly
similar amount of blowback. However, the first generator generates its
blowback over the course of 15 sec. after the probe, steadily ramping up its
sending rate every second until it reaches almost 25K packets per second
(pps), while the second generator generates its blowback over much longer
period of time – 600 sec. – but only at roughly 700-800 pps and using a
pulsating pattern, in which sending intervals interleave with periods of
silence. Other examples in Figure 4 provide more cases of pulsating patterns
(Figure 4f) and widely different duration and sending rates (e.g., compare
Figure 4c and d). The blowback from some generators seems bursty (Figure 4e)
and extremely regular from others (e.g., Figure 4h, where the generator sends
exactly 1 packet per second for hours; we assume the gaps in the figure may be
due to packet loss).

Our selected examples also show some staggering blowback volumes. A single
ping to the IP address in Figure 4c produces over 56M packets back! Other
responders in the figure all produce tens of thousand to millions of blowback
packets. Fortunately, as seen from Figure 2, the number of such prolific
blowback generators is rather small.

##  4\. Attack Potential

(a) Packets per second

(b) Bytes per second

Figure 5.  Blowback attack bandwidth (aggregated across six probe types).

We turn to assessing the impact potential of a blowback-leveraging attack. We
assume the attacker conducts a full scan, using its true scanner IP address,
to determine blowback generators and then probes the discovered generators
using the victim’s IP address as the source address of the probes, directing
blowback to the victim.

Consequently, we use the blowback observed in the first rescan (which, to
recall, involves generators found to produce at least 4 blowback packets
during the full scan) and simulate the attack assuming that all rescan probing
is done at the start of the attack. In other words, if a particular generator
was probed 100 sec from the start of the rescan in our experiment, all packet
arrivals from this responder are shifted by 100 sec. earlier in the
simulation.

Figure 5 shows blowback bandwidth in each second after the start of the
aggregated attack (i.e., using all six protocols/ports) in terms of packets
and bytes per second666 We stress that this analysis implies that simultaneous
probing with different protocols will produce cumulative blowback – the
assumption we have not tested experimentally.. By sending 850K packets and
38.4MB in the first second (adding the total number of probes and their byte
volume from Table 2), the attacker can trigger a blowback response of 9M
packets during the first second and ¿1M pps sustained over the first ten
seconds. In terms of data volume, in the first three seconds, the blowback
response is ¿100MBps – sufficient to saturate a common Ethernet link of 1Gbps.
Both packet and byte amplification for the first second is about 16x.
Furthermore, as these packets arrive from a large number of senders, they are
likely to impose a disproportionately high load on stateful intrusion
detection systems at the victim. While in absolute terms, the above numbers
are unlikely to overwhelm large server platforms and we leave the
experimentation with sustained and higher-volume attacks via repeated probing
of the same targets to future work, these numbers indicate a plausible potency
of the attack.

##  5\. Conclusions and Future Work

The Internet fundamentally contains a large number of hosts willing to respond
to packets from arbitrary senders, including hosts running various public
services (e.g., DNS, NTP, HTTP servers) and destinations simply complying with
the ICMP protocol, a ubiquitous network-level protocol on the Internet. An
attacker can use these hosts to direct reflected response traffic to their
victims, while researchers routinely scout the Internet for these hosts to
probe and measure various aspects of the Internet behavior. This paper takes a
first look at the phenomenon where a single probe to a target generates
multiple, sometimes numerous, packets in response – which we refer to as
”blowback”. Blowback has serious implications on both the researchers’
experimental setups to ensure they can cope with bursts of blowback traffic
and on security given the amplification capability that the blowback provides
to an attacker. We find that tens of thousands, and in some protocols,
hundreds of thousands, of hosts generate blowback, with orders of magnitude
amplification on average. However, these hosts differ vastly in the amount of
blowback they produce, and some generate millions of response packets in the
aftermath of a single probe. Furthermore, blowback generators are fairly
stable over periods of weeks, so once identified, many of these hosts can be
avoided by researchers (and exploited by attackers). Interestingly, routes to
a substantial number of blowback hosts from our scanner exhibit routing loops.
This, and occasional blowback spikes from some autonomous systems, suggest
potential misconfigurations in the destination networks. Our study represents
only the first step in investigating the blowback phenomenon. Key areas for
future work includes finer-grained analysis of blowback origins and an
experimental confirmation of the extent of the security thread due to the
blowback.

Acknowledgments: This work was supported in part by NSF through grant
CNS-2219736. Mark Allman of ICSI fully participated in this study and co-wrote
parts of the paper. We expect him to join us as a co-author for the conference
version of this paper once he completes his pass over the paper.

## References

  * [1] GeoLite2 Free Geolocation Data.  https://dev.maxmind.com/geoip/geolite2-free-geolocation-data.
  * [2] python-geoip.  https://pythonhosted.org/python-geoip/.
  * [3] University of Oregon Route Views Project.  https://www.routeviews.org/routeviews/.
  * [4] Rami Al-Dalky, Michael Rabinovich, and Kyle Schomp.  A look at the ecs behavior of dns resolvers.  In Proceedings of the Internet Measurement Conference, pages 116–129, 2019.
  * [5] Chad Brubaker, Suman Jana, Baishakhi Ray, Sarfraz Khurshid, and Vitaly Shmatikov.  Using frankencerts for automated adversarial testing of certificate validation in ssl/tls implementations.  In 2014 IEEE Symposium on Security and Privacy, pages 114–129. IEEE, 2014.
  * [6] Zakir Durumeric, James Kasten, Michael Bailey, and J Alex Halderman.  Analysis of the https certificate ecosystem.  In Proceedings of the 2013 conference on Internet measurement conference, pages 291–304, 2013.
  * [7] Zakir Durumeric, Eric Wustrow, and J Alex Halderman.  Zmap: Fast internet-wide scanning and its security applications.  In USENIX Security Symposium, volume 8, pages 47–53, 2013.
  * [8] Marc Kührer, Thomas Hupperich, Jonas Bushart, Christian Rossow, and Thorsten Holz.  Going wild: Large-scale classification of open dns resolvers.  In Proceedings of the 2015 Internet Measurement Conference, pages 355–368, 2015.
  * [9] Marc Kührer, Thomas Hupperich, Christian Rossow, and Thorsten Holz.  Exit from hell? reducing the impact of amplification ddos attacks.  In 23rd $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 14), pages 111–125, 2014.
  * [10] Rapid7 Labs.  SSL Certificates.  https://github.com/rapid7/sonar/wiki/SSL-Certificates; Accessed on May 2, 2023, 2023.
  * [11] Yevheniya Nosyk, Maciej Korczyński, and Andrzej Duda.  Routing loops as mega amplifiers for dns-based ddos attacks.  In Oliver Hohlfeld, Giovane Moura, and Cristel Pelsser, editors, Passive and Active Measurement, pages 629–644, 2022.
  * [12] Ruoming Pang, Vinod Yegneswaran, Paul Barford, Vern Paxson, and Larry Peterson.  Characteristics of internet background radiation.  In Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, pages 27–40, 2004.
  * [13] Jeman Park, Rhongho Jang, Manar Mohaisen, and David Mohaisen.  A large-scale behavioral analysis of the open dns resolvers on the internet.  IEEE/ACM Transactions on Networking, 30(1):76–89, 2021.
  * [14] pyasn: Python IP address to Autonomous System Number lookup module.  https://github.com/hadiasghari/pyasn.
  * [15] Christian Rossow.  Amplification hell: Revisiting network protocols for ddos abuse.  In NDSS, pages 1–15, 2014.
  * [16] Matthew Sargent, John Kristoff, Vern Paxson, and Mark Allman.  On the Potential Abuse of IGMP.  ACM Computer Communication Review, 47(1), January 2017.
  * [17] Ramin Yazdani, Roland van Rijswijk-Deij, Mattijs Jonker, and Anna Sperotto.  A matter of degree: characterizing the amplification power of open dns resolvers.  In Passive and Active Measurement: 23rd International Conference, PAM 2022, Virtual Event, March 28–30, 2022, Proceedings, pages 293–318. Springer, 2022.


# Neighborly partitions and the numerators
of Rogers-Ramanujan identities

Zahraa Mohsen, Hussein Mourtada

###### Abstract

We prove two partition identities which are dual to the Rogers-Ramanujan
identities. These identities are inspired by (and proved using) a
correspondence between three kinds of objects: a new type of partitions
(neighborly partitions), monomial ideals and some infinite graphs.

Keywords— Rogers-Ramanujan identities, Integer partitions, monomial ideals,
simple graphs, Hilbert series.

2020 Mathematics Subject Classification — 11P84,
11P81,05A17,05A19,05C31,13F55,13D40.

##  1 Introduction

Among the most famous and ubiquitous formulas involving $q-$series, we find
the Rogers-Ramanujan identities:

$\displaystyle\sum_{k=0}^{\infty}\frac{q^{k^{2}}}{(1-q)\cdots(1-q^{k})}$
$\displaystyle=$ $\displaystyle\frac{\prod\limits_{j\geq
1,\leavevmode\nobreak\ j\leavevmode\nobreak\ \equiv\leavevmode\nobreak\
0,\pm{2}\leavevmode\nobreak\ \mbox{mod}\leavevmode\nobreak\
5}(1-q^{j})}{\prod\limits_{j\geq 1}(1-q^{j})},$ (1)
$\displaystyle\sum_{k=0}^{\infty}\frac{q^{k^{2}+k}}{(1-q)\cdots(1-q^{k})}$
$\displaystyle=$ $\displaystyle\frac{\prod\limits_{j\geq
2,\leavevmode\nobreak\ j\leavevmode\nobreak\ \equiv\leavevmode\nobreak\
0,\pm{1}\leavevmode\nobreak\ \mbox{mod}\leavevmode\nobreak\
5}(1-q^{j})}{\prod\limits_{j\geq 2}(1-q^{j})}.$ (2)

On the left side of the identities, the term corresponding to $k=0$ is taken
to be $1.$ Usually the right side of this identity is written after the
obvious simplifications which allow to put $1$ in the numerators. We chose
this form, because the numerators play an important role in this article. As
revealed by MacMahon [18], these identities can be stated in the realm of the
theory of partitions: recall first that an integer partition of a positive
integer $n$ is simply a decreasing sequence of positive integers
$\lambda=(\lambda_{1},..,\lambda_{r})$, such that
$|\lambda|:=\lambda_{1}+\cdots+\lambda_{r}=n$. The $\lambda_{i}$’s are called
the parts of $\lambda$ and $r=:size(\lambda)$ is its size; see [6, 10] for
more about the theory of partitions.

######  Theorem 1.

(Rogers-Ramanujan identities) Let $n$ be a positive integer. For
$i\in\\{1,2\\}$, let $\mathcal{T}_{i}(n)$ be the set of partitions of $n$
without equal nor consecutive parts and the part $1$ appears at most $i-1$
times. Let $\mathcal{E}_{i}(n)$ be the number of partitions of $n$ into parts
congruent to $\pm{(2+i)}$ mod $5.$ Then we have

$\mid\mathcal{T}_{i}(n)\mid=\mid\mathcal{E}_{i}(n)\mid.$

The notation $\mid A\mid$ in the theorem stands for the cardinal of a set $A.$
Observe that the sums side in the $q-series$ identities corresponds to the
generating series of the $\mid\mathcal{T}_{i}(n)\mid$ (first for $i=2$ and
then for $i=1$) and the products side corresponds to the generating series of
the $\mid\mathcal{E}_{i}(n)\mid.$ These identities appear in many fields other
than combinatorics, such as statistical mechanics, number theory,
representation theory, algebraic geometry, probability theory or commutative
algebra [7, 9, 8, 14, 13, 11, 12, 16, 5, 1, 2, 3, 4].

The main goal of this article is to prove two identities which are in some
sense dual to the Rogers-Ramanujan identities. We begin by introducing the
notions appearing in these new identities: neighborly partitions, signature of
a neighbourly partition.

######  Definition 2.

For $i\in\\{1,2\\}$ and for a positive integer $n,$ we call neighborly
partitions of $n$ the set $\mathcal{N}_{i}(n)$ of partitions $\lambda$ of $n$
which satisfy the following properties:

  1. 1.

For every part $\lambda_{j}$ of $\lambda,$ there exists
$l\in\textbf{N}_{>0},\leavevmode\nobreak\ l\not=j$ such that
$\mid\lambda_{l}-\lambda_{j}\mid\leq 1.$

  2. 2.

The partition $\lambda$ has at most two equal parts.

  3. 3.

For every $l\in\textbf{N},\leavevmode\nobreak\ \leavevmode\nobreak\
\lambda_{l}\geq 3-i$ (i.e. for $i=1$, there are no parts equal to $1).$

The terminology $neighborly$ is inspired by the property 1. which says that
for every part $\lambda_{j}$ of $\lambda,$ there is a neighbor part
$\lambda_{l}$ of $\lambda$ which is equal or at a distance $1$ to
$\lambda_{j}.$ As an example, the integer $4$ has $5$ partitions:

$4=4=3+1=2+2=2+1+1=1+1+1+1.$

Then the neighborly partitions are

$\mathcal{N}_{1}(4)=\\{2+2\\},\leavevmode\nobreak\ \leavevmode\nobreak\
\mathcal{N}_{2}(4)=\\{2+2,2+1+1\\}.$

Note that the multiplicity (i.e. the number of occurrences) of a part of a
neighborly partition is at most two. With a neighborly partition $\lambda$, we
associate a graph $G_{\lambda}$ as follows: The set $V(G_{\lambda})$ of
vertices of $G_{\lambda}$ is in bijection with the set of parts of $\lambda;$
if $h$ is a part of $\lambda$ of multiplicity $1,$ the associated vertex is
called $x_{h};$ if $h$ is a part of $\lambda$ of multiplicity $2,$ the
vertices associated with the two equal parts are named respectively $x_{h}$
and $y_{h}.$ The set $E(G_{\lambda})$ of edges of $G_{\lambda}$ is given by

$E(G_{\lambda})=\\{(x_{h+1},x_{h}),(x_{l},y_{l}),\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{for every}\leavevmode\nobreak\ \leavevmode\nobreak\
x_{h+1},x_{h},x_{l},y_{l}\in V(G_{\lambda})\\}.$

For example $V(G_{2+1+1})=\\{x_{2},x_{1},y_{1}\\},$
$E(G_{2+1+1})=\\{(x_{2},x_{1}),(x_{1},y_{1})\\}$ and $G_{2+1+1}$ has the
following shape

$x_{1}$$y_{1}$$x_{2}$ Figure 1: $G_{2+1+1}$

A subgraph $H$ of $G_{\lambda}$ is said to be vertex-spanning if
$V(H)=V(G_{\lambda});$ it is said to be without isolated vertices if any
vertex of $H$ is an endpoint of some edge in $E(H).$

######  Definition 3.

Let $\lambda$ be a neighborly partition. We define the signature
$\delta(\lambda)$ of $\lambda$ by

$\delta(\lambda)=\sum_{H}(-1)^{\mid E(H)\mid},$

where $H$ ranges over the vertex spanning subgraphs of $G_{\lambda}$, which
have no isolated vertices and $\mid E(H)\mid$, as mentioned before, is the
cardinal of $E(H).$

We now are ready to state the main theorem. Let $n$ be a positive integer; for
$i\in\\{1,2\\},$ let $\mathcal{R}_{i}(n)$ be the set of partitions of $n$
whose parts are larger or equal to $3-i,$ distinct and congruent to $0$ or
$\pm{(i)}\leavevmode\nobreak\ $ mod $\leavevmode\nobreak\ 5.$

######  Theorem 4.

Let $n$ be a positive integer. For $i\in\\{1,2\\},$ we have the identities

$\sum_{\lambda\in\mathcal{N}_{i}(n)}\delta(\lambda)=\sum_{\lambda\in\mathcal{R}_{i}(n)}(-1)^{size(\lambda)}.$

######  Example 5.

  1. 1.

For $n=6$ and $i=1$, we have $\mathcal{N}_{1}(6)=\\{3+3\\}$ and
$\mathcal{R}_{1}(6)=\\{6\\}.$ The graph $G_{3+3}$ has the following shape

$x_{3}$$y_{3}$ Figure 2: $G_{3+3}$

and it has no (strict) subgraphs which are vertex-spanning without isolated
singularities. Hence, we have

$\sum_{\lambda\in\mathcal{N}_{1}(6)}\delta(\lambda)=\delta(3+3)=(-1)^{1}=\sum_{\lambda\in\mathcal{R}_{1}(6)}(-1)^{size(\lambda)}=(-1)^{size(6)}=(-1)^{1}.$

  2. 2.

For $n=6$ and $i=2$, we have $\mathcal{N}_{2}(6)=\\{3+3,3+2+1,2+2+1+1\\}$ and
$\mathcal{R}_{2}(6)=\phi.$ The graphs corresponding to the partitions
$3+3,3+2+1$ have no (strict) strict vertex-spanning subgraphs without isolated
singularities ; hence we have $\delta(3+3)=(-1)^{1}$ and
$\delta(3+2+1)=(-1)^{2}$. The graph $G_{2+2+1+1}$ has the shape

$x_{1}$$y_{1}$$x_{2}$$y_{2}$ Figure 3: $G_{2+2+1+1}$

and beside $G_{2+2+1+1}$ itself, its only vertex-spanning subgraph without
isolated singularities is

$x_{1}$$y_{1}$$x_{2}$$y_{2}$

Hence, we have $\delta(2+2+1+1)=(-1)^{3}+(-1)^{2}=0$ and

$\sum_{\lambda\in\mathcal{N}_{2}(6)}\delta(\lambda)=\delta(3+3)+\delta(3+2+1)+\delta(2+2+1+1)=-1+1+0=0=\sum_{\lambda\in\mathcal{R}_{2}(6)}(-1)^{size(\lambda)}.$

For $i\in\\{1,2\\},$ We set
$\mathcal{N}_{i}=\cup_{n\in\textbf{N}_{>0}}\mathcal{N}_{i}(n).$ By considering
the generating sequence of both sides of Theorem 4, we find the following
equivalent statement:

######  Corollary 6.

For $i\in\\{1,2\\},$ we have the identities

$\sum_{\lambda\in\mathcal{N}_{i}}\delta(\lambda)q^{\mid\lambda\mid}=\prod_{j\geq
3-i,j\leavevmode\nobreak\ \equiv\leavevmode\nobreak\
0,\pm{i}\leavevmode\nobreak\ \mbox{mod}\leavevmode\nobreak\ 5}(1-q^{j}).$

One observes that the right side of the identities in corollary 6 corresponds
to the numerators of the identities (1) and (2). As we will show later, the
left side of the identities in the theorem is related to the left side of the
identities (1) and (2). Here we use the Rogers-Ramanujan identities to prove
theorem 4. The proof of the main theorem is actually a proof that the Rogers-
Ramanujan identities are equivalent to corollary 6; in particular, a direct
proof (i.e. which does not use the Rogers-Ramanujan identities) of theorem 4
would also give a proof of the Rogers-Ramanujan identities.

##  2 Strategy and proof of the main result

We will divide the scheme of the proof into three steps which are the subject
of the three subsections of this section.

  1. 1.

For $i\in\\{1,2\\},$ we interpret the $q-$series
$\sum_{\lambda\in\mathcal{N}_{i}}\delta(\lambda)q^{\mid\lambda\mid}$ (see
corollary 6) in terms of a generating series $S_{i}$ ”counting” the subgraphs
of an infinite (simple) graph $G_{i}^{\infty}.$

  2. 2.

For $i\in\\{1,2\\},$ we give a formula relating $S_{i}$ to the Hilbert series
$\mathcal{H}_{i}$ of a graded ring which is the quotient of polynomial ring
with a (infinite) countable number of variables: In this step, we use the
notion of edge ideals, and the result that we prove is valid for any edge
ideal.

  3. 3.

For $i\in\\{1,2\\},$ we describe a formula relating $\mathcal{H}_{i}$ in terms
of the generating series of $\mid\mathcal{T}_{i}(n)\mid$ (see theorem 1). Then
we use the Rogers-Ramanujan identities to obtain the main results.

All the graphs that we will consider are simple, i.e they do not have more
than one edge between any two vertices and no edge starts and ends at the same
vertex.

###  2.1 Neighborly partitions and enumerating subgraphs

For $i\in\\{1,2\\},$ we begin by considering the infinite graph
$G_{i}^{\infty}$ whose set of vertices is
$V(G_{i}^{\infty})=\\{x_{j},y_{j};j\in\textbf{N},j\geq 3-i\\}$ and whose set
of edges is $E(G_{i}^{\infty})=\\{(x_{j},x_{j+1}),(x_{j},y_{j});j\geq 3-i\\}.$
Notice that for a neighborly partition $\lambda\in\mathcal{N}_{i},$ the graph
$G_{\lambda}$ is an induced subgraph of $G_{i}^{\infty}$ which has no isolated
vertices. So $G_{i}^{\infty}$ has the following shape

$x_{3-i}$$y_{3-i}$$x_{4-i}$$y_{4-i}$$x_{l-1}$$y_{l-1}$$x_{l}$$y_{l}$$\dots$$\dots$

Recall that a subgraph $H$ is said to be induced if an edge of $G$ is an edge
of $H$ whenever its endpoints are vertices of $H.$ In particular, such a
subgraph is completely determined by it vertices. Conversely any induced
subgraph of $G_{i}^{\infty},i=1,2,$ without isolated singularities is of the
type $G_{\lambda}$ for some $\lambda\in\mathcal{N}_{i}.$

######  Definition 7.

Let $G$ be a simple graph, let $V(G)=\\{v_{j},j\in I\\}$ be its set of
vertices that we assume countable. We call the multivariable subgraph
enumerating series of $G$ the series in the variables $(v_{j})_{j\in I}$ and
which is defined by

$S_{G}(\textbf{v},z)=\sum_{H}(\prod_{v_{j}\in V(H)}v_{j})z^{\mid E(H)\mid},$

where $H$ ranges over finite subgraphs of $G$ without isolated vertices and
where we denoted by v the multivariable $(v_{j})_{j\in I}.$

Note that, since we are only considering finite subgraphs, the monomials in
the multivariable subgraph enumerating series make intervene a finite number
of variables. We will express the series corollary 6 in terms of the
multivariable subgraph enumerating series of $G_{i}^{\infty},i=1,2.$ Recall
the vertices $v_{j}$ of $G_{i}^{\infty},i=1,2$ belong to
$\\{x_{j},y_{j};j\in\textbf{N},j\geq 3-i\\}.$ Denote by x the multivariable
$(x_{j})_{j\geq 3-i}$ and by y the multivariable $(y_{j})_{j\geq 3-i}.$

######  Lemma 8.

For $i\in\\{1,2\\},$ set
$S_{i}(\textbf{v},z):=S_{G_{i}^{\infty}}(\textbf{v},z)=S_{i}(\textbf{x},\textbf{y},z)$.
Let $S_{i}^{w}(q,z)$ be the series which is obtained from
$S_{i}(\textbf{x},\textbf{y},z)$ by substituting $x_{j}$ and $y_{j}$ by
$q^{j}.$ We have

$\sum_{\lambda\in\mathcal{N}_{i}}\delta(\lambda)q^{\mid\lambda\mid}=S_{i}^{w}(q,-1).$

###### Proof.

For $i\in\\{1,2\\},$ we have

$S_{i}(\textbf{v},z)=\sum_{H}(\prod_{v_{j}\in V(H)}v_{j})z^{\mid E(H)\mid}$
$=\sum_{V\subset V(G_{i}^{\infty})}(\sum_{\\{H;V(H)=V\\}}(\prod_{v_{j}\in
V}v_{j})z^{\mid E(H)\mid})=\sum_{V\subset V(G_{i}^{\infty})}(\prod_{v_{j}\in
V}v_{j})(\sum_{\\{H;V(H)=V\\}}z^{\mid E(H)\mid}),$

where $H$ ranges over finite subgraphs of $G_{i}^{\infty}$ without isolated
vertices and $V$ over the sets of vertices of such subgraphs $H.$ So we have
gathered the subgraphs which have the same set of vertices $V$ together. The
induced subgraph of $G_{i}^{\infty}$ whose set of vertices is such a $V$ is of
the form $G_{\lambda}$ for some $\lambda\in\mathcal{N}_{i}.$ In particular, if
we replace in $\prod_{v_{j}\in V}v_{j}$ the $x_{j}$’s and the $y_{j}$’s by
$q^{j},$ we obtain $q^{|\lambda|}.$ Moreover if we set
$\varphi(z)=\sum_{\\{H;V(H)=V\\}}z^{\mid E(H)\mid},$ we obtain by the
definition of the signature that $\delta(\lambda)=\varphi(-1)$ and the lemma
follows.

∎

###  2.2 Multigraded Hilbert series of Edge ideals and enumerating subgraphs

Let $G$ be a simple graph, let $V(G)=\\{v_{j},j\in I\\}$ be its set of
vertices that we assume countable or finite. Let $E(G)$ be set of edges of $G$
that we also assume countable or finite (this is sufficient for our purposes).
Let K be a field of zero characteristic. We consider the ring of polynomials
$A=\textbf{K}[\textbf{v}]=\textbf{K}[v_{j},j\in I]$ whose variables range in
the set of vertices $V(G).$ With the graph $G$ we associate its edge ideal
which is a square-free monomial ideal generated by

$\mathcal{I}(G)=<v_{j}v_{l}\mid(v_{j},v_{l})\in E(G)>.$

We are interested in the multigraded Hilbert series which counts the monomials
in the quotient ring of the polynomial ring by an edge ideal.

######  Definition 9.

Let $G$ be a simple graph as above. The multigraded Hilbert series of
$A/\mathcal{I}(G)$ is the series $\mathcal{H}_{G}$ in the variables
$v_{j},j\in I$ which is defined by

$\mathcal{H}_{A/\mathcal{I}(G)}(\textbf{v})=\mathcal{H}_{G}(\textbf{v})=\sum_{M\not\in\mathcal{I}(G)}M,$

where $M$ ranges over the monomials of $A$ (making intervene a finite number
of variables) which are not in the ideal $\mathcal{I}(G).$

Note that the multigraded Hilbert series of $A/\mathcal{I}(G)$ ”counts” the
monomials in $A$ which are not zero in $A/\mathcal{I}(G).$ We have the
following formula expressing the multigraded Hilbert series in terms of the
multivariable subgraph enumerating series.

######  Lemma 10.

Let $G$ be a simple graph as above. We have

$\mathcal{H}_{G}(\textbf{v})=\frac{S_{G}(\textbf{v},-1)}{\prod_{j\in
I}(1-v_{j})}.$

###### Proof.

First one remarks that (one may think of the one variable and then two
variables cases to be convinced)

$\mathcal{H}_{A}(\textbf{v})=\frac{1}{\prod_{j\in I}(1-v_{j})}.$

Now recall that a monomial belongs to a monomial ideal if and only if it is
divisible by at least one of its generators. Let $M=\\{m_{1},m_{2},\ldots\\}$
be the set of generators of $\mathcal{I}(G)$ which are in bijection with the
edges of $G.$ We have the formula

$\mathcal{H}_{A/\mathcal{I}(G)}(\textbf{v})=\mathcal{H}_{A}(\textbf{v})-\sum_{m\in
M}m\mathcal{H}_{A}(\textbf{v})$ $+\sum_{\\{m_{j_{1}},m_{j_{2}}\\}\subset
M}lcm(m_{j_{1}},m_{j_{2}})\mathcal{H}_{A}(\textbf{v})+\cdots+$
$(-1)^{k}\sum_{\\{m_{j_{1}},m_{j_{2}},\ldots,m_{j_{k}}\\}\subset
M}lcm(m_{j_{1}},m_{j_{2}},\ldots,m_{j_{k}})\mathcal{H}_{A}(\textbf{v})+\cdots=$
$\mathcal{H}_{A}(\textbf{v})[1-\sum_{m\in
M}m+\sum_{\\{m_{j_{1}},m_{j_{2}}\\}\subset M}lcm(m_{j_{1}},m_{j_{2}})+\cdots+$
$(-1)^{k}\sum_{\\{m_{j_{1}},m_{j_{2}},\ldots,m_{j_{k}}\\}\subset
M}lcm(m_{j_{1}},m_{j_{2}},\ldots,m_{j_{k}})+\cdots],$ (3)

where $lcm$ stands for the least common multiple. The formula expresses that
the (non-zero) monomials $A/\mathcal{I}(G)$ are the monomials in $A$ except
those which are divisible by one of the $m_{j}^{\prime}$s. When taking out the
monomials which are divisible by one of the $m_{j}$ (which is expressed by
$-\sum_{m\in M}m\mathcal{H}_{A}(\textbf{v})$), we take out twice those which
are divisible at the same time by some $m_{j_{1}}$ and $m_{j_{2}}$ (i.e. by
$lcm(m_{j_{1}},m_{j_{2}}$)); so we need to add once those which are divisible
by both (this is expressed by adding $\sum_{\\{m_{j_{1}},m_{j_{2}}\\}\subset
M}lcm(m_{j_{1}},m_{j_{2}})\mathcal{H}_{A}(\textbf{v}))$ hence adding twice
those which are divisible by three and so on: this is simply the inclusion
exclusion-principle since the monomials in $\mathcal{I}(G)$ are those which
belong to the union of the ideals generated by the $m_{j}^{\prime}$s. Now
remark that choice of $k$ monomials $m_{j_{1}},m_{j_{2}},\ldots,m_{j_{k}}$
corresponds to the choice of $k$ edges of $G,$ i.e. a subgraph of $G$ having
$k$ edges and the variables appearing in the associated monomial (which are
square free, the graph $G$ being simple) correspond to vertices of this
subgraph; hence we have

$1-\sum_{m\in
M}m+\cdots+(-1)^{k}\sum_{\\{m_{j_{1}},m_{j_{2}},\ldots,m_{j_{k}}\\}\subset
M}lcm(m_{j_{1}},m_{j_{2}},\ldots,m_{j_{k}})+\cdots=S_{G}(\textbf{v},-1)$

and the proposition follows.

∎

######  Remark 11.

  1. 1.

Note that the formula (3) in lemma 10 can also be seen as a direct application
of the Taylor resolution (see [20]) of the monomial ideal $\mathcal{I}(G).$

  2. 2.

A variant of the formula in lemma 10 exists in the literature, often for
special gradings [15]; however, this exact statement will be needed in the
next subsection and the proof makes the paper self-contained.

###  2.3 Proof of the main result

For $i=1,2$ we now consider the $\textbf{K}-$algebra
$\mathcal{P}_{i}:=K[x_{j},y_{j},j\geq 3-i]/\mathcal{I}(G_{i}^{\infty})$ which,
by definition of the ideal $\mathcal{I}(G_{i}^{\infty})$ is equal to

$\frac{\textbf{K}[x_{j},y_{j},j\geq 3-i]}{<x_{j}y_{j},x_{j}x_{j+1},j\geq
3-i>}.$

By giving to $x_{j}$ and $y_{j},$ for $j\geq 3-i,$ the weight $j,$ the algebra
$\mathcal{P}$ inherits the structure of a graded algebra, i.e. we can write

$\mathcal{P}_{i}=\oplus_{h\in\textbf{Z}_{\geq 0}}\mathcal{P}_{i,h}$

where the $\mathcal{P}_{i,h}$’s are additive groups satisfying
$\mathcal{P}_{i,h}.\mathcal{P}_{i,h^{\prime}}\subset\mathcal{P}_{i,h+h^{\prime}}.$
By abuse of notation, the $\mathcal{P}_{i,h}$ is a $\textbf{K}-$ vector space
generated by all the monomials which does not belong to
$\mathcal{I}(G_{i}^{\infty})$ and which have weight equal to $h.$ The Hilbert-
Poincaré series of the graded algebra $\mathcal{P}_{i}$ is by definition

$\mathcal{HP}_{\mathcal{P}_{i}}(q):=\sum_{h\in\textbf{Z}_{\geq
0}}dim_{\textbf{K}}\mathcal{P}_{i,h}q^{h}.$

One notices that the monomials in the varaibles $x_{j},y_{j}$ which are of
weight $h$ are exactly those such that when we replace $x_{j}$ and $y_{j}$ by
$q^{j},$ we obtain $q^{h}:$ for instance, $x_{j}x_{j^{\prime}}$ is of weight
$j+j^{\prime}$ and the mentioned substitution gives $q^{j+j^{\prime}}.$ Hence,
if we set $\mathcal{H}^{w}_{\mathcal{P}_{i}}(q)$ to be the series which is
obtained from $\mathcal{H}_{G_{i}^{\infty}}(\textbf{v})$ (see Definition 9) by
substituting $x_{j}$ and $y_{j}$ by $q^{j}$ we find

$\mathcal{HP}_{\mathcal{P}_{i}}(q)=\mathcal{H}^{w}_{\mathcal{P}_{i}}(q).$

Applying lemma 10 and lemma 8 we deduce the following:

######  Proposition 12.

We have

$\mathcal{HP}_{\mathcal{P}_{i}}(q)=\frac{\sum_{\lambda\in\mathcal{N}_{i}}\delta(\lambda)q^{\mid\lambda\mid}}{\prod_{j\geq
3-i}(1-q^{j})^{2}}.$

To make the link with Rogers-Ramanujan identities we will consider
polarization of monomial ideals: this is a procedure that allows to associate
with a monomial ideal a squarefree monomial ideal in a polynomial ring which
has more variables. The interesting fact is that invariants of both ideals are
very related. The procedure amounts to replace any power of the type $x^{e}$
(in some polynomial ring having $x$ as a variable) by the monomial
$xy_{1}\ldots y_{e-1}$ where the $y_{i}$ are variables in a new polynomial
ring extending the variables in the original polynomial ring. By applying this
process to the generators of a monomial ideal, we obtain a squarefree monomial
ideal. The important examples for us are the ideals

$\mathcal{I}(G_{i}^{\infty})=<x_{j}y_{j},x_{j}x_{j+1},j\geq
3-i>\subset\textbf{K}[x_{j},y_{j},j\geq 3-i],\ \text{for}\ i=1,2.$

These are the polarization (this is why we called our ring above
$\mathcal{P}_{i}$) of the ideals

$<x_{j}^{2},x_{j}x_{j+1},j\geq 3-i>\subset\textbf{K}[x_{j},j\geq 3-i],$

where the grading is induced from giving to $x_{j}$ the weight $j.$ We have
the following (Corollary 1.6.3 in [17], see also [19, 20]):

$\mathcal{HP}_{\mathcal{P}_{i}}(q)=\frac{\mathcal{HP}_{\textbf{K}[x_{j},j\geq
3-i]/<x_{j}^{2},x_{j}x_{j+1},j\geq 3-i>}(q)}{\prod_{j\geq 3-i}(1-q^{j})}.$ (4)

Note that, in loc. cit., the proof is given for finitely generated ideals. But
this extends easily to our situation. Indeed, the $\textbf{K}-$ algebra

$R:=\textbf{K}[x_{j},j\geq 3-i]/<x_{j}^{2},x_{j}x_{j+1},j\geq 3-i>$

is the inductive limit of the $\textbf{K}-$finitely generated algebra

$R_{n}=\textbf{K}[x_{j},3-i\leq j\leq n+1]/<x_{j}^{2},x_{j}x_{j+1},3-i\leq
j\leq n>.$

Moreover, since the weights of the variables $x_{j}$ are growing we can see
that

$\mathcal{HP}_{R_{n}}(q)=\mathcal{HP}_{R}(q)\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{modulo}\leavevmode\nobreak\ \leavevmode\nobreak\
q^{n}.$

This implies

$\lim\limits_{n\rightarrow+\infty}\mathcal{HP}_{R_{n}}(q)=\mathcal{HP}_{R}(q),$

and that the case of finitely generated ideals gives the equality (4).

Now everything is settled down for the proof of Corollary 6 (which is
equivalent to Theorem 4).

###### Proof.

On one hand, from Proposition 12 and the equality (4) we otain that for
$i\in\\{1,2\\}$ we have

$\frac{\sum_{\lambda\in\mathcal{N}_{i}}\delta(\lambda)q^{\mid\lambda\mid}}{\prod_{j\geq
3-i}(1-q^{j})^{2}}=\frac{\mathcal{HP}_{\textbf{K}[x_{j},j\geq
3-i]/<x_{j}^{2},x_{j}x_{j+1},j\geq 3-i>}(q)}{\prod_{j\geq 3-i}(1-q^{j})}.$ (5)

On the other hand, the homogeneous components of weight $h$ of

$R=\frac{\textbf{K}[x_{j},j\geq 3-i]}{<x_{j}^{2},x_{j}x_{j+1},j\geq 3-i>}$

is generated by the monomials $x_{i_{1}}\cdots x_{i_{r}}$ such that
$i_{1}+\cdots+i_{r}=h$ and which are not divisible by neither $x_{j}^{2}$ nor
$x_{j}x_{j+1},$ for any $j\in\textbf{N}.$ So the data of such a monomial is
equivalent to the data of a partitions of $h$ without equal nor consecutive
parts and the part $1$ appears at most $i-1$ times (because of the condition
$j\geq 3-i$ in the indices of the variables $x_{j}$). Hence we have

$\mathcal{HP}_{R}(q)=\sum_{h\geq 0}\mid\mathcal{T}_{i}(h)\mid q^{h},$

which is the left side of the identities (1) (for $i=2)$ and of (2) (for
$i=1).$ From the equalities (5), (1) and (2), we get that for $i\in\\{1,2\\},$
we have:

$\frac{\sum_{\lambda\in\mathcal{N}_{i}}\delta(\lambda)q^{\mid\lambda\mid}}{\prod\limits_{j\geq
3-i}(1-q^{j})}=\frac{\prod\limits_{j\geq 3-i,\leavevmode\nobreak\
j\leavevmode\nobreak\ \equiv\leavevmode\nobreak\ 0,\pm{i}\leavevmode\nobreak\
\mbox{mod}\leavevmode\nobreak\ 5}(1-q^{j})}{\prod\limits_{j\geq
3-i}(1-q^{j})},$

and the theorem follows.

∎

Acknowledgment The first author would like to acknowledge the National Council
for Scientific Research of Lebanon (CNRS-L) and the Agence Universitaire de la
Francophonie in cooperation with Lebanese University for granting a doctoral
fellowship to her.

## References

  * [1] P. Afsharijoo, Looking for a new version of Gordon’s identities, Ann. Comb. 25 (2021), no. 3, 543–571.
  * [2] P. Afsharijoo, Even–odd partition identities of Rogers–Ramanujan type, Ramanujan J (2021). https://doi.org/10.1007/s11139-021-00470-3.
  * [3] P. Afsharijoo, J. Dousse, F. Jouhet, and H. Mourtada, Andrews-Gordon identities and commutative algebra, preprint arxiv.org/abs/2104.09422 (2021).
  * [4] P. Afsharijoo, J. Dousse, F. Jouhet, and H. Mourtada, New companions to Gordon identities from commutative algebra, preprint.
  * [5] P. Afsharijoo and H. Mourtada, Partition identities and application to finite dimensional Gröbner basis and vice versa, Arc Schemes and Singularities, World Scientific Publishing, pp. 145-161 (2020).
  * [6] G. E. Andrews, The theory of partitions, Encyclopedia of mathematics and its applications, Vol. 2, Addison-Wesley, Reading, Massachusetts, 1976.
  * [7] G. E. Andrews, $q$-series: their development and application in analysis, number theory, combinatorics, physics and computer algebra, CBMS Regional Conference Series in Mathematics, 66, AMS, Providence, 1986.
  * [8] G. E. Andrews, A. Schilling, and S.O. Warnaar, An $A_{2}$ Bailey lemma and Rogers–Ramanujan-type identities, J. Amer. Math. Soc. 12 (1999), 677–702.
  * [9] R. J. Baxter, Hard hexagons: exact solution, J. Phys. A 13 (1980), no. 3, L6–L70.
  * [10] B. Berndt, Number theory in the spirit of Ramanujan, Student Mathematical Library, 34. American Mathematical Society, Providence, RI, 2006. xx+187 pp.
  * [11] C. Bruschek, H. Mourtada, and J. Schepers, Arc spaces and Rogers-Ramanujan identities, The Ramanujan J. 30 (2013), 9–38.
  * [12] C. Bruschek, H. Mourtada, and J. Schepers, Arc spaces and Rogers-Ramanujan Identities, Discrete Mathematics and Theoretical Computer Science Proceedings, FPSAC (2011), 211–220.
  * [13] J. Fulman, _A Probabilistic Proof of the Rogers–Ramanujan Identities_ , Bulletin of the London Mathematical Society, Volume 33, Issue 4, July 2001, Pages 397–407.
  * [14] K. Garrett, M. E. H. Ismail, and D. Stanton, Variants of the Rogers-Ramanujan Identities, Adv. in Appl. Math. 23 (1999), 274–299.
  * [15] A. Goodarzi, On the Hilbert series of monomial ideals, J. Combin. Theory Ser. A 120 (2013), no. 2, 315–317.
  * [16] M. J. Griffin, K. Ono, and S. O. Warnaar, _Framework of Rogers-Ramanujan identities and their arithmetic properties_ , Duke Math. J. 165 (2016), no. 8, 147–1527.
  * [17] J. Herzog, T. Hibi, _Monomial ideals_ , Graduate Texts in Mathematics, 260. Springer-Verlag London, Ltd., London, 2011. xvi+305 pp.
  * [18] P. A. MacMahon, Combinatory Analysis, Volume 2, Cambridge University Press, Cambridge, 1916.
  * [19] E. Miller, B. Sturmfels, Combinatorial commutative algebra, Graduate Texts in Mathematics, 227. Springer-Verlag, New York, 2005. xiv+417 pp.
  * [20] I. Peeva, Graded syzygies, Algebra and Applications, 14. Springer-Verlag London, Ltd., London, 2011. xii+302 pp.

[Z. Mohsen] Université de Paris, Sorbonne Université, CNRS, Institut de
Mathématiques de Jussieu-Paris Rive Gauche, F-75013 Paris, France and
Department of Mathematics, Lebanese University, Hadath, Beirut, Lebanon
<EMAIL_ADDRESS>

[H. Mourtada] Université de Paris, Sorbonne Université, CNRS, Institut de
Mathématiques de Jussieu-Paris Rive Gauche, F-75013 Paris, France
<EMAIL_ADDRESS>