# HyperLogLog (HLL) Security: Inflating Cardinality Estimates

Pedro Reviriego
Universidad Carlos III de Madrid
Leganés 28911, Madrid, Spain
email<EMAIL_ADDRESS>
&Pablo Adell
Universidad Carlos III de Madrid
Leganés 28911, Madrid, Spain
email<EMAIL_ADDRESS>
&Daniel Ting
Tableau Software
Seattle, Washington, USA
email<EMAIL_ADDRESS>

###### Abstract

Counting the number of distinct elements on a set is needed in many
applications, for example to track the number of unique users in Internet
services or the number of distinct flows on a network. In many cases, an
estimate rather than the exact value is sufficient and thus many algorithms
for cardinality estimation that significantly reduce the memory and
computation requirements have been proposed. Among them, Hyperloglog has been
widely adopted in both software and hardware implementations. The security of
Hyperloglog has been recently studied showing that an attacker can create a
set of elements that produces a cardinality estimate that is much smaller than
the real cardinality of the set. This set can be used for example to evade
detection systems that use Hyperloglog. In this paper, the security of
Hyperloglog is considered from the opposite angle: the attacker wants to
create a small set that when inserted on the Hyperloglog produces a large
cardinality estimate. This set can be used to trigger false alarms in
detection systems that use Hyperloglog but more interestingly, it can be
potentially used to inflate the visits to websites or the number of hits of
online advertisements. Our analysis shows that an attacker can create a set
with a number of elements equal to the number of registers used in the
Hyperloglog implementation that produces any arbitrary cardinality estimate.
This has been validated in two commercial implementations of Hyperloglog:
Presto and Redis. Based on those results, we also consider the protection of
Hyperloglog against such an attack.

##  1 Introduction

Count distinct or cardinality estimation is widely used in many computing and
networking applications [1]. For example, detecting changes in the number of
connections or active nodes on a network may be an indication of a cyber-
attack or a network scanning [2],[3]. Similarly, it is useful to identify
nodes that have many active connections on a network [4] and cardinality
estimation is also useful to detect the spreading of worms [5]. In computing,
cardinality estimation is also widely used for example to estimate the number
of distinct users on a website and it is supported in most data processing
libraries and databases [6],[7],[8].

An exact count of the number of distinct elements on a large set is costly and
needs memory that is linear on the cardinality of the set. As in many
applications, a reasonably accurate estimate is enough, many cardinality
estimation algorithms have been proposed among which Hyperloglog [9] is widely
used [6],[7],[8],[10]. Hyperloglog uses a small number of registers, each
having only a few bits to accurately estimate any practical cardinality value.
This means that cardinality estimation can be implemented with a small memory
footprint. Additionally, the operations to insert elements on the Hyperloglog
are simple and only one memory access is needed per insertion.

As Hyperloglog is used today in many systems, its privacy and security become
important and have been recently studied [11],[12]. In particular, for the
security, it has been shown that an attacker that has no knowledge of the
Hyperloglog implementation details can create a set of elements with large
cardinality for which Hyperloglog produces a much smaller estimate. This could
be used by an attacker to evade Hyperloglog based detection when performing
for example a denial of service attack or network scan [2],[3].

In this paper, Hyperloglog’s security is studied from the opposite angle: an
attacker that wants to create a set of elements that when inserted on the
Hyperloglog will produce an estimate that is much larger than the number of
elements in the set. This set can then be used by the attacker to for example
trigger false alarms on Hyperloglog based detection systems but more
importantly, also to inflate the estimates of the number of users, number of
hits and similar performance metrics used for Internet services when estimated
using Hyperloglog. The analysis shows that the attacker can create a set with
the same number of elements as registers in the Hyperloglog (typically at most
a few thousands) that produces any arbitrarily large cardinality value on the
Hyperloglog cardinality estimation. This has been verified on two commercial
implementations of Hyperloglog [7],[8]. This is done without any knowledge of
the Hyperloglog’s implementation, which is worrying given the wide adoption of
Hyperloglog. Fortunately, the protection scheme proposed in [12] to detect
attacks that reduced the Hyperloglog estimate can also be used to protect
against this new attack that inflates the Hyperloglog estimate.

The rest of the paper is organized as follows: the next section briefly
discusses the Hyperloglog algorithm. Then, in section 3 the adversarial model
and the proposed attack are presented and the detection of the attack is also
briefly discussed. The attack is evaluated in section 4 and the paper ends
with the conclusion in section 5.

##  2 HyperLogLog

As discussed in the introduction, HyperLogLog (HLL) is a data sketch that
efficiently estimates number of unique elements in a data stream [9]. It is
formed by an array of $R$ registers $r_{1},\ldots,r_{R}$ each having a small
number of bits, typically four or five. To insert an element $x$ in the
sketch, it is first mapped to one register $r_{h(x)}$ using a hash function
$h(x)$. A second hash function $g(x)$ is used to generate a value $v(x)$ that
is computed as one plus the number of leading zeros in the bit representation
of $g(x)$. If $v(x)$ is larger than the value stored in register $r_{h(x)}$,
then it is written on the register such that each register keeps the maximum
value for all elements mapped to that register.

Figure 1 illustrates an Hyperloglog showing the insertion of element $x$ that
is mapped to register $i$ and has a value $v(x)=4$. Since the register stores
a value of 3 that is smaller, the new value is written to the register as
shown in the Figure. The probability of a register having a value with $t_{z}$
leading zeros is related to the number of elements mapped to the counter in an
exponential way. This enables the registers to cover a wide range of
cardinalities using only a few bits.

Figure 1: Example of a register update in HLL

To estimate the cardinality, Hyperloglog first computes the inverse of the
harmonic mean of the registers contents as follows:

$Z=\sum_{i=1}^{R}2^{-r_{i}},$ (1)

where $r_{i}$ is the value of the $i^{th}$ register.

Then by multiplying by a constant factor given in [9] that depends on the
number of counters $R$, the cardinality estimate is obtained as:

$C_{HLL}={\alpha}_{R}\frac{R^{2}}{Z}$ (2)

For cardinalities that are much larger than the number of registers $R$, the
relative error of the HLL estimate is approximately $\frac{1.04\cdot
C}{\sqrt{R}}$ where $C$ is the true cardinality. Therefore, by selecting the
number of registers $R$, the desired accuracy can be obtained. For example
with 1024 registers, the relative error is approximately 3%. When the
cardinality $C$ is comparable to $R$ or smaller, the estimate provided with
equation 2 is worse and thus alternative estimates are used. The original
Hyperloglog algorithm [9] proposed using each register as a bit of a Linear
Probabilistic Counting Array (LPCA) [13]. In more detail, the bit is one when
the value of the register is different from zero and zero when it is zero.
Recently, more sophisticated estimates for low cardinalities have been
proposed [14].

Hyperloglog sketches that use the same hash functions $g(x)$ and $h(x)$ can be
merged to compute the cardinality of the union of their data streams. To do
so, a new sketch is created by taking for each register the maximum of values
of the same register across all the merged sketches. This merging is useful in
many applications.

Before moving to the next section, an interesting observation is that once all
elements in the data stream have been inserted, the set
$X={x_{1},x_{2},...,x_{R}}$ formed by $R$ elements each mapping to one
register such that $x_{i}$ maps to register $i$ and has value
$v(x_{i})=r_{i}(x)$ would produce the same Hyperloglog estimation as the
entire data stream.

##  3 Inflating HyperLogLog Cardinality Estimates

This section first presents the model considered for the attacker. Then the
proposed attacked is presented and finally the protection against such an
attack is briefly discussed.

###  3.1 Adversarial Model

The assumption is that the attacker can create Hyperloglog instances that use
the same hash functions as the target Hyperloglog instance being attacked,
perform insertions, and check the Hyperloglog estimate. Using the same hash
functions is critical in many applications of Hyperloglog as it allows
Hyperloglog sketches to be merged to compute cardinalities of unions. On the
other hand, the attacker has no information on the specific implementation of
Hyperloglog. In particular the hash functions $g$ and $h$ and the number of
registers $R$ are not known. Information about an item $x$’s hash values
$g(x),h(x)$ can only be obtained indirectly through observing cardinality
estimates before and after inserting $x$ into a Hyperloglog instance. This
attacker model is the same as the one considered in our previous work [12].

###  3.2 Inflating Hyperloglog (HLL) Estimates

Let us consider a set of elements $S$ with cardinality $C$. After inserting
the elements in $S$ on an HLL with $R$ registers, by construction of the HLL
instance, for each register $i$ there is an element $x_{i}$ that maps to the
register and has its final value $v(x_{i})=r_{i}(x)$. Therefore, if we can
identify those $R$ elements $X={x_{1},x_{2},...,x_{R}}$, by inserting them on
the HLL, the cardinality estimate would be $C$ instead of $R$. This means that
the cardinality estimate of HLL can be set to any arbitrary value $C$ using a
set of only $R$ elements. However, finding those $R$ elements without having
any details on how the HLL is implemented does not seem to be straightforward.

To find those $R$ elements, we first insert the elements in set $S$ on an
empty HLL and after inserting each element $y$ we check if it has increased
the HLL estimate and if so we add it to an initial set $Y$. This set will in
general be different from $X$. This is due on one hand to the fact that when
inserting elements from $S$ on register $i$, the register can take several
intermediate values until reaching its final value $r_{i}$. Then, the elements
that correspond to those intermediate values will be inserted on set $Y$ if
they increment the HLL estimate. On the other hand, if the cardinality
estimates are rounded to the nearest integer, there may be cases in which
inserting the element $x_{i}$ that sets the final value $r_{i}$ does not
increment the HLL estimate and thus $x_{i}$ would not be added to $Y$. This
can occur if the HLL implementation uses the LPCA estimate for low
cardinalities as discussed in the previous section. Then when few elements
have been inserted if there is an element already mapped to register $i$,
inserting $x_{i}$ will not increment the LPCA estimate (as the LPCA bit was
already a one after the first element was inserted) and thus $x_{i}$ will not
be added to $Y$. When more elements have been inserted into the HLL instance
so that the HLL estimate is used, if the register has a value that is large
relative to the number of elements that have been inserted so far,
incrementing its value may also not increase the HLL estimate and thus again
$x_{i}$ may also not be inserted on $Y$. Therefore, this initial set $Y$ will
have both elements that are not in $X$ and miss elements from $X$. An initial
analysis of the impact of the missing elements on the HLL cardinality estimate
is presented in the Appendix. A more detailed analysis is left for future
work.

To illustrate those cases, let us consider an HLL with $R=1024$ registers an a
set $S$ with a cardinality $C=100,000$. Then on average approximately 100
elements would map to each register. Let us focus on register $i$ and assume
that there are two elements $a$ and $b$ that map to that register with values
$v(a)=3$ and $v(b)=4$ and that both are the first two elements inserted on the
HLL. Then, if the HLL uses the LPCA estimate for low cardinalities, the
estimate would depend only on the number of registers that are not zero and
this will only change when inserting $a$ so that $b$ will not be added to $Y$.
Now, let us consider another register $j$ to which also two elements $c$ and
$d$ map with $v(c)=7$ and $v(d)=8$ and that both are added when the
cardinality estimate for HLL is already 5,000. Then the sum of the values of
the HLL registers used in the denominator of equation 2 would be approximately
150 on average. Changing the value of register $j$ from 0 to 7 when inserting
$c$ would decrease the average to approximately 149, thus increasing the
cardinality by approximately $5000/149\approx 34>1$. A subsequent insertion of
$d$ would introduce a small change in the HLL estimate that is approximately
$2^{-8}$ times smaller and thus lower than one and likely not detectable if
estimates are rounded. Therefore, $d$ is not added to the set. Finally, let us
consider a third register $k$ to which elements $e$ and $f$ map with $v(e)=3$
and $v(f)=4$ and both are added when the HLL estimate is already close to
100,000. Then, both will increment the HLL estimate and thus will be added to
the set $Y$. These three cases show how elements in $X$ may not be added to
$Y$ and also how additional elements that are not in $X$ can be added to $Y$.
However, the initial set $Y$ should produce an HLL estimate that is reasonably
close to $C$ and thus can be used as an initial step to build set $X$.

Once set $Y$ has been constructed, to identify the missing elements from $X$,
we can do the following. Build a new HLL and insert only the elements in $Y$.
Then insert all the elements in $S$ and add those that increment the HLL
estimate to $Y$. Now, since the cardinality estimate for $Y$ would be larger
than the range for which the LPCA is used and close to $C$, the missing
elements from $X$ should increase the cardinality estimate and thus would be
added to $Y$.

Finally, to obtain the final set, we can build another empty HLL and insert
the elements from $Y$ in reverse order. That is the elements that were added
last to $Y$ are inserted first. After inserting each element, we check if the
HLL estimate has increased and if so we add the element to a new set $V$. This
procedure by construction will select for each register, the element in $Y$
that has the maximum value and thus set $V$ will tend to be the same or very
similar to set $X$. The entire algorithm is summarized in Algorithm 1.

Algorithm 1 Procedure to generate the attack set $V$

1:construct a set $S$ with the target cardinality $C$.

2:construct an empty HLL instance.

3:construct empty sets $Y$ and $V$.

4:—- PHASE 1: build the initial version of $Y$ —-

5:for $s$ in $S$ do

6: get HLL estimate $HLL_{before}$.

7: insert $s$ on the HLL.

8: get HLL estimate $HLL_{after}$.

9: if $HLL_{after}>HLL_{before}$ then

10: add $s$ to set $Y$.

11: end if

12:end for

13:—- PHASE 2: add missing elements to $Y$ —-

14:construct an empty HLL instance.

15:for $y$ in $Y$ do

16: insert $y$ on the HLL.

17:end for

18:for $s$ in $S$ do

19: get HLL estimate $HLL_{before}$.

20: insert $s$ on the HLL.

21: get HLL estimate $HLL_{after}$.

22: if $HLL_{after}>HLL_{before}$ then

23: add $s$ to set $Y$.

24: end if

25:end for

26:—- PHASE 3: build $V$ from $Y$ —-

27:construct an empty HLL instance.

28:for $y$ in $Y$ starting from last to first inserted do

29: get HLL estimate $HLL_{before}$.

30: insert $y$ on the HLL.

31: get HLL estimate $HLL_{after}$.

32: if $HLL_{after}>HLL_{before}$ then

33: add $y$ to set $V$.

34: end if

35:end for

From the description of the algorithm, it can be seen that the number of
operations required on the Hyperloglog to build an attack set of $R$ elements
that produces a cardinality estimate of $C$ is $O(C)$. That means that the
complexity of the attack is of the same order to that of inserting a set of
$C$ elements on the Hyperloglog and thus it would be feasible to build attack
sets for common cardinality values.

###  3.3 Protecting Against the Attack

The attack described in the previous subsection poses a challenge to
Hyperloglog security and thus it is important to discuss what can be done to
detect and prevent the attack. The use of a random salt in the hash functions
$h(x)$ and $g(x)$ so that each Hyperloglog instance is different is one
alternative, but as discussed in [12], it means that Hyperloglog sketches can
no longer be merged, which is a key feature for many applications. An
alternative to detect the attack could be the use of two Hyperloglog sketches:
the main one not salted so that it can be merged and an auxiliary one salted
as proposed in [12]. Then, if the estimates of the two sketches are
significantly different, an attack is detected. This Salted Not Salted (SNS)
protection proposed in [12] to detect attacks that try to reduce the
Hyperloglog estimate can also detect the inflating attack described in the
previous subsection.

Simpler techniques may also be used to detect the attack. For example, logging
the percentage of Hyperloglog insertions that increase the register values and
the average increment of the value. In a normal state, only a small fraction
of the insertions would increment the register values once the cardinality
estimate is larger than $R$. The average increment on the value would also be
small with one having a probability of approximately 50%, two of 25%, three of
12.5% and so on giving an average of close to two. Therefore, if at some point
either a large fraction of the insertions increment the value or the average
increment is large, an attack is detected. The detailed study of these
detection schemes is left for future work.

##  4 Evaluation

The proposed attack has been implemented in Redis [7] that uses a default
Hyperloglog implementation with $R=16384$ and in Presto [8] that uses by
default $R=4096$ registers111The code for the attack both for Redis and Presto
is available in https://github.com/adell13pablo/hll_attack. For Redis, the
estimated cardinalities for the attack set on phases 1,2,3 are shown in Figure
2 and the attack set sizes on Figure 3. It can be seen that the attack
achieves the same cardinality estimate as that of the entire set in phase 2
and phase 3. In phase 1, the attack set produces also a large cardinality
estimate but smaller than that of the original set. This is inline with the
expected results. Finally, the attack size is significantly reduced in phase 3
bringing very close to the value of $R$ again as expected.

After validating the attack in Redis, it was also implemented in Presto [8].
In this case, the default configuration of Hyperloglog uses $R=4096$
registers. Then attack was run for sets with cardinalities of
$C=20,000,40,000,60,000,80,000$ and $100,000$. The results are summarized in
Tables 1,2 that show the Hyperloglog cardinality estimate when inserting the
attack set and the size of the attack set for the three phases of algorithm 1.
It can be seen how the algorithm increases the cardinality estimate in the
second phase and reduces the size of the attack set in the third phase to
obtain a final attack set of approximately $R=4096$ elements that creates an
Hyperloglog estimate of approximately $C$. These results are similar those of
Redis and confirm the analysis presented in the previous section and the
feasibility of the attack.

Figure 2: Hyperloglog Cardinality Estimate for the original set that the
attack set in phases 1,2,3
Figure 3: Size of the attack set in phases 1,2,3 Table 1: Cardinality estimate in Presto  Cardinality | 20,000 | 40,000 | 60,000 | 80,000 | 100,000
---|---|---|---|---|---
Phase 1 | 17,128 | 36,756 | 48,332 | 63,940 | 78,372
Phase 2 | 19,739 | 40,005 | 59,132 | 79,134 | 98,723
Phase 3 | 19,739 | 39,625 | 59,132 | 79,314 | 98,723
Table 2: Attack set size in Presto  Cardinality | 20,000 | 40,000 | 60,000 | 80,000 | 100,000
---|---|---|---|---|---
Phase 1 | 6883 | 9306 | 10,143 | 11,018 | 11,691
Phase 2 | 7321 | 9715 | 10,396 | 11,234 | 11,870
Phase 3 | 4088 | 4124 | 4125 | 4127 | 4134

##  5 Conclusion

In this paper, the security of Hyperloglog against an attacker that wants to
artificially inflate the cardinality estimate has been considered. The
analysis shows that even without any knowledge of the Hyperloglog
implementation, the attacker can create a small set of elements that when
inserted on the Hyperloglog sketch produces a large cardinality estimate. The
feasibility of the attack has been demonstrated by implementing and testing it
on two commercial products that use Hyperloglog for cardinality estimation.
The experimental results confirm the validity of the analysis and suggest that
Hyperloglog implementations should incorporate mechanisms to detect and
prevent such an attack.

The detection of the attack has also been briefly discussed showing that
previous protection techniques are applicable to detect the attack. In
addition, simpler techniques to detect the attack have also been identified
and their detailed studied is left for future work. More generally, the
security of data sketches should be carefully studied as computing systems
rely increasingly on them to perform many operations beyond cardinality
estimation.

## Acknowledgment

Pedro Reviriego would like to acknowledge the support of the ACHILLES project
PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T funded by the
Spanish Ministry of Science and Innovation and of the Madrid Community
research project TAPIR-CM grant no. P2018/TCS-4496.

##  Appendix A Appendix

This appendix discusses in more detail first why some elements of the optimal
attack set are not identified in the first phase of the attack algorithm and
then why those missing elements have a non negligible impact on the
cardinality estimate.

###  A.1 Missing elements in Phase 1

There are two effects that make us miss elements when building the attack set
on the first Phase. The first one is due to the use of the LPCA estimate when
cardinality is low. For each register in the sketch, only the first element
hashed to it affects the LPCA estimate. All subsequent elements in the
register are ignored until the sketch switches to the HLL estimate. The switch
between the LPCA and HLL estimates is typically done when the cardinality is
$\approx 2.5\cdot R$ [14]. So there are in expectation 2.5 items per bin at
the time of the switch. If there are $N$ distinct items in total, the number
of missed items $M$ should be roughly $M\approx
R\cdot[2.5/(N/R)]\cdot(1.5/2.5)=1.5R^{2}/N$. That is $R$ times the chance that
the largest hash value in a register is inserted during the LPCA phase of the
sketch and is not the first one hashed to the register.

The second effect that makes us miss elements is that some of them produce a
small increment on the cardinality estimation. Therefore, if the HLL
implementation returns an integer value, the increment may not be detected.
For example, if the current estimate is 4002.1 and the increment is only 0.2
giving 4002.3, the HLL query would return 4002 in both cases and the element
is missed. To see how this happens, let us start with the cardinality estimate
is given by:

$C_{est}=\alpha\cdot\frac{R^{2}}{Z}$ (3)

a change on a counter from value $c_{old}$ to $c_{new}$ changes the value of
$Z$ by:

$\delta=2^{-c_{old}}-2^{-c_{new}}$ (4)

and the estimated cardinality by:

$I=\alpha\cdot\frac{R^{2}}{Z-\delta}-\alpha\cdot\frac{R^{2}}{Z}=\alpha\cdot\frac{R^{2}\cdot\delta}{Z\cdot(Z-\delta)}$
(5)

that can be approximated by:

$I\approx\alpha\cdot\frac{R^{2}\cdot\delta}{Z^{2}}=\frac{\delta\cdot(C_{est})^{2}}{\alpha\cdot
R^{2}}.$ (6)

The increment will be smaller than 0.5 when:

$\delta<0.5\cdot\frac{\alpha\cdot R^{2}}{(C_{est})^{2}}$ (7)

For example, if $R=4096$ and $C_{est}=20000$ values of $\delta$ lower than
0.015 may not be detected. For example, a counter that is incremented from 6
to 8 has a lower $\delta$ and may not be detected. To analyze the probability
that one of elements of the attack set is missed due to this second effect we
can start by noting that $\delta<2^{-c_{old}}$ and thus for an element to be
missed:

$2^{-c_{old}}<0.5\cdot\frac{\alpha\cdot R^{2}}{(C_{est})^{2}}$ (8)

Taking the $log_{2}$ on both sides of the equation we get:

$c_{old}>1+log_{2}(\alpha)+2\cdot log_{2}(\frac{C_{est}}{R})$ (9)

This is much larger than the expected value of a register when the HLL has an
estimate of $C_{est}$ that is $1+log_{2}(\frac{C_{est}}{R})$. Therefore, it
seems unlikely that a register is in a state (has a large enough $c_{old}$
value) to miss an element. For example, if the HLL has $R=4096$ and
$C_{est}=32000$, the expected value would be around four and the condition to
miss elements would require a value larger than approximately eight so few
counters would meet that condition. As the cardinality grows, the probability
would be even lower. Therefore, it seems that this second effect would have
less impact than the first and is not considered further.

###  A.2 Impact of the missing elements on the cardinality estimate

The number of missed elements can be approximated by $1.5R^{2}/N$ as discussed
in the previous subsection. It would seem that when $N$ is large (as it would
be the case in the proposed attack as we are trying to inflate the HLL
estimate), the value would be small. For example, if $R=4096$ and
$N=1,000,000$, only 25 elements would be missed from the expected 4096
elements. However, although the number of missed elements is small the impact
of these missed elements on the cardinality estimate is significant as was
seen in the evaluation results. To understand why, an example can be used,
consider a counter to which many elements map and there is one with maximum
value $v_{max}$. If that element happens to be missed, then the rest of the
elements will not increment the counter. Therefore, that counter for the
attack set will take the value of the first element that mapped to it that
will on average be low. This can significantly affect the cardinality
estimate. For example, if $v_{max}=10$ and the first element has a value of 1,
the counter would take a much lower value.

The probability that this happens on a counter would be approximately
$\frac{R}{C}$ as on average $\frac{C}{R}$ elements map to each counter thus
the probability of picking the maximum is the inverse of that assuming
$\frac{C}{R}$ is much larger than one. Therefore, on average this will occur
for $\frac{R^{2}}{C}$ counters. For each of them, the value would be reduced
to an average value of close to 2. Therefore the relative impact on the
denominator of the HLL estimate could be roughly approximated by:

$Z_{a}=\frac{1}{\sum_{i=1}^{R}2^{-r_{i}}+\frac{R^{2}}{C}\cdot(2^{-2}-\frac{R}{C})}$
(10)

The ratio of the cardinality of the attack set to that of the initial set is
shown in Figure 4 that also shows the rough theoretical estimate just
presented. It can be seen that there is a lost of approximately 20 to 30% and
that the theoretical estimate is inline with the simulation results. This is
because even a few counters can significantly affect the HLL estimate if they
take values that are much lower than the rest of the counters as previously
discussed in [15].

Figure 4: Ratio of the HLL estimate for the attack set in phase 1 to the HLL
estimate for the original set

## References

  * [1] Z. Bar-yossef, T. S. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan,“Counting distinct elements in a data stream,” in RANDOM, 2002.
  * [2] W. Chen, Y. Liu and Y. Guan,“Cardinality change-based early detection of large-scale cyber-attacks’,’ in Proceedings IEEE INFOCOM, 2013.
  * [3] Y. Chabchoub, R. Chiky, and B. Dogan, “How can sliding Hyperloglog and EWMA detect port scan attacks in IP traffic?” in the EURASIP Journal on Information Security, pp. 1-11, 2014.
  * [4] Y. Liu, W. Chen, and Y. Guan, “Identifying high-cardinality hosts from network-wide traffic measurements,” IEEE Transactions on Dependable and Secure Computing, vol. 13, no. 5, pp. 547–558, 2016.
  * [5] M. Cai, K. Hwang, J. Pan and C. Papadopoulos,“WormShield: Fast Worm Signature Generation with Distributed Fingerprint Aggregation,” in IEEE Transactions on Dependable and Secure Computing, vol. 4, no. 2, pp. 88-104, April-June 2007.
  * [6] Apache Data Sketches Library, https://datasketches.apache.org/
  * [7] RedisBloom: Probabilistic Datatypes Module for Redis, https://oss.redislabs.com/redisbloom/
  * [8] “HyperLogLog in Presto: A significantly faster way to handle cardinality estimation”, https://engineering.fb.com/data-infrastructure/hyperloglog/
  * [9] P. Flajolet, E. Fusy, O. Gandouet, and et al.,“Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm,” in Proceedings of the International Conference on Analysis of Algorithms (AOFA), 2007.
  * [10] S. Heule, M. Nunkesser, and A. Hall,“Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm,” in Proceedings of the International Conference on Extending Database Technology (EDBT), 2013.
  * [11] D. Desfontaines, A. Lochbihler, D.A. Basin, “Cardinality Estimators do not Preserve Privacy,” in Proceedings on Privacy Enhancing Technologies, no. 2, May 2019.
  * [12] P. Reviriego and D. Ting, “Security of HyperLogLog (HLL) cardinality estimation: Vulnerabilities and protection,” IEEE Communications Letters, vol. 24, no. 5, pp. 976–980, 2020.
  * [13] K.-Y. Whang, B. T. Vander-Zanden, and H. M. Taylor, “A linear-time probabilistic counting algorithm for database applications,” ACM Transactions on Database Systems, vol. 15, no. 2, pp. 208–229, 1990.
  * [14] O. Ertl, “New cardinality estimation algorithms for HyperLogLog sketches,” CoRR, abs/1702.01284, 2017.
  * [15] P. Reviriego, J. Martinez, O. Rottenstreich, S. Liu and F. Lombardi, “Remove Minimum (RM): An Error-Tolerant Scheme for Cardinality Estimate by HyperLogLog,’ in IEEE Transactions on Dependable and Secure Computing (in press).


#
Collision Geometry and Flow in Uranium+Uranium Collisions

Andy Goldschmidt1, Zhi Qiu1,2, Chun Shen1,3, Ulrich Heinz1
1Department of Physics, The Ohio State University,
Columbus, OH 43210, USA
2Google Inc., Mountain View, CA 94043, USA
3Department of Physics, McGill University,
Montreal, Quebec H3A 0G4, Canada

###### Abstract

Using event-by-event viscous fluid dynamics to evolve fluctuating initial
density profiles from the Monte-Carlo Glauber model for U+U collisions, we
report a “knee”-like structure in the elliptic flow as a function of collision
centrality, located near 0.5% centrality as measured by the final charged
multiplicity. This knee is due to the preferential selection of tip-on-tip
collision geometries by a high-multiplicity trigger. Such a knee structure is
not seen in the STAR data. This rules out the two-component MC-Glauber model
for initial energy and entropy production. An enrichment of tip-tip
configurations by triggering solely on high-multiplicity in the U+U collisions
thus does not work. On the other hand, using the Zero Degree Calorimeters
(ZDCs) coupled with event-shape engineering, we identify the selection purity
of body-body and tip-tip events in the full-overlap U+U collisions. With
additional constraints on the asymmetry of the ZDC signals one can further
increases the probability of selecting tip-tip events in U+U collisions.

##  1 Introduction

High energy collisions between heavy ions are used to probe emergent phenomena
in Quantum Chromodynamics (QCD), the theory of strong interaction. One feature
of QCD is the transition from hadronic matter to a color-deconfined quark-
gluon plasma (QGP) [1, 2, 3] as the temperature is increased. This transition
can occur in heavy-ion collisions of sufficient energy for the system to melt
into a hot dense fireball of asymptotically free quarks and gluons.

Relativistic hydrodynamic models have been successful in describing the
dynamical evolution of QGP [4]. Motivated as a testing ground for these
models, a U+U collisions program was recommended in order to study the unique
collision geometry resulting from the prolate deformation of the uranium
nucleus [5, 6, 7, 8, 9, 10, 11]. Such a program was carried out in 2012 at the
Relativistic Heavy Ion Collider (RHIC) at Brookhaven National Lab [12].

To understand the attraction of uranium, consider that the initial temperature
distribution of each QGP droplet is controlled by two main factors:
deterministic collision geometry (i.e. the shape of the overlap region between
two nuclei), and quantum mechanical fluctuations in the nucleon positions. For
spherical nuclei, the collision geometry is entirely a function of the impact
parameter. However, in prolate deformed uranium, the geometry of the initial
temperature distribution also depends on the relative spatial orientation of
the two nuclei which can be described by the Euler angles between their long
major axis.

We focus in this paper on two limiting cases for fully overlapping uranium
collisions. In one extreme we have “tip-tip” events, defined when the major
axes of both nuclei are parallel to the beam direction. The opposite limit are
“body-body” events, where the major axes of both nuclei are perpendicular to
the beam direction and parallel to each other. We are interested in answering
the question how, and with what precision, we can distinguish experimentally
between these configurations. Their conceptual importance is explained in [7].

##  2 The model

To model the initial energy density distribution of U+U collisions we employ
the two-component (wounded nucleon/binary collision) Monte-Carlo Glauber
model. We use the deformed Woods-Saxon distribution

$\rho(r,\theta,\varphi)=\frac{\rho_{0}}{1+e^{(r-r(\theta,\varphi))/d}}$ (1)

to sample the positions of nucleons inside a uranium nucleus. In Eq. (1), the
surface diffusiveness parameter is $d=0.44\mathrm{\ fm}$ and the saturation
density parameter is $\rho_{0}=0.1660\mathrm{\ fm}^{-3}$ [14, 15]. The spatial
configuration of a uranium nucleus is deformed; we model its radius as [16]

$r(\theta,\varphi)=r_{0}(1+\sum_{l=1}^{\infty}{\sum_{m=-l}^{l}\beta_{lm}Y_{l}^{m}(\theta,\phi)}),$
(2)

where the average radius $r_{0}=6.86\mathrm{\ fm}$ is adjusted in such a way
that, after folding Eq. (1) with the finite charge radius of an individual
nucleon, the resulting nuclear charge density distribution agrees with
experimental constraints [15]. We assume the uranium nucleus is azimuthally
symmetric and choose [17] the non-vanishing deformation parameters
$\beta_{20}=0.28$ and $\beta_{40}=0.093$ for the quadrupole and hexadecupole
deformations along its main axis, respectively. The choices of these
parameters agree well with a recent reanalysis in [18], except for
$\beta_{20}$ for which Ref. [18] gives the value $0.265$.

We use the Woods-Saxon density (1) to Monte-Carlo sample the nucleon centers
and represent each nucleon in the transverse plane by a gaussian areal density
distribution about its center:

$\rho_{n}(\vec{\mathbf{r}}_{\perp})=\frac{1}{(2\pi B)^{3/2}}e^{-r^{2}/(2B)}.$
(3)

The width parameter $B=\sigma_{NN}^{in}(\sqrt{s_{NN}})/14.30$ depends on
collision energy as described in [19]. The sum of these gaussian nucleon
density distributions represents the nuclear density distribution for the
sampled nucleus at the time of impact and is used to compute the initial
energy density distribution generated in the collision. For this calculation,
the two-component Monte-Carlo Glauber model weighs a relative contribution
from binary collisions $N_{b}$ and wounded nucleon participants $N_{p}$ [20].

The binary collision term counts the entropy deposited by pairs of colliding
nucleons and is modeled by a gaussian distribution with the same size as a
nucleon (see Eq .(3)) [21]; the total binary collision density per unit
transverse area is

$n_{\mathrm{BC}}(\vec{\mathbf{r}}_{\perp})=\sum_{i,j}{\gamma_{i,j}\frac{1}{2\pi
B}e^{-\left|\vec{\mathbf{r}}_{\perp}-\vec{\mathbf{R}}_{i,j}\right|^{2}/(2B)}}$
(4)

where the sum is over all pairs of colliding nucleons and the normalization
$\gamma_{i,j}$ is a $\Gamma$-distributed random variable with unit mean that
accounts for multiplicity fluctuations in individual nucleon-nucleon
collisions.

Each struck nucleon is said to be wounded by (or participating in) the
collision and contributes a portion of the initial entropy density distributed
symmetrically about its center; the resulting total wounded nucleon density
per unit area is given by

$n_{\mathrm{WN}}(\vec{\mathbf{r}}_{\perp})=\sum_{i}{\gamma_{i}\frac{1}{2\pi
B}e^{-\left|\vec{\mathbf{r}}_{\perp}-\vec{\mathbf{r}}_{i,\perp}\right|^{2}/(2B)}}$
(5)

where the sum is over all wounded nucleons in both nuclei and $\gamma_{i}$ is
again a fluctuating normalization factor with unit mean.

We model multiplicity fluctuations in a single nucleon-nucleon collision by
taking the normalizations $\gamma_{i,j}$ and $\gamma_{i}$ to be
$\Gamma$-distributed random variables with unit mean and variances controlled
by parameters $\theta_{\mathrm{BC}}$ and $\theta_{\mathrm{WN}}$, respectively.
The generic $\Gamma$ distribution with unit mean and scale parameter $\theta$
is given by

$\Gamma\left(\gamma;\theta\right)=\frac{\gamma^{1/\theta-1}{e}^{-\gamma/\theta}}{\Gamma\left(1/\theta\right){\theta}^{1/\theta}}{,}\quad\gamma\in\left[0,\infty\right)$
(6)

The multiplicity fluctuations from wounded nucleons and binary collisions are
related by requiring [21]:

$\theta_{pp}=\frac{1-\alpha}{2}\theta_{\mathrm{WN}}=\alpha\theta_{\mathrm{BC}}.$
(7)

where the parameter $\theta_{pp}=0.9175$ has been fit to the measured
multiplicity distributions in p+p collisions [21].

The distribution in the transverse plane of the deposited entropy per unit
volume is determined by mixing the binary collision and wounded nucleon
sources using

$s_{0}(\vec{\mathbf{r}}_{\perp})=\frac{\kappa_{s}}{\tau_{0}}\left(\frac{1-\alpha}{2}n_{\mathrm{WN}}(\vec{\mathbf{r}}_{\perp})+\alpha
n_{\mathrm{BC}}(\vec{\mathbf{r}}_{\perp})\right)$ (8)

where $\tau_{0}$ is the starting time for the (hydro)dynamical evolution of
the collision fireball. We choose $\kappa_{s}=17.16$ and the mixing ratio
$\alpha=0.12$ to reproduce the measured charged multiplicities and their
dependence on collision centrality in Au+Au collisions at 200 $A$ GeV. The
shape of the resulting energy density distribution in the transverse plane is
calculated from the entropy density using the equation of state (EoS)
`s95p-v0-PCE` from Lattice QCD [22]. The initial energy profile is evolved
using the viscous relativistic fluid dynamic code package `iEBE-VISHNU` [21]
with specific shear viscosity $\eta/s=0.08$. Simulations begin at time
$\tau_{0}=0.6$ fm/$c$ and decouple at a temperature $T_{\mathrm{dec}}=120$
MeV. The single particle momentum distribution is then computed using the
Cooper-Fyre Formula. A full calculation of charged hadron observables that
includes all hadronic resonance decay processes on an event-by-event basis is
numerically costly; for this reason we computed only the directly emitted
positively charged “thermal pions”, $\pi^{+}$, and take this quantity as a
measure for total charged multiplicity. At a fixed freeze-out temperature of
120 MeV, the two quantities are related by a constant factor 4.6,
$dN_{\mathrm{ch}}/d\eta\simeq 4.6\ dN_{\pi^{+}}/dy$.

The initial energy density profiles fluctuate from event to event. Each
profile can be characterized by the $r^{n}$-weighted eccentricity coefficients
$\varepsilon_{n}$ and their associated “participant plane angles” $\Phi_{n}$:

$\mathcal{E}_{n}:=\varepsilon_{n}e^{in\Phi_{n}}=-\frac{\int
d\vec{\mathbf{r}}_{\bot}r^{n}e^{in\varphi}e(\vec{\mathbf{r}}_{\perp})}{\int
d\vec{\mathbf{r}}_{\bot}r^{n}e(\vec{\mathbf{r}}_{\perp})},$ (9)

where $(r,\varphi)$ are the standard polar coordinates in the transverse plane
and $e(\vec{\mathbf{r}}_{\perp})$ is the initial energy density [23, 24].
Through the hydrodynamic evolution, these spatial eccentricities
$\\{\epsilon_{n},\Phi_{n}\\}$ translate themselves into the anisotropic flow
coefficients $\\{v_{n},\Psi_{n}\\}$ [25, 24, 26, 27]:

$\mathcal{V}_{n}:=v_{n}e^{in\Psi_{n}}=\frac{\int
d\varphi_{p}dp_{T}e^{in\varphi_{p}}dN/(p_{T}dp_{T}d\varphi_{p})}{\int
d\varphi_{p}dp_{T}dN/(p_{T}dp_{T}d\varphi_{p})}.$ (10)

Apart from the Monte-Carlo Glauber model, there exist various other
initialization models. These include the IP-Glasma model [28], the MC-KLN
model [29, 30], and the TRENTO model [31]. As we will see, U+U collisions can
provide experimental measurements to distinguish between these various
initializations.

##  3 Constraining collision geometry with multiplicity, flow, and ZDC cuts

###  3.1 Eccentricity and flow coefficients as a function of multiplicity

---

Figure 1: Panels (a,b) show the event-averaged eccentricities
$\varepsilon_{n}$, before hydrodynamic evolution, panels (c,d) the event-
averaged flows $v_{n}$ after hydrodynamic evolution. The left panels (a,c)
represent 35,000 minimum bias events that include multiplicity fluctuations
whereas the right panels (b,d) were obtained from a different set of 35,000
multiplicity-selected events covering the 0-5% centrality range without
multiplicity fluctuations.

In Fig. 1, we present the centrality dependence of the initial eccentricities
and the final anisotropic flow coefficients of thermal pions for harmonic
order $n=2-5$ in U+U collisions at 193 $A$ GeV. In Figs. 1a,c minimum bias
results are shown as functions of the thermal pion yields, $dN_{\pi^{+}}/dy$.
We notice that the variance of $\varepsilon_{2,4}$ and $v_{2,4}$ in “most
central” (i.e. highest multiplicity) collisions are larger than in the rest of
the centrality range. This is because there the two uranium nuclei are
colliding almost centrally (i.e. with impact parameter $b\approx 0$) but, as a
result of the large spatial deformation, not always with full overlap. A
mixture of tip-tip and body-body collisions in these high-multiplicity events
increases the variance of the initial $\varepsilon_{2,4}$ which then drives a
larger variance in $v_{2,4}$.

In Figs. 1b and 1d, we increase the statistics and focus on the 0-5% most
central U+U collisions. We find a “knee” structure in the high multiplicity
regime ($<0.5\%$ centrality) for both $\varepsilon_{2}$ and $v_{2}$. This can
be understood as follows: First, while the ellipticity in the transverse plane
for a tip-tip collision is small (as the overlap area is approximately
circular), body-body collisions produce an ellipsoidally deformed overlap
region with larger ellipticity $\varepsilon_{2}$. Second, although fully
overlapping tip-tip and body-body collisions share the same number of
participants, more binary collisions between nucleons can happen in the
optically thicker tip-tip event, implying (in our two-component Glauber model)
a larger initial $dS/dy$ deposited in the tip-tip configuration. In the
presence of fluctuations which lead to a range of $\varepsilon_{2}$ values for
a given $dS/dy$ and vice-versa, the larger average multiplicity in tip-tip
collisions implies an increasing bias toward small $\varepsilon_{2}$ when
selecting events with larger and larger values of $dS/dy$. This preferential
selection of tip-tip orientations at high multiplicities accounts for the
appearance of a knee structure in the initial ellipticity [11] (Fig. 1). We
see in Fig. 1c that the knee is preserved after an event-by-event hydrodynamic
simulation when plotting the elliptic flow of the final particle distribution
as a function of multiplicity.

We emphasize that experimental results from STAR do not show this knee
structure [12]. Considering the preservation of the structure after
hydrodynamic evolution as seen in Fig. 1, we conclude that, in contrast to
Au+Au collisions where it has been extensively tested, the two-component MC-
Glauber model fails to correctly identify entropy production in ultra central
U+U collisions where the knee is predicted by the model but not found
experimentally. Hence the non-linear dependence of multiplicity on the number
of wounded nucleons observed in spherical Au+Au and Pb+Pb collisions as a
function of collision centrality cannot be attributed to a binary collision
component as implemented in the two-component MC-Glauber model.

Figure 2: The ellipticity $\varepsilon_{2}$ as a function of $dS/dy$ from the
MC-Glauber model, for collisions roughly in the 0-5% centrality range, with
(blue dashed line) and without (black solid line) including multiplicity
fluctuations from single p+p collisions.

Some corrections to the entropy production in these ultra central events arise
from the inclusion of p+p multiplicity fluctuations. We see in Fig. 2 that
adding said multiplicity fluctuations weakens but does not erase the knee
structure in $\varepsilon_{2}$ vs. $dS/dy$. Hence, this effect alone does not
appear sufficient to reach agreement of the MC-Glauber model with data for
ultra central U+U collisions. We acknowledge that more drastic fluctuation
models [32] have been suggested in order to more successfully adjust the
theoretical predictions of MC-Glauber to experimental results.

Also of note is the success of the gluon saturation physics as implemented in
the IP-Glasma model. Interestingly, this model is able to simultaneously
accomodate a strong nonlinearity of $dN/dy$ as a function of
$N_{\mathrm{part}}$ in Au+Au and Pb+Pb and a weak dependence of $dN/dy$ on
collision orientation in central U+U at fixed number of participants, while
the MC-Glauber model cannot [33]. Alternatively, it has been suggested in [34]
that a model that produces entropy according to the number of wounded valence
gluons (rather than wounded nucleons) can also reproduce the observed
nonlinearity of $dN/dy$ as a function of particpant nucleons in Au+Au and
Pb+Pb at RHIC and LHC, without a binary collision component. It would be
interesting to study the preduction of such a model for central U+U collisions
of varying orientations.

###  3.2 Selecting high overlap events with combined ZDC and multiplicity cuts

In an experimental analysis of relativistic heavy ion collisions, the charged
hadron multiplicity, $dN_{\mathrm{ch}}/dy$ and its elliptic flow coefficient
$v_{2}$ can be used to classify events. Hydrodynamic studies have shown that
the initial $\varepsilon_{2}$ maps linearly to the $v_{2}$ of hadrons [26] and
the the initial $dS/dy$ is monotonically related the final total particle
multiplicity, $dN/dy$ [21]. We can therefore use $dS/dy$ and $\varepsilon_{2}$
from the initial conditions as a satisfactory proxy for charged hadron
$dN_{\mathrm{ch}}/dy$ and $v_{2}$ to test whether we can select the fully
overlapping tip-tip and body-body U+U collisions.

For our analysis, we make theoretical approximations for the use of
experimental forward and backward zero degree calorimeters (ZDCs). Placed at
zero degrees far from the colliding pair, ZDCs catch information about the
spectator neutrons that pass through a collision without participating. We
classify our collisions by using the number of spectators
$N_{s}=476-N_{\mathrm{part}}$ to mimic the experimental ZDC signal [8]. For
our study we look at 65,000 events in the $1\%$ most participating ZDC range
($N_{s}<19$). Selecting on the most participating ZDC collisions allows for a
restriction of the set of collisions to more fully overlapping events. In such
a regime, any initial geometric effects should come more exclusively from the
deformed shape of the uranium nucleus.

We define the tip-tip and body-body event classes using the pair of angles
$(\theta_{1,2},\phi_{1,2})$ from the two incoming nuclei, where $\theta$
denote the polar angle between the long major axis of the uranium nucleus and
the beam direction and $\phi$ is the azimuthal angle in the transverse plane.
An event is defined as tip-tip if
$\sqrt{\cos^{2}\theta_{1}+\cos^{2}\theta_{2}}>0.86$. We classify an event as a
body-body event if both $\sqrt{\cos^{2}\theta_{1}+\cos^{2}\theta_{2}}<.31$ and
$\left|\phi_{1}-\phi_{2}\right|<\pi/10$. The polar angle constraints imply
that for equal $\theta_{1}=\theta_{2}$, this common angle $\theta$ is less
than $\pi/10$ for tip-tip and greater than $4\pi/10$ for body-body. For body-
body events, the additional azimuthal constraint forces alignment of the long
major axes.

---
Figure 3: Probability distribution for $dS/dy$ (left) and $\varepsilon_{2}$
(right) for different event classes within a sample of 1% ZDC events. The top
panels show the distributions of tip-tip and body-body collisions scaled
according to their contribution to the total population within the 1% ZDC
sample. The bottom panels show relative probabilities for tip-tip and body-
body events among all events of a given $dS/dy$ (left) or $\varepsilon_{2}$
(right).

In Fig. 3 we plot the probability distributions for $\varepsilon_{2}$ and
$dS/dy$. Using our collision definitions we can directly read off from the
figure the likelihood of selecting a certain orientation based on a given
eccentricity or multiplicity cut. We see in the left bottom panel that by
cutting (within our 1% ZDC sample) on events with large $dS/dy$ we can enrich
the fraction of tip-tip events to about 50%, whereas cutting on low $dS/dy$
enriches the fraction of body-body events, but never to more than about 20%.
The 20% limit arises from admixtures from imperfectly aligned collisions that
are not really ”full overlap”. The enrichment of tip-tip or body-body by
varying $dS/dy$ relies on the assumed two-component nature of entropy
production which also produced the knee structure discussed before. Indeed,
selection efficiency of specific collision geometries by cutting on $dS/dy$ is
model dependent.

We therefore consider “event engineering”, i.e. selecting events by the
magnitude of their $v_{2}$ flow vectors (for us, of the linearly related
$\varepsilon_{2}$), shown in the right panels of Fig. 3. Since tip-tip events
have on average smaller ellipticities (see upper right panel), selecting
events with small ellipticity (or, in experiment, small $v_{2}$) enriches the
tip-tip fraction. However, in this way we will never reach more than about 25%
purity of the tip-tip sample. On the other hand, cutting the 1% ZDC events on
large $\varepsilon_{2}$ (or $v_{2}$) will enrich the sample in body-body
events, with a purity that can reach about 40% for the largest
$\varepsilon_{2}$ values. While we have not yet been able to verify this with
an actual cut on $v_{2}$, we expect this feature to survive the hydrodynamic
evolution due to the almost perfect linearity between $\varepsilon_{2}$ and
$v_{2}$.

The current ZDC cut strategy can be refined further to increase the
probability of selecting tip-tip events. Rather than looking at the ZDC signal
in one of the two ZDC detectors or the sum of the ZDC signals in both
detectors, we can look at the correlation of these two signals. Events with
equal forward and backward ZDC signals (i.e. equal numbers of spectators from
both nuclei) provide a better definition of the categories full overlap, tip-
tip, and body-body than events with asymmetric ZDC signals where all
spectators come from only one of the colliding nuclei. The difference in
participants $\Delta
N_{\mathrm{part}}=\left|N_{\mathrm{part,1}}-N_{\mathrm{part,2}}\right|$
quantifies the ZDC correlation in our model. Low values of $\Delta N_{p}$
correspond to the most correlated forward and backward ZDC signals. To
demonstrate one application, we reconsider the events from the bottom right
panel in Fig. 3 and now select from the sample only events in the lowest 10%
of $\Delta N_{\mathrm{part}}$. The selection on small values of $\Delta
N_{\mathrm{part}}$ eliminates from the sample asymmetric configurations that
we loosely describe as “tip-body”. Collisions of this type produce low values
of $\varepsilon_{2}$ without the angular criteria necessary to be considered
tip-tip and therefore dilute the contribution of the true tip-tip
configurations at the lower range of $\varepsilon_{2}$. We show in Fig. 4 that
selecting the lowest 10% of $\Delta N_{\mathrm{part}}$ increases the selection
efficiency of $\varepsilon_{2}$ for tip-tip configurations by a factor of 1.4.
As a final comment, we point out that it might also be interesting to use ZDC
correlations in the opposite way and to select and study events with
asymmetric tip-body configurations.

Figure 4: The black curve is the distribution of tip-tip events scaled
according to their contribution to the total probability distribution for
$\varepsilon_{2}$ as seen in the bottom right pannel in Fig. 3. The blue
dashed curve shows the increased contribution of tip-tip collisions within the
10% of events having the smallest difference in participants $\Delta
N_{\mathrm{part}}$ (a proxy for ZDC correlation).

##  4 Conclusion

Within the two-component MC-Glauber model for initial energy production, the
prolate deformation of the uranium nucleus was shown to generate a knee in the
centrality dependence of the ellipticity of the initial temperature
distribution. The knee was seen to be preserved by hydrodynamic evolution,
after which it manifests itself in the centrality dependence of $v_{2}$. Such
a knee structure is not seen in the STAR data. This rules out the two-
component MC-Glauber model for initial energy and entropy production. An
enrichment of tip-tip configurations by triggering only on high-multiplicity
in the U+U collisions thus does not work.

To increase the selection capability between different collision geometries,
we impose combined cuts on initial conditions using the spectators (ZDC),
$dS/dy$, and $\varepsilon_{2}$. For 1% ZDC events, we found that we could
enrich tip-tip collision geometries to about 50% by cutting on high
multiplicity within that sample, and body-body configurations to about 20%
purity by selecting low-multiplicity events. These numbers rely on the binary
collision admixture in the two-component MC-Glauber model and are thus model-
dependent. They do include effects from multiplicity fluctuations.

We also studied the efficiency of selecting different collision geometries by
“event engineering”, i.e. by cutting on $\varepsilon_{2}$ (by cutting on
$v_{2}$ in the experiment). In this case events selected for high
$\varepsilon_{2}$ can enrich body-body collisions to about 40% purity while
cutting on low $\varepsilon_{2}$ gives a tip-tip sample with about 25% purity.
The latter can be boosted to about 35% purity by eliminating events with
asymmetric ZDC signals. These results should not be sensitive to the binary
collision admixture in the two-component MC-Glauber model and thus should be
less model dependent.

Acknowledgments
This work was supported in part by the U.S. Department of Energy, Office of
Science, Office of Nuclear Physics under Award No. DE-SC0004286.

## References

  * [1] U. Heinz, Nucl. Phys. A 721, 30 (2003).
  * [2] M. Gyulassy, nucl-th/0403032.
  * [3] E. V. Shuryak, Nucl. Phys. A 750, 64 (2005).
  * [4] P. F. Kolb and U. Heinz, In *Hwa, R.C. (ed.) et al.: Quark gluon plasma* 634-714 [nucl-th/0305084].
  * [5] E. V. Shuryak, Phys. Rev. C 61, 034905 (2000).
  * [6] P. F. Kolb, J. Sollfrank and U. Heinz, Phys. Rev. C 62, 054909 (2000).
  * [7] U. Heinz and A. Kuhlman, Phys. Rev. Lett. 94, 132301 (2005).
  * [8] A. J. Kuhlman and U. Heinz, Phys. Rev. C 72, 037901 (2005).
  * [9] C. Nepali, G. Fai and D. Keane, Phys. Rev. C 73, 034911 (2006).
  * [10] C. Nepali, G. I. Fai and D. Keane, Phys. Rev. C 76, 051902 (2007) [Erratum-ibid. C 76, 069903 (2007)].
  * [11] S. A. Voloshin, Phys. Rev. Lett. 105, 172301 (2010).
  * [12] H. Wang, P. Sorensen et al. [STAR Collaboration], Nucl. Phys. A 932, 169 (2014).
  * [13] R. D. Woods and D. S. Saxon, Phys. Rev. 95, 577 (1954).
  * [14] L. C. Chamon et al. Phys. Rev. C 66, 014610 (2002).
  * [15] T. Hirano, P. Huovinen and Y. Nara, Phys. Rev. C 83, 021902 (2011).
  * [16] P. Moller, J. R. Nix, W. D. Myers and W. J. Swiatecki, Atom. Data Nucl. Data Tabl. 59, 185 (1995).
  * [17] P. Filip, R. Lednicky, H. Masui and N. Xu, Phys. Rev. C 80, 054903 (2009).
  * [18] Q. Y. Shou, Y. G. Ma, P. Sorensen, A. H. Tang and H. Wang, arXiv:1409.8375 [nucl-th].
  * [19] U. Heinz and J. S. Moreland, Phys. Rev. C 84, 054905 (2011).
  * [20] A. Bialas, M. Bleszynski and W. Czyz, Nucl. Phys. B 111, 461 (1976).
  * [21] C. Shen, Z. Qiu, H. Song, J. Bernhard, S. Bass and U. Heinz, arXiv:1409.8164 [nucl-th].
  * [22] P. Huovinen and P. Petreczky, Nucl. Phys. A 837, 26 (2010).
  * [23] B. Alver and G. Roland, Phys. Rev. C 81, 054905 (2010) [Erratum-ibid. C 82, 039903 (2010)].
  * [24] F. G. Gardim, F. Grassi, M. Luzum and J. Y. Ollitrault, Phys. Rev. C 85, 024908 (2012).
  * [25] S. Voloshin and Y. Zhang, Z. Phys. C 70, 665 (1996).
  * [26] Z. Qiu and U. Heinz, Phys. Rev. C 84, 024911 (2011).
  * [27] Z. Qiu, arXiv:1308.2182 [nucl-th].
  * [28] B. Schenke, P. Tribedy and R. Venugopalan, Phys. Rev. Lett. 108, 252301 (2012).
  * [29] D. Kharzeev and M. Nardi, Phys. Lett. B 507, 121 (2001); D. Kharzeev, E. Levin and M. Nardi, Nucl. Phys. A 730, 448 (2004) [Erratum-ibid. A 743, 329 (2004)].
  * [30] H.-J. Drescher and Y. Nara, Phys. Rev. C 75, 034905 (2007); and Phys. Rev. C 76, 041903 (2007).
  * [31] J. S. Moreland, J. E. Bernhard and S. A. Bass, arXiv:1412.4708 [nucl-th].
  * [32] M. Rybczynski, W. Broniowski and G. Stefanek, Phys. Rev. C 87, 044908 (2013).
  * [33] B. Schenke, P. Tribedy and R. Venugopalan, arXiv:1403.2232 [nucl-th].
  * [34] S. S. Adler et al. [PHENIX Collaboration], Phys. Rev. C 89, 044905 (2014).


configuration spaces of unit diameter disks on the infinite strip of width
$2$.

######  Proposition 6.1.

Given any element $z(e)$ of the basis for
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ from Theorem 2.17 there is a
unique $k$-barrier set $C^{\prime}$ such that $z(e)$ is the unique element
with greatest signature of some element in
$M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$. If the signature
of $z(e)$ is $(l_{1},\dots,l_{k})$, then the signature of $C^{\prime}$ is
$(l^{\prime}_{1},\dots,l^{\prime}_{k})$, where $l^{\prime}_{j}=l_{j}$ if
$l_{j}$ is even, and $l^{\prime}_{j}=-1$ if $l_{j}$ is an odd. Additionally,
$\dim\big{(}M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}\big{)}$
many such basis elements for $H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$
from Theorem 2.17 appear as the leading term of an element in
$M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$.

###### Proof.

Every basis element for $H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ from
Theorem 2.17 is of the form $z(e_{1})|\cdots|z(e_{k})$ where the $z(e_{j})$s
are properly ordered injected $1$-cycles on distinct labels arising from a
$1$-cycle in $C_{j}$, where for $1\leq j\leq k-1$, $C_{j}$ is of the form
$A_{n_{j},n_{j}-2}$ or $B_{n_{j},n_{j}-2}$, and $C_{k}$ is a set of the form
$A_{n_{k},m_{k}}$ or $B_{n_{k},m_{k}}$, such that $\sum_{i=1}^{k}n_{i}=p$.

If $z(e_{i})$ is a properly ordered injected cycle arising from an element of
$A_{n,m}$, then by Corollary 4.13, there is a linear combination of properly
ordered injected cycles $z^{\prime}(e_{j,i})$ arising from elements of
$A^{\prime}_{n,m}$ with the same set of labels are $e_{i}$ such that

$z(e_{i})+\sum
a^{\prime\prime}_{e^{\prime\prime}_{i}}z(e^{\prime\prime}_{i})=\sum
a_{e^{\prime}_{j,i}}z^{\prime}(e_{j,i}),$

where $L\big{(}z(e_{i})\big{)}>L\big{(}z(e^{\prime\prime}_{i})\big{)}$ for all
$1$-cycles $z(e^{\prime\prime}_{i})$ with nontrivial coefficient in the left
hand sum. Thus $L\big{(}z(e_{i})\big{)}>L\big{(}\sum
a^{\prime\prime}_{e^{\prime\prime}_{i}}z(e^{\prime\prime}_{i})\big{)}$. It
follows that

$\sum a_{e^{\prime}_{j,1}}z^{\prime}(e_{j,1})|\cdots|\sum
a_{e^{\prime}_{j,k}}z^{\prime}(e_{j,k})=\sum\cdots\sum
a_{e^{\prime}_{j,1}}\cdots
a_{e^{\prime}_{j,k}}z^{\prime}(e_{j,1})|\cdots|z^{\prime}(e_{j,k}),$

is a concatenation product of injected cycles on distinct labels arising from
the sets $B_{n,m}$ and $A^{\prime}_{n,m}$ of Theorem 4.9, with unique greatest
term in the $L$-value $z(e_{1})|\cdots|z(e_{k})$. By Theorem 5.6 each element
$z^{\prime}(e_{j,1})|\cdots|z^{\prime}(e_{j,k})$ is contained in
$M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$, where elements in
$C^{\prime}$ are of the form
$z^{\prime}(\bar{e}_{1})|\cdots|z^{\prime}(\bar{e}_{k})$, and
$z^{\prime}(\bar{e}_{j})$ is a properly ordered injected cycle arising from an
element of $C^{\prime}_{j}$, such that for $i<k$, $C^{\prime}_{i}$ is a set of
the form $A^{\prime}_{n_{j},n_{j}-2}$ if the $z^{\prime}(e_{j,i})$s are
properly ordered injected cycle s arising from elements of
$A_{n_{j},n_{j}-2}$, and if $z^{\prime}(e_{j,i})$s are properly ordered
injected cycles arising from elemenst of $B_{n_{j},n_{j}-2}$, $C^{\prime}_{i}$
is of the form $B_{2}$; if the $z^{\prime}(e_{j,k})$s are properly ordered
injected cycles arising from elements of $A_{n_{k},m_{k}}$, $C^{\prime}_{k}$
is of the form $A^{\prime}_{n_{k},n_{k}-2}$, and if the $z^{\prime}(e_{j,k})$s
are properly ordered injected cycles arising from elements of
$B_{n_{k},m_{k}}$, $C^{\prime}_{k}$ is of the form $B_{2}$. This also shows
that the signature of $C^{\prime}$ has the form of the proposition statement.
Finally, note that that there are exactly as many elements of the form
$z(e_{1})|\cdots|z(e_{k})$ as
$z^{\prime}(\bar{e}_{1})|\cdots|z^{\prime}(\bar{e}_{k})$ as the $e_{j}$s and
$\bar{e}_{j}$s are indexed in exactly the same way. Thus, there are least
$\dim\big{(}M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}\big{)}$
many elements of the basis for
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ from Theorem 2.17 that appear
as leading terms of an element in
$M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$.

To see that $C^{\prime}$ is the unique $k$-barrier set with
$z(e)=z(e_{1})|\cdots|z(e_{k})$ as a leading term, consider the $L$-value of
$z(e)$. Let $L\big{(}z(e)\big{)}=(l_{1},\dots,l_{k})$. The only way a $z(e)$
is the leading term of some linear combination of elements of
$M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$, is if
$L(C^{\prime\prime})\leq L\big{(}z(e)\big{)}$, since high-insertion cannot
decrease the signature. Moreover, the even terms of $L\big{(}z(e)\big{)}$ must
be equal to the even terms of $L(C^{\prime\prime})$, as the leading terms of
the free FI${}_{S(C^{\prime\prime})+1}$-module can only have $L$-value
differing from $L(C^{\prime\prime})$ in the odd terms due to the rules we
imposed on high-insertion. Additionally, by Proposition 5.10, given any
$k$-barrier set $C^{\prime\prime}$ the odd terms of $L(C^{\prime\prime})$ are
all $-1$. There is only one $k$-barrier set $C^{\prime\prime}$ such that all
the even terms of $L(C^{\prime\prime})$ are equal to the even terms of
$L\big{(}z(e)\big{)}$, and all the odd terms are $-1$ namely $C^{\prime}$.
Thus $C^{\prime}$ is unique. This also, shows that there can be no more than
$\dim\big{(}M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}\big{)}$
many elements of the basis for
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ from Theorem 2.17 that appear
as leading terms of an element in
$M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$, so there must be
exactly this many elements. ∎

Now we decompose $H_{k}\big{(}\text{cell}(\bullet,2);\mathbb{Q}\big{)}$ into a
direct sum of free FId-modules.

######  Theorem 6.2.

$H_{k}\big{(}\text{cell}(\bullet,2);\mathbb{Q}\big{)}=\bigoplus
M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime}),$

where the direct sum ranges over all $k$-barrier sets $C^{\prime}$.

###### Proof.

By Proposition 6.1 every element $z(e)$ the basis of Theorem 2.17 for
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ is the leading term of an
element in a FI${}_{S(C^{\prime})+1}$-module generated by some $k$-barrier set
$C^{\prime}$. Thus, $z(e)+\sum a_{e^{\prime}}z(e^{\prime})\in
M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$, where
$L\big{(}z(e^{\prime})\big{)}<L\big{(}z(e)\big{)}$ for all nontrivial terms in
the sum, and the $z(e^{\prime})$ are in the basis of Theorem 2.17 for
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$. Note that for each
$z(e^{\prime})$ there exists a $k$-barrier set $C^{\prime}_{e^{\prime}}$ such
that $z(e^{\prime})$ is the leading term of an element in the
FI${}_{S(C^{\prime}_{e^{\prime}})+1}$-module generated by some $k$-barrier set
$C^{\prime}_{e^{\prime}}$, i.e., $z(e^{\prime})+\sum
a_{e^{\prime\prime}}z(e^{\prime\prime})\in
M^{\text{FI}_{S(C^{\prime}_{e^{\prime}})+1}}(\mathbb{Q}C^{\prime}_{e^{\prime}})_{n}$,
such that $L\big{(}z(e^{\prime\prime})\big{)}<L\big{(}z(e^{\prime})\big{)}$
for all nontrivial terms in the sum. Note that we can repeat this process a
finite number of times, since there are only finitely many elements in
$\mathbb{Z}_{\geq-1}^{k}$ less than $L\big{(}z(e)\big{)}$, and see that
$z(e)\in\sum M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$. Thus,

$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}=\sum
M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}.$

Now we prove that

$\sum\dim\big{(}M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}\big{)}=\dim\Big{(}H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}\Big{)},$

as this will prove that
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}=\bigoplus
M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$.

By Proposition 6.1 there are
$\dim\big{(}M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}\big{)}$
many elements of the basis for
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ from Theorem 2.17 that are
leading terms of some element in
$M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$. By Proposition
6.1, each element in the basis for
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ from Theorem 2.17 is a
leading term of an element of exactly one free FId-module generated by a
$k$-barrier set. Thus, the dimension of
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ is equal to
$\sum\dim\big{(}M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{p}\big{)}$.
Moreover, this is true for all $n$. Therefore, since Theorem 2.17 proves that
the dimension of $H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ is finite,
it follows that

$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}=\bigoplus
M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}$

for all $n$. Therefore,

$H_{k}\big{(}\text{cell}(\bullet,2);\mathbb{Q}\big{)}=\bigoplus
M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})$

∎

######  Proposition 6.3.

Let $C^{\prime}$ be a $k$-barrier set. Then,
$M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}=0\subseteq
H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ if and only if

$D(C^{\prime})\leq n.$

###### Proof.

Theorem 5.6 proves that $\mathbb{Q}C^{\prime}$ is an FB-module concentrated in
degree $D(C^{\prime})$. Proposition 3.12 shows that the dimension of the
$n^{\text{th}}$-degree of the free FId-module generated by a FB-module $W$
concentrated in degree $m$ is

$\dim(W_{m})\binom{n}{m}d^{n-m}.$

This is non-zero if and only if $n\geq m$. ∎

######  Corollary 6.4.

As a representation of $S_{n}$, the homology group
$H_{k}\big{(}\text{Conf}(n,2);\mathbb{Q}\big{)}$ decomposes as follows

$H_{k}\big{(}\text{Conf}(n,2);\mathbb{Q}\big{)}\cong\bigoplus_{\begin{subarray}{c}(n_{1},\dots,n_{k})\text{
such that}\\\ n_{i}\geq 2,\text{ }\sum_{j=1}^{k}n_{j}\leq
n\end{subarray}}\Big{(}\bigoplus_{\begin{subarray}{c}a=(a_{1},\dots,a_{d+1})\text{
such that}\\\ d\text{ is the number of }n_{i}=2,\\\ |a|=n-\sum
n_{i}\end{subarray}}\big{(}\text{Ind}^{S_{n}}_{S_{n_{1}}\times\cdots\times
S_{n_{k}}\times S_{a}}W_{n_{1}}\boxtimes\cdots\boxtimes
W_{n_{k}}\boxtimes\mathbb{Q}\big{)}\Big{)},$

where $W_{n_{j}}=Triv_{2}$ if $n_{j}=2$, $W_{n_{j}}=Std_{n_{j}}$ if $n_{j}>2$,
and $\mathbb{Q}$ denotes the trivial representation of
$S_{a}:=S_{a_{1}}\times\cdots\times S_{a_{d+1}}$.

###### Proof.

By Theorem 2.15 $H_{k}\big{(}\text{Conf}(n,2);\mathbb{Q}\big{)}$ and
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ are isomorphic as
$S_{n}$-representations. So, by Theorem 6.2

$H_{k}\big{(}\text{Conf}(n,2);\mathbb{Q}\big{)}\cong\bigoplus
M^{\text{FI}_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}.$

By Theorem 5.6, we have

$M^{FI_{S(C^{\prime})+1}}(\mathbb{Q}C^{\prime})_{n}=M^{FI_{S(C^{\prime})+1}}\left(\text{Ind}^{S_{D(C^{\prime})}}_{S_{n_{1}}\times\cdots\times
S_{n_{k}}}W_{n_{1}}\boxtimes\cdots\boxtimes W_{n_{k}}\right),$

where $D(C^{\prime}_{j})=n_{j}$ and $V_{n_{j}}=Triv_{2}$ if $n_{j}=2$ and
$V_{n_{j}}=\wedge^{2}Std_{n_{j}}$ if $n_{j}\geq 2$ as $S_{p}$-representations.
By Proposition 3.14 we can rewrite this as

$\bigoplus_{\begin{subarray}{c}a=(a_{1},\dots,a_{d+1})\text{ such that}\\\
d\text{ is the number of }n_{i}=2,\\\ |a|=n-\sum
n_{i}\end{subarray}}\big{(}\text{Ind}^{S_{n}}_{S_{n_{1}}\times\cdots\times
S_{n_{k}}\times S_{a}}W_{n_{1}}\boxtimes\cdots\boxtimes
W_{n_{k}}\boxtimes\mathbb{Q}\big{)}.$

where $\mathbb{Q}$ denotes the trivial representation of
$S_{a}:=S_{a_{1}}\times\cdots\times S_{a_{d+1}}$.

By Proposition 6.3 we only need to consider $k$-barrier sets $C^{\prime}$ such
that $D(C^{\prime})=\sum_{j=1}^{k}D(C^{\prime}_{j})\leq n$. This is the set of
$k$-tuples $(n_{1},\dots,n_{k})$ such that $\sum_{j=1}^{k}n_{j}\leq n$ and
such that $n_{j}\geq 2$ for all $j$. Moreover, Proposition 6.3 shows that all
such $k$-barrier sets are nontrivial summands of
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$. Thus, we see that we can
decompose $H_{k}(\text{Conf}(n,2);\mathbb{Q}\big{)}$ as an
$S_{n}$-representation as

$H_{k}\big{(}\text{Conf}(n,2);\mathbb{Q}\big{)}\cong\bigoplus_{\begin{subarray}{c}(n_{1},\dots,n_{k})\text{
such that}\\\ n_{i}\geq 2,\text{ }\sum_{j=1}^{k}n_{j}\leq
n\end{subarray}}\Big{(}\bigoplus_{\begin{subarray}{c}a=(a_{1},\dots,a_{d+1})\text{
such that}\\\ d\text{ is the number of }n_{i}=2,\\\ |a|=n-\sum
n_{i}\end{subarray}}\big{(}\text{Ind}^{S_{n}}_{S_{n_{1}}\times\cdots\times
S_{n_{k}}\times S_{a}}W_{n_{1}}\boxtimes\cdots\boxtimes
W_{n_{k}}\boxtimes\mathbb{Q}\big{)}\Big{)},$

where $W_{n_{j}}=Triv_{2}$ if $n_{j}=2$, and $W_{n_{j}}=Std_{n_{j}}$ if
$n_{j}>2$.

∎

We use Corollary 6.4 to determined the multiplicity of the alternating and
trivial symmetric group representations in
$H_{k}\big{(}\text{conf}(n,2);\mathbb{Q}\big{)}$. These are examples of
multiplicity stability for FId-modules as stated in [Ram17], which generalize
the multiplicity stability results for FI-modules found in [CEF15] and
[CEFN14].

######  Corollary 6.5.

The alternating representation of $S_{n}$ occurs with multiplicity $1$ in
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ if $n-3k=0$ or $1$, and with
multiplicity $0$ otherwise.

###### Proof.

This follows from Corollary 6.4 and the Littlewood-Richardson Rule, see, for
example, [FH13, A.8]. The only way for the alternating representation of
$S_{n}$ to appear in the decomposition of
$H_{k}\big{(}\text{cell}(p,2);\mathbb{Q}\big{)}$ given in Corollary 6.4 is if
all of $V_{n_{1}},\dots,V_{n_{k}}$ are alternating representations of the
corresponding $S_{n_{j}}$. By Theorem 4.9 this is only possible if $n_{j}=3$
for all $j=1,\dots,k$. In this case $S(C^{\prime})=0$. Thus, we only need to
count the number of times the alternating representation occurs in

$\text{Ind}^{S_{n}}_{S_{3}\times\cdots\times S_{3}\times
S_{a}}Alt_{3}\boxtimes\cdots\boxtimes Alt_{3}\boxtimes\mathbb{Q},$

where $Alt_{n}$ denotes the alternating representation of $S_{n}$ and $a$ is
the $1$-composition of $n-3k$, $(n-3k)$. It follows from Pieri’s Rule that the
alternating representation of $S_{n}$ occurs if and only if $n-3k=0$ or $1$,
see, for example, [FH13, A.7]. In these cases the Littlewood–Richardson rule
also proves the alternating representation of $S_{n}$ occurs only once. ∎

######  Corollary 6.6.

The trivial representation of $S_{n}$ occurs with multiplicity
$\binom{n-k}{k}$ in $H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ if $n\geq
2k$, and with multiplicity $0$ otherwise.

###### Proof.

This also follows from Corollary 6.4 and the Littlewood-Richardson rule. The
only way for the trivial representation of $S_{n}$ to occur in the
decomposition of $H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ given in
Corollary 6.4 is if each of the $V_{n_{1}},\dots,V_{n_{k}}$ is a trivial
representation of the corresponding $S_{n_{j}}$. By 4.9 this is only possible
if $n_{j}=2$ for all $j=1,\dots,k$. In this case $S(C^{\prime})=k$. Thus, we
only need to consider the number of times the trivial representation occurs in

$\bigoplus_{a=(a_{1},\dots,a_{k+1})||a|=n-2k}\big{(}\text{Ind}^{S_{n}}_{S_{2}\times\cdots\times
S_{2}\times S_{a}}Triv_{2}\boxtimes\cdots\boxtimes
Triv_{2}\boxtimes\mathbb{Q}\big{)}.$

By an application of the Littlewood–Richardson rule, this is equal to the
number of $k+1$-compositions of $n-2k$. If $p\geq 2k$ this is equal to
$\binom{n-2k+k+1-1}{k+1-1}=\binom{n-k}{k}$, and if $n<2k$ then there are no
such compositions. ∎

We can use Corollary 6.6 and the transfer map to determine the structure of
the homology groups of the unordered configuration space of $n$ unit-diameter
disks on the infinite strip of width $w$.

######  Corollary 6.7.

Let $\text{UConf}(n,w)=\text{Conf}(n,w)/S_{n}$ denote the unordered
configuration space of $n$ unit-diameter disks on the infinite strip of width
$w$. Then,
$H_{k}\big{(}\text{UConf}(n,2);\mathbb{Q}\big{)}\cong\mathbb{Q}^{\binom{n-k}{k}}$.

###### Proof.

Note that $\text{Conf}(n,2)$ is a covering space of $\text{UConf}(n,2)$ with
deck group $S_{n}$. The transfer map
$\tau_{*}:H_{k}\big{(}\text{UConf}(n,2);\mathbb{Q}\big{)}\to
H_{k}\big{(}\text{Conf}(n,2);\mathbb{Q}\big{)}$ is injective, with image
$H_{k}\big{(}\text{Conf}(n,2);\mathbb{Q}\big{)}^{S_{n}}$, see, for example,
[Hat01, Proposition 3G.1]. If an element in
$H_{k}\big{(}\text{Conf}(n,2);\mathbb{Q}\big{)}$ is invariant under the
$S_{n}$-action it spans a copy of the trivial representation of ${S_{n}}$.
Moreover, every copy of the trivial representation is invariant under the
$S_{n}$-action. Thus, $H_{k}\big{(}\text{Conf}(n,2);\mathbb{Q}\big{)}^{S_{n}}$
is equal to the sum of all the trivial representations of $S_{n}$ in
$H_{k}\big{(}\text{Conf}(n,2);\mathbb{Q}\big{)}$. By the previous corollary
this has dimension $\binom{n-k}{k}$. Thus,
$H_{k}\big{(}\text{UConf}(n,2);\mathbb{Q}\big{)}\cong\mathbb{Q}^{\binom{n-k}{k}}$.
∎

This agrees with Alpert and Manin’s Corollary 9.4 [AM21, Corollary 9.4].

######  Remark 6.8.

In general $H_{k}\big{(}\text{UConf}(\bullet,2);\mathbb{Q}\big{)}$ is a free
module over the twisted commutative algebra $\mathbb{Q}[x_{0},\dots,x_{k}]$
where multiplication by $x_{i}$ corresponds to inserting a disk after the
$i^{\text{th}}$-barrier, where only the only barriers are images of $z(1\,2)$
under the quotient of the symmetric group action. Thus
$H_{k}\big{(}\text{UConf}(\bullet,2);\mathbb{Q}\big{)}$ exhibits a notation of
homological stability as
$H_{k}\big{(}\text{UConf}(\bullet,2);\mathbb{Q}\big{)}$ is a free
$\mathbb{Q}[x_{0},\dots,x_{k}]$-module generated in degree $2k$.

We have recovered a decomposition of
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ into induced
$S_{n}$-representations. This decomposition came at a cost. In [Alp20] Alpert
proved that $H_{k}\big{(}\text{cell}(\bullet,2);\mathbb{Q}\big{)}$ is a
finitely generated FIk+1-module. We have used the FIk+1-structure, but did
away with Alpert’s finite generating set. Instead, we found a new generating
set that has elements in every large degree used this set to construct smaller
free FId-modules. By keeping tracking of our generators and using some basic
facts about FId-modules we are able to make our decomposition. In short we
have traded finite generation for freedom, losing a more unified view of
$H_{k}\big{(}\text{cell}(n,2);\mathbb{Q}\big{)}$ to better see the finer
details.

##  7\. Declarations

Conflict of Interest The author states that there is no conflict of interest.

## References

  * [AKM21] Hannah Alpert, Matthew Kahle, and Robert MacPherson.  Configuration spaces of disks in an infinite strip.  Journal of Applied and Computational Topology, pages 1–34, 2021\.
  * [Alp20] Hannah Alpert.  Generalized representation stability for disks in a strip and no-k-equal spaces.  arXiv preprint arXiv:2006.01240, 2020.
  * [AM21] Hannah Alpert and Fedor Manin.  Configuration spaces of disks in a strip, twisted algebras, persistence, and other stories, 2021.
  * [Arn69] Vladimir I Arnold.  The cohomology ring of the colored braid group.  In Vladimir I. Arnold-Collected Works, pages 183–186. Springer, 1969.
  * [BBK14] Yuliy Baryshnikov, Peter Bubenik, and Matthew Kahle.  Min-type Morse theory for configuration spaces of hard spheres.  International Mathematics Research Notices, 2014(9):2577–2592, 2014\.
  * [CEF15] Thomas Church, Jordan S Ellenberg, and Benson Farb.  FI-modules and stability for representations of symmetric groups.  Duke Mathematical Journal, 164(9):1833–1910, 2015.
  * [CEFN14] Thomas Church, Jordan S Ellenberg, Benson Farb, and Rohit Nagpal.  Fi-modules over noetherian rings.  Geometry & Topology, 18(5):2951–2984, 2014.
  * [CGKM12] Gunnar Carlsson, Jackson Gorham, Matthew Kahle, and Jeremy Mason.  Computational topology for configuration spaces of hard disks.  Physical Review E, 85(1):011303, 2012.
  * [CLM76] Frederick Ronald Cohen, Thomas Joseph Lada, and Peter J May.  The homology of iterated loop spaces, volume 533.  Springer, 1976.
  * [Dia09] Persi Diaconis.  The markov chain monte carlo revolution.  Bulletin of the American Mathematical Society, 46(2):179–205, 2009\.
  * [Far08] Michael Farber.  Invitation to topological robotics, volume 8.  European Mathematical Society, 2008.
  * [FH13] William Fulton and Joe Harris.  Representation theory: a first course, volume 129.  Springer Science & Business Media, 2013.
  * [Hat01] Allen Hatcher.  Algebraic topology.  Cambridge University Press, 2001.
  * [JLL01] Gordon James, Martin W Liebeck, and Martin Liebeck.  Representations and characters of groups.  Cambridge University Press, 2001.
  * [Knu18] Ben Knudsen.  Configuration spaces in algebraic topology.  arXiv preprint arXiv:1803.11165, 2018.
  * [Ram17] Eric Ramos.  Generalized representation stability and FId-modules.  Proceedings of the American Mathematical Society, 145(11):4647–4660, 2017.
  * [Ram19] Eric Ramos.  Configuration spaces of graphs with certain permitted collisions.  Discrete & Computational Geometry, 62(4):912–944, 2019.
  * [Sin06] Dev Sinha.  The homology of the little disks operad.  arXiv preprint math/0610236, 2006.
  * [SS17] Steven Sam and Andrew Snowden.  Gröbner methods for representations of combinatorial categorie.  Journal of the American Mathematical Society, 30(1):159–203, 2017\.
  * [SS19] Steven Sam and Andrew Snowden.  Gl-equivariant modules over polynomial rings in infinitely many variables. ii.  Forum of Mathematics, Sigma, 7, 2019.
  * [Wil18] Jenny Wilson.  An introduction to FI–modules and their generalizations.  URL: http://www. math. lsa. umich. edu/~ jchw/FILectures. pdf, 2018.